Solarian Programmer

My programming ramblings

Implementing Scheme in C++ - Special forms

Posted on November 21, 2011 by Sol

The code for this article is on GitHub: https://github.com/sol-prog/schm.

In my last post I’ve started to implement a Scheme interpreter in C++. This article continues with the implementation of six Scheme special forms: quote, if, set!, define, lambda and begin.

I’m not, currently, interested in the interpreter’s performance, but rather in the clarity of the implementation. The first version of the interpreter, the one presented in my last post, was not particularly well structured, this article presents a completely restructured code and a working version of Scheme. I’m sure there are bugs in my implementation and probably memory leaks.

The first version of the interpreter was able to do simple arithmetic calculations and return the results of evaluating an s-expression as a C++ string. Because now we aim to be able to create Scheme variables and procedures, the eval function was changed accordingly. The eval function will now return a Cell object that can store a variable value or a Scheme procedure:

Let’s see the new interpreter in action:

 1 schm >>>(define aa 10)
 2 schm >>>aa
 3 10
 4 schm >>>(define cube (lambda (x) (* x x x)))
 5 schm >>>(cube aa)
 6 1000
 7 schm >>>(define double (lambda (x) (* 2 x)))
 8 schm >>>(+ (cube (double aa)))
 9 8000
10 schm >>>
11 ; Recursive Fibonaci
12 (define fib4 (lambda (n)
13                (if (= n 0) 0
14                    (if (= n 1) 1
15                        (+ (fib4 (- n 1)) (fib4 (- n 2)))))))
16 schm >>>(fib4 2)
17 1
18 schm >>>(fib4 10)
19 55
20 schm >>>fib4
21 procedure fib4
22 schm >>>((lambda (x y) (+ x y)) 10 12)
23 22
24 schm >>>

If you want to have syntax highlighting, parentheses matching and automatic indentation when you run the interpreter you could access the schm executable from Emacs.

The new implementation of eval:

  1 Cell eval(PList &pp, Environment &env) {
  2     int N = pp.size();
  3     //Check for symbol, constant literal, procedure with no argument
  4     if (N == 1) {
  5         if (pp.elem(0) == "(" && pp.elem(pp.full_size() - 1) == ")") {
  6             PList aux = pp.get(0);
  7             string inp = aux.elem(0);
  8             for (int i = 1; i < pp.full_size() - 2; i++)inp = inp + pp.elem(i);
  9             //Check for procedure with no argument, e.g. (quit)
 10             if (env.find(inp) != env.end()) {
 11                 if (env[inp].get_kind() == &quot;procedure&quot; &amp;&amp; env[inp].check_native_procedure() == true) return env[inp].apply();
 12                 else return env[inp].get_value();
 13             } else {
 14                 return (("Error! Unbound variable: " + inp));
 15             }
 16         } else {
 17             string inp = pp.elem(0);
 18             //Check if character
 19             if (inp[0] == '#' && inp[1] == '\\')return Cell("character type not yet implemented");
 20             //Check if string
 21             if (inp[0] == '\"' && inp[inp.size() - 1] == '\"')return inp;
 22             //Check if number
 23             if (number(inp))return inp;
 24             //Check if variable or procedure
 25             if (env.find(inp) != env.end()) {
 26                 if (env[inp].get_kind() == "variable")return env[inp].get_value();
 27                 else {
 28                     if (show_err1_flag)cout << env[inp].get_kind() << " ";
 29                     show_err1_flag = true;
 30                     return inp;
 31                 }
 32             } else {
 33                 string res;
 34                 if (show_err2_flag)res = "Error! Unbound variable: " + inp;
 35                 show_err2_flag = true;
 36                 return res;
 37             }
 38         }
 39     } else {
 40         show_err1_flag = false;
 41         show_err2_flag = false;
 42         string proc;
 43         PList aux = pp.get(0);
 44         if (aux.size() == 1) proc = aux.elem(0);
 45         else {
 46             PList aux2 = aux.get(0);
 47             string tst = aux2.elem(0);
 48             if (tst == "lambda") {
 49                 Procedure anonymous = Procedure(aux);
 50                 //Collect the arguments of the lambda expression:
 51                 PList args;
 52                 args.puts("(");
 53                 for (int i = 1; i < N; i++) {
 54                     PList piece = pp.get(i);
 55                     string res = (eval(piece, env)).get_str();
 56                     args.puts(res);
 57                 }
 58                 args.puts(")");
 59                 return apply_proc(anonymous, args, env);
 60             } else {
 61                 proc = (eval(aux, env)).get_str();
 62             }
 63         }
 64         if (proc == "define") {
 65             if (pp.size() != 3)return Cell("Ill-formed special form: define");
 66             else {
 67                 string name = (pp.get(1)).elem(0);
 68                 PList value = pp.get(2);
 69                 Cell res = eval(value, env);
 70                 if (res.get_str() == "") {
 71                     Procedure prr = res.get_proc();
 72                     env[name] = prr;
 73                 } else {
 74                     string stt = res.get_str();
 75                     env[name] = stt;
 76                 }
 77                 return Cell("");
 78             }
 79         } else if (proc == "set!") {
 80             if (pp.size() != 3)return Cell("Ill-formed special form: set!");
 81             else {
 82                 string name = (pp.get(1)).elem(0);
 83                 if (env.find(name) == env.end()) {
 84                     return Cell("Error! Unbound variable: " + name);
 85                 }
 86                 PList value = pp.get(2);
 87                 string res = (eval(value, env)).get_str();
 88                 env[name] = res;
 89                 return Cell("");
 90             }
 91         } else if (proc == "quote") {
 92             if (pp.size() != 2)return Cell("Ill-formed special form: quote");
 93             else {
 94                 PList value = pp.get(1);
 95                 return value.toString();
 96             }
 97         } else if (proc == "if") {
 98             if (pp.size() == 3) {
 99                 PList cond = pp.get(1);
100                 PList if_true = pp.get(2);
101                 string aux = (eval(cond, env)).get_str();
102                 //If cond is a number evaluate the TRUE branch, if cond is a boolean evaluate accordingly
103                 if (number(aux))return eval(if_true, env);
104                 if (aux == "#t")return eval(if_true, env);
105                 else return Cell("");
106             }
107             if (pp.size() == 4) {
108                 PList cond = pp.get(1);
109                 PList if_true = pp.get(2);
110                 PList if_false = pp.get(3);
111                 string aux = (eval(cond, env)).get_str();
112                 //If cond is a number evaluate the TRUE branch, if cond is a boolean evaluate accordingly
113                 if (number(aux))return eval(if_true, env);
114                 if (aux == "#t")return eval(if_true, env);
115                 else return eval(if_false, env);
116             } else {
117                 return Cell("Ill-formed special form: if");
118             }
119         } else if (proc == "lambda") {
120             Procedure pr = Procedure(pp);
121             return pr;
122         } else if (proc == "begin") {
123             if (pp.size() < 2)return Cell("Ill-formed special form: begin");
124             string res;
125             for (int i = 1; i < pp.size(); i++) {
126                 PList aux = pp.get(i);
127                 res = (eval(aux, env)).get_str();
128             }
129             return res;
130         } else {
131             PList exps;
132             exps.puts("(");
133             for (int i = 0; i < N; i++) {
134                 PList piece = pp.get(i);
135                 string aux = (eval(piece, env)).get_str();
136                 if (aux == "")aux = (piece.get(0)).elem(0);
137                 exps.puts(aux);
138             }
139             exps.puts(")");
140             string pr = (exps.get(0)).elem(0);
141             vector<string>args;
142             for (int i = 1; i < exps.size(); i++)args.push_back((exps.get(i)).elem(0));
143             if (env.find(pr) != env.end()) {
144                 if (env[pr].check_native_procedure()) {
145                     return env[pr].apply(args);
146                 } else {
147                     Procedure prt = env[pr].get_proc();
148                     PList argss;
149                     argss.puts("(");
150                     for (int i = 1; i < N; i++) {
151                         PList piece = pp.get(i);
152                         string res = (eval(piece, env)).get_str();
153                         argss.puts(res);
154                     }
155                     argss.puts(")");
156                     return apply_proc(prt, argss, env);
157                 }
158 
159             } else {
160                 return Cell(&quot;Error! Unbound variable: &quot; + pr);
161             }
162         }
163     }
164 }

The above C++ implementation of eval is complete for quote, if, set!, define and begin. Currently, the lambda form is incomplete, it will work only with a defined number of inputs and any number of s-expressions for the body of the procedure. The user can use named or anonymous procedures with the interpreter.

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.

comments powered by Disqus