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! ;-)
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
