fixpoint operator that works with functions of different numbers of arguments

Here's a cute procedure you might enjoy if you haven't seen it before.

We want to write a fixpoint operator, such that

((fix G) x y z ...) = ((G (fix G)) x y z ...)

That is, such that

(apply (fix G) (list x y z ...)) = (apply (G (fix G)) (list x y z ...))

So using unrestricted lambda, one simply writes down the right hand side,

naming the list args (or whatever):

(define fix

(lambda (G)

(lambda args

(apply (G (fix G)) args))))

Then you can use this to do the usual stuff you can do with a fix

point combinator. For example...

(define fact-gen

(lambda (fact)

(lambda (n)

(if (zero? n)

1

(* n (fact (- n 1)))))))

(define factorial (fix fact-gen))

Of course, you can write fix without using recursion

(the famous Y combinator). But if you're just interested

in taking fixpoints for computation, and not in explaining

the semantics of features like define and letrec,

then the above definition of fix is adequate.

Gary Leavens

--

229 Atanasoff Hall, Department of Computer Science

phone: (515)294-1580 fax: (515)294-0258 ftp site: ftp.cs.iastate.edu

URL: http://www.*-*-*.com/ ~leavens/homepage.html