Wednesday, September 15

A micro manual for Lisp in C++

It was with some interest that I read A Micro Manual for Lisp in C. One thing I have noticed about such efforts is that they are nearly always implemented in idiomatic C. I thought (out of idle curiosity, mainly) I'd see what a similar thing implemented in idomatic C++ would look like.


The main practical advantage that it offered in the end was the fact that boost::shared_ptr gave me rudimentary garbage collection for free. I used boost::variant to give me polymorphic lisp objects and thus did not have to use naked pointers anywhere, which seems to me to be an improvement in code safety. The price of this is a nosier syntax. You pay your money and you takes your choice..

As a concrete example here is what the implementation of CONS looked like.



boost::shared_ptr<lisp::object> fn_cons(boost::shared_ptr<lisp::object> args,
boost::shared_ptr<lisp::object> env) {

boost::shared_ptr<lisp::object> list = make_cons(car(args), boost::shared_ptr<lisp::object>());
args = car(cdr(args));

while ((args != NULL) && (args->which() == lisp::e_CONS)) {
append(list, car(args));
args = cdr(args);
}
return list;
}

Its probably also worth noting that avoiding naked pointers meant using boost::function for function objects, thusly..



enum kind {
e_ATOM = 0,
e_CONS,
e_FUNC,
e_LAMBDA
};

struct atom {
std::string name;

atom(const std::string& n) : name(n) {
}
};

struct cons {
boost::shared_ptr<object> car;
boost::shared_ptr<object> cdr;

cons(boost::shared_ptr<object> first, boost::shared_ptr<object> second) : car(first), cdr(second) {

}
};

typedef boost::function< boost::shared_ptr<object> (boost::shared_ptr<object>,boost::shared_ptr<object>) > lisp_func;

struct func {
lisp_func fn;

func(const lisp_func& f) : fn(f) {

}
};

struct lambda {
boost::shared_ptr<object> args;
boost::shared_ptr<object> sexp;

lambda(boost::shared_ptr<object> a, boost::shared_ptr<object> s) : args(a), sexp(s) {

}
};

typedef boost::variant< atom, cons, func, lambda > base_object;

And creating the environment like so...



boost::shared_ptr<lisp::object> init_env() {

boost::shared_ptr<lisp::object> nul;

boost::shared_ptr<lisp::object> a_quote(new lisp::object(std::string("QUOTE")));
boost::shared_ptr<lisp::object> f_quote(new lisp::object(fn_quote));

boost::shared_ptr<lisp::object> a_car(new lisp::object(std::string("CAR")));
boost::shared_ptr<lisp::object> f_car(new lisp::object(fn_car));

boost::shared_ptr<lisp::object> a_cdr(new lisp::object(std::string("CDR")));
boost::shared_ptr<lisp::object> f_cdr(new lisp::object(fn_cdr));

boost::shared_ptr<lisp::object> a_cons(new lisp::object(std::string("CONS")));
boost::shared_ptr<lisp::object> f_cons(new lisp::object(fn_cons));

boost::shared_ptr<lisp::object> a_equal(new lisp::object(std::string("EQUAL")));
boost::shared_ptr<lisp::object> f_equal(new lisp::object(fn_equal));

boost::shared_ptr<lisp::object> a_atom(new lisp::object(std::string("ATOM")));
boost::shared_ptr<lisp::object> f_atom(new lisp::object(fn_atom));

boost::shared_ptr<lisp::object> a_cond(new lisp::object(std::string("COND")));
boost::shared_ptr<lisp::object> f_cond(new lisp::object(fn_cond));

boost::shared_ptr<lisp::object> a_lambda(new lisp::object(std::string("LAMBDA")));
boost::shared_ptr<lisp::object> f_lambda(new lisp::object(fn_lambda));

boost::shared_ptr<lisp::object> a_label(new lisp::object(std::string("LABEL")));
boost::shared_ptr<lisp::object> f_label(new lisp::object(fn_label));


boost::shared_ptr<lisp::object> env = make_cons(make_cons(a_quote,make_cons(f_quote,nul)),nul);


append(env,make_cons(a_car, make_cons(f_car,nul)));
append(env,make_cons(a_cdr, make_cons(f_cdr,nul)));
append(env,make_cons(a_cons, make_cons(f_cons,nul)));
append(env,make_cons(a_equal, make_cons(f_equal,nul)));
append(env,make_cons(a_atom, make_cons(f_atom,nul)));
append(env,make_cons(a_cond, make_cons(f_cond,nul)));
append(env,make_cons(a_lambda, make_cons(f_lambda,nul)));
append(env,make_cons(a_label, make_cons(f_label,nul)));

boost::shared_ptr<lisp::object> a_tee(new lisp::object(std::string("#T")));
tee = a_tee;
nil = make_cons(nul,nul);

return env;
}