Evaluation with Continuation Passing Style without the Cont Monad

Question

I have a task: to write a function evalCPS which evaluates expressions formalized by the ADT below, using Continuation Passing Style but without Cont Monad or similar stuff.

data Expr a = Expr a :+: Expr a
            | Expr a :/: Expr a
            | Num Int
            | Var a
            | Let a Int (Expr a)

I did it for the first three constructors, that's not so hard:

evalCPS :: Expr a -> (Int -> r) -> r

evalCPS (Num n) k = k n

evalCPS (e1 :+: e2) k =
   evalCPS e1 $ \n1 ->
   evalCPS e2 $ \n2 ->
   k (n1 + n2)

evalCPS (e1 :/: e2) k =
  evalCPS e2 $ \n2 ->
  if n2 == 0 then error "division by zero" else evalCPS e1 $ \n1 ->
  k (n1 `div` n2)

But now I'm stuck with Var and Let constructors. I think I kinda understand how to do this with monad, since I have bind operator in it, but I need an advice how to solve it directly, without using monads. Will be very thankful for help!

I think you need some kind of "environment" parameter, e.g. rho :: a -> Int to evaluate variables. You can also use a Map or association list, if you restrict a a little with a typeclass constraint. — chi
Thanks for reply! Was thinking of something like this, but I don't get where I should define this rho :: a -> Int t I mean should it be something like: evalCPS (Var v) k = k . (env v) where env :: a -> Int or i misunderstood? I'm not able to change evalCPS function's type. — gehirndienst
Without changing the type is more difficult. Perhaps you only need to handle closed terms, which define all the variables they use? If so, you could state evalCPS (Let x n e) k = evalCPS (subst x n e) k where subst is a kind of syntactic substitution helper. I'm unsure about what is the expected solution here. — chi

Fyodor Soikin Fyodor Soikin · Accepted Answer · 2019-11-25T03:12:33

You need to get yourself some sort of storage to store values for variables that get defined via Let. In the general interpreter/compiler terminology, such storage is usually called "environment". Let's define it this way:

type Env a = ...

Whenever you encounter a Let, you need to add a variable to the storage. Whenever you encounter a Var, you need to lookup the variable in the storage. Also, the whole computation should start out with an empty storage. This means that there should be three operations on storage:

emptyEnv :: Env a
lookupVar :: a -> Env a -> Int
insertVar :: (a, Int) -> Env a -> Env a

Now, your evalCPS function needs to take an Env as argument (otherwise how would it lookup variables?). This would be the environment in whose context the expression should be evaluated:

evalCPS :: Env a -> Expr a -> (Int -> r) -> r

The :+: case doesn't need to look at the environment, so it should just tunnel it through to the recursive evalCPS calls:

evalCPS env (e1 :+: e2) k =
   evalCPS env e1 $ \n1 ->
   evalCPS env e2 $ \n2 ->
   k (n1 + n2)

And similarly for the :/: case.

The Var case would lookup the variable value in the environment and just return it (by calling the continuation):

evalCPS env (Var a) k =
   k $ lookupVar a env

Simple enough.

The Let case has to construct a new environment by adding the new variable to the old one, and then evaluate the expression in the context of this new environment:

evalCPS env (Let a value e) k =
    let newEnv = insertVar (a, value) env
    in evalCPS newEnv e k

Still simple enough.

Now, how might we implement the environment itself? What should the bodies of lookupVar, insertVar, and emptyEnv look like?

Conceptually, the environment could be seen as just a function: you give it a variable identifier, it gives you back its Int value. From this understanding, the simplest possible implementation of the environment falls out:

type Env a = a -> Int

And from this, it is trivial to define lookupVar:

lookupVar :: a -> Env a -> Int
lookupVar a env = env a

emptyEnv is a bit trickier. Let's think: what should happen when the program tries to reference a variable that hasn't been defined? There is a wide range of possible answers to this question, but I will follow your lead and handle this error condition the same way you handle division by zero: simply call error:

emptyEnv :: Env a
emptyEnv _ = error "Undefined variable"

insertVar is trickier still. Let's think again: when I add a variable a with value v to an existing environment e, the result should be a new environment, such that if somebody tries to lookup variable a, the result should be value v. Let write that down:

insertVar :: Eq a => (a, Int) -> Env a -> Env a
insertVar (a, v) oldEnv = 
    \x -> if x == a then v else ???

And otherwise? Well, if somebody tries to lookup any variable other than a, the result should be the same as whatever oldEnv would give. Let's write that down too:

insertVar :: Eq a => (a, Int) -> Env a -> Env a
insertVar (a, v) oldEnv = 
    \x -> if x == a then v else oldEnv x

Simple enough. Note that, because I am using the comparison operator ==, I had to add an Eq a constraint to the type signature. And since evalCPS tries to call insertVar at some point, the constraint would bleed into evalCPS as well:

evalCPS :: Eq a => Env a -> Expr a -> (Int -> r) -> r

This is only reasonable: if we want to be able to lookup variables in our variable storage, there has to be some way of telling which variable is which.

Of course, this implementation of Env has one crucial drawback: it effectively performs a linear search on every lookup, resulting in poor performance when there are a lot of variables. While this is ok for a toy exercise, this won't do for any serious compiler or interpreter.

If better performance is desired, feel free to experiment with other ways of storing the variable -> value mapping. For example, you might want to implement your storage as a Map (which offers logarithmic lookup times):

type Env a = Map a Int

I will leave the implementations of emptyEnv, lookupVar, and insertVar as an exercise.

Evaluation with Continuation Passing Style without the Cont Monad

1 Answers