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.