New compiler docs
Slava Pestov — 2004-06-10 22:05:49
Don Groves — 2004-06-11 22:03:07
Hi all,
The classic definition of a stack has only two operations,
push and pop. Under this definition, only the top item is
available for use - the prototypical example being a stack
of dinner plates at a buffet, only the topmost plate is
visible to the diners.
The stack that Concatenators use also has permutation
operations defined, swap, rot, etc., which require that
more than just the topmost item be "visible", in a sense.
Maybe we should invent a new term for this kind of "stack"
to avoid any possible confusion. I propose calling a
concatenative stack a "pack" - short for permutation stack
as used in the Henry Baker article, "Linear Logic and
Permutation Stacks -- The Forth Shall be First".
A pack then is a data structure with push, pop, and the usual
permutation operators defined on it. Like a pack of cards
which is normally dealt from the top (by honest folks) but
can be shuffled as well.
Any agreement, booing and hissing, or other suggestions?
--
Don Groves
Slava Pestov — 2004-06-11 22:15:18
Hi,
Permutations can be defined in terms of pop/push; for example, dup is just
temp = pop();
push(temp);
push(temp);
swap is
a = pop();
b = pop();
push(a);
push(b);
... and so on.
Don Groves wrote:
> Hi all,
>
> The classic definition of a stack has only two operations,
> push and pop. Under this definition, only the top item is
> available for use - the prototypical example being a stack
> of dinner plates at a buffet, only the topmost plate is
> visible to the diners.
>
> The stack that Concatenators use also has permutation
> operations defined, swap, rot, etc., which require that
> more than just the topmost item be "visible", in a sense.
>
> Maybe we should invent a new term for this kind of "stack"
> to avoid any possible confusion. I propose calling a
> concatenative stack a "pack" - short for permutation stack
> as used in the Henry Baker article, "Linear Logic and
> Permutation Stacks -- The Forth Shall be First".
>
> A pack then is a data structure with push, pop, and the usual
> permutation operators defined on it. Like a pack of cards
> which is normally dealt from the top (by honest folks) but
> can be shuffled as well.
>
> Any agreement, booing and hissing, or other suggestions?
> --
> Don Groves
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
Martin Young — 2004-06-11 22:25:47
On Fri, 2004-06-11 at 23:03, Don Groves wrote:
> The classic definition of a stack has only two operations,
> push and pop [...] The stack that Concatenators use also has
> permutation operations defined, swap, rot, etc.
In my experience stacks are generally understood to include all the
operators you mention. The classic stack orientated language, forth,
has them all and more.
I don't think a new term will do anything other than make concatenative
programming a teensy bit less accessible.
So I guess that's a boo and a hiss.
--
Martin Young, at home.
Don Groves — 2004-06-11 22:31:03
This is true, but it is not the way we implement or
visualize the situation. In the same way, multiplication
can be defined in terms of addition but having a multiplication
operator greatly simplies the syntax of arithmetic. Carrying
this to the extreme, all we need are the S and K combinators
to compute anything we want, why do we have all this other stuff?
--
Don
On Fri, 11 Jun 2004 18:15:18 -0400, Slava Pestov <slava@...> wrote:
> Hi,
>
> Permutations can be defined in terms of pop/push; for example, dup is just
>
> temp = pop();
> push(temp);
> push(temp);
>
> swap is
>
> a = pop();
> b = pop();
> push(a);
> push(b);
>
> ... and so on.
>
> Don Groves wrote:
>> Hi all,
>>
>> The classic definition of a stack has only two operations,
>> push and pop. Under this definition, only the top item is
>> available for use - the prototypical example being a stack
>> of dinner plates at a buffet, only the topmost plate is
>> visible to the diners.
>>
>> The stack that Concatenators use also has permutation
>> operations defined, swap, rot, etc., which require that
>> more than just the topmost item be "visible", in a sense.
>>
>> Maybe we should invent a new term for this kind of "stack"
>> to avoid any possible confusion. I propose calling a
>> concatenative stack a "pack" - short for permutation stack
>> as used in the Henry Baker article, "Linear Logic and
>> Permutation Stacks -- The Forth Shall be First".
>>
>> A pack then is a data structure with push, pop, and the usual
>> permutation operators defined on it. Like a pack of cards
>> which is normally dealt from the top (by honest folks) but
>> can be shuffled as well.
>>
>> Any agreement, booing and hissing, or other suggestions?
>> --
>> Don Groves
>>
>>
>>
>>
>>
>> Yahoo! Groups Links
>>
>>
>>
>>
>>
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
Don Groves — 2004-06-11 22:39:03
Forth is not a "classic stack" oriented language. The classic
stack as defined in any University class or book on data
structures has only the two original operators defined.
The Forth stack was the first to use the permutation operators,
Forth was not the first language to use stacks.
What I'm proposing is to make concatenative programming a
teensy bit more rigorous.
--
Don
On 11 Jun 2004 23:25:47 +0100, Martin Young <martin@...> wrote:
> On Fri, 2004-06-11 at 23:03, Don Groves wrote:
>> The classic definition of a stack has only two operations,
>> push and pop [...] The stack that Concatenators use also has
>> permutation operations defined, swap, rot, etc.
>
> In my experience stacks are generally understood to include all the
> operators you mention. The classic stack orientated language, forth,
> has them all and more.
>
> I don't think a new term will do anything other than make concatenative
> programming a teensy bit less accessible.
>
> So I guess that's a boo and a hiss.
>
asimjalis — 2004-06-11 22:45:39
On Fri, Jun 11, 2004 at 03:31:03PM -0700, Don Groves wrote:
> This is true, but it is not the way we implement or visualize
> the situation. In the same way, multiplication can be defined
> in terms of addition but having a multiplication operator
> greatly simplies the syntax of arithmetic. Carrying this to
> the extreme, all we need are the S and K combinators to compute
> anything we want, why do we have all this other stuff?
1. Whether you define number theory with multiplication or not,
in both cases you would call the underlying model the set of
numbers. Adding new operations defined in terms of previous ones
should not change the name of the underlying model.
2. Multiplication is not implemented in terms of addition in most
architectures. Yet, we persist in calling the underlying data
structure integers.
Asim
----
http://asimjalis.blogspot.com
Don Groves — 2004-06-11 23:00:15
Sorry, but I don't understand your comments in the context
of the operations defined on a stack.
--
Don
On Fri, 11 Jun 2004 22:45:39 -0000, asimjalis <asimjalis@...> wrote:
> On Fri, Jun 11, 2004 at 03:31:03PM -0700, Don Groves wrote:
>> This is true, but it is not the way we implement or visualize
>> the situation. In the same way, multiplication can be defined
>> in terms of addition but having a multiplication operator
>> greatly simplies the syntax of arithmetic. Carrying this to
>> the extreme, all we need are the S and K combinators to compute
>> anything we want, why do we have all this other stuff?
>
> 1. Whether you define number theory with multiplication or not,
> in both cases you would call the underlying model the set of
> numbers. Adding new operations defined in terms of previous ones
> should not change the name of the underlying model.
>
> 2. Multiplication is not implemented in terms of addition in most
> architectures. Yet, we persist in calling the underlying data
> structure integers.
>
> Asim
phimvt@lurac.latrobe.edu.au — 2004-06-16 06:53:01
On Fri, 11 Jun 2004, Don Groves wrote:
> Hi all,
>
> The classic definition of a stack has only two operations,
> push and pop. Under this definition, only the top item is
> available for use - the prototypical example being a stack
> of dinner plates at a buffet, only the topmost plate is
> visible to the diners.
>
> The stack that Concatenators use also has permutation
> operations defined, swap, rot, etc., which require that
> more than just the topmost item be "visible", in a sense.
And let's not forget the runtime stack of most languages:
it contains return addresses (in the "dynamic link),
actual parameters amd local variables, and is also used for
expression evaluation. It might also contain global variables
at the bottom of the stack. In languages like Pascal it also
contains the "static link" or an equivalent "display"
for access to local variables in enclosing procedures.
A wonderful invention, the whole thing.
But it is also called a stack, and it is at the other extreme
of complexity. At the simplicity extreme is the push-pop only
stck that you mentioned. I think it is too late to change usage.
- Manfred
Don Groves — 2004-06-16 18:01:17
Agreed. I'll pack up my pack idea and dispose of it.
Long live the stack!
--
Don Groves
On Wed, 16 Jun 2004 17:53:01 +1100, <phimvt@...> wrote:
>
> On Fri, 11 Jun 2004, Don Groves wrote:
>
>> Hi all,
>>
>> The classic definition of a stack has only two operations,
>> push and pop. Under this definition, only the top item is
>> available for use - the prototypical example being a stack
>> of dinner plates at a buffet, only the topmost plate is
>> visible to the diners.
>>
>> The stack that Concatenators use also has permutation
>> operations defined, swap, rot, etc., which require that
>> more than just the topmost item be "visible", in a sense.
>
> And let's not forget the runtime stack of most languages:
> it contains return addresses (in the "dynamic link),
> actual parameters amd local variables, and is also used for
> expression evaluation. It might also contain global variables
> at the bottom of the stack. In languages like Pascal it also
> contains the "static link" or an equivalent "display"
> for access to local variables in enclosing procedures.
> A wonderful invention, the whole thing.
>
> But it is also called a stack, and it is at the other extreme
> of complexity. At the simplicity extreme is the push-pop only
> stck that you mentioned. I think it is too late to change usage.