*** empty log message ***

3 files changed, 285 insertions, 198 deletions

diff --git a/sources/examples/parsers.scala b/sources/examples/parsers.scala
index efe90fc306..3112e0346d 100644
--- a/sources/examples/parsers.scala
+++ b/sources/examples/parsers.scala
@@ -1,53 +1,79 @@
 package examples;
+abstract class Parsers[intype] {
 
-module Parse {
+  abstract class Parser {
 
-  type Result = Option[List[Char]];
+    type Result = Option[intype];
 
-  trait Parser with Function1[List[Char],Result] {
-    def &&& (def p: Parser) = new Parser {
-      def apply(in: List[Char]) = Parser.this.apply(in) match {
-        case Some(in1) => p(in1)
-        case n => n
+    def apply(in: intype): Result;
+
+    /*** p &&& q applies first p, and if that succeeds, then q
+     */
+    def &&& (def q: Parser) = new Parser {
+      def apply(in: intype): Result = Parser.this.apply(in) match {
+        case None => None
+        case Some(in1)  => q(in1)
       }
     }
 
-    def ||| (def p: Parser) = new Parser {
-      def apply(in: List[Char]) = Parser.this.apply(in) match {
-        case None() => p(in)
+    /*** p ||| q applies first p, and, if that fails, then q.
+     */
+    def ||| (def q: Parser) = new Parser {
+      def apply(in: intype): Result = Parser.this.apply(in) match {
+        case None => q(in)
         case s => s
       }
     }
   }
 
-  val empty = new Parser { def apply(in: List[Char]): Result = Some(in) }
-
-  def fail = new Parser { def apply(in: List[Char]): Result = None() }
-
-  def chrWith(p: Char => Boolean) = new Parser {
-    def apply(in: List[Char]): Result = in match {
-      case List() => None()
-      case (c :: in1) => if (p(c)) Some(in1) else None()
-    }
+  val empty = new Parser {
+    def apply(in: intype): Result = Some(in)
   }
 
-  def chr(c: Char): Parser = chrWith(d => d == c);
+  val fail = new Parser {
+    def apply(in: intype): Result = None
+  }
 
-  def opt(p: Parser): Parser = p ||| empty;
-  def rep(p: Parser): Parser = opt(rep1(p));
-  def rep1(p: Parser): Parser = p &&& rep(p);
+  def opt(p: Parser): Parser = p ||| empty;    // p? = (p | <empty>)
+  def rep(p: Parser): Parser = opt(rep1(p));   // p* = [p+]
+  def rep1(p: Parser): Parser = p &&& rep(p);  // p+ = p p*
 }
 
-module ExprParser {
-  import Parse._;
+abstract class ListParsers[intype] extends Parsers[intype] {
+
+  def chr(p: char => boolean): Parser;
 
-  def letter    =   chrWith(c => c.isLetter);
-  def digit     =   chrWith(c => c.isDigit);
+  def chr(c: char): Parser = chr(d: char => d == c);
 
-  def ident     =   letter &&& rep(letter ||| digit);
-  def number    =   digit &&& rep(digit);
+  def letter    : Parser = chr(Character.isLetter);
+  def digit     : Parser = chr(Character.isDigit);
 
-  def expr:Parser =  expr1 &&& rep((chr('+') &&& expr1) ||| (chr('-') &&& expr1));
-  def expr1     =  expr2 &&& rep((chr('*') &&& expr2) ||| (chr('/') &&& expr2));
-  def expr2     =  ident ||| number ||| (chr('(') &&& expr &&& chr(')'));
+  def ident     : Parser = letter &&& rep(letter ||| digit);
+  def number    : Parser = digit &&& rep(digit);
+  def list      : Parser = chr('(') &&& listElems &&& chr(')');
+  def listElems : Parser = expr &&& (chr(',') &&& listElems ||| empty);
+  def expr      : Parser = ident ||| number ||| list;
+}
+
+class ParseString(s: String) extends Parsers[int] {
+  val input = 0;
+  def chr(p: char => boolean) = new Parser {
+    def apply(in: int): Parser#Result =
+      if (in < s.length() && p(s charAt in)) Some(in + 1);
+      else None;
+  }
+}
+
+object Test {
+
+  def main(args: Array[String]): unit =
+    if (args.length == 1) {
+      val ps = new ListParsers[int] with ParseString(args(0));
+      ps.exprs(input) match {
+	case Some(n) =>
+	  System.out.println("parsed: " + args(0).substring(0, n));
+	case None =>
+	  System.out.println("nothing parsed");
+      }
+    } else System.out.println("usage: java examples.Test <expr-string>");
 }
diff --git a/sources/examples/parsers1.scala b/sources/examples/parsers1.scala
index bbd0a0dbe0..06e8ed0fe0 100644
--- a/sources/examples/parsers1.scala
+++ b/sources/examples/parsers1.scala
@@ -1,52 +1,49 @@
 package examples;
 
-trait Tree {}
-case class Var(n: String)                   : Tree extends Tree {}
-case class Num(n: Int)                      : Tree extends Tree {}
-case class Binop(op: Char, l: Tree, r: Tree): Tree extends Tree {}
+abstract class Parsers {
 
-module Parse {
+  type input;
 
-  trait Parser[p] {
+  trait Parser[a] {
 
-    type Result = Option[Pair[p, List[Char]]];
+    type Result = Option[Pair[a, input]];
 
-    def apply(in: List[Char]): Result;
+    def apply(in: input): Result;
 
-    def filter(p: p => Boolean) = new Parser[p] {
-      def apply(in: List[Char]): Result = Parser.this.apply(in) match {
-        case Some(Pair(x, in1)) => if (p(x)) Some(Pair(x, in1)) else None()
-        case n => n
+    def filter(pred: a => boolean) = new Parser[a] {
+      def apply(in: input): Result = Parser.this.apply(in) match {
+        case None => None
+        case Some(Pair(x, in1)) => if (pred(x)) Some(Pair(x, in1)) else None
       }
     }
 
-    def map[b](f: p => b) = new Parser[b] {
-      def apply(in: List[Char]): Result = Parser.this.apply(in) match {
+    def map[b](f: a => b) = new Parser[b] {
+      def apply(in: input): Result = Parser.this.apply(in) match {
+        case None => None
 	case Some(Pair(x, in1)) => Some(Pair(f(x), in1))
-        case None() => None()
       }
     }
 
-    def flatMap[b](f: p => Parser[b]) = new Parser[b] {
-      def apply(in: List[Char]): Result = Parser.this.apply(in) match {
-	case Some(Pair(x, in1)) => f(x)(in1)
-        case None() => None()
+    def flatMap[b](f: a => Parser[b]) = new Parser[b] {
+      def apply(in: input): Result = Parser.this.apply(in) match {
+        case None => None
+	case Some(Pair(x, in1)) => f(x).apply(in1)
       }
     }
 
-    def ||| (def p: Parser[p]) = new Parser[p] {
-      def apply(in: List[Char]): Result = Parser.this.apply(in) match {
-	case None() => p(in)
+    def ||| (def p: Parser[a]) = new Parser[a] {
+      def apply(in: input): Result = Parser.this.apply(in) match {
+	case None => p(in)
 	case s => s
       }
     }
 
     def &&& [b](def p: Parser[b]): Parser[b] =
-      for (val _ <- this; val result <- p) yield result;
+      for (val _ <- this; val x <- p) yield x;
   }
 
-  def succeed[p](x: p) = new Parser[p] {
-    def apply(in: List[Char]) = Some(Pair(x, in))
+  def succeed[a](x: a) = new Parser[a] {
+    def apply(in: input) = Some(Pair(x, in))
   }
 
   def rep[a](p: Parser[a]): Parser[List[a]] =
@@ -56,60 +53,58 @@ module Parse {
     for (val x <- p; val xs <- rep(p)) yield x :: xs;
 
   def opt[a](p: Parser[a]): Parser[Option[a]] =
-    (for (val x <- p) yield Some(x): Option[a]) ||| succeed(None(): Option[a]);
+    (for (val x <- p) yield List(x)) ||| List();
 }
 
+abstract class ExprParsers extends Parsers {
 
-module ExprParser {
-  import Parse._;
+  def any: Parser[char];
 
-  def chrWith(p: Char => Boolean) = new Parser[Char] {
-    def apply(in: List[Char]): Result = in match {
-      case List() => None()
-      case (c :: in1) => if (p(c)) Some(Pair(c, in1)) else None()
-    }
-  }
+  def chr(ch: char) =
+    for (val c <- any; c == ch) yield c;
 
-  def chr(c: Char): Parser[Char] = chrWith(d => d == c);
-
-  def letter: Parser[Char] = chrWith(c => c.isLetter);
-  def digit : Parser[Char] = chrWith(c => c.isDigit);
+  def chr(p: char => boolean) =
+    for (val c <- any; p(c)) yield c;
 
   def ident: Parser[String] =
-    for (val c <- letter; val cs <- rep(letter ||| digit))
-    yield ((c :: cs) foldr "") {(c, s) => c+ s}
-
-  def number: Parser[Int] =
-    for (val d <- digit; val ds <- rep(digit))
-    yield ((d - '0') foldl_: ds) {(x, y) => x * 10 + (y - '0')};
-
-  def expr: Parser[Tree] =
-    for {
-      val e1 <- expr1;
-      val es <- rep (
-	for {
-	  val op <- chr('+') ||| chr('-');
-	  val e <- expr1
-	} yield (x: Tree => Binop(op, x, e))
-      )
-    } yield (e1 foldl_: es) {(x,f) => f(x)}
-
-  def expr1: Parser[Tree] =
-    for {
-      val e1 <- expr2;
-      val es <- rep (
-	for {
-	  val op <- chr('*') ||| chr('/');
-	  val e <- expr2
-	} yield (x: Tree => Binop(op, x, e))
-      )
-    } yield (e1 foldl_: es) {(x,f) => f(x)}
-
-  def expr2: Parser[Tree] =
-        (for { val n <- ident } yield Var(n))
-    ||| (for { val n <- number } yield Num(n))
-    ||| (for { val _ <- chr('('); val e <- expr; val _ <- chr(')') } yield e);
-
-  private def applyAll[a](fs: List[a => a], x: a) =
-    (x foldl_: fs) { (x, f) => f(x) }
+    for (
+      val c: char <- chr(Character.isLetter);
+      val cs: List[char] <- rep(chr(Character.isLetterOrDigit))
+    ) yield (c :: cs).mkString("", "", "");
+
+  def number: Parser[int] =
+    for (
+      val d: char <- chr(Character.isDigit);
+      val ds: List[char] <- rep(chr(Character.isDigit))
+    ) yield ((d - '0') /: ds) ((x, digit) => x * 10 + digit - '0');
+
+  def list: Parser[List[Tree]] =
+    for (
+      val _ <- chr('(');
+      val es <- listElems ||| succeed(List());
+      val _ <- chr(')')
+    ) yield es;
+
+  def listElems: Parser[List[Any]] =
+    for (
+      val x <- expr;
+      val xs <- chr(',') &&& listElems ||| succeed(List())
+    ) yield x :: xs;
+
+  def expr: Parser[Any] =
+    list ||| ident ||| number;
+
 }
+
+object Test {
+  def main(args: Array[String]) =
+    System.out.println(
+      if (args.length == 1)
+	new ExprParserFamily(args(0)).expr(0) match {
+	  case Some(Pair(tree, _)) => tree.toString();
+	  case None => "Syntax error"
+	}
+      else "usage: java examples.Test <expr-string>"
+    );
+}
+
diff --git a/sources/examples/typeinf.scala b/sources/examples/typeinf.scala
index 0a3a96819e..77976be656 100644
--- a/sources/examples/typeinf.scala
+++ b/sources/examples/typeinf.scala
@@ -1,49 +1,41 @@
 package examples;
 
 trait Term {}
-case class Var(x: String)                   extends Term {}
-case class Lam(x: String, e: Term)          extends Term {}
-case class App(f: Term, e: Term)            extends Term {}
-case class Let(x: String, e: Term, f: Term) extends Term {}
-
-object types {
-  trait Type {}
-  case class Tyvar(a: String) extends Type {}
-  case class Arrow(t1: Type, t2: Type) extends Type {}
-  case class Tycon(k: String, ts: List[Type]) extends Type {}
-  private var n: Int = 0;
-  def newTyvar: Type = { n = n + 1 ; Tyvar("a" + n) }
-}
-import types._;
-
-case class ListSet[a](elems: List[a]) {
-
-  def contains(y: a): Boolean = elems match {
-    case List() => false
-    case x :: xs => (x == y) || (xs contains y)
-  }
 
-  def union(ys: ListSet[a]): ListSet[a] = elems match {
-    case List() => ys
-    case x :: xs =>
-      if (ys contains x) ListSet(xs) union ys
-      else ListSet(x :: (ListSet(xs) union ys).elems)
-  }
+case class Var(x: String)                   extends Term {
+  override def toString() = x
+}
+case class Lam(x: String, e: Term)          extends Term {
+  override def toString() = "(\\" + x + "." + e + ")"
+}
+case class App(f: Term, e: Term)            extends Term {
+  override def toString() = "(" + f + " " + e + ")"
+}
+case class Let(x: String, e: Term, f: Term) extends Term {
+  override def toString() = "let " + x + " = " + e + " in " + f;
+}
 
-  def diff(ys: ListSet[a]): ListSet[a] = elems match {
-    case List() => ListSet(List())
-    case x :: xs =>
-      if (ys contains x) ListSet(xs) diff ys
-      else ListSet(x :: (ListSet(xs) diff ys).elems)
-  }
+sealed trait Type {}
+case class Tyvar(a: String) extends Type {
+  override def toString() = a
+}
+case class Arrow(t1: Type, t2: Type) extends Type {
+  override def toString() = "(" + t1 + "->" + t2 + ")"
+}
+case class Tycon(k: String, ts: List[Type]) extends Type {
+  override def toString() =
+    k + (if (ts.isEmpty) "" else ts.mkString("[", ",", "]"))
 }
 
 object typeInfer {
 
+  private var n: Int = 0;
+  def newTyvar(): Type = { n = n + 1 ; Tyvar("a" + n) }
+
   trait Subst with Function1[Type,Type] {
     def lookup(x: Tyvar): Type;
     def apply(t: Type): Type = t match {
-      case Tyvar(a) => val u = lookup(Tyvar(a)); if (t == u) t else apply(u);
+      case tv @ Tyvar(a) => val u = lookup(tv); if (t == u) t else apply(u);
       case Arrow(t1, t2) => Arrow(apply(t1), apply(t2))
       case Tycon(k, ts) => Tycon(k, ts map apply)
     }
@@ -54,26 +46,9 @@ object typeInfer {
 
   val emptySubst = new Subst { def lookup(t: Tyvar): Type = t }
 
-  def tyvars(t: Type): ListSet[String] = t match {
-    case Tyvar(a) => new ListSet(List(a))
-    case Arrow(t1, t2) => tyvars(t1) union tyvars(t2)
-    case Tycon(k, ts) => tyvars(ts)
-  }
-  def tyvars(ts: TypeScheme): ListSet[String] = ts match {
-    case TypeScheme(vs, t) => tyvars(t) diff new ListSet(vs)
-  }
-  def tyvars(ts: List[Type]): ListSet[String] = ts match {
-    case List() => new ListSet[String](List())
-    case t :: ts1 => tyvars(t) union tyvars(ts1)
-  }
-  def tyvars(env: Env): ListSet[String] = env match {
-    case List() => new ListSet[String](List())
-    case Pair(x, t) :: env1 => tyvars(t) union tyvars(env1)
-  }
-
-  case class TypeScheme(vs: List[String], t: Type) {
+  case class TypeScheme(tyvars: List[Tyvar], tpe: Type) {
     def newInstance: Type =
-      vs.foldLeft(emptySubst) { (s, a) => s.extend(Tyvar(a), newTyvar) } (t);
+      (emptySubst /: tyvars) ((s, tv) => s.extend(tv, newTyvar())) (tpe);
   }
 
   type Env = List[Pair[String, TypeScheme]];
@@ -84,50 +59,66 @@ object typeInfer {
   }
 
   def gen(env: Env, t: Type): TypeScheme =
-    TypeScheme((tyvars(t) diff tyvars(env)).elems, t);
+    TypeScheme(tyvars(t) diff tyvars(env), t);
 
-  def mgu(t: Type, u: Type)(s: Subst): Subst = Pair(s(t), s(u)) match {
-    case Pair(Tyvar( a), Tyvar(b)) if (a == b) =>
+  def tyvars(t: Type): List[Tyvar] = t match {
+    case tv @ Tyvar(a) => List(tv)
+    case Arrow(t1, t2) => tyvars(t1) union tyvars(t2)
+    case Tycon(k, ts) => (List[Tyvar]() /: ts) ((tvs, t) => tvs union tyvars(t));
+  }
+
+  def tyvars(ts: TypeScheme): List[Tyvar] =
+    tyvars(ts.tpe) diff ts.tyvars;
+
+  def tyvars(env: Env): List[Tyvar] =
+    (List[Tyvar]() /: env) ((tvs, nt) => tvs union tyvars(nt._2));
+
+  def mgu(t: Type, u: Type, s: Subst): Subst = Pair(s(t), s(u)) match {
+    case Pair(Tyvar(a), Tyvar(b)) if (a == b) =>
       s
-    case Pair(Tyvar(a), _) =>
-      if (tyvars(u) contains a) error("unification failure: occurs check")
-      else s.extend(Tyvar(a), u)
+    case Pair(Tyvar(a), _) if !(tyvars(u) contains a) =>
+      s.extend(Tyvar(a), u)
     case Pair(_, Tyvar(a)) =>
-      mgu(u, t)(s)
+      mgu(u, t, s)
     case Pair(Arrow(t1, t2), Arrow(u1, u2)) =>
-      mgu(t1, u1)(mgu(t2, u2)(s))
+      mgu(t1, u1, mgu(t2, u2, s))
     case Pair(Tycon(k1, ts), Tycon(k2, us)) if (k1 == k2) =>
-      ((ts zip us) map {case Pair(t,u) => mgu(t,u)}).foldLeft(s) { (s, f) => f(s) }
-    case _ => error("unification failure");
+      (s /: (ts zip us)) ((s, tu) => mgu(tu._1, tu._2, s))
+    case _ => throw new TypeError("cannot unify " + s(t) + " with " + s(u))
   }
 
-  def tp(env: Env, e: Term, t: Type)(s: Subst): Subst = e match {
-    case Var(x) => {
-      val u = lookup(env, x);
-      if (u == null) error("undefined: x");
-      else mgu(u.newInstance, t)(s)
-    }
-    case Lam(x, e1) => {
-      val a = newTyvar, b = newTyvar;
-      val s1 = mgu(t, Arrow(a, b))(s);
-      val env1 = Pair(x, TypeScheme(List(), a)) :: env;
-      tp(env1, e1, b)(s1)
-    }
-    case App(e1, e2) => {
-      val a = newTyvar;
-      val s1 = tp(env, e1, Arrow(a, t))(s);
-      tp(env, e2, a)(s1)
-    }
-    case Let(x, e1, e2) => {
-      val a = newTyvar;
-      val s1 = tp(env, e1, a)(s);
-      tp(Pair(x, gen(env, s1(a))) :: env, e2, t)(s1)
+  case class TypeError(s: String) extends Exception(s) {}
+
+  def tp(env: Env, e: Term, t: Type, s: Subst): Subst = {
+    current = e;
+    e match {
+      case Var(x) =>
+	val u = lookup(env, x);
+	if (u == null) throw new TypeError("undefined: " + x);
+	else mgu(u.newInstance, t, s)
+
+      case Lam(x, e1) =>
+	val a = newTyvar(), b = newTyvar();
+	val s1 = mgu(t, Arrow(a, b), s);
+	val env1 = Pair(x, TypeScheme(List(), a)) :: env;
+	tp(env1, e1, b, s1)
+
+      case App(e1, e2) =>
+	val a = newTyvar();
+	val s1 = tp(env, e1, Arrow(a, t), s);
+	tp(env, e2, a, s1)
+
+      case Let(x, e1, e2) =>
+	val a = newTyvar();
+	val s1 = tp(env, e1, a, s);
+	tp(Pair(x, gen(env, s1(a))) :: env, e2, t, s1)
     }
   }
+  var current: Term = null;
 
   def typeOf(env: Env, e: Term): Type = {
-    val a = newTyvar;
-    tp(env, e, a)(emptySubst)(a)
+    val a = newTyvar();
+    tp(env, e, a, emptySubst)(a)
   }
 }
 
@@ -137,7 +128,7 @@ object predefined {
   def listType(t: Type) = Tycon("List", List(t));
 
   private def gen(t: Type): typeInfer.TypeScheme = typeInfer.gen(List(), t);
-  private val a = newTyvar;
+  private val a = typeInfer.newTyvar();
   val env = List(
 /*
     Pair("true", gen(booleanType)),
@@ -155,11 +146,86 @@ object predefined {
   )
 }
 
-object test with Executable {
+abstract class MiniMLParsers[intype] extends CharParsers[intype] {
+
+  /** whitespace */
+  def whitespace = rep{chr(' ') ||| chr('\t') ||| chr('\n')};
+
+  /** A given character, possible preceded by whitespace */
+  def wschr(ch: char) = whitespace &&& chr(ch);
+
+  /** identifiers or keywords */
+  def id: Parser[String] =
+    for (
+      val c: char <- rep(chr(' ')) &&& chr(Character.isLetter);
+      val cs: List[char] <- rep(chr(Character.isLetterOrDigit))
+    ) yield (c :: cs).mkString("", "", "");
+
+  /** Non-keyword identifiers */
+  def ident: Parser[String] =
+    for (val s <- id; s != "let" && s != "in") yield s;
+
+  /** term = '\' ident '.' term | term1 {term1} | let ident "=" term in term */
+  def term: Parser[Term] =
+    ( for (
+	val _ <- wschr('\\');
+	val x <- ident;
+	val _ <- wschr('.');
+	val t <- term)
+      yield Lam(x, t): Term )
+    |||
+    ( for (
+        val letid <- id; letid == "let";
+        val x <- ident;
+	val _ <- wschr('=');
+        val t <- term;
+	val inid <- id; inid == "in";
+	val c <- term)
+      yield Let(x, t, c) )
+    |||
+    ( for (
+	val t <- term1;
+	val ts <- rep(term1))
+      yield (t /: ts)((f, arg) => App(f, arg)) );
+
+  /** term1 = ident | '(' term ')' */
+  def term1: Parser[Term] =
+    ( for (val s <- ident)
+      yield Var(s): Term )
+    |||
+    ( for (
+	val _ <- wschr('(');
+	val t <- term;
+	val _ <- wschr(')'))
+      yield t );
+
+  /** all = term ';' */
+  def all: Parser[Term] =
+    for (
+      val t <- term;
+      val _ <- wschr(';'))
+    yield t;
+}
+
+object testInfer {
 
-// def showType(e: Term) = typeInfer.typeOf(predefined.env, e);
-  def showType(e: Term) = typeInfer.typeOf(Nil, e);
+  def showType(e: Term): String =
+    try {
+      typeInfer.typeOf(predefined.env, e).toString();
+    } catch {
+      case typeInfer.TypeError(msg) =>
+	"\n cannot type: " + typeInfer.current +
+	"\n reason: " + msg;
+    }
 
-  Console.println(
-    showType(Lam("x", App(App(Var("cons"), Var("x")), Var("nil")))));
+  def main(args: Array[String]): unit = {
+    val ps = new MiniMLParsers[int] with ParseString(args(0));
+    ps.all(ps.input) match {
+      case Some(Pair(term, _)) =>
+	System.out.println("" + term + ": " + showType(term));
+      case None =>
+	System.out.println("syntax error");
+    }
+  }
 }
+