Implementing mini imperative language in Haskell.

  • Context: MHB 
  • Thread starter Thread starter JamesBwoii
  • Start date Start date
  • Tags Tags
    Language
Click For Summary

Discussion Overview

The discussion revolves around implementing a mini imperative language in Haskell, specifically focusing on the creation of increment and decrement functions similar to those found in other programming languages. Participants are working with provided skeleton code to evaluate arithmetic expressions and control structures, including a factorial function that utilizes these operations.

Discussion Character

  • Technical explanation
  • Homework-related
  • Debate/contested

Main Points Raised

  • One participant expresses difficulty in implementing the increment and decrement functions and questions the correctness of their existing code.
  • Another participant points out the absence of Incr and Decr operations in the skeleton code and questions the type signature of the evalA function.
  • There is a suggestion that the assignment may not involve monads, as the participants are new to Haskell.
  • Clarifications are made regarding the expected behavior of the evalA function, particularly for the Var constructor.
  • One participant shares their implementation of the Incr and Decr functions, but encounters compilation errors related to the use of an undefined function called 'update'.
  • Another participant confirms that 'update' should be defined similarly to the provided 'get' function and discusses the correct implementation of the evalA function for constants.
  • Errors related to type mismatches in the code are discussed, with participants seeking clarification on the nature of the errors encountered during compilation.

Areas of Agreement / Disagreement

Participants generally agree on the need for the Incr and Decr operations and the correct type signature for evalA. However, there are ongoing disagreements and uncertainties regarding specific implementations and the handling of state within the language.

Contextual Notes

Participants mention various assumptions about the definitions and implementations of functions like 'get' and 'set', and there are unresolved issues regarding the correct handling of constants in the evalA function. The discussion reflects a collaborative effort to refine the code while addressing compilation errors.

JamesBwoii
Messages
71
Reaction score
0
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:
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:
Code: 
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.

Code: 
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
 
Technology news on Phys.org
JaAnTr said:
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?

JaAnTr said:
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)

JaAnTr said:
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.

JaAnTr said:
Code: 
evalA (Var v) s   = (s, v)
The right-hand side should be [m](s, get v s)[/m].

JaAnTr said:
Code: 
evalA (Incr v) s  = undefined
Well, you are told that the result should be something like
Code: 
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.
 
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:

Code: 
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:

Code: 
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!
 

Attachments

  • Screen Shot 2015-03-07 at 18.19.18.png
    Screen Shot 2015-03-07 at 18.19.18.png
    40.4 KB · Views: 114
  • Screen Shot 2015-03-07 at 18.19.48.png
    Screen Shot 2015-03-07 at 18.19.48.png
    31.6 KB · Views: 116
You are right about the type of evalA.

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

JaAnTr said:
But when compiling I get the error:

Code: 
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.
 
Evgeny.Makarov said:
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?).

Code: 
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,

Code: 
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:

Code: 
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
 
JaAnTr said:
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.
 
Evgeny.Makarov said:
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:

Code: 
------------------------- 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:

Code: 
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.

Code: 
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.
 
Last edited:
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').
 

Similar threads

Solving MIPS Runtime Error: Address Out of Range 0x00000000
  • · Replies 1 ·
Replies
1
Views
10K
Undergrad Micromass' big October challenge
  • · Replies 125 ·
5
Replies
125
Views
20K