Scheme from Scratch - Bootstrap v0.4 - Strings

Another day, another data type: strings.

Like with the character implementation, we only need to worry about ASCII strings for a bootstrap interpreter. The only tricks are reading and writing escaped double quote and newline characters inside a string.

A sample REPL session with strings:

$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> "asdf"
"asdf"
> "asdf\"asdf"
"asdf\"asdf"
> "asdf\n"
"asdf\n"
> "asdf
"
"asdf\n"

Note that when you want to enter a newline as part of a string you type two characters \n and when the string is displayed a newline is displayed as the same two characters; however, in the interpreter’s internal string model, a newline is stored as a single byte.

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

Can I see a show of hands who has actually compiled the Bootstrap Scheme code themselves? Has anyone improved it?

Previous article: Characters
Next article: The Empty List

Comments

Have something to write? Comment on this article.

kbob January 8, 2010

I compiled and ran v0.02. It was much more interesting to read the source than to run it.

John January 8, 2010

I’ve been following along and compiling. I took a different approach in a couple situations (ie. I used strtol for fixnum parsing).

I’m not much of a C programmer, but shouldn’t you use an int for checking the return value of getc? See http://c-faq.com/stdio/getcharc.html.

Peter Michaux January 8, 2010

John,

Thanks for your suggestions. strtol is a good idea and you can check for overflow errors that way also. You are clearly right about getc. I will update the code to fix this.

Derek Hammer January 8, 2010

http://github.com/petermichaux/bootstrap-scheme/blob/master/scheme.c#L191

I think that this is going to introduce an error for any input that has more than one number in the input string. Test cases, after you have implemented operations:

-1 +  1 ==  0
-1 *  1 == -1
-1 * -1 ==  1 (this one will pass)
 1 * -1 == -1 (this one will also pass)

Then again, I may be reviewing the code with too much of the future in my mind.

Peter Michaux January 8, 2010

Derek,

I just tried your examples in my more complete interpreter. It computes the correct values (i.e. the values you’ve shown.) The C read function is called for each object entered. Since the sign is reset at the top of the read function each time it is called, things work out correctly.

Dan Ballard January 8, 2010

I’ve been following along trying to write my own and referring to yours when stuck for ideas. Yours has compiled just fine on my Ubuntu karmic box.

Thanks!

Christopher Roach January 8, 2010

Just wanted to let you know that I have been following these “Scheme From Scratch” posts since the beginning and they are fantastic. The code is really neat and clean and very understandable. Keep up the good work.

Chris January 9, 2010

I’ve been following you and reading through your code every so often. Of course, my knowledge of scheme and lisp is pretty much nil so I’m attempting to use this as an attempt to learn the language from the inside out. I took a slightly different take (using flex and bison) for parsing and autotools as a build environment. The code is atrocious but appears to work well enough for me as a starting point. It helps a great deal to have someone to pace.

Peter Michaux January 9, 2010

Chris,

That is great that you are doing things a bit differently to engage at a deeper level. If you are interested in flex and bison you may be interested in the code from Matthew Flatt’s lecture on Dec 3, 2002 called “Interpreters from Scratch” where it looks like he is using lex and yacc.

Daryl Lee January 6, 2011

I know I’m a year late, but I just discovered this site. I’m interested in a tiny Scheme interpreter for an embedded app, so I’m building it with a minimum of OS support—only getchar() and putchar() for I/O, and so far it’s working nicely. I don’t expect any OS support; I’ll even eventually implement my own putchar() and getchar() function to handle my hardware I/O channel. As I go I’m building up an lprintf(...) function to substitute for printf(...).

Huge thanks for doing this!

Werner Heigl December 8, 2012

Peter, many thanks for putting this together. I was always puzzled how one would actually go about implementing a programming language. And ever since I’ve got myself a copy of SICP I have not been able to put it aside. There are a lot of concepts in that book that are not part of mainstream computer programming (at least not in my field of exploration geophysics). I figured that if I really wanted to understand SICP I need to implement scheme from scratch. I have made it this far and your series has been an excellent guide.

Have something to write? Comment on this article.