Re: Compiler's bane

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