# Peter Norvigs' lis.py in c++17

I wanted to try convert Peter Norvigs' Python Scheme interpreter to C++. I had tried this a few years before and failed abysmally but I saw that the latest C++ standard includes several features which might make things easier so I tried again. The tokenizing and parsing bits were easy but I struggled for a while with eval() until I had an epiphany and then that was straightforward to implement too.

I have several more features to add before the program is equivalent to the python version (e.g. a REPL, if, quote, set! and lambda, the rest of the standard environment) but I have enough to run the example program Norvig gives so I thought it would be an appropriate juncture to ask for a critique. Apart from the standard issues of style etc. there are some specific questions I'd like to ask.

• Is std::list the best choice for the List datatype? There are a couple of places where using operator[] would make the code a little easier to read but std::list doesn't provide that. On the other hand it seems that e.g std::deque or std::vector use more memory/have other features I don't need.

• Am I using std::any correctly? All that typeid-ing and casting seems a bit clunky to me. At least I wish there was some way to add a "tag" more comprehensible than the gibberish the compile provides as a type name. Would I be better off in the long run providing my own class to hold Scheme data types (perhaps a wrapper around std::any?) instead of using raw std:any?

• builtin functions in the Python version are very elegant thanks to that languages lambda operator. "Well C++ has lambdas now" I thought but I ran into some difficulty. It is easy to stuff a lambda into a std::any but getting it back out is another matter entirely. I think it is because each lambda gets a unique and essentially random type name so we won't know what to std::any_cast it to. Is this correct? My workaround was to wrap lambdas in a std::function which does have an identifiable type name. Is this the right way to do it?

• This one is minor but is M_PI standard C++ or not? It seems not to be but if you include cmath, g++ defines it without giving a warning.

#include <any>
#include <cmath>
#include <functional>
#include <iostream>
#include <list>
#include <sstream>
#include <stdexcept>
#include <string>
#include <typeinfo>
#include <unordered_map>

using Symbol = std::string;
using Expression = std::any;
using List = std::list<Expression>;
using Environment = std::unordered_map<Symbol, Expression>;
using Function = std::function<Expression(List&, Environment&)>;

Expression atom(const std::string& token) {
try {
auto result = stol(token);
return result;
}
catch (std::invalid_argument) {
try {
auto result = stod(token);
return result;
}
catch (std::invalid_argument) {
}
catch (std::out_of_range& e) {
throw e;
}
}
catch (std::out_of_range) {
throw std::runtime_error(token + " is out of range");
}
}

if (tokens.size() == 0) {
throw std::runtime_error("unexpected EOF");
}

auto token = tokens.front();
tokens.pop_front();

if (token == "(") {
List L;
while (tokens.front() != ")") {
}
tokens.pop_front(); // pop off ')'
return L;

} else if (token == ")") {
throw std::runtime_error("unexpected )");
} else {
return atom(token);
}
}

const std::list<std::string> tokenize(const std::string& str) {
std::string replaced;

for (auto& c: str) {
switch(c) {
case '(':
replaced.append(" ( ");
break;
case ')':
replaced.append(" ) ");
break;
default:
replaced.append(1, c);
}
}

std::istringstream stream(replaced);
std::list<std::string> tokens;
std::string token;

while (stream >> token) {
tokens.push_back(token);
}

}

Expression parse(const std::string& str) {
auto tokens = tokenize(str);
}

Expression eval(Expression exp, Environment& env) {

auto& type = exp.type();

try {
if (type == typeid(Symbol)) {
auto symbol = std::any_cast<Symbol>(exp);
try {
return env.at(symbol);
} catch (std::out_of_range&) {
throw std::runtime_error(symbol + " is undefined");
}

} else if (type == typeid(double)) {
return std::any_cast<double>(exp);

} else if (type == typeid(long)) {
return std::any_cast<long>(exp);

} else if (type == typeid(List)) {
auto list = std::any_cast<List>(exp);

auto proc = std::any_cast<Symbol>(list.front());
list.pop_front();

if (proc == "define") {
auto var = std::any_cast<Symbol>(list.front());
list.pop_front();
env[var] = eval(list.front(), env);
return {};
} else {

List args;
for (auto& arg: list) {
args.push_back(eval(arg, env));
}
return
std::invoke(std::any_cast<Function>(env[proc]), args, env);
}
} else {
std::string error{exp.type().name()};
error += " is an unknown type";
throw std::runtime_error(error);
}
}

std::string error{exp.type().name()};
error += " is the wrong type";
throw std::runtime_error(error);
}

return exp;
}

std::ostream& operator<<(std::ostream& out, const Expression& exp) {

auto& type = exp.type();

try {
if (type == typeid(Symbol)) {
out << std::any_cast<Symbol>(exp) << ' ';

} else if (type == typeid(double)) {
out << std::any_cast<double>(exp);

} else if (type == typeid(long)) {
out << std::any_cast<long>(exp);

} else if (type == typeid(List)) {
out << "[ ";
auto list = std::any_cast<List>(exp);
for (auto& item : list) {
out << item;
}
out << "] ";

} else {
std::string error{exp.type().name()};
error += " is an unknown type";
throw std::runtime_error(error);
}
}

std::string error{exp.type().name()};
error += " is the wrong type";
throw std::runtime_error(error);
}

return out;
}

auto number(Expression& exp) {
return exp.type() == typeid(double)
? std::any_cast<double>(exp)
: exp.type() == typeid(long)
? std::any_cast<long>(exp)
: throw std::runtime_error("not a number");
}

int main () {
std::string program{"(begin (define r 10) (* pi (* r r)))"};

Environment standard_env;

standard_env["begin"] = Function([](List& args, Environment&) -> Expression{
return args.back();
});

standard_env["*"] = Function([](List& args, Environment&) -> Expression {
auto a = number(args.front());
args.pop_front();
auto b = number(args.front());

return a * b;
});

standard_env["pi"] =  M_PI;

try {
std::cout << eval(parse(program), standard_env) << '\n';
}

catch (std::runtime_error& e) {
std::cerr << e.what() << '\n';
return EXIT_FAILURE;
}

return EXIT_SUCCESS;
}


Is std::list the best choice for the List datatype? There are a couple of places where using operator[] would make the code a little easier to read but std::list doesn't provide that. On the other hand it seems that e.g std::deque or std::vector use more memory/have other features I don't need.

Probably not. (cdr) returns a list, but std::list does not have tail, so, first, cdr defined on a std::list works in O(N), and more important, it returns a fresh distinct list, unlike Scheme's that would only return the second element of a pair. Same for cons. It would make more sense to either use true pairs, as they did fifty years ago, or pairs of iterators pointing inside a storage (which is idiomatic in STL.)

Would I be better off in the long run providing my own class to hold Scheme data types (perhaps a wrapper around std::any?) instead of using raw std:any?

Why not std::variant? Basically, there's but a few types in Scheme, and std::variant gives you type predicates for free.

My workaround was to wrap lambdas in a std::function which does have an identifiable type name. Is this the right way to do it?

Why do you call it a workaround? std::function is a longed function object finally standardized in C++ after so many years. It is exactly that: a first-class callable, something that is quite common in many languages but was not found in C++ stdlib years ago. Scheme's procedures are exactly that.

is M_PI standard C++ or not? It seems not to be but if you include cmath, g++ defines it without giving a warning.

It's an extension.

Recursive templates are quite possible, why not. They form the basis of CRTP after all. One drawback, you cannot make template alias recursive, the LHS of using-declaration cannot appear in its RHS; but distinct types can depend on themselves easily.

#include <variant>
#include <vector>

struct Tree: std::variant<int, std::vector<Tree>> {
using std::variant<int, std::vector<Tree>>::variant;
};

int main() {
Tree shallow{std::vector{Tree{42}, Tree{278}}};
}


With lists it would be somewhat harder to implement. of course, there is always an option to do it as before:

using Cons = std::pair<Expression, std::shared_ptr<Expression>>;


But to save some memory and processing time we can try to make it more complicated.

struct Chunk: std::enable_shared_from_this {
std::deque<Expression> storage;
int negative = 0; // amount of elements prepended
std::shared_ptr<Chunk> next;
int nextIdx;
};

struct List {
std::shared_ptr<Chunk> data;
int dataIdx;
};

List cons(Expression head, List tail) {
if(tail.dataIdx + tail.data->negative == 0) {
// tail starts with its chunk
List retVal{std::move(tail.storage), tail.index - 1};
--retVal.storage->negative;
return retVal;
};
else {
// tail starts somewhere inside the chunk
List retVal{std::make_shared<Chunk>(
return retVal;
}
}

Expression &car(List &l) { return l.data->storage[l.dataIdx]; }
Expression &cdr(List &l) {
if(l.dataIdx + l.data->negative == l.data->size() - 1) {
return List{l.data->next, l.data->next->negative};
}
return List{l.data, l.dataIdx + 1}
}


And so forth. This may take long to write down everything properly and consistently.

Anyway the real challenge starts when you start implementing call/cc. :-|

• "It would make more sense to either use true pairs, as they did fifty years ago, or pairs of iterators pointing inside a storage (which is idiomatic in STL. " You mean e.g. std::pair<Expression, Expression>? I'm having trouble visualizing what the pair of iterators version would look like. Can you go into more detail? – Jaldhar Aug 30 '18 at 2:48
• I did consider making Expression a std::variant originally but I rejected it because Expression has to be able to hold e.g. a List or Function and they are in turn defined in terms of Expressions and you can't have a recursive std::variant. Or can you? – Jaldhar Aug 30 '18 at 2:54
• Thanks for the feedback about std::function and M_PI. I use g++ 7.3.0 with the -std=c++17 and -pedantic -Wall options so I'm surprised the usage of M_PI did not get flagged. Any other suggestions you have about my code will be most welcome. – Jaldhar Aug 30 '18 at 2:58
• I've added some more content. – bipll Aug 30 '18 at 13:32