summaryrefslogtreecommitdiff
path: root/docs/examples/typeinf.scala
diff options
context:
space:
mode:
authormichelou <michelou@epfl.ch>2006-02-22 17:54:31 +0000
committermichelou <michelou@epfl.ch>2006-02-22 17:54:31 +0000
commit96ae92e4f6f830a9a4e55768c3de0328a2a030ba (patch)
tree0b84d247c1693bf186787aaa8f0c75d89fea9be3 /docs/examples/typeinf.scala
parentc1e184a3657d970a8fba6e3c7049f20a2e466bf0 (diff)
downloadscala-96ae92e4f6f830a9a4e55768c3de0328a2a030ba.tar.gz
scala-96ae92e4f6f830a9a4e55768c3de0328a2a030ba.tar.bz2
scala-96ae92e4f6f830a9a4e55768c3de0328a2a030ba.zip
adapted code to Scala 2 syntax in files src/exa...
adapted code to Scala 2 syntax in files src/examples/**/*.scala
Diffstat (limited to 'docs/examples/typeinf.scala')
-rw-r--r--docs/examples/typeinf.scala109
1 files changed, 56 insertions, 53 deletions
diff --git a/docs/examples/typeinf.scala b/docs/examples/typeinf.scala
index a9ac59968b..d9b2b5f3d1 100644
--- a/docs/examples/typeinf.scala
+++ b/docs/examples/typeinf.scala
@@ -1,4 +1,4 @@
-package examples;
+package examples
object typeinf {
@@ -14,7 +14,7 @@ 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;
+ override def toString() = "let " + x + " = " + e + " in " + f
}
sealed trait Type {}
@@ -31,18 +31,18 @@ case class Tycon(k: String, ts: List[Type]) extends Type {
object typeInfer {
- private var n: Int = 0;
+ 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;
+ trait Subst extends Function1[Type, Type] {
+ def lookup(x: Tyvar): Type
def apply(t: Type): Type = t match {
- case tv @ Tyvar(a) => val u = lookup(tv); 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)
}
def extend(x: Tyvar, t: Type) = new Subst {
- def lookup(y: Tyvar): Type = if (x == y) t else Subst.this.lookup(y);
+ def lookup(y: Tyvar): Type = if (x == y) t else Subst.this.lookup(y)
}
}
@@ -50,10 +50,10 @@ object typeInfer {
case class TypeScheme(tyvars: List[Tyvar], tpe: Type) {
def newInstance: Type =
- (emptySubst /: tyvars) ((s, tv) => s.extend(tv, newTyvar())) (tpe);
+ (emptySubst /: tyvars) ((s, tv) => s.extend(tv, newTyvar())) (tpe)
}
- type Env = List[Pair[String, TypeScheme]];
+ type Env = List[Pair[String, TypeScheme]]
def lookup(env: Env, x: String): TypeScheme = env match {
case List() => null
@@ -61,19 +61,19 @@ object typeInfer {
}
def gen(env: Env, t: Type): TypeScheme =
- TypeScheme(tyvars(t) diff tyvars(env), t);
+ TypeScheme(tyvars(t) diff tyvars(env), t)
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));
+ 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));
+ (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) =>
@@ -86,51 +86,52 @@ object typeInfer {
mgu(t1, u1, mgu(t2, u2, s))
case Pair(Tycon(k1, ts), Tycon(k2, us)) if (k1 == k2) =>
(s /: (ts zip us)) ((s, tu) => mgu(tu._1, tu._2, s))
- case _ => throw new TypeError("cannot unify " + s(t) + " with " + s(u))
+ case _ =>
+ throw new TypeError("cannot unify " + s(t) + " with " + s(u))
}
case class TypeError(s: String) extends Exception(s) {}
def tp(env: Env, e: Term, t: Type, s: Subst): Subst = {
- current = e;
+ 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)
+ 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, b = newTyvar();
- val s1 = mgu(t, Arrow(a, b), s);
- val env1 = Pair(x, TypeScheme(List(), a)) :: env;
- tp(env1, e1, b, s1)
+ val a, 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)
+ 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)
+ 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;
+ var current: Term = null
def typeOf(env: Env, e: Term): Type = {
- val a = newTyvar();
+ val a = newTyvar()
tp(env, e, a, emptySubst)(a)
}
}
object predefined {
- val booleanType = Tycon("Boolean", List());
- val intType = Tycon("Int", List());
- def listType(t: Type) = Tycon("List", List(t));
+ val booleanType = Tycon("Boolean", List())
+ val intType = Tycon("Int", List())
+ def listType(t: Type) = Tycon("List", List(t))
- private def gen(t: Type): typeInfer.TypeScheme = typeInfer.gen(List(), t);
- private val a = typeInfer.newTyvar();
+ private def gen(t: Type): typeInfer.TypeScheme = typeInfer.gen(List(), t)
+ private val a = typeInfer.newTyvar()
val env = List(
/*
Pair("true", gen(booleanType)),
@@ -148,24 +149,24 @@ object typeInfer {
)
}
- abstract class MiniMLParsers extends CharParsers {
+ mixin class MiniMLParsers extends CharParsers {
/** whitespace */
- def whitespace = rep{chr(' ') ||| chr('\t') ||| chr('\n')};
+ def whitespace = rep{chr(' ') ||| chr('\t') ||| chr('\n')}
/** A given character, possible preceded by whitespace */
- def wschr(ch: char) = whitespace &&& chr(ch);
+ 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("", "", "");
+ ) yield (c :: cs).mkString("", "", "")
/** Non-keyword identifiers */
def ident: Parser[String] =
- for (val s <- id; s != "let" && s != "in") yield s;
+ for (val s <- id; s != "let" && s != "in") yield s
/** term = '\' ident '.' term | term1 {term1} | let ident "=" term in term */
def term: Parser[Term] =
@@ -188,7 +189,7 @@ object typeInfer {
( for (
val t <- term1;
val ts <- rep(term1))
- yield (t /: ts)((f, arg) => App(f, arg)) );
+ yield (t /: ts)((f, arg) => App(f, arg)) )
/** term1 = ident | '(' term ')' */
def term1: Parser[Term] =
@@ -206,39 +207,41 @@ object typeInfer {
for (
val t <- term;
val _ <- wschr(';'))
- yield t;
+ yield t
}
class ParseString(s: String) extends Parsers {
- type intype = int;
- val input = 0;
+ type intype = int
+ val input = 0
def any = new Parser[char] {
def apply(in: int): Parser[char]#Result =
- if (in < s.length()) Some(Pair(s charAt in, in + 1)) else None;
+ if (in < s.length()) Some(Pair(s charAt in, in + 1)) else None
}
}
def showType(e: Term): String =
try {
- typeInfer.typeOf(predefined.env, e).toString();
- } catch {
+ typeInfer.typeOf(predefined.env, e).toString()
+ }
+ catch {
case typeInfer.TypeError(msg) =>
- "\n cannot type: " + typeInfer.current +
- "\n reason: " + msg;
+ "\n cannot type: " + typeInfer.current +
+ "\n reason: " + msg
}
def main(args: Array[String]): unit =
Console.println(
if (args.length == 1) {
- val ps = new MiniMLParsers with ParseString(args(0));
+ val ps = new ParseString(args(0)) with MiniMLParsers
ps.all(ps.input) match {
case Some(Pair(term, _)) =>
"" + term + ": " + showType(term)
case None =>
- "syntax error"
+ "syntax error"
}
- } else "usage: java examples.typeinf <expr-string>"
- );
+ }
+ else
+ "usage: java examples.typeinf <expr-string>"
+ )
}
-