Y overriding self-application

Using the fixed-point combinator explicitly has more than theoretical interest. When we write a recursion via the explicit Y, we get the opportunity to override the self-application later, e.g., to transparently introduce memoization. That fact is illustrated in the paper [McAdam]. This page shows a similar technique -- but in Scheme and using a different different fixpoint combinator. This page is based on an unpublished manuscript written in March 2000 -- approximately the same time frame as that of McAdam's paper.

Using a fixpoint combinator explicitly lets us, in OOP parlance, ``extend'', or ``subclass'', a function and ``override'' the self-application.

On this page, we will be using the fixed-point combinator U [U-comb], defined as follows:

     (define (U f) (f f))

Our running example is the ever so convenient Fibonacci function. More interesting and practical examples are described in [staged-memo]. Because we wish to explicitly employ the fixed-point combinator, we write the Fibonacci function in a slightly different way. We introduce an extra argument f meaning ``self''. Whenever we want to apply fib-nr recursively, we write (f f) instead. We hence avoid any explicit mentioning of fib-nr in the body of the function. Therefore, the code below is obviously not recursive.

     (define (fib-nr f)
       (lambda (n)
         (if (< n 2) 1 (+ ((f f) (- n 1)) ((f f) (- n 2))))))

We can run the function as follows, e.g., to find the 35-th Fibonacci number.

     ((U fib-nr) 35) ;==> 14930352

We now introduce a more generic fixpoint combinator:

     (define (UM myapply f)
       (define (g v)
         (lambda args (myapply (f v) args)))
       (f g))

     (define (make-memoizer)
       (let ((application-cache '()))
         (lambda (function args)
           (cond
             ((assoc args application-cache) => cdr)
             (else
               (let ((result (apply function args)))
                 (set! application-cache
                   (cons (cons args result) application-cache))
                 result))))))

In OOP parlance, we ``inherited'' from a function and ``overrode'' its self-application. Incidentally, there is a deep connection between object-based programming and Y: Indeed, given a state transformer function

     transform:: State -> Message -> State 

     ((Y (\self state msg -> self (transform state msg)) init-state) 

The papers [staged-memo] describe a similar technique to stage dynamic programming algorithms and FFT. The fixed-point combinator is applied in a monadic setting, for a state + CPS monad. The state is the memoization table, which helps us avoid code duplication in the generated specialized code.

References

[LTU-message] Y in Practical Programs.
< http://lambda-the-ultimate.org/classic/message5463.html>
A message to the Lambda-the-Ultimate list posted on Tue, 31 Dec 2002 07:02:20 GMT

[McAdam] Bruce McAdam. Y in Practical Programs. Extended abstract presented at FICS 2001.
< http://www.scms.rgu.ac.uk/staff/bjm/doc/#fics2001>

[staged-memo] A Methodology for Generating Verified Combinatorial Circuits.
Joint work with Kedar N. Swadi and Walid Taha.
To appear in Proc. of EMSOFT'04, the Fourth ACM International Conference on Embedded Software, September 27­29, 2004, Pisa, Italy.
< http://www.cs.rice.edu/~taha/publications/conference/emsoft04.pdf>

[U-comb] Fixed-point combinators other than Y

Last updated August 1, 2004

This site's top page is http://okmij.org/ftp/

Converted from SXML by SXML->HTML