1
//############################################################################
2
// Lisp interpreter (revived as an optimizer test.)
3
//############################################################################
5
//############################################################################
8
class LispTokenizer(s: String) extends Iterator[String] {
10
private def isDelimiter(ch: Char) = ch <= ' ' || ch == '(' || ch == ')'
11
def hasNext: Boolean = {
12
while (i < s.length() && s.charAt(i) <= ' ') i += 1
18
if (isDelimiter(s charAt i)) i += 1
21
while (!isDelimiter(s charAt i))
23
} else sys.error("premature end of string")
26
//############################################################################
32
def string2lisp(s: String): Data
33
def lisp2string(s: Data): String
35
def evaluate(d: Data): Data
36
// !!! def evaluate(s: String): Data = evaluate(string2lisp(s))
37
def evaluate(s: String): Data
40
//############################################################################
41
// Lisp Implementation Using Case Classes
43
object LispCaseClasses extends Lisp {
48
def elemsToString(): String = toString();
50
case class CONS(car: Data, cdr: Data) extends Data {
51
override def toString() = "(" + elemsToString() + ")";
52
override def elemsToString() = car.toString() + (cdr match {
54
case _ => " " + cdr.elemsToString();
57
case class NIL() extends Data { // !!! use case object
58
override def toString() = "()";
60
case class SYM(name: String) extends Data {
61
override def toString() = name;
63
case class NUM(x: Int) extends Data {
64
override def toString() = x.toString();
66
case class STR(x: String) extends Data {
67
override def toString() = "\"" + x + "\"";
69
case class FUN(f: List[Data] => Data) extends Data {
70
override def toString() = "<fn>";
75
def list(x0: Data): Data =
77
def list(x0: Data, x1: Data): Data =
79
def list(x0: Data, x1: Data, x2: Data): Data =
80
CONS(x0, list(x1, x2));
81
def list(x0: Data, x1: Data, x2: Data, x3: Data): Data =
82
CONS(x0, list(x1, x2, x3));
83
def list(x0: Data, x1: Data, x2: Data, x3: Data, x4: Data): Data =
84
CONS(x0, list(x1, x2, x3, x4));
85
def list(x0: Data, x1: Data, x2: Data, x3: Data, x4: Data, x5: Data): Data =
86
CONS(x0, list(x1, x2, x3, x4, x5));
87
def list(x0: Data, x1: Data, x2: Data, x3: Data, x4: Data, x5: Data,
89
CONS(x0, list(x1, x2, x3, x4, x5, x6));
90
def list(x0: Data, x1: Data, x2: Data, x3: Data, x4: Data, x5: Data,
91
x6: Data, x7: Data): Data =
92
CONS(x0, list(x1, x2, x3, x4, x5, x6, x7));
93
def list(x0: Data, x1: Data, x2: Data, x3: Data, x4: Data, x5: Data,
94
x6: Data, x7: Data, x8: Data): Data =
95
CONS(x0, list(x1, x2, x3, x4, x5, x6, x7, x8));
96
def list(x0: Data, x1: Data, x2: Data, x3: Data, x4: Data, x5: Data,
97
x6: Data, x7: Data, x8: Data, x9: Data): Data =
98
CONS(x0, list(x1, x2, x3, x4, x5, x6, x7, x8, x9));
100
var curexp: Data = null
101
var trace: Boolean = false
104
def lispError[a](msg: String): a =
105
sys.error("error: " + msg + "\n" + curexp);
108
def lookup(n: String): Data;
109
def extendRec(name: String, expr: Environment => Data) =
111
def lookup(n: String): Data =
112
if (n == name) expr(this) else Environment.this.lookup(n);
114
def extend(name: String, v: Data) = extendRec(name, (env1 => v));
116
val EmptyEnvironment = new Environment {
117
def lookup(n: String): Data = lispError("undefined: " + n);
120
def toList(x: Data): List[Data] = x match {
122
case CONS(y, ys) => y :: toList(ys)
123
case _ => lispError("malformed list: " + x);
126
def toBoolean(x: Data) = x match {
131
def normalize(x: Data): Data = x match {
132
case CONS(SYM("def"),
133
CONS(CONS(SYM(name), args), CONS(body, CONS(expr, NIL())))) =>
134
normalize(list(SYM("def"),
135
SYM(name), list(SYM("lambda"), args, body), expr))
136
case CONS(SYM("cond"), CONS(CONS(SYM("else"), CONS(expr, NIL())),NIL())) =>
138
case CONS(SYM("cond"), CONS(CONS(test, CONS(expr, NIL())), rest)) =>
139
normalize(list(SYM("if"), test, expr, CONS(SYM("cond"), rest)))
140
case CONS(h, t) => CONS(normalize(h), normalize(t))
144
def eval(x: Data, env: Environment): Data = {
145
val prevexp = curexp;
148
for (x <- range(1, indent)) Console.print(" ");
149
Console.println("===> " + x);
152
val result = eval1(x, env);
155
for (x <- range(1, indent)) Console.print(" ");
156
Console.println("<=== " + result);
162
def eval1(x: Data, env: Environment): Data = x match {
165
case CONS(SYM("def"), CONS(SYM(name), CONS(y, CONS(z, NIL())))) =>
166
eval(z, env.extendRec(name, (env1 => eval(y, env1))))
167
case CONS(SYM("val"), CONS(SYM(name), CONS(y, CONS(z, NIL())))) =>
168
eval(z, env.extend(name, eval(y, env)))
169
case CONS(SYM("lambda"), CONS(params, CONS(y, NIL()))) =>
170
mkLambda(params, y, env)
171
case CONS(SYM("if"), CONS(c, CONS(t, CONS(e, NIL())))) =>
172
if (toBoolean(eval(c, env))) eval(t, env) else eval(e, env)
173
case CONS(SYM("quote"), CONS(x, NIL())) =>
176
apply(eval(y, env), toList(xs) map (x => eval(x, env)))
181
lispError("illegal term")
184
def apply(fn: Data, args: List[Data]): Data = fn match {
185
case FUN(f) => f(args);
186
case _ => lispError("application of non-function: " + fn);
189
def mkLambda(params: Data, expr: Data, env: Environment): Data = {
191
def extendEnv(env: Environment,
192
ps: List[String], args: List[Data]): Environment =
193
Pair(ps, args) match {
194
case Pair(List(), List()) =>
196
case Pair(p :: ps1, arg :: args1) =>
197
extendEnv(env.extend(p, arg), ps1, args1)
199
lispError("wrong number of arguments")
202
val ps: List[String] = toList(params) map {
203
case SYM(name) => name
204
case _ => sys.error("illegal parameter list");
207
FUN(args => eval(expr, extendEnv(env, ps, args)))
210
val globalEnv = EmptyEnvironment
212
case List(NUM(arg1),NUM(arg2)) => NUM(if (arg1 == arg2) 1 else 0)
213
case List(STR(arg1),STR(arg2)) => NUM(if (arg1 == arg2) 1 else 0)}))
215
case List(NUM(arg1),NUM(arg2)) => NUM(arg1 + arg2)
216
case List(STR(arg1),STR(arg2)) => STR(arg1 + arg2)}))
218
case List(NUM(arg1),NUM(arg2)) => NUM(arg1 - arg2)}))
220
case List(NUM(arg1),NUM(arg2)) => NUM(arg1 * arg2)}))
222
case List(NUM(arg1),NUM(arg2)) => NUM(arg1 / arg2)}))
224
case List(CONS(x, xs)) => x}))
226
case List(CONS(x, xs)) => xs}))
227
.extend("null?", FUN({
228
case List(NIL()) => NUM(1)
230
.extend("cons", FUN({
231
case List(x, y) => CONS(x, y)}));
233
def evaluate(x: Data): Data = eval(normalize(x), globalEnv);
234
def evaluate(s: String): Data = evaluate(string2lisp(s));
236
def string2lisp(s: String): Data = {
237
val it = new LispTokenizer(s);
238
def parse(token: String): Data = {
239
if (token == "(") parseList
240
else if (token == ")") sys.error("unbalanced parentheses")
241
else if ('0' <= token.charAt(0) && token.charAt(0) <= '9')
243
else if (token.charAt(0) == '\"' && token.charAt(token.length()-1)=='\"')
244
STR(token.substring(1,token.length() - 1))
247
def parseList: Data = {
249
if (token == ")") NIL() else CONS(parse(token), parseList)
254
def lisp2string(d: Data): String = d.toString();
257
//############################################################################
258
// Lisp Implementation Using Any
260
object LispAny extends Lisp {
266
case class Lambda(f: List[Data] => Data);
268
var curexp: Data = null;
269
var trace: Boolean = false;
272
def lispError[a](msg: String): a =
273
sys.error("error: " + msg + "\n" + curexp);
276
def lookup(n: String): Data;
277
def extendRec(name: String, expr: Environment => Data) =
279
def lookup(n: String): Data =
280
if (n == name) expr(this) else Environment.this.lookup(n);
282
def extend(name: String, v: Data) = extendRec(name, (env1 => v));
284
val EmptyEnvironment = new Environment {
285
def lookup(n: String): Data = lispError("undefined: " + n);
288
def asList(x: Data): List[Data] = x match {
290
case _ => lispError("malformed list: " + x)
293
def asInt(x: Data): Int = x match {
295
case _ => lispError("not an integer: " + x)
298
def asString(x: Data): String = x match {
300
case _ => lispError("not a string: " + x)
303
def asBoolean(x: Data): Boolean = x != 0
305
def normalize(x: Data): Data = x match {
306
case 'and :: x :: y :: Nil =>
307
normalize('if :: x :: y :: 0 :: Nil)
308
case 'or :: x :: y :: Nil =>
309
normalize('if :: x :: 1 :: y :: Nil)
310
case 'def :: (name :: args) :: body :: expr :: Nil =>
311
normalize('def :: name :: ('lambda :: args :: body :: Nil) :: expr :: Nil)
312
case 'cond :: ('else :: expr :: Nil) :: rest =>
314
case 'cond :: (test :: expr :: Nil) :: rest =>
315
normalize('if :: test :: expr :: ('cond :: rest) :: Nil)
316
case 'cond :: 'else :: expr :: Nil =>
319
normalize(h) :: asList(normalize(t))
324
def eval(x: Data, env: Environment): Data = {
325
val prevexp = curexp;
328
for (x <- range(1, indent)) Console.print(" ");
329
Console.println("===> " + x);
332
val result = eval1(x, env);
335
for (x <- range(1, indent)) Console.print(" ");
336
Console.println("<=== " + result);
342
def eval1(x: Data, env: Environment): Data = x match {
345
case 'def :: Symbol(name) :: y :: z :: Nil =>
346
eval(z, env.extendRec(name, (env1 => eval(y, env1))))
347
case 'val :: Symbol(name) :: y :: z :: Nil =>
348
eval(z, env.extend(name, eval(y, env)))
349
case 'lambda :: params :: y :: Nil =>
350
mkLambda(params, y, env)
351
case 'if :: c :: y :: z :: Nil =>
352
if (asBoolean(eval(c, env))) eval(y, env) else eval(z, env)
353
case 'quote :: y :: Nil =>
356
apply(eval(y, env), z map (x => eval(x, env)))
360
case y => lispError("illegal term")
363
def lisp2string(x: Data): String = x match {
364
case Symbol(name) => name
367
def list2string(xs: List[Data]): String = xs match {
369
case y :: ys => " " + lisp2string(y) + list2string(ys)
371
"(" + lisp2string(y) + list2string(ys) + ")"
372
case _ => if (x.isInstanceOf[String]) "\"" + x + "\""; else x.toString()
375
def apply(fn: Data, args: List[Data]): Data = fn match {
376
case Lambda(f) => f(args);
377
case _ => lispError("application of non-function: " + fn + " to " + args);
380
def mkLambda(params: Data, expr: Data, env: Environment): Data = {
382
def extendEnv(env: Environment,
383
ps: List[String], args: List[Data]): Environment =
384
Pair(ps, args) match {
385
case Pair(List(), List()) =>
387
case Pair(p :: ps1, arg :: args1) =>
388
extendEnv(env.extend(p, arg), ps1, args1)
390
lispError("wrong number of arguments")
393
val ps: List[String] = asList(params) map {
394
case Symbol(name) => name
395
case _ => sys.error("illegal parameter list");
398
Lambda(args => eval(expr, extendEnv(env, ps, args)))
401
val globalEnv = EmptyEnvironment
403
case List(arg1, arg2) => if(arg1 == arg2) 1 else 0})
405
case List(arg1: Int, arg2: Int) => arg1 + arg2
406
case List(arg1: String, arg2: String) => arg1 + arg2})
408
case List(arg1: Int, arg2: Int) => arg1 - arg2})
410
case List(arg1: Int, arg2: Int) => arg1 * arg2})
412
case List(arg1: Int, arg2: Int) => arg1 / arg2})
414
.extend("cons", Lambda{
415
case List(arg1, arg2) => arg1 :: asList(arg2)})
416
.extend("car", Lambda{
417
case List(x :: xs) => x})
418
.extend("cdr", Lambda{
419
case List(x :: xs) => xs})
420
.extend("null?", Lambda{
424
def evaluate(x: Data): Data = eval(normalize(x), globalEnv);
425
def evaluate(s: String): Data = evaluate(string2lisp(s));
427
def string2lisp(s: String): Data = {
428
val it = new LispTokenizer(s);
429
def parse(token: String): Data = {
430
if (token == "(") parseList
431
else if (token == ")") sys.error("unbalanced parentheses")
432
//else if (Character.isDigit(token.charAt(0)))
433
else if (token.charAt(0).isDigit)
435
else if (token.charAt(0) == '\"' && token.charAt(token.length()-1)=='\"')
436
token.substring(1,token.length() - 1)
439
def parseList: List[Data] = {
441
if (token == ")") Nil else parse(token) :: parseList
447
//############################################################################
450
class LispUser(lisp: Lisp) {
454
def evaluate(s: String) = lisp2string(lisp.evaluate(s));
458
Console.println(string2lisp("(lambda (x) (+ (* x x) 1))").asInstanceOf[AnyRef]);
459
Console.println(lisp2string(string2lisp("(lambda (x) (+ (* x x) 1))")));
462
Console.println("( '(1 2 3)) = " + evaluate(" (quote(1 2 3))"));
463
Console.println("(car '(1 2 3)) = " + evaluate("(car (quote(1 2 3)))"));
464
Console.println("(cdr '(1 2 3)) = " + evaluate("(cdr (quote(1 2 3)))"));
465
Console.println("(null? '(2 3)) = " + evaluate("(null? (quote(2 3)))"));
466
Console.println("(null? '()) = " + evaluate("(null? (quote()))"));
469
Console.println("faculty(10) = " + evaluate(
470
"(def (faculty n) " +
473
"(* n (faculty (- n 1)))) " +
475
Console.println("faculty(10) = " + evaluate(
476
"(def (faculty n) " +
479
"(else (* n (faculty (- n 1))))) " +
481
Console.println("foobar = " + evaluate(
497
"(val nil (quote ())" +
499
"(val v2 (+ (foo 1) (foo 2)) " +
500
"(val v3 (+ (+ (foo 3) (foo 4)) (foo 5)) " +
502
"(cons v1 (cons v2 (cons v3 (cons v4 nil))))))))))"));
507
//############################################################################
511
def main(args: Array[String]) {
512
new LispUser(LispCaseClasses).run;
513
new LispUser(LispAny).run;
518
//############################################################################