Scheme

• Scheme
  • Выполнение выражений
    • Пример
  • Порядок решения
  • Организация кода
  • Дополнительные материалы
  • Further reading

В этом задании вам предстоит реализовать интерпретатор для LISP-подобного языка программирования, а именно некоторого подмножества Scheme.

Язык будет состоять из:

• Примитивных типов: целых чисел, bool-ов и символов (идентификаторов).
• Составных типов: пар и списков.
• Переменных с синтаксической областью видимости.
• Функций и лямбда-выражений.

Ваша программа должна будет выполнять выражения языка и возвращать результат выполнения.

    1 => 1
    (+ 1 2) => 3

Обозначение => в примерах здесь и далее разделяет выражение и результат его выполнения.

Выполнение выражений

Выполнение языка происходит в 3 этапа:

Токенизация - преобразует текст программы в последовательность атомарных лексем.

Синтаксический анализ - преобразует последовательность токенов в AST. AST в LISP-подобных языках программирования представляется в виде списков.

Вычисление - рекурсивно обходит AST программы и преобразует его в соответствии с набором правил.

Пример

Выражение

    (+ 2 (/ -3 +4))

в результате токенизации превратится в список токенов:

    { 
        OpenParen(),
        Symbol("+"),
        Number(2),
        OpenParen(),
        Symbol("/"),
        Number(-3),
        Number(4),
        CloseParen(),
        CloseParen()
    }

Последовательность токенов в результате синтаксического анализа превратится в дерево:

    Cell{
        Symbol("+"),
        Cell{
            Number(2),
            Cell{
                Cell{
                    Symbol("/"),
                    Cell{
                        Number(-3),
                        Cell{
                            Number(4),
                            nullptr
                        }
                    }
                }
                nullptr
            }
        }
    }

Результатом же выполнения выражения будет

    (+ 2 (/ -3 +4)) => 1

Порядок решения

Задача разделена на 5 подзадач. Подзадачи зависят от предыдущих, решать нужно только по порядку.

№	Название	Стоимость	О чем пункт
1	tokenizer	2 балла	Здесь вы напишете токенизатор - класс, который преобразует входной поток символов в последовательность токенов.
2	parser	2 балла	В этом пункте вы реализуете парсер - набор методов, который читает поток токенов и строит по ним синтаксическое дерево.
3	basic	3 балла	Имея парсер, можно описывать процесс вычисления. В простой версии не будет переменных и лямбда-функций.
4	advanced	2 балла	Здесь вы поддержите условные выражения, создание переменных и лямбда-функции, которые будут уметь захватывать контекст.
5	tidy	1 балл	При решении подзадачи advanced вы наверняка столкнетесь с утечками памяти. В advanced мы их не проверяем, чтобы не увеличивать сложность. Для избавления от утечек нужно написать свой сборщик мусора - это вы и сделаете в tidy.

Организация кода

Решение каждой подзадачи нужно писать в соответствующей поддиректории. Во всех подзадачах вы вольны менять любые файлы *.h и *.cpp в директории , в том числе удалять и создавать новые. Нельзя удалять только error.h, parser.h, scheme.h и tokenizer.h (там, где они есть), так как они включаются тестами. При добавлении нового .cpp-файла не забудьте прописать его в файле sources.cmake в каталоге подзадачи.

Дополнительные материалы

• Видеоурок введение в scheme объяснит базовые конструкции языка.

• Для погружения в язык стоит воспользоваться интерактивным интерпретатором. Такого рода среды программирования называются REPL (read-eval-print loop) и существуют для самых разных языков программирования. К сожалению, разные интерпретаторы реализуют некоторые функции Scheme по-разному. Мы рекомендуем установить mit-scheme (apt, brew) и запускать выражения в нем, либо использовать этот онлайн-интерпретатор

Further reading

• Книга Build Your Own Lisp разбирает детали реализации интерпретатора на языке C.

• Книга Crafting Interpreters разбирает реализацию интерпретатора для более сложного языка, чем LISP.