Quais são as operações fundamentais de manipulação de pilha?

8

Estou criando uma máquina virtual orientada a pilha e, então, comecei a aprender a Forth para uma compreensão geral sobre como ela funcionaria. Em seguida, selecionei as operações essenciais de manipulação de pilha que precisaria implementar na minha máquina virtual:

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

Acredito que as quatro operações de manipulação de pilha a seguir possam ser usadas para simular qualquer outra operação de manipulação de pilha. Por exemplo:

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

Dito isto, porém, eu queria saber se listei todas as operações fundamentais de manipulação de pilha necessárias para manipular a pilha de qualquer maneira possível.

Existem operações de manipulação de pilha mais fundamentais que eu precisaria implementar, sem as quais minha máquina virtual não estaria completa com Turing?

virtual-machine operators stack forth factor Aadit M Shah
fonte
3
Você também pode estar interessado em Postcript.
Mouviciel
1
Algumas das alternativas da sua segunda lista não dependem muito do comprimento da pilha? Por exemplo, rot rotcomo uma alternativa para -rot? O que acontece quando há mais de 3 itens na pilha? Você não precisaria rottantas Length-1vezes quantas vezes conseguir -rot?
Marjan Venema
Sim, de fato. Foi por isso que aceitei a resposta @mouviciel fornecida. Em vez de dup, swape roteu uso pick ( a_n ... a_0 n -- a_n ... a_0 a_n)e em roll ( a_n ... a_0 n i )vez disso. Se ifor negativo, rolldesloca os elementos para a esquerda; mais para a direita.
Aadit M Shah
Quanto à integridade de Turing - você pode estar interessado em: Existem critérios mínimos para uma linguagem de programação ser Turing completa? da troca de pilha de ciência da computação. O CS.SE também pode ser um bom lugar para solicitar as operações necessárias para que uma máquina de empilhar seja Turing completa.
1
Observe que o SWAP pode ser implementado com o DUP ROT ROT DROP.
Gort the Robot

Respostas:

5

Muitas linguagens baseadas em pilha também usam roll, o que é generalizado rotem um número arbitrário de elementos na pilha. Eles também implementam a operação reversa para girar a pilha para o outro lado.

Eu diria que rollé mais fundamental que rot.

Ainda não tenho resposta sobre Turingness disso.

mouviciel
fonte
sem referências de algum tipo de memória arbitrária a única coisa que você tem é um PDA nota o rolo vai irá satisfazer Turing completude se você pode consultar o tamanho da pilha para que você possa acessar elemento arbitrário na pilha
aberração catraca
4

Brent Kirby estabelece uma série de bases computacionais completas de operações de pilha em sua Teoria dos combinadores concatenativos . Você precisa de alguma noção de "cotação" dos termos da pilha. Usando sua nomenclatura, os seguintes conjuntos de combinadores são 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 minha nomenclatura preferida, um conjunto completo conveniente para implementar é:

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