Tail call optimization (TCO) - Lecture

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

Published on March 6, 2014

Author: JesseFrankley

Source: slideshare.net

Description

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

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

 User name: Comment:

Related presentations

International Schools Services - ISS Managed Schoo...

September 23, 2017

How To Pick A Glorious Career Without Selling Your...

September 23, 2017

A Training Course That Paves Way For Assured Job

September 23, 2017

A Course for Professionals Seeking Better Job

September 23, 2017

Energy and Metabolism fall 2017 posted

September 23, 2017

Module Five—WRIT 5930

September 23, 2017

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 ...

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 ...

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 ...

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

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 ...

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)

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

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 ...