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

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.

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.

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!

Chris,

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

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.

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...

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.

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.

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. (-:

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.

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! (-: )

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!