-
-
Save jneira/1321624 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Compositional evaluator as visitor | |
import java.math.BigInteger; | |
// Syntax | |
interface Exp { | |
<X> X accept(Visitor<X> v); | |
} | |
interface Visitor<X> { | |
<X> X visit(String x); | |
<X> X visit(String x, Exp e); | |
<X> X visit(Exp l, Exp r); | |
} | |
class Var implements Exp { | |
String x; | |
Var(String x) { | |
this.x = x; | |
} | |
public <X> X accept(Visitor<X> v) { | |
return v.visit(this.x); | |
} | |
} | |
class Lam implements Exp { | |
String x; | |
Exp e; | |
Lam(String x, Exp e) { | |
this.x = x; | |
this.e = e; | |
} | |
public <X> X accept(Visitor<X> v) { | |
return v.visit(this.x, this.e); | |
} | |
} | |
class App implements Exp { | |
Exp left; | |
Exp right; | |
App(Exp left, Exp right) { | |
this.left = left; | |
this.right = right; | |
} | |
public <X> X accept(Visitor<X> v) { | |
return v.visit(this.left, this.right); | |
} | |
} | |
// Values | |
// A Value is a function or an integer | |
interface Value { | |
Value apply(Value v); | |
BigInteger getConst(); | |
} | |
abstract class Function implements Value { | |
public BigInteger getConst() { | |
throw new Error("Not an integer"); | |
} | |
} | |
class Const implements Value { | |
BigInteger i; | |
Const(BigInteger i) { | |
this.i = i; | |
} | |
public BigInteger getConst() { return this.i; } | |
public Value apply(Value v) { | |
throw new Error("Not a function"); | |
} | |
} | |
// Environments | |
abstract class Env { | |
abstract public Value lookup(String x); | |
public Env extend(String x, Value v) { | |
return new Cons_Env(x, v, this); | |
} | |
} | |
class MT_Env extends Env { | |
public Value lookup(String x) { | |
throw new Error("Unbound variable: " + x); | |
} | |
} | |
class Cons_Env extends Env { | |
String x; | |
Value v; | |
Env rest; | |
Cons_Env(String x, Value v, Env rest) { | |
this.x = x; | |
this.v = v; | |
this.rest = rest; | |
} | |
public Value lookup(String y) { | |
return this.x.equals(y) ? this.v : rest.lookup(y); | |
} | |
} | |
// Semantics | |
class Eval implements Visitor<Value> { | |
Env env; | |
Eval(Env env) { | |
this.env = env; | |
} | |
public Value visit(String x) { | |
return env.lookup(x); | |
} | |
public Value visit(final String x, final Exp e) { | |
return new Function() { | |
public Value apply(Value v) { | |
return e.accept(new Eval(env.extend(x, v))); | |
} | |
}; | |
} | |
public Value visit(Exp l, Exp r) { | |
return l.accept(this).apply(r.accept(this)); | |
} | |
} | |
// An example | |
public class Evaluator { | |
public static void main(String [] args) { | |
Exp prog = | |
new Lam("f", | |
new Lam("x", | |
new App(new Var("f"), | |
new App(new Var("f"), | |
new Var("x"))))); | |
Value twice = prog.accept(new Eval(new MT_Env())); | |
Value add1 = new Function () { | |
public Value apply(Value v) { | |
return new Const(v.getConst().add(BigInteger.ONE)); | |
} | |
}; | |
Value res = | |
// Don't even *think* about applying twice another time. | |
twice.apply(twice).apply(twice).apply(twice).apply(add1) | |
.apply(new Const(BigInteger.ZERO)); | |
System.out.println(res.getConst()); // 65536 | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment