# Auxiliary stacks and Dip

## Christopher Diggins — 2006-07-19 05:13:19

    So I implemented a DIP combinator in Cat and I realized that in order

    to implement it I had to use an extra stack!

    It wasn't obvious because I was actually using the interpreter's call

    stack, but in effect this is a second stack. So I thought to myself,

    why only give a simple DIP combinator, when I might as well give an

    entire second stack.

    By adding an auxiliary stack Cat suddenly becomes muchg easier to

    translate to from arbitrary Algol derived language X, and can be more

    easily compiled to some arbitrary target Y.

    I wonder how this will interfere with the algebraic properties of

    single stack concatenative language. Any thoughts?

## William Tanksley, Jr — 2006-07-19 17:30:25

    Christopher Diggins <cdiggins@...> wrote:

     > So I implemented a DIP combinator in Cat and I realized that in order

    > to implement it I had to use an extra stack!

     Pretty much, yup.

     > It wasn't obvious because I was actually using the interpreter's call

    > stack, but in effect this is a second stack. So I thought to myself,

    > why only give a simple DIP combinator, when I might as well give an

    > entire second stack.

     I like your thinking :-). Yes, exposing the entire second stack gives

    a lot more flexibility. Forth calls it the "return stack". There are

    costs, though -- the second stack has to be used in very specific

    ways; for example, it's very bad to leave a temporary item on the

    second stack when your function attempts to return. Static

    typechecking can easily check for all of the critical errors you can

    make.

    dip has the advantage of being self-contained; it's not possible to

    leave a temporary item behind on the return stack.

     > By adding an auxiliary stack Cat suddenly becomes muchg easier to

    > translate to from arbitrary Algol derived language X, and can be more

    > easily compiled to some arbitrary target Y.

     Yes, I think we talked about this a couple of weeks ago. I also

    mentioned the possibility of typechecking that stack at the time. You

    might go back and re-read those messages in light of what you've

    discovered.

     > I wonder how this will interfere with the algebraic properties of

    > single stack concatenative language. Any thoughts?

     No, because both stacks are passed to and returned from all functions,

    so the composition properties remain the same.

    Now, if you start supporting some of the tricky stuff I advocate

    you'll get the concatenative properties really tied in a knot. But

    that requires explicit abuses of the return stack, and can be easily

    prohibited by a very simple modification to the static typechecker.

    -Billy

## Manfred Von Thun — 2006-07-26 08:55:09

    This is not specific to any particular post on the topic, but it is on

    the topic.

    In Joy you can add as many extra stacks as you like, of even an extra stack

    of stacks. This is because stacks are just lists. In the simplest case,

    consider

    this program skeleton:

    1:     []                             # create an extra stack

    2:     [..] dip                      # do something which ignores the extra

    stack

    3:     [dup] dip  cons          # save the value computed by [..] onto the

    extra stack

    4:     [..] dip                      # do something else which ignores the

    extra stack

    .......                                 # do more, with or without the extra

    stack

    20:   uncons                      # shift the value saved at 3: or elsewhere

    back to main stack

    I have used this technique repeatedly for implementing backtracking in Joy.

    I am sure it can be used for many other purposes, including any you might

    have in mind.

      - Manfred

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