[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 / eine Modifikation der Java-Version des folgenden Artikels verwendet. Es ist eine Zusammenfassung.
Bei der Implementierung des LISP-Verarbeitungssystems mit den Mindestfunktionen ist es sehr einfach, den Evaluator (eval) zu implementieren, der der Hauptteil ist. 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 Java 11.0.8.
$ java jmclisp
(car (cdr '(10 20 30)))
20
$ java jmclisp
((lambda (x) (car (cdr x))) '(abc def ghi))
def
$ java jmclisp
((lambda (f x y) (f x (f y '()))) 'cons '10 '20)
(10 20)
$ java jmclisp
((lambda (f x y) (f x (f y '())))
'(lambda (x y) (cons x (cons y '())))
'10 '20)
(10 (20 ()))
$ java jmclisp
((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 (Cons-Zelle intern erstellen)t (true) und nil (false) = leere Liste ="nil"Einzelheiten 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.java
//
// JMC Lisp: defined in McCarthy's 1960 paper,
// with S-expression input/output and basic list processing
//
import java.util.Scanner;
class pair {
private Object x, y;
public pair(Object car, Object cdr) {
x = car; y = cdr;
}
public Object car() { return x; }
public Object cdr() { return y; }
}
public class jmclisp {
// basic list processing: cons, car, cdr, eq, atom
private static Object cons(Object s1, Object s2) {
return new pair(s1, s2);
}
private static Object car(Object s) { return ((pair)s).car(); }
private static Object cdr(Object s) { return ((pair)s).cdr(); }
private static Boolean eq(Object s1, Object s2) {
if (s1 instanceof String && s2 instanceof String) {
return ((String)s1).equals((String)s2);
} else {
return false;
}
}
private static Boolean atom(Object s) { return (s instanceof String); }
// S-expression output: s_string
private static Object s_strcons(Object s) {
Object sa_r = s_string(car(s));
Object sd = cdr(s);
if (eq(sd, "nil")) { return sa_r; }
else if (atom(sd)) {
return (String)sa_r + " . " + (String)sd;
} else {
return (String)sa_r + " " + (String)s_strcons(sd);
}
}
private static Object s_string(Object s) {
if (eq(s, "nil")) { return "()"; }
else if (atom(s)) { return s; }
else { return "(" + (String)s_strcons(s) + ")"; }
}
// lexical analysis for S-expression: s_lex
private static String[] s_lex(String s) {
return s.replace("(", " ( ")
.replace(")", " ) ")
.replace("'", " ' ")
.trim().split(" +");
}
// abstract syntax tree generator: s_syn
private static int posl;
private static String[] rl;
private static Object quote(Object x) {
if ((posl >= 0) && (rl[posl]).equals("'")) {
posl = posl - 1;
return cons("quote", cons(x, "nil"));
} else {
return x;
}
}
private static Object s_syn() {
String t = rl[posl];
posl = posl - 1;
if (t.equals(")")) {
Object r = (Object)"nil";
while (!((rl[posl]).equals("("))) {
if ((rl[posl]).equals(".")) {
posl = posl - 1;
r = cons(s_syn(), car(r));
} else {
r = cons(s_syn(), r);
}
}
posl = posl - 1;
return quote(r);
} else {
return quote((Object)t);
}
}
// JMC Lisp evaluator: s_eval
private static Object caar(Object x) { return car(car(x)); }
private static Object cadr(Object x) { return car(cdr(x)); }
private static Object cadar(Object x) { return car(cdr(car(x))); }
private static Object caddr(Object x) { return car(cdr(cdr(x))); }
private static Object caddar(Object x) { return car(cdr(cdr(car(x)))); }
private static Boolean s_null(Object x) {
if (eq(x, "nil")) { return true; }
else { return false; }
}
private static Object s_append(Object x, Object y) {
if (s_null(x)) { return y; }
else {
Object r = s_append(cdr(x), y);
return cons(car(x), r);
}
}
private static Object s_list(Object x, Object y) {
return cons(x, cons(y, "nil"));
}
private static Object s_pair(Object x, Object y) {
if (s_null(x) && s_null(y)) {
return "nil";
} else if (!(atom(x)) && !(atom(y))) {
return cons(s_list(car(x), car(y)),
s_pair(cdr(x), cdr(y)));
} else {
return "nil";
}
}
private static Object s_assoc(Object x, Object y) {
if (s_null(y)) { return "nil"; }
else if (eq(caar(y), x)) { return cadar(y); }
else { return s_assoc(x, cdr(y)); }
}
private static Object s_atom(Object s) { return atom(s) ? "t" : "nil"; }
private static Object s_eq(Object s1, Object s2) { return eq(s1, s2) ? "t" : "nil"; }
private static Object s_eval(Object e, Object a) {
if (eq(e, "t")) { return "t"; }
else if (eq(e, "nil")) { return "nil"; }
else if (atom(e)) { return s_assoc(e, a); }
else if (atom(car(e))) {
if (eq(car(e), "quote")) { return cadr(e); }
else if (eq(car(e), "atom")) { return s_atom(s_eval(cadr(e), a)); }
else if (eq(car(e), "eq")) { return s_eq( s_eval(cadr(e), a),
s_eval(caddr(e), a)); }
else if (eq(car(e), "car")) { return car( s_eval(cadr(e), a)); }
else if (eq(car(e), "cdr")) { return cdr( s_eval(cadr(e), a)); }
else if (eq(car(e), "cons")) { return cons( s_eval(cadr(e), a),
s_eval(caddr(e), a)); }
else if (eq(car(e), "cond")) { return evcon(cdr(e), a); }
else { return s_eval(cons(s_assoc(car(e), a), cdr(e)), a); }
} else if (eq(caar(e), "lambda")) {
return s_eval(caddar(e),
s_append(s_pair(cadar(e), evlis(cdr(e), a)), a));
} else {
System.out.println("Error");
return "nil";
}
}
private static Object evcon(Object c, Object a) {
if (eq(s_eval(caar(c), a), "t")) { return s_eval(cadar(c), a); }
else { return evcon(cdr(c), a); }
}
private static Object evlis(Object m, Object a) {
if (s_null(m)) { return "nil"; }
else { return cons(s_eval(car(m), a), evlis(cdr(m), a)); }
}
// REP (no Loop): s_rep
private static void s_rep(String s) {
rl = s_lex(s);
posl = rl.length - 1;
System.out.println(s_string(s_eval(s_syn(), "nil")));
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String s = "", i;
do {
i = scan.nextLine();
s = s + i;
} while (!(i.equals("")));
s_rep(s);
}
}
Listenverarbeitung: cons`` car`` cdr`` eq atom, S-Ausdrucksausgabe: s_string
Auszug aus Vorheriger Artikel. Conscell wird unter Verwendung des Objekttyps erstellt.
S Ausdruckseingabe: s_lex und s_syn
Neu erstellt. Der Phrasenanalyseteil "s_lex" ordnet eine Zeichenfolge durch Identifizieren von "()" und "" an, und der Teil "s_syn" zur Erzeugung abstrakter Syntaxbäume unterstützt in Klammern verschachtelte Punkte gegenüber Anführungszeichen und ist eine Listenverarbeitungsfunktion. Generieren Sie einen Syntaxbaum.
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, das s_lex → s_syn → s_eval → s_string zusammenfasst. Beschreiben Sie außerdem, wie Sie mehrere Zeilen eingeben, bis eine leere Zeile mit der Funktion main eingegeben wird, um eine Zeichenfolge zu erstellen, und übergeben Sie sie an s_rep.
Recommended Posts