[plt-scheme] Smallest set of operators

From: Robby Findler (robby.findler at gmail.com)
Date: Fri Feb 2 16:29:35 EST 2007

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


Posted on the users mailing list.