Wie erkenne ich Tail-Calls?

[sproksch]

Wir sitzen hier gerade in unserer Lerngruppe und diskutieren wild, wie genau man nun einen Tail-Call erkennen kann. Insbesondere geht es um das Kapitel "Continuations" (S. 71/72). Warum ist das erstere ein Tail-Call, das zweitere aber nicht?

[marlic]

Naja, da wir CPS machen, sind es letztendlich natürlich alles Tail Calls.

Allerdings wäre der If Fall auch ohne CPS ein Tail Call, add allerdings nicht. Das wiederum erkennt man, da der Reciever bei If nicht erweitert wird.

Ich hoffe das hat euch weitergeholfen.

Im allgemeinen erkennt man Tail Calls daran, dass im Kontrollfluss nach dem Aufruf des Callees, keine weiteren Berechnungen im Caller stattfinden, so dass der Rückgabewert des Callees direkt auch vom Caller zurückgegeben werden kann.

[BastiS]

Wie ist dann sowas in dem Kontext zu sehen?

Code: Alles auswählen

(define (length l k) 
  (if (empty? l)
      (k 0)
      (length (rest l) (lambda (n) (k (+ 1 n))))))

Ist CPS, aber der Receiver wird erweitert. Oder?

[oggy]

Diese Funktion ist folglich auch nicht tail-recursive, folgend
eine Version, die tail-recursive ist. Der Counter wird explizit als
Parameter mitgegeben, anstatt implizit einen Rückgabewert zu
benutzen.

Code: Alles auswählen

(define (length/trk l c k) 
  (if (empty? l)
      (k c)
      (length/trk (rest l) (+ 1 c) k)))

Da k nicht erweitert wird, braucht man diesen Parameter auch nicht:

Code: Alles auswählen

(define (length/tr l c) 
  (if (empty? l)
      c
      (length/tr (rest l) (+ 1 c))))

Aufrufen würde man das ganze dann so:

Code: Alles auswählen

(length/trk '(1 2 3 4 5) 0 (lambda (v) v))
(length/tr '(1 2 3 4 5) 0)

[BastiS]

Danke auch für deine Antwort.
Ist die erste von dir vorgestellte Version dann die, die hieraus resultieren könnte (continuations, slide 73) :

Any program can be automatically transformed to a CPS
version that only contains tail calls.

?
Die zweite kann es ja nicht mehr sein, da dies keine Continuation mehr besitzt.

Noch eine weitere Frage hierzu: Was heißt denn überhaupt "augment the Receiver" bzw. "erweitern des Receivers"? Ist ein Call wie (foo value (lambda (n) (bar k))) schon ein Erweitern oder erst (foo value (k anothervalue))? (k ist die Continuation)

[oggy]

Mhhh, also wenn ich das richtig verstanden habe entspricht

Code: Alles auswählen

(define (length l k) 
  (if (empty? l)
      (k 0)
      (length (rest l) (lambda (n) (k (+ 1 n))))))

Einer "normalen" Funktion ohne Tail Call. D.h. würde man die Funktion ohne Continuation schreiben, dann
wäre sie eine ohne Tail Call (Die Version mit Continuation ist natürlich mit Tail Call).
Die "nicht-CPS" Version würde dann z.B. so aussehen:

Code: Alles auswählen

(define (length l) 
  (if (empty? l)
      (k 0)
      (+ (length (rest l)))))

Und die enthält dann wir leicht zu sehen keinen Tail Call.
Es ging also nur darum zu zeigen wie man einen Tail Call in einer Funktion ohne Continuation in einer Version
der gleichen Funktion mit Continuation erkennt. Grundsätzlich nutzen CPS Funktionsaufrufe immer Tail Calls, sonst würde der Stack recht schnell überlaufen.
Ein Tail Call entspricht also einer unveränderten Weitergabe von k, dieser Aufruf selbst sollte dann auch ein Tail Call
sein.
Wir k augmentiert, also beispielsweise als Paramter (k x) weitergegeben, dann entspricht das einem "Nicht-Tail-Call" in einer
"Nicht-CPS" Funktion, der Aufruf selber ist aber natürlich - weil CPS - ein Tail Call.

Ich hoffe ich habe das korrekt verstanden und halbwegs verständlich erklären können.

[Aaron]

Also ich hätte (nach wie vor) Folgendes gesagt, was meint Ihr dazu:

Folie 71:

Code: Alles auswählen

(define interp expr env k
 ...
  [if0 (test then else) 
     (interp test env    ; 1. kein TC, da nicht k, sondern ein erweiterter Receiver ("(lambda (tv) ...") übergeben wird
       (lambda (tv)
         (if (num-zero? tv)
             (interp then env k )   ; 2. TC, da k übergeben wird
             (interp else env k ))))]   ; 3. TC, da k übergeben wird
...)
(define interp expr env
 ...
  [if0 (test then else) 
      (if (isZero (interp test env))   ; 1. interp kein TC, da mit dem Ergebnis weiter gerechnet wird (durch if)  (siehe Definition "Tail Call Informally" auf Folie 8)
             (interp then env)   ; 2. TC, da Ergebnis von interp = Ergebnis von if0  (angenommen, "if0" wäre die betrachtete aufrufende Funktion, auf Folie 8 "f" genannt)
             (interp else env))]  ; 3. wie 2.
...)

Folie 72:

Code: Alles auswählen

[add(l r) 
   (interp l env (lambda (lv)   ; 4. kein TC
                   (interp r env (lambda (rv)   ; 5. wie 4.
                                   (k (num+ lv rv))))))]   ; 6. TC! num+ ist nicht in CPS geschrieben (sonst hätte es einen receiver-Parameter "k") aber das macht keinen Unterschied: egal, ob man (k (f x)) oder (f x k) hat, in *beiden* Fällen wird zuerst (f x) berechnet und k mit dem Ergebnis aufgerufen: (k (f x))

[add(l r) 
   (num+    ; 6. TC, da Ergebnis von num+ = Ergebnis von add
      (interp l env)   ; 4. kein TC, da num+ noch mit dem Ergebnis von interp ausgeführt werden muss
      (interp r env)]   ; 5. wie 4.

[sewe]

@oggy: Folgendes ist etwas missverständlich:

Ein Tail Call entspricht also einer unveränderten Weitergabe von k, dieser Aufruf selbst sollte dann auch ein Tail Call
sein. Wir k augmentiert, also beispielsweise als Paramter (k x) weitergegeben, dann entspricht das einem "Nicht-Tail-Call" in einer "Nicht-CPS" Funktion, der Aufruf selber ist aber natürlich - weil CPS - ein Tail Call.

Egal ob ich im CPS das Original k oder eine augmentierte Version als Continuation weitergeben, ist der Aufruf (oder sollte es sein, wenn die CPS-Transformation korrekt angewandt wurde) ein Tail-Call. Am Augmentieren kann man allerdings, wie du richtig klarzumachen versuchst, erkennen, ob der Aufruf vor der CPS-Transformation bereits ein Tail-Call war: dies ist dann der Fall, wenn k nicht augmentiert wird.