[plt-scheme] Smallest set of operators

From: hendrik at topoi.pooq.com (hendrik at topoi.pooq.com)
Date: Fri Feb 2 16:26:34 EST 2007

On Fri, Feb 02, 2007 at 01:13:35PM -0800, Michael Vanier wrote:
> Paulo,
> You should get the book "Lisp In Small Pieces" by Christian Queinnec.  Even 
> though it won't directly answer your question (which, as has been pointed 
> out, is somewhat vague) it will show a lot of different ways to implement 
> Scheme.
> The X that Matthias refers to is from H. P. Barendregt's book "The Lambda 
> Calculus -- Its Syntax and Semantics".  The definition of X (from 
> http://en.wikipedia.org/wiki/Combinator#One_point_basis) is:
> (define K (lambda (x) (lambda (y) x)))
> (define S (lambda (f) (lambda (g) (lambda (x) ((f x) (g x))))))
> (define X (lambda (x) (((x K) S) K)))
> and you can show that X can generate S and K:
> (define K2 ((X X) X))
> (define S2 (X (X X)))
> S and K are capable of expressing everything in lambda calculus, so X is 
> too.
> Mike

I thought it would be something like that.
I don't see it formatting anyone's hard disk.

-- hendrik

Posted on the users mailing list.