Tail call optimization (TCO) - Lecture

50 %
50 %
Information about Tail call optimization (TCO) - Lecture

Published on March 6, 2014

Author: JesseFrankley

Source: slideshare.net


Accompanying powerpoint slides for a lecture on tail call optimization given to The Evergreen State College's Computer Science Foundations program.

Tail-call Optimization (TCO)

What is tail-call optimization? A compiler optimization that allows the efficient use of procedure calls in the tail position

What’s a procedure? Blocks of callable code  Functions  Methods  Subroutines  Routines

What does it mean for a procedure call to be in tail position? A procedure call is in tail position if it’s the last thing to happen before returning

int a = bar(): return a + 1; } Example 1 public static void foo1(){

int a = bar(): return a; } Example 2 public static void foo2(){

Where does the inefficiency come from?

Call stack Container for storing procedure calls Grows upward Last in, first out (LIFO) Composed of stack frames

Keeping with current analogies…  Each pancake represents some procedure to be stepped through (some computation).  The plate represents boilerplate used by the runtime system to return from procedures once they’ve run to completion.  Boilerplate might consist of return addresses, formal parameters, etc.

What’s in a stack frame? Each stack frame is made of up of:  Some computation to run (a pancake)  Some boilerplate used for returning (a plate) So our stack really looks more like this…

Specifically… ↵ b() a() main()

Fine-tuning the analogy… Remember, we consider a pancake some amount of computation/work that needs to be performed before a procedure can return. So we would expect the pancake to vary in size over the course of its lifetime.

Concretely… ; b() a() ↵ main()

What would the stack look like if our functions made use of tail calls?

Probably something like this… b() ↵ a() main()

So where’s the inefficiency?

Oh no, stack overflow! Our stack has to exist in memory, so it has a finite size. If we have too many stack frames, eventually we’ll run out of room and get a stack overflow.

A solution approaches  If procedure calls are in tail position, we can pop their remaining stack frame, since the plate is all that’s left.  Since stack frames aren’t something the programmer deals with explicitly, we let the compiler take care of the details.  Thus we have tail call elimination/optimization. (TCE/TCO)

A comparison Without TCO With TCO b() a() main() b() main()

Why should I care about this?

Benefits of TCO You can solve problems efficiently using recursion. You can make efficient use of function calls within procedures. More stack space means more room for the procedures that aren’t able to make use of tail calls.

More examples: https://gist.github.com/numberten/4acb8e7e8988caba8b5d

Related Wikipedia pages  http://en.wikipedia.org/wiki/Call_stack  http://en.wikipedia.org/wiki/Tail_call  http://en.wikipedia.org/wiki/Subroutines  http://en.wikipedia.org/wiki/Mutual_recursion  http://en.wikipedia.org/wiki/Structured_programming

Add a comment

Related presentations

Related pages

Lecture 03 - Recursion and Tail Recursion - EECS 280 ...

... Lecture 03 - Recursion and Tail Recursion from EECS 280 at Michigan. EECS 280 Lecture 3 1 Recursion and Tail ... What is tail call optimization (TCO ...
Read more

Prolog - Wikipedia, the free encyclopedia

Prolog systems typically implement a well-known optimization method called tail call optimization (TCO) ... allowing Java and Prolog to call each other ...
Read more

Tail-call optimisation | Lugar de coincidencia en Internet ...

... TCO (Tail Call Optimization) ... y tiene "tail-call optimization" las funciones recursivas con "tail call" tienen un rendimiento ... Lecture Notes in ...
Read more

java - Could an iterative function call itself? - Stack ...

... pay attention to the entire lecture. ... Scheme has tail call optimization, ... the compiler would actually implement tail-call optimization (TCO) ...
Read more

The Flying Frog Blog: When celebrity programmers attack ...

When celebrity programmers attack: Guido on tail ... aka Tail Call Optimization (TCO), ... can be achieved without tail call optimization ...
Read more

CS 440 – Programming languages and translators Week 12

CS 440 – Programming languages and translators ... - Lecture Notes 1. ... Every call is a tail call. Tail call optimization (TCO)
Read more

Once a value of n is multiplied into result we can just ...

Once a value of n is multiplied into result we can just forget it Working in from EECS 280 at Michigan
Read more

Python to Scheme to Assembly, Part 1: Recursion and Named ...

Python to Scheme to Assembly, Part 1: ... That’s “tail call optimization” (TCO) ... Lecture 1: Relations ...
Read more

Scala Functional Programming Patterns- Sample Chapter

We use it to make sure that the method will be compiled with tail call optimization (TCO). TCO converts the recursive form into a loop. ... Pic 10 Lecture 4.
Read more

In plain English, what is recursion? - Software ...

Do not talk to early abut things like tail call optimization. I know, I know, TCO is ... don't talk straight from the first lecture about the call stack ...
Read more