Каков минимальный набор примитивов, требуемых таким образом, что язык полон по Тьюрингу и вариант шепелявости?
Походит на автомобиль, CDR и некоторое управление потоком, и что-то для REPL достаточно. Это быть хорошим, если существует такой список.
Предположите, что существует только 3 типа данных, целых чисел, символов и списков. (как в picolisp)
Это хорошо обсуждается в FAQ по Lisp . Это зависит от вашего выбора примитивов. В оригинальном «Руководстве программиста LISP 1.5» Маккарти реализовано пять функций: CAR, CDR, CONS, EQ и ATOM.
лямбда-исчисление является полным по Тьюрингу. В нем есть один примитив - лямбда. Преобразование этого в синтаксис лиспа довольно тривиально.
Я считаю, что минимальный набор - это то, что Джон Маккарти опубликовал в оригинальной статье.
Код .