Come simulare il flusso di controllo senza utilizzare i primitivi del flusso di controllo

0

Fondamentalmente, voglio sapere come simulare while e if se sto gestendo il flusso di controllo attraverso una serie di istruzioni.

Il ciclo while può essere simulato da if , come visto con il branching di assieme con je e così via. Ma la domanda è: una dichiarazione if può essere simulata in qualche modo, forse simulando un contatore di programma o un puntatore di istruzioni in un ciclo?

Per simulato intendo replicato senza utilizzare direttamente le primitive del flusso di controllo, diverso dal while (true) { ... } loop per scorrere le istruzioni.

Ad esempio:

var pointer = 0

var instructions = [
  doa,
  dob,
  dob2,
  dob3,
  doc,
  dod
]

var a = 1
var b = 2
var c = 3

while (true) {
  var instruction = instructions[pointer]
  instruction()
}

function doa() {
  a = 10
  pointer = 1
}

function dob() {
  doif(a == 10, dob2)
  doif(a != 10, dob3)
}

function dob2() {
  b = 20
  pointer = 4
}

function dob3() {
  b = 2
  pointer = 4
}

function doc() {
  c = 30
  pointer = 5
}

function dod() {
  console.log(a, b, c)
}

function doif(a, b) {
  // How to remove this:
  if (a) b()
}

In fondo c'è un doif . Ti chiedi se esiste un modo per modificare la sua implementazione in modo che non utilizzi la percentuale di% co_de incorporata, come in if . In qualche modo forse aggiunge dinamicamente un'istruzione allo stack, e forse imposta il puntatore delle istruzioni, quindi lo apre in qualche modo. Ma non vedo come farlo senza ricorrere a if (a) b() da qualche parte.

Come già detto, voglio farlo senza usare le primitive del flusso di controllo direttamente. Quindi so che c'è un modo per simulare un'istruzione if , come if , ma voglio evitarlo perché è solo una scorciatoia sintattica. Anche usare un ciclo a && b() come while è la stessa cosa, e così sta usando l'operatore ternario while (a) { b(); break }

Ogni pensiero sarebbe apprezzato. Grazie.

    
posta Lance Pollard 06.07.2018 - 19:59
fonte

3 risposte

3

Stai mescolando due modi di flusso di controllo. Da un lato, stai usando l'array instructions per passare il controllo all'istruzione successiva.

Ma d'altra parte quando scrivi:

function dob() {
  doif(a == 10, dob2)
  doif(a != 10, dob3)
}

Quindi utilizzi il metodo JavaScript che chiama per richiamare doif .

Quindi il nostro primo ordine del giorno è quello di risolvere questo problema. Forse facendo qualcosa di simile

function dob() {
  // note that you need additional structure to support not just method names in instructions, but also arguments
  instructions.push({
    method: doif,
    args: [a == 10, dob2]
  })

  instructions.push({
    method: doif,
    args: [a != 10, dob3]
  })
}

Ma il problema ora è che hai inserito il puntatore del codice nelle istruzioni. Ciò rende più difficile manipolare l'array instructions .

Questo è ciò che vorresti fare:

while (true) {
  var instruction = instructions[pointer] // get current instruction
  instruction.method.apply(instruction.args) // execute it
  pointer++ // increase program counter
}

Potresti anche passare 2a e 3a istruzione, quindi qualunque cosa tu faccia con pointer nell'esecuzione dell'istruzione corrente sarà ciò che sarà definitivo. Nel modo in cui l'ho scritto, basta impostare il puntatore su un valore inferiore a quello che si desidera effettivamente impostare, dal momento che verrà incrementato. Questo non dovrebbe fare molta differenza

Con questo macchinario corretto, la tua doif diventa:

function doif(condition, methodAndArgs) {
  instructions.splice(pointer + 1, 0, methodAndArgs) // insert methodAndArgs after current instruction
  pointer += !condition // if false, add one which makes you jump over the next instruction
}

E dob diventa effettivamente:

function dob() {
  instructions.splice(pointer + 1, 0, {
    method: doif,
    args: [a == 10, {method: dob2, args: []}]
  })

  instructions.splice(pointer + 1, 0, {
    method: doif,
    args: [a != 10, {method: dob3, args: []}]
  })
}

Ecco come sarà il tuo codice completo:

var pointer = 0

var instructions = [
  {method: doa, args: []},
  {method: dob, args: []},
  {method: dob2, args: []},
  {method: dob3, args: []},
  {method: doc, args: []},
  {method: dod, args: []}
]

var a = 1
var b = 2
var c = 3

while (true) {
  var instruction = instructions[pointer]
  instruction.method.apply(instruction.args)
  pointer++
}

function doa() {
  a = 10
}

function dob() {
  instructions.splice(pointer + 1, 0, {
    method: doif,
    args: [a == 10, {method: dob2, args: []}]
  })

  instructions.splice(pointer + 1, 0, {
    method: doif,
    args: [a != 10, {method: dob3, args: []}]
  })
}

function dob2() {
  b = 20
}

function dob3() {
  b = 2
}

function doc() {
  c = 30
}

function dod() {
  console.log(a, b, c)
}

function doif(condition, methodAndArgs) {
  instructions.splice(pointer + 1, 0, methodAndArgs)
  pointer += !condition // if false, add one which makes you jump over the next instruction
}
    
risposta data 06.07.2018 - 20:39
fonte
1

Per compilare if / else in qualche tipo di codice operativo, abbiamo bisogno di un'istruzione di salto condizionale e incondizionata.

Assumiamo questo codice:

if (cond()) {
  when_true();
} else {
  when_false();
}
afterwards();

Questo sarebbe stato compilato in opcode come questo:

  ...       ; cond
  jz ELSE   ; if condition is false, jump to the label
  ...       ; when_true
  jmp END
ELSE:
  ...       ; when_false
END:
  ...       ; afterwards

A seconda dell'insieme di istruzioni, i salti potrebbero avere una posizione assoluta o potrebbero essere relativi alla posizione corrente del puntatore di istruzioni. In entrambi i casi, la posizione non è ancora nota quando viene scritta l'istruzione di salto. Questo può essere risolto con un approccio a due passaggi:

  • Nel primo passaggio emettiamo le istruzioni. I bersagli di salto sono lasciati vuoti. Quando incontriamo un'etichetta, memorizziamo la posizione dell'etichetta in un dizionario.
  • Nel secondo passaggio visitiamo tutte le istruzioni di salto. Ora le posizioni delle etichette sono note, quindi possiamo riscrivere le istruzioni per utilizzare la posizione di destinazione corretta.

Un buon esempio di alto livello di questo è nella generazione bytecode nel codice sorgente CPython .

Quando si scrive un interprete, non è necessario mantenere le istruzioni corrette e semplici. In linea di massima possiamo usare un oggetto arbitrario come opcode. Ciò significa che potremmo mantenere una pila di codici operativi. Ad ogni passo di valutazione, compiamo una istruzione e la interpretiamo. Alcune istruzioni possono spingere nuovi opcode sullo stack. Un nativo se / allora / else potrebbe essere una tale istruzione. Dovrebbe quindi contenere una serie di istruzioni per entrambi i casi quando la condizione è vera o falsa. A seconda del risultato della condizione, spingerà uno o l'altro array sullo stack di istruzioni.

Questi tipi di opcode non sono tuttavia molto comuni:

  • La macchina SECD è una macchina virtuale astratta destinata alle dimostrazioni su programmi di calcolo lambda. Utilizza 4 stack: dati, ambiente (variabili, necessari per le chiusure), controllo (opcode) e continuazioni (necessari per determinati flussi di controllo). In questa codifica non ci sono salti, invece un condizionale decide quale funzione chiamare. Una chiamata di funzione sostituisce lo stack di controllo con il contenuto della funzione.
  • La macchina virtuale Perl utilizza un grafico opcode (quindi gli opcode condizionali puntano su altri opcode che verranno eseguiti in caso di risultato vero / falso). Tuttavia, questo grafico opcode non viene modificato in fase di runtime.
  • Le lingue concatenative possono essere interpretate come spingere le operazioni su una pila.
  • Mi piace utilizzare questo modello negli interpreti perché è estremamente semplice da implementare nei linguaggi di alto livello.

Questo è simile allo splicing degli opcode nell'array delle istruzioni come suggerito da Peeyush Kushwaha, ma usando una pila o camminando su un grafo significa che non dobbiamo spostare gli elementi esistenti nell'array delle istruzioni. Nota che i salti relativi o assoluti non hanno senso se le istruzioni sono su una pila o se l'array di istruzioni può essere modificato, così dovrai tenere i frammenti opcode all'interno degli oggetti opcode.

    
risposta data 06.07.2018 - 21:06
fonte
0

Questo è modo fuori dal regno delle applicazioni del mondo reale, ma è venerdì ...

È possibile diramare senza usare JMP se l'architettura del processore tratta il contatore del programma come qualsiasi altro registro generale. Ad esempio, su PDP-11 , puoi creare una tabella contenente gli indirizzi di destinazione, utilizzare un valore in un registro per selezionare uno di questi valori e memorizzarlo nel contatore del programma:

mov TABLE(R0), R7

Questo è un modo abbastanza standard per implementare un'istruzione switch , ma potrebbe anche essere usata per semplici operazioni di test-and-jump (anche se nessuno lo farebbe perché il PDP-11 aveva un completo complemento di test-and- salti).

Diventare un po 'straniero è l'istruzione "47", così chiamata perché il suo valore numerico è 014747:

mov -(R7), -(R7)

Questo utilizza la modalità indiretta del registro pre-decremento: il valore del registro viene decrementato (di 1 o 2, a seconda che si tratti di un'operazione di byte o parola) e quindi l'indirizzo indicato da tale registro viene utilizzato come operando.

Come puoi immaginare, R7 è solo un altro nome per il contatore del programma. Dopo aver letto un'istruzione, normalmente verrà incrementata di 2. Quindi il primo predecrement annulla questo, il che significa che l'istruzione originale è la fonte della mossa. Il secondo pre-decremento imposta il contatore del programma all'indirizzo prima dell'istruzione originale e viene utilizzato come destinazione dello spostamento.

Il che significa che l'istruzione si copia sul successivo indirizzo di memoria inferiore e quindi esegue l'istruzione a quell'indirizzo. Esegui in modo efficace il processore all'indietro, riempiendo la memoria con 014747 finché non cade dal mondo.

    
risposta data 06.07.2018 - 20:33
fonte

Leggi altre domande sui tag