# Re: [stack] Strictness; Infinite Sequences

## Louis Madon — 2001-08-05 13:55:42

    Implementing a lazy variant of Joy or creating a lazy library for current

    Joy are indeed possibilites. A third possibility (which would actually be my

    own preference) is to make laziness type-driven. The idea is that functions

    like cons, uncons, map, i, etc should be polymorphic so that they would do

    the "right thing" depending on whether they were passed a normal list or

    lazy list. The advantage of this is that you can write generic code that

    will operate over either type.  For example, a function like

    square-all == [dup *] map

    should not have to care that the value on the top of stack is a pre-existing

    list or is being constructed lazily. The essence of the function (squaring

    each element) should remain seperate from such implementation details.

    Current Joy already provides polymorhism in some of its primitives, so it

    may well be feasible to extend that implemenation to handle lazy lists.

    Overall though, implementation is perhaps the easy part.  Learning lots of

    lazy programming techniques would be the larger pursuit.

    Louis.

    From: Jack Waugh

    There is no question in my mind that Joy functions are strict in

    their arguments.  A language with syntax and semantics very close to

    Joy's could be invented where this would not be so (I'm not saying

    whether it should be invented or used).  Maybe such a language

    wouldn't inherit _all_ the advantages of nonstrict langauges with

    lambda abstraction, (e. g., it might still be necessary to somehow

    quote or enclose the true part and the false part for ifte).

    Now I will try the challenge of writing something _like_ "nats"

    and "evens" in Joy.  For now, rather than try to translate nonstrict

    notation to strict notation, I'll attempt to use a nonstrictness-

    inspired _style_ within strict notation.  That is very different from

    what I was asking in the first place.  Just as one can program in

    Lisp (which has assignments) in a "functional style" by avoiding the

    assignments, or you can program in C, not an OO language at all, in

    an "object-oriented style", I will try here programming in joy in

    a "nonstrict style".

    Let's try a stylistic convention that we represent an infinite

    sequence by a pair.  The first element in the pair will be the first

    result in the sequence.  The second element in the pair will be

    quoted code that when evaluated will produce the rest of the infinite

    sequence (expressed in this same convention).

    Since the second element of our pairs are always quoted code and

    therefore a list in Joy, we can just use a cons node to represent the

    pair.

    Then nats is

        dup 1 + [nats] cons cons

    and evens is

        uncons swap dup + swap

        [evens] concat cons

    I think this is right.  Evens begins by separating the first element

    of its argument from the function to produce the rest of the

    argument.  It applies its doubling to the first element.  Addressing

    the rest, it concatenates [evens] on to it so as to make a new

    function that when evaluated, will apply evens to the rest of the

    input.  Finally, we use cons to pack up the package again.

    What about a procedure to get the next element of an infinite list?

    Let us make it work sort of like uncons, by giving us the next

    element and the rest of the list.  But the rest of the list must be

    in our conventional representation.

    infinite-list-uncons ==

        uncons i

    That wasn't hard!

    How about a generalization of evens, infinite-list-map?  What was the

    order of arguments to map?  Oh, of course, Joy combinitors always

    want the function(s) last.  So:

    infinite-list-map ==

        cons dup uncons swap first swap i swap

        uncons swap rest swap concat cons

    Maybe I got that right.

    Perhaps I didn't choose the most productive representation for

    infinite lists.  Here's maybe a better one:  Represent an infinite

    list with a function that, when executed, will leave the first

    element of the list on the stack followed by the rest of the list.

    Thus infinite-list-uncons becomes simply i.  I leave as an exercise

    to the reader to rewrite nats, evens, and infinite-list-map using

    this new convention, and to evaluate which convention works better in

    the end.

    Thinking about graph reduction leads to the question of how to

    represent a graph in Joy.  Represent each node with an integer;

    present the graph as a list of arcs?  Too hard to process.  How about

    an array of the nodes, each node containing a list of its out-arcs as

    integers for the nodes they lead to?  Or maybe a redundant

    representation where for each node you carry the out-arcs as well as

    the in-arcs?

    My examples of nats and evens didn't need any graph reduction.  Can a

    language or style produce the benefits of nonstrictness without

    really needing nonstrictness in its fullnes as requires graph

    reduction?

## Jack Waugh — 2001-08-06 10:07:25

    In the message of mine that Louis Madon quotes in its entirety in

    http://groups.yahoo.com/group/concatenative/message/746 , I'm sure I

    got that last function wrong.  Rather than try to correct it, I

    intend to try expressing nats, evens, etc. in the other convention I

    came up with for representing infinite lists in Joy: represent it

    with a function that effectively unconses the list.  I'm out of time,

    so I intend to try that in a future message (unless someone else does

    it).

    Aside: what if we wanted to represent lazy lists that may be finite?

    Then two fundamental functions are required: test for emptiness, and

    uncons.  A way to handle it would be to represent a lazy list that

    may be finite as an infinite list where every other element is an

    element of the list we are representing, but the other every other

    element is either true if the rest of the list is empty, or false

    otherwise.  I think that with any representation, the possibly-finite

    list will lead to more complexity than is worthwhile for the time

    being.

## Manfred von Thun — 2001-08-06 09:28:52

    On Mon, 6 Aug 2001, Jack Waugh wrote:

      I'm out of time,

    > so I intend to try that in a future message (unless someone else does

    > it).

    If you can bear it, you might want to look at Chapter 5 "Recursion Theory"

    which has a fair bit on self-reproducing programs, and also several

    variants that are "almost" self-reproducing. In particular I have

    in mind a program in which successive generations differ internally

    in a numeric parameter which starts at 0 and gets incremented at

    every generation. Fire up that chapter, search for "infra", and the

    page before and the two pages after that will be relevant. I do not

    know whether this will lead anywhere with your project, but somebody

    should have a look at that sort of thing. (But watch your sanity.)

    I agree with your view that "possibly-infinite" lists (as opposed

    to "definitely infinite" ones) should be shelved for the time being.

    Good luck

      - Manfred

## Manfred von Thun — 2001-08-09 06:21:25

    On Mon, 6 Aug 2001, Manfred von Thun wrote:

     >

    > On Mon, 6 Aug 2001, Jack Waugh wrote:

    >

    >   I'm out of time,

    > > so I intend to try that in a future message (unless someone else does

    > > it).

    > If you can bear it, you might want to look at Chapter 5 "Recursion Theory"

    > which has a fair bit on self-reproducing programs, and also several

    > variants that are "almost" self-reproducing.

     Another step in what might be the right direction is the following.

    Assume that operators and combinators for infinite sequences are written

    with a leading capital letter:

        Cons, Uncons, Swons, Unswons, First, Map  etc.

    As operators we really only need  Cons and Uncons, the others are

    definable in terms of them.

    Assume the infinite list [5 6 7 8 ..] is written [5..]

    In the most general case there will be other elements before

    the infinite list becomes regular:

       [ 42 3 777 5..]

    where each of the additional elements might have been cons'ed into it:

        42  3  777  [5..]  Cons Cons Cons   =>   [42 3 777 5..]

    Here is the easy part:

        Cons  ==  cons

    Now to Uncons. Represent the infinite tail 5..  simply as 5:

        [42 3 77 5]

    If a list has only one element (say [5]),

       then Uncons must produce   5 [6]

    If a list has more than 1 element (say [77 5]),

       then Uncons is just uncons.

    So we can define

            Uncons  ==

    		[small]			(* or:  [size 1 =]

    		[first dup succ [] cons]

    		[uncons]

    		ifte;

    But this is only a first draft of Uncons.

    To do a Map, say

         [2 3 7 5]  [dup *]  Map

    the [dup *] has to be done to the first three elements but not to 5.

    Instead the [dup *] has to be incorporated into the representation

    of the infinite part of the list:

         [4 9 49  [5 [dup *]] ]

    Now Uncons can pull out 4 9 49 in the obvious way, but eventually

    the infinite part [5 [dup *]] is reached. Then we need

         [ [5 [dup *]] ]        =>     25  [ [6 [dup *]] ]

    Maybe this will give you some ideas how a proper Uncons and Map

    should be implemented.

    I foresee difficulties for Filter, though.

      - Manfred

## Jack Waugh — 2001-08-09 08:54:31

    Mr. von Thun says

     > Assume the infinite list [5 6 7 8 ..] is written [5..]

    > In the most general case there will be other elements before

    > the infinite list becomes regular:

    >    [ 42 3 777 5..]

    > where each of the additional elements

    > might have been cons'ed into it:

    >     42  3  777  [5..]  Cons Cons Cons   =>   [42 3 777 5..]

    > Here is the easy part:

    >     Cons  ==  cons

    > Now to Uncons. Represent the infinite tail 5..  simply as 5:

    >     [42 3 77 5]

     I find your proposed treatment of sequences that increase by 1 too

    special.

    Uncons (following your capitalization convention) == i (just because

    I think it beautiful).  I take this as my axiom and proceed from here.

    Cons == [[] cons] dip cons.

    I conjecture that I can write

        nats == [1 [1 +] [something] dup i].

    where [something] dup i will suffice to take any two arguments of

    types ->a and a->a and yield the infinite sequence consisting of the

    first argument, the second argument applied to the first argument,

    the second argument applied twice to the first argument, and so on.

    Given the effect of the "dup i" part, the "something" is going to

    wake up in a situation like this:

        initial-value incrementor [something] something.

    Let's try:

        something ==

            (First, we have to dip to the initial-value and duplicate

             it so as to leave a copy of it behind for the final result.)

            [[dup] dip] dip

            (Now we have to copy the incrementor so when we apply

             it we shan't have to lose our only remaining copy.)

            [dup] dip

            (Apply it now.  The stack is

                initial-value initial-value incrementor incrementor

                [me].)

            [[i] dup] dup

            (Now we have initial-value second-value incrementor [me].

             We want to achieve initial-value [second-value

             incrementor [me] dup i].)

            [dup i] cons cons cons.

    So in summary,

        nats == [

            1 [1 +] [

                [[dup] dip] dip

                [dup] dip

                [[i] dup] dup

                [dup i] cons cons cons

            ] dup i

        ].

    Now to evens.

        evens == [dup +] Map.

    where

        Map ==

            (We face a stack that looks like: sequence function.)

            (Oh, we have to recurse, so do the recursion trick.)

            [map'] dup i.

        map' == (sequence function [me])

            [   (I have to apply the function to the first

                 element of the sequence, then I have to

                 use the function again in packaging the

                 rest of the result sequence.)

                (sequence function)

                [Uncons cons] dip cons dup

                [uncons i] dip uncons

                (We have result-first-value second-sequence function)

            ] dip

            (result-first-value second-sequence function [me])

            [dup i] cons cons cons Cons.

## Manfred von Thun — 2001-08-13 09:22:28

    On Sun, 5 Aug 2001, Louis Madon wrote:

     > Implementing a lazy variant of Joy or creating a lazy library for current

    > Joy are indeed possibilites. A third possibility (which would actually be my

    > own preference) is to make laziness type-driven. The idea is that functions

    > like cons, uncons, map, i, etc should be polymorphic so that they would do

    > the "right thing" depending on whether they were passed a normal list or

    > lazy list. The advantage of this is that you can write generic code that

    > will operate over either type.  For example, a function like

    >

    > square-all == [dup *] map

    >

    > should not have to care that the value on the top of stack is a pre-existing

    > list or is being constructed lazily. The essence of the function (squaring

    > each element) should remain seperate from such implementation details.

     Fully agree with everything you said. One possibility is to write

    these polymorphic versions of operators with capitals, and then a

    definition would look like e.g.

        Map  ==

    	    [some-condition]

    	    [some-function]

    	    [map]		(* for the easy cases *)

    	    ifte

    Hard part is to decide on suitable conditions and functions.

    For "infinite" lists my thoughts are now along these lines:

       1. elements need not be numbers, but could be anything

          (e.g. more and more complex lists)

       2. differences between successive elements need not be constant

       3. elements need not be ascending everywhere, could zig-zag

       4. there could be infinitely repeating loops

       5. the number of elements could be finite after all

    Just as sets can be defined by an unordered list of their members or by a

    prediate which they all satisfy, so these ordered list could be

    defined by a program which generates them one after another -

    when called upon, "lazily" so to speak. I'll think of them

    as intensionally defined lists, whether they are finite or not.

    I suspect that this sort of thing does already exist in the

    literature, and I would be grateful for pointers (Clu's generators ???).

    Such an intensionally defined list (IDL) will need:

       a) something resembling an internal state to remember how far

          elements have been extracted by Uncons, Unswons, First, Rest

       b) a constant program to move to the next state when an

          extraction occurs.

    Typically a) could be simply a number, the next number to be

    extracted. Typically b) will be something like "succ" or "dup *".

    But in the most general case a) will be more than just one item

    since any item could occur repeatedly even when there are no

    infinite cycles. It may be that the idea is too general to be

    of much use.

    I will not pursue the idea myself at the moment, I am just too

    busy with other things about Joy. But I hope that somebody can

    find some time to spend on it.

      - Manfred

## Jack Waugh — 2001-08-13 15:06:39

    (Replying to http://groups.yahoo.com/group/concatenative/message/773 )

    OK.  Then I think any implementation of the following abstractions

    would satisfy the requirements you propose.

    As a bit of side propaganda, I'm going to name all functions in a

    convention where the name describes the required arguments in their

    order and describes the results the function will produce in their

    order.  Anything I run together with no spaces you must take as a

    single function name, except a period at the end, which I use at the

    end of a definition.  I think this will keep me from getting confused

    about the order of arguments.  I will also give the function names we

    have been using, such as Uncons.

    lazy-list:is-empty? == Null

    nonempty-lazy-list:first;rest == Uncons

    initial-state:state-to-is-empty?:state-to-first:state-to-next-

    state:lazy-list

    To sum up the requirements: first requirement is a function from a

    lazy list to a Boolean stating whether the lazy list is empty.

    Second requirement is a function from a lazy list that has already

    been established to be in fact not empty, to two results: the first

    element of the list, and a lazy list of the remaining elements.  The

    third requirement is a means of constructing a lazy list

    intensionally.  We express the intension under the notion that the

    lazy list contains some "state" from which the mechanism can compute

    whether the list is empty, the first element if any, and a successor

    state unless the list is empty.  The rest of the list, then, we

    understand to work as though constructed from the successor state and

    the same functions for emptiness, state to successor state, and state

    to first element.

    Given these abstractions, then, we could write, for example, nats, as:

        1 [pop false] [] [1 +] initial-state:state-to-is-empty?:state-to-

    first:state-to-next-state:lazy-list.

    lazy-list:function:Map->lazy-list ==

        [   [lazy-list:is-empty?]

            [lazy-list:first]

        ] dip concat

        [lazy-list:rest]

        initial-state:state-to-is-empty?:state-to-first:state-to-next-

    state:lazy-list.

    Now for the implementations; I don't think they're going to be hard.

    initial-state:state-to-is-empty?:state-to-first:state-to-next-

    state:lazy-list ==

        [initial-state:state-to-is-empty?:state-to-first:state-to-next-

    state:lazy-list]

        cons cons cons cons.

    lazy-list:is-empty? == uncons uncons pop i.

    lazy-list:first == uncons uncons uncons pop [pop] dip i.

    lazy-list:rest ==

        uncons uncons uncons uncons pop

        dup

        [  swap

            [   swap

                [i] dip

            ] dip

        ] dip

        initial-state:state-to-is-empty?:state-to-first:state-to-next-

    state:lazy-list.

    lazy-list:first;rest == dup [lazy-list:first] dip lazy-list:rest.

    I think that's it; I think this completely answers von Thun's

    suggestion or request relative to lazy lists.

    The design could be made more robust through the use of private

    functions.