Come implementare la valutazione lazy di if ()

10

Attualmente sto implementando un valutatore di espressioni (espressioni a linea singola, come le formule) in base a quanto segue:

  • l'espressione inserita viene tokenizzata per separare booleani letterali, interi, decimali, stringhe, funzioni, identificatori (variabili)
  • Ho implementato l'algoritmo Shunting-yard (leggermente modificato per gestire le funzioni con un numero variabile di argomenti) per sbarazzarsi delle parentesi e ordinare agli operatori una precedenza decente in un ordine postfixed
  • il mio shunting-yard produce semplicemente una coda (simulata) di token (per mezzo di un array, il mio linguaggio Powerbuilder Classic può definire oggetti, ma ha solo array dinamici come memoria nativa - non vero elenco, nessun dizionario) che valuto sequenzialmente con una semplice macchina stack

Il mio valutatore funziona correttamente, ma mi manca ancora if() e mi chiedo come procedere.

Con il mio shunting-yard valutazione postfixed e stack based, se aggiungo if() come un'altra funzione con parti true e false, un singolo if(true, msgbox("ok"), msgbox("not ok")) mostrerà entrambi i messaggi mentre vorrei mostrarne solo uno. Questo perché quando ho bisogno di valutare una funzione, tutti i suoi argomenti sono già stati valutati e messi nello stack.

Potresti darmi un modo per implementare if() in modo pigro?

Ho pensato di elaborarli come una specie di macro, ma all'inizio non ho ancora valutato la condizione. Forse ho bisogno di usare un altro tipo di struttura rispetto a una coda per tenere separatamente la condizione e le espressioni vero / falso? Per ora l'espressione viene analizzata prima della valutazione, ma ho anche intenzione di memorizzare la rappresentazione intermedia come tipo di espressione precompilata per la valutazione futura.

Modifica : dopo un po 'sul problema, penso che potrei costruire una rappresentazione ad albero della mia espressione (un AST invece di un flusso di token lineare), da cui potrei facilmente ignorare l'uno o l'altro ramo del mio if() .

    
posta Seki 14.03.2013 - 17:08
fonte

3 risposte

9

Ci sono due opzioni qui.

1) Non implementare if come una funzione. Rendilo un linguaggio con la semantica speciale. Facile da fare, ma meno "puro" se vuoi che tutto sia una funzione.

2) Implementa la semantica "call by name", che è molto più complicata, ma consente al compilatore magico di occuparsi del problema della valutazione pigra mantenendo al tempo if come funzione invece di un elemento linguaggio. Funziona così:

if è una funzione che accetta due parametri, entrambi dichiarati come "per nome". Quando il compilatore vede che sta passando qualcosa a un parametro by-name, cambia il codice da generare. Invece di valutare l'espressione e passare il valore, crea una chiusura che valuta l'espressione e passa invece quella. E quando si richiama un parametro by-name all'interno della funzione, il compilatore genera il codice per valutare la chiusura.

    
risposta data 14.03.2013 - 17:25
fonte
3

Piuttosto che la funzione con la firma:

object if(bool, object, object)

Dagli la firma:

object if(bool, object function(), object function())

Quindi la tua funzione if chiamerà la funzione appropriata in base alla condizione, valutando solo una di esse.

    
risposta data 14.03.2013 - 23:37
fonte
1

È abbastanza facile, se si compila tutto pigramente. Devi avere alcuni mezzi per vedere se un valore è già valutato, o se ha bisogno di più evasione.

Quindi puoi fare quanto segue: Se è un letterale o una variabile (hai quelli ?, ovvero i nomi delle funzioni?), spingila in pila. Se si tratta di un'applicazione di una funzione, compila separatamente e spinge il punto di ingresso nello stack.

L'esecuzione di un programma è, quindi, semplicemente un loop fino a quando non viene valutata la parte superiore dello stack e non una funzione. Se non viene valutato o una funzione, chiama il codice in cima alla pila.

    
risposta data 14.03.2013 - 19:09
fonte

Leggi altre domande sui tag