fml

Небольшой язык из семейства ML, реализованный с нуля на F#. Лексер, парсер, система типов и вычислитель - полная цепочка от исходного кода до результата.

TL;DR

Маленький язык из семейства ML, построенный с нуля на F#: лексер, парсер, система типов и вычислитель - полный путь от исходного текста до результата. Самая трудная часть - система типов.

Обзор

fml - это маленький язык программирования из семейства ML, построенный с нуля на F#. У него четыре звена, которые вместе ведут от исходного текста к результату: лексер, парсер, система типов и вычислитель. Каждое делает одну вещь, но самое интересное и самое трудное - система типов.

Собственный язык - это проект, который учит смирению. Это не одна задача, а целая последовательность, в которой выход одного этапа - вход следующего, а ошибка на раннем этапе возвращается с удвоенной силой тремя шагами позже. Именно поэтому это такое хорошее упражнение в мышлении о системах.

Исходный текст нужно нарезать на токены, токены сложить в дерево, дерево проверить на типы, а в конце выполнить. Это цепь, в которой нельзя схитрить ни на одном этапе, потому что следующий сразу это выхватит - или, что хуже, не выхватит, и ошибка проявится лишь в конце как непонятный результат.

Эта зависимость этапов - одновременно и трудность, и красота проекта. Каждое звено можно понять отдельно, но лишь вместе они образуют нечто, что действительно выполняет программу. Спроектировать границы между ними так, чтобы они были чистыми, - половина успеха.

Типы, которые не нужно писать

В языке из семейства ML самое интересное - система типов. Вам не нужно писать типы вручную - компилятор сам выводит их из того, как вы используете значения. Вы пишете обычную функцию, а язык сам доходит до того, какой у неё тип, и следит, чтобы вы не использовали её вразрез с ним.

example.fml · fsharp

let rec map f xs =
  match xs with
  | [] -> []
  | x :: rest -> f x :: map f rest

map (fun n -> n + 1) [1; 2; 3]

Примечание

Нигде в этом коде мы не написали ни одного типа, и всё же язык знает, что у map тип (a -> b) -> список a -> список b. Это вывод типов - одна из самых красивых вещей, какие можно написать своими руками, и одновременно одна из самых требовательных.

Четыре этапа от текста до результата

Весь путь раскладывается на четыре шага с ясно разделёнными ролями. Текст становится токенами, токены - деревом, дерево получает типы, а в конце вычисляется. Несовпадения типов выходят на третьем этапе, ещё до запуска, а не во время работы.

Лексер

исходный текст становится потоком токенов.

Парсер

токены складываются в синтаксическое дерево.

Система типов

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

Вычислитель

дерево вычисляется до результата.

Цепь компилятора

Этап	Вход	Выход
Лексер	исходный текст	токены
Парсер	токены	синтаксическое дерево
Система типов	дерево	дерево с типами
Вычислитель	дерево	результат

Эффект: язык ML, написанный на языке ML

На выходе - маленький, но полный язык, который действительно выполняет программу - от первого символа в файле до вычисленного результата. F# был тут естественным выбором, ведь он сам принадлежит семейству ML, а писать язык ML на языке ML есть нечто приятно рекурсивное. Это проект, после которого слово "компилятор" перестаёт быть абстракцией.

Больше проектов

Другие работы из той же категории - посмотрите, как мы решаем похожие задачи.

Есть похожий проект?

Напишите нам - смета бесплатна и приходит в течение часа.