[Haskell-cafe] Tiger compiler: variable escaping analysis phase

[José Romildo Malaquias]

Hello.

I have been teaching an introductory course on compiler construction to
our undergraduates students using Appel's "Modern Compiler
Implementation in Java". There are also versions of the book in ML and
C. The books explain how to write a compiler for the Tiger programming
language.

Now I want to implement a Tiger compiler in Haskell.

The lexer and parser (built with the help of alex and happy) and the
type checker are already working.

Next step is implementing a variable escape analysis phase, needed for
the intermediate code generator. The objective of this phase is to find
out if each variable escapes or not. In general an escaping variable
should be allocated in the stack frame (in memory). Non escaping
variables may be allocated in the stack frame or in a register.

Generally, a variable escapes if it is passed by reference, its address
is taken (using C's & operator, for instance), or it is accessed from a
nested function. Only the last is possible with Tiger.

The approach adopted by Appel in his books is easy: a muttable field in
the abstract syntax of variable declarations, of for expressions, and of
function formal parameters, which introduce new variables, is used to
collect the escaping information of the variable. In the ML version of
the book this is a reference to boolean (bool ref). Initially, in a
conservative approach, the reference is initialized to true.

In the variable escaping analysis phase of the compiler, a function
findEscape looks for escaping variables and record this information in
the escape fields of the abstract syntax. To do this the entire abstract
syntax tree is traversed looking for escaping uses of every variable,
and, when found, the field is set to true.

findEscape uses a symbol table to accomplish its work, binding variable
names to a reference to boolean (the same reference used in the abstract
syntax tree). When processing a variable declaraction, for instance, it
inserts the variable name into the symbol table, binding it to its
escaping field. When processing an expression which is a simple
variable, if the variable occurs in a nested function, its binding in
the symbol table is set to true. This reflects directly in the abstract
syntax tree of the variable declaration, as the escape field in the
variable declaration and the binding in the symbol table are the same
reference to bool.

I am look for good ways to implement the variable escaping analysis
phase in Haskell, which is a pure language. I see two alternatives:

1) adopt the same approach as Appel used in his ML version of the
   compiler: use a mutable reference in the IO monad (Data.IORef) to
   hold the variable escaping information, and write everything inside
   the IO monad

2) build a new abstract syntax tree with updated information regarding
   variable escaping

The second option is more elegant in my point of view, but would be much
less efficient than the first one.

So I want to know what advices Haskell programmers has to me about
implementing this phase of the Tiger compiler in Haskell.


Regards,

Romildo
--
Computer Science Department
Universidade Federal de Ouro Preto, Brazil