Техническая реализация

Как устроен интерпретатор Глаголицы изнутри: парсер, AST, вычислитель и центральная идея List-монады.

Введение

Глаголица реализована в виде интерпретатора на языке F# (.NET 10). Архитектура классическая для функциональных интерпретаторов: исходный код проходит через парсер, превращается в абстрактное синтаксическое дерево (AST), затем дерево обходится вычислителем, который порождает значения.

Парсер построен на библиотеке FParsec — это комбинаторный парсер на F#, в котором правила грамматики описываются как обычные функции. Никаких внешних кодогенераторов (yacc/bison/ANTLR) не используется.

Весь интерпретатор умещается в пять модулей:

Содержание

1. Общая схема работы интерпретатора
2. AST: модуль Ast.fs
3. Парсер: модуль Parser.fs
4. Вычислитель: модуль Evaluator.fs
5. List-монада как ядро вычислений
6. Окружение и связывание имён
7. Реализация рекурсии
8. Реализация каррирования
9. Сопоставление с образцом
10. Асинхронность
11. Структурные типы
12. Импорт модулей
13. Встроенные функции
14. TypeChecker
15. Точка входа: модуль Program.fs
16. Сборка проекта

1. Общая схема работы интерпретатора

1. Program.fs читает файл .gl и передаёт строку в Parser.parse.
2. Парсер возвращает Expr — корень AST.
3. TypeChecker.typeCheck делает поверхностную проверку (на текущем этапе — почти no-op).
4. Evaluator.eval defaultEnv ast вычисляет дерево, возвращая список значений Value list.
5. Все значения списка печатаются printValue. Список из нескольких элементов означает несколько «вселенных» — это особенность List-монады.

2. AST: модуль Ast.fs

Ast.fs определяет два типа: Pattern и Expr.

2.1. Тип Pattern

Описывает шаблоны для конструкции СОПОСТАВИТЬ ... С:

type Pattern =
    | PatWildcard            // _
    | PatEmptyList           // ПУСТО
    | PatInt of int          // целое
    | PatBool of bool        // ИСТИНА / ЛОЖЬ
    | PatString of string    // "..."
    | PatVar of string       // имя (привязка)
    | PatCons of Pattern * Pattern   // [голова - хвост]

2.2. Тип Expr

Главный тип — узлы AST. Ключевые конструкторы:

Все узлы — обычные алгебраические типы F#, поэтому AST легко обходить через сопоставление с образцом.

3. Парсер: модуль Parser.fs

Parser.fs построен на FParsec. Парсер — это композиция мелких комбинаторов, каждый из которых разбирает определённую конструкцию.

3.1. Лексические основы

• Идентификаторы — pIdent: первая буква — латинская/кириллическая или _, далее можно цифры. Ключевые слова отсеиваются проверкой isKeyword.
• Пробелы и комментарии — ws пропускает любые пробелы, однострочные комментарий: ... и многострочные комментарий { ... }.
• Литералы: pInt (через pint32), pString, pBool, pEmptyList, pPlaceholder.

3.2. Forward-references

Так как грамматика рекурсивная (выражение может содержать выражения), используется приём createParserForwardedToRef:

let pExpr, pExprRef = createParserForwardedToRef<Expr, unit> ()

Сначала объявляется ссылка pExpr, мелкие комбинаторы её используют, а в конце файла pExprRef.Value <- ... указывает фактическую реализацию.

3.3. Основные комбинаторы

3.4. Объявления функций

pLet — самый интересный комбинатор: он распознаёт как ПУСТЬ имя = выр, так и ПУСТЬ имя(а, б) { тело }. Если есть аргументы, pLet строит LetRec и применяет foldBack по аргументам, превращая многоаргументную функцию в цепочку лямбд:

let innerBody = List.foldBack (fun arg b -> Lambda(arg, b)) xs valExpr
LetRec(id, x, innerBody, EmptyList)

Это и есть автоматическое каррирование: ПУСТЬ ф(а, б, в) { ... } — это на самом деле LetRec("ф", "а", Lambda("б", Lambda("в", тело)), ...).

3.5. Операторы и приоритеты

Используется OperatorPrecedenceParser из FParsec. Уровни приоритета:

И и ИЛИ реализованы отдельно — поверх OperatorPrecedenceParser, через chainl1. Это сделано потому, что они кириллические идентификаторы и требуют ручной проверки notFollowedBy (satisfy isIdentifierChar), чтобы не съесть начало слова, которое случайно начинается на И.

3.6. Применение функций и доступ к полям

После терминального выражения «приклеивается» хвост вызовов и .поле:

pTerm .>>. many (pCallArgs <|> pFieldAcc)
|>> fun (term, operations) -> List.fold (fun acc op -> op acc) term operations

Каждый вызов с несколькими аргументами разворачивается в цепочку Application, что согласуется с каррированной формой функций.

3.7. Точка входа парсера

let parse (input: string) =
    match run (ws >>. many1 (attempt pExpr) .>> eof) input with
    | Success(result, _, _) -> if result.Length = 1 then result.Head else Block result
    | Failure(errorMsg, _, _) -> failwith errorMsg

Несколько последовательных выражений верхнего уровня оборачиваются в Block.

4. Вычислитель: модуль Evaluator.fs

Evaluator.fs — сердце интерпретатора.

4.1. Тип значений Value

type Value =
    | VInt of int
    | VFloat of float
    | VBool of bool
    | VString of string
    | VList of Value list
    | VRecord of Map<string, Value>
    | VClosure of string * Expr * Env
    | VBuiltin of string * (Value -> Value list)
    | VResult of Result<Value, Value>
    | VFuture of System.Threading.Tasks.Task<Value list>
    | VPlaceholder
    | VUnit

Несколько неочевидных деталей:

• VBuiltin возвращает Value list, а не Value — это ключевой выбор: каждое вычисление потенциально недетерминировано. Подробнее в разделе про List-монаду.
• VPlaceholder — соответствует _ и обрабатывается особым образом при applyValue.
• VFuture — обёртка над Task<Value list> для асинхронных вычислений.
• VUnit — возвращается побочными функциями (вывод), чтобы не печатать ничего лишнего.

4.2. Окружение Env

and Env = Map<string, Value>

Простая иммутабельная карта «имя → значение». Каждое связывание создаёт новый Env через Map.add, что естественно для функционального стиля и автоматически обеспечивает корректную лексическую область видимости.

4.3. Главная функция eval

Сигнатура:

eval : Env -> Expr -> Value list

Возвращает список значений, а не одно. Это позволяет одной и той же функции eval обслуживать и обычные детерминированные вычисления (список из одного элемента), и недетерминированные (ВАРИАНТЫ), и параллельные ветви.

Главный приём — использование bind:

let bind (vals: Value list) (f: Value -> Value list) = List.collect f vals

Это и есть оператор связывания >>= для List-монады. Каждое подвыражение связывается через bind, поэтому если хоть одно из подвыражений раздваивается, общий результат содержит все возможные комбинации.

Пример — сложение:

| Add(e1, e2) ->
    bind (eval env e1) (fun v1 ->
        bind (eval env e2) (fun v2 ->
            match v1, v2 with
            | VInt a, VInt b -> [ VInt(a + b) ]
            | _ -> failwith "Type error Add"))

Если e1 и e2 — детерминированные, eval вернёт список из одного элемента, и bind просто проденет результат дальше. Если же одно из них — ВАРИАНТЫ, мы автоматически получим декартово произведение.

5. List-монада как ядро вычислений

Это самая важная архитектурная идея интерпретатора. Все остальные «магические» возможности языка вырастают из неё.

5.1. Как работает недетерминизм

| Variants xs -> List.collect (eval env) xs

ВАРИАНТЫ(1, 2, 3) буквально превращается в [VInt 1; VInt 2; VInt 3]. Когда в дальнейшем коде это значение участвует в Add, bind пропускает каждое значение через продолжение по очереди — и результат тоже становится списком.

5.2. Отсечение через ТРЕБОВАТЬ

| Guard cond ->
    bind (eval env cond) (fun c ->
        match c with
        | VBool true -> [ VBool true ]   // вселенная остаётся
        | VBool false -> []              // вселенная отсекается
        | _ -> failwith "Type error")

Возврат пустого списка означает, что эта ветвь вычислений уничтожена — она не даст ни одного результата. В программах вида «найти все x, y из 1..3 такие, что x + y = 4» именно Guard, возвращая [] для несоответствующих пар, выкидывает их из итогового списка.

5.3. Цена и польза

• Польза: декларативные комбинаторные задачи пишутся естественно. Нет нужды в явных циклах и фильтрах — это всё в семантике языка.
• Цена: даже простое выражение 1 + 1 гоняется через bind со списком из одного элемента. Это накладные расходы на обёртки, но они невелики и единообразны для всего языка.

6. Окружение и связывание имён

Let — самый простой случай:

| Let(x, e1, e2) ->
    bind (eval env e1) (fun val1 ->
        let newEnv = Map.add x val1 env
        eval newEnv e2)

Однако в реальности парсер генерирует Let(x, e1, EmptyList) для простых объявлений, а сами объявления собираются в Block. Внутри Block есть отдельная логика runBlock, которая последовательно расширяет окружение:

| Let(x, e1, _) :: rest ->
    bind (eval currentEnv e1) (fun val1 ->
        runBlock (Map.add x val1 currentEnv) rest)

Это обеспечивает то, что объявления в верхнеуровневом блоке видят друг друга в линейном порядке.

7. Реализация рекурсии

Все функции в Глаголице рекурсивны по умолчанию. Это достигается через LetRec:

| LetRec(f, x, body, eContext) ->
    let rec recFunc argEnv (argValue: Value) =
        let newEnv = env |> Map.add f (VBuiltin(f, recFunc argEnv)) |> Map.add x argValue
        eval newEnv body
    let closure = VBuiltin(f, recFunc env)
    let newEnv = Map.add f closure env
    eval newEnv eContext

Хитрость в том, что recFunc помещает саму себя в окружение до вычисления тела функции. Когда внутри тела встречается имя функции f, в окружении уже есть VBuiltin(f, recFunc env), который при вызове вернёт нас в recFunc — отсюда и рекурсия.

8. Реализация каррирования

Каррирование — двухуровневое.

8.1. На уровне парсера

Многоаргументная функция превращается в цепочку лямбд (pLet / pLambda):

ПУСТЬ ф(а, б, в) { тело }

эквивалентно

LetRec("ф", "а", Lambda("б", Lambda("в", тело)), ...)

8.2. На уровне applyValue

let rec applyValue (func: Value) (arg: Value) : Value list =
    match arg with
    | VPlaceholder -> [ VBuiltin("curried", fun x -> applyValue func x) ]
    | _ ->
        match func with
        | VClosure(x, body, closureEnv) -> eval (Map.add x arg closureEnv) body
        | VBuiltin(_, f) -> f arg
        | _ -> failwith "Application error: not a function"

Если в качестве аргумента передан VPlaceholder (_), то вместо вызова возвращается новая функция, которая ждёт ещё один аргумент и подставит его на место плейсхолдера. Это и есть частичное применение.

9. Сопоставление с образцом

Проверка одного шаблона:

let rec matchPattern (pat: Pattern) (v: Value) : Env option =
    match pat, v with
    | PatWildcard, _ -> Some Map.empty
    | PatEmptyList, VList [] -> Some Map.empty
    | PatInt i, VInt iv when i = iv -> Some Map.empty
    ...
    | PatVar x, _ -> Some(Map.ofList [ (x, v) ])
    | PatCons(ph, pt), VList(h :: t) -> ...

Возвращает Some bindings, если шаблон подошёл, и привязки, которые нужно добавить в окружение. Если ни одна ветвь Match не подошла — вычисление падает с failwith "Pattern match error".

Match сводится к перебору ветвей с помощью tryBranches:

| Match(e, branches) ->
    bind (eval env e) (fun v ->
        let rec tryBranches = function
            | [] -> failwith "Pattern match error"
            | (pat, body) :: rest ->
                match matchPattern pat v with
                | Some bindings ->
                    let newEnv = Map.fold (fun ac k vv -> Map.add k vv ac) env bindings
                    eval newEnv body
                | None -> tryBranches rest
        tryBranches branches)

Здесь снова работает List-монада: если значение e — недетерминированное, bind пропустит каждый его вариант через все ветви.

10. Асинхронность

Реализована поверх System.Threading.Tasks.Task:

| Spawn e ->
    let t = System.Threading.Tasks.Task.Run(fun () -> eval env e)
    [ VFuture t ]
| Await e ->
    bind (eval env e) (fun v ->
        match v with
        | VFuture f -> f.Result
        | x -> [ x ])

Spawn запускает вычисление в Task.Run и возвращает VFuture. Await блокирует, пока задача не завершится, и возвращает её результат как обычный Value list. Если на вход ДОЖДАТЬСЯ подали не фьючер, значение возвращается как есть.

11. Структурные типы

DefineStruct ничего не делает во время выполнения ([VList []]) — определение типа существует только как пометка для читателя. Значение типа создаётся через StructInstance, которое строит VRecord(Map<string, Value>):

| StructInstance(name, fields) ->
    let rec evFields currentFields = function
        | [] -> [ VRecord(Map.ofList currentFields) ]
        | (fName, fExpr) :: xs ->
            bind (eval env fExpr) (fun fVal ->
                evFields ((fName, fVal) :: currentFields) xs)
    evFields [] fields

Доступ к полю — через FieldAccess:

| FieldAccess(e, fName) ->
    bind (eval env e) (function
        | VRecord map -> [ Map.find fName map ]
        | _ -> failwith "Not a record")

12. Импорт модулей

Import читает файл по пути, парсит его и вставляет результат:

| Import filename ->
    let code = System.IO.File.ReadAllText(filename)
    let importedExpr = GlagolLanguage.Parser.parse code
    eval env importedExpr

Если Import встречен внутри Block, его содержимое разворачивается прямо в текущий блок:

| Import filename :: rest ->
    let code = System.IO.File.ReadAllText(filename)
    let importedExpr = GlagolLanguage.Parser.parse code
    match importedExpr with
    | Block stmts -> runBlock currentEnv (stmts @ rest)
    | single -> runBlock currentEnv (single :: rest)

Это обеспечивает то, что объявления из импортированного файла видны в импортирующем.

13. Встроенные функции

Они собраны в buildMapEnv () и подставляются в defaultEnv — окружение, с которым стартует любая программа. Каждая функция представлена как VBuiltin(имя, F# функция).

Реализованные встроенные:

• Ввод/вывод: вывод, чтение, читать_файл.
• Преобразования типов: Число, Строка, Дробное. Все возвращают VResult для безопасной обработки ошибок.
• Высшего порядка: отобразить, отфильтровать, свернуть, взять_пока. Реализованы как двухуровневые VBuiltin (сначала функция, затем список) — это и есть встроенное каррирование.

Пример — отобразить:

"отобразить", VBuiltin("отобразить", fun func ->
    [ VBuiltin("отобразить1", fun lst ->
        match lst with
        | VList xs ->
            let mapped = xs |> List.collect (fun x -> applyValue func x)
            [ VList mapped ]
        | _ -> failwith "Not a list") ])

List.collect здесь — снова та же List-монада: если func возвращает несколько вариантов, все они попадают в итоговый список.

14. TypeChecker

TypeChecker.fs на текущем этапе содержит мягкую проверку типов — почти все выражения помечаются как TAny. Это плейсхолдер для будущего расширения, спроектированный так, чтобы:

1. Не мешать рантайму — typeCheck всегда возвращает true.
2. Позволить инкрементально вводить более строгие правила без ломки существующих программ.

Тип-система описана как алгебраический тип:

type Type =
    | TInt | TFloat | TBool | TString
    | TList of Type
    | TArrow of Type * Type
    | TStruct of string
    | TAny

В текущем виде TAny — это «любой тип», и почти все ветви checkExpr его и возвращают.

15. Точка входа: модуль Program.fs

Program.fs реализует CLI:

• Запуск файла (dotnet run --project src -- путь/к/файлу.gl):
  1. Проверка расширения .gl и существования файла.
  2. Чтение, парсинг, type-check, eval.
  3. Печать результирующего списка значений (или сообщение, что все вселенные отсечены).
• REPL (--repl или -i): построчное чтение с эвристикой определения многострочного ввода — если строка кончается на В, ТО, ИНАЧЕ, ->, |, или содержит СОПОСТАВИТЬ без ->, ждём продолжения. Завершение многострочного блока — по ;;.

printValue форматирует значения по типам, специально обрабатывая VResult (печатает УСПЕХ(...)/ПРОВАЛ(...)) и VUnit (ничего не печатает).

В начале main устанавливаются UTF-8 кодировки консоли — это важно для корректной работы кириллических ключевых слов в Windows.

16. Сборка проекта

<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net10.0</TargetFramework>
  </PropertyGroup>
  <ItemGroup>
    <Compile Include="Ast.fs" />
    <Compile Include="Parser.fs" />
    <Compile Include="Evaluator.fs" />
    <Compile Include="TypeChecker.fs" />
    <Compile Include="Program.fs" />
  </ItemGroup>
  <ItemGroup>
    <PackageReference Include="FParsec" Version="1.1.1" />
  </ItemGroup>
</Project>

Порядок <Compile> критичен в F#: типы и модули должны быть объявлены до использования. Поэтому Ast.fs идёт первым (типы AST), затем Parser.fs, который их использует, затем Evaluator.fs, и так далее.

Сборка и запуск:

dotnet build src
dotnet run --project src -- examples/hello.gl

Единственная внешняя зависимость — пакет FParsec версии 1.1.1.

Заключение

Глаголица построена вокруг одной простой, но мощной идеи: eval возвращает не значение, а список значений. Это позволяет в одном и том же интерпретаторе элегантно реализовать:

• обычные детерминированные вычисления (списки длины 1),
• недетерминированные вычисления через ВАРИАНТЫ/ТРЕБОВАТЬ,
• асинхронность (через VFuture, оборачивающий Task<Value list>),
• монадические цепочки (УСПЕХ / ДАЛЕЕ_УСПЕШНО),
• каррирование (через VPlaceholder и двухуровневые VBuiltin).

Парсер, написанный на FParsec, повторяет ту же функциональную композицию: грамматика собирается из мелких комбинаторов, как и AST — из мелких алгебраических конструкторов. Это и делает интерпретатор компактным: меньше 500 строк ядра при поддержке всех возможностей языка.