Rich versus Simple ASTs

(This post is a result of my thinking since I've posted "Representing
Closures in C" at an earlier date in this news group).


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


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.


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.

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