Re: Rich versus Simple ASTs

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

Return to the comp.compilers page.
Search the comp.compilers archives again.