<br><br><div class="gmail_quote">2010/6/22 José Romildo Malaquias <span dir="ltr"><<a href="mailto:j.romildo@gmail.com">j.romildo@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hello.<br>
<br>
I have been teaching an introductory course on compiler construction to<br>
our undergraduates students using Appel's "Modern Compiler<br>
Implementation in Java". There are also versions of the book in ML and<br>
C. The books explain how to write a compiler for the Tiger programming<br>
language.<br>
<br>
Now I want to implement a Tiger compiler in Haskell.<br>
<br>
The lexer and parser (built with the help of alex and happy) and the<br>
type checker are already working.<br>
<br>
Next step is implementing a variable escape analysis phase, needed for<br>
the intermediate code generator. The objective of this phase is to find<br>
out if each variable escapes or not. In general an escaping variable<br>
should be allocated in the stack frame (in memory). Non escaping<br>
variables may be allocated in the stack frame or in a register.<br>
<br>
Generally, a variable escapes if it is passed by reference, its address<br>
is taken (using C's & operator, for instance), or it is accessed from a<br>
nested function. Only the last is possible with Tiger.<br>
<br>
The approach adopted by Appel in his books is easy: a muttable field in<br>
the abstract syntax of variable declarations, of for expressions, and of<br>
function formal parameters, which introduce new variables, is used to<br>
collect the escaping information of the variable. In the ML version of<br>
the book this is a reference to boolean (bool ref). Initially, in a<br>
conservative approach, the reference is initialized to true.<br>
<br>
In the variable escaping analysis phase of the compiler, a function<br>
findEscape looks for escaping variables and record this information in<br>
the escape fields of the abstract syntax. To do this the entire abstract<br>
syntax tree is traversed looking for escaping uses of every variable,<br>
and, when found, the field is set to true.<br>
<br>
findEscape uses a symbol table to accomplish its work, binding variable<br>
names to a reference to boolean (the same reference used in the abstract<br>
syntax tree). When processing a variable declaraction, for instance, it<br>
inserts the variable name into the symbol table, binding it to its<br>
escaping field. When processing an expression which is a simple<br>
variable, if the variable occurs in a nested function, its binding in<br>
the symbol table is set to true. This reflects directly in the abstract<br>
syntax tree of the variable declaration, as the escape field in the<br>
variable declaration and the binding in the symbol table are the same<br>
reference to bool.<br>
<br>
I am look for good ways to implement the variable escaping analysis<br>
phase in Haskell, which is a pure language. I see two alternatives:<br>
<br>
1) adopt the same approach as Appel used in his ML version of the<br>
compiler: use a mutable reference in the IO monad (Data.IORef) to<br>
hold the variable escaping information, and write everything inside<br>
the IO monad<br>
<br>
2) build a new abstract syntax tree with updated information regarding<br>
variable escaping<br>
<br>
The second option is more elegant in my point of view, but would be much<br>
less efficient than the first one.<br></blockquote><div><br></div><div>In Haskell you will get a lot of sharing between the original AST and the updated AST. This greatly reduces the overhead of #2. Have you read Chris Okasaki's Purely Functional Datastructures book? My other bit of advice would be to code it in the purely functional way and then do some benchmarking / profiling to see that it does have sufficiently good performance characteristics. If you find that it's getting awkward to manage the purely functional code then refactor that code into a monad that hides the tedious bits.</div>
<div><br></div><div>I had some other comments to make but others here have already covered it :) (Such as using Writer or State or ST instead of IO, etc).</div><div><br></div><div>Jason</div></div>