Implementing Scheme in C++ - Introduction
Posted on November 14, 2011 by Paul
The code for this article is on GitHub: https://github.com/sol-prog/schm.
Update: 2011/11/21: The code presented in this article was completely restructured (one instruction per line, classes implementation separated from the definition, more comments etc …) in the second article from this series.
Implementing a high order programming language in a low level language, like C++ (Assembly is too low level for my background and C … well there are already a few Scheme implementations in C), has always been a fascinating subject for me. Writing a program that interprets other programs is a great and fun experience for anyone, it is almost like a rite or passage for a programmer.
My purpose in starting this series of articles is to better understand some of the fundamentals of the Scheme programming language and how an interpreter works. A secondary purpose will be to test my Scheme implementation on some of the examples and exercises presented in SICP (I will probably skip the Picture language presented in Chapter 2). This will allow me to redo some of the exercises from the book on my own Scheme implementation and in the same time on a mature implementation like Gambit Scheme, for comparison purposes.
The Scheme subset I’ve choose to start with, is inspired by an article of Peter Norvig (How to Write a (Lisp) Interpreter (in Python)). This will be my Scheme - zero implementation, only six special forms (quote, if, set!, define, lambda and begin) and a generic Number type, that will allow simple operations with integers and floats.
The REPL will allow the programmer to test simple Scheme programs like these:
1 schm >>>(+ 3 4 10)
2 17
3 schm >>>(define square (lambda (x) (* x x))
4 schm >>>(square 10)
5 100
6 schm >>>(define fact (lambda (x) (if (<= x 1) 1 (* x (fact (- x 1))))))
7 schm >>>(fact 1)
8 1
9 schm >>>(fact 8 )
10 40320
11 schm >>>(define list (lambda x x))
12 schm >>>(list 1 2 3)
13 (1 2 3)
14 schm >>>(quit)We will start by implementing the REPL function in C++:
1 /*Simple REPL (read - evaluate - print).*/
2 void REPL(Environment &env){
3 prompt();
4 for(;;){
5 string inp=get_input();
6 if(inp=="")continue; //if the input buffer is empty go to the start of the for loop
7 vector<string>out=clean_input(inp);
8 //Evaluate an expression and print the result
9 PList pp = PList(out);
10 cout<<eval(pp,env)<<endl;
11 prompt();
12 }
13 }The above code will read the user input (a Scheme expression) and will evaluate this expression. Internally, in C++, we will use vectors of strings from the STL to store a Scheme expression, we will create new C++ class PList for this. A PList can store one or more Scheme expressions, for example:
1 (+ 1 2 3) ;4 PLists
2 (+ 1 2 (- 4 5)) ;4 PLists, the last Plist is made by 3 PListsA simplified version of the PList class (for the complete code see “PList.h”):
1 class PList{
2 vector<string>store;
3
4 public:
5 PList(){}
6 PList(vector<string>vv){store=vv;}
7 void print(){for(size_t i=0;i<store.size();i++)cout<<store[i]<<" ";cout<<endl;}
8 string get_store(){string aux=""; for(size_t i=0;i<store.size();i++)aux=aux+store[i]+" ";return aux;}
9 void clear(){store.clear();}
10
11 size_t size(){
12 ...
13 }
14
15 PList get(size_t pos){
16 ...
17 }
18
19 size_t full_size(){
20 return store.size();
21 }
22
23 string elem(size_t pos){
24 ...
25 }
26
27 void puts(string ss){store.push_back(ss);}
28
29 ~PList(){store.clear();}
30 };A Scheme environment will be simulated with a map data structure that will use strings as keys and will store: strings, PLists and pointers to functions. This way I will be able to use a single data structure for managing variables and procedures in Scheme. This will allow us to redefine any variable as a procedure and vice-versa, like in the following example:
1 schm >>>(define aa 10)
2 schm >>>aa
3 10
4 schm >>>(define aa (lambda (x) (* a a a))
5 schm >>>aa
6 Procedure
7 schm >>>(aa 2)
8 8
9 schm >>>(define aa +)
10 schm >>>(aa 2 3)
11 5The environment implementation (see “Environment.h”) is as follows:
1 class Object{
2 string(*pp)(vector<string>&);
3 string(*rr)();
4 string value;
5 string kind;
6
7 public:
8 Object(){};
9 Object(string ss){value=ss;kind="variable";pp=NULL;};
10 Object(string(*p_)(vector<string>&)){pp=p_;kind="procedure";value="";};
11 string get_kind(){
12 return kind;
13 }
14 string get_value(){
15 return value;
16 }
17 string apply(vector<string>&V){
18 return pp(V);
19 }
20 string apply(){
21 vector<string>V;
22 return pp(V);
23 }
24 };
25
26 typedef map<string,Object> Environment;Adding a new Scheme procedure directly in the C++ code is as simple as:
1 ...
2 Environment env;
3 env["+"]=add;
4 ...where, for this particular case, the add function can be implemented as:
1 string add(vector<string>&vv){
2 if(vv.size()==0)return "Wrong number of arguments for procedure +";
3 stringstream ss;
4 double sum=strtod(vv[0].c_str(),NULL);
5 for(size_t i=1;i<vv.size();i++)sum+=strtod(vv[i].c_str(),NULL);
6 ss<<sum;
7 return ss.str();
8 }The above implementation will allow us to sum an arbitrary number of arguments. Please note that internally, each number is treated as a double. For now we will use only the native C++ numerical types, a future version of the interpreter will allow arbitrary integer size by use of the GMP library.
Using the above defined Environment we can implement a first version of the evaluator, this will act as a simple arithmetic calculator:
1 string eval(PList &pp,Environment &env){
2 int N=pp.size();
3 if(N==1){ //Check for symbol, constant literal, procedure with no argument
4 if(pp.elem(0)=="(" && pp.elem(pp.full_size()-1)==")"){
5 PList aux=pp.get(0); string inp=aux.elem(0);
6 //Check for procedure with no argument, e.g. (quit)
7 if(env.find(inp)!=env.end()){
8 return env[inp].apply();
9 }
10 else{
11 return(("Error! Unbound variable: "+inp));
12 }
13 }
14 else{
15 string inp=pp.elem(0);
16 //Check if character
17 if(inp[0]=='#' && inp[1]=='\\')return "character type not yet implemented";
18 //Check if string
19 if(inp[0]=='\"' && inp[inp.size()-1]=='\"')return inp;
20 //Check if number
21 if(number(inp))return inp;
22 //Check if variable or procedure
23 if(env.find(inp)!=env.end()){
24 if(env[inp].get_kind()=="variable")return env[inp].get_value();
25 else{
26 if(show_err1_flag)cout<<env[inp].get_kind()<<" ";
27 show_err1_flag=true;
28 return inp;
29 }
30 }
31 else{
32 string res;
33 if(show_err2_flag)res="Error! Unbound variable: "+inp;
34 show_err2_flag=true;
35 return res;
36 }
37 }
38 }
39 else{
40 PList aux=pp.get(0); string proc=aux.elem(0);
41 show_err1_flag=false;
42 show_err2_flag=false;
43 if (proc=="quote"){return ((proc+" - not yet implemented!"));}
44 else if(proc=="if"){return ((proc+" - not yet implemented!"));}
45 else if(proc=="define"){return ((proc+" - not yet implemented!"));}
46 else if(proc=="set!"){return ((proc+" - not yet implemented!"));}
47 else if(proc==if){return ((proc+" - not yet implemented!"));}
48 else if(proc=="lambda"){return ((proc+" - not yet implemented!"));}
49 else if(proc=="begin"){return ((proc+" - not yet implemented!"));}
50 else{
51 PList exps; exps.puts("(");
52 for(int i=0;i<N;i++){
53 PList piece=pp.get(i);
54 string aux=eval(piece,env);
55 if(aux=="")aux=(piece.get(0)).elem(0);
56 exps.puts(aux);
57 }
58 exps.puts(")");
59 string pr=(exps.get(0)).elem(0);
60 vector<string>args;
61 for(int i=1;i<exps.size();i++)args.push_back((exps.get(i)).elem(0));
62 if(env.find(pr)!=env.end()) return env[pr].apply(args);
63 else{
64 return(("Error! Unbound variable: "+pr));
65 }
66 }
67 }
68 }Let’s see the above code in action:
1 schm >>>+
2 procedure +
3 schm >>>(+ 1 2)
4 3
5 schm >>>(+ 1 3 (- 10 5))
6 9
7 schm >>>(+ 0.5 0.786)
8 1.286
9 schm >>>(< 2 3)
10 #t
11 schm >>>"This is a test."
12 "This is a test."
13 schm >>>#\c
14 character type not yet implemented
15 schm >>>In the next article from these series, we will implement the main Scheme special forms: quote, if, set!, define, lambda and begin.
If you want to learn more about Scheme and interpreters in general I would recommend reading Structure and Interpretation of Computer Programs by H. Abelson, G. J. Sussman, J. Sussman:
If you are interested in learning more about the new C++11 syntax I would recommend reading Professional C++ by M. Gregoire, N. A. Solter, S. J. Kleper 2nd edition:
or, if you are a C++ beginner you could read C++ Primer (5th Edition) by S. B. Lippman, J. Lajoie, B. E. Moo.
