I want to implement a scheme interpreter for studying SICP

Question

I'm reading the book Structure and Interpretation of Computer Programs, and I'd like to code a scheme interpreter gradually.

Do you knows the implementation of the scheme most easy to read (and short)? I will make a JavaScript in C.

Answer 1

I would recommend the blog series Scheme from scratch which incrementally builds up a scheme interpreter in C.

Answer 2

SICP itself has several sections detailing how to build a meta-circular interpreter, but I would suggest that you take a look at the following two books for better resources on Scheme interpreters: Programming Languages: Application and Interpretation and Essentials of Programming Languages. They're both easy to read and gradually guide you through building interpreters.

Answer 3

I would recommend reading Kent Dybvig's dissertation "Three Implementation Models for Scheme". Not the whole dissertation, but the first part (up to chapter 3) where he discusses the Heap-Based Model is very suitable for a naive implementation of Scheme.

Another great resource (if I understood it correctly and you want to implement it in C) is Nils Holm's "Scheme 9 from Empty Space". This link is to Nils's page, and there's a link at the bottom to the old, public domain, edition of the book and to the newer, easier to read, commercially available edition. Read both and loved 'em.

Answer 4

I can give you an overview on how my interpreter works, maybe it can give you an idea of the general thing. Although the answer is pretty late, I hope this can help someone else, who has come to this thread and wants a general idea.

1. For each line of scheme entered , a Command object is created. If the command is partial then its nest level is stored(number of remaining right brackets to complete the expression). If the command is complete an Expression Object is created and the evaluators are fired on this object.
2. There are 4 types of evaluator classes defined , each derived from the base class Evaluator

a) Define_Evaluator :for define statements

b) Funcall_Evaluator :for processing other user defined functions

c) Read_Evaluator :for reading an expression and converting it to a scheme object

d) Print_Evaluator :prints the object depending on the type of the object.

e) Eval_Evaluator :does the actual processing of the expression.

3.-> First each expression is read using the Read Evaluator which will create a scheme object out of the expression. Nested expressions are calculated recursively until the expression is complete.

->Next, the Eval_Evaluator is fired which processes the Scheme Expression Object formed in the first step. this happens as so

a) if the expression to be evaluated is a symbol. Return its value. Therefore the variable blk will return the object for that block.

b) if the expression to be evaluated is a list. Print the list.

c) if the expression to be evaluated is a function. Look for the definition of the function which will return the evaluation using the Funcall_Evaluator.

->Lastly the print evaluator is fired to print the outcome , this print will depend on what type the output expression is.

Disclaimer: This is how my interpreter works , doesnt have to be that way.