Quali sono le operazioni fondamentali di manipolazione dello stack?

Naviga le tue risposte
8

Sto creando una macchina virtuale orientata allo stack e così ho iniziato a imparare Forth per una comprensione generale di come avrebbe funzionato. Quindi ho selezionato le operazioni essenziali di manipolazione dello stack che avrei dovuto implementare nella mia macchina virtuale: 

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

Credo che le seguenti quattro operazioni di manipolazione dello stack possano essere utilizzate per simulare qualsiasi altra operazione di manipolazione dello stack. Ad esempio: 

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

Detto ciò, volevo sapere se ho elencato tutte le operazioni fondamentali di manipolazione dello stack necessarie per manipolare lo stack in qualsiasi modo possibile.

Ci sono altre operazioni fondamentali di manipolazione dello stack che avrei bisogno di implementare, senza le quali la mia macchina virtuale non sarebbe completa con Turing?

    
posta Aadit M Shah 15.12.2012 - 09:22
fonte

2 risposte

5

Molte lingue basate sullo stack usano anche roll , che è un% co_de generalizzato su un numero arbitrario di elementi nello stack. Implementano anche l'operazione inversa per ruotare lo stack nell'altro modo.

Direi che rot è più fondamentale di roll .

Non ho alcuna risposta su Turingness di questo.

    
risposta data 15.12.2012 - 10:10
fonte
4

Brent Kirby stabilisce un numero di basi computazionalmente complete di operazioni stack nella sua teoria dei combinatori concatenanti . Hai bisogno di una nozione di "quotazione" dei termini dello stack. Usando la sua nomenclatura, i seguenti gruppi di combinatori sono tutti completi di 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 la mia nomenclatura preferita, un comodo set completo da implementare è: 

          A dup == A A
       A B swap == B A
         A drop ==
        A quote == [A]
[A] [B] compose == [A B]
      [A] apply == A
    
risposta data 22.02.2013 - 23:03
fonte

Leggi altre domande sui tag

Basso accoppiamento che elabora grandi quantità di dati In che modo le strutture di controllo originali di Fortran erano insufficienti?