Jonathan Cast wrote:
On Fri, 2008-08-29 at 20:56 +0100, Andrew Coppin wrote:
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?
If you want to avoid infinite normal forms (or just plain lack of normal
forms, as in let x = x in x or (\x -> x x) (\ x -> x x)), you need to
follow three rules:
1) Static typing
2) No value recursion
3) If you allow data types, no recursive data types
Otherwise, your language will be Turing-complete, so yes, trying to
determine ahead of time if even a HNF exists will be the halting
problem.
If you really want to write a general-purpose evaluator, then infinite
normal forms may not be an issue, as long as they are generated lazily,
so your evaluator can at least print something out while it goes into an
infinite loop. Otherwise, you can declare f x, where f is an unknown
function, a HNF, and stop at that point, or go on only under the
client's control.
The optimizers used by GHC and YHC pick one function out of each
recursive binding group, and just refuse to inline it at all. If you
don't mind producing expressions that aren't really in any definable
HNF, that would be an alternative as well.
Right. So if I have, say, the factorial function defined using the Y
combinator, there's no way to stop the interpretter expanding an
infinite number of copies of Y, even though in theory the factorial
function should terminate?
Oh well, I guess I'll just have to live with that one. Maybe I can make
the binding to expand user-selectable or something...
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
