[Haskell-cafe] Compiler's bane

[Andrew Coppin]

Neil Mitchell wrote:
> Hi
>
>   
>> I'm writing a simple interpretter for a small extended-lambda-calculus sort
>> of language. And I'd just like to say... RECURSIVE LET-BINDS! GAAAAH!!! >_<
>>     
>
> Agreed :-)
>   

I'm glad it's not just me! ;-)

(Oleg cat sez: "see, yr type problum not so hard".)

>> To illustrate:
>>
>>  let x = f x; y = 5 in x y
>>
>> A simple-minded interpretter might try to replace every occurrance of "x"
>> with "f x". This yields
>>
>>  let y = 5 in (f x) y
>>     
>
> That's wrong, its a two step transformation. You just substitute all
> occurances of x for f x:
>
> let x = f (f x); y = 5 in (f x) y
>
> For the case let x = 5 in x, you do the same thing:
>
> let x = 5 in 5
>
> Now as a second step you hoover up unused let bindings and disguard:
>
> 5
>
> You seem to be combining the substitution and the removing of dead let
> bindings, if you separate them you should have more luck.
>   

Right. So substitute in the RHS and then perform a let-cull afterwards. 
Got it.

I've been playing with this today, and no matter what rules I come up 
with, it seems to be ridiculously easy to put the interpretter into an 
infinite loop from which it will never escape. Is there any way to know 
which binds are "worth" expanding and which ones aren't? (I have a 
sinking feeling this might be equivilent to the Halting Problem...)

For example, if you have "let x = f y; y = g x in x" then since all the 
functions are free variables, there's really nothing much "useful" you 
can do to simplify this any further. However, my interpretter merrily 
goes into an endless loop building a huge expression like "f (g (f (g (f 
(g..." Is it possible to avoid this?

(The problem isn't unique to recursive let-binds of course. I discovered 
today that (\x -> x x) (\x -> x x) reduces to itself, so that puts the 
interpretter into a loop too. However, NON-recursive let-binds always 
terminate eventually. It's only the recursive ones that cause problems.)

My word, this stuff is really surprisingly hard! At least this time I 
built a general-purpose renamer rather than trying to avoid name capture 
by construction! ;-)