Which are the fundamental stack manipulation operations?

Question

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?

Answer 1

Brent Kerby 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

Answer 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.