# Concatenative operators as functions over stacks.

## Don Groves — 2007-10-15 04:32:12

    I've long been intrigued by Manfred's statement that Joy operators are

    best described as functions from stacks to stacks and last night

    decided to put pencil to paper and try to put that idea into some sort

    of formal form -- both to aid my understanding of the implications of

    this statement, and to see if something useful might emerge from the

    effort. Here's a synopsis of what I've come up with so far:

    A stack S is a sequence (ordered collection) of terms S = s0, s1, ...,

    s(t-1), s(t) where only the most recently added term, s(t) is

    available. (Note: "t" can be though of as standing for "top") Except

    for the identity function, id : S --> S, all functions on S must begin

    with some operation on s(t).

    The function notation I use is

    f : S --> S\modifications

    which reads "function f is a mapping from stack S onto stack S

    modified by whatever follows the backslash." So we can define push and

    pop as:

    push(x,S) : S --> S\t=t+1 s(t)=x

    x = pop(S) : S --> S\x=s(t) t=t-1

    Given any pair x,S where x is a term and S a stack, we can compute,

    pop(push(x,S)) = pop(S\t=t+1 s(t)=x) = x,S\t=t+1-1 = x,S

    which is as expected.

    So, here's the question -- can all required operations of a

    concatenative language be defined in terms of these two primitive

    stack operations and function composition?

    To simplify the notation, we can get rid of the S (actually, make the

    S implicit)

    in the function definitions by push(x,S) = pushS(x) and pop(S) =

    popS() and then

    redefine them as push(x) and pop assuming there is only one stack

    under  consideration.

    The shuffle operators now become,

    dup : S --> S\x=pop push(x) push(x)

    swap : S --> S\x=pop y=pop push(x) push(y)

    etc...

    As Manfred points out, even concatenative literals behave as

    functions. For any literal value v,

    v : S --> S\push(v)

    The arithmetic operators become,

    add : S --> S\x=pop y=pop push(x+y)

    etc...

    Actually we can generalize arithmetic and relational operators as

    binary operators,

    binop(op) : S --> S\x=pop y=pop push(x op y) for op in

    (+,-,*,/,mod,=,!=,...)

    By adding additional notation for lists, sets, ..., this method seems

    able to account for any concatentative operation. For example, if we

    use the Haskell list notation [x|xs], then cons becomes,

    cons : S --> S\x=pop [xs]=pop push([x|xs])

    If we say that [Q] is a quoted program, we can define map as,

    map : S --> S\[Q]=pop [y]=pop push([Q(y0) Q(y1) ... ])

    The above seems to be the lambda calculus version of the situation as

    it uses dummy variables. If variables are forbidden, the situation

    becomes different quickly. If we try to write swap, for instance,

    without dummy variables,

    swap : S --> S\pop pop ? push push

    we have an immediate problem -- how do we change the order of  the two

    popped values? What replaces the question mark? Of course it is the C

    combinator and now we're off down the combinator trail which Manfred

    seems to prefer anyway.

    If someone wants to take the time to produce a combinator version of

    this notation, it would be a useful addition to our knowledge base, imho.

    This is getting very long and I won't bore anyone with further details

    but I'd like to know if anyone considers this a useful avenue for

    further exploration. I'm thinking of writing a tiny interpreter using

    only the methods given and hinted at here just to see how it goes and

    what kind of program results.

    One thing of interest is that the notation above lends itself to

    direct compilation from a specification, if we remove the arrows and

    just write

    dup ::=  x=pop push(x) push(x)

    etc...

    --

    Don Groves

## pml060912 — 2007-10-15 13:13:35

    --- In concatenative@yahoogroups.com, "Don Groves" <dgroves@...> wrote:

     >

    > I've long been intrigued by Manfred's statement that Joy operators are

    > best described as functions from stacks to stacks

     If you just look at that on its own, it isn't enough. There's a

    standard computer science result, that I don't have a reference to off

    hand, that says that a PURE stack machine isn't Turing equivalent,

    i.e. if you can only work within a limited depth of one stack at any

    stage and the stack only holds simple values (roughly speaking). You

    can get Turing equivalent if you have a two stack machine, or if you

    have non-standard operators, e.g. like Forth's PICK and ROLL, or

    non-functional stuff for memory peeking and poking like Forth's @ and !.

    .

    .

    .

     > So, here's the question -- can all required operations of a

    > concatenative language be defined in terms of these two primitive

    > stack operations and function composition?

     No, not within the pure stack machine limit. When I look at my own

    work with Furphy (mentioned in earlier threads), it turns out that all

    operations in that take two stacks and return two stacks, but most

    operations leave one - the return stack - essentially unchanged. So,

    most operations can be thought of as taking and yielding a single

    stack, but some need both; these are really higher order functions in

    some sense (you can build PICK and ROLL using these and the simpler

    operations). But you don't need to go beyond two stacks and end up

    with a regress of stacks, a stack of stacks say.

    .

    .

    .

     > By adding additional notation for lists, sets, ..., this method seems

    > able to account for any concatentative operation.

     That's another way of expanding what you can do with one stack, enough

    to make it Turing equivalent. And of course I provide that in Furphy

    too - but it turns out, so far, that this is orthogonal to what Furphy

    does with higher order, two stack using, operations. PML.

## Don Groves — 2007-10-15 20:12:30

    On Oct 15, 2007, at 19:13 , pml060912 wrote:

     > --- In concatenative@yahoogroups.com, "Don Groves" <dgroves@...>

    > wrote:

    >>

    >> I've long been intrigued by Manfred's statement that Joy operators

    >> are

    >> best described as functions from stacks to stacks

    >

    > .

    > .

    >> By adding additional notation for lists, sets, ..., this method seems

    >> able to account for any concatentative operation.

    >

    > That's another way of expanding what you can do with one stack, enough

    > to make it Turing equivalent. And of course I provide that in Furphy

    > too - but it turns out, so far, that this is orthogonal to what Furphy

    > does with higher order, two stack using, operations. PML.

     Thanks for the response, Peter.