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

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

Маккарти ' s элементарные S-функции и предикаты было:

1. atom

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

2. eq

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

3. car

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

4. cdr

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

5. cons

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

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

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

1. quote

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

2. cond

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

3. lambda

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

4. label

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

---

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

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

atom может быть отброшен, если вы определили элемент car операция по возврату атомов NIL.

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

лучший способ на самом деле знать это наверняка, если вы его реализуете. Я 3 лета, чтобы создать Zozotez который является Маккарти-иш Лисп работает на Brainfuck.

Я попытался выяснить, что мне нужно, и на форуме вы найдете тему, которая говорит вам нужна только лямбда. таким образом, вы можете сделать целый Лисп в лямбда-исчислении I вы хотели бы. Я нашел это интересным, но это вряд ли путь, если вы хотите что-то, что в конечном итоге имеет сторону эффекты и работает в реальном мире.

для полного Лиспа Тьюринга я использовал объяснение пола Грэхема статьи Маккарти и все, что вам действительно нужно, это:

• символ-оценка
• специальная форма цитата
• специальная форма if (или cond)
• специальная форма лямбда (аналогично цитате)
• функция eq
• функция atom
• минусы функция

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

этой faq состояния:

нет единого" лучшего " минимального набора примитивов; все зависит от реализация. Например, даже что-то как цифры не обязательно быть примитивным, а может быть представлен в виде списков. Один из возможных набор примитивов может включать автомобиль, CDR и минусы для манипулирования S-выражения, чтение и печать для ввода / вывода S-выражений и подать заявку и EVAL для кишок переводчика. Но тогда вы можно хотите добавить лямбда для функций, эквалайзер для равенства, COND для условные обозначения, заданные для присвоения и DEFUN для определений. ЦИТАТА может пригодиться также.

это исходит из Школы компьютерных наук, веб-сайт Карнеги дыни.

Пол Грэм реализует eval с помощью семь.

В микро-руководстве Маккарти для LISP он реализует eval с помощью десять.

вы просто нужен x86 MOV - инструкции.

" M/o / Vfuscator (короткий 'o', звучит как "mobfuscator") компилирует программы в инструкции "mov" и только инструкции "mov". Арифметика, сравнения, прыжки, вызовы функций и все остальное, что нужно программе, выполняются с помощью операций mov; нет самомодифицирующегося кода, нет вычисления, инициируемого транспортом, и никакой другой формы обмана без mov."

серьезно хотя эти примитивы не будут реализовывать машину Lisp. Машина нуждается в таких средствах, как ввод-вывод и сбор мусора. Не говоря уже о механизме вызова функции! Хорошо, у вас есть семь примитивов, которые являются функциями. Как машина вызывает функцию?

правильное понимание того, что эти примитивы делают возможным то, что они разоблачение набор инструкций a Универсальная Машина Тьюринга. Потому что эти инструкции "шепелявые", по скольжению язык (говорящий с шепелявостью) мы тайно называем это "машиной шепелявости". "Универсальный" означает, что машина программируется: с помощью некоторых комбинационных инструкций, применяемых к универсальной машине Тьюринга, мы можем создать экземпляр любой машины Тьюринга. Но пока все это чисто математическая конструкция.

чтобы фактически смоделировать этот UTM-реализовать его физически, чтобы исследовать его на компьютере, нам нужна машина, которая обеспечивает нам способ фактически вводить те формы, которые создавайте машины Тьюринга из комбинаций этих семи инструкций Lisp. И нам также нужна какая-то форма вывода; машина, по крайней мере, сможет сказать нам "Да", "нет" или "подождите, я все еще бегу".

также обратите внимание, что семь примитивов Грэма не имеют явной поддержки чисел, поэтому вам придется их построить вне функций (техника "церковных цифр"). Никакая производственная реализация Lisp не делает такую сумасшедшую вещь.