Hello. I need to annotate abstract syntax tree with additional information in a compiler. Using the Annotations package[1] I have written the following small program: import Annotations.F.Annotated import Annotations.F.Fixpoints data ExprF r = Num Double | Var String | Add r r | Sub r r | Mul r r | Div r r deriving (Eq,Show) type BareExpr = Fix ExprF e :: BareExpr e = In (Mul (In (Num 5)) (In (Add (In (Var "x")) (In (Num 8))))) type ValExpr = Fix (Ann Double ExprF) type Memory = [(String,Double)] eval :: Memory -> BareExpr -> ValExpr eval _ (In (Num x)) = In (Ann x (Num x)) eval m (In (Var x)) = let y = case lookup x m of Just k -> k Nothing -> 0 in In (Ann y (Var x)) eval m (In (Add x y)) = op m (+) Add x y eval m (In (Sub x y)) = op m (-) Sub x y eval m (In (Mul x y)) = op m (*) Mul x y eval m (In (Div x y)) = op m (/) Div x y op m f k x y = let x'@(In (Ann v1 _)) = eval m x y'@(In (Ann v2 _)) = eval m y in In (Ann (f v1 v2) (k x' y')) With these definitions we can represent simple arithmetic expressions and we can also evaluate them, annotating each node in the abstract syntax tree with its corresponding value. Now I want to add statements to this toy language. One statement may be a print statement containing an expression whose value is to be printed, an assign statement containing an identifier and an expression, or a compound statement containing two statements to be executed in sequence. How the data types for statements can be defined? How a function to execute an statement anotating its node with the corresponding state (memory plus output) after its execution can be defined? Without annotations the type of statements could be: data Stm = PrintStm Expr | AssignStm String Expr | CompoundStm Stm Stm How to enable annotations in this case? Note that Stm uses both Expr and Stm. [1] http://hackage.haskell.org/package/Annotations Romildo
Hi Romildo,
If I understand correctly, you now want to add annotations to
mutually-recursive datatypes. The annotations package supports that.
Section 8 of our paper [1] gives an example of how to do that, and also
Chapter 6 of Martijn's MSc thesis [2].
Let me know if these references do not answer your question.
Cheers,
Pedro
[1] http://www.dreixel.net/research/pdf/gss.pdf
[2] http://martijn.van.steenbergen.nl/projects/Selections.pdf
On Thu, Apr 26, 2012 at 10:07,
Hello.
I need to annotate abstract syntax tree with additional information in a compiler.
Using the Annotations package[1] I have written the following small program:
import Annotations.F.Annotated import Annotations.F.Fixpoints
data ExprF r = Num Double | Var String | Add r r | Sub r r | Mul r r | Div r r deriving (Eq,Show)
type BareExpr = Fix ExprF
e :: BareExpr e = In (Mul (In (Num 5)) (In (Add (In (Var "x")) (In (Num 8)))))
type ValExpr = Fix (Ann Double ExprF)
type Memory = [(String,Double)]
eval :: Memory -> BareExpr -> ValExpr eval _ (In (Num x)) = In (Ann x (Num x)) eval m (In (Var x)) = let y = case lookup x m of Just k -> k Nothing -> 0 in In (Ann y (Var x)) eval m (In (Add x y)) = op m (+) Add x y eval m (In (Sub x y)) = op m (-) Sub x y eval m (In (Mul x y)) = op m (*) Mul x y eval m (In (Div x y)) = op m (/) Div x y
op m f k x y = let x'@(In (Ann v1 _)) = eval m x y'@(In (Ann v2 _)) = eval m y in In (Ann (f v1 v2) (k x' y'))
With these definitions we can represent simple arithmetic expressions and we can also evaluate them, annotating each node in the abstract syntax tree with its corresponding value.
Now I want to add statements to this toy language. One statement may be a print statement containing an expression whose value is to be printed, an assign statement containing an identifier and an expression, or a compound statement containing two statements to be executed in sequence.
How the data types for statements can be defined?
How a function to execute an statement anotating its node with the corresponding state (memory plus output) after its execution can be defined?
Without annotations the type of statements could be:
data Stm = PrintStm Expr | AssignStm String Expr | CompoundStm Stm Stm
How to enable annotations in this case? Note that Stm uses both Expr and Stm.
[1] http://hackage.haskell.org/package/Annotations
Romildo
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Thu, Apr 26, 2012 at 10:21:36AM +0200, José Pedro Magalhães wrote:
Hi Romildo,
If I understand correctly, you now want to add annotations to mutually-recursive datatypes. The annotations package supports that. Section 8 of our paper [1] gives an example of how to do that, and also Chapter 6 of Martijn's MSc thesis [2].
Let me know if these references do not answer your question.
I am reading Martijn's MSc thesis and trying some code he presents. In secton 5.1 he presents catamorphisms over fixed points. The code I am trying is attached. When evaluating the expression cata exprEval (runExpr (1+2*3)) I am getting the following error: No instance for (Functor ExprF) arising from a use of `cata' Possible fix: add an instance declaration for (Functor ExprF) In the expression: cata exprEval (runExpr (1 + 2 * 3)) In an equation for `it': it = cata exprEval (runExpr (1 + 2 * 3)) How should an instance of (Functor ExprF) be defined? It is not shown in the thesis. Romildo
Romildo,
How should an instance of (Functor ExprF) be defined? It is not shown in the thesis.
It's actually quite straigtforward: instance Functor ExprF where fmap _ (Num n) = Num n fmap _ (Var x) = Var x fmap f (Bin op l r) = Bin op (f l) (f r) As expected you get:
cata exprEval (runExpr (1+2*3)) 7.0
HTH, Stefan
On Fri, Apr 27, 2012 at 08:39:23AM -0300, romildo@malaquias.DHCP-GERAL wrote:
On Thu, Apr 26, 2012 at 10:21:36AM +0200, José Pedro Magalhães wrote:
Hi Romildo,
If I understand correctly, you now want to add annotations to mutually-recursive datatypes. The annotations package supports that. Section 8 of our paper [1] gives an example of how to do that, and also Chapter 6 of Martijn's MSc thesis [2].
Let me know if these references do not answer your question.
I am reading Martijn's MSc thesis and trying some code he presents. In secton 5.1 he presents catamorphisms over fixed points.
The code I am trying is attached.
When evaluating the expression
cata exprEval (runExpr (1+2*3))
I am getting the following error:
No instance for (Functor ExprF) arising from a use of `cata' Possible fix: add an instance declaration for (Functor ExprF) In the expression: cata exprEval (runExpr (1 + 2 * 3)) In an equation for `it': it = cata exprEval (runExpr (1 + 2 * 3))
How should an instance of (Functor ExprF) be defined? It is not shown in the thesis. [...] type Id = String
data Op = Add | Sub | Mul | Div deriving (Show)
data ExprF r = Num Double | Var Id | Bin Op r r deriving (Show)
I could write the (Functor ExprF) instance: instance Functor ExprF where fmap f expr = case expr of Num n -> Num n Var v -> Var v Bin op x y -> Bin op (f x) (f y) Romildo
For simple datatypes like this, GHC can derive the Functor implementation
for you:
{-# LANGUAGE DeriveFunctor #-}
data ExprF r = ....
deriving (..., Functor)
See http://www.haskell.org/ghc/docs/7.0.4/html/users_guide/deriving.html
-- ryan
On Fri, Apr 27, 2012 at 5:40 AM, Stefan Holdermans wrote: Romildo, I could write the (Functor ExprF) instance: instance Functor ExprF where
fmap f expr = case expr of
Num n -> Num n
Var v -> Var v
Bin op x y -> Bin op (f x) (f y) Yes, excellent. That'll do. Cheers, Stefan _______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (4)
-
j.romildo＠gmail.com -
José Pedro Magalhães -
Ryan Ingram -
Stefan Holdermans