Tail calls and CPS

For users of dfns, both novice and expert

Tail calls and CPS

Postby JohnS|Dyalog on Sun Dec 06, 2009 1:03 pm

Tail calls are a-good-thing. Compare these functions for the sum of two natural numbers; the first uses a non-tail-recursive call, whilst the second is tail-recursive. Apart from the placement of the 1+, the functions are identical. In particular, profiling would show them calling the same number of primitive functions.

Code: Select all
      cmpx'2{⍵=0:⍺ ⋄ 1+⍺ ∇ ⍵-1}3' '2{⍵=0:⍺ ⋄ (1+⍺)∇ ⍵-1}3'
  2{⍵=0:⍺ ⋄ 1+⍺ ∇ ⍵-1}3  → 8.0E¯6 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  2{⍵=0:⍺ ⋄ (⍺+1)∇ ⍵-1}3 → 6.2E¯6 | -23% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕         

Ideally, we would like to arrange that all calls within a capsule are tail calls, though sometimes it isn't immediately obvious how to do so. For example, in the above sum code, it would be more difficult if the expression to the right of the tail-recursive call ∇ included a call to a sub-function:
Code: Select all
        ⍵=0:⍺ ⋄ (1+⍺)∇ pred ⍵    ⍝ non-tail call on predecessor function pred

The question is, how can we make the call to pred also a tail call?

The answer is to use a technique called "continuation-passing", and instead of calling pred, we pass the ∇ to it as an operand and have pred recursively tail-call the outer function.
Code: Select all
        pred←{⍺ ⍺⍺ ⍵-1}         ⍝ tail call on sum (⍺⍺).
        ⍵=0:⍺ ⋄ (1+⍺)∇ pred ⍵   ⍝ AND tail call on pred

Now every call is a tail call.

A more substantial example of CPS can be found in the "Technical note" section of
with the corresponding code in

Return to Functional Programming

Who is online

Users browsing this forum: No registered users and 1 guest