A "Lazy" list, as described for Perl 6, is a way of not doing the work to find that list element's value unless (until) it is needed. Often times a list can be compactly represented as an iterator. Perl 5 has some special cases for efficiency, but in Perl 6 the concept of "Lazy lists" is general.

My brainstorm is that a "Lazy list" is just a "work list" of pending tasks that may need to get done. Meanwhile, hyperoperators apply an operator to a list, but assume that it is side-effect free so it can do them in parallel implicitly. But, the iterator and the hyperoperator are just two extremes of a continuum of guarantees and flexibility of how a "work list" can be processed.

It's been touted that hyperoperators are an example of making threading available as a deeper part of the language, not requiring explicit low-level thread operations to acheive. I think that the Lazy list is likewise, but in fact serves as a better exemplar of how to use it for background activities because you can put general and arbitrary work in your work list.

My essay is posted here. I invite feedback to improve the article, as well as general discussion of the idea.

—John

  • Comment on Lazy Lists as a model for implicit parallelism

Replies are listed 'Best First'.
Re: Lazy Lists as a model for implicit parallelism
by moritz (Cardinal) on Sep 16, 2008 at 08:44 UTC
    Here is what the first example would do without the new :injective flag, and why:

    In general a map can aggregate multiple values per call to the transforming block, so accessing @result[7] would fill @result eagerly up to index 7, so the expected output looks something like this: 

    [0][1][2][3][4]13
[5][6][7]57
3

    [download]

    I seem to recall that TimToady actually said that map (and likewise for) do guarantee an order of execution, so even if the compiler can prove that the block passed to map will only ever return exactly one item, it will still process them in the way I described.

    The :injective flag is a nice idea on your behalf, but since the array has to know how to evaluate itself (not just the map) that's a bigger change than just adding a flag to a builtin, it requires a different underlying List implementation.

    Together with the other flags you propose I think that there are too many confusing options on how to process lists. If we do integrate them into the language, we'll see dozens of threads on perlmonks discussing the merits and drawbacks of the various flags when they are really just premature optimizations.

    The current state of the specification also suggests that laziness is not strict, ie the map is actually allowed to process more than it has to, as long as it doesn't suck up infinite resources when trying to process an infinite list.

    So my proposal is to use (lexically scoped) pragmas instead: 

    use List qw/strict-lazy/;
# now all list processing is haskell-like strictly lazy
# this is mostly good for testing laziness ;)

use List qw/parallel/;
# allow parallel processing of lazy lists, even when 
# when it's not that lazy. This is the default.

    [download]

    I think that all further attempts to control what happens under the hood are

    • optimizations that the compiler should care about, not the programmer
    • actually contra-productive, because it means we have to define the current semantics of laziness more precisely, thus taking the compilers the freedom to optimize
    • not very perlish, in that we usually try not to expose what happens under the hood. It should just work, you know
[reply]
[d/l]
[select]
Re: Lazy Lists as a model for implicit parallelism
by Anonymous Monk on Sep 16, 2008 at 02:47 UTC
    You need a SEE ALSO/Bibliography type-dealie :)
[reply]
      What should be also-seen?
[reply]

Back to Meditations