Abstract Syntax Tree representing a program in Haskell

Question

I've been given the following Data types:

data Aexp = N Integer | V Var | Add Aexp Aexp | Mult Aexp Aexp | Sub Aexp Aexp
data Bexp = Bcon Bool | Eq Aexp Aexp | Le Aexp Aexp | Neg Bexp | And Bexp Bexp
data Stm  = Ass Var Aexp | Skip | Comp Stm Stm | If Bexp Stm Stm | While Bexp Stm | Block DecV DecP Stm | Call Pname

For Arithmetic expressions, Boolean expressions and Statements respectively.

I have been asked to return a Stm representing the following program:

x:=5;
y:=1;
while ¬(x=1) do
    y:=y*x;
    x:=x-1

So far I have the following :

p :: Stm
p = (Ass x 5) (Ass y 1) (While (Neg (Eq x 1)) Ass x (Sub x 1) Ass y (Mult y x))

I did this simply by writing out the program on paper and then drawing a syntax tree from it. Firstly I'm not sure if this is actually correct as I don't really know how to prove it. And secondy when I compile I get lots of errors like:

denotational.hs:122:10: Not in scope: `x'
denotational.hs:122:20: Not in scope: `y'
denotational.hs:122:41: Not in scope: `x'
denotational.hs:122:51: Not in scope: `x'
denotational.hs:122:58: Not in scope: `x'
denotational.hs:122:67: Not in scope: `y'
denotational.hs:122:75: Not in scope: `y'
denotational.hs:122:77: Not in scope: `x'

Any help with this would be greatly appreciated. Thanks

You're mixing up Haskell variables and variables in your language. The Haskell variables x and y aren't defined anywhere, so you can't use them in you definition of p. You probably want to do Ass "x" 5 etc., assuming that type Var = String. — fjh
– fjh, Commented Apr 11, 2014 at 22:38
You are correct in saying that type Var = String however when I tried that with all the variables I get all kinds of errors. For example The function Ass is applied to four arguments, but its type Var -> Aexp -> Stm has only two or The function While' is applied to 7 arguments, but its type Bexp -> Stm -> Stm has only two I think I might be constructing the actual statement incorrectly compared to the data type I'm given. But I can't really see how. — James Baker
– James Baker, Commented Apr 12, 2014 at 1:21
Juxtaposition is pretty much always function application in Haskell. For example, you're applying the result of (Ass x 5) to two arguments: (Ass y 1) and (While (Neg (Eq x 1)) Ass x (Sub x 1) Ass y (Mult y x)). Since you've also already applied Ass to x and 5, the compiler complains that you've given it a total of four arguments. There is a similar problem in the call to While. — David Young
– David Young, Commented Apr 12, 2014 at 1:43
You mention correctness in your problem. One simple solution once you iron out the syntax errors is to write an interpreter that takes your syntax tree and evaluates it to a result! — crockeea
– crockeea, Commented Apr 12, 2014 at 1:50
@DavidYoung That makes sense thanks, I'm just not really sure how to get around this problem? For example how to I assign (Ass x 5) and then re-use it later whithout causing this problem. Thanks — James Baker
– James Baker, Commented Apr 12, 2014 at 12:35

J. Abrahamson · Accepted Answer · 2014-04-12 14:09:18Z

Your AST is a representation of the syntax of the (sub-)language. Everything that is in that sublanguage must be in your AST and nothing of Haskell.

So, assuming your language is fully represented by a list of Stms you might write

x:=5;

as

fragx :: [Stm]
fragx = [ Ass "x" (N 5) ]

which captures in the tree structure of your AST all of the information in that fragment from the sort of literal to the name of the variable being bound. A larger example

x:=5;
y:=1;

is

frag2 :: [Stm]
frag2 = [ Ass "x" (N 5)
        , Ass "y" (N 1)
        ]

fragy :: [Stm]
fragy = [ Ass "y" (N 1) ]

with

frag2 == fragx ++ fragy

which demonstrates how we can talk about appending two programs syntactically as the Haskell function (++) :: [Stm] -> [Stm] -> [Stm]. Again, these fragments are simple static representations of the syntax of the sublanguage. There is nothing tricky going on in the Haskell side, in particular, no bleeding of Haskell variables into sublanguage variables.

The adding final fragment might look like

fragAll :: [Stm]
fragAll = fragx ++ fragy
          ++ [ While (Neg (Eq (V "x") (N 1))) (Block ...)
             ]

but it cannot be completed without looking into the structure of the arguments to Block.

Collectives™ on Stack Overflow

Abstract Syntax Tree representing a program in Haskell

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related