Re: Maintainable compiler design?

On Wednesday 29 Jul 2009 18:12, Michiel <mhelvens@gmail.com> wrote:
> I now made lazy properties of the relevant AST nodes. For
> example, when I want to know the type of an expression, I'll just ask
> the expression node and it will, only once, compute its own type by
> querying its subexpressions, and so on.
>...
> To be honest, I'm not sure if a design like this has been used before.


Back in the late 1980's when I developed the first version of the
FermaT Program Transformation System, one of the initial design
decisions was to use a version of Lisp as the implementation language.
AST nodes are implemented as Lisp cons cells, editing a node in the
tree involves building a new tree, sharing subtrees wherever
possible. This means that the original tree is still available via the
original root node.


Any function whose value depends only on the current node and its
decendants is "memoised": its value is computed once and then stored
in the AST node. Each AST node is a list of the form: (table, type,
value, c1, c2, ...) where cn is the nth component. "table" is a table
of values for functions. If the value is present in the table, it is
returned immediately, otherwise it is calculated and stored in the
table (using !set-cons so that the AST node is updated in-place). For
example, "variables used in this statement" is an example of such a
function.


An additional advantage is that a naive implementation of a function,
which would take exponential time to execute, will execute in linear
time. For example, the "pretty printer" computes how many lines and
characters are needed to print the current AST node. If it fits on one
line, then the corresponding string is stored. In order to pretty
print a node we need to know how big each of its components are: so
the pretty printer gets called *twice* on each component. This would
lead to exponential execution time, if the result of the first call
were not cached in the node!


FermaT is available under the GPL from here:
http://www.gkc.org.uk/fermat.html
http://www.cse.dmu.ac.uk/~mward/fermat.html


--
Martin


martin@gkc.org.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4
G.K.Chesterton web site: http://www.cse.dmu.ac.uk/~mward/gkc/
Mirrors: http://www.gkc.org.uk and http://www.gkc.org.uk/gkc

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