Tail Calls

Lamora
Neuling
Neuling
Beiträge: 5
Registriert: 21. Jun 2013 17:33

Tail Calls

Beitrag von Lamora »

Hello,

I have at least 1.000 questions about this course so I am taking the courage to post one of them here:

V6.pdf / slide 127 : Ok, clearly stated that when we augment the receiver it is not a tail call.
V6.pdf / slide 35 : Is this a tail call? The answer seems (to me) to be it is not, since we augment the receiver.

But are not tail calls what triggered our discussion of CPS? What am I missing here?

Thanks in advance

Matt
Erstie
Erstie
Beiträge: 18
Registriert: 20. Dez 2011 19:22

Re: Tail Calls

Beitrag von Matt »

Lamora hat geschrieben: V6.pdf / slide 35 : Is this a tail call?
Yes, it is. There is nothing left to do after the call. If n is equal to 0 you just call r and then do nothing else so it's a tail call. If n isn't 0 you just call factCPS and then do nothing else so it's a tail call.

Lamora
Neuling
Neuling
Beiträge: 5
Registriert: 21. Jun 2013 17:33

Re: Tail Calls

Beitrag von Lamora »

Hello Matt,

thank you for your answer. Pardon my dullness of mind though as I have to insist again on this thing
about augmented receivers. Why are the receivers on slides 103 and 127 augmented but the
receiver on 35 is not? The way I get it, from my very limited understanding, is that the only way
not to augment a receiver (and thus allow a tail call according to slide 127) is to pass an
argument like r(value) and not something like value => r (value) .
Am I wrong in this assumption?

Thanks

f_jakob
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 27. Okt 2009 14:05

Re: Tail Calls

Beitrag von f_jakob »

Hi Lamora,

the receivers on slides 103 and 127 are augmented, because the function in tail call position interp is again called inside the receiver.

On slide 35 the function in tail call position factCPS is not used inside the receiver, that is why it is not augmented.

At least this is my understanding to the term augmented in the slides.

You can check if a function can be tail-call optimized (and thus all recursive calls are in tail position) by using the Scala @tailrec annotation. Check out the first part of this article for a few more examples on tail calls and tail call optimization.

Lamora
Neuling
Neuling
Beiträge: 5
Registriert: 21. Jun 2013 17:33

Re: Tail Calls

Beitrag von Lamora »

Hello f_jakob,

Thank you for you answer. Being a bit slow, it is hard for me to wrap my mind around these concepts.
I thought about your answer, so now let's take a look at WebLab / Exercise 9 / Task 1 / Fibonacci Sample Solution

def fibCPS(n: Int, k: Int => Int): Int =
n match {
case 0 | 1 => k(1)
case _ => fibCPS(n - 1, { n_1 =>
fibCPS(n - 2, { n_2 =>
k(n_1 + n_2) })})

Is this not a similar use to slide 103 ? Thus, an augmented receiver and the calls not tail calls?
Yet above the exercise is this "This implies that every call has to be a tail-call."
What am I missing?

Thanks in advance

f_jakob
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 27. Okt 2009 14:05

Re: Tail Calls

Beitrag von f_jakob »

A call is a tail call, if it is in tail position of a function. So you have to look at the call in relation to a function.

So in the given example, k(1) is a tail call in fibCPS and fibCPS(n - 1, …) is a tail call in fibCPS. But fibCPS(n - 2, …) is not a tail call in fibCPS, yet still a tail call in the continuation passed to the call to fibCPS(n - 1).

Because there is a call to fibCPS, which is not in tail position in fibCPS, fibCPS is not tail recursive and thus can not be optimized for tail recursion (using the @tailrec).

My understanding of the term augmented in the lecture is, that it refers to functions, which have a recursive call in tail position (that is not a tail recursive call) in one of the continuations inside that function definition.

So in the example, all calls are tail calls, but fibCPS is augmented, because it has a recursive call in tail position in one of the continuations (fibCPS(n - 2, …)).

Antworten

Zurück zu „Archiv“