Scheme from Scratch - Bootstrap v0.17 - And and Or

One more round of library syntax: the and and or forms. These could be split into two different versions but they are so similar I think biting them off in one chunk is justified. If you do and first then or will be easy.

Sample REPL session:

$ ./scheme
Welcome to Bootstrap Scheme. Use ctrl-c to exit.
> (and 1 2 3)
3
> (and)
#t
> (or #f 2 #t)    
2
> (or)
#f

An important aspect of and and or is they are short-circuiting. Here is an example demonstrating the importance of and short-circuiting when side-effects are involved:

> (define a 1)
ok
> (and #f (set! a 2))
#f
> a
1
> (and #t (set! a 2))
ok
> a
2

If you are not already consulting the Scheme spec when implementing features in your interpreter, now might be a good time to give that a try. I have R5RS printed on real paper which is handy.

I’m not 100% sure but I think it might now be possible to run all the examples in The Little Schemer in your interpreter.

I’ve enjoyed the watch feature on GitHub to follow other’s progress. It is motivating to see implementations moving forward and really great to see people have actually implemented features I haven’t discussed yet: apply, load, etc.

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

Previous article: Let
Next article: Apply

Comments

Have something to write? Comment on this article.

Jim Ingram January 21, 2010

I’m thinking of adding read, eval, and write as scheme primitives, and moving the REPL out of main() and into a separate scheme file.

Peter Michaux January 21, 2010

Jim those are all good ideas. I’ll be adding those primitives over the next few days. I won’t be making my implementation for these articles as a library. Just a single file is fine for bootstrap and expository purposes; however, if I was building a Scheme interpreter for embedding it would be in a library.

Chris January 21, 2010

It is utterly amazing how satisfying it is to see something actually working on an interpreter you’ve built yourself. For my implementation, I’ve added partial floating point support. This evening, just to see if I could pull it off, I worked through the details of a square root routine while reading the first chapter of SICP online. It worked beautifully! YEAH!

Peter Michaux January 21, 2010

Chris,

I agree. It is a real thrill to see the interpreter work and visualize the model being manipulated as the code executes.

Jim Ingram January 22, 2010

I printed out the standard (R5RS) last night, and am reading through it. I think I’m going to implement basic support for ports to replace my current hacked-on file support. Matei Conovici beat me to it in yalfs, which has some other interesting ideas in it as well.

Stu January 22, 2010

I implemented a method call form in my interp thinking I’d hack some OO ness into the system. Implementing new types (method_call) and a binding keyword, using ~ as the syntactic sugar and pushing ‘self’ as the first arg in every methodcall list.

(define boot 1)
(procbind boot 'to_string
	(lambda () (number->string self))
)
(boot~to_string)

Only after I hacked all this together, it was apparent it gives objects methods but what I really lacked was a form of class abstraction as I realised every declaration is of global scope or down on the lambda level, what I really needed was the sharing to stop at the instance level.

thinking about it, each object needs an environment created when the first method call is attached, which can then sit between and created lambdas on the object and the global environment (or whatever is above the object).

bah, just need to think about my implementation details a bit more.

I’m well off the rails and crazy...

Jim Ingram January 22, 2010

I’ve not done much OOP with Lisp or Scheme, but I think the usual way of doing it is to use multiple-dispatch. Methods are not contained in classes, but are grouped together in generic functions. When a call to a generic function is made, it determines which method to call based on the types of all of its arguments.

The wikipedia pages for Generic Functions and CLOS probably explain it more clearly. CLOS is for Common Lisp, but there are similar object systems for Scheme.

Peter Michaux January 22, 2010

SICP covers both message passing (i.e. Smalltalk, and Java-like OOP) and data-directed programming (i.e. CLOS-like OOP). Neither requires extra to be added to the language. For message passing, I would do it exactly like SICP does and would not add any special support for inheritance. For data-directed programming, SICP uses tagged lists to identify types. That bothers me a bit as the new types are not disjoint from the language types. I would look at something like SRFI 9 Defining Record Types or something like PLT Structures to allow the programmer to define new disjoint types.

kbob January 22, 2010

Peter, I was surprised to see that you implemented AND and OR directly in eval(). Did you consider implementing them like COND, i.e., rewriting them into chains of IF expressions? (Actually, OR turns into LET + IF, which can be rewritten again as LAMBDA + IF.)

(and a b c) => (if a (if b c) #f)
(or a b c) => (let ((t a)) (if t t (let ((t b)) (if t t c))))

The latter statement lets you verify that your name scoping is functioning correctly. (-:

Peter Michaux January 22, 2010

kbob,

I did consider implementing and and or as expansions into other forms like cond but I kept coming up with expansions for or that involved let or lambda which introduces nested scopes. I don’t think that and and or forms are supposed to be introducing new scopes. My main concern was that if one of the tests was actually a define form; however, that may not actually be allowed. You may be right, perhaps I should have done it like cond.

kbob January 22, 2010

Thanks for your reply, Peter.

(a) AND is much easier than OR to expand into nested IF expressions.

(b) You are correct that the simple expansion I showed above is not hygienic. If one of the OR clauses referenced the symbol T, then it would get the T from the nearest LET scope, not the T it was supposed to get. Given how much I’ve been thinking about macros lately, I should have known better.

There’s nothing wrong with macros (or C rewriters) introducing scopes, it’s just that they need to avoid name conflicts.

If I were doing it, I’d create an anonymous symbol for the LET variable. By anonymous, I mean a symbol with no name, not linked into the global symbol table. You can look up the value of an anonymous symbol in an environment, but it won’t collide with any other symbol.

object *make_anon_symbol(void)
{
    object *obj = alloc_object();
    obj->type = SYMBOL;
    obj->data.symbol.value = ""; /* or call it "t" */
    return obj;
}

But it’s your interpreter and your solution is perfectly good and possibly simpler. If you aren’t building a general macro facility anyway, then my suggestion is probably overkill.

(c) In Beautiful Code, OR is one of the canonical examples for macro hygiene. See Section 1, page 4 in the linked PDF.

(d) R5RS permits DEFINE only at top level and at the beginning of a body. (R5RS section 5.2) R6RS is similar.

BTW, I am back in the game. I started a new Scheme interpreter code base last weekend. Right now I’ve got an RPL (read-print loop, no eval). I hope to post it on github this weekend.

My plan for this code base is kind of radical. Whenever object allocation fails because the heap is full, it runs the garbage collector, then calls longjmp(). Because I use a copying GC, all the object references on the C stack become invalid, so longjmp() throws them all away. The corresponding setjmp() will restart the evaluator from the last continuation. The same setjmp/longjmp mechanism will be used for Scheme exception handling. (Wish me luck! (-: )

Peter Michaux January 22, 2010

kbob,

BTW, I am back in the game. I started a new Scheme interpreter code base last weekend. Right now I’ve got an RPL (read-print loop, no eval). I hope to post it on github this weekend.

If these articles are at all even partly responsible, I’m sorry. ;-)

Thanks for the info and good luck with your longjump fun!

Have something to write? Comment on this article.