-исчисление
Описание
-исчисление (лямбда-исчисление) лежит в основе большинства функциональных языков программирования: семейства Лиспа (Common Lisp, Scheme, Clojure и др.) и семейства ML (Standard ML, Haskell, Agda и пр.).
-исчисление состоит из языка -выражений и набора правил преобразования. Базовые правила построения -выражений:
- переменная является -выражением;
- если — -выражение, а — переменная, то также -выражение (лямбда-абстракция);
- если и — -выражения, то также -выражение (аппликация).
Для удобства работы с -выражениями, при записи могут использоваться следующие упрощения:
- внешние скобки могут быть опущены
- ;
- аппликация считается лево-ассоциативной
- ;
- тело -выражения распространяется вправо насколько возможно
- ;
- последовательные -абстракции схлопываются в одну
- .
Оператор связывает переменную в выражении . Переменные, подпадающие под какой-либо оператор -абстракции, называются связанными. Все прочие переменные называются свободными. Например, переменная свободна в выражении . Переменная связывается ближайшим оператором . Например, единственное вхождение переменной в выражении связано со вторым оператором .
Значение -выражения определяется правилами редукции:
- -конверсия
- переименовывание связанных переменных
- -редукция
- применение функции к аргументам
- -конверсия
- выражает принцип две функции идентичны, если имеют одинаковый результат на всех входах
Применение функции к аргументам осуществляется засчёт подстановки выражения-аргумента вместо связанной переменной в теле -выражения:
Язык -выражений может быть расширен:
- базовыми типами данных (например, числа, булевы значения, строки);
- базовыми контейнерными типами (списки и кортежи);
- встроенными операциями (например, , , , , , , )
- специальными конструкциями (например, или );
- системой типов;
- пользовательские структуры данных;
- и т.д.
Минимальные требования (базовая часть)
Базовая реализация проекта, в которой должны разбираться все участники, должна:
- определять структуру данных для синтаксического дерева;
- содержать раздельно парсер и интерпретатор (с любой стратегией редукций);
- предоставлять простую интерактивную среду программирования (REPL).
Расширенный парсер (индивидуальная часть)
Расширенный парсер должен добавлять хотя бы 2 различные возможности к базовому варианту. Ниже перечислены возможные варианты расширения парсера, однако этим списком они не ограничены:
- разбор расширенного -исчисления;
- восстановление после ошибок (например, если пользователь написал запятую (
,
) вместо точки (.
), парсер может запомнить эту ошибку и продолжить разбор программы); - поддержка пользовательских инфиксных операций с возможностью задать приоритет и ассоциативность;
- и т.д.
Система типов (индивидуальная часть)
Система типов помогает определить семантику -выражений, но также может быть использована для оптимизаций при интерпретации и генерации кода.
Система типов должна поддерживать хотя бы 2 различные возможности:
- базовые типы (числа, булев тип, строки);
- контейнерные типы (списки, кортежи, суммы);
- параметрический полиморфизм;
- пользовательские типы данных;
- механизм автоматического вывода типа для терма;
- и т.д.
Расширенная интерактивная среда (индивидуальная часть)
Расширенная интерактивная среда должна добавлять хотя бы 2 различные возможности к базовому интерфейсу. Ниже перечислены возможные варианты расширения интерактивной среды, однако этим списком они не ограничены:
- команды интерпретатора:
- показать все возможные варианты редукции терма (одного шага) и выбрать один;
- показать тип выражения;
- поменять порядок редукции;
- перевести терм из/в кодировку Чёрча;
- загрузить программу из файла;
- интерпретация расширенного -исчисления;
- дружелюбные сообщения об ошибках (например, для замкнутых термов при опечатке в имени переменной можно предложить имена переменных, отличающихся одной буквой, которые находятся в области видимости);
- и т.д.
Генерация кода (индивидуальная часть)
Модуль генерации кода — предпоследний этап компиляции. Генерация кода может быть реализована многими способами, но чтобы простым образом получить портируемый компилятор, можно генерировать промежуточный код на низкоуровневом языке программирования, таком как C или еще ниже, например, LLVM.
Генерация кода должна переводить именованные -термы в соответствующие функции (для этого язык должен быть расширен возможностью именования -термов).
Демонстрация генерации кода должна включать в себя программу на любом языке, использующую сгененированный объектный код при сборке.