Re: [stack] S-K Construction of Dip?

Cancel the cancellation. The previous cancellation was for a very tentative
pre-Prolog draft of something about typing Joy. My mailer claims it was
sent to concatenative, and I did receive it back, but I did not see it when
I
looked at the group from Google. I really don¹t know what I have done
wrong.

Anyhow, here is the other posting that I did intend to send, which did
get through, but which might have been mistaken as the cancelled one.
I have made a few changes, mainly because I have seen how some of
the concepts can be generalised to something possibly useful, but also
because
I noticed some really bad typos.

On 22/3/07 4:23 PM, "Manfred Von Thun" <[email protected]> wrote:
> 
Here is a flat concatenative language which I shall call L. After a lot of
discussions on this group I now have some intuitive understanding of what a
flat language is. I shall discuss this language L in relation to Joy.

The problem seems to be how to handle apparent non-flatness due to
quotations/lists, which can be nested. I need to introduce the notion of a
waiting room, or ante-room, or briefly, a foyer. This is where incoming
items form a queue (perhaps similar to Stevan¹s Y queue in his XY language).
At certain times a queue in a foyer gets sent elsewhere and the foyer is
destroyed. A foyer is created by the special item ³[³, and destroyed by the
special item ³]².  I also need a notation for describing foyers: a newly
created empty foyer is written <>, an after a ³dup² item arrives the foyer
is written <dup>, after a ³*² item arrives it is written <dup *>. But a
foyer is not a list, in fact a foyer can contain lists. Foyers cannot be
nested, but there is a stack of foyers: I shall write this stack with the
topmost item on the right.  When a foyer is destroyed by ³]², the contained
queue is sent to the foyer below as a list. Finally, a ³.² will use the
contents
of the top foyer as a program to execute by using foyer below as a stack.
> 
Here is a contrived example to illustrate several nestings. Let the program
be

9999 [ [2 3] [dup *] map ] dip .             # should produce:  [4 9]  9999

The program starts with a stack containing two empty foyers. I shall now
trace the execution of the program by writing each step on a separate line,
followed by a picture of the stack of foyers, followed by a comment.

         <> <>       # start with stack of just two empty foyers
9999  <> <9999>  # put 999 at end of top foyer top foyer
[        <> <9999> <>  # start a new foyer
[        <> <9999> <>  <> # start a new foyer
2        <> <9999> <> <2> # put 2 at end of top foyer
3        <> <9999> <> <2 3>  # put 3 at end of top foyer

]        <>  <9999> <[2 3]>  # pop top foyer, put content into foyer below
[         <> <9999> <[2 3]> <>  # start a new foyer
dup     <> <9999> <[2 3]> <dup> # put dup at end of top foyer
*         <> <9999> <[2 3]> <dup *> # put * at end of top foyer
]         <> <9999> <[2 3] [dup *]> # pop top foyer, put content into foyer
below
map     <> <9999> <[2 3] [dup *] map>  # put map at end of top foyer
]          <> <9999 [[2 3] [dup *] map]> pop top foyer, put content below
dip       <> <9999 [[2 3] [dup *] map] dip> put dip at end of top foyer
.           pop the top foyer, execute its contents as a Joy program, using
the
            foyer below as a normal Joy stack for execution.
finally:  <[4 9] 9999>  the stack contains  two items, a list and a number

To recapitulate: everything gets appended to the top foyer, except for
the three special commands ³[³  ³]² and ³.² ,  as follows:

³[³ starts a new foyer
³]² pops the top foyer and appends its contents as a list to the foyer
below.
³.² pops top foyer and executes contents on foyer below.

This is the flat concatenative language L. The foyers are just about
invisible
to the user of the language: they are created, filled, emptied and executed
entirely behind the scenes.

Is L flat enough? It is a language from stacks to stacks, using
concatenative notation. The behaviour of a whole program up to its
termination as a Joy program is to compute a function, and all parts compute
functions, and function computed by the whole is the composition of the
functions computed by the parts. And of course if any parts get snipped out,
the remainder will compute a function which may well be the empty  (nowhere
defined) composition of the functions computed by the remaining parts.

Would anyone be tempted to implement a language such as L? Don¹t
rush off to do it, because it is nothing new. I¹ll let the cat out of the
bag now:
Look again at the paragraph at the beginning of the original posting,
the paragraph that started as ³Here is a flat ...². There are three
sentences
in that paragraph. From each sentence take the last word. The three words
form a sentence. It is true. All that stuff about foyers actually occurs
inside
the function ³readterm()² inside my joy.c, which reads a term (a sequence
of factors) and translates it into internal code.

One consequence from all this is that Joy is or is not a flat language,
depending on what one considers the language to be. Presumably the same
could be said of just about any language which has nesting of one kind
or another. To express it as a slogan: flatness is in the eye of the
beholder.

But one could invent an extension L++ which allows other things to be done
to foyers. Go back again five paragraphs, to the explanation of what ³[³,
³]²
and ³.² do. Nothing there says that ³[³ and ³]² have to be properly nested.
Consider the curious looking program

> [5 *] [ [dup] infra . i .

Let us execute it in the same way as before, using ³[³ , ³]² and ³.² as
explained.

            <> <> # two empty foyers
[           <> <> <> # start new foyer
5           <> <> <5> # append 5
*           <> <> <5 *> # append *
]            <> <[5 *]> # append as list
[            <> <[5 *]> <> # start new foyer
[            <> <[5 *]> <> <> # start another foyer
dup        <> <[5 *]> <> <dup> # append dup
]             <> <[5 *]> <[dup]> append as list
infra        <> <[5 *]> <[dup] infra> # append infra
.              <> <[5 *] [dup]]> <infra> # starting to execute
                <> <[5 5 *]>   # finished executing
i               <> <[5 5 *] i>  # append i
.               <[5 5 *]> <i>  # start executing
                <>  <5 5 *> # this is what i always does
                <5> <5 *> # pushed first 5
So the stack end up with a single 5. Not an exciting way to do it,
but it points to possibilities: construct a partial program, use Joy
itself to modify it, then finally execute the modified program. I have
used something similar in some of the Joy papers, where I speak of
executing ³constructed programs². But what all this shows is that
the behaviour of foyers that occurs inside function ³readterm()²
could be extended (even indefinitely) by just allowing ³.² to occur
after a ³[³ without a closing ³]² first.

Is it worth extending Joy in this way? It would take only a few very
tiny changes inside ³readterm()². Before you hasten to make those
changes, consider obtaining the identical effects from plain ol¹ Joy,
completely ignoring what goes on inside ³readterm()². Here is
the same program in plain Joy:

> [5 *] [dup] infra i .
> 
start with an empty stack:

                ->          # empty stack
[5 *]         ->   [5 *]    # push the quote
[dup]        ->    [5 *] [dup]   # push second quote
infra          ->    [5 5 *]  # execute the dup via infra
i                ->    25   # execute the top quote via i

Same behaviour, and probably a better notation.

Conjecture -- 1: Joy can be seen as a flat language, and could be programmed
that way if one really wanted to. But 2: But everything that can be done  by
programming in the flat version can equally well be done with the plain
version.

I am sorry that this has been so long.

  - Manfred













[Non-text portions of this message have been removed]