Сколько примитивов требуется для создания машины LISP? Десять, семь или пять?

В этом часто задаваемых вопросах говорится:

Не существует единого «лучшего» минимального набора примитивов; все зависит от реализация. Например, даже такие простые вещи, как числа не обязательно должен быть примитивным и может быть представлен в виде списков. Один возможный набор примитивов может включать CAR, CDR и CONS для управления S-выражения, READ и PRINT для ввода / вывода S-выражений и APPLY и EVAL для смелости переводчика. Но тогда вы могли бы хотите добавить LAMBDA для функций, EQ для равенства, COND для условные выражения, SET для присвоения и DEFUN для определений. ЦИТИРОВАТЬ тоже может пригодиться.

Это взято с сайта Школы информатики Карнеги-Мелон.

Основные предикаты/F-функции

Маккарти в Элементарных S-функциях и предикатах были:

1. atom

   Что было необходимо, потому что car и cdr определены только для списков, что означает, что вы не можете рассчитывать на какой-либо ответ, указывающий на то, что происходит, если вы дадите car атому.

2. eq

   Для проверки равенства между атомами.

3. car

   Для возврата первой половины (адреса) ячейки cons. (Содержимое адресного регистра).

4. cdr

   Для возврата второй половины (декремента) ячейки cons. (Содержимое регистра декремента).

5. cons

   Для создания новой ячейки cons, половина адреса которой содержит первый аргумент cons, а половина декремента - второй аргумент.

Связывает все вместе: S-функции

Затем он добавил к своей базовой нотации возможность писать то, что он назвал S-функциями:

1. quote

   Для представления выражения без его оценки.

2. cond

   Базовое условие для использования с ранее описанными предикатами.

3. lambda

   Для обозначения функции.

4. label

   Хотя для рекурсии это не нужно, он мог не знать о Y-комбинаторе (согласно Полу Грэму), он добавил это для удобства и для простой рекурсии.

Таким образом, вы видите, что он фактически определил 9 основных "операторов" для своей машины Lisp. В предыдущем ответе на другой ваш вопрос я объяснил, как можно представлять числа и оперировать ими с помощью этой системы.

Но ответ на этот вопрос действительно зависит от того, что вы хотите получить от своей Lisp-машины. Вы можете реализовать его без функции label, поскольку вы можете просто функционально компоновать все, и получить рекурсию путем применения Y-комбинатора.

atom можно отбросить, если определить операцию car над атомами так, чтобы она возвращала NIL.

По сути, вы можете иметь машину LISP Маккарти с 7 из этих 9 определенных примитивов, но вы можете, якобы, определить более сжатую версию в зависимости от того, сколько неудобств вы хотите себе причинить. Мне вполне нравится его машина или множество примитивов в более новых языках, таких как Clojure.

Маккарти использовал семь операторов для определения исходного Лиспа: quote , atom , eq , car , cdr , cons и cond . Эта статья повторяет его шаги.