9

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?

5
  • 3
    You may be interested in Postcript as well.
    – mouviciel
    Commented 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? Commented 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. Commented 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
    Commented Feb 22, 2013 at 20:41
  • 1
    Note that SWAP can be implemented with DUP ROT ROT DROP.
    – user53141
    Commented Feb 22, 2013 at 23:11

2 Answers 2

4

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
1
  • After reading the Theory of Concatenative Combinators, I believe that the sets {j', i}, {take, cat, i}, and {cons, sap} are in fact not Turing complete. The set {j', i} is what author calls conservative complete. You can't implement zap (a.k.a. pop or drop) using j' and i. The sets {take, cat, i} and {cons, sap} are even more restrictive. These sets are what the author calls linear complete. You can't implement zap or dup using these sets. Commented Sep 29, 2022 at 4:15
5

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.

1
  • 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 Commented Dec 15, 2012 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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