Как называется эта функция языка программирования и существуют ли какие-либо реальные языки, которые ее поддерживают?

Пусть древовидная структура данных определяется как таковая:

У дерева один узел в качестве корня. Узел является либо листом, либо внутренним узлом, у которого есть один или несколько узлов в качестве дочерних.

В каком-то псевдо-объектно-ориентированном языке программирования мы можем определить такое дерево:

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. Можно ли реализовать эту языковую функцию как проверку во время компиляции с нулевыми затратами во время выполнения?

programming-languages pseudocode language-theory
person DudeDoesThings    schedule 05.12.2019    source источник
comment
Это очень подробный синтаксис для чего-то, что сопоставление с образцом и алгебраические типы данных делают намного чище.   -  person SK-logic    schedule 29.01.2021

Ответы (1)


arrow_upward
2
arrow_downward

Вы описываете, что компилятор использует граф потока управления для сужения типа переменной, так что, когда оператор 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: number, которого у InnerNode нет, тогда !anyNode.isLeaf() будет работать так, как вы ожидали.)

person kaya3    schedule 05.12.2019