Хочу реализовать интерпретатор схем для изучения SICP

Сам SICP имеет несколько разделов, подробно описывающих, как создать метакруговой интерпретатор, но я бы посоветовал вам взглянуть на следующие две книги для получения лучших ресурсов по интерпретаторам Scheme: Языки программирования: применение и интерпретация и Основы языков программирования . Их легко читать, и они постепенно проведут вас через создание интерпретаторов.

Я бы порекомендовал серию блогов Схема с нуля, в которой поэтапно создается интерпретатор схем в С.

Книга Кристиана Квиннека Lisp In Small Pieces превосходна. Более современный, чем EoPL. Охватывает как Lisp, так и Scheme, и подробно описывает кровавые низкоуровневые вещи, опущенные в большинстве книг.

Я бы рекомендовал прочитать диссертацию Кента Дибвига "Три модели реализации для схемы". Не вся диссертация, но первая часть (до главы 3), где он обсуждает Heap-Based Model, очень подходит для наивной реализации Scheme.

Еще один замечательный ресурс (если я правильно его понял и вы хотите реализовать его на C) — это Нильса Холма "Схема 9 из пустого пространства" . Эта ссылка ведет на страницу Нильса, а внизу есть ссылка на старое общедоступное издание книги и на более новое, более легкое для чтения, коммерчески доступное издание. Прочитал оба и полюбил их.

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

1. Для каждой введенной строки схемы создается объект Command. Если команда является частичной, то сохраняется ее уровень вложенности (количество оставшихся правых скобок для завершения выражения). Если команда завершена, создается объект Expression Object, и оценщики запускаются для этого объекта.
2. Определено 4 типа классов оценщиков, каждый из которых является производным от базового класса Evaluator.

а) Define_Evaluator: для операторов определения

б) Funcall_Evaluator: для обработки других пользовательских функций.

c) Read_Evaluator: для чтения выражения и преобразования его в объект схемы.

г) Print_Evaluator: печатает объект в зависимости от типа объекта.

e) Eval_Evaluator: выполняет фактическую обработку выражения.

3.-> Сначала каждое выражение считывается с помощью Read Evaluator, который создает объект схемы из выражения. Вложенные выражения вычисляются рекурсивно, пока выражение не будет завершено.

-> Далее запускается Eval_Evaluator, который обрабатывает объект выражения схемы, сформированный на первом этапе. это происходит так

а) если оцениваемое выражение является символом. Верните его значение. Поэтому переменная blk вернет объект для этого блока.

б) если вычисляемое выражение является списком. Распечатайте список.

c) если вычисляемое выражение является функцией. Найдите определение функции, которая вернет оценку, используя Funcall_Evaluator.

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

Отказ от ответственности. Так работает мой интерпретатор, так быть не должно.

Я был в аналогичной миссии, но несколько лет спустя, рекомендации:

• Схема Питера Мишо с нуля: http://michaux.ca/articles/scheme-from-scratch-introduction и его репозиторий на github: https://github.com/petermichaux/bootstrap-scheme/blob/v0.21/scheme.c. К сожалению, его королевская схема, похоже, застопорилась. Были обещания ВМ, что с его ясностью объяснений было бы здорово.
• Питер Норвигс lis.py: http://norvig.com/lispy.html, хотя и написан на питоне, очень понятен и использует все преимущества использования динамического слабо типизированного языка для создания другого. У него есть следующая статья, в которой добавлены более продвинутые функции.
• Энтони С. Хэй использовал lis.py как источник вдохновения для создания реализации на C++: http://howtowriteaprogram.blogspot.co.uk/2010/11/lisp-interpreter-in-90-lines-of-c.html
• Более полной реализацией является схема чиби: http://synthcode.com/scheme/chibi/, которая включать виртуальную машину, но кодовая база все еще не слишком велика для понимания.

Я все еще ищу хорошие сообщения в блогах о создании виртуальной машины lisp/scheme, которая может быть связана с JIT (важно для любой конкурентной реализации JS :).

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