Tail calls and CPS

[JohnS|Dyalog]

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

    sum←{
        pred←{⍵-1}
        ⍵=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

    sum←{
        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
http://www.dyalog.com/dfnsdws/n_mac.htm
with the corresponding code in
http://www.dyalog.com/dfnsdws/c_mac.htm