// scratch.cpp
// 

#include <stdexcept>
#include <iostream>
#include <string>
#include <deque>
#include <sstream>
#include <map>
#include <vector>

using namespace std;

// lexing ------------------------------------------------------------------- //
void replace (std::string &s, std::string from, std::string to) {
    int idx = 0;
    int next;
    while ((next = s.find (from, idx)) != std::string::npos) {
        s.replace (next, from.size (), to);
        idx = next + to.size ();
    } 
}

std::deque<std::string>& tokenize (std::string& s, std::deque<std::string>& result) {
    replace (s, "(", " ( ");
    replace (s, ")", " ) ");
    std::istringstream iss (s);
    result.insert (result.end (), std::istream_iterator<std::string> (iss),
		std::istream_iterator<std::string> ());
    return result;
}

template <typename T>
bool isNumber (std::string& s) {
	std::istringstream iss (s);
	T dummy;
	iss >> std::noskipws >> dummy;
	return iss && iss.eof ();
}

// ast  --------------------------------------------------------------------- //	
typedef double REAL;

class Sexpr;
class Environment;
typedef Sexpr* (*functor) (Sexpr*, Environment*);

enum SType {
	LIST,
	NUMBER,
	SYMBOL,
	LAMBDA,
	BUILTIN
};

struct Sexpr {
	Sexpr () { type = LIST; val = 0; lexeme = ""; tail.clear (); body = args = 0; env = 0; func = 0; }		
	Sexpr (REAL v) { type = NUMBER; val = v; lexeme = ""; tail.clear (); body = args = 0; env = 0; func = 0; }
	Sexpr (const std::string& lex) { type = SYMBOL; val = 0; lexeme = lex; tail.clear (); body = args = 0;  env = 0; func = 0; }
	Sexpr (Sexpr* b, Sexpr* a, Environment* e) { type = LAMBDA; val = 0; lexeme = ""; tail.clear (); body = b; args = a; env = e;  func = 0; }
	Sexpr (functor f) { type = BUILTIN; val = 0; lexeme = ""; tail.clear (); body = args = 0; env = 0; func = f; }
	
	SType type;
	REAL val;
	std::string lexeme;
	std::deque<Sexpr*> tail;
	Sexpr* body;
	Sexpr* args;
	Environment* env;
	functor func;
};

Sexpr nil ("nil");

struct EnvEntry {
	EnvEntry (const string& k, Sexpr* v) {
		key = k;
		val = v;
	}
	string key;
	Sexpr* val;
};

class Environment {
public:
	//typedef std::map<std::string, Sexpr*> env_t;
	typedef std::vector<EnvEntry*> env_t;
	
	Environment () : m_outer (0) {}
	Environment (Sexpr* params, Sexpr* args, Environment* outer) : m_outer (outer) {
        for (unsigned int i = 0; i < params->tail.size (); ++i) {
            //m_lookup[args->tail[i]->lexeme] = params->tail[i];
			m_lookup.push_back (new EnvEntry (args->tail[i]->lexeme, params->tail[i]));
        }
    }
	
	Sexpr* add (const std::string& key, Sexpr* val) {
		int pos = find (key);
		if (pos >= 0) m_lookup[pos]->val = val;
		else m_lookup.push_back (new EnvEntry (key, val));
		return val;
	}
	Sexpr* get (const std::string& key) {
		int pos = find (key);
		if (pos >= 0) return m_lookup[pos]->val;
		if (m_outer) return m_outer->get (key);
		
		throw std::runtime_error ("[get] symbol not found");
		return 0;
	}
	Sexpr* set (const std::string& key, Sexpr* val) {
		int pos = find (key);
		if (pos >= 0) {
			m_lookup[pos]->val = val;
			return val;
		}
		if (m_outer) return m_outer->set (key, val);
		
		throw std::runtime_error ("[set] symbol not found");
		return 0;
	}
	
private:
	int find (const std::string& key) {
		int pos = -1;
		for (size_t i = 0; i < m_lookup.size (); ++i) {
			if (m_lookup[i]->key == key) {
				pos = i;
				break;
			}
		}
	
		return pos;
	}
	
	env_t m_lookup;
	Environment* m_outer;
};

// parsing ------------------------------------------------------------------ //
Sexpr* atom (std::string& lexeme) {		
	if (isNumber<REAL> (lexeme)) {
		return new Sexpr (atof (lexeme.c_str ()));
	} else {
		return new Sexpr (lexeme);
	}
}

// return the expression in the given tokens
Sexpr* tail (std::deque<std::string>& tokens) {
	if (!tokens.size ()) return NULL;
	std::string lexeme (tokens.front ());
	tokens.pop_front ();
	if (lexeme == "(") {
		Sexpr* list = new Sexpr ();
		while (tokens.front() != ")") {			
			Sexpr* c = tail (tokens);
			list->tail.push_back (c);
		}
		tokens.pop_front ();
		return list;
	} else return atom (lexeme);
}

// evaluation --------------------------------------------------------------- //

Sexpr* eval (Sexpr* node, Environment* env) {
	if (node->type == SYMBOL) { return env->get (node->lexeme); }
	if (node->type == NUMBER) return node;
	if (node->tail.size () == 0) return &nil;
	
	if (node->tail[0]->type == SYMBOL)  {
		if (node->tail[0]->lexeme == "quote") return node->tail[1];
        if (node->tail[0]->lexeme == "if") return eval (eval (node->tail[1], env)->val == 0 ? (node->tail.size () < 4 ? &nil : node->tail[3]) : node->tail[2], env);
        if (node->tail[0]->lexeme == "set!") {
			return env->set (node->tail[1]->lexeme, eval (node->tail[2], env));
		}
        if (node->tail[0]->lexeme == "define") {
			return env->add (node->tail[1]->lexeme, eval (node->tail[2], env));
		}
		if (node->tail[0]->lexeme == "lambda") return new Sexpr (node->tail[2], node->tail[1], env);
        if (node->tail[0]->lexeme == "begin") {
            for (size_t i = 1; i < node->tail.size() - 1; ++i) eval (node->tail[i], env);
            return eval (node->tail[node->tail.size() - 1], env);
        }		
	}
	
	Sexpr* proc = eval (node->tail[0], env);
	Sexpr* params = new Sexpr (); // list
	for (unsigned int i = 1; i < node->tail.size (); ++i) {
		params->tail.push_back (eval (node->tail[i], env));
	}
	
	if (proc->type == LAMBDA) return eval (proc->body, new Environment (params, proc->args, proc->env));
	if (proc->type == BUILTIN) return proc->func (params, env);

	return &nil;
}


Sexpr* add (Sexpr* node, Environment* env) {
	REAL v = 0;
	
	for (unsigned int i = 0; i < node->tail.size (); ++i) {
		v += eval (node->tail[i], env)->val;
	}
	
	return new Sexpr (v);
}

Sexpr* sub (Sexpr* node, Environment* env) {
	REAL v = node->tail[0]->val;
	
	for (unsigned int i = 1; i < node->tail.size (); ++i) {
		v -= eval (node->tail[i], env)->val;
	}
	
	return new Sexpr (v);
}

// repl --------------------------------------------------------------------- //
void traverse (Sexpr* node, std::ostream& out) {
	if (node->type == LIST) {
		out << "( ";
		for (int  i = 0; i < node->tail.size (); ++i) {
			traverse (node->tail[i], out);
		}
		out << ") ";
	} else if (node->type == NUMBER) {
		out << node->val << " " ;
	} else if (node->type == SYMBOL) {
		out << node->lexeme << " ";
	} else if (node->type == LAMBDA) {
		out << "<Lambda " << node << ">" << " ";
	} else if (node->type == BUILTIN) {
		out << "<Builtin " << node << ">" << " ";
	}
}
	
void repl (Environment* env) {
	while  (true) {
		cout << ">> ";
		std::string tmp;
		getline (cin, tmp);
		if (!tmp.size ()) continue;
		std::deque<std::string> tokens;

		traverse (eval (tail (tokenize (tmp, tokens)), env), cout);
		std::cout << std::endl;
	}
}

int main (int argc, char* argv[]) {
	try {
		Environment env;
		env.add ("+", new Sexpr (&add));
		env.add ("-", new Sexpr (&sub));
		
		repl (&env);

	}
	catch (exception& e) {
		cout << "Error: " << e.what () << endl;
	}
	catch (...) {
		cout << "Fatal error: unknown exception" << endl;
	}
	return 0;
}

// EOF