Peter Norvigs' lis.py in c++17

Question

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) {
            return token;
        }
        catch (std::out_of_range& e) {
            throw e;
        }
    }
    catch (std::out_of_range) {
        throw std::runtime_error(token + " is out of range");
    }
}

Expression read_from_tokens(std::list<std::string>& tokens) {
    if (tokens.size() == 0) {
        throw std::runtime_error("unexpected EOF");
    }

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

    if (token == "(") {
        List L;
        while (tokens.front() != ")") {
            L.push_back(read_from_tokens(tokens));
        }
        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);
    }

    return tokens;
}

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

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);
        }
    }

    catch(std::bad_any_cast& e) {
        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);
        }
    }

    catch(std::bad_any_cast& e) {
        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;
}

Answer 1

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>(
            std::deque{head}, 0, tail.data, tail.dataIdx)};
        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. :-|