CODEWITHSUNDEEP
haskellsyntaxtreewhile-loopabstract
James Baker
James Baker

Reputation: 333

Abstract Syntax Tree representing a program in Haskell

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

Upvotes: 0

Views: 1016

Answers (1)

J. Abrahamson
J. Abrahamson

Reputation: 74394

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.

Upvotes: 2

Related Questions