29 Jul 2006 14:09:19 -0400

Related articles |
---|

Rich versus Simple ASTs johan.tibell@gmail.com (Johan Tibell) (2006-07-28) |

Re: Rich versus Simple ASTs haberg@math.su.se (2006-07-29) |

Re: Rich versus Simple ASTs jakacki@gmail.com (Grzegorz Jakacki) (2006-07-29) |

Re: Rich versus Simple ASTs holgersiegel74@yahoo.de (Holger Siegel) (2006-07-29) |

From: | Holger Siegel <holgersiegel74@yahoo.de> |

Newsgroups: | comp.compilers |

Date: | 29 Jul 2006 14:09:19 -0400 |

Organization: | Compilers Central |

References: | 06-07-091 |

Keywords: | parse, AST |

Posted-Date: | 29 Jul 2006 14:09:19 EDT |

Am Samstag, 29. Juli 2006 00:45 schrieb Johan Tibell:

*> Considered a grammar for lambda calculus that allows abbreviation of*

*> nested lambda abstractions:*

*>*

*> \ x. \ y. x - y*

*>*

*> this can be abbreviated as:*

*>*

*> \ x y. x - y*

*>*

*> (where \ is the lambda symbol)*

*>*

*> This convenient abbreviation can be implemented in (at least?) two*

*> different ways. Either the parser translates each occurrence of the*

*> second expression into the same AST representation used by the first or*

*> the AST uses a "richer" representation for lambda abstractions that*

*> allows for more than one variable. In Haskell syntax:*

*>*

*> data Expr = Lam Id Expr -- lambda abstraction*

*> | App Expr Expr -- function application*

*> | ...*

*>*

*> or the richer representation:*

*>*

*> data Expr = Lam [Id] Expr -- lambda abstraction*

*> | App Expr Expr -- function application*

*> | ...*

*>*

*> where [Id] denotes a list of identifiers*

I would use the first version to represent the Core of your language. The

second version is a representation of the concrete syntax of your language.

Since an AST is an Abstract /Syntax/ Tree, I would prefer the second version.

*> Would it be useful to have an AST representation like the second?*

*> More*

*> specifically, when you want compile the code and find a source line*

*> that looks like this:*

*>*

*> (\ x y. x - y) 1 2*

*>*

*> Using the second representation we could possibly detect that the*

*> function (of two arguments) is in fact applied to two arguments and*

*> thus there's no need to generate an intermediate closure. Or is it*

*> better two just use the first representation and apply some*

*> optimization that removes unnecessary closures? If so how can I*

*> implement such an optimization? Some pseudo code would be nice.*

Since all argumets are ground terms (they don't contain any identifiers),

there's no need to generate closures at all.

Let the type Env be an environment like {Id:=Core; ..}. A closed value is a

ground term or a Closure:

data Closed = Ground Core | Closure Env Core

The Core language is an applied Lambda Calculus:

data Core = Lam Id Core | App Core Core | (Int) | Core - Core | (Id)

Now, to evaluate an expressions means to call a function 'eval' with an empty

argument list in an empty environment

-- environment -> expression -> applied arguments -> result

eval :: Env -> Core -> [Closed] -> Closed

Your example goes like:

eval {} (read "(\ x y. x - y) 1 2") []

= eval {} (App (App (Lam x (Lam y (x - y))) 1) 2) []

= eval {} (App (Lam x (Lam y (x - y))) 1) [Ground 2]

= eval {} (Lam x (Lam y (x - y))) [Ground 1, Ground 2]

= eval {x:=Ground 1} (Lam y (x - y)) [Ground 2]

= eval {x:=Ground 1; y:=Ground 2} (x - y) []

= ... (*)

= Ground (-1)

(*) How did you implement delta reduction? By

(Sub 1 2),

by

(ApplyStrict (ApplyStrict Sub 1) 2),

or in some other way?

*> I guess this is a more general question. Should the richness of the*

*> language you are compiling be represented in the AST or should the AST*

*> be simplified as much as possible?*

*>*

*> P.S. The second representation could also be useful for pretty printing*

*> the expression exactly as it was written which is not possible with the*

*> first.*

My rule of thumb is to keep the AST as near as possible to the concrete

syntax. That keeps the parser and prettyprinter simple, and conversion to a

core representation is done in an explicit, clean step.

___________________________________________________________

Der frühe Vogel fängt den Wurm. Hier gelangen Sie zum neuen Yahoo! Mail: http://mail.yahoo.de

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.