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) ;==> 14930352which 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) (cond ((assoc args application-cache) => cdr) (else (let ((result (apply function args))) (set! application-cache (cons (cons args result) application-cache)) result))))))Now,
((UM (make-memoizer) fib-nr) 35)gives the same result, 14930352, under 0.01 seconds. The function
fib_nrdid 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 -> Statean 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.
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.
[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.
[U-comb] Fixed-point combinators other than Y
This site's top page is http://pobox.com/~oleg/ftp/
Converted from SXML by SXML->HTML