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.

5 comments:

Gops said...

If you've coded it, it _must_ be correct. Man! I can't believe you did IT's in one weekend!

Balbir Singh said...

Man! it took a lot of inspiration to finish the IT work. I am not sure of the correctness of the implementation, thanks for kudos though. I did not finish it in a weekend, I have been working on it bit by bit. It will be fun to generate the final assembly, when I get there.

For now, tiger is on a hold!

kattricker said...

Hey Balbir, have been a keen visitor to your blog. So far most things have gone over the head! Hope to catch up sometime. You did recognize me, didnt you?

kattricker said...

oh well, saw your other blog about Harsha and me a lil late...

Balbir Singh said...

Thats modesty Karthik. I am sure you understand it all.

I should start posting about my travel, once I get my camera into action again.

Dynamic programming for the binomial coefficient

More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don'...