"The Essence of Functional Programming" Basic Interpreter

interpreter.hs

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

interpreter.scala

/**
 * 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))
}

Digitizing books?

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?