Valutazione Lisp di dichiarazioni let

Question

Sto scrivendo un interprete Scheme e mi trovo di fronte a una dichiarazione let valida come:

;; should print 7
(let ((a 4) (b 3))
    (let ((a (* a a)) 
          (b (* b b)))
       (+ a b)
       (- a b)))

Il mio interprete implementa solo un sottoinsieme puramente funzionale di Scheme, quindi non ci saranno effetti collaterali come set !. In un linguaggio puramente funzionale, perché dovresti consentire più espressioni all'interno di un'istruzione let come sopra?

E scrivendo il mio interprete, c'è qualche motivo per cui dovrei valutare qualcosa di diverso dall'ultima espressione nel let? Sembra che non possano mai influenzare il risultato dell'ultima dichiarazione valutata.

Answer 1

Hai ragione (quasi): se stai implementando un sottoinsieme puramente funzionale di Scheme (cioè nessun set! , set-car! , set-cdr! ) quindi qualsiasi espressione tranne l'ultima in un let verrà cancellata dal loro valore di ritorno, e dato che sei sicuro di non avere effetti collaterali, non c'è pericolo in silenzio ignorandoli.

Tuttavia, c'è un piccolo caso che devi considerare, e cioè quando le espressioni precedenti sono define s:

(let ((x 3))
  (define y 4)
  (+ x y))

Questo è sia legale che funzionale. Tuttavia, ci sono alcune buone notizie: all'interno di un blocco (come un let ) devi avere tutti i tuoi definisci in alto. Come in, questo non è considerato schema legale:

(let ((x 3))
  (+ 2 3)
  (define y 4)
  (+ x y))

Ciò significa che durante la valutazione di un blocco, tutto ciò che devi fare è scansionare la parte superiore alla ricerca di define e avvolgerli nell'espressione equivalente letrec , quindi procedere a ignora tutto tranne l'ultima espressione (che poi restituiresti).

modifica: antti.huima sottolinea in modo eccellente call / cc. Se hai intenzione di includere continuazioni nella tua implementazione, non puoi davvero fare molte ipotesi su quando verranno valutate le cose.

Answer 2

in realtà non puoi " eliminare " tutti tranne l'ultima affermazione, perché le dichiarazioni precedenti potrebbero essere non terminanti. Ad esempio:

(define (func) (func))

(let ()
  (func) ;; does not return
  1)

Qui se si lascia (func) non valutato, si ottiene il risultato sbagliato (che è 1), mentre si dovrebbe ottenere un calcolo non terminante.

Un altro problema è che call / cc (call-with-current-continuation) (e sì, appartiene al sottoinsieme funzionale) può essere effettivamente utilizzato per restituire dal calcolo da non-tail posizione, ad esempio:

(call-with-current-continuation
  (lambda (ret)
    (let ()
      (ret 3)
      4)))

che restituirà 3 e non 4. Questo è puramente funzionale.

Nota BTW che (let () xyz) è equivalente al modulo a singola istruzione (let () (inizia xyz)) quindi la vera domanda è se tu è necessario inizio :)

Answer 3

Va ??bene, il let sta solo creando un'associazione, come un define . Non c'è nulla lì che sta cambiando una variabile associata come farebbe set! . Quindi ora, pensa a quale sia il ambito dei tuoi nomi: a di '(+ ab) è uguale a a` sei legato a 4? (Suggerimento: no.)

Il vero punto qui è che devi comportarti correttamente anche in casi viziosi come questo: le regole di scoping e binding sono semplici e ben definite e fanno qualcosa del genere, che sembra confuso, è solo una conseguenza di loro. È conveniente, perché avendo associazioni locali con ambito lessicale con let , puoi scrivere programmi più chiari, anche se ci sono casi laterali perversi.

Aggiorna Oh, ho lasciato un punto. Hai ragione sul fatto che l'invocazione (+ ab) non ha alcun effetto duraturo, ma in generale non puoi supporre che sarebbe vero e non puoi determinare se sia vero esaminando il testo del programma lì da solo. (Considera: potrebbero esserci altre funzioni al posto di " + " ;.) Per il resto, però, se pensi di ottenere il risultato corretto senza valutare i vari lascia , non capisci cosa sta ancora cercando di fare.