Семантический анализ: области видимости, таблицы символов, разрешение имён

Парсер из статьи 02 с удовольствием разберёт вот это:

fn main() {
  let total = subtotal + tax;
  print totl;
}

Дерево построится безупречно: скобки сбалансированы, точки с запятой на месте, приоритеты расставлены. И при этом программа бессмысленна — subtotal и tax никто не объявлял, totl опечатка, а объявленный total не использован ни разу. Синтаксис говорит, что текст построен правильно; о том, что текст что-то значит, синтаксис не говорит ничего. Фазу, которая закрывает этот разрыв, называют семантическим анализом, и её центральная задача — разрешение имён: для каждого вхождения идентификатора найти то единственное объявление, к которому оно относится, а если такого нет — сказать об этом человеческим языком. В конце статьи мы напишем резолвер для языка Mini: он ловит пять классов ошибок, раздаёт переменным номера ячеек в кадре вызова и заранее вычисляет, какие переменные будут захвачены замыканиями. Проверку типов оставляем статье 05 — это отдельный и гораздо более объёмный сюжет.

Что именно проверяет семантический анализ

Первые три группы — чистый обход дерева, это тема сегодняшнего дня. Четвёртая требует графа потока управления: определённое присваивание в Java и C# проверяется решением системы уравнений над графом, а не обходом AST, — территория статей 06 и 07. Пятая — вообще не проверки, а данные для кодогенератора.

Почему это отдельная фаза, а не строчка в грамматике

Контекстно-свободные грамматики по построению не умеют «помнить» произвольный набор ранее увиденных имён: их память — стек магазинного автомата, а нужен словарь неограниченного размера с произвольным доступом. Формально язык «программы, в которых каждый идентификатор объявлен» контекстно-зависимый — см. «Автоматы и формальные языки». Один раз границу между парсером и семантикой нарушили: в C строка A * B; это либо объявление указателя B на тип A, либо выражение «умножить A на B», и что именно — зависит от того, объявлен ли A через typedef, то есть от таблицы символов. Парсер вынужден спрашивать у семантической фазы; приём называется the lexer hack. Мораль: если разбор зависит от смысла, фазы больше не разделяются и весь фронтенд усложняется в разы. Языки, спроектированные позже (Go, Rust, Swift), синтаксис устроили так, чтобы этой зависимости не возникало.

Область видимости: связывание имени с объявлением

Три понятия полезно держать раздельно: объявление — место, где имя вводится (let n = 10;, параметр, имя функции); вхождение — место, где имя используется (n * 2); область видимости — участок программы, в котором данное объявление доступно для вхождений. Разрешение имён есть функция из вхождений в объявления. Это ровно то же различие свободных и связанных переменных, что и в лямбда-исчислении: в λx. x y переменная x связана абстракцией, y свободна. Только вместо λ у компилятора блоки, функции и модули.

Лексическая (статическая) область видимости означает, что область определяется положением объявления в тексте и вычисляется, ничего не запуская, — именно поэтому резолвер возможен как статический проход. При динамической имя разрешалось бы по стеку вызовов во время работы: функция show, печатающая x, брала бы x того, кто её вызвал. По умолчанию такой механизм почти вымер — функция перестаёт быть понятной локально, — но как дополнительный он жив: контекст запроса в веб-фреймворках, contextvars в Python, thread-local storage, binding в Clojure, обработчики исключений, только явно и опционально.

На схеме важны две вещи. Вложенность областей в тексте один в один превращается в связный список во время анализа — родительский указатель есть материализованная вложенность. И область блока не создаёт нового кадра вызова, поэтому номера ячеек (слотов) продолжают нумерацию функции: область — понятие фазы анализа, кадр — понятие рантайма, совпадать они не обязаны.

Таблица символов: структура, операции, стоимость

Таблица символов — отображение «имя → всё, что компилятор знает про это имя»: вид (переменная, функция, тип, модуль), позиция объявления, тип, изменяемость, видимость наружу, номер ячейки, размер, выравнивание. Интерфейс минимален и одинаков у всех: begin_scope, end_scope, declare(name, info), lookup(name). Реализаций по существу две. Цепочка хеш-таблиц: у каждой области свой словарь и указатель на родителя — просто, прозрачно и легко сохранить область целиком, что нужно для LSP и отложенного анализа тел функций (так устроен go/types и наш резолвер ниже). Одна таблица со стеками и журналом отката: глобальный словарь «имя → стек символов», declare кладёт символ на стек и пишет имя в журнал области, end_scope снимает всё, что в журнале; поиск — одно обращение независимо от глубины (классика «драконьей книги» и, с вариациями, IdentifierResolver в Clang).

Полный проход стоит O(n·d) для первой схемы и O(n) для второй, но на практике разницы почти нет: d в реальном коде редко превышает 8–10. Берите первую, если фронтенд должен переиспользоваться инструментами (статья 13), вторую — если важна скорость однопроходной компиляции. Третий вариант, персистентная таблица, вообще не нуждается в end_scope — вы продолжаете пользоваться старой версией словаря; declare дорожает до O(log n), зато анализ становится чистой функцией и бесплатно откатывается, что бесценно для спекулятивного разбора в IDE (персистентные структуры).

Обратите внимание на разделение Scope и Frame: область — про текст, кадр — про рантайм. Один кадр обслуживает много вложенных областей, и именно кадр владеет нумерацией слотов.

Порядок объявлений: где языки расходятся сильнее всего

Как только имя разрешено использовать до объявления, нужны минимум два прохода — сначала собрать объявления, потом разрешить тела. Без этого невозможна взаимная рекурсия: в паре is_even/is_odd первая функция ссылается на вторую, которой в таблице ещё нет. В нашем резолвере это две строчки в методе body. Для let мы этого специально не делаем: у переменной есть инициализатор, выполняемый по порядку, и «подъём» превратил бы понятную ошибку в чтение мусора. Ровно эту границу проводит Rust.

Резолвер для Mini: рабочий код

Расширим язык из статьи 00 блоками и функциями:

decl   := "fn" IDENT "(" params? ")" block | stmt
stmt   := "let" IDENT "=" expr ";" | "print" expr ";" | "return" expr ";" | block
block  := "{" decl* "}"
factor := NUMBER | IDENT | IDENT "(" args? ")" | "(" expr ")"

Узлы AST берём из статьи 03: Num, Var, Bin, Call, Let, Print, Return, Block, FnDecl; от них нужны два поля — line для сообщений и nid, стабильный номер узла на весь конвейер.

from difflib import get_close_matches

class Symbol:
    def __init__(self, name, kind, line, slot, frame, arity=-1, ready=True):
        self.name, self.kind, self.line = name, kind, line     # kind: var | param | fn
        self.slot, self.frame, self.arity = slot, frame, arity
        self.ready, self.used, self.captured = ready, False, False

class Frame:
    """Кадр функции: нумерация ячеек и список захваченных переменных."""
    def __init__(self, name):
        self.name, self.next_slot, self.max_slots, self.upvalues = name, 0, 0, []

    def alloc(self):
        self.next_slot += 1
        self.max_slots = max(self.max_slots, self.next_slot)
        return self.next_slot - 1

    def upvalue(self, sym):
        names = [u[0] for u in self.upvalues]
        if sym.name in names:
            return names.index(sym.name)               # уже захвачена — тот же индекс
        self.upvalues.append((sym.name, sym.frame.name))
        return len(self.upvalues) - 1

class Scope:
    def __init__(self, parent, kind, frame):
        self.parent, self.kind, self.frame, self.names = parent, kind, frame, {}

Дальше сам резолвер. Ошибки здесь копятся, а не бросаются, а дубликат имени ищется только в текущей области — иначе любое законное перекрытие стало бы ошибкой.

class Resolver:
    def __init__(self):
        self.globals = Frame("<global>")
        self.scope = Scope(None, "global", self.globals)
        self.frames, self.diags, self.refs = [self.globals], [], {}

    def say(self, sev, line, msg, hint=""):
        self.diags.append((line, sev, msg, hint))      # не бросаем исключение — копим

    def push(self, kind, frame=None):
        self.scope = Scope(self.scope, kind, frame or self.scope.frame)

    def pop(self):
        live = list(self.scope.names.values())
        for s in live:
            if not s.used and s.kind == "var":
                self.say("предупреждение", s.line, f"{s.name!r} объявлена, но не используется")
        if self.scope.kind == "block":                 # слоты блока освобождаются
            self.scope.frame.next_slot -= sum(1 for s in live if s.kind != "fn")
        self.scope = self.scope.parent

    def declare(self, name, kind, line, arity=-1, ready=True):
        if name in self.scope.names:                   # дубликат ищем ТОЛЬКО в текущей области
            first = self.scope.names[name]
            self.say("ошибка", line, f"имя {name!r} уже объявлено в этой области",
                     f"первое объявление — строка {first.line}")
            return first
        outer = self.find(name)
        if outer is not None and self.scope.parent is not None:
            self.say("предупреждение", line, f"{name!r} перекрывает имя из внешней области",
                     f"внешнее объявление — строка {outer.line}")
        slot = self.scope.frame.alloc() if kind != "fn" else -1
        sym = self.scope.names[name] = Symbol(name, kind, line, slot, self.scope.frame, arity, ready)
        return sym

    def find(self, name):
        s = self.scope
        while s is not None:                           # подъём по цепочке до первого попадания
            if name in s.names:
                return s.names[name]
            s = s.parent
        return None

    def visible(self):
        out, s = set(), self.scope
        while s is not None:
            out |= set(s.names); s = s.parent
        return out

Сердце фазы — resolve_name: здесь решается, во что превратится имя.

    def resolve_name(self, n, name, line):
        sym = self.find(name)
        if sym is None:
            near = get_close_matches(name, self.visible(), n=1, cutoff=0.6)
            self.say("ошибка", line, f"неизвестное имя {name!r}",
                     f"возможно, вы имели в виду {near[0]!r}" if near else "")
            return None
        if not sym.ready:
            self.say("ошибка", line, f"{name!r} используется в собственном инициализаторе",
                     "значение ещё не вычислено — перенесите объявление выше")
            return None
        sym.used = True
        if sym.kind == "fn":
            self.refs[n.nid] = ("fn", 0)
        elif sym.frame is self.globals:
            self.refs[n.nid] = ("global", sym.slot)
        elif sym.frame is self.scope.frame:
            self.refs[n.nid] = ("local", sym.slot)
        else:                                          # пересекли границу функции — это захват
            sym.captured = True
            self.refs[n.nid] = ("upvalue", self.scope.frame.upvalue(sym))
        return sym

    def resolve(self, n):                              # компактная замена паттерна Visitor
        getattr(self, "v_" + type(n).__name__)(n)

    def v_Num(self, n):    pass
    def v_Var(self, n):    self.resolve_name(n, n.name, n.line)
    def v_Bin(self, n):    self.resolve(n.left); self.resolve(n.right)
    def v_Print(self, n):  self.resolve(n.value)
    def v_Return(self, n): self.resolve(n.value)
    def v_Block(self, n):  self.push("block"); self.body(n.stmts); self.pop()

    def v_Let(self, n):
        sym = self.declare(n.name, "var", n.line, ready=False)
        self.resolve(n.init)                           # инициализатор НЕ видит своё имя
        sym.ready = True

    def v_Call(self, n):
        for a in n.args:
            self.resolve(a)
        sym = self.resolve_name(n, n.callee, n.line)
        if sym is None:
            return
        if sym.kind != "fn":
            self.say("ошибка", n.line, f"{n.callee!r} — не функция, вызвать нельзя")
        elif len(n.args) != sym.arity:
            self.say("ошибка", n.line, f"{n.callee!r} принимает {sym.arity} арг., передано {len(n.args)}",
                     f"объявлена в строке {sym.line}")

    def v_FnDecl(self, n):
        n.frame = Frame(n.name)                        # кадр пригодится кодогенератору
        self.frames.append(n.frame)
        self.push("function", n.frame)
        for p in n.params:
            self.declare(p, "param", n.line)
        self.body(n.body.stmts)
        self.pop()

    def body(self, stmts):
        for s in stmts:                                # проход 1: подъём объявлений функций
            if isinstance(s, FnDecl):
                self.declare(s.name, "fn", s.line, arity=len(s.params))
        for s in stmts:                                # проход 2: всё остальное по порядку
            self.resolve(s)

    def run(self, program):
        self.body(program); self.pop()
        self.diags.sort()                              # диагностики — в порядке файла
        return self.diags

Скармливаем резолверу программу с ошибками: fn add(a, b) в строке 1; fn outer() со вложенной fn inner() в строках 4–10, где inner захватывает n из внешней функции; fn main() в строках 12–22, где let x = x + 1; в строке 15 читает себя же, let y = 2; в 16 не используется, let z = add(x); в 19 передаёт один аргумент вместо двух, а print zz; в 20 содержит опечатку.

[ошибка] строка 15: 'x' используется в собственном инициализаторе
    подсказка: значение ещё не вычислено — перенесите объявление выше
[предупреждение] строка 15: 'x' перекрывает имя из внешней области
    подсказка: внешнее объявление — строка 13
[предупреждение] строка 16: 'y' объявлена, но не используется
[ошибка] строка 19: 'add' принимает 2 арг., передано 1
    подсказка: объявлена в строке 1
[ошибка] строка 20: неизвестное имя 'zz'
    подсказка: возможно, вы имели в виду 'z'

кадр <global>   ячеек: 0  захвачено: []
кадр add        ячеек: 2  захвачено: []
кадр outer      ячеек: 1  захвачено: []
кадр inner      ячеек: 0  захвачено: [('n', 'outer')]
кадр main       ячеек: 3  захвачено: []

В выводе три отдельных достижения. Пять диагностик за один проход, а не «первая ошибка и выход» — резолвер нигде не бросает исключение, а записывает сообщение, возвращает None и продолжает. Приём называется отравленным символом (poison symbol): дальше по конвейеру гуляет заглушка, а все проверки, которые её касаются, молчат, чтобы не порождать каскад вторичных ошибок. кадр main ячеек: 3, хотя переменных объявлено четыре (x, внутренний x, y, z) — слоты внутреннего блока освобождаются на pop() и переиспользуются под z; это и есть уменьшение кадра стека, то, что позже станет заботой распределителя регистров (статья 08). кадр inner захвачено: [('n', 'outer')] — резолвер понял, что inner обращается к переменной чужого кадра, ещё до запуска программы.

Что резолвер оставляет после себя

После фазы у каждого вхождения имени есть Ref, и дальше по конвейеру имён больше нет — есть номера: это не оптимизация, а необходимость, потому что искать строку в хеш-таблице на каждое обращение к переменной в десятки раз дороже, чем прочитать frame[2]. Виртуальная машина (статья 09) превращает ("local", slot) в LOAD_LOCAL slot (чтение по индексу в кадре), ("upvalue", idx) в LOAD_UPVAL idx (одна лишняя косвенность), ("global", slot) в чтение из массива глобалов, а ("fn", …) — в прямой вызов по статически известному адресу. Ровно эта схема — в CPython: LOAD_FAST, LOAD_DEREF и LOAD_GLOBAL; разница в их стоимости — причина известного приёма «положи len в локальную переменную перед горячим циклом». Пара «сколько границ пересекли, номер слота» — по сути обобщение индексов де Брёйна из лямбда-исчисления, и после такой замены альфа-эквивалентные программы становятся буквально одинаковыми структурами.

Отдельный вопрос — куда складывать результат. Мутировать узел (node.ref = ...) быстро и просто, но AST перестаёт быть неизменяемым и его нельзя разделять между потоками или переиспользовать между инкрементальными пересборками. Боковая таблица nid → Ref, как у нас, оставляет дерево чистыми данными, допускает несколько независимых результатов и позволяет всё выбросить и пересчитать — именно поэтому в rustc есть NodeId/HirId. Ключом такой таблицы не должен быть адрес объекта (id(node) в Python, указатель в C): сборщик мусора освободит узел, адрес переиспользуется, и таблица начнёт тихо врать.

Замыкания: когда имя переживает свою область видимости

Пока функции не были значениями, всё было просто: вышли из кадра — переменные исчезли. С вложенными функциями, которые можно вернуть наружу, возникает конфликт: n живёт в кадре outer, а inner продолжает к ней обращаться после того, как outer завершилась.

Языки решают конфликт тремя способами. Запретить: ранний C, вложенных функций нет. Всё захваченное сразу в кучу: компилятор помечает переменную как ячейку (cell) и размещает вне кадра с самого начала — так делают CPython (cellvars/freevars) и большинство реализаций JavaScript; дёшево, но каждая захваченная переменная это лишняя аллокация и работа для сборщика мусора. Открытые и закрытые upvalue: пока кадр жив, замыкание указывает прямо в его слот, при выходе значение «закрывается» — переносится в саму запись upvalue (The Implementation of Lua 5.0).

Третий вариант оптимален, потому что подавляющее большинство захватов свой кадр не переживает. Здесь же появляется escape-анализ: компилятор Go именно так решает, разместить значение на стеке или в куче (go build -gcflags=-m покажет решение по каждой переменной).

Второй вопрос, который фаза обязана прояснить, — захват по значению или по ссылке. В Python funcs = [lambda: i for i in range(3)] даёт три функции, возвращающие 2: все замыкания захватили одну и ту же переменную i, а не три её значения. В Go до 1.22 действовало то же правило и было самой частой ошибкой в языке; в 1.22 переменную цикла стали создавать заново на каждой итерации (loopvar), в JavaScript ту же проблему решили в 2015-м посвязочной семантикой let, а Rust сделал захват явным (move) и с редакции 2021 захватывает не переменную целиком, а только используемые поля (disjoint capture). Подробнее — в функциональной парадигме и в статье о стратегиях вычисления.

Пространства имён, модули и квалифицированные имена

До сих пор отображение было одно, «строка → символ». В реальных языках их несколько и они независимы: в Scheme функция и переменная делят одно пространство ((define list ...) затирает встроенный list), в Common Lisp — разные, поэтому нужны #' и funcall; в C пространств четыре (идентификаторы, теги struct/union/enum, метки goto, члены структуры), поэтому struct stat stat; легален; Rust разделяет типы, значения и макросы.

Модули добавляют второе измерение — квалифицированные имена (math.sqrt, std::vec::Vec): сначала найти модуль-контейнер, затем искать в его таблице экспорта. Отсюда граф импортов, где циклы либо запрещены, либо требуют аккуратного порядка инициализации, а их обнаружение — поиск в глубину с цветами (обход графов, теория графов); отсюда же неоднозначность use a::*; use b::*;, когда оба экспортируют Foo. И отсюда же гигиена макросов: раскрытие с временной tmp при пользовательском tmp захватит имя — та же беда, что при наивной подстановке в лямбда-исчислении, и лечится тем же переименованием. syntax-rules и macro_rules! гигиеничны по построению, препроцессор C — нет (см. метапрограммирование).

Диагностика: чем хороший резолвер отличается от рабочего

• Не останавливаться на первой ошибке и не порождать каскад. Возвращать None вместо исключения, а зависящие проверки типов подавлять — стандартный приём — тип-заглушка (error type), совместимая со всем.
• Подсказывать похожее. get_close_matches — это расстояние Левенштейна под обёрткой (строковые алгоритмы). Ограничьте кандидатов видимыми именами: подсказка про недоступный символ хуже её отсутствия.
• Показывать оба места. «Имя уже объявлено» бесполезно без «первое объявление — строка N»; ради этого символ и хранит line. И различать серьёзность: перекрытие имени и неиспользуемая переменная — не ошибки, а повод задуматься; смешаете с настоящими ошибками — предупреждения начнут игнорировать целиком.
• Сортировать по позиции. Диагностики рождаются в порядке обхода: предупреждение о неиспользуемой переменной возникает при закрытии области, то есть заведомо позже. Без сортировки вывод выглядит хаотично.

Эргономика сообщений — тема статьи 12; эталон — диагностика rustc с подчёркиванием фрагмента и предлагаемым исправлением.

Производительность и инкрементальность

Интернирование строк: лексер (статья 01) кладёт каждое уникальное имя в глобальную таблицу, и дальше по конвейеру гуляет 32-битный идентификатор — сравнение имён превращается в сравнение целых, хеширование в тождественную функцию (Symbol в rustc, IdentifierInfo в Clang). Арены вместо россыпи объектов: символы, области и узлы AST живут ровно столько, сколько идёт компиляция единицы трансляции, и удаляются все разом, а аллокация из непрерывного блока даёт локальность (см. иерархию памяти). Инкрементальность: языковой сервер не может пересчитывать проект на каждое нажатие клавиши, отсюда разделение на сигнатурную часть (меняется редко) и тела функций (меняются постоянно, но наружу не влияют) плюс кэширование с отслеживанием зависимостей — rustc и rust-analyzer построены на системе запросов salsa (статья 13).

Как это устроено в настоящих компиляторах

CPython делает ровно нашу работу в проходе Python/symtable.c между построением AST и генерацией байткода, и этот проход открыт наружу модулем symtable: для def outer(a): n = a + g; def inner(): return n * 2 он пометит a параметром, n локальной в outer и свободной в inner, а g глобальной. «Свободная» — это в точности наш ("upvalue", 0), и именно из неё выведется LOAD_DEREF вместо LOAD_FAST: вся разница между быстрым и медленным доступом решается здесь, задолго до исполнения (сравните с python -m dis).

rustc строит стек «рёбер» (ribs) — буквально нашу цепочку областей, только с отдельными стеками для типов, значений и макросов; результат — отображение NodeId → Res (dev guide). TypeScript называет фазу binder (src/compiler/binder.ts): она создаёт объекты Symbol, связывает их с объявлениями и заодно строит граф потока управления для сужения типов (обзор архитектуры). Clang совмещает разрешение имён с разбором в классе Sema (наследие C), а роль области видимости играет DeclContext (Internals Manual). Go даёт явные объекты Scope с методом Lookup в пакете go/types, корнем цепочки служит Universe со встроенными именами (спецификация).

Типичные ошибки реализации

• Искать имя во всей цепочке при проверке на дубликат. Дубликат ищется только в текущей области, иначе любое законное перекрытие станет ошибкой.
• Объявлять имя после разбора инициализатора. Тогда let x = x; тихо возьмёт внешний x вместо понятной ошибки. Объявляйте сразу, но с флагом «не готово».
• Путать область и кадр. Новый кадр на каждую область — лишние аллокации и сломанный доступ по фиксированному смещению; не освобождать слоты при выходе из блока — кадр раздувается пропорционально сумме всех блоков вместо максимума по вложенности.
• Ключевать боковую таблицу адресом объекта. После сборки мусора адрес переиспользуется, и таблица начинает возвращать чужие данные.
• Помечать used при объявлении, а не при обращении. Предупреждения о неиспользуемых переменных перестают работать, а вместе с ними и устранение мёртвого кода (статья 07).
• Считать, что все языки одинаковы. Прежде чем писать резолвер, ответьте на три вопроса: можно ли использовать имя до объявления, разрешено ли перекрытие в одной области, сколько у языка независимых пространств имён. От ответов зависит вся структура фазы.

Источники

• Robert Nystrom, Crafting Interpreters: главы Resolving and Binding и Closures — ближайший к этой статье текст.
• Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, разделы 2.7 и 7.1 — таблицы символов и записи активации; Cooper, Torczon, Engineering a Compiler, гл. 5 — вариант с журналом отката.
• Модуль symtable — docs.python.org/3/library/symtable.html; rustc dev guide, Name resolution — rustc-dev-guide.rust-lang.org/name-resolution.html.
• The Implementation of Lua 5.0 — lua.org/doc/jucs05.pdf: происхождение открытых и закрытых upvalue.
• ECMAScript, let and const declarations — tc39.es/ecma262: формальное определение временной мёртвой зоны.

Мини-итог

Семантический анализ существует потому, что грамматика физически не способна выразить «имя объявлено»: это контекстно-зависимое условие, а парсер работает с контекстно-свободными языками. Центральный механизм — таблица символов, цепочка отображений «имя → символ», где вложенность областей из текста превращается в связный список с родительскими указателями; поиск идёт снизу вверх до первого попадания, сложность — O(n·d) при цепочке хеш-таблиц и O(n) при одной таблице с журналом отката. Результат фазы — не только диагностика: каждое вхождение имени превращается в координату «вид, номер», имена исчезают из программы, кадры получают размер, а захваченные переменные помечаются задолго до создания замыкания. Разделяйте область видимости и кадр вызова, объявляйте имя до разбора инициализатора и с флагом «не готово», не падайте на первой ошибке — и половина неприятностей следующих фаз не возникнет вовсе.

Что дальше

Имена связаны, каждое вхождение знает своё объявление — но о значениях мы по-прежнему не знаем ничего: ничто не мешает написать let x = true + 1; или передать строку туда, где ждут число. Следующая статья — о том, как компилятор приписывает выражениям типы, проверяет их согласованность и в лучших системах выводит их сам: правила типизации, унификация, алгоритм Хиндли — Милнера и то, почему он выводит тип функции, у которой не написано ни одной аннотации.

Проверка и вывод типов: системы типов, унификация, Хиндли-Милнер