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? May 1 '15 at 5:48
  • 1
    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... May 1 '15 at 6:15
  • I believe that cons, car, cdr, if, +, -, >= lambda, pair?, set!, procedure?, symbol?, integer? should be enough May 1 '15 at 7:55
  • 1
    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. 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. 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).

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


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.

  • I expect to see some reasonable accomodation for primitives such as proper handling of numbers,not Church Encoding, for example. In other words, it would have to be reasonably fast. Someone familiar with the Scheme dialects, and perhaps having implemented one himself, would know where that dividing line is. I suspect it could be done with a dozen basic forms or so. May 1 '15 at 17:04
  • 1
    You can go even further down than lambda calculus and get the SKI combinator calculus, or go even further down by building the S, K, and I combinators of that calculus out of the single Iota combinator. And some may not think that a scheme with only minimalist number support is practical, they may want IO and string primitives. Or networking primitives. Or all the way up to a full proper set of practical libraries. Bottom line - practical is too subjective.
    – Jack
    Jun 1 '15 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.