# Which are the fundamental stack manipulation operations?

I'm creating a stack oriented virtual machine, and so I started learning Forth for a general understanding about how it would work. Then I shortlisted the essential stack manipulation operations I would need to implement in my virtual machine:

``````drop ( a -- )
dup  ( a -- a a )
swap ( a b -- b a )
rot  ( a b c -- b c a )
``````

I believe that the following four stack manipulation operations can be used to simulate any other stack manipulation operation. For example:

``````nip  ( a b -- b )       swap drop
-rot ( a b c -- c a b ) rot rot
tuck ( a b -- b a b )   dup -rot
over ( a b -- a b a )   swap tuck
``````

That being said however I wanted to know whether I have listed all the fundamental stack manipulation operations necessary to manipulate the stack in any possible way.

Are there any more fundamental stack manipulation operations I would need to implement, without which my virtual machine wouldn't be Turing complete?

• You may be interested in Postcript as well. Dec 15, 2012 at 9:13
• Aren't some of the alternatives in your second list very dependent on the length of the stack? For example `rot rot` as an alternative for `-rot`? What happens when there are more than 3 items on the stack? Wouldn't you then have to `rot` as often as `Length-1` times to achieve `-rot`? Dec 15, 2012 at 10:05
• Yes, indeed. That's why I accepted the answer @mouviciel provided. Instead of `dup`, `swap` and `rot` I use `pick ( a_n ... a_0 n -- a_n ... a_0 a_n)` and `roll ( a_n ... a_0 n i )` instead. If `i` is negative then `roll` shifts the elements to the left; else to the right. Dec 15, 2012 at 13:48
• As to the Turing completeness - you might be interested in Are there minimum criteria for a programming language being Turing complete? from the Computer Science Stack exchange. CS.SE might also be a good place to ask the operations necessary for a stack machine to be Turing complete.
– user40980
Feb 22, 2013 at 20:41
• Note that SWAP can be implemented with DUP ROT ROT DROP. Feb 22, 2013 at 23:11

Many stack based languages use `roll` as well, which is a generalized `rot` on an arbitrary number of elements in the stack. They also implement the reverse operation for rotating the stack the other way.

I would say that `roll` is more fundamental than `rot`.

• without references of some kind to arbitrary memory the only thing you have is a PDA note that roll will will satisfy turing completeness if you can query the size of the stack so you can access arbitrary element on the stack Dec 15, 2012 at 13:38

Brent Kirby establishes a number of computationally complete bases of stack operations in his Theory of Concatenative Combinators. You need some notion of “quotation” of stack terms. Using his nomenclature, the following sets of combinators are all Turing-complete:

``````            [B] [A] cons == [[B] A]
[B] [A] sip  == [B] A [B]
[B] [A] k    == A

[D] [C] [B] [A] s'   == [[D] C] A [D] B
[B] [A] k    == A

[B] [A] cake == [[B] A] [A [B]]
[B] [A] k    == A

[E] [D] [C] [B] [A] j'   == [[D] A [E] B] [C] B
[A] i    == A

[B] [A] take == [A [B]]
[B] [A] cat  == [B A]
[A] i    == A

[B] [A] cons == [[B] A]
[B] [A] sap  == A B
``````

Using my preferred nomenclature, a convenient complete set to implement is:

``````          A dup == A A
A B swap == B A
A drop ==
A quote == [A]
[A] [B] compose == [A B]
[A] apply == A
``````