[plt-scheme] Smallest set of operators

From: Dave Griffiths (dave at pawfal.org)
Date: Fri Feb 2 11:48:11 EST 2007

> 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.

I found this an interesting read when pondering such questions myself:

The answer does seem to be around 7...




Posted on the users mailing list.