# Lazy evaluation

## r_v_dalen — 2006-09-09 11:30:28

    I'm wondering how many concatenative languages are lazily evaluated.

    I'm aware that Joy can be lazily evaluated, although I believe that the C implementation is

    strict?

    Side effects rule out lazy evaluation. That's why I believe Factor is probably strict too

    (although some parts of Factor could be lazy). I'm not sure about K, J and APL.

    But I do know that a lot of data structures aren't strict in APL. It looks like mixing strict and

    lazy evaluation is the most practical approach.

    My question: how does one decide when to evaluate and when not to evaluate? What kind of

    heuristics can be applied? (memory vs time?)

    Hopefully, the members of concatenative can provide me some of the answers.

    Thanks,

    Robbert.

## Chris Double — 2006-09-09 11:57:17

    On 9/9/06, r_v_dalen <r_v_dalen@...> wrote:

     >

    > Side effects rule out lazy evaluation. That's why I believe Factor is

    > probably strict too (although some parts of Factor could be lazy).

     There is a lazy-lists library in Factor and the parser combinators

    code  relies on it a lot. A parser combinator returns a 'lazy list of

    successes' as the result of a parse.

    I believe there is also lazy evaluation code available for Joy and the

    following paper as well:

    http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-reprod.html

    Chris.

    --

    http://www.bluishcoder.co.nz

## stevan apter — 2006-09-09 13:24:26

    APL, J, and K are strict.  i'm not sure what you mean by

    saying that some data structures in APL are lazy.

    SLACK is a lazy implementation of K, based on SASL.  in

    SLACK, an expression involving an infinite list like

        head tail one where one is 1:two where two is 2:one

    compiles to a functional expression

          +------@-------+

          |              |

       +--@---+    +-----@------+

       |      |    |            |

     +-@-+   tail  Y      +-----@------+

     |   |                |            |

     B  head           +--@---+      +-@-+

                       |      |      |   |

                       B    +-@-+  cons n:2

                            |   |

                          cons n:1in which the Y combinator is used to compute mutual recursion

    between the lists 'one' and 'two'.

    computations "go strict" when an operator like + is reduced.

    + causes its operands to be evaluated in full.  so e.g.

        one + two where one is 1:two where two is 2:one

    will blow memory.

     ----- Original Message -----

    From: "r_v_dalen" <r_v_dalen@...>

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, September 09, 2006 7:30 AM

    Subject: [stack] Lazy evaluation

    > I'm wondering how many concatenative languages are lazily evaluated.

    >

    > I'm aware that Joy can be lazily evaluated, although I believe that the C implementation is

    > strict?

    >

    > Side effects rule out lazy evaluation. That's why I believe Factor is probably strict too

    > (although some parts of Factor could be lazy). I'm not sure about K, J and APL.

    >

    > But I do know that a lot of data structures aren't strict in APL. It looks like mixing strict and

    > lazy evaluation is the most practical approach.

    >

    > My question: how does one decide when to evaluate and when not to evaluate? What kind of

    > heuristics can be applied? (memory vs time?)

    >

    > Hopefully, the members of concatenative can provide me some of the answers.

    >

    > Thanks,

    >

    > Robbert.

    >

    >

    >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

    >

## Robbert van Dalen — 2006-09-09 15:15:42

    > APL, J, and K are strict.  i'm not sure what you

    > mean by

    > saying that some data structures in APL are lazy.

     Just copied this from wikipedia:

    "A widely cited paper "The APL Machine" perpetuated

    the myth that APL made pervasive use of lazy

    evaluation where calculations would not actually be

    performed until the results were needed and then only

    those calculations strictly required. Although this

    technique was used by just a few implementations, it

    embodies the language's best survival mechanism: not

    specifying the order of scalar operations. Even as

    eventually standardized by X3J10, APL is so highly

    data-parallel, it gives language implementers immense

    freedom to schedule operations as efficiently as

    possible."

     > SLACK is a lazy implementation of K, based on SASL.

     I really like SLACK as a name and as a language. Don't

    know enough K to really understand the implementation

    though. I still have to learn a great deal of K and J

    terminology (nouns, verbs, abverbs) and concepts

    (shape, rank, valence) to really appreciate all the

    interesting stuff that's sitting on your www.nsl.nl

     > compiles to a functional expression

    >

    >       +------@-------+

    >       |              |

    >    +--@---+    +-----@------+

    >    |      |    |            |

    >  +-@-+   tail  Y      +-----@------+

    >  |   |                |            |

    >  B  head           +--@---+      +-@-+

    >                    |      |      |   |

    >                    B    +-@-+  cons n:2

    >                         |   |

    >                       cons n:1in which the Y

     That really looked like line noise in propertional

    font ;)

    To bad you cannot force mono-spaced fonts in the yahoo

    mail reader.

     > computations "go strict" when an operator like + is

    > reduced.

    > + causes its operands to be evaluated in full.  so

    > e.g.

    >

    >     one + two where one is 1:two where two is 2:one

    >

    > will blow memory.

     Similarly, folding an infinite list would also blow

    memory.

    I suspect you can always make lazy evaluation strict

    and build lazy structures (Factor's lazy list) with

    stict evaluation.

    But that's probably not saying much.

    Robbert.

     > ----- Original Message -----

    > From: "r_v_dalen" <r_v_dalen@...>

    > To: <concatenative@yahoogroups.com>

    > Sent: Saturday, September 09, 2006 7:30 AM

    > Subject: [stack] Lazy evaluation

    >

    >

    > > I'm wondering how many concatenative languages are

    > lazily evaluated.

    > >

    > > I'm aware that Joy can be lazily evaluated,

    > although I believe that the C implementation is

    > > strict?

    > >

    > > Side effects rule out lazy evaluation. That's why

    > I believe Factor is probably strict too

    > > (although some parts of Factor could be lazy). I'm

    > not sure about K, J and APL.

    > >

    > > But I do know that a lot of data structures aren't

    > strict in APL. It looks like mixing strict and

    > > lazy evaluation is the most practical approach.

    > >

    > > My question: how does one decide when to evaluate

    > and when not to evaluate? What kind of

    > > heuristics can be applied? (memory vs time?)

    > >

    > > Hopefully, the members of concatenative can

    > provide me some of the answers.

    > >

    > > Thanks,

    > >

    > > Robbert.

    > >

    > >

    > >

    > >

    > >

    > >

    > >

    > > Yahoo! Groups Links

    > >

    > >

    > >

    > >

    > >

    > >

    > >

    > >

    >

     __________________________________________________

    Do You Yahoo!?

    Tired of spam?  Yahoo! Mail has the best spam protection around

    http://mail.yahoo.com

## William Tanksley, Jr — 2006-09-09 22:13:31

    r_v_dalen <r_v_dalen@...> wrote:

     > I'm wondering how many concatenative languages are lazily evaluated.

     Lazy data structures (that is, data structures that contain code that

    generate later values) are easy in any language. Actual lazy

    evaluation is /impossible/ in a concatenative language -- lazy

    evaluation means that parameters to functions aren't evaluated until

    and unless they're actually used. This is impossible because

    concatenative semantics doesn't have function parameters.

     > Robbert.

     -Billy

## Christopher Diggins — 2006-09-09 22:36:37

    However every term in a concatenative language can be viewed as a

    function which takes a single function (a stack) and outputs a single

    value (another stack).

    For an example of lazy evaluation, consider the following

    concatenative program:

    define f { [] [1 concat] [true] while pop }

    In english: while true concatenate 1 to the list on the top of the

    stack. When done pop the value.

    If the language semantics do not enforce this as an infinite loop,

    then it would make sense to say that the language supports lazy

    evaluation.

    - Christopher Diggins

     On 9/9/06, William Tanksley, Jr <wtanksleyjr@...> wrote:

    >

    > r_v_dalen <r_v_dalen@...> wrote:

    > > I'm wondering how many concatenative languages are lazily evaluated.

    >

    >

    > Lazy data structures (that is, data structures that contain code that

    > generate later values) are easy in any language. Actual lazy

    > evaluation is /impossible/ in a concatenative language -- lazy

    > evaluation means that parameters to functions aren't evaluated until

    > and unless they're actually used. This is impossible because

    > concatenative semantics doesn't have function parameters.

## William Tanksley, Jr — 2006-09-09 23:14:31

    Christopher Diggins <cdiggins@...> wrote:

     > For an example of lazy evaluation, consider the following

    > concatenative program:

    > define f { [] [1 concat] [true] while pop }

    > In english: while true concatenate 1 to the list on the top of the

    > stack. When done pop the value.

    > If the language semantics do not enforce this as an infinite loop,

    > then it would make sense to say that the language supports lazy

    > evaluation.

     I can see that being acceptable, yes.

    This is one of the things I've been trying to figure out to see if I

    can think of a way to control the cartesian product in Enchilada -- if

    you could specify that only some of the multiplications are relevant

    to the rest of your program, and have only those ones actually get

    carried out.

     > - Christopher Diggins

     -Billy

## r_v_dalen — 2006-09-11 14:26:59

    > > If the language semantics do not enforce this as an infinite loop,

    > > then it would make sense to say that the language supports lazy

    > > evaluation.

    >

    > I can see that being acceptable, yes.

     Billy, I also agree with you and Christopher. I always think of lazy

    evalutation to be some kind of stream. Every time you get an element

    from a stream, that element is forced step to be evaluated.

     > This is one of the things I've been trying to figure out to see if I

    > can think of a way to control the cartesian product in Enchilada -- if

    > you could specify that only some of the multiplications are relevant

    > to the rest of your program, and have only those ones actually get

    > carried out.

     The cartesian product is not so problematic. Actually the zip and

    desolve operator are to most interesting ones. For instance, the

    cartesian product could also be written as:

    [a, b, c] [x, y] * =:= [a, b, c, a, b, c] [x, x, x, y, y, y] % =>

    [a x, b x, c x, a y, b y, c y]

    And the result can be as lazy as myself. Just imagine the following

    tree structure.

    (% (<1,3>[a, b, c]) (<3,1>[x, y]) )

    We can query the tree structure to return the expression sitting at

    index 4:

    4(%(<1,3>[a, b, c])(<3,1>[x, y])) =>

    {%(4<1,3>[a, b, c])(4<3,1>[x, y])} =>

    {%{[a]}{[y]}} =>

    {a y}

    Hopefully, the latter does make some sense. I've tried to visualize a

    reduction tree (like the ones found in functional languages).

    Robbert.