Lazy lists vs generators
Yves Pare`s wrote:
I cannot help smiling when I hear Java/C#/Python developers telling about the "wondeful features" of their languages ;) (- We have generators! We can _yield_ values! [1] - Yeah, so nice... We have simple lists... with lazy evaluation)
Just for the record, lazy lists per se are sufficient only for simplest generators. Re-writing an accumulating traversal to accommodate suspension by hand is too ungainly and error prone. Still, if we just add exceptions (the Either monad), we can idiomatically write all the generator examples of Python or Icon, for example. If we do not need effects other than yielding or non-determinism, [Either e a], which is ErrorT e [] a, suffices. If we need IO or mutable state, we should replace [] with LogicT (which is the monad of lazy lists with effect). The following web page talks about lazy lists and generators http://okmij.org/ftp/continuations/generators.html in (perhaps too) great detail.
Le 11/06/2011 11:06, oleg@okmij.org a écrit :
The following web page talks about lazy lists and generators http://okmij.org/ftp/continuations/generators.html in (perhaps too) great detail.
Oleg, when you mention Icon, you might - perhaps - observe that Griswold didn't introduce the co-expressions (this is their terminology, not "generators") out of the air, they have been present as the "unevaluated expressions" in Snobol4. Icon has been built upon the Snobol4 philosophy, although as language it was very different. Another remark about "yield" in Python. This is not just a non-deterministic return mechanism, but an expression, which yields a value also for the generator code. It becomes thus a reentrant co-procedure, which goes quite a mileage beyond the lazy list model. Jerzy Karczmarczuk
On 11/06/2011, at 9:06 PM,
The following web page talks about lazy lists and generators http://okmij.org/ftp/continuations/generators.html in (perhaps too) great detail.
The Origins section mentions Alphard, saying "Modern generators first appeared in the language Alphard developed in the the group of Mary Shaw at CMU in mid-1970s." But Interlisp-10 had generators back in 1973, if I'm reading the manual at Trailing Edge correctly. The implementation of generators in Interlisp used the "Spaghetti Stack", closely modelled on "A Model and Stack Implementation of Multiple Environments" by Bobrow & Wegbreit.
But Interlisp-10 had generators back in 1973, if I'm reading the manual at Trailing Edge correctly.
As the following document explains, generators were common to all new-generation AI languages that appeared in early 1970 (such as SAIL, CONNIVER, POPLER, INTERLISP amd QLISP): http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-73-2_New_Programming... It seems IPL-V from mid-1960s has been the inspiration. There is quite a bit of difference between the above paper, for example, and Shaw et al paper. In AI languages, generators are introduced by pure hacking. The run-time environment lets the program access and arbitrarily modify the components of the frame structure. One can mess with the return pointers as well with bound variables (or anything else for that matter). On the other hand, Shaw et al had distilled iteration to an abstract interface. Moreover, they have introduced reasoning principles, in the form of Hoare logic assertions and proof rules. To me, that is the modern thinking to aspire to. Jerzy Karczmarczuk wrote:
Griswold didn't introduce the co-expressions (this is their terminology, not "generators") out of the air, they have been present as the "unevaluated expressions" in Snobol4. Icon has been built upon the Snobol4 philosophy, although as language it was very different.
I do mention that Icon took a lot from SL5 (and SL5 took a lot from Snobol4). One can find more information elsewhere: http://lambda-the-ultimate.org/node/1780#comment-21647 I read somewhere Griswold's saying that Icon was meant as a clean cut from SL5 (although he was going to SL5 from time to time to steal features from). The SL5 paper `Ralph E. Griswold and David R. Hanson, An Overview of SL5' convinced me that SL5 was the real place for innovation in control. It seems Alphard, Icon and CLU stand out as the languages that are explicitly designed around generators as the fundamental form of control.
participants (3)
-
Jerzy Karczmarczuk -
oleg＠okmij.org -
Richard O'Keefe