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

80

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)

Sokole Oko
źródło

Odpowiedzi:

58

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.

Izaak
źródło
19
Sugestia, że ​​McCarthy nie wiedział o Y-Combinator, wydaje się być błędna. Na stronie 7 "Funkcje rekurencyjne ..." McCarthy pisze: Istnieje notacja obejmująca operatory zwane kombinatorami do łączenia funkcji bez użycia zmiennych. Niestety, wyrażenia kombinacyjne dla interesującej kombinacji funkcji są zwykle długie i nieczytelne.
luser droog
1
Coś tu brakuje. Taki seplenienie nie mógł dodać dwóch liczb ani nawet zrozumieć, że 12 to liczba.
Albert van der Horst,
1
Rzeczywiście może! Napisałem też o tym wpis na blogu. blog.isaachodes.io/p/set-theory-and-lisp
Isaac
1
Z pewnością nie użyłby tradycyjnej automatycznej reprezentacji liczb całkowitych i byłby raczej nieefektywny.
Isaac
14

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.

Sylwester
źródło
3
Jeśli chodzi o użycie wyłącznie lambdy, porównaj z "Komputer z jednym zestawem instrukcji", "logiką NAND", "rachunkiem kombinatora SKI", ... :-)
ajm475du
2
@ ajm475du Wszystko to jest takie samo, jak „potrzebujesz tylko lambdy”. Jest kompletny, ale prawie niemożliwy do użycia z powodu braku we / wy. BF potrzebuje tylko 6 instrukcji, aby być kompletnym. reszta, jeśli ma być praktyczna.
Sylwester
1
Hmm. Co się stanie, jeśli połączysz stdin / stdout interpretera bf z innym programem, który może interpretować polecenia file / io? Następnie bf-lisp może zapisywać żądania i odczytywać je z żądanego pliku.
luser droog
2
@luserdroog Sugerujesz użycie stdin / stdout jako magistrali komunikatów do jakiegoś programu / systemu operacyjnego w celu zaimplementowania wywołań systemowych. Właściwie myślę o zrobieniu tego dla mojego kompilatora, który skompiluje się do BF. Na przykład. Jeśli używasz więcej operacji we / wy niż do odczytu / zapisu, program wysyła magiczny ciąg wymagań, a interfejs API dałby uzgadnianie w taki sam sposób, jak podczas uruchamiania programów Windows w DOS w latach 90-tych. Zauważ, że BF nadal musi zapewnić terminal, więc na początek I / O, więc jest to tylko dalsza rozbudowa.
Sylwester
10

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

Vijay Mathew
źródło
1
Właściwie też używał label, chociaż nie było to konieczne.
Izaak
2
I on też potrzebował lambda.
Izaak
9
Byłem zdezorientowany o tym na początku też, ale on faktycznie definiuje lambdai labelpod względem siedmiu pierwotnych danych. Po prostu wprowadza, co zamierza, aby oznaczały, zanim poda ich implementację w definicji evalw sekcji 4. Widać, że implementacja evalzapewnia wsparcie dla lambda/ listbez siebie w zależności od jednego z nich.
amalloy
8

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.

bennybdbc
źródło
2

Paul Graham wdraża eval za pomocą siedmiu .

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

Sokole Oko
źródło
2

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.

Kaz
źródło
1
Kocham to. Zadałbym pytanie o UTM, ale myślę, że już go rozwaliłeś. Próbuję wymyślić kwestię związaną z home brew 8, ale komputery, UTM i Lisp.
hawkeye