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
 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() == &quot;procedure&quot; &amp;&amp; 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(&quot;Error! Unbound variable: &quot; + 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 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.

blog comments powered by Disqus