What is the minimum practical definition for the Scheme language?

Question

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?

Answer 1

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

Your question needs an entire book to be answered, and Queinnec's book is that book.

Answer 2

The answer to this question is going to depend almost entirely on your italicized term, practical. You probably feel very different than I do about what exactly constitutes practicality. Obivously, you can strip everything down to the lambda calculus, and you wind up with a turing-complete language including only lambda, varrefs, and application.