[plt-scheme] Smallest set of operators

From: Paulo J. Matos (pocm at soton.ac.uk)
Date: Fri Feb 2 11:28:14 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.

Cheers,
-- 
Paulo Jorge Matos - pocm at soton.ac.uk
http://www.personal.soton.ac.uk/pocm
PhD Student @ ECS
University of Southampton, UK


Posted on the users mailing list.