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
which took 31.35 sec run time (using Scheme48 on a 2GHz Pentium 4).

We now introduce a more generic fixpoint combinator:

     (define (UM myapply f)
       (define (g v)
         (lambda args (myapply (f v) args)))
       (f g))
which is parameterized by a function myapply. The latter function acts like a filter between self-applications of the function f. We can use the freedom of choosing myapply, for example, to transparently interpose memoization.
     (define (make-memoizer)
       (let ((application-cache '()))
         (lambda (function args)
             ((assoc args application-cache) => cdr)
               (let ((result (apply function args)))
                 (set! application-cache
                   (cons (cons args result) application-cache))
Now, ((UM (make-memoizer) fib-nr) 35) gives the same result, 14930352, under 0.01 seconds. The function fib_nr did not have to be changed at all.

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 
an object, of a recursive type Object = Message -> Object, is a fixpoint
     ((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.



[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 2729, 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/

Your comments, problem reports, questions are very welcome!

Converted from SXML by SXML->HTML