Действительно минимальный шут
Какой минимальный набор примитивов требуется для того, чтобы язык был полным по Тьюрингу и вариантом lisp?
Похоже, автомобиль, CDR и некоторые управления потоком и что-то для REPL достаточно. Было бы хорошо, если бы был такой список.
Предположим, есть только 3 типа данных, целые числа, символы и списки (как в picolisp).
5 ответов
Лямбда-исчисление завершается. У него есть один примитив - лямбда. Переводить его в синтаксис LISP довольно тривиально.
Я считаю, что минимальный набор - это то, что Джон Маккарти опубликовал в оригинальной статье.
Код.
Лучший способ узнать это наверняка - это реализовать его. Я использовал 3 лета для создания Zozotez, который представляет собой LISP McCarty-ish, работающий на Brainfuck.
Я попытался выяснить, что мне нужно, и на форуме вы найдете ветку, в которой говорится, что вам нужна только лямбда. Таким образом, вы можете сделать целый LISP в лямбда-исчислении, если хотите. Мне это показалось интересным, но вряд ли это будет путь, если вы хотите что-то, что в конечном итоге имеет побочные эффекты и работает в реальном мире.
Для полного LISP по Тьюрингу я использовал объяснение Пола Грэмса о работе Маккарти, и все, что вам действительно нужно, это:
- Символ-оценка
- специальная форма цитаты
- специальная форма if (или cond)
- специальная форма лямбда (аналог цитаты)
- функция эквалайзер
- функциональный атом
- функции минусы
- функциональная машина
- функция CDR
- функция-диспетчеризация (в основном применяется, но фактически не отображается в системе, поэтому обрабатывает список, в котором первый элемент является функцией)
Thats 10. В дополнение к этому, чтобы иметь реализацию, которую вы можете тестировать, а не только на чертежной доске:
- функция чтения
- функция записи
Thats 12. В моем Zozotez я реализовал set а также flambda (анонимные макросы, такие как лямбда), а также. Я мог бы снабдить его библиотекой, реализующей любой динамический связанный lisp (Elisp, picoLisp), за исключением файлового ввода-вывода (потому что базовый BF не поддерживает его, кроме stdin/stdout).
Я рекомендую всем реализовать LISP1-интерпретатор, как в LISP а также (not LISP), чтобы полностью понять, как язык реализован. У LISP очень простой синтаксис, так что это хорошая отправная точка. Для всех других языков программирования способ реализации интерпретатора очень похож. Например. в видео SICP мастера создают интерпретатор для логического языка, но структура и способы его реализации очень похожи на интерпретатор lisp, хотя этот язык полностью отличается от Lisp.