Haskell & Language Design: Design Struggle in implementing Do-While Loop for imperative language

user_11191691 0
Viewed 188

I'm designing an imperative language but I'm having issues in implementing loop functionality. A loop would take the following form:

Do (n < 10)->
          Loop Body

I can parse a loop correctly however when it comes to evaluating the loop, two problems arise. The first is I can't exit loop without returning a faux exit success code, though I do think it's because of how I'm implementing the loop. The second issue is that I can't evaluate the body of the loop when there exists more than one expression. I discovered this because I originally had my loop represented as follows:

data HVal
  = HInteger Integer
  | HBool    Bool
  | HString  String
  | HList    [HVal]
  | Expr    HVal Op HVal  -- Arithmetic, Relational, and Boolean 
  | Assign  String HVal 
  | Do      HVal  HVal

In this instance the following evaluation function for a loop works when the body consists of a single expression:

evalDo :: Env -> HVal -> HVal -> IOThrowsError HVal
evalDo env cond expr = eval env cond >>= \x -> case x of
                                                  HBool True  -> eval env expr >>= \y -> eval env $ Do cond y
                                                  HBool False -> return $ HInteger 1

This function evaluates the following loop correctly:

n := 0
Do (n < 10)->
             n := (n + 1)

When it came to evaluating a longer loop body I found that it made more sense to change the loop representation to:

Do HVal [HVal]

My logic behind this is that a loop will consist of the guard and then a list of expressions to be evaluated upon in the loop body. I then made a change to evalDo:

evalDo :: Env -> HVal -> [HVal] -> IOThrowsError HVal
evalDo env cond expr = eval env cond >>= \x -> case x of
                                                           HBool False -> return $ HInteger 1
                                                           HBool True  -> do
                                                                   y  <- return $ map (\x -> eval env x) expr
                                                                   eval env $ Do cond expr

This however causes the following loop to go into an infinite loop:

n := 0
r := 1

Do (n < 10)->
             n := (n + 1)
             r := (r * 2)

I think the problem stems from the return when I evaluate the expression but I receive the following error when I don't have it:

Couldn't match type ‘[]’ with ‘ExceptT HError IO’
      Expected type: ExceptT HError IO (IOThrowsError HVal)
        Actual type: [IOThrowsError HVal]

Any guidance or help on this would be great.

parsing haskell
1 Answers

The first is I can't exit loop without returning a faux exit success code, though I do think it's because of how I'm implementing the loop.

To avoid that issue, imperative languages commonly define their syntax in two levels, expressions, like 1 + 2, which have values, and statements, like loops, which don't have values, but their point is their side effects. Expressions are also often considered a subset of statements by ignoring their value. Following that approach, your syntax could be reorganized to look like this:

data Expr
  = HInteger Integer
  | Expr Expr Op Expr

data Stmt
  = Block [Stmt]
  | Do Expr Stmt
  | Assign Var Expr  -- In C, an assignment is actually an expression, but it is widely considered a misfeature.
  | Eval_ Expr

(...) This however causes the following loop to go into an infinite loop:

In your interpretation of Do, you are using map, which only constructs a list of computations, but you need to compose those computations into a single one.

Use traverse_ from Data.Foldable.

  -- traverse_ (\x -> eval env x) expr
  -- or shorter, --
  traverse_ (eval env) expr
  eval env ...

As a tip for diagnosing that issue, you can tell that something is wrong from reading the code because y <- return ..., where y is not used later, is always a noop, so

  _ <- return $ map (\x -> eval env x) expr
  eval env ...

because of return, that is the same as

  eval env ...

whereas you didn't mean to ignore the map ... part.

user_68637490
Related