1

让树数据结构定义如下:

一棵树有一个节点作为它的根。节点要么是叶子,要么是具有一个或多个节点作为其子节点的内部节点。

在某种伪 OO 编程语言中,我们可以定义这样的树:

Node := InnerNode | Leaf

Leaf {

    isLeaf() : TRUE

}

InnerNode {

    isLeaf() : FALSE
    children() : List<Node>

}

Tree {
    root() : Node
}

现在我们可以定义两个函数,“bad_code”和“good_code”。函数 'bad_code' 不编译,其他函数编译:

function bad_code(Node anyNode) : void {

    // this will give a compile time error "type Node does not define method children()"
    anyNode.children();
}

function good_code(Node anyNode) : void {

    // the compiler understands that all Nodes must have a method called isLeaf() which 
    // returns a boolean
    let b : boolean <- anyNode.isLeaf();

    if (b == FALSE) {

        // this will not give a compile time error because the compiler can deduce that 
        // anyNode must be of type InnerNode which has the method children()
        anyNode.children();
    }
}

问题:

  1. 以上是否是以某种官方方式定义/描述的语言功能的示例?
  2. 如果是这样:这种语言功能的正式名称是什么?
  3. 是否有任何实现此语言功能的现实世界编程语言?
  4. 这种语言功能可以实现为运行时零成本的编译时检查吗?
4

1 回答 1

2

您所描述的是编译器使用控制流图来缩小变量的类型,以便当if语句测试与变量类型相关的条件时,可以为同一变量使用更具体的类型推断为if语句的主体。

这称为控制流类型缩小,它在例如Typescript中完成。它纯粹是静态检查,在编译时完成,没有运行时损失;事实上,Typescript 中的类型在运行时根本不可用。

type TreeNode = InnerNode | Leaf

interface Leaf {
    isLeaf: true
}

interface InnerNode {
    isLeaf: false
    children: Node[]
}

function bad_code(anyNode: TreeNode): void {
    // type error: Property 'children' does not exist on type 'TreeNode'.
    console.log(anyNode.children);
}

function good_code(anyNode: TreeNode): void {
    if (!anyNode.isLeaf) {
        // narrowed type to anyNode: InnerNode
        console.log(anyNode.children);
    }
}

请注意,Typescript 要求您以特定方式执行此操作;我们anyNode.isLeaf直接测试而不是先将其存储在变量中b: boolean,因为 Typescript 不跟踪两个变量b和之间的关系anyNode

function bad_in_typescript(anyNode: TreeNode): void {
    let b: boolean = anyNode.isLeaf;

    if (!b) {
        // type error: Property 'children' does not exist on type 'TreeNode'.
        console.log(anyNode.children);
    }
}

此外,在上面的代码isLeaf中是属性而不是方法。Typescript 确实有一个称为用户定义类型保护的相关功能,它允许方法的返回类型类似于this is Leaf,表明该方法true仅在调用类型时才返回Leaf

type TreeNode = InnerNode | Leaf

interface BaseNode {
    ifLeaf(): this is Leaf
    isInner(): this is InnerNode
}

interface Leaf extends BaseNode {}

interface InnerNode extends BaseNode {
    children(): Node[]
}

但是,Typescript 仍然比您的示例更受限制;我们必须进行测试anyNode.isInner(),因为!anyNode.isLeaf()不一定会进行相同的缩小。(Typescript 使用结构类型,因此实际上这Leaf是 的超类型InnerNode,这会导致联合类型出现一些问题。如果您提供Leaf类似value: numberwhichInnerNode没有的属性,则!anyNode.isLeaf()可以按照您的预期工作。)

于 2019-12-05T16:31:39.637 回答