Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
3  
You may be interested in Postcript as well. –  mouviciel Dec 15 '12 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? –  Marjan Venema Dec 15 '12 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. –  Aadit M Shah Dec 15 '12 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. –  MichaelT Feb 22 '13 at 20:41
    
Note that SWAP can be implemented with DUP ROT ROT DROP. –  Steven Burnap Feb 22 '13 at 23:11
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
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 –  ratchet freak Dec 15 '12 at 13:38
add comment

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
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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