comments - 3

phimvt@lurac.latrobe.edu.au — 2000-07-12 06:20:24

Wow - and I'm still in May ... but I will catch up slowly.

1. "Reversible computation"

     this was a fascinating discussion. I had never thought of putting

reversibility and garbage collection into the same sentence. But you

are right - if operands from the stack are discarded into the heap,

then the heap is a (reversible) trace of the computation.

    Not all implementations will discard all operands, though. Most will

do this to say   2  3  + :

    2   push 2 onto the stack

    3   push 3 onto the stack

    +   pop 3, overwrite the top element (2) with the result (5)

This is the common array implementation for stacks. One could use a

similar one for a linked list implementation of the stack:

    2   alloc a new cell, value=2, next=stack, stack=this new cell

    3   ditto with 3

    +   pop 3 (becomes garbage) overwrite top element (2) with (5)

But I did not use this method in the implementation because there

might be a copy of the stack somewhere, which would be (non-functionally)

affected by the "overwrite". Instead I use:

    2   alloc new cell .. value=2 ..

    3   alloc new cell .. value=3 ..

    +   pop two from stack, alloc new cell .. value=5 ..

The old (2) and (3) cells will still be there somewhere. In a

mark-sweep system they will now be the top elements of the free list.

In a stop-copy system (like my prototype), they will be in the

current half of the heap.

   Fascinating notion. thanks.

2. Complete Joy base without DIP

    I still haven't got a really good complete set of primitives.

There are various desiderata:

    a) as few as possible (maybe take combinatory logic as a model)

    b) a psychologically nice and intuitive collection (much more

       than in a))

    c) a collection that is suitable for an implementation

Unfortunately the three seem to be incompatible.

On the topic of "dip", Brent Kirby suggested

    dip   ==   swap unit cat call           (call = i)

Maybe - I have not thought it through properly. In a later

discussion it was asked whether one could use "cons" instead of

"cat". Well, in most functional list processing languages concatenation

is defined recursively in terms of "null" "nil" and "cons" or

something to that effect. Can be done in Joy, too, of course,

and even without recursion by using "linrec" or "y". Nice

exercise. So if "dip" in terms of "cat" is correct, then by

substitution we can put in the (nonrecursive) "cons" version

using "linrec" or "y".

    Incidentally, "call" (or "i") can be defined in terms of

"dip":

    call   ==   dup dip pop

It looks funny. It makes a copy of the [..] program parameter,

dips below the original to execute the copy and then restore the

original, and then pops off the original. I think this law (for "i")

is already mentioned in the algebra paper.

3. "tree diagrams"

    There was a detailed discussion. I was not convinced that the

tree form was an advantage over the linear form.

    Still under the same heading, there was some discussion on typing.

I might have mentioned before, I would welcome a strongly typed

(possibly subset of) Joy.

    Also under the same heading, some discussion on closures, and

the clarification that they belong with lambda-calculus languages

which do have formal parameters ("variables") for substitution

when the function is applied to actual parameters ("arguments").

But it is not correct that closures make sense for all applicative

languages - in combinatory logic there are functions which can

be applied to arguments, but there are no variables and hence no

closures. 

    There is something somewhat close to closures (pun not intended).

Suppose we have a program

    a b .. k l m  [..]  ?  n o  ..  x y  i

where a..m create some items on the stack, then a program [..]

is pushed, and now we want a "closure-like-maker" ? which

will wrap up the stack together with [..] which is then passed

along (but not modified) by n..y . At  this point the final i

is supposed to execute the wrapped up version of [..] with

the earlier stack.

   I think the required effect can be achieved by

       ?   ==   [stack] dip [infra] cons cons

Then what exists in the period n..y is

       [ [oldstack]  [..]  infra ]

All sorts of variants are possible. I still do not know when such

a beast would be useful, but I'd be glad to hear suggestions.

4. "implementations"

    It was splendid to hear of several Joy/Forth variants being

implemented. Keep it up.

    Best wishes

        Manfred