simple interpreter used TCO, inspired by @Belleve's version

interpreter.cpp

/*
 * simple interpreter
 * @author youxi
 * @email  pwq1989@gmail.com
 */
#include <iostream>
#include <time.h>
#include <stdlib.h>

#include "interpreter.h"


using namespace std;

//////////////////////////////////
// primitive function

ENV initPrimitive() {
	ENV env(new map<std::string,Value>());

	// function(x,y,k) {return k(x+y);}
	env->insert(make_pair("+",
			Value(ClosureMake([](ValueList args) -> CResult {
				const auto k = args[2].closure;
				const auto x = args[0].number;
				const auto y = args[1].number;
				ValueList result;
				result.push_back(Value(x + y));
				return k->operator()(result);
			}))));
	// function(x,y,k) {return k(x>y);}
	env->insert(make_pair(">",
			Value(ClosureMake([](ValueList args) -> CResult {
				const auto k = args[2].closure;
				const auto x = args[0].number;
				const auto y = args[1].number;
				ValueList result;
				result.push_back(Value((x > y) ? 1 : 0));
				return k->operator()(result);
			}))));
	// function(x,y,k) {return k(x<y);}
	env->insert(make_pair("<",
			Value(ClosureMake([](ValueList args) -> CResult {
				const auto k = args[2].closure;
				const auto x = args[0].number;
				const auto y = args[1].number;
				ValueList result;
				result.push_back(Value((x < y) ? 1 : 0));
				return k->operator()(result);
			}))));
	// function(x,k) {print(x);return k(x);}
	env->insert(make_pair("print",
			Value(ClosureMake([](ValueList args) -> CResult {
				const auto k = args[1].closure;
				auto x = args[0];
				x.show();
				ValueList result;
				result.push_back(Value(x));
				return k->operator()(result);
			}))));
	env->insert(make_pair("begin",
			Value(ClosureMake([](ValueList args) -> CResult {
				const auto k = args[args.size()-1].closure;
				const auto x = args[args.size()-2];
				ValueList result;
				result.push_back(Value(x));
				return k->operator()(result);
			}))));
	return env;
}


class Chunk {
public:
	ClosurePtr     f;
	ClosurePtr     k;
	ValueList      args;
	bool           isEnd;

	void reset(ClosurePtr f_, ClosurePtr k_, ValueList args_) {
        f = f_;
        k = k_;
        args = args_;
        isEnd = false;
	}

	void evaluate() {
		while (!isEnd) {
			isEnd = true;
			while (k->isReturn || k->ori.get() != NULL) {
				k = k->ori;
			}
			Value k1(k);
			args.push_back(k1);

			f->operator()(args);
		}
	}
};

// store expressions which will be evaluted
Chunk chunk;

//set k is returning
ClosurePtr Returning(ClosurePtr k) {
	auto k1 = ClosureMake([=](ValueList args){
		return k->operator()(args);
	});
	k1->setIsReturning(true);
	k1->setOri(k);
	return k1;
}

// forward declare
Value interpret(ASTNodePtr c, ENV e, ClosurePtr k);

// evaluted expression
Value interpretE(ASTNodePtr c, ENV e, ClosurePtr k) {
	if (c->nodelist.size() == 0) {
		ValueList args;
		//args.push_back(Value::NIL());
		return k->operator()(args);
	} else {
		return interpret(c->get(0), e, ClosureMake(
				[=](ValueList args0) {
					return interpretE(c->slice(1), e, ClosureMake(
							[=](ValueList args) {
								ValueList term(args0);
								for (auto v:args) {
									term.push_back(v);
								}
								return k->operator()(term);
							}));
				}));
	}
}

// interpret AST
Value interpret(ASTNodePtr c, ENV e, ClosurePtr k) {
	// e.g. root is 'x' ,user define
	if (c->isSymbol()) {
		ValueList args;
		args.push_back(e->operator[](c->getSymbol()));
		return k->operator()(args);
	} else if (c->isExpression()) {
		switch (c->get(0)->type) {
		case ASTBaseNode::IF: {
			return interpret(c->get(1), e, ClosureMake(
					[=](ValueList args) {
						auto test = args[0].number;
						if(test) {
							return interpret(c->get(2), e, k);
						} else if (c->get(3)) {
							return interpret(c->get(3), e, k);
						} else {
							ValueList args2;
							//args2.push_back(Value::NIL());
							return k->operator()(args2);
						}
					}));
			break;
		}
		case ASTBaseNode::LAMBDA: {
			auto params = c->get(1);
			auto body = c->get(2);
			Value func = Value(ClosureMake([=](ValueList args){
					ENV e_(new map<std::string,Value>(*e));
					//set new symbols note: -1 because of last arg is continuaton
					assert(params->nodelist.size() == args.size()-1);
					for (size_t i = 0; i < args.size()-1; ++i) {
						e_->operator[](params->get(i)->getSymbol()) = args[i];
					}
					auto k0 = Returning(args[args.size()-1].closure);
					return interpret(body, e_, k0);
				}));
            ValueList argsk;
            argsk.push_back(func);
			return k->operator()(argsk);
			break;
		}
		case ASTBaseNode::SET: {
		    return interpret(c->get(2), e, ClosureMake(
			    	[=](ValueList args) {
			    		auto v = args[0];
			    		e->operator[](c->get(1)->getSymbol()) = v;
			    		return k->operator()(args);
			    	}));
			break;
		}
		default: {
		    return interpretE(c, e, ClosureMake(
		    		[=](ValueList args) {
		    			// get function from args
		    			// f is in index 0, other is args for f
		    			auto f_ = args[0].closure;
		    			args.erase(args.begin());
		    			auto args_(args);
		    			chunk.reset(f_, k, args_);
		    			return Value::NIL();
		    		}));
		}
		} // end of switch
	} else {
		//c type is number
		ValueList args;
		args.push_back(Value(c->getNumber()));
		return k->operator()(args);
	}

}

int main() {
	cout << "start ..." << endl;
	clock_t start, end;
	const char* script =
	R"(['begin',
		['set', 'sum', ['lambda', ['low', 'hi', 'acc'],
			['if', ['<', 'low', 'hi'],
				['sum', ['+', 'low', 1], 'hi', ['+', 'low', 'acc']],
				['+', 'acc', 'low']]]],
		['sum', 0, 1000, 0]
	])";

	ASTBaseNode::NodePtr ast(new ExpressionNode());
	Parser::parse(ast, const_cast<char**>(&script));

	auto k = ClosureMake([=](ValueList args){
		args[0].show();
		return Value::NIL();
	});

	ENV e = initPrimitive();

	start = clock();
	auto root = ast->get(0);
	interpret(root, e, k);

	chunk.evaluate();

	end = clock();
	cout << "use " << (double)(end - start) / CLOCKS_PER_SEC << "s " << endl;
	return 0;
}

interpreter.h

/*
 * simple interpreter
 * @author youxi
 * @email  pwq1989@gmail.com
 */

#ifndef LAMBDA_H_INCLUDED
#define LAMBDA_H_INCLUDED
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include <string>
#include <functional>
#include <vector>
#include <memory>
#include <iostream>
#include <map>

/////////////////////////

typedef uint64_t Number;

class ASTBaseNode {
public:
	enum Type {
		EXPRESSION = 0,
		SYMBOL,
		NUMBER,
		IF,
		SET,
		LAMBDA,
		NIL
	};
	typedef std::shared_ptr<ASTBaseNode> NodePtr;
	typedef std::vector<NodePtr> NodeList;

	Type      type;
	NodeList  nodelist;

	ASTBaseNode() {}

	ASTBaseNode(NodeList list)
		: nodelist(list) {
		type = EXPRESSION;
	}

	NodePtr operator[](int idx) {
		int len = nodelist.size();
		if (idx < len) {
			return nodelist[idx];
		} else {
			return NULL;
		}
	}

	NodePtr get(int idx) {
		int len = nodelist.size();
		if (idx < len) {
			return nodelist[idx];
		} else {
			return NULL;
		}
	}

	NodePtr getlast() {
		return nodelist[nodelist.size() - 1];
	}

	virtual NodePtr slice(int n) {
		int len = nodelist.size();
		NodeList list;
		for (int i = n; i < len; ++i) {
			list.push_back(nodelist[i]);
		}
		return NodePtr(new ASTBaseNode(list));
	}

	bool isNumber() {
		return type == NUMBER;
	}
	bool isSymbol() {
		return type == SYMBOL;
	}
	bool isExpression() {
		return type == EXPRESSION;
	}

	virtual std::string getSymbol() { return std::string();};
	virtual Number getNumber() { return -1;};

	// for debug
	virtual void show(int level) {
	    using namespace std;
		cout << level << ":  ";
		cout << type << endl;
		for (auto node:nodelist) {
			node->show(level + 1);
		}
	}

};

typedef ASTBaseNode::NodePtr ASTNodePtr;

class SymbolNode : public ASTBaseNode {
public:
	SymbolNode(std::string s)
		: value(s) {
		type = ASTBaseNode::SYMBOL;
	}
	std::string value;
    virtual std::string getSymbol() {
		return value;
	}
};

class NumberNode : public ASTBaseNode {
public:
	NumberNode(Number v)
		: value(v) {
		type = ASTBaseNode::NUMBER;
	}
	Number value;
	virtual Number getNumber() {
		return value;
	}
};

class ExpressionNode : public ASTBaseNode {
public:
	ExpressionNode() {
		type = ASTBaseNode::EXPRESSION;
	}
};

////////////////////////
class Value;
//class CResult {};
typedef Value CResult;


template <typename Ret, typename ...Arg>
class ClosureBase {
public:
	typedef std::shared_ptr<ClosureBase<Ret,Arg...>> CPtr;

	ClosureBase()
		: isReturn(false),
		  ori(NULL) {
	}

	bool       isReturn;
	CPtr       ori;

	void setIsReturning(bool flag) {
		isReturn = flag;
	}

	void setOri(CPtr clz) {
		this->ori = clz;
	}

	virtual Ret operator()(Arg... arg) = 0;
};


template <typename Lambda, typename TResult, typename ...TArgs>
class Closure : public ClosureBase<TResult,TArgs...> {
public:
        typedef Closure<Lambda,TResult,TArgs...> ClosureSelf;
        Closure(Lambda lambda)
		: f_(lambda) {
        }

        Closure(ClosureSelf&& goner)
    	    : f_(std::move(goner.f_)) {
        }

    	Closure(const ClosureSelf &rhs)
    		: f_(rhs.f_) {
    	}

    	// should have some other functons..

    	Lambda f_;

    	TResult operator()(TArgs... arg) {
		return f_(arg...);
	 }
private:
	Closure() = delete;
};

template<typename Lambda, typename TMethod>
struct ClosureTyper
{
	typedef void LambdaType;
	typedef void ClosureBaseType;
	typedef void ClosureType;
};

template<typename Lambda, typename TClass, typename TResult, typename ...TArgs>
struct ClosureTyper<Lambda, TResult(TClass::*)(TArgs...)> {
	typedef TResult LambdaType(TArgs...);
	typedef ClosureBase<TResult, TArgs...> ClosureBaseType;
	typedef Closure<Lambda, TResult, TArgs...> ClosureType;
};

template<typename Lambda, typename TClass, typename TResult, typename ...TArgs>
struct ClosureTyper<Lambda, TResult(TClass::*)(TArgs...) const> {
	typedef TResult LambdaType(TArgs...);
	typedef ClosureBase<TResult, TArgs...> ClosureBaseType;
	typedef Closure<Lambda, TResult, TArgs...> ClosureType;
};

template<typename TLambda>
std::shared_ptr<typename ClosureTyper<TLambda, decltype(&TLambda::operator())>::ClosureBaseType> ClosureMake(TLambda lambda) {
    std::shared_ptr<typename ClosureTyper<TLambda, decltype(&TLambda::operator())>::ClosureBaseType> ptr(new typename ClosureTyper<TLambda, decltype(&TLambda::operator())>::ClosureType(lambda));
	return ptr;
}


typedef std::vector<Value> ValueList;
typedef ClosureBase<CResult,ValueList> CommonClosure;

typedef std::shared_ptr<CommonClosure> ClosurePtr;
typedef std::shared_ptr<std::map<std::string,Value>> ENV;

enum VType {
	NUMBER = 0,
	STRING,
	CLOSURE,
	ENVIRNMENT,
	CODE,
	NIL
};

class Value {
public:
	VType type;
	// should use some trick to save memory, but I'm lazy..
	uint64_t         number;
	std::string      str;
	ClosurePtr       closure;
	ENV              env;
	ASTNodePtr       node;


	Value() {}
	Value(const Value& rhs)
		: type(rhs.type),
		  number(rhs.number),
		  str(rhs.str),
		  closure(rhs.closure),
		  env(rhs.env),
		  node(rhs.node) {

	}

	static Value NIL() {
		return Value();
	}

	Value(uint64_t num): number(num) { type = VType::NUMBER; }
	Value(const std::string& s): str(s) { type = VType::STRING; }
	Value(const ClosurePtr& ptr): closure(ptr) { type = VType::CLOSURE; }
	Value(const ENV& e): env(e) { type = VType::ENVIRNMENT; }
	Value(const ASTNodePtr& n): node(n) { type = VType::CODE; }

    	Value(Value&& goner) = default;

	Value& operator=(const Value& rhs) {
		number = rhs.number;
		str = rhs.str;
		closure = rhs.closure;
		env = rhs.env;
		node = rhs.node;
		type = rhs.type;
		return *this;
	}

	void show() {
		switch (type) {
		case VType::NUMBER:
			std::cout << number << std::endl;
			break;
		case VType::STRING:
			std::cout << str << std::endl;
			break;
		case VType::CLOSURE:
			std::cout << "closure<CResult(ValueList)> ..." << std::endl;
			break;
		case VType::ENVIRNMENT:
			std::cout << "envirnment ..." << std::endl;
			break;
		case VType::CODE:
			std::cout << "source code ...." << std::endl;
			break;
		default:
			std::cout << "other..." << std::endl;
		}
	}

	CResult operator()(ValueList args) {
		return closure->operator()(args);
	}

};


////////////////////////////////////////////
/// parser
#define CODEEOF 0
#define NORMAL 1
class Parser {
public:
	static int parse(ASTNodePtr root, char** src) {
		if(**src == '\0') {return CODEEOF;}
		skipSpace(src);
		while (**src != ']') {
			skipSpace(src);
			if (**src == '[') {
				root->nodelist.push_back(ASTNodePtr(new ExpressionNode()));
				++*src;
				parse(root->getlast(), src);
			}
			if (**src == '\0') {
				return CODEEOF;
			}
			if (**src == ',') {
				++*src;
				skipSpace(src);
			} else if (**src == '\'') {
				++*src;
				parseSymbol(root, src);
			} else if (**src >= '0' && **src <= '9') {
				parseNumber(root, src);
			} else {
				++*src;
			}
		}
		//++*src;
		skipSpace(src);
		return NORMAL;
	}

private:
	static int parseSymbol(ASTNodePtr root, char** src) {
		std::string symbol;
		while (**src != '\'') {
			symbol.append(1,**src);
			++*src;
		}
		auto ptr = ASTNodePtr(new SymbolNode(symbol));
		if (symbol == "if") {
			ptr->type = ASTBaseNode::Type::IF;
		} else if (symbol == "lambda") {
			ptr->type = ASTBaseNode::Type::LAMBDA;
		} else if (symbol == "set") {
			ptr->type = ASTBaseNode::Type::SET;
		} else {
			ptr->type = ASTBaseNode::Type::SYMBOL;
		}
		root->nodelist.push_back(ptr);

		++*src;
		return NORMAL;
	}

	static int parseNumber(ASTNodePtr root, char** src) {
		assert(**src >= '0' && **src <= '9');
		Number value = atoi(*src);
		root->nodelist.push_back(ASTNodePtr(new NumberNode(value)));
		while (**src >= '0' && **src <= '9') {
			++*src;
		}
		return NORMAL;
	}

	static int skipSpace(char** src) {
		if(**src == '\0') {
			return CODEEOF;
		}
		while (!((**src >= 'a' && **src <= 'z')
			  || (**src >= 'A' && **src <= 'Z')
			  || (**src >= '0' && **src <= '9')
			  || (**src == ']') || (**src == '[')
			  || (**src == '\'') || (**src == ','))) {
			if(**src == '\0') {
				return CODEEOF;
			} else {
				++*src;
			}
		}
		return NORMAL;
	}

};


#endif // LAMBDA_H_INCLUDED