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

Ответ 1

Смотрите этот другой вопрос для создания макросов из набора из семи примитивов Пола Грэма.

Ответ 2

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

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

• atom

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

• eq

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

• car

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

• cdr

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

• cons

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

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

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

• quote

  Представить выражение без его оценки.

• cond

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

• lambda

  Обозначить функцию.

• label

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

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

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

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

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

Ответ 3

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

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

Для полной Тьюринга LISP я использовал объяснение Paul Grahams статьи Маккарти, и все, что вам действительно нужно:

• символ-оценка
• специальная цитата формы
• специальная форма if (или cond)
• специальная форма лямбда (похожа на цитату)
• Функция eq
• function atom
• функция cons
• функция машина
• Функция cdr
• function-dispatch (list-lambda)

Thats 10. В дополнение к этому, для реализации, которую вы можете протестировать, а не только на чертежной доске:

• функция чтения
• функция write

Thats 12. В моем Zozotez я выполнил набор и flambda (анонимные макросы, например лямбда). Я мог бы снабдить библиотеку реализацией любой динамической привязки LISP (Elisp, picoLisp), за исключением файлового ввода-вывода (потому что базовый BF не поддерживает его, кроме stdin/stdout).

Я рекомендую всем реализовать LISP1-интерпретатор как в LISP, так и (не LISP), чтобы полностью понять, как реализован язык. LISP имеет очень простой синтаксис, поэтому он является хорошей отправной точкой для синтаксического анализатора. В настоящее время я работаю над составителем схемы, написанным на схеме с разными целями (например, Сталин для цели C), надеюсь, BF как один из них.

Ответ 4

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

Ответ 5

В этом faq говорится:

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

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

Ответ 6

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

В McCarthy Micro Manual для LISP он реализует eval, используя десять.

Ответ 7

Вы просто нужна инструкция x86 MOV.

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

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

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

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

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

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