Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ames!pacbell.com!pacbell!osc!jgk From: jgk@osc.COM (Joe Keane) Newsgroups: comp.lang.functional Subject: Re: Applications for lazy functional languages Summary: Laziness is an implementation issue. Keywords: strict Message-ID: <4682@osc.COM> Date: 23 Mar 91 01:02:17 GMT References: Reply-To: jgk@osc.COM (Joe Keane) Distribution: comp Organization: Versant Object Technology, Menlo Park, CA Lines: 66 In article acha@CS.CMU.EDU (Anurag Acharya) writes: >I am curious about the kind of applications that lazy functional languages >are suitable for. What can you do with such languages (in a natural and >elegant fashion) that you cannot similarly do with a strict language augmented >by a lazy type constructor ? Nothing. Besides the obvious argument of Turing equivalence, given any language i can think of you can show how to implement lazy closures. In C you can use structs and function pointers. In Scheme you can implement `delay' and `force' as lambda expressions. >For the sake of concreteness, what >can be done in these languages that cannot be done naturally and elegantly in >SML augmented by a "lazytype" construct that allows declarations like the >following: > >lazytype 'a stream = LAZY_CONS of 'a * 'a stream | NULL > >with appropriate lazy semantics. Again, you can do anything you could do in a lazy language. If you know when you want something to be lazy, you can use one of these lazy streams and it works fine. But since you said ``naturally and elegantly'', that gives me some more space... First of all, laziness is not an `extra'. It exists in every language, it just may not be apparent from the terminology. Laziness is necessary to protect yourself from code being executed when you don't want it to be. It's just that in most languages lazy functions are kept separate from normal functions. For example, the C operator `&&' is defined to be lazy in its second argument. If it suddenly became strict, then most of the C programs in the world would stop working. In fact, the if-then-else construct can be considered a lazy function. Clearly this can't be made strict either. In Lisp, there's a lot of laziness rules. Normal functions always evaluate their arguments, macros never evaluate their arguments, and special forms do whatever they feel like. Unlike C, this is made somewhat more transparent by the fact that the same syntax is used for each. Now, to the point: strictness is only a matter of implementation. In terms of correctness, making a strict function lazy never hurts. On the other hand, making a function strict can easily break something. This says that, conceptually at least, we only need lazy functions. Lambda calculus and combinators both work this way; they have no strict functions. So it makes a lot of sense to have a language where every function is lazy. This eliminates an artificial distinction, and allows you to get the benefits of laziness everywhere, not just where someone thought it might be useful. So why don't people do this? The answer is always the same: ``It's too slow.'' Some people claim this is an inherent problem with lazy languages. I strongly disagree with this position. Naive implementations do a lot of unnecessary testing and jumping around, and i'm afraid that this has given lazy languages a bad reputation for inefficiency. With the proper techniques, a lazy language can be faster than a traditional one. I don't feel like explaining this in depth, since you could easily write a book on it. Also, it's better to just do something, instead of describing how you think it could be done. So for now, i'll just leave this as an unsubstantiated claim. -- Joe Keane, supercombinator hacker