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