MHB Implementing mini imperative language in Haskell.

[JamesBwoii]

Hi, I need to implement a mini imperative language in Haskell but I'm struggling to get my head around it.

I need to implement an increment and decrement function like ++ and -- in other languages.

We've been given some skeleton code which we need to complete in order to run a factorial function using the decrement operator.

Here's the skeleton code:

data Aexp = Num Integer
          | Var Variable
          | Aexp :+: Aexp
          | Aexp :-: Aexp
          | Aexp :*: Aexp

evalA (Num n) s   = undefined
evalA (Var v) s   = undefined
evalA (a :+: b) s = undefined
evalA (a :*: b) s = undefined
evalA (a :-: b) s = undefined

Here's the factorial function which it needs to run:

factorial :: Comm
factorial = ("y" :=: Num 1) :>:
            While (Num 1 :<=: Var "x")
              ("y" :=: (Var "y" :*: Decr "x"))

runFactorial :: Integer -> Integer
runFactorial i = get "y" s
  where
    s = evalC factorial (set "x" i empty)

This is mainly to teach me about the semantics and as such I've been given nothing the following definitions:

A[v++](s)=(t,n) where t=s[v􏰀→n+1] and n=s(v)
A[v−−](s)=(t,n) where t=s[v􏰀→n−1] and n=s(v)

This is my attempt so far, but I'm struggling the with Decr and Incr functions and I'm not sure if the rest of what I have done is correct.

data Aexp = Num Integer
          | Var Variable
          | Aexp :+: Aexp
          | Aexp :-: Aexp
          | Aexp :*: Aexp
          | Incr Variable
          | Decr VariableevalA :: Aexp -> State -> (State, Integer)
evalA (Num n) s   = (s, n)
evalA (Var v) s   = (s, v)
evalA (Incr v) s  = undefined
evalA (Decr v) s = undefined
evalA (a :+: b) s0 = let (s1, na) = evalA a s0; (s2, nb) = evalA b s1 in (s2, na + nb)
evalA (a :*: b) s0 = let (s1, na) = evalA a s0; (s2, nb) = evalA b s1 in (s2, na * nb)
evalA (a :-: b) s0 = let (s1, na) = evalA a s0; (s2, nb) = evalA b s1 in (s2, na - nb)

Thanks for any help! :D

 

[Evgeny.Makarov]

Here's the skeleton code:

Why doesn't it include the Incr and Decr operations? Also, were you given that the type of evalA should be Aexp -> State -> (State, Integer) and not evalA :: Aexp -> State -> Integer? Does this assignment involve monads by chance?

This is mainly to teach me about the semantics and as such I've been given nothing the following definitions:

So, nothing or the following definitions? (Smile)

A[v++](s)=(t,n) where t=s[v􏰀→n+1] and n=s(v)
A[v−−](s)=(t,n) where t=s[v􏰀→n−1] and n=s(v)

What symbol follows v in s[v􏰀→n+1]? It is not shown correctly in my browser.

evalA (Var v) s   = (s, v)

The right-hand side should be [m](s, get v s)[/m].

evalA (Incr v) s  = undefined

Well, you are told that the result should be something like

let n = get v s in
  let t = update s v (n + 1) in
    (t, n)

where [m]update s v m[/m] returns a state that is like s but maps v into m.

 

[JamesBwoii]

Why doesn't it include the Incr and Decr operations? Also, were you given that the type of evalA should be Aexp -> State -> (State, Integer) and not evalA :: Aexp -> State -> Integer? Does this assignment involve monads by chance?

Not sure why it wasn't given, the specification says - "Complete the data type Aexp for Aexp given in coursework_1.hs, using the constructors Incr and Decr for post-increment and post-decrement. Un- comment factorial and runfactorial, which should pass type-checking." I don't know if it involves monads, but I doubt it. We've never done Haskell before and it's meant to be fairly easy coursework and from what I've just read monads are meant to be quite complex.

We weren't given that type, I have done that myself as it's one of the requirements. Is it wrong?

So, nothing or the following definitions?

That is a typo, not sure why I typed "nothing". :P

What symbol follows v in s[v􏰀→n+1]? It is not shown correctly in my browser.

Here is the relevant parts from the specification. I've taken a screenshot so you can see the symbols. :D

View attachment 4074View attachment 4075I've read through the other things you've said and put them in so my code now looks like this:

data Aexp = Num Integer
          | Var Variable
          | Aexp :+: Aexp
          | Aexp :-: Aexp
          | Aexp :*: Aexp
          | Incr Variable
          | Decr VariableevalA :: Aexp -> State -> (State, Integer)
evalA (Num n) s   = (s, n)
evalA (Var v) s   = (s, v)
evalA (Incr v) s  = let n = get v s in
                      let t = update s v (n + 1) in
                        (t, n)
evalA (Decr v) s = let n = get v s in
                      let t = update s v (n - 1) in
                        (t, n)
evalA (a :+: b) s0 = let (s1, na) = evalA a s0; (s2, nb) = evalA b s1 in (s2, na + nb)
evalA (a :*: b) s0 = let (s1, na) = evalA a s0; (s2, nb) = evalA b s1 in (s2, na * nb)
evalA (a :-: b) s0 = let (s1, na) = evalA a s0; (s2, nb) = evalA b s1 in (s2, na - nb)

But when compiling I get the error:

coursework_1.hs:54:31: Not in scope: ‘update’

coursework_1.hs:57:31: Not in scope: ‘update’

I've googled but I can't seem to find what the word "update" does or if it's built into Haskell?

Thanks!

 

[Evgeny.Makarov]

You are right about the type of evalA.

The right-hand side of [m]evalA (Var v) s[/m] is still wrong.

But when compiling I get the error:

coursework_1.hs:54:31: Not in scope: ‘update’

[m]update[/m] is a function that should be defined in your code, just like [m]get[/m]. I described what it should do. Maybe you already have it under a different name. Since I don't know how state is implemented in your program, I can't say how to write it at this point.

 

[JamesBwoii]

You are right about the type of evalA.

The right-hand side of [m]evalA (Var v) s[/m] is still wrong.

[m]update[/m] is a function that should be defined in your code, just like [m]get[/m]. I described what it should do. Maybe you already have it under a different name. Since I don't know how state is implemented in your program, I can't say how to write it at this point.

Ok, I've been given code for a get function and a set function (which I assume is the same as update?).

type Variable = String

type State = [(Variable,Integer)]

empty :: State
empty = []

set :: Variable -> Integer -> State -> State
set v n [] = [(v,n)]
set v n ((w,m):xs) | v == w = (v,n) : xs
                   | otherwise = (w,m) : set v n xs

get :: Variable -> State -> Integer
get v [] = 0
get v ((w,m):xs) | v == w = m
                 | otherwise = get v xs

So this is my code now,

data Aexp = Num Integer
          | Var Variable
          | Aexp :+: Aexp
          | Aexp :-: Aexp
          | Aexp :*: Aexp
          | Incr Variable
          | Decr VariableevalA :: Aexp -> State -> (State, Integer)
evalA (Num n) s   = (s, get n s)
evalA (Var v) s   = (s, get v s)
evalA (Incr v) s  = let n = get v s in
                      let t = set s v (n + 1) in
                        (t, n)
evalA (Decr v) s = let n = get v s in
                      let t = set s v (n - 1) in
                        (t, n)
evalA (a :+: b) s0 = let (s1, na) = evalA a s0; (s2, nb) = evalA b s1 in (s2, na + nb)
evalA (a :*: b) s0 = let (s1, na) = evalA a s0; (s2, nb) = evalA b s1 in (s2, na * nb)
evalA (a :-: b) s0 = let (s1, na) = evalA a s0; (s2, nb) = evalA b s1 in (s2, na - nb)

However, I'm getting lots of errors from the compiler such as:

Couldn't match type ‘(Variable, Integer)’ with ‘Char’
    Expected type: Variable
      Actual type: State
    In the first argument of ‘get’, namely ‘s’
    In the expression: get s n

I really don't understand the error, would you be able to explain it.

Thanks :D

 

[Evgeny.Makarov]

Ok, I've been given code for a get function and a set function (which I assume is the same as update?).

Yes, your [m]set[/m] is what I called [m]update[/m], up to the order of arguments.

Now that you corrected the line [m]evalA (Var v) s = (s, get v s)[/m], the previous line [m]evalA (Num n) s = (s, get n s)[/m] is wrong. If you have a constant in your program, you don't need to look it up in the state; you just return it. What you had previously: [m]evalA (Num n) s = (s, n)[/m], was correct. But if you have a variable, you need to return its value, which is stored in the state. A state is a function from variable names to values, in this case, integers.

Now, the error message you gave complains about the expression [m]get s n[/m], and I don't see it in your code. Perhaps you actually have [m]evalA (Num n) s = (s, get s n)[/m] and not [m](s, get n s)[/m]. The function [m]get[/m] takes a string, which is a list of Char, and a state. If you pass it a state, which is a list of pairs (Variable, Integer), i.e., (String, Integer), as the first argument, Haskell attempts to match a list of (Variable, Integer) (actually given) and a list of Char (expected). For this it compares (Variable, Integer) and Char and fails. That's the meaning of the error message. But again, you don't have to look up [m]n[/m] is the state; it is already an integer that can be returned.

You also have incorrect order of arguments to [m]set[/m]. I wrote [m]update s v (n + 1)[/m] because I did not know the type of [m]update[/m]. It should be [m]set v (n + 1) s[/m] instead.

 

[JamesBwoii]

Yes, your [m]set[/m] is what I called [m]update[/m], up to the order of arguments.

Now that you corrected the line [m]evalA (Var v) s = (s, get v s)[/m], the previous line [m]evalA (Num n) s = (s, get n s)[/m] is wrong. If you have a constant in your program, you don't need to look it up in the state; you just return it. What you had previously: [m]evalA (Num n) s = (s, n)[/m], was correct. But if you have a variable, you need to return its value, which is stored in the state. A state is a function from variable names to values, in this case, integers.

Now, the error message you gave complains about the expression [m]get s n[/m], and I don't see it in your code. Perhaps you actually have [m]evalA (Num n) s = (s, get s n)[/m] and not [m](s, get n s)[/m]. The function [m]get[/m] takes a string, which is a list of Char, and a state. If you pass it a state, which is a list of pairs (Variable, Integer), i.e., (String, Integer), as the first argument, Haskell attempts to match a list of (Variable, Integer) (actually given) and a list of Char (expected). For this it compares (Variable, Integer) and Char and fails. That's the meaning of the error message. But again, you don't have to look up [m]n[/m] is the state; it is already an integer that can be returned.

You also have incorrect order of arguments to [m]set[/m]. I wrote [m]update s v (n + 1)[/m] because I did not know the type of [m]update[/m]. It should be [m]set v (n + 1) s[/m] instead.

Ah that's great, no errors from any of that code. I did forget to mention that we'd been given some more skeleton code that we need to complete. If you wouldn't mind helping me out that would be great. I've had a go but am getting a bit stuck. Here it is:

------------------------- Boolean expressions

data Bexp = Boolean Bool
          | Aexp :==: Aexp
          | Aexp :<=: Aexp
          | Neg Bexp
          | Bexp :&: Bexp
          | Bexp :|: Bexp

evalB (Boolean b) s = undefined
evalB (a :==: b)  s = undefined
evalB (a :<=: b)  s = undefined
evalB (Neg b)     s = undefined
evalB (a :&: b)   s = undefined
evalB (a :|: b)   s = undefined------------------------- Commands

data Comm = Skip
          | Variable :=: Aexp
          | Comm :>: Comm
          | If Bexp Comm Comm
          | While Bexp Comm

evalC :: Comm -> State -> State
evalC Skip        s = s
evalC (v :=: a)   s = set v x t where (t,x) = evalA a s
evalC (c :>: d)   s = evalC d (evalC c s)
evalC (If b c d)  s | x         = evalC c t
                    | otherwise = evalC d t
                    where (t,x) = evalB b s
evalC (While b c) s | x         = evalC (While b c) (evalC c t) 
                    | otherwise = t
                    where (t,x) = evalB b s

What I think I need to do is complete the type signature for evalB and then complete the evalB functions.

Reading through to lecture notes I've done this:

data Bexp = Boolean Bool
          | Aexp :==: Aexp
          | Aexp :<=: Aexp
          | Neg Bexp
          | Bexp :&: Bexp
          | Bexp :|: Bexp

evalB :: Bexp -> State -> Bool
evalB (Boolean b) s = s
evalB (a :==: b)  s = evalA a s == evalA b s
evalB (a :<=: b)  s = evalA a s <= evalA b s
evalB (Neg b)     s = not (evalB b s)
evalB (a :&: b)   s = evalB a s && evalB b s
evalB (a :|: b)   s = evalB a s || evalB b s

But I think that could be wrong. Should the type signature be:

evalB :: Bexp -> State -> (State, Bool)?

If that's the case I guess that would make all my evalB functions wrong too.

Thanks.EDIT:

I've managed to get it working now, although I have to comment out the line:

evalB (Neg b) s = not (evalB b s)

when running runFactorial as I'm not sure how to negate a boolean so it returns both state and boolean and it isn't needed for the runFactorial function. Here's the code just to show you.

data Bexp = Boolean Bool
          | Aexp :==: Aexp
          | Aexp :<=: Aexp
          | Neg Bexp
          | Bexp :&: Bexp
          | Bexp :|: Bexp

evalB :: Bexp -> State -> (State, Bool)
evalB (Boolean b) s = (s, b)
evalB (a :==: b)  s0 = let (s1, na) = evalA a s0; (s2, nb) = evalA b s1 in (s2, na == nb)
evalB (a :<=: b)  s0 = let (s1, na) = evalA a s0; (s2, nb) = evalA b s1 in (s2, na <= nb)
evalB (Neg b)     s = not (evalB b s)
evalB (a :&: b)   s0 = let (s1, na) = evalB a s0; (s2, nb) = evalB b s1 in (s2, na && nb)
evalB (a :|: b)   s0 = let (s1, na) = evalB a s0; (s2, nb) = evalB b s1 in (s2, na || nb)

If you could perhaps help me with the negation that would be fantastic.

 

[Evgeny.Makarov]

You did conjunction and disjunction correctly, and negation is even simpler. You need to get a pair of a new state t and a Boolean result b' after evaluating b in s and return a pair (t, not b').