¿Cuáles son las operaciones fundamentales de manipulación de la pila?

8

Estoy creando una máquina virtual orientada a la pila, así que comencé a aprender Forth para una comprensión general sobre cómo funcionaría. Luego seleccioné las operaciones esenciales de manipulación de la pila que necesitaría implementar en mi máquina virtual:

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

Creo que las siguientes cuatro operaciones de manipulación de la pila se pueden utilizar para simular cualquier otra operación de manipulación de la pila. Por ejemplo:

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

Dicho esto, sin embargo, quería saber si he enumerado todas las operaciones fundamentales de manipulación de la pila necesarias para manipular la pila de alguna manera posible.

¿Hay más operaciones fundamentales de manipulación de pila que necesitaría implementar, sin las cuales mi máquina virtual no estaría completa?

virtual-machine operators stack forth factor Aadit M Shah
fuente
3
Puede que también te interese Postcript.
mouviciel
1
¿No son algunas de las alternativas en su segunda lista muy dependientes de la longitud de la pila? Por ejemplo, rot rotcomo una alternativa para -rot? ¿Qué sucede cuando hay más de 3 artículos en la pila? ¿No tendrías que hacerlo rottan a menudo como los Length-1tiempos para lograrlo -rot?
Marjan Venema
Si, de hecho. Por eso acepté la respuesta que @mouviciel proporcionó. En lugar de dup, swapy rotyo uso pick ( a_n ... a_0 n -- a_n ... a_0 a_n)y en su roll ( a_n ... a_0 n i )lugar. Si ies negativo, rolldesplaza los elementos hacia la izquierda; más a la derecha.
Aadit M Shah
En cuanto a la integridad de Turing, puede interesarle. ¿Hay criterios mínimos para que un lenguaje de programación sea completo? del intercambio de Computer Science Stack. CS.SE también podría ser un buen lugar para solicitar las operaciones necesarias para que una máquina de pila se complete.
1
Tenga en cuenta que SWAP se puede implementar con DUP ROT ROT DROP.
Gort the Robot

Respuestas:

5

rollTambién se usan muchos lenguajes basados ​​en la pila , que se generaliza roten un número arbitrario de elementos en la pila. También implementan la operación inversa para girar la pila hacia el otro lado.

Yo diría que rolles más fundamental que rot.

Aunque no tengo respuesta sobre Turingness de esto.

Mouviciel
fuente
sin referencias de algún tipo de memoria arbitraria lo único que tienes es un PDA nota que rollo se va a satisfacer Turing completo si se puede consultar el tamaño de la pila para que pueda acceder elemento arbitrario en la pila
monstruo de trinquete
4

Brent Kirby establece una serie de bases computacionalmente completas de operaciones de apilamiento en su Teoría de los Combinadores Concatenativos . Necesita alguna noción de "cita" de los términos de la pila. Usando su nomenclatura, los siguientes conjuntos de combinadores son todos completos de Turing:

            [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

Usando mi nomenclatura preferida, un conjunto completo conveniente para implementar es:

          A dup == A A
       A B swap == B A
         A drop ==
        A quote == [A]
[A] [B] compose == [A B]
      [A] apply == A
Jon Purdy
fuente