diff options
author | paltherr <paltherr@epfl.ch> | 2003-03-14 09:44:10 +0000 |
---|---|---|
committer | paltherr <paltherr@epfl.ch> | 2003-03-14 09:44:10 +0000 |
commit | b4b5355b6b2bba37c2ea74b086992625038f8e7b (patch) | |
tree | a1b31e8137b3e3f17702afaf84f0cd67d9b3a9e7 /test | |
parent | 8a4a9a98097d79be41effac00c6cd95b1d5d8cac (diff) | |
download | scala-b4b5355b6b2bba37c2ea74b086992625038f8e7b.tar.gz scala-b4b5355b6b2bba37c2ea74b086992625038f8e7b.tar.bz2 scala-b4b5355b6b2bba37c2ea74b086992625038f8e7b.zip |
- Added Course-2002-11.scala
Diffstat (limited to 'test')
-rw-r--r-- | test/files/run/Course-2002-11.check | 11 | ||||
-rw-r--r-- | test/files/run/Course-2002-11.scala | 296 |
2 files changed, 307 insertions, 0 deletions
diff --git a/test/files/run/Course-2002-11.check b/test/files/run/Course-2002-11.check new file mode 100644 index 0000000000..526d7ea790 --- /dev/null +++ b/test/files/run/Course-2002-11.check @@ -0,0 +1,11 @@ + +( '(1 2 3)) = (1 2 3) +(car '(1 2 3)) = 1 +(cdr '(1 2 3)) = (2 3) +(null? '(2 3)) = 0 +(null? '()) = 1 + +faculty(10) = 3628800 +faculty(10) = 3628800 +foobar = ("a" "bc" "def" "z") + diff --git a/test/files/run/Course-2002-11.scala b/test/files/run/Course-2002-11.scala new file mode 100644 index 0000000000..46d86c17d6 --- /dev/null +++ b/test/files/run/Course-2002-11.scala @@ -0,0 +1,296 @@ +//############################################################################ +// Programmation IV - 2002 - Week 11 +//############################################################################ +// $Id$ + +module Lisp { + + trait Data { + def elemsToString(): String = toString(); + } + case class CONS(car: Data, cdr: Data) extends Data { + override def toString() = "(" + elemsToString() + ")"; + override def elemsToString() = car.toString() + (cdr match { + case NIL() => "" + case _ => " " + cdr.elemsToString(); + }) + } + case class NIL() extends Data { // !!! use case module + override def toString() = "()"; + } + case class SYM(name: String) extends Data { + override def toString() = name; + } + case class NUM(x: Int) extends Data { + override def toString() = x.toString(); + } + case class STR(x: String) extends Data { + override def toString() = "\"" + x + "\""; + } + case class FUN(f: List[Data] => Data) extends Data { + override def toString() = "<fn>"; + } + + def list(): Data = + NIL(); + def list(x0: Data): Data = + CONS(x0, NIL()); + def list(x0: Data, x1: Data): Data = + CONS(x0, list(x1)); + def list(x0: Data, x1: Data, x2: Data): Data = + CONS(x0, list(x1, x2)); + def list(x0: Data, x1: Data, x2: Data, x3: Data): Data = + CONS(x0, list(x1, x2, x3)); + def list(x0: Data, x1: Data, x2: Data, x3: Data, x4: Data): Data = + CONS(x0, list(x1, x2, x3, x4)); + def list(x0: Data, x1: Data, x2: Data, x3: Data, x4: Data, x5: Data): Data = + CONS(x0, list(x1, x2, x3, x4, x5)); + def list(x0: Data, x1: Data, x2: Data, x3: Data, x4: Data, x5: Data, + x6: Data): Data = + CONS(x0, list(x1, x2, x3, x4, x5, x6)); + def list(x0: Data, x1: Data, x2: Data, x3: Data, x4: Data, x5: Data, + x6: Data, x7: Data): Data = + CONS(x0, list(x1, x2, x3, x4, x5, x6, x7)); + def list(x0: Data, x1: Data, x2: Data, x3: Data, x4: Data, x5: Data, + x6: Data, x7: Data, x8: Data): Data = + CONS(x0, list(x1, x2, x3, x4, x5, x6, x7, x8)); + def list(x0: Data, x1: Data, x2: Data, x3: Data, x4: Data, x5: Data, + x6: Data, x7: Data, x8: Data, x9: Data): Data = + CONS(x0, list(x1, x2, x3, x4, x5, x6, x7, x8, x9)); + + var curexp: Data = null; + var trace: Boolean = False; + var indent: Int = 0; + + def lispError[a](msg: String): a = + error("error: " + msg + "\n" + curexp); + + trait Environment { + def lookup(n: String): Data; + def extendRec(name: String, expr: Environment => Data) = + new Environment { + def lookup(n: String): Data = + if (n == name) expr(this) else Environment.this.lookup(n); + } + def extend(name: String, v: Data) = extendRec(name, (env1 => v)); + } + val EmptyEnvironment = new Environment { + def lookup(n: String): Data = lispError("undefined: " + n); + } + + def toList(x: Data): List[Data] = x match { + case NIL() => List() + case CONS(y, ys) => y :: toList(ys) + case _ => lispError("malformed list: " + x); + } + + def toBoolean(x: Data) = x match { + case NUM(0) => False + case _ => True + } + + def normalize(x: Data): Data = x match { + case CONS(SYM("def"), + CONS(CONS(SYM(name), args), CONS(body, CONS(expr, NIL())))) => + normalize(list(SYM("def"), + SYM(name), list(SYM("lambda"), args, body), expr)) + case CONS(SYM("cond"), CONS(CONS(SYM("else"), CONS(expr, NIL())),NIL())) => + normalize(expr) + case CONS(SYM("cond"), CONS(CONS(test, CONS(expr, NIL())), rest)) => + normalize(list(SYM("if"), test, expr, CONS(SYM("cond"), rest))) + case CONS(h, t) => CONS(normalize(h), normalize(t)) + case _ => x + } + + def eval(x: Data, env: Environment): Data = { + val prevexp = curexp; + curexp = x; + if (trace) { + for (val x <- range(1, indent)) do System.out.print(" "); + System.out.println("===> " + x); + indent = indent + 1; + } + val result = eval1(x, env); + if (trace) { + indent = indent - 1; + for (val x <- range(1, indent)) do System.out.print(" "); + System.out.println("<=== " + result); + } + curexp = prevexp; + result + } + + def eval1(x: Data, env: Environment): Data = x match { + case SYM(name) => + env lookup name + case CONS(SYM("def"), CONS(SYM(name), CONS(y, CONS(z, NIL())))) => + eval(z, env.extendRec(name, (env1 => eval(y, env1)))) + case CONS(SYM("val"), CONS(SYM(name), CONS(y, CONS(z, NIL())))) => + eval(z, env.extend(name, eval(y, env))) + case CONS(SYM("lambda"), CONS(params, CONS(y, NIL()))) => + mkLambda(params, y, env) + case CONS(SYM("if"), CONS(c, CONS(t, CONS(e, NIL())))) => + if (toBoolean(eval(c, env))) eval(t, env) else eval(e, env) + case CONS(SYM("quote"), CONS(x, NIL())) => + x + case CONS(y, xs) => + apply(eval(y, env), toList(xs) map (x => eval(x, env))) + case NUM(_) => x + case STR(_) => x + case FUN(_) => x + case _ => + lispError("illegal term") + } + + def apply(fn: Data, args: List[Data]): Data = fn match { + case FUN(f) => f(args); + case _ => lispError("application of non-function: " + fn); + } + + def mkLambda(params: Data, expr: Data, env: Environment): Data = { + + def extendEnv(env: Environment, + ps: List[String], args: List[Data]): Environment = + Pair(ps, args) match { + case Pair(List(), List()) => + env + case Pair(p :: ps1, arg :: args1) => + extendEnv(env.extend(p, arg), ps1, args1) + case _ => + lispError("wrong number of arguments") + } + + val ps: List[String] = toList(params) map { + case SYM(name) => name + case _ => error("illegal parameter list"); + } + + FUN(args => eval(expr, extendEnv(env, ps, args))) + } + + val globalEnv = EmptyEnvironment + .extend("=",FUN({ + case List(NUM(arg1),NUM(arg2)) => NUM(if(arg1 == arg2) 1 else 0) + case List(STR(arg1),STR(arg2)) => NUM(if(arg1 == arg2) 1 else 0)})) + .extend("+", FUN({ + case List(NUM(arg1),NUM(arg2)) => NUM(arg1 + arg2) + case List(STR(arg1),STR(arg2)) => STR(arg1 + arg2)})) + .extend("-", FUN({ + case List(NUM(arg1),NUM(arg2)) => NUM(arg1 - arg2)})) + .extend("*", FUN({ + case List(NUM(arg1),NUM(arg2)) => NUM(arg1 * arg2)})) + .extend("/", FUN({ + case List(NUM(arg1),NUM(arg2)) => NUM(arg1 / arg2)})) + .extend("car", FUN({ + case List(CONS(x, xs)) => x})) + .extend("cdr", FUN({ + case List(CONS(x, xs)) => xs})) + .extend("null?", FUN({ + case List(NIL()) => NUM(1) + case _ => NUM(0)})) + .extend("cons", FUN({ + case List(x, y) => CONS(x, y)})); + + def evaluate(x: Data): Data = eval(normalize(x), globalEnv); + def evaluate(s: String): Data = evaluate(string2lisp(s)); + + def string2lisp(s: String): Data = { + val it = new LispTokenizer(s); + def parseExpr(token: String): Data = { + if (token == "(") parseList + else if (token == ")") error("unbalanced parentheses") + else if ('0' <= token.charAt(0) && token.charAt(0) <= '9') + NUM(new java.lang.Integer(token).intValue()) + else if (token.charAt(0) == '\"' && token.charAt(token.length()-1)=='\"') + STR(token.substring(1,token.length() - 1)) + else SYM(token) + } + def parseList: Data = { + val token = it.next; + if (token == ")") NIL() else CONS(parseExpr(token), parseList) + } + parseExpr(it.next) + } +} + +class LispTokenizer(s: String) extends Iterator[String] { + private var i = 0; + private def isDelimiter(ch: Char) = ch <= ' ' || ch == '(' || ch == ')'; + def hasNext: Boolean = { + while (i < s.length() && s.charAt(i) <= ' ') { i = i + 1 } + i < s.length() + } + def next: String = + if (hasNext) { + val start = i; + var ch = s.charAt(i); i = i + 1; + if (ch == '(') "(" + else if (ch == ')') ")" + else { + while (i < s.length() && !isDelimiter(s.charAt(i))){ i = i + 1 } + s.substring(start, i) + } + } else error("premature end of string") +} + +//############################################################################ + +module M0 { + + def test = { + import Lisp._; + System.out.println(); + System.out.println("( '(1 2 3)) = " + evaluate(" (quote(1 2 3))")); + System.out.println("(car '(1 2 3)) = " + evaluate("(car (quote(1 2 3)))")); + System.out.println("(cdr '(1 2 3)) = " + evaluate("(cdr (quote(1 2 3)))")); + System.out.println("(null? '(2 3)) = " + evaluate("(null? (quote(2 3)))")); + System.out.println("(null? '()) = " + evaluate("(null? (quote()))")); + System.out.println(); + System.out.println("faculty(10) = " + evaluate( + "(def (faculty n) " + + "(if (= n 0) " + + "1 " + + "(* n (faculty (- n 1)))) " + + "(faculty 10))")); + System.out.println("faculty(10) = " + evaluate( + "(def (faculty n) " + + "(cond " + + "((= n 0) 1) " + + "(else (* n (faculty (- n 1))))) " + + "(faculty 10))")); + System.out.println("foobar = " + evaluate( + "(def (foo n) " + + "(cond " + + "((= n 0) \"a\")" + + "((= n 1) \"b\")" + + "((= (/ n 2) 1) " + + "(cond " + + "((= n 2) \"c\")" + + "(else \"d\")))" + + "(else " + + "(def (bar m) " + + "(cond " + + "((= m 0) \"e\")" + + "((= m 1) \"f\")" + + "(else \"z\"))" + + "(bar (- n 4)))))" + + "(val nil (quote ())" + + "(val v1 (foo 0) " + + "(val v2 (+ (foo 1) (foo 2)) " + + "(val v3 (+ (+ (foo 3) (foo 4)) (foo 5)) " + + "(val v4 (foo 6) " + + "(cons v1 (cons v2 (cons v3 (cons v4 nil))))))))))")); + System.out.println(); + } +} + +//############################################################################ + +module Test { + def main(args: Array[String]): Unit = { + M0.test; + () + } +} + +//############################################################################ |