Lambda the Ultimate

; The U combinator
(define (U f) (f f))


; A non-recursive function
(define (fib-nr f)
  (lambda (n)
    (if (< n 2) 1 (+ ((f f) (- n 1)) ((f f) (- n 2))))))


; Finding the 35-th Fibonacci number, by passing 35 to 
; the fixpoint of fib-nr


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


which took 31.35 sec run time (using Scheme48 on a 2GHz Pentium 4).
I didn't have a powerful computer back in 2000, so the old paper
computed only 25-th Fibonacci number.


Now, let's define a more generic fixpoint combinator:


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


which uses an "abstract" function myapply. We can use the freedom of
choosing myapply, for example, to _transparently_ interpose a
memoization.


			; Cache function's arguments and results
(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 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"
the 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 = Object -> Message -> Object)
is a fixpoint
 ((Y (\self state msg -> self (transform state msg)) init-state)

I never got around to post that article...

That's a nice idea. I had to try this. Javascript does not let you inherit from a function, so that didn't work. But Loell does, so I added a recursion overriding example on the Loell page: http://w3future.com/html/loell/

I typed in:

let rec y' f x = f (y' f) x;;

And to my surprise... got:

val y' : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

(i.e. it worked!)

With a little bit of obvious coding, I was able to go through implementation of the printer and memoization wrappers.

Very slick.

Which goes to show you that everyone should have a personal toy language to play with and extend...

Javascript does not let you inherit from a function

While this is technically true, you can achieve the desired effect using JavaScript.

function fib(n) {
  return n < 2 ? 1 : fib(n-1) + fib(n-2);
}

function cache(f) {
  return function() {
    var a = Array.from(arguments);
    return typeof(f[a]) != "undefined" ? f[a] : f[a]= f.apply(this, a);
  };
}

fib = cache(fib);

Array.from() is a utility function from the BeyondJS library that converts the arguments object into a real JS array. Now that I've done this I'll probably add this functionality to BeyondJS as well :-)

I would also like to point out that the lazy lists implemented by BeyondJS, which are essentially just functions wrapped in a container interface, also provide such a caching mechanism.

Oh well, now back to real work ...

fib = fib.cached();

to get the caching version of the fib function.

BTW, the caching mechanism supports multiple arguments (not just one), and the resulting (caching) function has the same argument signatute as the original.

Note: this version of BeyondJS isn't online yet.