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

Question

На этом сайте говорят, что есть 10 примитивов LISP.Примитивы: atom, quote, eq, car, cdr, cons, cond, lambda, label, apply.

http://hyperpolyglot.wikidot.com/lisp#ten-primitives

Стивей считает, что существует семь (или пять):

Его часть чистотыидеи LISP: вам нужно всего семь (или пять?) примитивов, чтобы собрать полную машину.http://steve -yegge.blogspot.com / 2006/04 / lisp-is-not-accept-lisp.html

Какое минимальное количество примитивов для построенияМашина LISP (то есть что-то, что может запускать функцию eval / value для кода LISP)?(А какие они?)

(я могу понять, что вы могли бы жить без atom, label and apply)

Answer 1

Основные предикаты / 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-Combinator ( в соответствии с Полом Грэмом ), он добавил это для удобства и включения простая рекурсия.

---

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

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

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

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

Answer 2

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

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

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

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

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

• функция read
• function write

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

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

Answer 3

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

Answer 4

См. этот другой вопрос , чтобы создать макросы из набора 7 примитивов Пола Грэма.

Answer 5

Это часто задаваемые вопросы:

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

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

Answer 6

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

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

Answer 7

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

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

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

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

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

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

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