diff options
author | michelou <michelou@epfl.ch> | 2006-02-22 17:54:31 +0000 |
---|---|---|
committer | michelou <michelou@epfl.ch> | 2006-02-22 17:54:31 +0000 |
commit | 96ae92e4f6f830a9a4e55768c3de0328a2a030ba (patch) | |
tree | 0b84d247c1693bf186787aaa8f0c75d89fea9be3 /docs/examples/typeinf.scala | |
parent | c1e184a3657d970a8fba6e3c7049f20a2e466bf0 (diff) | |
download | scala-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.scala | 109 |
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>" + ) } - |