Scheme from Scratch - Bootstrap v0.11 - Primitive Procedures Part 1
It is about time we applied a procedure to some arguments. The best place to start is with primitive procedures. There are many primitive procedures in Scheme: null?, cons, etc. To start we can add just one primitive procedure. I’ve chosen addition, +, but you could choose another one if you like. Adding more than one primitive procedure to start would just cloud what is conceptually important about this incremental step. Tomorrow’s, part 2 of primitive procedures will be to add many more primitive procedures.
A sample REPL session:
$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> (+ 1 2 3)
6
> (+ 3 -1)
2
> +
#<procedure>The first examples shows that addition is a variadic procedure (i.e. can take a varying number of arguments.) This is one of the benefits of using a procedure for addition rather than a binary operator as done in many languages.
The last example shows that the output for a procedure, #<procedure>, is a bit cryptic. A primitive procedure doesn’t have any particular useful external representation and so there isn’t really anything better to print.
In the implementation, we do need to add a new internal data type PRIMITIVE_PROC. This data type uses pointers to functions so if that part of C is a bit rusty for you then please have a look in section 5.11 Pointers to Functions of K&R 2e.
All primitive procedures will have a first line like the following with only the “add” part of the name changed. The “_proc” suffix of the name will be in all primitive procedure names.
object *add_proc(object *arguments)Bootstrap Scheme is designed to run a compiler program once. A compiler program will need many more primitives than just addition. Feel free to start adding more primitives that you think will be useful in a compiler program. I’ll be adding many more tomorrow.
It’s been motivating to see Chris, Jim, Nick, Stu posting their code and seeing that their commits keep on coming. They have variations with tokenizers, flex/bison, Ada. It looks like another Chris might be starting an implementation in Go. Did I miss anyone?
There is a v0.11 branch on github for this version.
Previous article: If
Next article: Primitive Procedures Part 2
Comments
Have something to write? Comment on this article.
I look forward to reading this every day. The world can really use someone to teach it how to write a scheme compiler. THANKS!
Just in case somebody is interested: I am rewriting this project in java for the lejos-firmware for Lego Mindstorms NXT. At the moment I have no lejos-specific code, just plain Java.
http://github.com/toelke/scheme-nxj
Next week I have access to my NXTs again, then I probably will begin to write the code to have a REPL on the bricks.
Thanks again for your inspiration.
Regards,
Philipp
I really enjoy this series, and would like to thank you. Also, I wrote a subtracting primitive procedure, http://sprunge.us/KRMe?c
Philipp,
Writing a Scheme interpreter for Lego Mindstorms?! That is really cool and may require me to finally buy some new Lego for adults! :-) Such a great application for Scheme. You have my admiration!
I’ve updated my code to use RE2C for tokenisation (its a bit gritty but passes all my tests). Code also passes the basic primitive function tests, I’ve added add/sub/mul/div.. with some basic checking (divide by zero, etc) and using 64bit ints.
still not sure I have environments correct but everything seems ok right now...
oh, since I added re2c, it now does C style comments /* */ and // just for the heck of it!
been playing with using lemon to write a parser rather than hand writing it but I’ll see where it takes me...
After implementing addition I came to the conclusion that might make sense use the same template for the other basic math operations. So, I converted my addition primitive into a macro and did the other three operations (May have the names wrong) using that. The code is towards the bottom of my scheme_funcs.c file.
I was wondering why you didn’t treat define, set, quote, etc. as normal primitives? Adding a couple of flags to indicate tail calling and weather to evaluate the primitives argument list seems to work fine for me. Am I missing something?
Chris,
It sounds like you are doing a lot of interesting thinking about the implementation. That is great.
All the decisions I’m making about the implementation are guided by my desire to keep everything as simple and readable as possible and as close to the first SICP meta-circular evaluator as possible. I think my strategy is working as many people have remarked that they find the code easy to read. Some of the techniques you are using are probably good ideas but I worry they might make the code unnecessarily complicated for my expository purpose.
I do hope readers start taking the code in their own directions. You are doing that so everything is going very well from my perspective.
My last commit to bs added primitive procedures, so I'm finally caught up. I'm going to add a few more primitives tonight, and maybe do a bit of code cleanup.
Ian: If you want to add support for unary minus to your subtraction procedure, try checking if arguments is empty just before starting the loop (line 7), and returning -result if it is.
Having just finished reading SICP and your series, I’ve started my own project. It's at http://github.com/cmatei/yalfs
The evaluator is much like yours, an almost direct translation of the metacircular one in the book. I used a slightly different storage model, I’m aiming to do garbage collection at some point.
(factorial 6) => 720. Next step is proper tail recursion everywhere and an emacs interface.
Thanks for your articles and code. I’ve ripped you off a bit with the reader :)
Also, instead of
define_variable(make_symbol("+"),
make_primitive_proc(add_proc),
the_global_environment);You maybe could have a function taking a char* and a function that did most of that, so you could instead have:
define_proc("+", add_proc);Jim Ingram: Hey, thanks, that’s a good idea. :)
Ian,
Even though I’ve used macros sparingly, I think your define_proc is screaming out to be one and it is in my v0.12 code.
Have something to write? Comment on this article.
I would have expected some kind of type error here:
I quickly tried scheme48 and it does indeed report the error. Is there any particular reason why you chose to omit type checking from the primitive add?