Overhead di call-by-name/call-by-name Strategia dell'interprete Lisp

Question

Ho un interprete parzialmente finito per un "Lisp puro" con lessicità (no set!) che utilizza un modello di valutazione call-by-need che viene fornito giù per chiamare con il semplice caching, l'interprete utilizza naturalmente un modello di valutazione basato sull'ambiente.

Il modo standard di valutare le astrazioni lambda, come in, la costruzione di un nuovo ambiente dai parametri formali e l'ambiente in cui viene valutata l'astrazione e semplicemente ponendo le valutazioni degli argomenti nel proprio ambiente in esso. Quindi valutare il corpo dell'astrazione nel nuovo ambiente non funzionerebbe perché significherebbe una semantica call-by-value.

La mia soluzione a questo problema stava sostituendo dove richiesto l'idea di "ambienti" con "funzioni di ricerca", che prendevano semplicemente un simbolo come argomento e producono un dato associato. Che può essere facilmente creato da un ambiente. Le Lambda-applicazioni sono fatte semplicemente valutando di nuovo il corpo con una funzione di ricerca che è fatta sia dall'ambiente in cui si trova la definizione, sia dal punto in cui si trova l'argomento. Che li valuta pigramente e solo quando richiesto.

Quello che mi chiedo è quale sia l'overhead di questo modello, quanto è costoso generare queste ricerche per ogni applicazione, il codice per queste ricerche è piuttosto grande. So che l'applicazione lambda e la creazione in Scheme sono abbastanza economiche e molte fonti sostengono di utilizzarle estensivamente per mantenere la leggibilità del codice, anche se in molti casi avrebbero un leggero sovraccarico. Ma dal momento che le applicazioni lambda sono onnipresenti in qualsiasi fiaba, mi chiedo quante prestazioni si potrebbero risparmiare dall'usare un modello potenzialmente diverso. Ho provato a cercare questo su google, ma tutti i modelli per gli interpreti call-by-need che ho trovato erano ancora più scomodi, ma spesso così da ospitare per set!.

Alcuni pezzi rilevanti del mio codice:

Il valutatore che utilizza la funzione di ricerca:

; evaluates a datum using a lookup 
; lookup is a function which takes a symbol as an argument and produces the value 
; some sorts of more powerful environment 
; if lookup is a standard environment, treats it as such 
(define (eval-datum! d lookup) 
    (cond 
    ((quoted? d) (dequote d)) ; if quoted, just dequote 
    ((hastype d symbol-type) ; symbols ... 
    (if (procedure? lookup) ; checks if it's an environment or a lookup function 
     (lookup d) 
     (lookup-symbol d lookup))) 
    ((hastype d pair-type) (eval-pair! d lookup)) ; function application 
    (else d))) ; rest is considered self-evaluating 

e la funzione che genera le ricerche più avanzate. Questo è soprattutto ciò che mi preoccupa, anche se è ricorsivo in coda e usa i confronti a buon mercato eq? e null?, non sembra efficiente come semplicemente usando assq in un elenco di ambiente, e alcune volte anche la mancanza di accesso casuale a quelli mi preoccupa un po.

; extends a lookup for use in a lambda abstraction 
; the inner environment is where the lambda is defined 
; the outer environment where it is applied 
; params can be either a pair or a symbol 
; params automatically tries to match the argument's pattern 
(define (extend-lookup! params args inner-env outer-env) 
    (lambda (s) 
    (let checkparams ((params params) (args args)) 
     (cond 
     ((eq? s params) (datum args)) ; for an improper list or a single symbol, simply turn the arglist into an evaluable list 
     ((null? params) (lookup-symbol s inner-env)) ; if the number of paramatres are exhausted, simply use the inner-env 
     ((eq? s (car params)) ; in case of a formal parametre match ... 
       (refeval! args 0 outer-env)) ; evaluate the needed argument and return it 
     (else (checkparams (cdr params) (cdr args))))))) ; repeat for the next paramatre 

Dovrebbe essere evidente che il valutatore funziona con un sistema semplice termine di riduzione che quando la valutazione di espressioni in una lista semplicemente li sostituisce con loro risultato, citando ogni volta il risultato non è considerato autovalutazione. Il che è possibile perché è una lisp puramente funzionale. Cattura anche il caching e la maggior parte della raccolta dei rifiuti in un colpo solo.

Devo aggiungere che una delle cose che ho sempre avuto una concezione molto povera della teoria generale e della complessità. Per quelli che dicono "Se vuoi performance, perché stai facendo il tuo interprete in Lisp?", È solo un test della struttura generale per vedere se funziona, lo scriverò di nuovo in C-- abbastanza presto.

Ah, non potevo nemmeno presentarlo all'inizio perché il tag "call-by-need" non esiste già, promettente inizio.

Answer 1

Un'altra cosa che "tu" potresti fare è semplicemente contrassegnare ogni singolo dato con un ambiente da solo che può essere recuperato da esso nella struttura dati, può sembrare esauriente ma alla fine tutto ciò che deve essere contrassegnato viene pensare che sono liste e un caso molto particolare che il corpo dell'astrazione lambda contiene un solo simbolo.Per altri dati nel tuo modello, la sua valutazione è indipendente dal suo ambiente.

Questo risolve anche un grosso problema con le celle lazy cons e le liste che vengono semplicemente passate ad altri posti nel programma.

Quindi, supponendo che una lista stessa sia contrassegnata da un ambiente, è possibile estrarre l'ambiente ogni volta che lo si valuta.