Re: Desperate Questions: [1]Absolute-Child-Number

[christo@xxxxxxxxxxxxxxxxxx (Frank Christoph)]

> From dssslist-owner@xxxxxxxxxxxxxxxx Wed Jun 25 04:24 JST 1997
> From: Paul Prescod <papresco@xxxxxxxxxxxxxxxxxxxxxxxxx>
Paul Prescod <papresco@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
> >   (define (absolute-child-number snl)
> >     (if (absolute-first-sibling? snl)
> > 	1
> > 	(+ 1 (absolute-child-number (ipreced snl)))))
> > 
> > Love that tail recursion!  
> 
> Is that tail recursion? The call to the function is kind of in the "tail
> position" (I'm not sure of the definition) but it can't be implemented as 
> a "goto" because the addition must still occur on the way back up.

It's not in tail-recursive form, but any self-respecting (eager) functional
compiler will transform such definitions into tail-recursive form, usually by
using something called the CPS transformation.  The prototypical example is
the factorial function, which most people would write:

  (define (fac n)
   (if (zero? n)
       1
       (* n (fac (- n 1)))))

  (fac 3) = (* 3 (fac 2))
          = (* 3 (* 2 (fac 1)))
          = (* 3 (* 2 (* 1 (fac 0))))
          = (* 3 (* 2 (* 1 1))) = (* 3 (* 2 1)) = (* 3 2) = 6

Observe that this is not tail-recursive because there is "work" left to do
after a recursive call.  Namely one must multiply the result of the recursive
call by n.  You can think of this "left-over work" as the context of the
expression or, what is more common, the continuation of the expression.

For example, the continuation (or context) of (+ n 1) in

  (* (+ n 1) 2)

is (* [] 2), where [] is a "hole".  You can reify this continuation as a
function which represents the hole as an argument.

  (lambda (x) (* x 2))

Then, using this, you can re-express the original complex expression in a
different fashion.

  ((lambda (x) (* x 2)) (+ n 1))

The way to bring definitions such as the factorial function above into
tail-recursive form, then, is to make the continuation of a recursive call
explicit and pass it as an extra argument to the function.  You accumulate
the continuation for each call in that argument and then apply it when you
bottom out. 

Note that the continuation of a recursive (fac n) call is (* n []).  Assume
that the expression (fac n) occurs in a context k.  Then we can form a
new continuation.

  (lambda (x) (k (* n x)))

So we can define an iterative factorial function by passing the continuation
k along with the original argument.

  (define (fac-helper n k)
    (if (zero? n)
        (k 1)
        (fac-helper (- n 1) (lambda (x) (k (* n x))))))

  (define (id x) x)
  (define (fac n) (fac-helper n id))

For notational brevity, I will label sub-expressions with {A}, {B}, ...

  (fac 3) = (fac-helper 3 id)
          = (fac-helper 2 {A}(lambda (x) (id (* 3 x))))
          = (fac-helper 1 {B}(lambda (x) (A (* 2 x))))
          = (fac-helper 0 {C}(lambda (x) (B (* 1 x))))
          = (C 1)
          = (B (* 1 1)) = (B 1)
          = (A (* 2 1)) = (A 2)
          = (id (* 3 2)) = (id 6)
          = 6

Incidentally, note that now the only purpose of n is to keep track of how many
recursions are left to make.

Also note the way we stick the continuations together: they form kind
of a pipe from the base case to the top call.  This suggests that we
might simply generate n fac-calls beforehand and then compose them.

  (define (gen n f)
    (let loop ((i n)
	       (xs '()))
      (if (zero? i)
          xs
          (loop (- i 1) (cons (f i) xs)))))
  ; e.g., (gen 3 id) = '(1 2 3)

  (define (compose f g)
    (lambda (x) (f (g x))))

  (define (fold f b xs)
    (if (null? xs)
        b
        (f (car xs) (fold f b (cdr xs)))))
  ; e.g., (fold + 0 '(1 2 3)) = (+ 1 (+ 2 (+ 3 0)))

  (define (fac n)
    (let* ((fac-call (lambda (n) (lambda (x) (* n x))))
           (calls (reverse (gen n fac-call))))
      ((fold compose id calls) 1)))

This constructs a list of functions

  '({F}(lambda (x). (* 3 x)) {G}(lambda (x). (* 2 x)) {H}(lambda (x) (* 1 x)))

then composes them

  F . G . H = (lambda (x) (* 3 (* 2 (* 1 x))))

and applies the resulting function to 1, the base case.

I don't think anyone would write fac in this way, but this example is useful
for pointing out (1) the parallelism inherent in a functional language, and
(2) the uses of combinators like gen, fold and compose, which incidentally
even more ubiquitous in lazy languages.
 
  -- FC

 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist