Dieser Artikel ist eine Zusammenfassung von Implementierungsbeispielen eines einfachen LISP-Verarbeitungssystems, das einen Auszug / eine Modifikation der Python-Version des folgenden Artikels verwendet.
Eine einfache Implementierung des Meta-Circular-Evaluators, der den Hauptteil des LISP-Verarbeitungssystems darstellt, ist Beispiel für die primäre Implementierung (Paul) Beispiel für die Beschreibung von Graham's Common Lisp: "McCarthys Original Lisp") und SICP 4.1 (/sicp/full-text/sicp/book/node76.html) wurde schon lange veröffentlicht, daher ist es sehr einfach. Vielmehr erfordert jede Entwicklungssprache mehr Zeit und Mühe, um eine Eingabe- / Ausgabe- und Listenverarbeitung vom Typ S zu implementieren, die eine Phrasen- / Syntaxanalyse durchführt, und ich habe sie für diejenigen zusammengefasst, die sich an der Schwelle befinden.
Da die beiden oben genannten Artikel zusätzlich zu Python C-Sprache, Ruby und JavaScript implementieren, erstellen wir möglicherweise denselben Artikel für diese Sprachversionen (daher lautet der Titel "Python-Version"). ).
Das Ausführungsbeispiel lautet wie folgt. Ersetzen Sie in Python2 "input ()" durch "raw_input ()".
>>> s_rep("(car (cdr '(10 20 30)))")
'20'
>>> s_rep(input())
((lambda (x y) (car (cdr x))) '(abc def ghi))
'def'
>>> s_rep("((lambda (f x y l) (f x (f y l))) + '10 '20 '0)")
'30'
>>> s_rep("((lambda (f x y l) (f x (f y l))) cons '10 '20 '())")
'(10 20)'
>>> s_rep("((fix (lambda (fact) (lambda (n) (if (eq? n '0) '1 (* n (fact (- n '1))))))) '10)")
'3628800'
>>> fassoc = "(lambda (assoc) (lambda (k) (lambda (v) (if (eq? v '()) #f (if (eq? k (car (car v))) (car v) ((assoc k) (cdr v)))))))"
>>> s_rep("(((fix" + fassoc + ") 'Orange) '((Apple . 110) (Orange . 210) (Lemmon . 180)))")
'(Orange . 210)'
Die Implementierungsinhalte sind wie folgt.
cons`` car`` cdr`` eq? `` Pair? (Cons-Zelle intern erstellen)+ -`` * / (berechnet durch Betrachten von zitierten Zahlen als Zahlen)# t (true) # f (false) fix (Kombinator für Immobilitätspunkte)[LispKit] statt Pure LISP, da es einen Fix gibt, mit dem Sie rekursive Prozeduren definieren können, anstatt Namen definieren zu können. Es kann in der Nähe von Lisp liegen](https://en.wikipedia.org/wiki/Lispkit_Lisp).
Auszug aus Vorheriger Artikel.
def cons(x, y): return (x, y)
def car(s): return s[0]
def cdr(s): return s[1]
def eq(s1, s2): return s1 == s2
def atom(s): return isinstance(s, str) or eq(s, None) or isinstance(s, bool)
Ändern Sie unter Vorheriger Artikel den Phrasenanalyseteil in "()" und "" Identifikation ("s_lex") und den Teil zur Erzeugung des abstrakten Syntaxbaums. Es wurde geändert, um einen Syntaxbaum von cons cell mit der Listenverarbeitungsfunktion zu generieren, während Punktpaare und Anführungszeichen (s_syn) unterstützt werden, und die S-Ausdruckseingabefunktion s_read definiert, die sie zusammenfügt.
def s_lex(s):
for p in "()'": s = s.replace(p, " " + p + " ")
return s.split()
def s_syn(s):
def quote(x):
if len(s) != 0 and s[-1] == "'":
del s[-1]
return cons("quote", cons(x, None))
else: return x
t = s[-1]
del s[-1]
if t == ")":
r = None
while s[-1] != "(":
if s[-1] == ".":
del s[-1]
r = cons(s_syn(s), car(r))
else: r = cons(s_syn(s), r)
del s[-1]
return quote(r)
else: return quote(t)
def s_read(s): return s_syn(s_lex(s))
Der S-Typ-Ausgabeabschnitt s_string wurde neu erstellt. Intern wird eine leere Liste mit dem Namen "None" auf output()gesetzt, und ein boolescher Wert wird auf output # t`` # f gesetzt.
def s_strcons(s):
sa_r = s_string(car(s))
sd = cdr(s)
if eq(sd, None):
return sa_r
elif atom(sd):
return sa_r + " . " + sd
else:
return sa_r + " " + s_strcons(sd)
def s_string(s):
if eq(s, None): return "()"
elif eq(s, True): return "#t"
elif eq(s, False): return "#f"
elif atom(s):
return s
else:
return "(" + s_strcons(s) + ")"
Erstellen Sie die Funktion "s_eval" unter Bezugnahme auf SICP 4.1. Informationen zur Anwendung integrierter Funktionen und pseudo-numerischer Operatoren finden Sie in Peter Norvigs "lis.py" und verwenden Sie die ursprüngliche Umgebung "env". Separat von der Anwendung implementiert. Der Immobilitätspunktkombinator ist eine geschlossene Version des Y-Kombinators [Z-Kombinator](https://ja.wikipedia.org/wiki/%E4%B8%8D%E5%8B%95%E7%82%B9%E3% 82% B3% E3% 83% B3% E3% 83% 93% E3% 83% 8D% E3% 83% BC% E3% 82% BF # Z% E3% 82% B3% E3% 83% B3% E3% 83% 93% E3% 83% 8D% E3% 83% BC% E3% 82% BF) ist in der Umgebung "env" voreingestellt.
s_builtins = {
"cons": lambda x, y: cons(x, y),
"car": lambda s: car(s),
"cdr": lambda s: cdr(s),
"eq?": lambda s1, s2: eq(s1, s2),
"pair?": lambda s: not atom(s),
"+": lambda s1, s2: str(int(int(s1) + int(s2))),
"-": lambda s1, s2: str(int(int(s1) - int(s2))),
"*": lambda s1, s2: str(int(int(s1) * int(s2))),
"/": lambda s1, s2: str(int(int(s1) / int(s2)))
}
def lookup_variable_value(var, env):
def loop(env):
def scan(vars, vals):
if eq(vars, None): return loop(cdr(env))
elif eq(var, car(vars)): return car(vals)
else: return scan(cdr(vars), cdr(vals))
frame = car(env)
fvar = car(frame)
fval = cdr(frame)
return scan(fvar, fval)
return loop(env)
def s_eval(e, env):
def sargs(a, env):
if eq(a, None): return None
else: return cons(s_eval(car(a), env), sargs(cdr(a), env))
if atom(e):
if e in s_builtins: return e
else: return lookup_variable_value(e, env)
elif eq(car(e), "quote"):
return car(cdr(e))
elif eq(car(e), "if"):
pred = car(cdr(e))
texp = car(cdr(cdr(e)))
fexp = cdr(cdr(cdr(e)))
if eq(s_eval(pred, env), True): return s_eval(texp, env)
else: return False if eq(fexp, None) else s_eval(car(fexp), env)
elif eq(car(e), "lambda"):
lvars = car(cdr(e))
lbody = car(cdr(cdr(e)))
return cons("lambda", cons(lvars, cons(lbody, cons(env, None))))
else:
f = s_eval(car(e), env)
args = sargs(cdr(e), env)
return s_apply(f, args)
def s_apply(f, args):
def pargs(al):
if eq(al, None): return []
else: return [car(al)] + pargs(cdr(al))
if atom(f): return s_builtins[f](*pargs(args))
else:
lvars = car(cdr(f))
lbody = car(cdr(cdr(f)))
lenvs = car(cdr(cdr(cdr(f))))
env = cons(cons(lvars, args), lenvs)
return s_eval(lbody, env)
fixproc = s_eval(s_read( \
"(lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y))))))" \
), None)
s_init_env = cons(cons( \
cons("fix", cons("#t", cons("#f", None))), \
cons(fixproc, cons(True, cons(False, None))) \
), None)
REP (no Loop)
Definieren Sie s_rep, eine Sammlung von s_read → s_eval → s_string.
def s_rep(s): return s_string(s_eval(s_read(s), s_init_env))
2020-09-07: Erste Ausgabe veröffentlicht
Recommended Posts