Scheme from Scratch - Bootstrap v0.10 - If

The if form is the most basic conditional form in Scheme. The cond and case forms can be reduced to a series of if forms.

A sample REPL session:

$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> (if #t 1 2)
1
> (if #t 'a 'b)
a
> (if #f 1 2)
2
> (if #t 1)
1
> (if #f 1)
#f
> (if 0 1 2)
1

Yes the last example is correct. In Scheme, all values are considered true except for #f.

When you look in the implementation, you may gasp when you see the goto. The goto is used to implement the tail expressions as discussed in section 3.5 of R5RS. It is possible to use a while (1) loop instead of the goto but I find that goto describes the semantics of a tail call better especially with a label tailcall. Feel free to do it either way in your code, of course.

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

Previous article: Environments
Next article: Primitive Procedures Part 1

Comments

Have something to write? Comment on this article.

Stu January 14, 2010

That was simpler than the previous article to implement :)

I’m getting the same results bar one as your example bar one.

> (if #f 1)
#t

hmm.. some debugging work needed on my end I think...

Philipp January 14, 2010

What would be the downside of just calling eval again? I. e. “return eval(exp, env)”? Of course, the compiler should optimize the tail-call to exactly the goto, so they are equivalent, but you specifically make the argument that the goto is sensible there, so I thought I should ask.

Peter Michaux January 14, 2010

Philipp,

In Scheme, we have to be sure that a procedure application in a tail position does not require more stack space. The C compiler might optimize by making a tail call but it isn’t guaranteed so we have to implement the tail call explicitly.

Stu January 14, 2010

OK, I have my code online.

git://github.com/stu/bootstrap-slip.git

This has the failing v0.10 test.

  • Passes around the context with all global data
  • Uses linked list (rather than PAIR)
  • Allows hex numbers (and negative hex)
  • single string instantiation (like symbols)
  • tracks all object allocations (poor mans gc!)
  • minor other changes

Jim Ingram January 14, 2010

So far I’m up to quotes. I’ll take a stab at environments tonight or tomorrow.

It’s interesting to try and come up with a solution to a problem on my own, then taking a look to see how others have handled it. My code’s biggest departure from Peter’s (besides C90/C99 differences, and stylistic issues) is probably separating the lexer from the parser. I’m using the same object model, and my evaluator and printer are structured much like his, but the read layer is pretty different. I’m also using a hash table for symbols, and I’m cheating and using the Boehm garbage collector.

It’s been a while since I’ve had an interesting project to work on, and it seems like a lot of ground has been covered in just a week. Lots of fun.

Have something to write? Comment on this article.