Sunday, May 31, 2009

A Narrow Road

I once had a great idea to compile to Thunk form, which is explicitly different from a stack machine, but is a simple representation for a graph rewrite system. The idea was a follows, the fac function


fac = \n -> if n = 1 then 1 else n * (fac (n-1))


Is compiled to

fac = \n -> if n = 1 then [1] else
[. . .] [*] [n] [[. .] [fac] [[. . .] [-] [n] *[1]]]


Reduces like

[fac 3]
[. . .] [*] [3] [[. .] [fac] [[. . .] [-] [3] *[1]]]
[. . .] [*] [3] [[. .] [fac] [[. . 1] [-] *[3]]]
[. . .] [*] [3] [[. .] [fac] [[. 3 1] *[-]]]
[. . .] [*] [3] [[. .] [fac] [*[- 3 1]]]
[. . .] [*] [3] [[. .] [fac] *[2]]
[. . .] [*] [3] [[. 2] *[fac]]
[. . .] [*] [3] [*[fac 2]]
[. . .] [*] [3] [[. . .] [*] [2] [[. .] [fac] [[. . .] [-] [2] *[1]]]]
... [. . .] [*] [3] [[. . .] [*] [2] [[. .] [fac] *[1]]]
... [. . .] [*] [3] [[. . .] [*] [2] *[1]]
... [. . .] [*] [3] *[2]
... *[6]


An optimizing compiler shouldn't push constants, so would evaluate (generate code) like this


fac = \n -> if n = 1 then 1 else
[* n .] [[fac .] *[[- n 1]]]


I am trying to get rid of the thunk form, to simplify the internal representation, and just use a dot to show where an application series is expecting an argument. I.e. the brackets now are simple parenthesis denoting subformulas, and after 'dotting' the formula it is 'linearized', i.e. the order of applications do not matter that much any more.

No comments:

Post a Comment