Monday, May 16, 2005

Intermediate Trees

Well, I have Intermediate Tree (IT) output from my tiger compiler. I received some help with the IT generation, but the text output is just not readable. So, what I did was generated a graphical representation using graphviz.

The most difficult thing about IT generation is following static links. I am going to show you the tree and the code that generates it.

/* define a recursive function */let/* calculate n! */function nfactor(n: int): int =  if  n = 0    then 1   else n * nfactor(n-1)in nfactor(10)end

and here is the tree

The tree on the right shows the main code

Can you guess what tree the following code will generate
let  type any = {any : int} var buffer := getchar()function readint(any: any) : int = let var i := 0     function isdigit(s : string) : int =     ord(buffer)>=ord("0") &          ord(buffer)<=ord("9")     function skipto() =       while buffer=" " | buffer="\n"         do buffer := getchar()  in skipto();     any.any := isdigit(buffer);     while isdigit(buffer)       do (i := i*10+ord(buffer)-ord("0");             buffer := getchar());     i end type list = {first: int, rest: list} function readlist() : list =    let var any := any{any=0}        var i := readint(any)     in if any.any         then list{first=i,rest=readlist()}         else nil    end function merge(a: list, b: list) : list =   if a=nil then b   else if b=nil then a   else if a.first < b.first       then        list{first=a.first,rest=merge(a.rest,b)}      else        list{first=b.first,rest=merge(a,b.rest)} function printint(i: int) =  let function f(i:int) = if i>0       then (f(i/10);         print(chr(i-i/10*10+ord("0"))))   in if i<0 then (print("-"); f(-i))      else if i>0 then f(i)      else print("0")  end function printlist(l: list) =   if l=nil then print("\n")   else (printint(l.first); print(" ");        printlist(l.rest))   var list1 := readlist()   var list2 := (buffer:=getchar();                    readlist())  /* BODY OF MAIN PROGRAM */ in printlist(merge(list1,list2))end

Well, the tree could take up a whole room, so here is the
condensed version

If you find too many long left/right subtrees, well they are due to static links. The language is tiger, see Andrew Appel's Home Page for more details

WARNING: The IT have not been checked for correctness, I can only hope they are correct.