# [plt-scheme] Smallest set of operators

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