[Artikel mit anderer Sprachversion verknüpfen] Implementierungsbeispiel eines einfachen LISP-Verarbeitungssystems [Zusammenfassung jeder Sprachversion]
Dieser Artikel ist ein Implementierungsbeispiel für ein einfaches LISP-Verarbeitungssystem ("McCarthys Original Lisp"), das einen Auszug und eine Modifikation der Ruby-Version des folgenden Artikels verwendet. Es ist eine Zusammenfassung.
Im Fall der Implementierung des LISP-Verarbeitungssystems mit den Mindestfunktionen ist die Implementierung des Evaluators (eval), der der Hauptteil ist, sehr einfach, sondern es wird die Implementierung der Eingabe / Ausgabe und Listenverarbeitung vom Typ S entwickelt, die eine Phrasen- / Syntaxanalyse durchführt. Es ist für diejenigen zusammengefasst, die für jede Sprache große Probleme haben, und es ist eine Schwelle.
Das Ausführungsbeispiel lautet wie folgt. Bestätigt mit Ruby 2.5.5.
$ irb --simple-prompt
>> load "jmclisp.rb"
=> true
>> s_rep("(car (cdr '(10 20 30)))")
=> "20"
>> s_rep(gets.chomp)
((lambda (x) (car (cdr x))) '(abc def ghi))
=> "def"
>> s_rep("((lambda (f x y) (f x (f y '()))) 'cons '10 '20)")
=> "(10 20)"
>> s_rep("((lambda (f x y) (f x (f y '())))
'(lambda (x y) (cons x (cons y '())))
'10 '20)")
=> "(10 (20 ()))"
>> s_rep("((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 sind wie folgt.
quote ( ') sollte für variable Werte verwendet werden.atom`` eq`` cons`` car cdr (Nachteile-Zelle intern erstellen)t (true) und nil (false) = leere ListeEinzelheiten zu "McCarthys Original Lisp" finden Sie unter Zusammenfassender Artikel. Da es sich um einen dynamischen Bereich handelt, wird im Ausführungsbeispiel der Lambda-Ausdruck anstelle von "letrec" (Schema) und "label" (Common Lisp) verwendet.
jmclisp.rb
####
#### JMC Lisp: defined in McCarthy's 1960 paper,
#### with S-expression input/output and basic list processing
####
#### basic list processing: cons, car, cdr, eq, atom
def cons(x, y) [x, y].freeze end
def car(s) s[0] end
def cdr(s) s[1] end
def eq(s1, s2) s1 == s2 end
def atom(s) s.is_a?(String) || eq(s, nil) || eq(s, true) || eq(s, false) end
#### S-expression input: s_read
def s_lex(s)
for p in ['(',')','\''] do
s = s.gsub(p, " #{p} ")
end
s.split
end
def s_syn(s)
def quote(x, s)
if s.length != 0 && s[-1] == '\'' then
s.delete_at(-1)
cons("quote", cons(x, nil))
else x
end
end
t = s.delete_at(-1)
if t == ')' then
r = nil
while s[-1] != '(' do
if s[-1] == '.' then
s.delete_at(-1)
r = cons(s_syn(s), car(r))
else
r = cons(s_syn(s), r)
end
end
s.delete_at(-1)
quote(r, s)
else
quote(t, s)
end
end
def s_read(s) s_syn(s_lex(s)) end
#### S-expression output: s_string
def s_strcons(s)
sa_r = s_string(car(s))
sd = cdr(s)
if eq(sd, nil) then sa_r
elsif atom(sd) then "#{sa_r} . #{sd}"
else "#{sa_r} #{s_strcons(sd)}"
end
end
def s_string(s)
if eq(s, nil) then "()"
elsif eq(s, true) then "t"
elsif eq(s, false) then "nil"
elsif atom(s) then s
else "(#{s_strcons(s)})"
end
end
#### JMC Lisp evaluator: s_eval
def caar(x) car(car(x)) end
def cadr(x) car(cdr(x)) end
def cadar(x) car(cdr(car(x))) end
def caddr(x) car(cdr(cdr(x))) end
def caddar(x) car(cdr(cdr(car(x)))) end
def s_null(x) eq(x, nil) end
def s_append(x, y)
if s_null(x) then y
else cons(car(x), s_append(cdr(x), y))
end
end
def s_list(x, y) cons(x, cons(y, nil)) end
def s_pair(x, y)
if s_null(x) and s_null(y) then nil
elsif (not atom(x)) and (not atom(y))
cons(s_list(car(x), car(y)), s_pair(cdr(x), cdr(y)))
else nil
end
end
def s_assoc(x, y)
if eq(caar(y), x) then cadar(y)
else s_assoc(x, cdr(y))
end
end
def s_eval(e, a)
if eq(e, "t") then true
elsif eq(e, "nil") then false
elsif atom(e) then s_assoc(e, a)
elsif atom(car(e))
if eq(car(e), "quote") then cadr(e)
elsif eq(car(e), "atom") then atom(s_eval(cadr(e), a))
elsif eq(car(e), "eq") then eq( s_eval(cadr(e), a), s_eval(caddr(e), a))
elsif eq(car(e), "car") then car( s_eval(cadr(e), a))
elsif eq(car(e), "cdr") then cdr( s_eval(cadr(e), a))
elsif eq(car(e), "cons") then cons(s_eval(cadr(e), a), s_eval(caddr(e), a))
elsif eq(car(e), "cond") then evcon(cdr(e), a)
else s_eval(cons(s_assoc(car(e), a), cdr(e)), a)
end
elsif eq(caar(e), "lambda")
s_eval(caddar(e), s_append(s_pair(cadar(e), evlis(cdr(e), a)), a))
else print("Error")
end
end
def evcon(c, a)
if s_eval(caar(c), a) then s_eval(cadar(c), a)
else evcon(cdr(c), a)
end
end
def evlis(m, a)
if s_null(m) then nil
else cons(s_eval(car(m), a), evlis(cdr(m), a))
end
end
#### REP (no Loop): s_rep
def s_rep(e) s_string(s_eval(s_read(e), s_read("()"))) end
Listenverarbeitung: cons`` car`` cdr`` eq atom
Auszug aus Vorheriger Artikel.
S Ausdruckseingabe: s_read
Ä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.
S Ausdrucksausgabe: s_string
Der S-Typ-Ausgabeabschnitt wird neu erstellt. Intern wird eine leere Liste mit dem Wert "nil" auf output()gesetzt, und ein boolescher Wert wird auf output t`` nil gesetzt.
Evaluator: s_eval + Utility-Funktion
Erstellt die Funktion "s_eval" und die Dienstprogrammfunktion basierend auf "McCarthys Original Lisp".
REP (no Loop)：s_rep
Definieren Sie s_rep, eine Sammlung von s_read → s_eval → s_string.
Recommended Posts