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

80

На этом сайте говорят, что есть 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-acceptable-lisp.html

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

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

соколиный глаз
источник

Ответы:

58

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

McCarthy «s Элементарные 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-комбинаторе ( по словам Пола Грэма ), он добавил это для удобства и для упрощения рекурсии.


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

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

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

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

Исаак
источник
19
Предположение, что Маккарти не знал об Y-комбинаторе, кажется ошибочным. На странице 7 книги «Рекурсивные функции ...» Маккарти пишет: « Есть обозначения, включающие операторы, которые называются комбинаторами для комбинирования функций без использования переменных. К сожалению, комбинаторные выражения для интересной комбинации функций имеют тенденцию быть длинными и нечитаемыми.
luser droog
1
Здесь чего-то не хватает. Такая шепелявка не могла сложить два числа или даже понять, что 12 - это число.
Альберт ван дер Хорст,
1
Действительно может! Я тоже написал об этом в блоге. blog.isaachodes.io/p/set-theory-and-lisp
Isaac
1
Конечно, он не будет использовать традиционное машинное представление целых чисел и в результате будет довольно неэффективным.
Исаак
14

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

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

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

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

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

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

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

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

Сильвестр
источник
3
Что касается использования ничего, кроме лямбды, сравните с «Компьютер с одним набором инструкций», «Логика NAND», «Расчет комбинатора SKI», ... :-)
ajm475du
2
@ ajm475du Все это то же самое, что «вам нужна только лямбда». Он полный, но использовать его практически невозможно из-за отсутствия ввода-вывода. BF нужно всего 6 инструкций для завершения Тьюринга. остальное, если сделать его практичным.
Sylwester
1
Хм. Что, если вы подключите stdin / stdout интерпретатора bf к другой программе, которая может интерпретировать команды file / io? Затем bf-lisp может записывать запросы, а затем читать из запрошенного файла.
luser droog 03
2
@luserdroog Вы предлагаете использовать stdin / stdout в качестве шины сообщений для некоторой программы / ОС для реализации системных вызовов. Я действительно думаю сделать это для своего компилятора, который будет компилироваться в BF. Например. если вы используете больше операций ввода-вывода, чем чтение / запись, программа отправляет волшебную строку требований, и API будет выдавать рукопожатие почти так же, как вы получали ошибки при запуске программ Windows в DOS еще в 90-х годах. Обратите внимание, что BF по-прежнему необходимо предоставить терминал, поэтому ввод-вывод для начала, так что это просто дальнейшее расширение.
Sylwester
10

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

Виджей Мэтью
источник
1
На самом деле он тоже использовал label, хотя в этом не было необходимости.
Исаак
2
И ему lambdaтоже было нужно .
Исаак
9
Я был смущен об этом сначала тоже, но на самом деле он определяет lambdaи labelв терминах семи примитивов данных. Он просто вводит то, что он намеревается означать, прежде чем дать их реализацию в определении evalв разделе 4. Вы можете видеть, что реализация evalобеспечивает поддержку для себя lambdaили listбез нее в зависимости от того и другого.
amalloy
8

В этом часто задаваемом вопросе говорится:

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

Это взято с сайта Школы компьютерных наук Карнеги-Мелон.

Bennybdbc
источник
2

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

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

соколиный глаз
источник
2

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

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

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

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

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

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

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

Каз
источник
1
Любить это. Я бы задал вопрос о UTM, но думаю, вы уже разбили его. Я пытаюсь придумать вопрос, связанный с домашним пивом 8, но вычислениями, UTM и Lisp.
hawkeye