[Link article to other language version] Implementation example of simple LISP processing system [Summary of each language version]
This article is an implementation example of a simple LISP processing system ("McCarthy's Original Lisp") that uses an excerpt / modification of the Java version of the following article. It is a summary.
In the case of implementing a LISP processing system with the minimum functions, it is very easy to implement the eval, which is the main body, but rather, S-expression input / output and list processing implementation that perform lexical / parsing are developed. It is summarized for those who have a lot of trouble for each language and it is a threshold.
The execution example is as follows. Confirmed with 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)
The implementation contents are as follows.
quote (') should be used for variable values.quote, cond and lambda can be used as syntax ʻeq cons`` car cdr (create cons cell internally)t (true) and nil (false) = empty list = " nil "For more information on "McCarthy's Original Lisp", see Summary Article. Since it is a dynamic scope, lambda expressions are used instead of letrec (Scheme) and labels (Common Lisp) in the execution example.
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);
}
}
List processing: cons`` car cdr ʻeq ʻatom, S-expression output: s_string
Excerpt from Previous article. Conscell is constructed using Object type.
S-expression input: s_lex and s_syn
Newly created. The lexical analysis part s_lex arranges one character string by identifying()and', and the abstract syntax tree generation part s_syn supports parentheses nested dots vs. quote symbols, and is a list processing function. Generate a syntax tree.
Evaluator: s_eval + utility function
Created s_eval and utility functions based on "McCarthy's Original Lisp".
REP (no Loop)：s_rep
Define s_rep which is a collection of s_lex → s_syn → s_eval → s_string. Also, describe to input multiple lines until a blank line is input with the main function to make one character string, and pass it to s_rep.
Recommended Posts