Dieser Artikel implementiert die minimale Eingabe / Ausgabe von S-Ausdrücken und die Verarbeitung von Listen in verschiedenen Programmiersprachen und anschließend John McCarthys Primitive LISP Interpreter Description. /recursive/recursive.html) implementiert von Paul Graham in Common Lisp ("McCarthys Original Lisp") (http://paulgraham.com/lispcode.html) (jmc.lisp) für jede Sprache Dies ist eine Sammlung von Links und allgemeinen Erklärungen von Beschreibungsbeispielen, die portiert und auf Funktion überprüft wurden.
Schema-Version (Schreiben Sie jmc.lisp neu)
[JavaScript-Version] (https://qiita.com/ytaki0801/items/2124d6ceba7f3a628a8c)
Common Lisp-Version (Beispiel für die Bestätigung des Betriebs von jmc.lisp mit jmc.lisp)
Darüber hinaus gibt es einen Artikel, der ein Beispiel zusammenfasst, das nur die grundlegende Listenverarbeitung und einen einfachen Parser der Beschreibung unter Verwendung mehrerer Arten von Klammern implementiert, und der durch Auszug oder Änderung aus dieser Beschreibung aufgenommen werden kann.
Dieser Artikel ist neuer und nach und nach organisiert, es kann jedoch zu Inkonsistenzen bei jedem verknüpften Artikel oder zu doppelten Beschreibungen und Erklärungen kommen. Wir würden uns über Ihr Verständnis freuen.
Unter Bezugnahme auf diese kann dasselbe LISP-Verarbeitungssystem, das die Eigenschaften eines hyperzirkulären Evaluators aufweist, leicht in anderen Programmiersprachen als dem LISP-System implementiert werden, und ** ist ideal für den Einstieg in die Implementierung des Sprachverarbeitungssystems ** ... Es sollte sein, aber wenn es sich um ein LISP-Verarbeitungssystem handelt, ist es standardmäßig mit einer Eingabe- / Ausgabeverarbeitung "S-Ausdruck" ausgestattet, die Phrasen und Syntax definiert, sowie einer grundlegenden Listenverarbeitung basierend auf einem S-Ausdruck (car, cdr, cons, eq, eq, Die Implementierung von atom) erfordert für jede Entwicklungssprache eine überwältigende Menge an Zeit und Mühe, was eine Schwelle darstellt.
Daher wird in jeder Programmiersprache ein einfaches Beispiel für die Implementierung / Ausgabe von S-Typ und die grundlegende Implementierung der Listenverarbeitung separat erstellt **, und "McCarthys Original Lisp" ist möglich. Der Zweck jedes Implementierungsbeispiels besteht diesmal darin, den anfänglichen Schwellenwert für die Implementierung des Sprachverarbeitungssystems zu senken, indem der Vorgang so portiert und überprüft wird, wie er ist.
Wie im folgenden Beispiel gezeigt, gibt es keine Methode zur Beschreibung von Namen oder Funktionsdefinitionen, und es wird nur eine Gruppe von S-Ausdrücken verarbeitet. Da es sich jedoch um einen dynamischen Bereich handelt, wird eine rekursive Funktion mithilfe eines Lambda-Ausdrucks definiert. Es kann auch verwendet werden (anstelle der "letrec" - oder Common Lisp "-Labels" von Scheme).
(car (cdr '(10 20 30)))
=> 20
((lambda (x) (car (cdr x))) '(abc def ghi))
=> def
((lambda (f x y) (f x (f y '()))) 'cons '10 '20)
=> (10 20)
((lambda (f x y) (f x (f y '())))
'(lambda (x y) (cons x (cons y '())))
'10 '20)
=> (10 (20 ()))
((lambda (assoc k v) (assoc k v))
'(lambda (k v)
(cond ((eq v '()) nil)
((eq (car (car v)) k)
(car v))
('t (assoc k (cdr v)))))
'Orange
'((Apple . 120) (Orange . 210) (Lemmon . 180)))
=> (Orange . 210)
Die Implementierungsinhalte des Bewertungsgremiums sind wie folgt.
cons`` car`` cdr`` eq atom (Cons-Zelle intern erstellen)t (true) und nil (false) = leere Liste (= NULL-Äquivalent)Die Konfiguration der Implementierung der Eingabe / Ausgabe und Listenverarbeitung vom Typ S ist wie folgt.
cons`` car`` cdr`` eq atom( ) ' als Phrase und Leerzeichen als Trennzeichen verwendet werden.( ) mit cons auf, 'fügt(quote ...), . ein, generiert die cons-ZelleDer Verarbeitungsinhalt von "s_eval" ist wie folgt. Außerdem wird im Gegensatz zum ursprünglichen "jmc.lisp" die Funktion "label" weggelassen.
Wenn e eine Zeichenfolge ist, die einen booleschen Wert angibt, wird ein vorbestimmter boolescher Wert zurückgegeben.
Wenn e keine Listenstruktur ist, wird es als Bindungsvariable betrachtet, und der entsprechende Wert wird aus der Umgebungsvariablen abgerufen und zurückgegeben.
Wenn "e1" "quote" ist, wird das zweite Element von "e" so zurückgegeben, wie es ist.
Wenn e1`` atom`` eq`` car`` cdr`` cons ist, wird die Funktion nach Auswertung der Argumentelemente angewendet und das Ergebnis zurückgegeben.
Wenn "e1" "cond" ist, übergeben Sie eine Liste der bedingten Ausdrücke und der Verarbeitung an "evcon" und geben Sie das Ergebnis zurück.
In anderen Fällen wird "e1" als Bindungsvariable des Lambda-Ausdrucks angesehen, der entsprechende Lambda-Ausdruck wird aus der Umgebungsvariablen erhalten, als erstes Element von "e" ersetzt und das Bewertungsergebnis zurückgegeben.
Wenn "e1" auch eine Listenstruktur ist und das erste Element "Lambda" ist, wird dies als Wertanwendung des Lambda-Ausdrucks angesehen und die folgende Verarbeitung wird durchgeführt.
Übergeben Sie eine Liste von Wertelementen, die auf "evlis" angewendet werden sollen, und erhalten Sie das Bewertungsergebnis jedes Elements erneut als Liste.
Erstellen Sie eine Liste, die jedes Argument des Lambda-Ausdrucks mit jedem ausgewerteten Wertelement verknüpft, und fügen Sie es der Umgebungsvariablen hinzu.
Gibt das Ergebnis der Auswertung des Verarbeitungskörpers des Lambda-Ausdrucks unter Verwendung der aktualisierten Umgebungsvariablen zurück.
Wenn "e" eine andere Konfiguration als die oben genannte hat, wird "()" als Fehler zurückgegeben.
Es geht darum, den Wert des Lambda-Ausdrucks anzuwenden, nachdem der Lambda-Ausdruck beispielsweise an das Argument eines anderen Lambda-Ausdrucks gebunden wurde.
(s_eval '((lambda (f) (f '(a b c))) '(lambda (x) (cdr x))) '()))
=> (s_eval '(f '(a b c)) '((f (lambda (x) (cdr x))) . ()))
=> (s_eval '((lambda (x) (cdr x)) '(a b c)) '((f (lambda (x) (cdr x))) . ()))
=> (s_eval '(cdr x) '((x (a b c)) (f (lambda (x) (cdr x))) . ()))
=> (cdr (s_eval 'x '((x (a b c)) (f (lambda (x) (cdr x))) . ())))
=> (cdr '(a b c))
=> (b c)
Es gibt nur eine Umgebungsvariable, obwohl sich das Argument dreht. Daher handelt es sich um einen dynamischen Bereich, aber diesmal betrachtet der Evaluator einen S-Ausdruck mit nur einem Lambda-Ausdruck als Fehler (vielmehr wird der andere Wert als der Boolesche Wert und die angegebene Beschreibung nicht zurückgegeben) und der Lambda-Ausdruck Sie können keinen Lambda-Ausdruck verarbeiten, der einen Lambda-Ausdruck als Verarbeitungskörper beschreibt, dh einen Lambda-Ausdruck zurückgibt. Als Funktionsfunktion höherer Ordnung entspricht sie einem sogenannten Objekt zweiter Klasse.
Tatsächlich ist es nicht unmöglich, zurückzukehren, wie es nur bei einem Lambda-Ausdruck wie einem Booleschen Wert der Fall ist, aber es muss ein lexikalischer Bereich sein, der eine lokale Umgebungsvariable im Lambda-Ausdruck enthält und eine Abschlussfunktion implementiert. ， Das Problem des Namenskonflikts (funarg) tritt auf. Und da der Wert der lokalen Umgebungsvariablen in einem anderen Lambda-Ausdruck nicht im lexikalischen Bereich angewendet werden kann, wird für die rekursive Verarbeitungsdefinition die Syntax zum Hinzufügen der Variablenbindung direkt zur globalen Umgebungsvariablen und zum Immobilitätspunkt wie dem Y-Kombinator verwendet. Sie benötigen einen Kombinator.
Obwohl es sich um ein einfaches Verarbeitungssystem handelt, kann es nicht implementiert werden, ohne verschiedene Funktionen der Host-Sprache zu nutzen. Daher geeigneter Typ und Maßstab als Fach für das ernsthafte Erlernen der Sprache Es gibt auch (: //pico.vub.ac.be/mc/mcexplanation.html). Vorläufig fand ich alle seltsamen Gewohnheiten von Haskells Handgelenksmonade heraus (eh).
Basierend auf dem oben Gesagten ist es ein gutes Sprachverarbeitungssystem, obwohl es die Mindestkonfiguration hat. Es ist also gut zu zeigen, dass die Sprache so verwendet werden kann, wie sie ist, indem die Funktionen in Bezug auf diesen Inhalt neu geschrieben und erweitert werden. Ich frage mich, ob es das gibt. Wenn zum Beispiel eine Person in einem anderen Bereich darüber nachdenkt, zu einem Programmierjob zu wechseln, ein Interview
Interviewer "Der Lebenslauf besagt, dass Sie ◯◯ Sprache sprechen können. Wie gut haben Sie es gelernt?" Sie "Nun, ist es nur eine einfache Implementierung eines Sprachverarbeitungssystems?" Interviewer "Was sind die Spezifikationen der Implementierungssprache? (Handelt es sich um eine Computerprogrammkopie, die die Parser-Bibliothek verwendet?)" Sie "Nun, können Sie zumindest eine rekursive Prozedur definieren?" Interviewer "!?" Sie "Nein, es war ein wenig schwierig, weil ich die Bibliothek nicht für die Phrasenanalyse und die Generierung abstrakter Syntaxbäume verwendet habe." Interviewer "!?"
Es ist genau richtig für ~~, es richtig zu machen ~~. Das ist keine Lüge. Eh, bin ich? Ich bin in der Lage zu sagen: "Es ist natürlich, dies in einer beliebigen Sprache tun zu können, es dauert zu viel Zeit und Verschwendung, und es gibt keine Fehlerprüfung." Ja.
sample.scm
(car (cdr '(10 20 30)))
=> 20
((lambda (x) (car (cdr x))) '(abc def ghi))
=> def
((lambda (f x y) (f x (f y '()))) cons '10 '20) ;Der als Argument übergebene Funktionsname muss nicht in Anführungszeichen gesetzt werden
=> (10 20)
((lambda (f x y) (f x (f y '())))
(lambda (x y) (cons x (cons y '()))) ;Der als Argument übergebene Lambda-Ausdruck muss ebenfalls nicht zitiert werden
'10 '20)
=> (10 (20 ()))
(letrec ((assoc_ (lambda (k v)
(cond ((eq? v '()) '())
((eq? (car (car v)) k)
(car v))
(else (assoc_ k (cdr v)))))))
(assoc_ 'Orange
'((Apple . 120) (Orange . 210) (Lemmon . 180))))
=> (Orange . 210)
sample.lsp
(car (cdr '(10 20 30)))
=> 20
((lambda (x) (car (cdr x))) '(abc def ghi))
=> DEF ;Die Alphabetanzeige als Symbol wird in Großbuchstaben angezeigt
((lambda (f x y) (funcall f x (funcall f y '()))) 'cons '10 '20) ;Die als Argument übergebene Funktion wird mit funcall ausgeführt
=> (10 20)
((lambda (f x y) (funcall f x (funcall f y '()))) ;Der als Argument übergebene Lambda-Ausdruck wird mit funcall ausgeführt
(lambda (x y) (cons x (cons y '()))) ;Lambda-Ausdrücke müssen nicht zitiert werden
'10 '20)
=> (10 (20 NIL))
(labels ((assoc_ (k v)
(cond ((eq v '()) '())
((eq (car (car v)) k)
(car v))
(t (assoc_ k (cdr v))))))
(assoc_ 'Orange
'((Apple . 120) (Orange . 210) (Lemmon . 180))))
=> (ORANGE . 210)
Recommended Posts