Goto - Alternatives - Tail Calls

Tail Calls

In a paper delivered to the ACM conference in Seattle in 1977, Guy L. Steele summarized the debate over the GOTO and structured programming, and observed that procedure calls in the tail position of a procedure can be most optimally treated as a direct transfer of control to the called procedure, typically eliminating unnecessary stack manipulation operations. Since such "tail calls" are very common in Lisp, a language where procedure calls are ubiquitous, this form of optimization considerably reduces the cost of a procedure call compared to the GOTO used in other languages. Steele argued that poorly implemented procedure calls had led to an artificial perception that the GOTO was cheap compared to the procedure call. Steele further argued that "in general procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as JUMP instructions", with the machine code stack manipulation instructions "considered an optimization (rather than vice versa!)". Steele cited evidence that well optimized numerical algorithms in Lisp could execute faster than code produced by then-available commercial Fortran compilers because the cost of a procedure call in Lisp was much lower. In Scheme, a Lisp dialect developed by Steele with Gerald Jay Sussman, tail call optimization is mandatory.

Although Steele's paper did not introduce much that was new to computer science, at least as it was practised at MIT, it brought to light the scope for procedure call optimization, which made the modularity-promoting qualities of procedures into a more credible alternative to the then-common coding habits of large monolithic procedures with complex internal control structures and extensive state data. In particular, the tail call optimizations discussed by Steele turned the procedure into a credible way of implementing iteration through tail recursion.

Read more about this topic:  Goto, Alternatives

Other articles related to "call, tail calls, tail call":

Tail Call - Description
... it can return to that location with the result once the call is complete ... Typically, this information is saved on the call stack, a simple list of return locations in order of the times that the call locations they describe were reached ... For tail calls, there is no need to remember the place we are calling from — instead, we can perform tail call elimination by leaving the stack alone (except ...

Famous quotes containing the words calls and/or tail:

    you who baited your hook with wide-awake dreams,
    and calls and letters and once a luncheon,
    and twice a reading by me for you.
    But I wouldn’t!
    Anne Sexton (1928–1974)

    Dizzily down the abyss he wheels—
    So fell Darius. Upon his crown,
    In the midst of the barn-yard he came down,
    In a wonderful whirl of tangled strings,
    Broken braces and broken springs,
    Broken tail and broken wings,
    John Townsend Trowbridge (1827–1916)