[Haskell-cafe] Compiler's bane

[Andrew Coppin]

Hi guys.

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!!! >_<

No other part of the program has consumed nearly as much brain power as 
me trying to figure out when it is and isn't safe to replace a variable 
with its RHS.

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

...and x is now a free variable. OOPS!

Trying to tease out exactly under which conditions you can and cannot 
perform the substitution is utterly maddening. Since this is a Haskell 
mailing list and as such it is populated by vast numbers of people with 
PhDs and so forth... does anybody happen to know the *correct* solution 
to this conundrum? Before I become clinically insane...? o_O



By the way... To all those people who work on projects like GHC and so 
on, who have to get this stuff right "for real": you have my infinite 
respect!