Основные предикаты / F-функции
McCarthy «s Элементарные S-функции и предикаты были:
atom
Это было необходимо, потому что car и cdr определены только для списков, а это значит, что вы не можете рассчитывать на какой-либо ответ, указывающий на то, что происходило, если вы дали car
атом.
eq
Для проверки равенства между атомами.
car
Для возврата первой половины (адреса) cons-ячейки. (Содержание адресного реестра).
cdr
Для возврата второй половины (декремента) cons-ячейки. (Содержание регистра декремента).
cons
Для создания новой cons-ячейки, половина адреса которой содержит первый аргумент cons, а половина декремента - второй аргумент.
Связать воедино: S-функции
Затем он добавил к своим основным обозначениям, чтобы можно было писать то, что он называл S-функциями:
quote
Чтобы представить выражение без его оценки.
cond
Базовое условное выражение, которое будет использоваться с ранее описанными предикатами.
lambda
Для обозначения функции.
label
Хотя он не нуждался в этом для рекурсии, он мог не знать об Y-комбинаторе ( по словам Пола Грэма ), он добавил это для удобства и для упрощения рекурсии.
Итак, вы можете видеть, что он фактически определил 9 основных «операторов» для своей Лисп-машины. В предыдущем ответе на еще один ваш вопрос я объяснил, как вы можете представлять числа и работать с ними с помощью этой системы.
Но ответ на этот вопрос действительно зависит от того, чего вы хотите от своей Lisp-машины. Вы можете реализовать один без label
функции, так как вы можете просто функционально скомпоновать все и получить рекурсию, применяя Y-Combinator.
atom
можно было бы отбросить, если вы определили car
операцию для возвращаемых атомов NIL
.
По сути, у вас может быть LISP-машина Маккарти с 7 из этих 9 определенных примитивов, но вы можете якобы определить более краткую версию в зависимости от того, сколько неудобств вы хотите причинить себе. Мне очень нравится его машина или множество примитивов в новых языках, таких как Clojure.
Лучший способ узнать это наверняка - это реализовать. Я использовал 3 лета, чтобы создать Zozotez, который является LISP в стиле Маккарти и работает на Brainfuck .
Я попытался выяснить, что мне нужно, и на форуме вы найдете ветку, в которой говорится, что вам нужна только лямбда. Таким образом, вы можете сделать целый LISP в лямбда-исчислении, если хотите. Мне это показалось интересным, но вряд ли это подходящее решение, если вы хотите что-то, что в конечном итоге имеет побочные эффекты и работает в реальном мире.
Для полного LISP по Тьюрингу я использовал объяснение работы Маккарти Полом Грэхэмом, и все, что вам действительно нужно, это:
Thats 10. В дополнение к этому, чтобы иметь реализацию, которую можно протестировать, а не только на чертежной доске:
Thats 12. В моем Zozotez я также реализовал set и flambda (анонимные макросы, такие как лямбда). Я мог бы скормить ему библиотеку, реализующую любой динамически связанный lisp (Elisp, picoLisp), за исключением файлового ввода-вывода (потому что базовый BF не поддерживает его, кроме stdin / stdout).
Я рекомендую всем реализовать интерпретатор LISP1 как в LISP, так и (не в LISP), чтобы полностью понять, как реализован язык. LISP имеет очень простой синтаксис, так что это хорошая отправная точка для синтаксического анализатора. В настоящее время я работаю над компилятором схемы, написанным на схеме с разными целями (например, Сталин для цели C), надеюсь, BF в качестве одной из них.
источник
Маккарти использовали семь операторов для определения оригинального Lisp:
quote
,atom
,eq
,car
,cdr
,cons
иcond
. Эта статья повторяет его шаги.источник
label
, хотя в этом не было необходимости.lambda
тоже было нужно .lambda
иlabel
в терминах семи примитивов данных. Он просто вводит то, что он намеревается означать, прежде чем дать их реализацию в определенииeval
в разделе 4. Вы можете видеть, что реализацияeval
обеспечивает поддержку для себяlambda
илиlist
без нее в зависимости от того и другого.В этом часто задаваемом вопросе говорится:
Это взято с сайта Школы компьютерных наук Карнеги-Мелон.
источник
Пол Грэм реализует eval, используя семь .
В «Микроруководстве по LISP» Маккарти реализует eval с помощью десяти .
источник
Вам просто нужна
MOV
инструкция x86 .Если серьезно, эти примитивы не будут реализовывать Lisp-машину. Машине нужны такие средства, как ввод-вывод и сборка мусора. Не говоря уже о механизме вызова функций! Хорошо, у вас есть семь примитивов, которые являются функциями. Как машина вызывает функцию?
Правильное понимание того, что эти примитивы делают возможным, состоит в том, что они раскрывают набор команд универсальной машины Тьюринга . Поскольку эти инструкции являются «Лиспи», мы оговоримся (говоря на Лиспе) украдкой называем это «Лисп-машиной». «Универсальный» означает, что машина является программируемой: применив некоторые комбинированные инструкции к универсальной машине Тьюринга, мы можем создать экземпляр любой машины Тьюринга. Но пока все это чисто математическая конструкция.
Чтобы на самом деле смоделировать эту UTM - реализовать ее физически, чтобы исследовать на компьютере, нам нужна машина, которая дает нам возможность фактически вводить те формы, которые создают машины Тьюринга из комбинаций этих семи инструкций Лиспа. И нам также нужна какая-то форма вывода; машина должна, по крайней мере, сказать нам «да», «нет» или «подождите, я все еще бегу».
Другими словами, единственный способ, которым эти семь инструкций могут практически работать, - это если они размещены на более крупной машине, которая обеспечивает среду.
Также обратите внимание на то, что семь примитивов Грэма не имеют явной поддержки чисел, поэтому вам придется строить их из функций (техника «цифр Чёрча»). Никакая производственная реализация Lisp не делает таких сумасшедших вещей.
источник