# What is the minimum practical definition for the Scheme language?

What is the smallest practical set of primitives that can be used to define the Scheme language?

For example, `map` can be defined as

``````(define (map proc lis)
(cond ((null? lis)
'())
((pair? lis)
(cons (proc (car lis))
(map proc (cdr lis))))))
``````

Can the functions in this definition be similarly reduced to smaller primitives?

• Do you want to define the full R5RS, or R7RS, Scheme, or do you want to define a mini Scheme? – Basile Starynkevitch May 1 '15 at 5:48
• And what about arithmetic: you might represent numbers as lists (in unary notation), but that is very inefficient... Also, Scheme requires a sophisticated number tower with bignums... – Basile Starynkevitch May 1 '15 at 6:15
• I believe that `cons`, `car`, `cdr`, `if`, `+`, `-`, `>=` `lambda`, `pair?`, `set!`, `procedure?`, `symbol?`, `integer?` should be enough – Basile Starynkevitch May 1 '15 at 7:55
• `cons`, `car` and `cdr` can be implemented in terms of `lambda` and `if`, and `if`, in turn, can be implemented in terms of `lambda` as well. I don't think you need anything besides `lambda` and probably `apply`. – Jörg W Mittag May 1 '15 at 8:47
• @JörgWMittag: this is theoretically true (in lamda-calculus), but in practice any Scheme want to represent pairs and numbers efficiently. – Basile Starynkevitch May 1 '15 at 9:11

I strongly suggest reading Queinnec's book Lisp In Small Pieces, it has several chapters to answer your question, taking into account your practicality request (without which some bare lambda-calculus would be enough); it also goes from simplistic mini-scheme interpreter (as an implementation of `eval`) to a complete Lisp-like compiler (to bytecode and to C).