Диалект Лисп

Описание

В данном задании предлагается реализовать интерпретатор диалекта языка программирования Лисп.

Базовым объектом Лисп является S-выражение и в предлагаемом диалекте оно может быть представлено

• атомом (IAMATOM, numberp, setf),
• числовым литералом (10, 34.2),
• строковым литералом ("hello, world!"),
• пустым списком (nil, ()),
• точечной парой ((1 . 2)).

Как обычно, непустой список представляется точечной парой, вторым элементом которой является другой список: (1 "asd" atom) эквивалентно (1 . ("asd" . (atom . nil))).

Каждое S-выражение может быть вычислено по следующим правилам:

• числовые, строковые литералы, пустой список и атом вычисляются в себя;
• список (f ...) вычисляется применением функции (или раскрытием макроса) f к остальным элементам списка;
• функция перед применением вычисляет все свои аргументы;
• макросы и специальные формы не вычисляют аргументы перед применением.

Программа на этом диалекте состоит из последовательности S-выражений.

Диалект языка выражений может быть расширен:

• встроенными специальными формами:
  • quote (');
  • if;
  • let;
  • macro;
  • setf;
• пользовательскими функциями: lambda, defun;
• лексическим/динамическим связыванием;
• операциями ввода-вывода;
• функциями с переменным числом аргументов;
• и т.д.

Минимальные требования (базовая часть)

Базовая реализация проекта, в которой должны разбираться все участники, должна:

• определять структуру данных для синтаксического дерева;
• содержать раздельно парсер и интерпретатор;
• предоставлять простую интерактивную среду программирования (REPL);
• предоставлять встроенные предикаты и функции:
  • atomp, numberp, listp, =;
  • car, cdr, cons.

Расширенный парсер (индивидуальная часть)

Расширенный парсер должен добавлять хотя бы 2 различные возможности к базовому варианту. Ниже перечислены возможные варианты расширения парсера, однако этим списком они не ограничены:

• разбор расширенного диалекта;
• восстановление после ошибок (например, если пользователь написал лишнюю закрывающую скобку, парсер может запомнить эту ошибку и продолжить разбор программы);
• и т.д.

Расширенная интерактивная среда (индивидуальная часть)

Расширенная интерактивная среда должна добавлять хотя бы 2 различные возможности к базовому интерфейсу. Ниже перечислены возможные варианты расширения интерактивной среды, однако этим списком они не ограничены:

• команды интерпретатора:
  • загрузить программу из файла;
  • провести один шаг вычисления;
  • раскрыть вызовы макросов;
• интерпретация расширенного диалекта;
• дружелюбные сообщения об ошибках (например, при опечатке в имени переменной можно предложить имена переменных, отличающихся одной буквой, которые находятся в области видимости);
• и т.д.

Генерация кода (индивидуальная часть)

Модуль генерации кода — предпоследний этап компиляции. Генерация кода может быть реализована многими способами, но чтобы простым образом получить портируемый компилятор, можно генерировать промежуточный код на низкоуровневом языке программирования, таком как C или еще ниже, например, LLVM.

Генерация кода должна переводить пользовательские функции в соответствующие функции целевого языка (для этого диалект должен быть расширен возможностью определения пользовательских функций).

Демонстрация генерации кода должна включать в себя программу на любом языке, использующую сгенерированный объектный код при сборке.