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

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

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

По словам Стиви, их семь (или пять):

 Its part of the purity of the idea of LISP: you only need the seven (or is it five?) primitives to build the full machine. 

http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html

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

(Я понимаю, что вы можете жить без atom, label and apply )

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

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

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

  1. atom

    Это было необходимо, потому что автомобиль и 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. В предыдущем ответе на один из ваших вопросов я объяснил, как вы можете представлять и использовать номера с этой системой.

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

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

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

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

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

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

  • Символ-оценка
  • специальная цитата из формы
  • специальная форма, если (или cond)
  • специальная форма lambda (похожая на цитату)
  • функция eq
  • атом функции
  • функция cons
  • функциональный автомобиль
  • функция cdr
  • функция-отправка (список-lambda)

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

  • функция чтения
  • функция записи

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

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

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

Этот вопрос гласит:

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

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

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

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

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

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

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

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

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

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

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

  • Spring v3 нет объявления для элемента 'mvc: resources'
  • Точечная запись в схеме
  • Считать количество элементов в списке на схеме?
  • OpenCV Orb не находит совпадений после введения инвариантов вращения / масштаба
  • Почему именно это зло?
  • Как создать весь DDL схемы Oracle (сценарий)?
  • conda, condi, conde, condu
  • В чем разница между цитатой и списком?
  • В чем разница между eq ?, eqv ?, equal ?, и = в схеме?
  • Функциональное программирование: что такое «неправильный список»?
  • Как хранить массивы в MySQL?
  • Давайте будем гением компьютера.