main.cpp

#include <string>
#include <iostream>
#include <sstream>
#include <memory>
#include <stack>
#include <list>
#include <unordered_map>
#include <functional>

#define FORMAT(...) (static_cast<std::ostringstream&>(std::ostringstream() << __VA_ARGS__).str())

template<typename T>
static inline auto stackPop(T& _stack) { auto ret = _stack.top(); _stack.pop(); return ret; }

namespace lisp
{
	class Atom;
	class Cons;
	class Context;

	class Atom: public std::enable_shared_from_this<Atom>
	{
	public:
		typedef std::shared_ptr<Atom> Pointer;

		virtual void dump(std::ostream &_strm) const = 0;

		virtual Pointer eval(Context&) { return shared_from_this(); }

		virtual Pointer call(Context&, Cons *_args)
		{
			std::stringstream ss;
			ss << "can't execute '";
			dump(ss);
			ss << "'";
			throw std::runtime_error(ss.str());
		}
	};

	inline std::ostream& operator <<(std::ostream& _strm, Atom const& _atom)
	{
		_atom.dump(_strm);
		return _strm;
	}
	
	// Type implementations

	class Quote: public Atom
	{
	public:
		static inline Pointer create(Atom& _toQuote)
		{
			std::shared_ptr<Quote> ret = std::make_shared<Quote>();
			ret->m_quoted = _toQuote.shared_from_this();
			return ret;
		}

		virtual Pointer eval(Context&) override { return m_quoted->shared_from_this(); }

		virtual void dump(std::ostream &_strm) const override
		{
			_strm << '\'';
			m_quoted->dump(_strm);
		}

	private:
		Pointer m_quoted;
	};

	class Cons: public Atom
	{
	public:
		typedef std::shared_ptr<Cons> Pointer;

		inline Atom const *car() const { return m_car.get(); }
		inline Atom *car() { return m_car.get(); }
		inline Atom const *cdr() const { return m_cdr.get(); }
		inline Atom *cdr() { return m_cdr.get(); }
		
		static inline Pointer nil() { return std::make_shared<Cons>(); }
		static inline Pointer create(Atom* _car, Atom* _cdr)
		{
			Pointer ret = std::make_shared<Cons>();
			if(_car)
				ret->m_car = _car->shared_from_this();
			if(_cdr)
				ret->m_cdr = _cdr->shared_from_this();
			return ret;
		}
		
		virtual void dump(std::ostream &_strm) const override
		{
			if(!m_car && !m_cdr)
			{
				_strm << "nil";
				return;
			}

			_strm << '(';
			if(m_cdr && !dynamic_cast<Cons*>(m_cdr.get()))
			{
				m_car->dump(_strm);
				_strm << " . ";
				m_cdr->dump(_strm);
			}
			else for(Cons const *i = this; i; i = dynamic_cast<Cons*>(i->m_cdr.get()))
			{
				if(i != this)
					_strm << ' ';
				if(!i->car())
					break;
				i->car()->dump(_strm);
			}
			_strm << ')';
		}
		
		virtual Atom::Pointer eval(Context &_ctx) override;

		inline Pointer append(Atom& _append)
		{
			Pointer ret = std::make_shared<Cons>();
			Cons* last = nullptr;

			if(m_car)
			{
				for(Cons *i = this; i; i = dynamic_cast<Cons*>(i->m_cdr.get()))
				{
					if(last)
					{
						Pointer next = nil();
						next->m_car = i->m_car;
						last->m_cdr = next;
						last = next.get();
					}
					else
					{
						ret->m_car = i->m_car;
						last = ret.get();
					}
				}
			}
			
			if(last)
			{
				Pointer next = nil();
				next->m_car = _append.shared_from_this();
				last->m_cdr = next;
				last = next.get();
			}
			else
			{
				ret->m_car = _append.shared_from_this();
				last = ret.get();
			}

			return ret;
		}

	private:
		Atom::Pointer m_car;
		Atom::Pointer m_cdr;
	};

	class StringAtom: public Atom
	{
	public:		
		StringAtom(std::string &&_text)
			: m_str(std::move(_text))
		{}

		inline std::string const& str() const { return m_str; }

	protected:
		std::string m_str;
	};

	class String: public StringAtom
	{
	public:
		using StringAtom::StringAtom;

		static inline Pointer create(std::string &&_str)
		{
			return std::make_shared<String>(std::move(_str));
		}

		virtual void dump(std::ostream &_strm) const override
		{
			_strm << '"' << m_str << '"';
		}
	};

	class Symbol: public StringAtom
	{
	public:
		using StringAtom::StringAtom;
		
		static inline Pointer create(std::string &&_str)
		{
			return std::make_shared<Symbol>(std::move(_str));
		}

		virtual Pointer eval(Context&) override;

		virtual void dump(std::ostream &_strm) const override
		{
			_strm << m_str;
		}
	};

	class Number: public Atom
	{
	public:
		inline double numberValue() const { return m_number; }

		static inline Pointer create(double _value)
		{
			std::shared_ptr<Number> ret = std::make_shared<Number>();
			ret->m_number = _value;
			return ret;
		}

		virtual void dump(std::ostream &_strm) const override
		{
			_strm << m_number;
		}


	private:
		double m_number;
	};

	// State implementation
	
	class State;
	class Context;

	class Scope: public std::enable_shared_from_this<Scope>
	{
	public:
		typedef std::shared_ptr<Scope> Pointer;
		typedef std::unordered_map<std::string, Atom::Pointer> SymbolTable;

		inline Scope(State& _state)
			: m_state(&_state)
			, m_parent(nullptr)
		{}

		inline Scope(Scope& _parent)
			: m_state(_parent.m_state)
			, m_parent(&_parent)
		{}

		virtual Atom* lookup(Context &_ctx, std::string const& _name)
		{
			auto it = m_symbols.find(_name);
			if(it == m_symbols.end())
			{
				if(m_parent)
					return m_parent->lookup(_ctx, _name);
				return nullptr;
			}

			return it->second.get();
		}

		void set(std::string const& _name, Atom& _value)
		{
			m_symbols.insert(std::make_pair(_name, _value.shared_from_this()));
		}

		void clear(std::string const& _name)
		{
			m_symbols.erase(_name);
		}

	private:
		State* m_state;
		Scope* m_parent;
		SymbolTable m_symbols;
	};

	class State: public Scope
	{
	public:
		inline State()
			: Scope(*this)
		{}
	};

	class Context
	{
	public:
		typedef std::stack<Atom::Pointer> AtomStack;

		inline Context(Scope& _scope)
			: m_scope(&_scope)
		{}

		inline Scope* scope() const { return m_scope; }

		Atom::Pointer popTop()
		{
			if(m_stack.empty())
				return Cons::nil();
			return stackPop(m_stack);
		}

		int skipWhitespace(const char *const _start, const char *const _end)
		{
			int done = 0;
			while(isspace(_start[done]))
				done++;
			return done;
		}

		static inline bool isSymbolChar(char c, bool isStart)
		{
			if(isalpha(c))
				return true;

			if(!isStart && isdigit(c))
				return true;

			if(isspace(c))
				return false;

			if((c == '(')
				|| (c == ')'))
				return false;

			return true;
		}
		
		int parseList(const char *const _start, const char *const _end)
		{
			if(*_start != '(')
				throw std::runtime_error("expected '('");

			int done = 1;
			Cons::Pointer ret = Cons::nil();

			for(;;)
			{
				done += skipWhitespace(_start + done, _end);
				if(done >= (_end - _start))
					throw std::runtime_error("expected ')' before EOF");

				if(_start[done] == ')')
				{
					++done;
					break;
				}

				bool dot = false;

				if(_start[done] == '.')
				{
					if(!ret->car() || ret->cdr())
						throw std::runtime_error(FORMAT("expected exactly two elements for dot notation"));

					done++;
					dot = true;

					done += skipWhitespace(_start + done, _end);
				}

				done += parseAtom(_start + done, _end);

				if(dot)
					ret = Cons::create(ret->car(), stackPop(m_stack).get());
				else
					ret = ret->append(*stackPop(m_stack));
			}

			m_stack.push(ret);
			return done;
		}
		
		int parseNumber(const char *const _start, const char *const _end)
		{
			const char *ptr = _start;

			// minus
			bool const minus = (*ptr == '-');
			if(minus && (++ptr >= _end))
				throw std::runtime_error("expected number after minus");

			// integer part
			double value = 0;
			while((ptr < _end) && isdigit(*ptr))
				value = (value * 10) + (*ptr++ - '0');

			// decimal part
			if((ptr < _end) && (*ptr == '.'))
			{
				ptr++;
				double place = 0.1;
				while((ptr < _end) && isdigit(*ptr))
				{
					value += (*ptr++ - '0') * place;
					place *= 0.1;
				}
			}

			// exponent
			if((ptr < _end) && ((*ptr == 'e') || (*ptr == 'E')))
			{
				ptr++;
				double exp = 0;
				while((ptr < _end) && isdigit(*ptr))
					exp = (exp * 10) + (*ptr++ - '0');

				value *= pow(10, exp);
			}

			m_stack.push(Number::create(value));
			return ptr - _start;
		}
		
		int parseSymbol(const char *const _start, const char *const _end)
		{
			if(!isSymbolChar(*_start, true))
				throw std::runtime_error("expected symbol-char");
			
			std::string str;
			str.push_back(*_start);
			int const size = _end - _start;
			int done = 1;
			while((done < size) && isSymbolChar(_start[done], false))
			{
				str.push_back(_start[done]);
				done++;
			}

			m_stack.push(Symbol::create(std::move(str)));
			return done;
		}

		int parseQuote(const char *const _start, const char *const _end)
		{
			if(*_start != '\'')
				throw std::runtime_error("expected '''");
			int const done = parseAtom(_start + 1, _end) + 1;
			m_stack.push(Quote::create(*stackPop(m_stack)));
			return done;
		}

		int parseSymbolOrNumber(const char *const _start, const char *const _end)
		{
			if(isdigit(*_start))
				return parseNumber(_start, _end);

			bool hasDot = (*_start == '.');
			bool hasMinus = (*_start == '-') || hasDot;
			if(!hasMinus)
				return parseSymbol(_start, _end);

			int const size = _end - _start;
			for(int done = 1; done < size; ++done)
			{
				if(_start[done] == '.')
				{
					if(hasDot)
						return parseSymbol(_start, _end);

					hasDot = true;
				}
				else if(_start[done] == '-')
				{
					if(hasMinus)
						return parseSymbol(_start, _end);

					hasMinus = hasDot = true;
				}
				else if(isdigit(_start[done]))
					return parseNumber(_start, _end);
				else
					return parseSymbol(_start, _end);
			}

			return parseSymbol(_start, _end);
		}

		int parseAtom(const char *const _start, const char *const _end)
		{
			switch(*_start)
			{
			case '(':
				return parseList(_start, _end);

			case ')':
				throw std::runtime_error("unexpected ')'");

			case '\'':
				return parseQuote(_start, _end);

			default:
				return parseSymbolOrNumber(_start, _end);
			}
		}

		int exec(const char *const _start, const char *const _end)
		{
			Atom::Pointer ret;
			int const size = _end - _start;
			int done = 0;
			while(done < size)
			{
				done += skipWhitespace(_start + done, _end);
				if(done >= size)
					break;

				done += parseAtom(_start + done, _end);

				Atom::Pointer cmd = stackPop(m_stack);
				ret = cmd->eval(*this);
			}

			m_stack.push(ret);
			return done;
		}

		int exec(const char *const _start)
		{
			return exec(_start, _start + strlen(_start));
		}

		static Atom::Pointer parseAtom(State& _state, const char *const _start, const char * const _end)
		{
			Context ctx(_state);
			if(ctx.parseAtom(_start, _end) != (_end - _start))
				throw std::runtime_error("not all of string was consumed");
			return stackPop(ctx.m_stack);
		}
		
		static Atom::Pointer parseAtom(State& _state, const char *const _start)
		{
			return parseAtom(_state, _start, _start + strlen(_start));
		}

	private:
		Scope* m_scope;
		AtomStack m_stack;
	};

	Atom::Pointer Symbol::eval(Context &_ctx)
	{
		if(_ctx.scope())
		{
			if(Atom *fn = _ctx.scope()->lookup(_ctx, m_str))
				return fn->shared_from_this();
		}

		throw std::runtime_error(FORMAT("no such variable '" << m_str << "'"));
	}
	
	Atom::Pointer Cons::eval(Context &_ctx)
	{
		if(!m_car)
			return nil();

		Atom::Pointer fn = m_car->eval(_ctx);
		if(!fn)
			return fn;

		return fn->call(_ctx, dynamic_cast<Cons*>(m_cdr.get()));
	}

	// Internal types
	
	class Function: public Atom
	{
	public:
		typedef std::shared_ptr<Function> Pointer;

		inline Function(Scope &_scope, Cons* _args, Cons* _body)
			: m_scope(_scope.shared_from_this())
			, m_args(_args ? std::dynamic_pointer_cast<Cons>(_args->shared_from_this()) : nullptr)
			, m_body(_body ? std::dynamic_pointer_cast<Cons>(_body->shared_from_this()) : nullptr)
		{}

		static Pointer create(Scope &_scope, Cons* _args, Cons* _body)
		{
			return std::make_shared<Function>(_scope, _args, _body);
		}

		static Pointer create(Scope &_scope, Cons &_args)
		{
			Cons *args = dynamic_cast<Cons*>(_args.car());
			Cons *body = dynamic_cast<Cons*>(_args.cdr());
			return create(_scope, args, body);
		}

		virtual void dump(std::ostream &_strm) const override
		{
			_strm << "(lambda (";
			for(Cons *arg = m_args.get(); arg; arg = dynamic_cast<Cons*>(arg->cdr()))
			{
				if(!arg->car())
					break;
				arg->car()->dump(_strm);
			}
			_strm << ")";

			for(Cons *body = m_body.get(); body; body = dynamic_cast<Cons*>(body->cdr()))
			{
				_strm << " ";
				body->car()->dump(_strm);
			}

			_strm << ")";
		}

		virtual Atom::Pointer call(Context &_ctx, Cons *_args) override
		{
			Scope::Pointer myScope = std::make_shared<Scope>(*m_scope);
			Context fnContext(*myScope);

			Atom::Pointer ret;

			if(_args)
			{
				Cons* argName = m_args.get();
				
				for(Cons* argValue = dynamic_cast<Cons*>(_args); argValue; argValue = dynamic_cast<Cons*>(argValue->cdr()))
				{
					if(!argName)
						throw std::runtime_error("too many arguments");

					Symbol *name = dynamic_cast<Symbol*>(argName->car());
					if(!name)
						throw std::runtime_error("arg names must be names");

					myScope->set(name->str(), *argValue->car()->eval(_ctx));

					argName = dynamic_cast<Cons*>(argName->cdr());
				}
			}

			for(Cons *i = m_body.get(); i; i = dynamic_cast<Cons*>(i->cdr()))
				ret = i->car()->eval(fnContext);

			return ret;
		}

		Cons::Pointer m_args;
		Cons::Pointer m_body;
		std::shared_ptr<Scope> m_scope;
	};

	class CFunction: public Atom
	{
	public:
		typedef std::function<Pointer(Context&, Cons*)> Function;

		inline CFunction(Function &&_fn)
			: m_fn(_fn)
		{}

		static Pointer create(Function &&_fn)
		{
			return std::make_shared<CFunction>(std::move(_fn));
		}

		virtual void dump(std::ostream &_strm) const override
		{
			_strm << "<built-in>";
		}
		
		virtual Atom::Pointer call(Context &_ctx, Cons *_args) override
		{
			return m_fn(_ctx, _args);
		}

	private:
		Function m_fn;
	};
}

int main(int _argc, char **_argv)
{
	try
	{
		std::shared_ptr<lisp::State> state = std::make_shared<lisp::State>();
		
		state->set("lambda", *lisp::CFunction::create([](lisp::Context &_ctx, lisp::Cons *_args) -> lisp::Atom::Pointer {
			if(!_args)
				return lisp::Cons::nil();

			return lisp::Function::create(*_ctx.scope(), *_args);
		}));

		state->set("define", *lisp::CFunction::create([](lisp::Context &_ctx, lisp::Cons *_args) -> lisp::Atom::Pointer {
			if(!_args)
				return lisp::Cons::nil();
			
			lisp::Cons *nextArg = dynamic_cast<lisp::Cons*>(_args->cdr());
			lisp::Symbol *var = dynamic_cast<lisp::Symbol*>(_args->car());

			if(var && nextArg)
				_ctx.scope()->set(var->str(), *lisp::Function::create(*_ctx.scope(), *nextArg));

			return lisp::Cons::nil();
		}));

		state->set("setq", *lisp::CFunction::create([](lisp::Context &_ctx, lisp::Cons *_args) -> lisp::Atom::Pointer {
			if(!_args)
				return lisp::Cons::nil();

			lisp::Cons *nextArg = dynamic_cast<lisp::Cons*>(_args->cdr());

			lisp::Symbol *var = dynamic_cast<lisp::Symbol*>(_args->car());
			lisp::Atom *value = nextArg ? nextArg->car() : nullptr;

			if(var && value)
				_ctx.scope()->set(var->str(), *value->eval(_ctx));
			else if(var)
				_ctx.scope()->clear(var->str());

			return lisp::Cons::nil();
		}));

		state->set("quote", *lisp::CFunction::create([](lisp::Context &_ctx, lisp::Cons *_args) -> lisp::Atom::Pointer {
			if(!_args)
				return lisp::Cons::nil();

			return lisp::Quote::create(*_args->car());
		}));
		
		state->set("read", *lisp::CFunction::create([](lisp::Context &_ctx, lisp::Cons *_args) -> lisp::Atom::Pointer {
			std::string line;
			std::cout << ">>> ";
			std::getline(std::cin, line);

			return lisp::String::create(std::move(line));
		}));

		state->set("eval", *lisp::CFunction::create([](lisp::Context &_ctx, lisp::Cons *_args) -> lisp::Atom::Pointer {
			if(!_args || !_args->car())
				return lisp::Cons::nil();
			std::shared_ptr<lisp::String> str = std::dynamic_pointer_cast<lisp::String>(_args->car()->eval(_ctx));
			if(!str)
				return _args->car()->shared_from_this();

			std::string const& cmd = str->str();

			lisp::Context evalCtx(*_ctx.scope());
			evalCtx.exec(cmd.data(), cmd.data() + cmd.size());

			return evalCtx.popTop();
		}));

		state->set("print", *lisp::CFunction::create([](lisp::Context &_ctx, lisp::Cons *_args) -> lisp::Atom::Pointer {
			while(_args)
			{
				_args->car()->eval(_ctx)->dump(std::cout);

				_args = dynamic_cast<lisp::Cons*>(_args->cdr());
			}
			
			std::cout << std::endl;
			return lisp::Cons::nil();
		}));

		state->set("loop", *lisp::CFunction::create([](lisp::Context &_ctx, lisp::Cons *_args) -> lisp::Atom::Pointer {
			for(;;)
			{
				for(lisp::Cons *cmd = _args; cmd; cmd = dynamic_cast<lisp::Cons*>(cmd->cdr()))
					cmd->car()->eval(_ctx);
			}
		}));

		state->set("nil", *lisp::Cons::nil());

		lisp::Context context(*state);

		while(std::cin)
		{
			try
			{
				context.exec("(loop (print (eval (read))))");
			}
			catch(std::exception _exc)
			{
				std::cout << "error: " << _exc.what() << "." << std::endl;
			}
		}

		return 0;
	}
	catch(std::exception _exc)
	{
		std::cout << "error: " << _exc.what() << "." << std::endl;
	}
	catch(...)
	{
		std::cout << "error: unknown exception occurred." << std::endl;
	}

	return -1;
}