# A purely complete base

## Brent L Kerby — 2002-04-03 02:21:43

    After a bit of thought, I realized (to my surprise, actually) that there is a

    base containing only true combinators, with the property that all combinators

    can be constructed by concatenating the bases, without the use of quotation (a

    base that has this property I'll call "purely complete"). A base that works is

    {nil, take, i, cons, dup, zap} where "nil" is a nice name for "[]". I don't yet

    really have a cohesive proof that this works, but here's my chain of thought:

    I was thinking that the "reverse" combinators would be very helpful, since there

    is a scheme for constructing them that does not rely on quotation:

      reverse2 == unit dip

      reverse3 == unit take dip

      reverse4 == unit take take dip

      ...

    And from "reverse", there immediate follows "bury" and "dig", because, for

    example, "bury5" can be constructed as

      bury5 == reverse5 reverse4

    The idea is that reverse5 buries the top item to the bottom, and then reverse4

    cleans up the mess. And then, "dig" being the inverse of "bury", you get

      dig5 == reverse4 reverse5

    Now, with this, we have the ability to rearrange the stack in any way. And,

    here's a scheme for generating "dipn":

      dip3 == take take take i reverse3

           == take take dip reverse3

    It works like this:

       [3] [2] [1] [0] take take take i reverse3

    == [3] [2] [0 [1]] take take i reverse3

    == [3] [0 [1] [2]] take i reverse3

    == [0 [1] [2] [3]] i reverse3

    == 0 [1] [2] [3] reverse3

    == 0 [3] [2] [1]

    So we have all the "dig"'s, "bury"'s, and "dip"'s. This, along with "dup",

    "zap", and "cons", gives us all the power we really need, I think.

    - Brent

## Manfred von Thun — 2002-04-03 08:42:18

    On the question of a small base of stack editing (pop,swap....)

    operators, here is a small contribution:

    The philosopher/logician W.V.O. Quine addressed a similar question

    in his monograph

        Algebraic Logic and Predicate Functors

        Bobbs-Merrill (Publisher), 1971

    (This, together with the famous Backus paper "Is Computer Science.."

    was one of the original inspirations for Joy.)

    A predicate can take any number of arguments. Think of them as a

    sequence or list (or a stack). The problem is to be able to shuffle

    arguments around so that any possible shuffling can be expressed.

    Quine came up with two interesting primitives:

        1: swap the first two (top two)

        2: SWAP the first and the last (or the top and the bottom)

    I think there were other primitives, but I cannot remember what

    they were. Probably something resembling dup and pop...?

    I suspect that these two primitives come from some theorem in

    permutation theory. Note that any sequence of swap's and SWAP's

    will keep the number of items the same - never add anything,

    never lose anything. So it is all about permutations of items

    in a sequence. (Any pure mathematicians out there ?)

    Together with whatever other primitives he had, Quine was able to

    show that his primitives were sufficient for his purpose -

    which was to eliminate the variables of quantification in

    predicate logic. (Schoenfinkel, Curry, Backus did much the same

    with the variables of lambda abstraction - although I must hasten

    to add, Schoenfinkel came well before the lambda calculus was

    invented.)

      - Manfred

## Manfred von Thun — 2002-04-04 05:36:09

    I felt it necessary to hunt for the original sources again...

    I have to correct some detail, and I can add some others to my post.

     On Wed, 3 Apr 2002, Manfred von Thun wrote:

    >

    > On the question of a small base of stack editing (pop,swap....)

    > operators, here is a small contribution:

    >

    > The philosopher/logician W.V.O. Quine addressed a similar question

    > in his monograph

    >     Algebraic Logic and Predicate Functors

    >     Bobbs-Merrill (Publisher), 1971

          [Reprinted in  The Ways of Paradox (2nd ed), Harvard UP, 1976]

    > (This, together with the famous Backus paper "Is Computer Science.."

    > was one of the original inspirations for Joy.)

    >

    > A predicate can take any number of arguments. Think of them as a

    > sequence or list (or a stack). The problem is to be able to shuffle

    > arguments around so that any possible shuffling can be expressed.

    > Quine came up with two interesting primitives:

    >     1: swap the first two (top two)

    >     2: SWAP the first and the last (or the top and the bottom)

    Actually this was not in the Algbraic Logic paper but in

          Variables explained away

          Proceedings of the Am. Philosophical Society, 1960

          [Reprinted in  Selected Logic Papers, Random House, 1966]

    The single primitive permutation operator in Algebraic Logic is even

    more mind-boggling: Swap the second and the last (!)

    Using the end of a list or the bottom of the stack is certainly one

    way of saving and later restoring things. One could do it in Joy,

    but in the current (singly linked) implementation of the stack

    it would be inefficient. Forth programs sometimes use the return

    stack similar effect. Joy has the dip combinator to save and restore

    the top element. Nested dip's then can get arbitrarily deep into

    the stack - the deeper the slower, of course.

    [ This might be the place to raise a possibility that I have been

      toying with for some time: inside the dipped quotation, allow

      at least read-access to either the last item that has been

      dipped away, or even the whole list of things that have been

      successively dipped away:

        a  b  c  [... read-access ...]  dip

                      ^^^^^^^^^^^  sees the c, in the form of a push.

      I suspect that sometimes this might be useful, but I don't have

      a clear example. Any opinions?

      Furthermore, could one allow write-access? Should one? ]

    > I think there were other primitives, but I cannot remember what

    > they were. Probably something resembling dup and pop...?

    Yes, my memory was correct on this point. But since the

    topic of both papers is predicate logic, the pop - curiously -

    is essentially existential quantification.

    > I suspect that these two primitives come from some theorem in

    Here I meant the swap and SWAP of the first definition

    > permutation theory. Note that any sequence of swap's and SWAP's

    > will keep the number of items the same - never add anything,

    > never lose anything. So it is all about permutations of items

    > in a sequence. (Any pure mathematicians out there ?)

    >

    > Together with whatever other primitives he had, Quine was able to

    > show that his primitives were sufficient for his purpose -

    > which was to eliminate the variables of quantification in

    > predicate logic. (Schoenfinkel, Curry, Backus did much the same

    > with the variables of lambda abstraction - although I must hasten

    > to add, Schoenfinkel came well before the lambda calculus was

    > invented.)

    >

    >   - Manfred

    As far as I can tell, any required reshuffling of the elements

    of a stack can be expressed by

      1. the Joy operators  dup pop swap

      2. the Joy combinator  dip

    The three operand operators such as

         rollup (two go up, top goes down into third place)

         rolldown (top two go down, third becomes top)

         rotate (interchange top and third)

    are easily defined in terms of the 1 and 2. They have been made

    primitive for efficiency. The total of six so far has been

    doubled by further primitives with an extra 'd at the end,

    because they are dipped versions of the others.

    It is just about impossible to keep on thinking up names

    for new operators. Most combinations of two of the above 12

    mean something that may be useful somewhere - but there must

    be already 80 such combinations...

      - Manfred

## Brent L Kerby — 2002-04-04 08:06:34

    > [ This might be the place to raise a possibility that I have been

    >   toying with for some time: inside the dipped quotation, allow

    >   at least read-access to either the last item that has been

    >   dipped away, or even the whole list of things that have been

    >   successively dipped away:

    >     a  b  c  [... read-access ...]  dip

    >                   ^^^^^^^^^^^  sees the c, in the form of a push.

    >   I suspect that sometimes this might be useful, but I don't have

    >   a clear example. Any opinions?

     Hmm, my opinion I guess is that such a read-access extension is unneccessary

    because if you wanted read-access, just use "sip" instead of "dip":

      [B] [A] sip == [B] A [B]

    You can see that the "dipped" program "A" has access to the "B" (albeit only

    through stack manipulation, which could get messy, if there are many objects),

    in addition to a copy being saved for afterwards. By the way, "sip" doesn't seem

    to be part of the standard implementation; I think it really should be, seeing

    that it is very fundamental.

    I think an extension that would accomplish your idea above while also doing very

    much other good would be to add a lambda construct:

    Basically, you would make it so that "x\" pops the top item off the stack and

    calls it "x". Essentially, this acts kind of like a "dip", since it temporarily

    gets rid of the top item on the stack. However, it is also like a "zap", if you

    choose never to use "x" again; or it is like, "dup", if you use "x" multiple

    times. Or, it is like "cons" if you use "x" inside a quotation. A lambda

    construct really is all the combinators rolled into one; it is truely beautiful,

    in my opinion.

    There is a subtle thing about how exactly to define lambdas here. It is:

      Assuming we've used a lambda 'x\', then should 'x' push a copy of

      x onto the stack, or should 'x' run the program 'x'?

    In other words, should "x\ x" be a program that does nothing, or should it be a

    construction the "i" combinator? My conclusion was that "x" should execute what

    what put in "x", because this makes it possible to construct the "i" combinator,

    and indeed all combinators, using the lambda construct.

    Anyway, I won't go on about this, because actually Billy and I discussed it

    quite a bit back in May 2000, on this concatenative list, right after it was

    opened.

    I should try to resolve one thing that wasn't resolved back then. In his last

    post, Billy asked, semi-rhetorically:

      So would you say that "[2]" means "push 2 on the stack?"

    This comes down to quite a subtle issue. To illustrate, note that "dup" can be

    described by the rewrite rule:

      [A] dup  == [A] [A]

    In a pure system (containing only combinators and pseudo-combinators, but no

    numeric data), this rule completely describes "dup". But, when numeric data is

    added to the system, this rule becomes insufficient, because it does not say

    that

      2 dup == 2 2

    In a way, I might say that for the system to be most natural, in a theoretical

    sense, really we should require "[2]" everywhere instead of just "2" (so, the

    answer to Billy's question above is "yes", sort of). In fact, for a version of

    Joy designed for theoretical proofing stuff, I might suggest actually use that

    approach (i.e., using [2] to push 2 onto the stack, instead of just "2"), and

    define

       0 == zap

       1 == i

       2 == dup dip i

       3 == dup dip dup dip i

       etc.

    These are the iterators (aka Church numbers), in a concatenative incarnation.

    And then, "2" by itself, means to run a program twice. (If you want to get

    really adventurous, define "-1" as an undo primitive).

    This reminds of an article regarding Church numbers and operators in an

    applicative system: <http://www.dcs.ed.ac.uk/home/pgh/amen.html>. The

    fascinating result here was that {+, *, ^, 0} (aka {A, M, E, N}) forms a

    complete combinatory base; I don't think quite the same thing happens in a

    concatenative system, though; oh well.

    Anyhow, for practical Joy-like systems, I think just "2" is fine for pushing 2

    onto the stack ...

     > As far as I can tell, any required reshuffling of the elements

    > of a stack can be expressed by

    >   1. the Joy operators  dup pop swap

    >   2. the Joy combinator  dip

     Yep. This is true. In fact, {dup, pop, swap, dip} gives you a little more power

    than to just shuffle stack items. Using "dip", it is possible to execute stack

    items. Throw in "cons", and this base becomes complete (and "swap" becomes

    unneccessary, being constructible as "[] cons dip"). Or alternatively, throw in

    "unit", "cat", and "i", and "dip" becomes unneccessary (being constructible as

    "swap unit cat i").

    Actually, the base {dup, pop, swap, unit, cat, i} is rather elegant because each

    combinator has a sort of symmetry:

        [A] dup  == [A] [A]

        [A] pop  ==

    [B] [A] swap == [A] [B]

        [A] unit == [[A]]

    [B] [A] cat  == [B A]

        [A] i    == A

     >   - Manfred

     - Brent

## Brent L Kerby — 2002-04-04 08:09:40

    > [ This might be the place to raise a possibility that I have been

    >   toying with for some time: inside the dipped quotation, allow

    >   at least read-access to either the last item that has been

    >   dipped away, or even the whole list of things that have been

    >   successively dipped away:

    >     a  b  c  [... read-access ...]  dip

    >                   ^^^^^^^^^^^  sees the c, in the form of a push.

    >   I suspect that sometimes this might be useful, but I don't have

    >   a clear example. Any opinions?

     Hmm, my opinion I guess is that such a read-access extension is unneccessary

    because if you wanted read-access, just use "sip" instead of "dip":

      [B] [A] sip == [B] A [B]

    You can see that the "dipped" program "A" has access to the "B" (albeit only

    through stack manipulation, which could get messy, if there are many objects),

    in addition to a copy being saved for afterwards. By the way, "sip" doesn't seem

    to be part of the standard implementation; I think it really should be, seeing

    that it is very fundamental.

    I think an extension that would accomplish your idea above while also doing very

    much other good would be to add a lambda construct:

    Basically, you would make it so that "x\" pops the top item off the stack and

    calls it "x". Essentially, this acts kind of like a "dip", since it temporarily

    gets rid of the top item on the stack. However, it is also like a "zap", if you

    choose never to use "x" again; or it is like, "dup", if you use "x" multiple

    times. Or, it is like "cons" if you use "x" inside a quotation. A lambda

    construct really is all the combinators rolled into one; it is truely beautiful,

    in my opinion.

    There is a subtle thing about how exactly to define lambdas here. It is:

      Assuming we've used a lambda 'x\', then should 'x' push a copy of

      x onto the stack, or should 'x' run the program 'x'?

    In other words, should "x\ x" be a program that does nothing, or should it be a

    construction the "i" combinator? My conclusion was that "x" should execute what

    what put in "x", because this makes it possible to construct the "i" combinator,

    and indeed all combinators, using the lambda construct.

    Anyway, I won't go on about this, because actually Billy and I discussed it

    quite a bit back in May 2000, on this concatenative list, right after it was

    opened.

    I should try to resolve one thing that wasn't resolved back then. In his last

    post, Billy asked, semi-rhetorically:

      So would you say that "[2]" means "push 2 on the stack?"

    This comes down to quite a subtle issue. To illustrate, note that "dup" can be

    described by the rewrite rule:

      [A] dup  == [A] [A]

    In a pure system (containing only combinators and pseudo-combinators, but no

    numeric data), this rule completely describes "dup". But, when numeric data is

    added to the system, this rule becomes insufficient, because it does not say

    that

      2 dup == 2 2

    In a way, I might say that for the system to be most natural, in a theoretical

    sense, really we should require "[2]" everywhere instead of just "2" (so, the

    answer to Billy's question above is "yes", sort of). In fact, for a version of

    Joy designed for theoretical proofing stuff, I might suggest actually use that

    approach (i.e., using [2] to push 2 onto the stack, instead of just "2"), and

    define

       0 == zap

       1 == i

       2 == dup dip i

       3 == dup dip dup dip i

       etc.

    These are the iterators (aka Church numbers), in a concatenative incarnation.

    And then, "2" by itself, means to run a program twice. (If you want to get

    really adventurous, define "-1" as an undo primitive).

    This reminds of an article regarding Church numbers and operators in an

    applicative system: <http://www.dcs.ed.ac.uk/home/pgh/amen.html>. The

    fascinating result here was that {+, *, ^, 0} (aka {A, M, E, N}) forms a

    complete combinatory base; I don't think quite the same thing happens in a

    concatenative system, though; oh well.

    Anyhow, for practical Joy-like systems, I think just "2" is fine for pushing 2

    onto the stack ...

     > As far as I can tell, any required reshuffling of the elements

    > of a stack can be expressed by

    >   1. the Joy operators  dup pop swap

    >   2. the Joy combinator  dip

     Yep. This is true. In fact, {dup, pop, swap, dip} gives you a little more power

    than to just shuffle stack items. Using "dip", it is possible to execute stack

    items. Throw in "cons", and this base becomes complete (and "swap" becomes

    unneccessary, being constructible as "[] cons dip"). Or alternatively, throw in

    "unit", "cat", and "i", and "dip" becomes unneccessary (being constructible as

    "swap unit cat i").

    Actually, the base {dup, pop, swap, unit, cat, i} is rather elegant because each

    combinator has a sort of symmetry:

        [A] dup  == [A] [A]

        [A] pop  ==

    [B] [A] swap == [A] [B]

        [A] unit == [[A]]

    [B] [A] cat  == [B A]

        [A] i    == A

     >   - Manfred

     - Brent

## Brent L Kerby — 2002-04-04 08:09:56

    > [ This might be the place to raise a possibility that I have been

    >   toying with for some time: inside the dipped quotation, allow

    >   at least read-access to either the last item that has been

    >   dipped away, or even the whole list of things that have been

    >   successively dipped away:

    >     a  b  c  [... read-access ...]  dip

    >                   ^^^^^^^^^^^  sees the c, in the form of a push.

    >   I suspect that sometimes this might be useful, but I don't have

    >   a clear example. Any opinions?

     Hmm, my opinion I guess is that such a read-access extension is unneccessary

    because if you wanted read-access, just use "sip" instead of "dip":

      [B] [A] sip == [B] A [B]

    You can see that the "dipped" program "A" has access to the "B" (albeit only

    through stack manipulation, which could get messy, if there are many objects),

    in addition to a copy being saved for afterwards. By the way, "sip" doesn't seem

    to be part of the standard implementation; I think it really should be, seeing

    that it is very fundamental.

    I think an extension that would accomplish your idea above while also doing very

    much other good would be to add a lambda construct:

    Basically, you would make it so that "x\" pops the top item off the stack and

    calls it "x". Essentially, this acts kind of like a "dip", since it temporarily

    gets rid of the top item on the stack. However, it is also like a "zap", if you

    choose never to use "x" again; or it is like, "dup", if you use "x" multiple

    times. Or, it is like "cons" if you use "x" inside a quotation. A lambda

    construct really is all the combinators rolled into one; it is truely beautiful,

    in my opinion.

    There is a subtle thing about how exactly to define lambdas here. It is:

      Assuming we've used a lambda 'x\', then should 'x' push a copy of

      x onto the stack, or should 'x' run the program 'x'?

    In other words, should "x\ x" be a program that does nothing, or should it be a

    construction the "i" combinator? My conclusion was that "x" should execute what

    what put in "x", because this makes it possible to construct the "i" combinator,

    and indeed all combinators, using the lambda construct.

    Anyway, I won't go on about this, because actually Billy and I discussed it

    quite a bit back in May 2000, on this concatenative list, right after it was

    opened.

    I should try to resolve one thing that wasn't resolved back then. In his last

    post, Billy asked, semi-rhetorically:

      So would you say that "[2]" means "push 2 on the stack?"

    This comes down to quite a subtle issue. To illustrate, note that "dup" can be

    described by the rewrite rule:

      [A] dup  == [A] [A]

    In a pure system (containing only combinators and pseudo-combinators, but no

    numeric data), this rule completely describes "dup". But, when numeric data is

    added to the system, this rule becomes insufficient, because it does not say

    that

      2 dup == 2 2

    In a way, I might say that for the system to be most natural, in a theoretical

    sense, really we should require "[2]" everywhere instead of just "2" (so, the

    answer to Billy's question above is "yes", sort of). In fact, for a version of

    Joy designed for theoretical proofing stuff, I might suggest actually use that

    approach (i.e., using [2] to push 2 onto the stack, instead of just "2"), and

    define

       0 == zap

       1 == i

       2 == dup dip i

       3 == dup dip dup dip i

       etc.

    These are the iterators (aka Church numbers), in a concatenative incarnation.

    And then, "2" by itself, means to run a program twice. (If you want to get

    really adventurous, define "-1" as an undo primitive).

    This reminds of an article regarding Church numbers and operators in an

    applicative system: <http://www.dcs.ed.ac.uk/home/pgh/amen.html>. The

    fascinating result here was that {+, *, ^, 0} (aka {A, M, E, N}) forms a

    complete combinatory base; I don't think quite the same thing happens in a

    concatenative system, though; oh well.

    Anyhow, for practical Joy-like systems, I think just "2" is fine for pushing 2

    onto the stack ...

     > As far as I can tell, any required reshuffling of the elements

    > of a stack can be expressed by

    >   1. the Joy operators  dup pop swap

    >   2. the Joy combinator  dip

     Yep. This is true. In fact, {dup, pop, swap, dip} gives you a little more power

    than to just shuffle stack items. Using "dip", it is possible to execute stack

    items. Throw in "cons", and this base becomes complete (and "swap" becomes

    unneccessary, being constructible as "[] cons dip"). Or alternatively, throw in

    "unit", "cat", and "i", and "dip" becomes unneccessary (being constructible as

    "swap unit cat i").

    Actually, the base {dup, pop, swap, unit, cat, i} is rather elegant because each

    combinator has a sort of symmetry:

        [A] dup  == [A] [A]

        [A] pop  ==

    [B] [A] swap == [A] [B]

        [A] unit == [[A]]

    [B] [A] cat  == [B A]

        [A] i    == A

     >   - Manfred

     - Brent

## venusian_1999 — 2002-04-04 13:14:02

    --- In concatenative@y..., Manfred von Thun <phimvt@l...> wrote:

     > [ This might be the place to raise a possibility that I have been

    >   toying with for some time: inside the dipped quotation, allow

    >   at least read-access to either the last item that has been

    >   dipped away, or even the whole list of things that have been

    >   successively dipped away:

    >     a  b  c  [... read-access ...]  dip

    >                   ^^^^^^^^^^^  sees the c, in the form of a push.

    >   I suspect that sometimes this might be useful, but I don't have

    >   a clear example. Any opinions?

    >   Furthermore, could one allow write-access? Should one? ]

     I've written a number of Joy-esque interpreters in a couple of

    different languages and one of the implementation idioms I keep coming

    back to is a three stack scheme.  This scheme allows read and write

    access to dipped items.

    Here's how it works:

    The first stack is the program stack: it's all the items left to

    execute with the "next" one at the top of the stack.  Execution of a

    program is the process of popping items one at a time and acting on them.

    The second stack is the data stack.  This is the normal Joy stack.

    Executing the program "1 drop" would involve removing "1" from the

    program stack an pushing it onto the data stack, then removing the

    word "drop" from the program stack and then popping the word "1" from

    the data stack.  Nothing complex here.

    The third stack is the dip stack.  It performs many of the same

    functions as the return stack in forth.  There are just two words

    defined which affect the dip stack: move and unmove.  "move" pops the

    top item from the data stack and pushes it onto the dip stack.

    "unmove" pops the top item from the dip stack and pushes it onto the

    data stack.

    Thus, dip can be defined as [ move i unmove ].  In a simpler world a

    program would be able to get the most recently dipped item by doing

    this: [ unmove dup move ].  The dip stack, however, has another

    implicit function which complecates things.

    The word "i" pushes the whole program stack, as a list, onto the dip

    stack and uses the quoted program as the program stack.  If the

    program stack become empty the top item on the dip stack is popped and

    used as the program stack.

    Thus, getting the dipped item is actually [ unmove unmove dup move

    swap move ] because the top item on the dip stack is the remains of

    the previous program when the quoted program was unquoted.  (I think

    this is the right code; I don't have the sources here but I can assure

    you it can be made to work).  Modifying the dip stack simply involves

    moving back a value other than that which you unmoved.

    Getting to items through N layers of dips is possible but messy. It's

    the sort of thing for which a sane person would require syntactic sugar.

    A nice side effect of having an explicit dip stack is that the current

    continuation is encapsulated by the dip stack with the current program

    stack pushed on top (as with "i").  It's possible (I've done it) to

    implement all of Joy's itterative and recursive combinators using

    "move", "unmove", "i" and a handful of list manipulation words.

    Perhaps this brings us vaguely back to the topic of small bases?

## Brent L Kerby — 2002-04-04 20:21:22

    > I've written a number of Joy-esque interpreters in a couple of

    > different languages and one of the implementation idioms I keep coming

    > back to is a three stack scheme.

    >

    > [interesting system ...]

     I wanted to mention an extension of lambdas which allows something similar to

    your "move" and "umove" ... (I think I may have mentioned an idea similar to

    this a long time ago, but I can't seem to find where)

    First, the basic idea of lambdas was that you could do

    "x\" to pop an item off the data stack, storing it on the "x" stack.

    "x/" to pop an item off the "x" stack, storing on the data stack.

    "x!" to pop an item off the data stack, overwriting the top of the "x" stack.

    "x@" to copy an item off the "x" stack, putting it on the data stack.

    "x#" to zap the top item on the "x" stack

    "x"  to execute the top item on the "x" stack

    These are essentially tools for manipulating variables, where each variable is a

    stack, for scoping purposes, and convenience. The only essential ones really are

    "x\", "x#", and "x" (and "x#" is in a way nonessential, theoretically, as long

    as you don't ever need to reclaim your storage).

    Anyway, the idea I really wanted to mention was to allow the blank, anonymous

    variable to play the role of a return stack. That is, you could use "\" to push

    to the return stack, "@" to read from it, "!" to write, "/" to pop back off, and

    "#" to zap the top item.

    Then, "\" and "/" would be the equivalent of your "move" and "umove", although

    with "\" and "/" it would not be possible to do the continuation tricks you

    described.

    - Brent

## Manfred von Thun — 2002-04-08 04:00:16

    On -1 xxx -1, Brent L Kerby wrote: [probably 4-APR-2002]

     > > [ This might be the place to raise a possibility that I have been

    > >   toying with for some time: inside the dipped quotation, allow

    > >   at least read-access to either the last item that has been

    > >   dipped away, or even the whole list of things that have been

    > >   successively dipped away:

    > >     a  b  c  [... read-access ...]  dip

    > >                   ^^^^^^^^^^^  sees the c, in the form of a push.

    > >   I suspect that sometimes this might be useful, but I don't have

    > >   a clear example. Any opinions?

    >

    > Hmm, my opinion I guess is that such a read-access extension is unneccessary

    > because if you wanted read-access, just use "sip" instead of "dip":

    >

    >   [B] [A] sip == [B] A [B]

     Yes, such  read-access is not necessary, but it might make programs

    clearer. On the other hand, since such access cannot be defined in

    existing Joy, it would be adding one extra mechanism which is not

    worth the conceptual complication. (The implementation would be just

    about trivial.)

     > You can see that the "dipped" program "A" has access to the "B" (albeit only

    > through stack manipulation, which could get messy, if there are many objects),

    > in addition to a copy being saved for afterwards. By the way, "sip" doesn't seem

    > to be part of the standard implementation; I think it really should be, seeing

    > that it is very fundamental.

     I would be very happy to add sip to the standard implementation if it

    is useful for your collection of fundamentals.

     > I think an extension that would accomplish your idea above while also doing very

    > much other good would be to add a lambda construct:

     I do remember this discussion arising quite a while back...

     > Basically, you would make it so that "x\" pops the top item off the stack and

    > calls it "x". Essentially, this acts kind of like a "dip", since it temporarily

    > gets rid of the top item on the stack. However, it is also like a "zap", if you

    > choose never to use "x" again; or it is like, "dup", if you use "x" multiple

    > times.

     One big and important decision is what the scope of the abstraction is

    to be. Lambda abstraction  has a definite scope for the abstracted

    variable, and at the end of that scope the previous (if any) binding

    will be in force. I think you are saying to make the scope the end of

    the current run? That would make it very difficult to use in case

    such as this:

      DEFINE   foo  ==  x\ ...x...x...

               bar  ==  x\ ...x...foo...x...

    The point is that to use foo one has to know which variable name it uses

    for its abstraction. In lambda calculus languages this problem does not

    arise.

    But there are other possible ways of introducing abstraction with a

    more orderly scope. I have thought about it on and off, but not

    come to any clear conclusion that is in the spirit of Joy.

    [...]

     > This reminds of an article regarding Church numbers and operators in an

    > applicative system: <http://www.dcs.ed.ac.uk/home/pgh/amen.html>. The

     Thanks. That is indeed an interesting paper.

    [...]

      - Manfred

## Manfred von Thun — 2002-04-08 04:31:50

    On Thu, 4 Apr 2002, venusian_1999 wrote:

     > --- In concatenative@y..., Manfred von Thun <phimvt@l...> wrote:

     [..]

     > >     a  b  c  [... read-access ...]  dip

    > >                   ^^^^^^^^^^^  sees the c, in the form of a push.

    > >   I suspect that sometimes this might be useful, but I don't have

    > >   a clear example. Any opinions?

    > >   Furthermore, could one allow write-access? Should one? ]

    >

    > I've written a number of Joy-esque interpreters in a couple of

    > different languages

     This sounds fascinating. Are any of them in a state that you would

    be willing to share with us? Perhaps in the files-are of caoncatenative?

     >                 and one of the implementation idioms I keep coming

    > back to is a three stack scheme.  This scheme allows read and write

    > access to dipped items.

    >

    > Here's how it works:

    >

    > The first stack is the program stack: it's all the items left to

    > execute with the "next" one at the top of the stack.  Execution of a

    > program is the process of popping items one at a time and acting on them.

     Incidentally, this is almost what the operator "conts" makes visible

    - it pushes the outstanding continuations onto the Joy stack. (But

    I haven't really found a use for it yet. However, that might change

    when I understand continuations better. I use programmed continuations

    for backtracking in plglib.joy (propositional logic) library. I am

    also using programmed continuations in my current work.)

     > The second stack is the data stack.  This is the normal Joy stack.

     [...]

     > The third stack is the dip stack.  It performs many of the same

    > functions as the return stack in forth.  There are just two words

    > defined which affect the dip stack: move and unmove.

     Yes, there is something similar in the unix desk calculator dc

    which gave me a similar idea. But then I abandoned it in favour of

    the more hight level, more structured dip combinator.

    All the time I have been aware of the controversy in the 70's

    that started with Dijkstra's paper "Goto considered harmful".

    Many things in the design of Joy I have rejected because

    they might be considered harmful.

    [...]

     > Thus, dip can be defined as [ move i unmove ].  In a simpler world a

    > program would be able to get the most recently dipped item by doing

    > this: [ unmove dup move ].  The dip stack, however, has another

    > implicit function which complecates things.

    >

    > The word "i" pushes the whole program stack, as a list, onto the dip

    > stack and uses the quoted program as the program stack.  If the

    > program stack become empty the top item on the dip stack is popped and

    > used as the program stack.

    >

    > Thus, getting the dipped item is actually [ unmove unmove dup move

    > swap move ] because the top item on the dip stack is the remains of

    > the previous program when the quoted program was unquoted.  (I think

    > this is the right code; I don't have the sources here but I can assure

    > you it can be made to work).  Modifying the dip stack simply involves

    > moving back a value other than that which you unmoved.

    >

    > Getting to items through N layers of dips is possible but messy. It's

    > the sort of thing for which a sane person would require syntactic sugar.

    >

    > A nice side effect of having an explicit dip stack is that the current

    > continuation is encapsulated by the dip stack with the current program

    > stack pushed on top (as with "i").  It's possible (I've done it) to

    > implement all of Joy's itterative and recursive combinators using

    > "move", "unmove", "i" and a handful of list manipulation words.

     Fascinating ideas here. I hope we hear more from you.

      - Manfred