Scheme from Scratch - Bootstrap v0.12 - Primitive Procedures Part 2

In the last version we implemented a single primitive procedure. In order for our bootstrap interpreter to be able to run a Scheme compiler written in Scheme, we will need several more primitive procedures. It it now a good time to bite off a reasonably meaty chunk and implement the majority of what is needed.

A few of the things you can execute in the REPL after today’s additions:

$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> (boolean? #t)
> (integer->char 99)
> (< 1 2 3)
> (cons 'a 'b)
(a . b)

To determine the following list of primitives to add, I trawled through R5RS looking for all the procedures that seemed like they would be required as primitive procedures. The following list also contains a few that could be implemented as library procedures later but I’m going with the list below. Perhaps some of the following won’t be used. Perhaps I’ve missed some and will have to sneak back to this article and append to the list.

type predicates:

  • null?
  • boolean?
  • symbol?
  • integer?
  • char?
  • string?
  • pair?
  • procedure?

type conversions:

  • char->integer
  • integer->char
  • number->string
  • string->number
  • symbol->string
  • string->symbol

working with integers:

  • +
  • -
  • *
  • quotient
  • remainder
  • =
  • <
  • >

working with pairs and lists:

  • cons
  • car
  • cdr
  • set-car!
  • set-cdr!
  • list

polymorphic equality testing:

  • eq?

You will notice a distinct lack of argument checks on the arguments to the primitive procedures: the number of arguments and argument types. Bootstrap Scheme is not a production Scheme implementation. It is rickety. It is just enough to bootstrap a Scheme compiler. It has the fun parts of implementing because we are doing this in our spare time;-) If you type meaningful Scheme into the interpreter it should provide the correct output.

Another goal of Bootstrap Scheme is educational and to help readers over the hump of implementing a first Scheme in C with as little resistance as possible. Being bogged down by the requirements of production quality code is counter to that goal. With the error checking included in the code, the code might just bloat to big enough to scare people away.

All that said, it would be almost trivial to add bulky error checking through out the code. Anyone who understands the code could surely do it. If you would like error checking in your interpreter then I encourage you to add it.

If you are following along with my code you will see that I spent some time today refactoring. I touched code in all eleven previous branches. Maintaining eleven versions of code takes some time. Scheme comments are now considered whitespace, the read function is a bit simpler, and the code is formatted a nicer in some places. I have a Bootstrap Scheme grand finale planned (hopefully only about a week away) and it requires comments.

Even with that teaser out there, I think tomorrow might be one of the most exciting days of the whole implementation. :-)

There is a v0.12 branch on github for this version.

Previous article: Primitive Procedures Part 1
Next article: Lambda the Ultimate


Have something to write? Comment on this article.

Ian January 17, 2010

Instead of repeating

is_sometype(car(arguments)) ? true : false;

You could make a macro or function to convert it for you, for instance:

object *make_boolean(char value) {
    return value ? true : false;

And then use:

jahhaj February 21, 2010

Very inspirational series. Thanks.

I just wanted to point out a sneaky optimization for the cons primitive. Instead of

object *cons_proc(object *arguments) {
    return cons(car(arguments), cadr(arguments));

you can write

object *cons_proc(object *arguments) {
    set_cdr(arguments, cadr(arguments));
    return arguments;

This saves one cons cell per call to cons, and works because the argument list is freshly allocated each time.

Have something to write? Comment on this article.