Created
July 13, 2011 06:04
-
-
Save mitchellh/1079807 to your computer and use it in GitHub Desktop.
"The Essence of Functional Programming" Basic Interpreter
This file contains hidden or 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
type Name = String | |
data Term = Var Name | |
| Con Int | |
| Add Term Term | |
| Lam Name Term | |
| App Term Term | |
data Value = Wrong | |
| Num Int | |
| Fun (Value -> M Value) | |
type Environment = [(Name, Value)] | |
showval :: Value -> String | |
showval Wrong = "<wrong>" | |
showval (Num i) = showint i | |
showval (Fun f) = "<function>" | |
interp :: Term -> Environment -> M Value | |
interp (Var x) e = Main.lookup x e | |
interp (Con i) e = unitM (Num i) | |
interp (Add u v) e = interp u e `bindM` (\a -> | |
interp v e `bindM` (\b -> | |
add a b)) | |
interp (Lam x v) e = unitM (Fun (\a -> interp v ((x,a):e))) | |
interp (App t u) e = interp t e `bindM` (\f -> | |
interp u e `bindM` (\a -> | |
apply f a)) | |
lookup :: Name -> Environment -> M Value | |
lookup x [] = unitM Wrong | |
lookup x ((y,b):e) = if x==y then unitM b else Main.lookup x e | |
add :: Value -> Value -> M Value | |
add (Num i) (Num j) = unitM (Num (i+j)) | |
add a b = unitM Wrong | |
apply :: Value -> Value -> M Value | |
apply (Fun k) a = k a | |
apply f a = unitM Wrong |
This file contains hidden or 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
/** | |
* The definition of a Monad is required. | |
* */ | |
trait Monad[M[_]] { | |
def unitM[A](a: A): M[A] | |
def bindM[A, B](a: M[A], f: A => M[B]): M[B] | |
def showM[A](a: M[A]): String | |
} | |
/** | |
* A basic interpreter for use in our monad example. | |
* */ | |
trait Interpreter { | |
// This is the monad that is used to hold our values | |
type M[_] | |
// This is the type that has the monad operations on it to | |
// manipulate M | |
val monadOps: Monad[M] | |
/** | |
* The rest below is basically a direct translation from Haskell | |
* to Scala of the example in Wadler's paper. | |
* */ | |
type Name = String | |
// Terms are the parts that build up our program. There are 5 | |
// types: | |
// | |
// * Variable references | |
// * Constants | |
// * Addition | |
// * Lambda | |
// * Function application | |
// | |
sealed abstract class Term | |
case class Var(name: Name) extends Term | |
case class Con(value: Int) extends Term | |
case class Add(a: Term, b: Term) extends Term | |
case class Lam(name: Name, value: Term) extends Term | |
case class App(name: Term, param: Term) extends Term | |
// Terms eventually yield values, there are only two types | |
// of values: | |
// | |
// * Number | |
// * Function which takes a value and returns a value | |
// | |
sealed abstract class Value | |
case object Wrong extends Value | |
case class Num(value: Int) extends Value | |
case class Fun(f: Value => M[Value]) extends Value | |
// The environment represents the state of the world for | |
// the interpreter, and contains a list of name to value | |
// pairs. This represents the variables. | |
type Environment = List[(Name,Value)] | |
// Takes a value and returns a string describing it. | |
def showval(value: Value) = value match { | |
case Wrong => "<wrong>" | |
case Num(i) => i.toString | |
case Fun(f) => "<function>" | |
} | |
// This is the heart of the interpreter, this takes a term and | |
// an environment and builds up the monad which contains the resulting | |
// value. | |
def interp(term: Term, env: Environment): M[Value] = term match { | |
case Var(x) => lookup(x, env) | |
case Con(i) => monadOps.unitM(Num(i)) | |
case Add(u, v) => | |
monadOps.bindM(interp(u, env), { a: Value => | |
monadOps.bindM(interp(v, env), { b: Value => | |
add(a, b) })}) | |
case Lam(x, v) => | |
monadOps.unitM(Fun(a => interp(v, (x, a) :: env))) | |
case App(t, u) => | |
monadOps.bindM(interp(t, env), { f: Value => | |
monadOps.bindM(interp(u, env), { a: Value => | |
apply(f, a) })}) | |
} | |
// Looks up a variable in the environment | |
def lookup(name: Name, env: Environment): M[Value] = env match { | |
case Nil => monadOps.unitM(Wrong) | |
case (other, value) :: rest => | |
if (name == other) | |
monadOps.unitM(value) | |
else | |
lookup(name, rest) | |
} | |
// Adds two values together, returning the result | |
def add(a: Value, b: Value): M[Value] = (a, b) match { | |
case (Num(i), Num(j)) => monadOps.unitM(Num(i + j)) | |
case _ => monadOps.unitM(Wrong) | |
} | |
// Applies a function with the given parameter and returns the result | |
def apply(value: Value, param: Value): M[Value] = value match { | |
case Fun(k) => k(param) | |
case _ => monadOps.unitM(Wrong) | |
} | |
}/** | |
* The definition of a Monad is required. | |
* */ | |
trait Monad[M[_]] { | |
def unitM[A](a: A): M[A] | |
def bindM[A, B](a: M[A], f: A => M[B]): M[B] | |
} | |
/** | |
* A basic interpreter for use in our monad example. | |
* */ | |
trait Interpreter { | |
// This is the monad that is used to hold our values | |
type M[_] | |
// This is the type that has the monad operations on it to | |
// manipulate M | |
val monadOps: Monad[M] | |
/** | |
* The rest below is basically a direct translation from Haskell | |
* to Scala of the example in Wadler's paper. | |
* */ | |
type Name = String | |
// Terms are the parts that build up our program. There are 5 | |
// types: | |
// | |
// * Variable references | |
// * Constants | |
// * Addition | |
// * Lambda | |
// * Function application | |
// | |
sealed abstract class Term | |
case class Var(name: Name) extends Term | |
case class Con(value: Int) extends Term | |
case class Add(a: Term, b: Term) extends Term | |
case class Lam(name: Name, value: Term) extends Term | |
case class App(name: Term, param: Term) extends Term | |
// Terms eventually yield values, there are only two types | |
// of values: | |
// | |
// * Number | |
// * Function which takes a value and returns a value | |
// | |
sealed abstract class Value | |
case object Wrong extends Value | |
case class Num(value: Int) extends Value | |
case class Fun(f: Value => M[Value]) extends Value | |
// The environment represents the state of the world for | |
// the interpreter, and contains a list of name to value | |
// pairs. This represents the variables. | |
type Environment = List[(Name,Value)] | |
// Takes a value and returns a string describing it. | |
def showval(value: Value) = value match { | |
case Wrong => "<wrong>" | |
case Num(i) => i.toString | |
case Fun(f) => "<function>" | |
} | |
// This is the heart of the interpreter, this takes a term and | |
// an environment and builds up the monad which contains the resulting | |
// value. | |
def interp(term: Term, env: Environment): M[Value] = term match { | |
case Var(x) => lookup(x, env) | |
case Con(i) => monadOps.unitM(Num(i)) | |
case Add(u, v) => | |
monadOps.bindM(interp(u, env), { a: Value => | |
monadOps.bindM(interp(v, env), { b: Value => | |
add(a, b) })}) | |
case Lam(x, v) => | |
monadOps.unitM(Fun(a => interp(v, (x, a) :: env))) | |
case App(t, u) => | |
monadOps.bindM(interp(t, env), { f: Value => | |
monadOps.bindM(interp(u, env), { a: Value => | |
apply(f, a) })}) | |
} | |
// Looks up a variable in the environment | |
def lookup(name: Name, env: Environment): M[Value] = env match { | |
case Nil => monadOps.unitM(Wrong) | |
case (other, value) :: rest => | |
if (name == other) | |
monadOps.unitM(value) | |
else | |
lookup(name, rest) | |
} | |
// Adds two values together, returning the result | |
def add(a: Value, b: Value): M[Value] = (a, b) match { | |
case (Num(i), Num(j)) => monadOps.unitM(Num(i + j)) | |
case _ => monadOps.unitM(Wrong) | |
} | |
// Applies a function with the given parameter and returns the result | |
def apply(value: Value, param: Value): M[Value] = value match { | |
case Fun(k) => k(param) | |
case _ => monadOps.unitM(Wrong) | |
} | |
// This runs the interpreter on the given term and returns the | |
// result as a string | |
def test(term: Term) = monadOps.showM(interp(term, Nil)) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The token 'showint' is throwing up on GHCi 7.6.3 as not defined. Neither Wadler nor prelude defines it, and I'm enough of a newbie to be lost. How is this token to be interpreted? How would I compile this?