Powrót do wywołania najwyższego poziomu funkcji rekursywnej w Lisp

Question

Mam funkcję rekursywną, która musi się powtarzać, dopóki nie znajdzie określonego wyniku. Jednak w ciele mojej funkcji po pierwszym rekursywnym wywołaniu mogę wykonać kilka innych obliczeń lub ewentualnie powtórzyć. Ale jeśli powrócę i znajdę wynik, którego szukam, to chciałbym po prostu przerwać rekurencję, którą robiłem i zwrócić ten wynik, aby uniknąć niepotrzebnych obliczeń.

W zwykłym wywołaniu rekurencyjnym, gdy dojdziesz do "przypadku podstawowego", który zostanie zwrócony do funkcji, która wywołała, to zostanie zwrócona do tej, która go nazwała, i tak dalej. Chciałbym wiedzieć, jak powrócić do pierwszego uruchomienia tej funkcji i nie trzeba zwracać czegoś dla wszystkich pośrednich kroków.

Dla mojego podstawowego rekursji mógłbym napisać funkcję tak:

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

Został on napisany w celu zilustrowania tego, co mam na myśli o funkcja działa więcej obliczeń po rekurencyjnego wywołania. I, jak napisano, nie zwraca nawet wartości, którą interesuję, ponieważ wykonuję niektóre wydruki po zwróceniu wartości, na której mi zależy. (Uwaga: Polecenie return-from jest tutaj obce, ponieważ mógłbym po prostu napisać "x" na swoim miejscu, aby tam narysować paralele, gdy próbuję powrócić do rekursji najwyższego poziomu w moim drugim przykładzie poniżej.)

Teraz, jeśli chcę wyrzucić te dodatkowe "Powtórne!" wydruki Mogłem zamknąć wszystko w bloku, a następnie po prostu wrócić do tego bloku:

EDYCJA: Oto otoki funkcji dla mojego oryginalnego przykładu. Ten przykład powinien być teraz bardziej przejrzysty.

(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)))) 

i działa ten blok leci aż 10 „znajduje się”, a następnie powraca do bloku z najwyższego poziomu bez nadruku obcego, tak jak chciałem. Ale wydaje się, że to bardzo chybiony sposób na uzyskanie tej funkcji. Chciałbym wiedzieć, czy istnieje standardowy lub "najlepszy" sposób na uzyskanie tego typu zachowania.

Answer 1

DEFUN już konfiguruje leksykograficznego blok:

(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))) 

starszymi stosowanie CATCH i THROW, który jest bardziej dynamiczny konstruktu i tym samym umożliwia wyjście z funkcji:

(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)))) 

Jak wspomniał Lars, jest jeszcze więcej sposobów na programowanie takiego przepływu sterowania.

Answer 2

Potrzebujesz jakiegoś nielokalnego wyjścia. Istnieje kilka opcji: return-from, go, throw, signal.

Może jakieś odmiany?

Wierzę, że robi to, co chcesz, chociaż może być dużo niepotrzebnego łapania.

Jak zawsze z Lisp, możesz sobie wyobrazić, że istnieje idealny język dla twojego problemu i napisać swój program w tym języku. Na przykład. coś

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

Potem jest tylko prosta sprawa programowania do wdrożenia nowych makr top-level-block i return-from-top-level.

niedoskonałe Kod próbki następująco:

(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))