Ile prymitywów potrzeba do zbudowania maszyny LISP? Dziesięć, siedem czy pięć?

Na tej stronie mówią, że jest 10 prymitywów LISP-a. Prymitywy są: atom, quote, eq, car, cdr, cons, cond, lambda, label, apply.

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

Stevey uważa, że ​​jest ich siedem (lub pięć):

Jest to część czystości idei LISP-a: potrzebujesz tylko siedmiu (a może pięciu?) Prymitywów do zbudowania pełnej maszyny. http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html

Jaka jest minimalna liczba prymitywów do zbudowania maszyny LISP (tj. Czegoś, co może uruchomić funkcję eval / value na kodzie LISP)? (A które to są?)

(Rozumiem, że możesz żyć bez atom, label and apply)

Podstawowe predykaty / funkcje F.

McCarthy jest podstawowe funkcje S i Predykaty były następujące:

1. atom

   Co było konieczne, ponieważ samochód i cdr są zdefiniowane tylko dla list, co oznacza, że ​​nie możesz liczyć na jakąkolwiek odpowiedź, która wskaże, co się dzieje, jeśli podałeś caratom.

2. eq

   Do testowania równości między atomami.

3. car

   Do zwrotu pierwszej połowy (adresu) komórki cons. (Zawartość rejestru adresowego).

4. cdr

   Do zwrotu drugiej połowy (dekrementacji) komórki minusów. (Zawartość rejestru dekrementów).

5. cons

   Do tworzenia nowej komórki wad, z połową adresu zawierającą pierwszy argument minus, a połową dekrementacji zawierającą drugi argument.

Powiązanie: funkcje S.

Następnie dodał do swojej podstawowej notacji, aby umożliwić pisanie tego, co nazwał S-funkcjami:

1. quote

   Reprezentowanie wyrażenia bez oceniania go.

2. cond

   Podstawowy warunek do użycia z poprzednio opisanymi predykatami.

3. lambda

   Aby oznaczyć funkcję.

4. label

   Chociaż nie potrzebował tego do rekurencji, mógł nie wiedzieć o Y-Combinatorze ( według Paula Grahama ), dodał to dla wygody i umożliwienia łatwej rekurencji.

Więc możesz zobaczyć, że faktycznie zdefiniował 9 podstawowych "operatorów" dla swojej maszyny Lisp. W poprzedniej odpowiedzi na inne pytanie wyjaśniłem, w jaki sposób można przedstawiać liczby i operować na nich w tym systemie.

Ale odpowiedź na to pytanie naprawdę zależy od tego, czego oczekujesz od swojej maszyny Lisp. Możesz zaimplementować jeden bez labelfunkcji, ponieważ możesz po prostu funkcjonalnie skomponować wszystko i uzyskać rekursję przez zastosowanie Y-Combinator.

atommożna by odrzucić, jeśli zdefiniowałeś caroperację na atomach do powrotu NIL.

Zasadniczo możesz mieć maszynę LISP firmy McCarthy'ego z 7 z tych 9 zdefiniowanych prymitywów, ale możesz rzekomo zdefiniować bardziej zwięzłą wersję w zależności od tego, ile niedogodności chcesz sobie wyrządzić. Podoba mi się jego maszyna lub wiele prymitywów w nowszych językach, takich jak Clojure.

Najlepszym sposobem, aby to wiedzieć na pewno, jest wdrożenie go. Wykorzystałem 3 lata do stworzenia Zozoteza, który jest LISP- em McCarty'ego działającym na Brainfuck .

Próbowałem się dowiedzieć, czego potrzebuję, a na forum znajdziesz wątek, który mówi, że potrzebujesz tylko lambdy. W ten sposób możesz zrobić cały LISP w rachunku lambda, który chcesz. Wydało mi się to interesujące, ale nie jest to dobra droga, jeśli chcesz czegoś, co w końcu ma skutki uboczne i działa w prawdziwym świecie.

Dla pełnego LISP-a Turinga użyłem wyjaśnienia Paula Grahamsa do artykułu McCarthy'ego i wszystko, czego naprawdę potrzebujesz, to:

• ocena symboli
• wycena w specjalnym formularzu
• specjalny formularz if (lub cond)
• specjalna forma lambda (podobna do cytatu)
• funkcja równ
• atom funkcji
• wady funkcji
• samochód funkcyjny
• funkcja cdr
• wysyłka funkcji (lista-lambda)

To 10. Oprócz tego, aby mieć implementację, którą można przetestować, a nie tylko na desce kreślarskiej:

• funkcja czytaj
• funkcja zapisu

To 12. W moim Zozotezie zestaw i flambdę (anonimowe makra, takie jak lambda). Mógłbym podać mu bibliotekę implementującą dowolne dynamiczne wiązane lisp (Elisp, picoLisp) z wyjątkiem wejścia / wyjścia pliku (ponieważ bazowy BF nie obsługuje go poza stdin / stdout).

Polecam każdemu zaimplementowanie interpretera LISP1 zarówno w LISP, jak i (nie LISP), aby w pełni zrozumieć, w jaki sposób język jest implementowany. LISP ma bardzo prostą składnię, więc jest dobrym punktem wyjścia dla parsera. Obecnie pracuję nad kompilatorem schematów napisanym w schemacie z różnymi celami (tak jak Stalin dla celu C), mam nadzieję, że BF jest jednym z nich.

McCarthy siedmiu operatorów stosowane do określenia pierwotnego Lisp: quote, atom, eq, car, cdr, consi cond. Ten artykuł śledzi jego kroki.

W tym często zadawanym pytaniu czytamy:

Nie ma jednego „najlepszego” minimalnego zestawu prymitywów; wszystko zależy od implementacji. Na przykład nawet coś tak podstawowego jak liczby nie musi być prymitywne i może być reprezentowane jako listy. Jeden możliwy zestaw prymitywów może obejmować CAR, CDR i CONS do manipulacji wyrażeniami S, READ i PRINT dla wejścia / wyjścia wyrażeń S oraz APPLY i EVAL dla wnętrzności interpretera. Ale wtedy możesz dodać LAMBDA dla funkcji, EQ dla równości, COND dla warunków, SET dla przypisania i DEFUN dla definicji. CYTAT też może się przydać.

To pochodzi ze strony internetowej School of Computer Science, Carnegie Melon.

Paul Graham wdraża eval za pomocą siedmiu .

W McCarthy's Micro Manual for LISP implementuje eval przy użyciu dziesięciu .

Ty po prostu potrzebujesz x86 MOVdyspozycję .

„M / o / Vfuscator (krótkie„ o ”, brzmi jak„ mobfuscator ”) kompiluje programy w instrukcje„ mov ”i tylko instrukcje„ mov ”. Arytmetyka, porównania, skoki, wywołania funkcji i wszystko inne, czego potrzebuje program, to wszystkie wykonywane za pomocą operacji przenoszenia; nie ma samomodyfikującego się kodu, żadnych obliczeń wyzwalanych przez transport i żadnej innej formy oszustwa bez ruchu. "

Poważnie jednak, te prymitywy nie zaimplementują maszyny Lisp. Maszyna potrzebuje udogodnień, takich jak operacje we / wy i czyszczenie pamięci. Nie wspominając o mechanizmie wywoływania funkcji! OK, masz siedem prymitywów, które są funkcjami. W jaki sposób maszyna wywołuje funkcję?

Prawidłowe zrozumienie tego, co te prymitywy umożliwiają, polega na tym, że ujawniają zestaw instrukcji Uniwersalnej Maszyny Turinga . Ponieważ te instrukcje są „Lispy”, przez przejęzyczenie (mówienie z Lispem) podstępnie nazywamy je „Lisp Machine”. „Uniwersalny” oznacza, że ​​maszyna jest programowalna: z niektórymi instrukcjami kombinacji zastosowanymi do Universal Turing Machine, możemy utworzyć instancję dowolnej Maszyny Turinga. Ale jak dotąd wszystko to jest czysto matematyczną konstrukcją.

Aby faktycznie zasymulować ten UTM - zrealizować go fizycznie w celu zbadania go na komputerze, potrzebujemy maszyny, która zapewni nam sposób na wprowadzenie tych form, które tworzą Maszyny Turinga z kombinacji tych siedmiu instrukcji Lispa. Potrzebujemy też jakiejś formy wyjścia; maszyna, aby przynajmniej móc powiedzieć nam „tak”, „nie” lub „czekaj, nadal działam”.

Innymi słowy, jedyny sposób, w jaki te siedem instrukcji może praktycznie działać, to umieszczenie ich na większej maszynie, która zapewnia środowisko.

Zauważ również, że siedem prymitywów Grahama nie ma wyraźnego wsparcia dla liczb, więc musiałbyś zbudować je z funkcji (technika „liczebników kościelnych”). Żadna produkcyjna implementacja Lispa nie robi tak szalonej rzeczy.