lisp.scala

JAVA 语言的函数式编程扩展

//############################################################################
// Lisp interpreter
//############################################################################
// $Id: lisp.scala 9110 2006-11-01 16:03:28Z mihaylov $

//############################################################################
// Lisp Scanner

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
      if (isDelimiter(s charAt i)) i = i + 1
      else 
        do i = i + 1
        while (!isDelimiter(s charAt i))
      s.substring(start, i)
    } else error("premature end of string")
}

//############################################################################
// Lisp Interface

trait Lisp {
  type Data;

  def string2lisp(s: String): Data;
  def lisp2string(s: Data): String;

  def evaluate(d: Data): Data;
  // !!! def evaluate(s: String): Data = evaluate(string2lisp(s));
  def evaluate(s: String): Data;
}

//############################################################################
// Lisp Implementation Using Case Classes

object LispCaseClasses extends Lisp {

  import List.range;

  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 object
    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)) Console.print(" ");
      Console.println("===> " + x);
      indent = indent + 1;
    }
    val result = eval1(x, env);
    if (trace) {
      indent = indent - 1;
      for (val x <- range(1, indent)) Console.print(" ");
      Console.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(token.toInt)
      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)
  }

  def lisp2string(d: Data): String = d.toString();
}

//############################################################################
// Lisp Implementation Using Any

object LispAny extends Lisp {