7
\$\begingroup\$

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;
}
\$\endgroup\$
3
\$\begingroup\$

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. :-|

\$\endgroup\$
  • \$\begingroup\$ "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? \$\endgroup\$ – Jaldhar Aug 30 '18 at 2:48
  • \$\begingroup\$ 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? \$\endgroup\$ – Jaldhar Aug 30 '18 at 2:54
  • \$\begingroup\$ 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. \$\endgroup\$ – Jaldhar Aug 30 '18 at 2:58
  • \$\begingroup\$ I've added some more content. \$\endgroup\$ – bipll Aug 30 '18 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.