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?

  • 3
    You may be interested in Postcript as well.
    – mouviciel
    Dec 15, 2012 at 9:13
  • 1
    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
  • 1
    Note that SWAP can be implemented with DUP ROT ROT DROP. Feb 22, 2013 at 23:11

2 Answers 2


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.

I have no answer though about Turingness of this.

  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.