Ist dies eine generische Methode, um eine rekursive Prozedur in eine Schwanzrekursion umzuwandeln?

13

Es scheint , dass ich einen generellen Weg gefunden zu konvertieren jede rekursive Prozedur bis zum Schwanz-Rekursion:

  1. Definieren Sie eine Hilfsteilprozedur mit einem zusätzlichen "Ergebnis" -Parameter.
  2. Wenden Sie auf diesen Parameter an, was auf den Rückgabewert der Prozedur angewendet wird.
  3. Rufen Sie diese Hilfsprozedur auf, um loszulegen. Der Anfangswert für den Parameter "result" ist der Wert für den Austrittspunkt des rekursiven Prozesses, sodass der resultierende iterative Prozess dort beginnt, wo der rekursive Prozess zu schrumpfen beginnt.

Hier ist zum Beispiel die ursprüngliche rekursive Prozedur, die konvertiert werden soll ( SICP-Übung 1.17 ):

(define (fast-multiply a b)
  (define (double num)
    (* num 2))
  (define (half num)
    (/ num 2))
  (cond ((= b 0) 0)
        ((even? b) (double (fast-multiply a (half b))))
        (else (+ (fast-multiply a (- b 1)) a))))

Hier ist die konvertierte, endrekursive Prozedur ( SICP-Übung 1.18 ):

(define (fast-multiply a b)
  (define (double n)
    (* n 2))
  (define (half n)
    (/ n 2))
  (define (multi-iter a b product)
    (cond ((= b 0) product)
          ((even? b) (multi-iter a (half b) (double product)))
          (else (multi-iter a (- b 1) (+ product a)))))
  (multi-iter a b 0))

Kann jemand dies beweisen oder widerlegen?

nalzok
quelle
1
Ö(Logn)
Zweiter Gedanke: bEine Potenz von 2 zu wählen, zeigt, dass die anfängliche Einstellung productauf 0 nicht ganz richtig ist. Aber wenn bes ungerade ist, funktioniert es nicht, es auf 1 zu setzen . Benötigen Sie 2 verschiedene Speicherparameter?
j_random_hacker
3
Sie haben eine Transformation einer rekursiven Non-Tail-Definition nicht wirklich definiert. Das Hinzufügen eines Ergebnisparameters und dessen Verwendung für die Akkumulation ist ziemlich vage und lässt sich kaum auf komplexere Fälle verallgemeinern, z. B. Baumdurchquerungen, in denen Sie zwei rekursive Aufrufe haben. Es gibt jedoch eine genauere Vorstellung von "Fortsetzung", bei der Sie einen Teil der Arbeit erledigen und anschließend einer "Fortsetzung" -Funktion die Übernahme der bisher geleisteten Arbeit als Parameter erlauben. Es heißt Continuation Passing Style (cps), siehe en.wikipedia.org/wiki/Continuation-passing_style .
Ariel,
4
Diese Folien fsl.cs.illinois.edu/images/d/d5/CS422-Fall-2006-13.pdf enthalten eine Beschreibung der cps-Transformation, in der Sie einen beliebigen Ausdruck verwenden (möglicherweise mit Funktionsdefinitionen mit Nicht-Tail-Aufrufen). und transformiere es in einen äquivalenten Ausdruck mit nur Tail Calls.
Ariel,
@j_random_hacker Ja, ich kann sehen, dass mein "konvertiertes" Verfahren tatsächlich falsch ist ...
nalzok

Antworten:

12

Ihre Beschreibung Ihres Algorithmus ist zu vage, um sie an dieser Stelle zu bewerten. Aber hier sind einige Dinge zu beachten.

CPS

Tatsächlich gibt es eine Möglichkeit, jeden Code in ein Formular umzuwandeln , das nur Tail-Calls verwendet. Dies ist die CPS-Transformation. CPS ( Continuation-Passing Style ) ist eine Form, Code auszudrücken, indem jeder Funktion eine Fortsetzung übergeben wird. Eine Fortsetzung ist ein abstrakter Begriff, der "den Rest einer Berechnung" darstellt. In Code in CPS Form ausgedrückt, die auf natürliche Weise reify eine Fortsetzung ist als eine Funktion , die einen Wert annimmt. In CPS wird statt einer Funktion, die einen Wert zurückgibt, die Funktion angewendet, die die aktuelle Fortsetzung darstellt, um von der Funktion "zurückgegeben" zu werden.

Betrachten Sie beispielsweise die folgende Funktion:

(lambda (a b c d)
  (+ (- a b) (* c d)))

Dies könnte in CPS wie folgt ausgedrückt werden:

(lambda (k a b c d)
  (- (lambda (v1)
       (* (lambda (v2)
            (+ k v1 v2))
          a b))
     c d))

Es ist hässlich und oft langsam, hat aber einige Vorteile:

  • Die Transformation kann vollständig automatisiert werden. Sie müssen den Code also nicht in CPS-Form schreiben (oder anzeigen).
  • In Kombination mit Thunking und Trampolining kann die Tail-Call-Optimierung in Sprachen durchgeführt werden, die keine Tail-Call-Optimierung bieten. (Die Optimierung von direkt rekursiven Funktionen für den Endanruf kann auch auf andere Weise erfolgen, z. B. durch Konvertieren des rekursiven Aufrufs in eine Schleife. Indirekte Rekursion ist jedoch auf diese Weise nicht so einfach zu konvertieren.)
  • Mit CPS werden Fortsetzungen zu erstklassigen Objekten. Da Fortsetzungen das Wesentliche der Steuerung sind, kann praktisch jeder Steuerungsoperator als Bibliothek implementiert werden, ohne dass eine spezielle Unterstützung durch die Sprache erforderlich ist. Zum Beispiel können Goto, Ausnahmen und kooperatives Threading mithilfe von Fortsetzungen modelliert werden.

TCO

Es scheint mir, dass der einzige Grund, sich mit Tail-Recursion (oder Tail-Calls im Allgemeinen) zu befassen, die Tail-Call-Optimierung (TCO) ist. Ich denke also, eine bessere Frage zu stellen ist: "Ist mein Transformationsertragcode für Tail-Calls optimierbar?".

Wenn wir noch einmal CPS betrachten, ist eine seiner Eigenschaften, dass der in CPS ausgedrückte Code nur aus Tail-Calls besteht. Da es sich bei allem um einen Tail-Call handelt, müssen wir keinen Rücksprungpunkt auf dem Stack speichern. Also alle Code in CPS Form muss Tail-Call - optimiert sein, nicht wahr?

Nicht ganz. Sie sehen, obwohl es den Anschein hat, als hätten wir den Stapel entfernt, haben wir lediglich die Art und Weise geändert, wie wir ihn darstellen. Der Stapel ist nun Teil des Verschlusses, der eine Fortsetzung darstellt. CPS optimiert also nicht auf magische Weise alle unsere Code-Tail-Calls.

Also, wenn CPS nicht alle TCO machen kann, gibt es eine Transformation speziell für die direkte Rekursion, die das kann? Nein, im Allgemeinen nicht. Einige Rekursionen sind linear, andere nicht. Nichtlineare (z. B. Baum-) Rekursionen müssen einfach irgendwo eine variable Zustandsgröße beibehalten.

Nathan Davis
quelle
Es ist ein bisschen verwirrend, wenn Sie im Unterabschnitt " TCO " "Tail-Call-optimiert" sagen, meinen Sie tatsächlich "mit konstanter Speichernutzung". Dass die dynamische Speichernutzung nicht konstant ist, negiert noch nicht die Tatsache, dass die Aufrufe tatsächlich schwächer sind und die Stack- Nutzung nicht unbegrenzt zunimmt. SICP nennt solche Berechnungen "iterativ", weshalb es (für mich) eine bessere Formulierung gewesen sein könnte, zu sagen, "obwohl es sich um TCO handelt, wird es immer noch nicht iterativ gemacht".
Will Ness
@WillNess Wir haben immer noch einen Call-Stack, er ist nur anders dargestellt. Die Struktur ändert sich nicht, nur weil wir den Heap und nicht den Hardware- Stack verwenden. Immerhin gibt es viele Datenstrukturen, die auf dynamischem Heap-Speicher basieren und deren Name "Stack" enthält.
Nathan Davis
Der einzige Punkt hierbei ist, dass einige Sprachen die Verwendung des Aufrufstapels fest verdrahtet haben.
Will Ness