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