15 files changed, 687 insertions, 14 deletions

diff --git a/src/compiler/scala/reflect/internal/Types.scala b/src/compiler/scala/reflect/internal/Types.scala
index cfc45695a7..67c858356c 100644
--- a/src/compiler/scala/reflect/internal/Types.scala
+++ b/src/compiler/scala/reflect/internal/Types.scala
@@ -4318,7 +4318,7 @@ trait Types extends api.Types { self: SymbolTable =>
               def throwError = abort("" + tp + sym.locationString + " cannot be instantiated from " + pre.widen)
 
               val symclazz = sym.owner
-              if (symclazz == clazz && !pre.isInstanceOf[TypeVar] && (pre.widen.typeSymbol isNonBottomSubClass symclazz)) {
+              if (symclazz == clazz && !pre.widen.isInstanceOf[TypeVar] && (pre.widen.typeSymbol isNonBottomSubClass symclazz)) {
                 // have to deconst because it may be a Class[T].
                 pre.baseType(symclazz).deconst match {
                   case TypeRef(_, basesym, baseargs) =>
diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala
index fb5b9b7169..9089be5cc0 100644
--- a/src/compiler/scala/tools/nsc/Global.scala
+++ b/src/compiler/scala/tools/nsc/Global.scala
@@ -72,7 +72,10 @@ class Global(var currentSettings: Settings, var reporter: Reporter) extends Symb
     if (forMSIL) new { val global: Global.this.type = Global.this } with MSILPlatform
     else new { val global: Global.this.type = Global.this } with JavaPlatform
 
-  def classPath: ClassPath[platform.BinaryRepr] = platform.classPath
+  type PlatformClassPath = ClassPath[platform.BinaryRepr]
+
+  def classPath: PlatformClassPath = platform.classPath
+
   def rootLoader: LazyType = platform.rootLoader
 
   // sub-components --------------------------------------------------
@@ -840,6 +843,97 @@ class Global(var currentSettings: Settings, var reporter: Reporter) extends Symb
   def printAfterEachPhase[T](op: => T): Unit =
     describeAfterEachPhase(op) foreach (m => println("  " + m))
 
+  // ------------ Invalidations ---------------------------------
+
+  /** Is given package class a system package class that cannot be invalidated?
+   */
+  private def isSystemPackageClass(pkg: Symbol) =
+    pkg == definitions.RootClass ||
+    pkg == definitions.ScalaPackageClass || {
+      val pkgname = pkg.fullName
+      (pkgname startsWith "scala.") && !(pkgname startsWith "scala.tools")
+    }
+
+  /** Invalidates packages that contain classes defined in a classpath entry, and
+   *  rescans that entry.
+   *  @param path  A fully qualified name that refers to a directory or jar file that's
+   *               an entry on the classpath.
+   *  First, causes the classpath entry referred to by `path` to be rescanned, so that
+   *  any new files or deleted files or changes in subpackages are picked up.
+   *  Second, invalidates any packages for which one of the following considitions is met:
+
+   *   - the classpath entry contained during the last compilation run classfiles
+   *     that represent a member in the package
+   *   - the classpath entry now contains classfiles
+   *     that represent a member in the package
+   *   - the set of subpackages has changed.
+   *
+   *  The invalidated packages are reset in their entirety; all member classes and member packages
+   *  are re-accessed using the new classpath.
+   *  Not invalidated are system packages that the compiler needs to access as parts
+   *  of standard definitions. The criterion what is a system package is currently:
+   *  any package rooted in "scala", with the exception of packages rooted in "scala.tools".
+   *  This can be refined later.
+   *  @return A pair consisting of
+   *    - a list of invalidated packages
+   *    - a list of of packages that should have been invalidated but were not because
+   *      they are system packages.
+   */
+  def invalidateClassPathEntry(path: String): (List[Symbol], List[Symbol]) = {
+    val invalidated, failed = new mutable.ListBuffer[Symbol]
+    classPath match {
+      case cp: util.MergedClassPath[_] =>
+        val dir = AbstractFile getDirectory path
+        val canonical = Some(dir.canonicalPath)
+        cp.entries find (_.origin == canonical) match {
+          case Some(oldEntry) =>
+            val newEntry = cp.context.newClassPath(dir)
+            platform.updateClassPath(oldEntry, newEntry)
+            informProgress(s"classpath updated to $classPath")
+            reSync(definitions.RootClass, classPath, oldEntry, newEntry, invalidated, failed)
+          case None =>
+            error(s"cannot invalidate: no entry named $path in classpath $classPath")
+        }
+    }
+    def show(msg: String, syms: collection.Traversable[Symbol]) =
+      if (syms.nonEmpty)
+        informProgress(s"$msg: ${syms map (_.fullName) mkString ","}")
+    show("invalidated packages", invalidated)
+    show("could not invalidate system packages", failed)
+    (invalidated.toList, failed.toList)
+  }
+
+  private def reSync(root: Symbol, all: PlatformClassPath,
+             oldEntry: PlatformClassPath, newEntry: PlatformClassPath,
+             invalidated: mutable.ListBuffer[Symbol], failed: mutable.ListBuffer[Symbol]) {
+    ifDebug(informProgress(s"syncing $root, $oldEntry -> $newEntry"))
+    val getName: ClassPath[platform.BinaryRepr] => String = (_.name)
+    val oldPackages = oldEntry.packages sortBy getName
+    val newPackages = newEntry.packages sortBy getName
+    val hasChanged =
+      oldEntry.classes.nonEmpty ||
+      newEntry.classes.nonEmpty ||
+      (oldPackages map getName) != (newPackages map getName)
+    if (hasChanged && !isSystemPackageClass(root)) {
+      root setInfo new loaders.PackageLoader(all)
+      invalidated += root
+    } else {
+      if (hasChanged) failed += root
+      for ((oldNested, newNested) <- oldPackages zip newPackages) {
+        val pkgname = newNested.name
+        val pkg = root.info decl newTermName(pkgname)
+        val allNested = (all.packages find (_.name == pkgname)).get
+        reSync(pkg.moduleClass, allNested, oldNested, newNested, invalidated, failed)
+      }
+    }
+  }
+
+  /** Invalidate contents of setting -Yinvalidate */
+  def doInvalidation() = settings.Yinvalidate.value match {
+    case "" =>
+    case entry => invalidateClassPathEntry(entry)
+  }
+
   // ----------- Runs ---------------------------------------
 
   private var curRun: Run = null
@@ -859,6 +953,7 @@ class Global(var currentSettings: Settings, var reporter: Reporter) extends Symb
    *
    *  @param    sym A class symbol, object symbol, package, or package class.
    */
+  @deprecated("use invalidateClassPathEntry instead")
   def clearOnNextRun(sym: Symbol) = false
     /* To try out clearOnNext run on the scala.tools.nsc project itself
      * replace `false` above with the following code
@@ -870,7 +965,7 @@ class Global(var currentSettings: Settings, var reporter: Reporter) extends Symb
       }
     }}
 
-     * Then, fsc -Xexperimental clears the nsc porject between successive runs of `fsc`.
+     * Then, fsc -Xexperimental clears the nsc project between successive runs of `fsc`.
      */
 
   /** Remove the current run when not needed anymore. Used by the build
@@ -1115,6 +1210,7 @@ class Global(var currentSettings: Settings, var reporter: Reporter) extends Symb
     /** Reset all classes contained in current project, as determined by
      *  the clearOnNextRun hook
      */
+    @deprecated("use invalidateClassPathEntry instead")
     def resetProjectClasses(root: Symbol): Unit = try {
       def unlink(sym: Symbol) =
         if (sym != NoSymbol) root.info.decls.unlink(sym)
@@ -1353,6 +1449,8 @@ class Global(var currentSettings: Settings, var reporter: Reporter) extends Symb
     }
 
     private def compileUnitsInternal(units: List[CompilationUnit], fromPhase: Phase) {
+      doInvalidation()
+
       units foreach addUnit
       val startTime = currentTime
 
diff --git a/src/compiler/scala/tools/nsc/backend/JavaPlatform.scala b/src/compiler/scala/tools/nsc/backend/JavaPlatform.scala
index 7da7611ce2..e5e67e8811 100644
--- a/src/compiler/scala/tools/nsc/backend/JavaPlatform.scala
+++ b/src/compiler/scala/tools/nsc/backend/JavaPlatform.scala
@@ -7,7 +7,7 @@ package scala.tools.nsc
 package backend
 
 import io.AbstractFile
-import util.{ClassPath,JavaClassPath}
+import util.{ClassPath,JavaClassPath,MergedClassPath,DeltaClassPath}
 import util.ClassPath.{ JavaContext, DefaultJavaContext }
 import scala.tools.util.PathResolver
 
@@ -17,7 +17,17 @@ trait JavaPlatform extends Platform {
 
   type BinaryRepr = AbstractFile
 
-  lazy val classPath  = new PathResolver(settings).result
+  private var currentClassPath: Option[MergedClassPath[BinaryRepr]] = None
+
+  def classPath: ClassPath[BinaryRepr] = {
+    if (currentClassPath.isEmpty) currentClassPath = Some(new PathResolver(settings).result)
+    currentClassPath.get
+  }
+    
+  /** Update classpath with a substituted subentry */
+  def updateClassPath(oldEntry: ClassPath[BinaryRepr], newEntry: ClassPath[BinaryRepr]) = 
+    currentClassPath = Some(new DeltaClassPath(currentClassPath.get, oldEntry, newEntry))
+
   def rootLoader = new loaders.PackageLoader(classPath.asInstanceOf[ClassPath[platform.BinaryRepr]])
     // [Martin] Why do we need a cast here?
     // The problem is that we cannot specify at this point that global.platform should be of type JavaPlatform.
diff --git a/src/compiler/scala/tools/nsc/backend/MSILPlatform.scala b/src/compiler/scala/tools/nsc/backend/MSILPlatform.scala
index 65b1fbc229..30447e1274 100644
--- a/src/compiler/scala/tools/nsc/backend/MSILPlatform.scala
+++ b/src/compiler/scala/tools/nsc/backend/MSILPlatform.scala
@@ -30,7 +30,11 @@ trait MSILPlatform extends Platform {
   lazy val classPath = MsilClassPath.fromSettings(settings)
   def rootLoader = new loaders.PackageLoader(classPath.asInstanceOf[ClassPath[platform.BinaryRepr]])
     // See discussion in JavaPlatForm for why we need a cast here.
-
+  
+  /** Update classpath with a substituted subentry */
+  def updateClassPath(oldEntry: ClassPath[BinaryRepr], newEntry: ClassPath[BinaryRepr]) = 
+    throw new UnsupportedOperationException("classpath invalidations not supported on MSIL")
+  
   def platformPhases = List(
     genMSIL   // generate .msil files
   )
diff --git a/src/compiler/scala/tools/nsc/backend/Platform.scala b/src/compiler/scala/tools/nsc/backend/Platform.scala
index 23592eeb61..f97d3e3d56 100644
--- a/src/compiler/scala/tools/nsc/backend/Platform.scala
+++ b/src/compiler/scala/tools/nsc/backend/Platform.scala
@@ -23,6 +23,9 @@ trait Platform {
 
   /** The root symbol loader. */
   def rootLoader: LazyType
+  
+  /** Update classpath with a substituted subentry */
+  def updateClassPath(oldEntry: ClassPath[BinaryRepr], newEntry: ClassPath[BinaryRepr])
 
   /** Any platform-specific phases. */
   def platformPhases: List[SubComponent]
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Members.scala b/src/compiler/scala/tools/nsc/backend/icode/Members.scala
index 019e887c4e..efb4e7a199 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Members.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Members.scala
@@ -156,7 +156,7 @@ trait Members {
 
     def newBlock() = code.newBlock
     def startBlock = code.startBlock
-    def lastBlock  = blocks.last
+    def lastBlock  = { assert(blocks.nonEmpty, symbol); blocks.last }
     def blocks = code.blocksList
     def linearizedBlocks(lin: Linearizer = self.linearizer): List[BasicBlock] = lin linearize this
 
diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
index 4aa30038f6..efde2cee25 100644
--- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
+++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -171,6 +171,7 @@ trait ScalaSettings extends AbsScalaSettings
   val Ynotnull        = BooleanSetting    ("-Ynotnull", "Enable (experimental and incomplete) scala.NotNull.")
   val YmethodInfer    = BooleanSetting    ("-Yinfer-argument-types", "Infer types for arguments of overriden methods.")
   val etaExpandKeepsStar = BooleanSetting ("-Yeta-expand-keeps-star", "Eta-expand varargs methods to T* rather than Seq[T].  This is a temporary option to ease transition.")
+  val Yinvalidate     = StringSetting     ("-Yinvalidate", "classpath-entry", "Invalidate classpath entry before run", "")
   val noSelfCheck     = BooleanSetting    ("-Yno-self-type-checks", "Suppress check for self-type conformance among inherited members.")
   val YvirtClasses    = false // too embryonic to even expose as a -Y //BooleanSetting    ("-Yvirtual-classes", "Support virtual classes")
 
diff --git a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
index 4d66fb5617..b36a92a186 100644
--- a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala
@@ -1457,6 +1457,9 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
       def binderToUniqueTree(b: Symbol) =
         unique(accumSubst(normalize(CODE.REF(b))), b.tpe)
 
+      @inline def /\(conds: Iterable[Cond]) = if (conds.isEmpty) Top else conds.reduceLeft(AndCond(_, _))
+      @inline def \/(conds: Iterable[Cond]) = if (conds.isEmpty) Havoc else conds.reduceLeft(OrCond(_, _))
+
       // note that the sequencing of operations is important: must visit in same order as match execution
       // binderToUniqueTree uses the type of the first symbol that was encountered as the type for all future binders
       def treeMakerToCond(tm: TreeMaker): Cond = {
@@ -1475,7 +1478,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
             }
             ttm.renderCondition(condStrategy)
           case EqualityTestTreeMaker(prevBinder, patTree, _)        => EqualityCond(binderToUniqueTree(prevBinder), unique(patTree))
-          case AlternativesTreeMaker(_, altss, _)                   => altss map (_ map treeMakerToCond reduceLeft AndCond) reduceLeft OrCond
+          case AlternativesTreeMaker(_, altss, _)                   => \/(altss map (alts => /\(alts map treeMakerToCond)))
           case ProductExtractorTreeMaker(testedBinder, None, subst) => NonNullCond(binderToUniqueTree(testedBinder))
           case ExtractorTreeMaker(_, _, _, _)
              | GuardTreeMaker(_)
@@ -1973,6 +1976,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL
               case Some(0) if testedBinder.tpe.typeSymbol == ListClass => // extractor.symbol.owner == SeqFactory
                 EqualityCond(binderToUniqueTree(p.prevBinder), unique(Ident(NilModule) setType NilModule.tpe))
               case _ =>
+                backoff = true
                 super.treeMakerToCond(tm)
             }
           case ExtractorTreeMaker(_, _, _, _) =>
diff --git a/src/compiler/scala/tools/nsc/util/ClassPath.scala b/src/compiler/scala/tools/nsc/util/ClassPath.scala
index 404490bd49..18b9c7dd01 100644
--- a/src/compiler/scala/tools/nsc/util/ClassPath.scala
+++ b/src/compiler/scala/tools/nsc/util/ClassPath.scala
@@ -312,6 +312,11 @@ class DirectoryClassPath(val dir: AbstractFile, val context: ClassPathContext[Ab
   override def toString() = "directory classpath: "+ origin.getOrElse("?")
 }
 
+class DeltaClassPath[T](original: MergedClassPath[T], oldEntry: ClassPath[T], newEntry: ClassPath[T]) 
+extends MergedClassPath[T](original.entries map (e => if (e == oldEntry) newEntry else e), original.context) {
+  require(original.entries contains oldEntry)
+}
+
 /**
  * A classpath unifying multiple class- and sourcepath entries.
  */
diff --git a/test/files/neg/patmatexhaust.check b/test/files/neg/patmatexhaust.check
index 6172811e13..1168f36e11 100644
--- a/test/files/neg/patmatexhaust.check
+++ b/test/files/neg/patmatexhaust.check
@@ -18,10 +18,6 @@ patmatexhaust.scala:53: error: match may not be exhaustive.
 It would fail on the following input: Gp()
     def ma5(x:Deep) = x match {
                       ^
-patmatexhaust.scala:59: error: match may not be exhaustive.
-It would fail on the following input: Nil
-  def ma6()  = List(1,2) match { // give up
-                   ^
 patmatexhaust.scala:75: error: match may not be exhaustive.
 It would fail on the following input: B()
   def ma9(x: B) = x match {
@@ -38,4 +34,4 @@ patmatexhaust.scala:126: error: match may not be exhaustive.
 It would fail on the following input: C1()
     def ma10(x: C) = x match { // not exhaustive: C1 is not abstract.
                      ^
-10 errors found
+9 errors found
diff --git a/test/files/neg/t5845.check b/test/files/neg/t5845.check
new file mode 100644
index 0000000000..8c6100d6de
--- /dev/null
+++ b/test/files/neg/t5845.check
@@ -0,0 +1,7 @@
+t5845.scala:9: error: value +++ is not a member of Int
+  println(5 +++ 5)
+            ^
+t5845.scala:15: error: value +++ is not a member of Int
+  println(5 +++ 5)
+            ^
+two errors found
diff --git a/test/files/neg/t5845.scala b/test/files/neg/t5845.scala
new file mode 100644
index 0000000000..823c722c14
--- /dev/null
+++ b/test/files/neg/t5845.scala
@@ -0,0 +1,16 @@
+class Num[T] {
+  def mkOps = new Ops
+  class Ops { def +++(rhs: T) = () }
+}
+
+class A {
+  implicit def infixOps[T, CC[X] <: Num[X]](lhs: T)(implicit num: CC[T]) = num.mkOps
+  implicit val n1 = new Num[Int] { }
+  println(5 +++ 5)
+}
+
+class B {
+  implicit def infixOps[T, CC[X] <: Num[X]](lhs: T)(implicit num: CC[T]) : CC[T]#Ops = num.mkOps
+  implicit val n1 = new Num[Int] {}
+  println(5 +++ 5)
+}
diff --git a/test/files/pos/exhaustive_heuristics.scala b/test/files/pos/exhaustive_heuristics.scala
index f6bea455a5..297900510b 100644
--- a/test/files/pos/exhaustive_heuristics.scala
+++ b/test/files/pos/exhaustive_heuristics.scala
@@ -12,5 +12,15 @@ object Test {
     case _ if turnOffChecks =>
   }
 
-  // TODO: we back off when there are any user-defined extractors
+  // we back off when there are any user-defined extractors
+  // in fact this is exhaustive, but we pretend we don't know since List's unapplySeq is not special to the compiler
+  // to compensate our ignorance, we back off
+  // well, in truth, we do rewrite List() to Nil, but otherwise we do nothing
+  // the full rewrite List(a, b) to a :: b :: Nil, for example is planned (but not sure it's a good idea)
+  List(true, false) match {
+    case List(_, _, _*) =>
+    case List(node, _*)  =>
+    case Nil =>
+  }
+
 }
\ No newline at end of file
diff --git a/test/files/pos/t4579.flags b/test/files/pos/t4579.flags
new file mode 100644
index 0000000000..1182725e86
--- /dev/null
+++ b/test/files/pos/t4579.flags
@@ -0,0 +1 @@
+-optimize
\ No newline at end of file
diff --git a/test/files/pos/t4579.scala b/test/files/pos/t4579.scala
new file mode 100644
index 0000000000..2404b19da1
--- /dev/null
+++ b/test/files/pos/t4579.scala
@@ -0,0 +1,518 @@
+//############################################################################
+// Lisp interpreter (revived as an optimizer test.)
+//############################################################################
+
+//############################################################################
+// 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 += 1
+    i < s.length()
+  }
+  def next: String = 
+    if (hasNext) {
+      val start = i
+      if (isDelimiter(s charAt i)) i += 1
+      else 
+        do i = i + 1
+        while (!isDelimiter(s charAt i))
+      s.substring(start, i)
+    } else sys.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 =
+    sys.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 (x <- range(1, indent)) Console.print(" ");
+      Console.println("===> " + x);
+      indent = indent + 1;
+    }
+    val result = eval1(x, env);
+    if (trace) {
+      indent = indent - 1;
+      for (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 _ => sys.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 == ")") sys.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 {
+
+  import List._;
+
+  type Data = Any;
+
+  case class Lambda(f: List[Data] => Data);
+
+  var curexp: Data = null;
+  var trace: Boolean = false;
+  var indent: Int = 0;
+
+  def lispError[a](msg: String): a =
+    sys.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 asList(x: Data): List[Data] = x match {
+    case y: List[_] => y
+    case _ => lispError("malformed list: " + x)
+  }
+
+  def asInt(x: Data): Int = x match {
+    case y: Int => y
+    case _ => lispError("not an integer: " + x)
+  }
+
+  def asString(x: Data): String = x match {
+    case y: String => y
+    case _ => lispError("not a string: " + x)
+  }
+
+  def asBoolean(x: Data): Boolean = x != 0
+
+  def normalize(x: Data): Data = x match {
+    case 'and :: x :: y :: Nil =>
+      normalize('if :: x :: y :: 0 :: Nil)
+    case 'or :: x :: y :: Nil =>
+      normalize('if :: x :: 1 :: y :: Nil)
+    case 'def :: (name :: args) :: body :: expr :: Nil =>
+      normalize('def :: name :: ('lambda :: args :: body :: Nil) :: expr :: Nil)
+    case 'cond :: ('else :: expr :: Nil) :: rest =>
+        normalize(expr);
+    case 'cond :: (test :: expr :: Nil) :: rest =>
+	normalize('if :: test :: expr :: ('cond :: rest) :: Nil)
+    case 'cond :: 'else :: expr :: Nil =>
+      normalize(expr)
+    case h :: t =>
+      normalize(h) :: asList(normalize(t))
+    case _ =>
+      x
+  }
+
+  def eval(x: Data, env: Environment): Data = {
+    val prevexp = curexp;
+    curexp = x;
+    if (trace) {
+      for (x <- range(1, indent)) Console.print(" ");
+      Console.println("===> " + x);
+      indent += 1;
+    }
+    val result = eval1(x, env);
+    if (trace) {
+      indent -= 1;
+      for (x <- range(1, indent)) Console.print(" ");
+      Console.println("<=== " + result);
+    }
+    curexp = prevexp;
+    result
+  }
+
+  def eval1(x: Data, env: Environment): Data = x match {
+    case Symbol(name) =>
+      env lookup name
+    case 'def :: Symbol(name) :: y :: z :: Nil =>
+      eval(z, env.extendRec(name, (env1 => eval(y, env1))))
+    case 'val :: Symbol(name) :: y :: z :: Nil =>
+      eval(z, env.extend(name, eval(y, env)))
+    case 'lambda :: params :: y :: Nil =>
+      mkLambda(params, y, env)
+    case 'if :: c :: y :: z :: Nil =>
+      if (asBoolean(eval(c, env))) eval(y, env) else eval(z, env)
+    case 'quote :: y :: Nil =>
+      y
+    case y :: z =>
+      apply(eval(y, env), z map (x => eval(x, env)))
+    case Lambda(_) => x
+    case y: String => x
+    case y: Int => x
+    case y => lispError("illegal term")
+  }
+
+  def lisp2string(x: Data): String = x match {
+    case Symbol(name) => name
+    case Nil => "()"
+    case y :: ys =>
+      def list2string(xs: List[Data]): String = xs match {
+        case List() => ""
+        case y :: ys => " " + lisp2string(y) + list2string(ys)
+      }
+      "(" + lisp2string(y) + list2string(ys) + ")"
+    case _ => if (x.isInstanceOf[String]) "\"" + x + "\""; else x.toString()
+  }
+
+  def apply(fn: Data, args: List[Data]): Data = fn match {
+    case Lambda(f) => f(args);
+    case _ => lispError("application of non-function: " + fn + " to " + args);
+  }
+
+  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] = asList(params) map {
+      case Symbol(name) => name
+      case _ => sys.error("illegal parameter list");
+    }
+
+    Lambda(args => eval(expr, extendEnv(env, ps, args)))
+  }
+
+  val globalEnv = EmptyEnvironment
+    .extend("=", Lambda{
+      case List(arg1, arg2) => if(arg1 == arg2) 1 else 0})
+    .extend("+", Lambda{
+      case List(arg1: Int, arg2: Int) => arg1 + arg2
+      case List(arg1: String, arg2: String) => arg1 + arg2})
+    .extend("-", Lambda{
+      case List(arg1: Int, arg2: Int) => arg1 - arg2})
+    .extend("*", Lambda{
+      case List(arg1: Int, arg2: Int) => arg1 * arg2})
+    .extend("/", Lambda{
+      case List(arg1: Int, arg2: Int) => arg1 / arg2})
+    .extend("nil", Nil)
+    .extend("cons", Lambda{
+      case List(arg1, arg2) => arg1 :: asList(arg2)})
+    .extend("car", Lambda{
+      case List(x :: xs) => x})
+    .extend("cdr", Lambda{
+      case List(x :: xs) => xs})
+    .extend("null?", Lambda{
+      case List(Nil) => 1
+      case _ => 0});
+
+  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 == ")") sys.error("unbalanced parentheses")
+      //else if (Character.isDigit(token.charAt(0)))
+      else if (token.charAt(0).isDigit)
+        token.toInt
+      else if (token.charAt(0) == '\"' && token.charAt(token.length()-1)=='\"')
+        token.substring(1,token.length() - 1)
+      else Symbol(token)
+    }
+    def parseList: List[Data] = {
+      val token = it.next;
+      if (token == ")") Nil else parseExpr(token) :: parseList
+    }
+    parseExpr(it.next)
+  }
+}
+
+//############################################################################
+// List User
+
+class LispUser(lisp: Lisp) {
+
+  import lisp._;
+
+  def evaluate(s: String) = lisp2string(lisp.evaluate(s));
+
+  def run = {
+
+    Console.println(string2lisp("(lambda (x) (+ (* x x) 1))").asInstanceOf[AnyRef]);
+    Console.println(lisp2string(string2lisp("(lambda (x) (+ (* x x) 1))")));
+    Console.println;
+
+    Console.println("(    '(1 2 3)) = " + evaluate("     (quote(1 2 3))"));
+    Console.println("(car '(1 2 3)) = " + evaluate("(car (quote(1 2 3)))"));
+    Console.println("(cdr '(1 2 3)) = " + evaluate("(cdr (quote(1 2 3)))"));
+    Console.println("(null? '(2 3)) = " + evaluate("(null? (quote(2 3)))"));
+    Console.println("(null?    '()) = " + evaluate("(null?    (quote()))"));
+    Console.println;
+
+    Console.println("faculty(10) = " + evaluate(
+      "(def (faculty n) " +
+        "(if (= n 0) " +
+          "1 " +
+          "(* n (faculty (- n 1)))) " +
+        "(faculty 10))"));
+    Console.println("faculty(10) = " + evaluate(
+      "(def (faculty n) " +
+        "(cond " +
+          "((= n 0) 1) " +
+          "(else (* n (faculty (- n 1))))) " +
+        "(faculty 10))"));
+    Console.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))))))))))"));
+    Console.println;
+  }
+}
+
+//############################################################################
+// Main
+
+object Test {
+  def main(args: Array[String]) {
+    new LispUser(LispCaseClasses).run;
+    new LispUser(LispAny).run;
+    ()
+  }
+}
+
+//############################################################################