Torna alla chiamata di livello superiore di una funzione ricorsiva in Lisp

Question

Ho una funzione ricorsiva che deve recurse fino a quando non trova un determinato risultato. Tuttavia nel corpo della mia funzione dopo la mia prima chiamata ricorsiva potrei fare altri calcoli o eventualmente ricorrere nuovamente. Ma se ricevo e trovo il risultato che sto cercando, mi piacerebbe semplicemente fermarmi da qualsiasi ricorsivo che stavo facendo e restituire quel risultato per evitare di fare calcoli inutili.

In una normale chiamata ricorsiva una volta raggiunto il "caso base" che viene restituito alla funzione che ha chiamato, viene restituito a quello che lo ha chiamato e così via. Mi piacerebbe sapere come tornare alla prima volta in cui è stata chiamata la funzione e non dover restituire qualcosa per tutti quei passaggi intermedi.

Per il mio ricorsione base che potrebbe scrivere una funzione come questa:

(defun recurse (x) 
    (if (= x 10) 
     (return-from recurse x) 
     (progn (recurse (+ x 1)) (print "Recursed!"))))) 
(recurse 1) 

E 'stato scritto per illustrare quello che voglio dire circa la funzione che esegue più calcoli dopo una chiamata ricorsiva. E, come scritto, questo non restituisce nemmeno il valore a cui sono interessato poiché faccio delle stampe dopo che ho restituito il valore a cui tengo. (Nota: il comando return-from è estraneo qui poichè potrei semplicemente scrivere "x" al suo posto. È lì solo per tracciare paralleli quando cerco di tornare alla ricorsione di primo livello nel mio secondo esempio qui sotto.)

Ora, se voglio abbandonare tutti quelli extra "Riscatto!" printings Potrei racchiudere tutto in un blocco e poi tornare a quel blocco invece:

EDIT: Ecco un wrapper di funzioni per il mio esempio originale. Questo esempio dovrebbe essere più chiaro ora.

(defun recurse-to-top (start) 
    (block top-level 
    (labels ((recurse (x) 
       (if (= x 10) 
        (return-from top-level x) 
        (progn (recurse (+ x 1)) (print "Recursed!"))))) 
     (recurse start)))) 

E l'esecuzione di questo blocco continua ad andare fino a 10 "si trova" e poi torna a dal blocco di livello superiore senza stampa estranei, proprio come volevo. Ma questo sembra un modo davvero goffo per ottenere questa funzionalità. Mi piacerebbe sapere se esiste un modo standard o "migliore" per ottenere questo tipo di comportamento.

Answer 1

DEFUN fissa già un blocco lessicale:

(defun recurse (start) 
    (labels ((recurse-aux (x) 
      (case x 
       (10 (return-from recurse x)) 
       (15 x) 
       (otherwise 
       (recurse-aux (+ x 1)) 
       (print "Recursed!"))))) 
    (recurse-aux start))) 

anziani è l'uso di CATCH e THROW, che è un costrutto più dinamico e quindi permette un uscita attraverso le funzioni:

(defun recurse (start) 
    (catch 'recurse-exit 
    (recurse-aux start))) 

(defun recurse-aux (x) 
    (case x 
    (10 (throw 'recurse-exit x)) 
    (15 x) 
    (otherwise 
    (recurse-aux (+ x 1)) 
    (print "Recursed!"))))) 
     (recurse-aux start)))) 

Come accennato da Lars, ci sono ancora più modi per programmare il flusso di controllo in questo modo.

Answer 2

Si desidera una specie di uscita non locale. Ci sono alcune scelte: return-from, go, throw, signal.

Forse qualche variazione su questo?

(defun recurse (x &optional (tag 'done)) 
    (catch tag 
    (when (= x 10) 
     (throw 'done x)) 
    (recurse (1+ x) nil) 
    (print "Cursed!"))) 

Credo che fa ciò che si vuole, anche se ci può essere un sacco di inutile cattura in corso.

Come sempre con Lisp, puoi immaginare che esiste un linguaggio perfetto per il tuo problema e scrivere il tuo programma in quella lingua. Per esempio. qualcosa come

(defun recurse (x) 
    (top-level-block recurse 
    (when (= x 10) 
     (return-from-top-level recurse x)) 
    (recurse (1+ x)) 
    (print "Cursed!"))) 

Poi c'è solo una semplice questione di programmazioneper attuare le nuove macro top-level-block e return-from-top-level.

codice di esempio imperfetto segue:

(defmacro top-level-block (name &body body) 
    `(if (boundp ',name) 
     (progn ,@body) 
     (catch ',name 
     (let ((,name t)) 
      (declare (special ,name)) 
      ,@body)))) 

(defmacro return-from-top-level (name value) 
    `(throw ',name ,value))