Zusammenfassung meiner Arbeit / 4. Stufe des Spickzettel. Ich habe die folgende Webseite gelesen und beschlossen, den ersten 7-Zeilen-Interpreter (Lambda-Berechnung) in Python und anderen Programmiersprachen zu schreiben. Daher vorerst nur die Schema-Beschreibung der Originalsprache und die Python-Beschreibung.
(λ x . x) → ((λ x . x)) ((λ x . x) (λ a . a)) → (λ a . a) (((λ f . f) (λ g . g)) (λ a . a)) → ((λ a . a)) (((λ f . (λ x . (f x))) (λ g . g )) (λ a . a)) → ((λ a . a))
In diesem Artikel verwendet das Lambda-Symbol "/" (anstelle von "λ").
Zur Vereinfachung der Portierungsarbeit (?) Ist die Struktur für jede Sprache in die folgenden Teile unterteilt. Um jedoch Doppelungen mit vorhandenen Funktionen zu vermeiden, ist "eval" der Funktionsname von "eval7" und "apply" der Funktionsname von "apply7".
Wahl lesen. Es analysiert die Phrase und Syntax von S-Ausdrücken (parse).
gosh> (read (open-input-string "(hoge hage (hige (foo bar)) baz)"))
(hoge hage (hige (foo bar)) baz)
Sie können assq verwenden.
gosh> (assq 'a '((a 10) (b 20) (c 30)))
(a 10)
Bewertungsteil der Formel. Fast kopieren und einfügen der obigen Webseite. Nimmt den Ausdruck "e" und die Umgebung "env", ruft den entsprechenden Wert aus der Umgebung "env" ab, wenn der Ausdruck "e" eine Variable ist, und gibt die Umgebung "env" als Wert zurück, wenn der Ausdruck "e" ein einzelner Lambda-Ausdruck ist. Davon abgesehen wird es als eine Liste der Funktion "(car e)" und des Werts "(cadr e)" angesehen, die der Funktion gegeben werden, und jede Funktion / jeder Wert wird zuerst selbst bewertet (anwendbare Reihenfolge). Rufen Sie apply auf, um die Funktion anzuwenden.
(define (eval7 e env)
(cond ((symbol? e) (cadr (assq e env)))
((eq? (car e) '/) (cons e env))
(else (apply7 (eval7 (car e) env)
(eval7 (cadr e) env)))))
Funktionsanwendungsteil. Fast kopieren und einfügen der obigen Webseite. Empfängt die Funktion "f" und den Wert "x", ordnet die Funktionsvariable "(cadr (car f))" dem Wert "x" zu und kombiniert sie mit dem verbleibenden nicht angewendeten Wert "(cdr f)" als Umgebung. , Nennen Sie den Ausdrucksbewertungsteil "eval" zusammen mit dem Funktionskörperausdruck "(cddr (car f))".
Als Vorsichtsmaßnahme für die Implementierung ist die rechte Seite der eingegebenen Lambda-Ausdrucksperiode automatisch der cdr-Teil des Punktpaars in Schema, so dass beispielsweise "f" ist ((/ a. (/ C. d))). Das "(cd dr (car f))" zum Zeitpunkt von) "wird zu" (\ c. D) "anstelle von" (. (/ C. d)) ".
(define (apply7 f x)
(eval7 (cddr (car f))
(cons (list (cadr (car f)) x)
(cdr f))))
Verwenden Sie "display" so wie es ist.
gosh> (display '((/ a . a)))
((/ a . a))#<undef>
gosh> (display (eval7 (read) '()))
(((/ f . (/ x . (f x))) (/ g . g )) (/ a . a))
((/ a . a))#<undef>
Python（Python 3，Python2）
Hier read_from_tokens () pakuri. Die Fehlerbehandlung ging verloren.
def readlist(x):
xl = x.replace('(', ' ( ').replace(')', ' ) ').split()
def ret(ts):
t = ts.pop(0)
if t == '(':
r = []
while ts[0] != ')': r.append(ret(ts))
ts.pop(0)
return tuple(r)
else:
return t
return ret(xl)
>>> readlist('(hoge hage (hige (foo bar)) baz)')
('hoge', 'hage', ('hige', ('foo', 'bar')), 'baz')
Zuerst dachte ich über die Verwendung des Wörterbuchtyps nach, aber es schien zum Zeitpunkt der λ-Auswertung problematisch zu sein, also implementierte ich ihn unter der Annahme des Taple-Typs.
def assoc(k, vl):
if not vl: return False
elif vl[0][0] == k: return vl[0]
else: return assoc(k, vl[1:])
>>> assoc('a', (('a', 10), ('b', 20), ('c', 30)))
('a', 10)
Index großer Erfolg. Schema (LISP) "(Auto x)", "(cdr x)", "(cadr x)" ist Pythons "x [0]", "x [1:]", "x [1]" Klassisch (normalerweise das Gegenteil).
def eval7(e, env):
if isinstance(e, str): return assoc(e, env)[1]
elif e[0] == '/': return (e,) + env
else: return apply7(eval7(e[0], env), eval7(e[1], env))
Der zweite große Erfolg bei den Indizes. Der Grund für "cdddr" = "[3:]" anstelle von "cddr" = "[2:]" ist das Entfernen von "." (Siehe Erläuterung der Schemaimplementierung).
def apply7(f, x): return eval7(f[0][3:][0], ((f[0][1], x),) + f[1:])
Die Umkehrung der Eingabe. Das ist wirklich meine eigene Arbeit. Das letzte [: -1] ist sehr technisch.
def writelist(x):
def ret(xs):
r = ('(')
for t in xs:
if isinstance(t, tuple):
r += ret(t)
else:
r = r + t + ' '
r = r[:-1] + ') '
return r
return ret(x)[:-1]
>>> writelist(('a', 'b', ('c', 'd'), (('e', 'f'), ('g', 'h'))))
'(a b (c d) ((e f) (g h)))'
Für Python3 (verwenden Sie input ()).
>>> print(writelist(eval7(readlist(input()), ())))
(((/ f . (/ x . (f x))) (/ a . a )) (/ b . b))
((/ b . b))
Für Python2 (verwenden Sie "raw_input ()").
>>> print(writelist(eval7(readlist(raw_input()), ())))
(((/ f . (/ x . (f x))) (/ a . a )) (/ b . b))
((/ b . b))
Recommended Posts