Implementing Scheme in C++ - Special forms
Posted on November 21, 2011 by Paul
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() == "procedure" && 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("Error! Unbound variable: " + 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.
