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...