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