# [plt-scheme] Smallest set of operators

On 2/2/07, hendrik at topoi.pooq.com <hendrik at topoi.pooq.com> wrote:
>* 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.
*
If you hard disk controller were implemented in Scheme (which was then
translated to Xs), it could.
Robby