Haskell: Convert an expression into a list of Instructions

Question

This is a Homework Problem.

My goal is to Convert a type Expression in the form of " into a list of CPU Instructions. Given the data structures

    data Expr = Const Double | Var String | Add Expr Expr | Mult Expr Expr

    data Instr = LoadImmediate RegisterNumber -- put value here
                               RegisterValue -- the value
               | Addition RegisterNumber -- put result here 
                          RegisterNumber -- first thing to add 
                          RegisterNumber -- second thing to multiply
               | Multiply RegisterNumber -- put result here 
                          RegisterNumber -- first thing to multiply 
                          RegisterNumber -- second thing to multiply
    type RegisterNumber = Int 
    type RegisterValue = Double

Type Expression has four main functions

Const: converts a number of type double to a type expression, letting you use it.
Var: basically converts a string (i.e. "x") into a type expression letting you apply it to constant
Then then Add and Mult commands that let you add and multiply two type expressions

And we can assume that the only variable we will see is "x" and it is already in register 2. The result will arrive in register 1. There is a total of 4 registers.

So Add Const 1 (Mult (Var "x") (Const 2)) in type [Instr] would be

[LoadImmediate 3 1,
LoadImmediate 4 2,
Multiply 1 4 2,
Addition 1 3 1]

EDIT: Sorry, I for got to mention, because this is a beginner course, we only need to consider expressions of the form

(Const a) `Add` ((Var "x") `Mult` Expr)

where 'Expr' is some expression. Or in math form a0+x(a1+x(a2+x...))

I fixed my code up a little bit, now the error I'm getting is "Not in scope: data constructor 'RegNum'"

expr2Code :: Expr -> [Instr]
expr2Code expr = e2C 1 expr
e2C:: Int -> Expr -> Instr
e2C RegNum (Const y) = [LoadImmediate RegNum y]
e2C RegNum (Var "x") = []
e2C RegNum (Add expr1 expr2) = e2C 3 expr1 ++ e2C 4 expr2 ++ [Addition RegNum 3 4]
e2C RegNum (Mult expr1 expr2) = e2C 3 expr1 ++ e2C 4 expr2 ++ [Multiply RegNum 3 4]

Sorry for the long post, any help would be appreciated.

Answer 1

Well I'm assuming you have an infinite number of registers. If not you can experience the joy that is register spilling, but you'd need some more instructions to deal with dynamic memory.

There are 3 straightforward ways to do this

1. Expressions -> SSA -> Instr
2. Expressions -> CPS -> Instr
3. Expressions -> Instr

The first 2 offer much easier opportunities to optimize your use of registers and what not, but involve an intermediate language. Since we're lazy, let's do 3.

import Control.Monad.State

type Gensym  = State Int

gensym :: Gensym RegisterNumber
gensym = modify (+1) >> fmap (subtract 1) get

Now that we have a way of uniquely generating registers, we can do the wonderfully inefficient approach.

withRegister :: (RegisterNumber -> [Instr]) -> Gensym (RegisterNumber, [Instr])
withRegister f = gensym >>= \r -> return (r, f r)

compile :: Expr -> Gensym (RegisterNumber, [Instr])
compile (Const d)    = withRegister $ \r -> [LoadImmediate r d]
compile (Var   "x")  = return (2, [])
compile (Add e1 e2)  = do
  (t1, c1) <- compile e1 -- Recursively compile
  (t2, c2) <- compile e2 -- Each subexpression like you were
  withRegister $ \r -> Addition t1 t2 r : (c1 ++ c2) -- Make sure we 
                                                     -- use a unique register
compile (Mult e1 e2)  = do
  (t1, c1) <- compile e1
  (t2, c2) <- compile e2
  withRegister $ \r -> Multiply t1 t2 r : (c1 ++ c2)

compileExpr :: Expr -> [Instr]
compileExpr = reverse . snd . flip evalState 3 . compile

This basically recursively compiles each expression, concatting their various chunks of code together. This is similar to what you had, but there are 3 major differences,

1. I'm using a monad to handle the registers for me. You have to ensure that you never clobber a register you're going to need, by using a monad I ensure that all the registers I'm using are unique. This is really inefficient,but trivially correct.

2. When handling Var, I just load whatever's in register 2, since LoadImmediate wants a double and you have no mechanism for actually binding variables in your expressions.

3. Because you're not dealing with expressions, each chunk of computation has to be stuck in a register explicitly. You can't do x + y * z any more. That's why if you look at the code for Add or Mult, each subexpression is compiled to a fresh register.

Your example generates

[LoadImmediate 4 2.0,Multiply 2 4 5,LoadImmediate 3 1.0,Addition 3 5 6]

Which is correct, it multiplies 4 and x, then adds 3.