[plt-scheme] Smallest set of operators

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


Paulo J. Matos wrote:
> Ok,
> I think we got to a lot more theoretical discussion than I initially
> intended. This is just mere curiosity and not directly involving my
> work, although somewhat related. What happened was I was thinking to
> myself: "Guess I would like to write a compiler for Scheme in C (or
> some other language other than Scheme iteself) and that I would want
> to spare the trouble of writing C. So I would write the bare minimum
> in C, the rest in Scheme using the C layer. Now, what would I have to
> write in the C layer? In other words, what would I need initially in
> the Scheme layer to implement the rest of scheme. No matter efficiency
> issues... Maybe I could have initially define, lambda, null?, '(),
> car, cons, cdr. Would I need anything else? Would you need anything
> else? Could you find a set with less than 7 operators (see operator
> here in a wider sense since '() is not really an operator)?
> 
> Of course this were the ones which came to me and you probably need
> more or maybe you need less but this was really the reason why I
> asked. Overall it seems a nice and reasonable question to be made.
> 
> Cheers,