Lambda the Ultimate

inactiveTopic Y in Practical Programs
started 12/30/2002; 3:32:09 PM - last post 3/17/2004; 3:22:02 AM
Ehud Lamm - Y in Practical Programs  blueArrow
12/30/2002; 3:32:09 PM (reads: 3569, responses: 8)
Y in Practical Programs
Bruce McAdam. Y in Practical Programs. Extended abstract presented at FICS 2001

Amazingly this paper wasn't mentioned here before. It's really cute.

Posted to functional by Ehud Lamm on 12/30/02; 3:32:43 PM

Oleg - Re: Y in Practical Programs  blueArrow
12/30/2002; 11:00:16 PM (reads: 1648, responses: 0)
Darn, I did something similar back in March 2000. I used Scheme and a different fixpoint combinator, U (explained in <>). Here's my old code:

; 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...

Sjoerd Visscher - Re: Y in Practical Programs  blueArrow
12/31/2002; 6:12:17 PM (reads: 1531, responses: 1)
> In OOP parlance, we "inherited" from a function and "overrode"
> the self-application.

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:

ranjan bagchi - Re: Y in Practical Programs  blueArrow
1/2/2003; 8:39:25 PM (reads: 1399, responses: 1)
I encourage those (like myself) who're trying to grok functional programming to go through the exercises in this paper. I fired up OCaml, thinking that there wasn't enough to get it to work.

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.

Ehud Lamm - Re: Y in Practical Programs  blueArrow
1/3/2003; 6:01:51 AM (reads: 1434, responses: 0)
Another good exercise when trying to grok FP is to try the examples from Friedman's Applications of Continuations paper.

Ehud Lamm - Re: Y in Practical Programs  blueArrow
1/3/2003; 3:49:24 PM (reads: 1406, responses: 0)

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

Dan Shappir - Re: Y in Practical Programs  blueArrow
1/5/2003; 6:40:05 AM (reads: 1313, responses: 1)
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 ...

Dan Shappir - Re: Y in Practical Programs  blueArrow
1/5/2003; 10:02:47 AM (reads: 1361, responses: 0)
OK, now BeyondJS lets you write:

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.

Ehud Lamm - Re: Y in Practical Programs  blueArrow
3/17/2004; 3:22:02 AM (reads: 148, responses: 0)
The paper uses ML. Is there a Scheme "tranlation" somewhere?