Архитектура интерпретатора

Устройство Goat изнутри: от исходного кода до результата вычисления.

Общая схема проекта

Конвейер исполнения

Каждая программа на Goat проходит следующие стадии:

Лексер

Файл Lexer.fs токенизирует исходный текст перед передачей в парсер. Поддерживаемые токены:

• Ключевые слова: let, fun, rec, if, then, else, match, with, when, lazy, force, io, type, of, in, do, return, mod, not
• Литералы: целые, вещественные, строки, булевы, unit
• Идентификаторы: строчная буква + буквенно-цифровые + _ '
• Конструкторы ADT: заглавная буква + буквенно-цифровые
• Операторы: арифметические, сравнения, логические, cons, pipe
• Комментарии: -- (строчный), {- -} (блочный)

Парсер (FParsec)

Parser.fs использует библиотеку FParsec — комбинаторный парсер для F#. Грамматика определена через комбинаторы, без явной грамматики BNF.

Приоритет операторов

Реализован через OperatorPrecedenceParser из FParsec:

Уровень	Операторы
1 (низший)	|> ~> — pipe
2	&& || — логические
3	== != /= < > <= >=
4	++ — конкатенация
5	:: — cons
6	+ -
7	* / mod
8	** — степень (право-ассоциативный)
9	not — унарное отрицание
10	унарный -
11 (высший)	применение функции f x

Структура программы

Программа — это список деклараций (Decl). Каждая декларация — это let-привязка, fun-объявление или объявление типа (type).

AST — Абстрактное синтаксическое дерево

Определён в Ast.fs. Основные типы:

-- Выражения
type Expr =
  | Lit     of Literal
  | Var     of Ident
  | Lam     of Pattern list * Expr
  | App     of Expr * Expr
  | If      of Expr * Expr * Expr
  | Match   of Expr * (Pattern * Expr option * Expr) list
  | Let     of Ident * Expr * Expr
  | BinOp   of string * Expr * Expr
  | Lazy    of Expr
  | Force   of Expr
  | List    of Expr list
  | Tuple   of Expr list
  | Range   of Expr * Expr
  | IOBlock of IOStmt list
  | Cons    of Expr * Expr

-- Декларации верхнего уровня
type Decl =
  | DLet  of Ident * Expr
  | DType of Ident * (Ident * Ident list) list

Desugar-pass

Desugar.fs нормализует AST перед вычислением. Это однопроходная трансформация дерева.

До desugaring	После
fun f x y = body	DLet("f", Lam([x, y], body))
x |> f	App(f, x)
x ~> f	App(f, Lazy(x))
fun rec f x = body	DLet("f", Fix(Lam(["f", x], body)))

Evaluator

Eval.fs — деревообходящий интерпретатор (tree-walking interpreter). Принимает Expr и Env, возвращает Result<Value, GoatError>.

Ключевые правила вычисления

Выражение	Результат
Lit l	Соответствующее runtime-значение
Var name	Поиск в окружении; ошибка если не найдено
Lam(params, body)	VClosure(params, body, env)
App(f, arg)	Вычислить f → VClosure, вычислить arg, расширить env, вычислить body
Let(x, e, body)	Вычислить e, расширить env[x=v], вычислить body
If(cond, t, f)	Вычислить cond → Bool, выбрать ветку
Match(e, cases)	Вычислить e, попробовать каждый паттерн по порядку
Lazy(e)	VThunk(Unevaluated(env, e))
Force(e)	Вычислить e → VThunk, форсировать
IOBlock(stmts)	VIO(closure) — IO-действие отложено

Тип ошибки

type GoatError =
  | RuntimeError of string * Span option
  | TypeError    of string * Span option
  | MatchError   of string
  | IOError      of string

Runtime-значения

Определены в Value.fs. Все значения языка представлены одним discriminated union:

Конструктор	Описание
VInt n	64-битное целое (int64)
VFloat f	64-битное вещественное (float)
VBool b	Булево значение
VString s	Строка
VUnit	Unit — единственный экземпляр типа ()
VNil	Пустой список []
VCons(head, tailRef)	Непустой список: голова + ссылка на ленивый хвост
VTuple values	Кортеж произвольной длины
VClosure(params, body, env)	Замыкание: параметры, тело и захваченное окружение
VBuiltin(name, fn)	Встроенная функция (F#-функция)
VCtor(name, fields)	Значение конструктора ADT
VThunk(ref)	Ленивое значение (thunk)
VIO(fn)	IO-действие: отложенная функция unit -> IOResult

Окружение (Environment)

Environment.fs — неизменяемый словарь Map<string, Value>. При каждом связывании создаётся новое окружение (persistent data structure).

type Env = Map<string, Value>

let empty   : Env = Map.empty
let extend  : Ident -> Value -> Env -> Env
let lookup  : Ident -> Env -> Result<Value, GoatError>

Функциональная чистота окружения гарантирует отсутствие мутаций при вычислении.

Pattern Matching

PatternMatch.fs реализует функцию matchPattern : Pattern -> Value -> Env -> Result<Env, …>. При успехе возвращает расширенное окружение с новыми связываниями.

Алгоритм

1. Если паттерн _ — успех, окружение не меняется.
2. Если паттерн — переменная — успех, добавить name = value.
3. Если паттерн — литерал — сравнить с ==.
4. Если p :: rest — значение должно быть VCons, рекурсивно сопоставить голову и хвост.
5. Если (p1, p2) — значение должно быть VTuple нужной длины.
6. Если Ctor args — значение должно быть VCtor с тем же именем, рекурсивно поля.
7. Гард when expr — вычислить выражение в расширенном окружении, проверить на true.

IO-система

Goat использует монадическую модель IO. IO-действия — это значения типа VIO, которые содержат отложенную функцию unit -> IOResult. Действие не выполняется до тех пор, пока интерпретатор не «запустит» его явно.

type IOResult =
  | IOOk    of Value
  | IOError of string

Семантика IO-блока

io { stmts } вычисляется в VIO(fn), где fn последовательно выполняет все инструкции:

• do! expr — вычислить expr до VIO, запустить, игнорировать значение.
• let! x = expr — запустить IO, связать результат с x.
• let x = expr — чистое вычисление, расширить локальное окружение.
• return expr — завершить IO-блок, вернуть значение.

Точка запуска

CLI вычисляет main до VIO, затем вызывает его. REPL выполняет IO автоматически при вводе IO-выражений.

Система ленивости

Goat использует явную ленивость. Thunk представлен как изменяемая ссылка на ThunkState:

type ThunkState =
  | Unevaluated of Env * Expr
  | Evaluated   of Value
  | BlackHole             -- защита от циклических вычислений

type ThunkRef = ThunkRef of ThunkState ref

Мемоизация

При первом force thunk переводится в BlackHole (защита), вычисляется, и состояние обновляется до Evaluated v. Последующие force возвращают сохранённое значение мгновенно.

Ленивые списки

VCons(head, tailRef) — голова вычислена, хвост — ThunkRef. Это позволяет строить и обрабатывать бесконечные последовательности: take форсирует ровно столько хвостов, сколько нужно.

Загрузка стандартной библиотеки

Stdlib написан на самом Goat и хранится как строка в Stdlib.fs. При старте интерпретатора:

1. Создаётся базовое окружение из встроенных функций (baseEnv).
2. Stdlib-строка парсится и десугарируется.
3. Каждая декларация вычисляется последовательно, расширяя окружение.
4. Результирующее окружение используется как начальное для пользовательского кода.

let fullEnv () : Result<Env, GoatError> =
    loadStdlib baseEnv

CLI и REPL

Команды CLI

Команда	Действие
goat run file.goat	Парсировать, вычислить, выполнить main
goat check file.goat	Парсировать и десугарировать без выполнения

REPL

REPL поддерживает многострочный ввод, историю команд и автоматическое выполнение IO-выражений. Окружение сохраняется между строками — можно определять функции в одной строке и использовать в следующей.

Тесты

138 xUnit-тестов в tests/Goat.Tests/:

Файл	Покрывает
ParserTests.fs	Парсинг всех синтаксических конструкций
EvalTests.fs	Вычисление выражений, арифметика, замыкания
PatternTests.fs	Все виды паттернов, гарды, as-паттерны
LazyTests.fs	Thunks, мемоизация, бесконечные списки
IOTests.fs	IO-блоки, do!/let!, файловые операции
StdlibTests.fs	Все stdlib-функции
IntegrationTests.fs	Полные программы end-to-end

dotnet test Goat.slnx --configuration Release

CI/CD

GitHub Actions workflow в .github/workflows/ci.yml запускается при каждом push и pull request в main:

1. Checkout репозитория
2. Setup .NET 10.0.x
3. dotnet restore
4. dotnet build --configuration Release
5. dotnet test --configuration Release
6. Smoke-тесты: запуск всех examples/*.goat

GitHub Pages собираются через .github/workflows/pages.yml: содержимое папки docs/ публикуется на gh-pages.