A Strict GCL Interpreter in Haskell

[Hector Guilarte]

Hi everyone!

(First of all, I don't know Monads!)

I made a GCL (Guarded Command Language) Compiler and Interpreter for my Languages and Machines course in my University with alex, happy and ghc. I still have a doubt:

1) Since Haskell is Lazy, and my GCL program is being interpreted in Haskell then my GCL is Lazy too (I know is not as simple as that but believe me, somehow it is behaving lazy). The problem is that it can't be lazy (said to me by my teacher on monday) so I tried using seq, but it didn't work, I'll paste the code after this:
Programs in GCL like:
a)
var i : value
main
    i <- 1 / 0
end

b)
var i : value
main
    i <- 1 / 0;
    show i
end

c)
var i : value
var foo : array of 2
main
    i <- foo[42]
end

d)
var i : value
var foo : array of 2
main
    i <- foo[42];
    show i
end

act like this:
a and c finish interpretation
b throws division by zero error and finish interpretation
d throws index out of bounds error and finish interpretation

Now the code:
(it is in Spanish. ListLValue is a List of L-Values for the assigments, ListExpr is the list of Expressions to be assigned, Tabla is the Symbol Table (Data.Map), actualizarVar updates a Variable in the Symbol Table with the new value "valor", ActualizarArray updates the position "indice" of an array in the Symbol Table. evalExpr evaluates an arithmetic Expression and returns an Int. Inside evalExpr are the verifications for division by zero of modulo by zero.)

evalAsignacion:: ListLvalue -> ListExpr -> Tabla -> Tabla
evalAsignacion [] [] tabla = tabla
evalAsignacion ((Lid id):valueList) (expr:exprList) tabla =
    let valor = (evalExpr expr tabla)
    in valor `seq` evalAsignacion valueList exprList (actualizarVar id valor tabla)
evalAsignacion ((LArrayPosition id exprArray):valueList) (expr:exprList) tabla =
    let valor = (evalExpr expr tabla)
        indice = (evalExpr exprArray tabla)
    in valor `seq` indice `seq` evalAsignacion valueList exprList (actualizarArray id indice valor tabla)

evalExpr:: Expr -> Tabla -> Int
evalExpr expr tabla =
    let salida = (snd (evalAritmetico expr tabla))
    in salida `seq` if (isLeft salida) then error (getLeft salida)
                              else getRight salida

--((Int,Int) is the Line and Colum, that's for error reporting)
evalAritmetico :: Expr -> Tabla -> ((Int,Int),(Either String Int))
--LET ME KNOW IF YOU NEED THIS PART TOO

Thanks in advance,

Hector Guilarte

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Daniel Fischer-4]

Am Donnerstag 02 Juli 2009 18:35:17 schrieb Hector Guilarte:

> Hi everyone!
>
> (First of all, I don't know Monads!)
>
> I made a GCL (Guarded Command Language) Compiler and Interpreter for my
> Languages and Machines course in my University with alex, happy and ghc. I
> still have a doubt:
>
> 1) Since Haskell is Lazy, and my GCL program is being interpreted in
> Haskell then my GCL is Lazy too (I know is not as simple as that but
> believe me, somehow it is behaving lazy). The problem is that it can't be
> lazy (said to me by my teacher on monday) so I tried using seq, but it
> didn't work, I'll paste the code after this:
> Programs in GCL like:
> a)
> var i : value
> main
>     i <- 1 / 0
> end
>
> b)
> var i : value
> main
>     i <- 1 / 0;
>     show i
> end
>
> c)
> var i : value
> var foo : array of 2
> main
>     i <- foo[42]
> end
>
> d)
> var i : value
> var foo : array of 2
> main
>     i <- foo[42];
>     show i
> end
>
> act like this:
> a and c finish interpretation
> b throws division by zero error and finish interpretation
> d throws index out of bounds error and finish interpretation

Sorry, I don't quite get that. Do you mean that in your interpreter a) and c) run to
completion without raising an error, although they should raise an error and terminate
upon that?
And b) and d) raise their respective error as they should?
Or what is the expected behaviour and what is the actual behaviour?

>
> Now the code:
> (it is in Spanish. ListLValue is a List of L-Values for the assigments,
> ListExpr is the list of Expressions to be assigned, Tabla is the Symbol
> Table (Data.Map), actualizarVar updates a Variable in the Symbol Table with
> the new value "valor", ActualizarArray updates the position "indice" of an
> array in the Symbol Table. evalExpr evaluates an arithmetic Expression and
> returns an Int. Inside evalExpr are the verifications for division by zero
> of modulo by zero.)
>
> evalAsignacion:: ListLvalue -> ListExpr -> Tabla -> Tabla
> evalAsignacion [] [] tabla = tabla
> evalAsignacion ((Lid id):valueList) (expr:exprList) tabla =
>     let valor = (evalExpr expr tabla)
>     in valor `seq` evalAsignacion valueList exprList (actualizarVar id
> valor tabla)
> evalAsignacion ((LArrayPosition id exprArray):valueList) (expr:exprList)
> tabla =
>     let valor = (evalExpr expr tabla)
>         indice = (evalExpr exprArray tabla)
>     in valor `seq` indice `seq` evalAsignacion valueList exprList
> (actualizarArray id indice valor tabla)
>
> evalExpr:: Expr -> Tabla -> Int
> evalExpr expr tabla =
>     let salida = (snd (evalAritmetico expr tabla))
>     in salida `seq` if (isLeft salida) then error (getLeft salida)
>                               else getRight salida
>
> --((Int,Int) is the Line and Colum, that's for error reporting)
> evalAritmetico :: Expr -> Tabla -> ((Int,Int),(Either String Int))
> --LET ME KNOW IF YOU NEED THIS PART TOO
>
>
> Thanks in advance,
>
> Hector Guilarte

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Tillmann Rendel-3]

Hi Hector,

Hector Guilarte wrote:
> 1) Since Haskell is Lazy, and my GCL program is being interpreted in Haskell
> then my GCL is Lazy too (I know is not as simple as that but believe me,
> somehow it is behaving lazy). The problem is that it can't be lazy (said to
> me by my teacher on monday).

> evalExpr:: Expr -> Tabla -> Int
> evalExpr expr tabla =
>     let salida = (snd (evalAritmetico expr tabla))
>     in salida `seq` if (isLeft salida) then error (getLeft salida)
>                               else getRight salida

I think the problem with your code is that you call error, instead of
reporting the error back to the caller. evalExpr can go wrong (consider
5 / 0), but this fact is not represented in the type:

   evalExpr:: Expr -> Tabla -> Int

The type says that for all expressions and all symbol tables, you can
produce an int result. But that is not true! So try using this more
adequate type:

   evalExpr :: Expr -> Tabla -> Either String Int

Now, for all expressions and symbol tables, evalExpr either can compute
an integer result, or it informs you that something went wrong. If you
have these kinds of types on all your functions, your main program
becomes something like:

   main = do
     code <- readAndParseFile "somefile"
     case evalProgram code of
       Left error -> putStrLn ("Error: " ++ error)
       Right () -> putStrLn "Worked fine!"

So if you need fine-grained control over error-handling, add explicit
error handling, and do not use the error function.

Good luck!

   Tillmann
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Tillmann Rendel-3]

Hi Hector,

Hector Guilarte wrote:
> I did that already, but it didn't work... Also, since this kind of error would be a run time error in my GCL Language, I don't want it to continue executing whenever an error is found, that's why I changed it back to just:
> evalExpr:: Expr -> Tabla -> Int
>
> Instead of using the Either String Int...

I think you misunderstand something.

If you use (Expr -> Table -> Int), you are announcing:
Whatever happens, I keep executing.

If you use (Expr -> Table -> Either String Int), you are announcing:
I may stop earlier because of some problem.

Since may you want to stop earlier, you should use the second type.


Let's look at a very small example, an interpreter for the following
little language:

   data Expression
     = Literal Integer
     | Add Expression Expression
     | Divide Expression Expression

Because of division by zero, an interpreter for this language may fail.
So we have two kinds of return values: Sometimes we return a number, and
sometimes we return an DivideByZero error. We can reflect that in a
datatype:

   data Result
     = Number Integer
     | DivideByZeroError

Now we can write our interpreter:

   eval :: Expression -> Result
   eval (Literal n)
     = Number n

   eval (Add a b)
     = case eval a of
         Number result_of_a
           -> case b of
                Number result_of_b
                  -> Number (result_of_a + result_of_b)

                DivideByZeroError
                  -> DivideByZeroError

         DivideByZeroError
           -> DivideByZeroError


   eval (Add a b)
     = case eval a of
         Number result_of_a
           -> case b of
                Number result_of_b
                  -> if b == 0
                       then DivideByZeroError
                       else Number (result_of_a + result_of_b)

                DivideByZeroError
                  -> DivideByZeroError

         DivideByZeroError
           -> DivideByZeroError


This interpreter will stop as soon as it encounters a division by zero,
because we take care to return DivideByZeroError whenever we see a
DivideByZeroError in one of the subterms.

So you have to use an appropriate return type (like (Either String Int)
or Result), and you have to pattern match on the result of "earlier"
parts of your program, and propagate the error.

   Tillmann
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Heinrich Apfelmus]

Tillmann Rendel wrote:

> Now we can write our interpreter:
>
>   eval :: Expression -> Result
>   eval (Literal n)
>     = Number n
>
>   eval (Add a b)
>     = case eval a of
>         Number result_of_a
>           -> case b of
>                Number result_of_b
>                  -> Number (result_of_a + result_of_b)
>
>                DivideByZeroError
>                  -> DivideByZeroError
>
>         DivideByZeroError
>           -> DivideByZeroError
>
>
>   eval (Add a b)
>     = case eval a of
>         Number result_of_a
>           -> case b of
>                Number result_of_b
>                  -> if b == 0
>                       then DivideByZeroError
>                       else Number (result_of_a + result_of_b)
>
>                DivideByZeroError
>                  -> DivideByZeroError
>
>         DivideByZeroError
>           -> DivideByZeroError
>
>
> This interpreter will stop as soon as it encounters a division by zero,
> because we take care to return DivideByZeroError whenever we see a
> DivideByZeroError in one of the subterms.
>
> So you have to use an appropriate return type (like (Either String Int)
> or Result), and you have to pattern match on the result of "earlier"
> parts of your program, and propagate the error.

And of course, these case expression are a case for the error monad. I
think that Wadler's paper is a great introduction to writing an
interpreter like the one at discussion here

  Monads for functional programming.
  Philip Wadler.
  http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf


Regards,
apfelmus

--
http://apfelmus.nfshost.com

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe