[Haskell-cafe] Re: A suggestion for the next high profile Haskell project [Was: Re: What is a hacker?]

Joachim Durchholz jo at durchholz.org
Tue Dec 19 16:54:09 EST 2006


Seth Gordon schrieb:
> Joachim Durchholz wrote:
>>> Trying to fully evaluate an infinite data structure will result in
>>> looping or memory exhaustion, and you have that possibilities in almost
>>> all languages.
>> Yes, but I suspect that Haskell makes it easier to make that kind of bug.
>> Worse, it's easy to introduce this kind of bug: just pass a list
>> returned from function a to function b, not being aware that a may
>> return an infinite list and that b may do something with it that
>> requires that it's evaluated. In other words, this kind of bug can come
>> into existence during code integration... and the type system doesn't
>> warn you when you do it.
> 
> If you're worrying about some unexpected input causing a function never
> to terminate, don't you also have to worry about some unexpected input
> causing a function to become so glacially slow that from the user's
> perspective, it *might as well* never terminate?

I'm not really talking about bad algorithms. I'd talking about 
integrating two innocent functions and getting a result that doesn't 
terminate.
That's a problem that doesn't exist in strict languages: feeding the 
output of one function into another function won't turn terminating 
functions into nonterminating ones.

However, you're right that composing functions might drastically change 
their performance - simply because the inner function may return data 
structures that are expensive to evaluate, and the outer function 
insists on evaluating them.
So, for a lazy language, nontermination is just one side of the coin, 
the other is unexpected performance effects.

OT3H this kind of problem may occur whenever you're passing around 
executable stuff, whether it's in the form of unevaluated lazy thunks, 
strict-language streams, or (to add the perspective from a non-FPL camp) 
passing around polymorphic objects that carry functions of unknown space 
and time complexity.
It's probably a question of how idiomatic code behaves.

OT4H I know how to annotate code with space and time complexities in a 
strict language.
I.e. a Sort typeclass should impose an O(N log N) complexity on the sort 
function, slower sorts don't really do what the programmer expects - and 
that's then a guarantee that callers of the sort function can build upon.
And while I have an in-principle approach for strict languages, I don't 
have one for lazy languages. Is there any literature on the subject?

Regards,
Jo



More information about the Haskell-Cafe mailing list