/* Resp: A programming language
 * Copyright (C) 2008-2009 David Robillard <http://drobilla.net>
 *
 * Resp is free software: you can redistribute it and/or modify it under
 * the terms of the GNU Affero General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or (at your
 * option) any later version.
 *
 * Resp is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Affero General
 * Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with Resp.  If not, see <http://www.gnu.org/licenses/>.
 */

/** @file
 * @brief Interface and type definitions
 */

#ifndef RESP_HPP
#define RESP_HPP

#include <stdarg.h>
#include <stdint.h>
#include <string.h>

#include <cassert>
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#include <boost/format.hpp>

#define FOREACH(IT, i, c)  for (IT i = (c).begin(); i != (c).end(); ++i)
#define FOREACHP(IT, i, c) for (IT i = (c)->begin(); i != (c)->end(); ++i)
#define THROW_IF(cond, error, ...) { if (cond) throw Error(error, __VA_ARGS__); }

using namespace std;
using boost::format;

/***************************************************************************
 * Basic Utility Classes                                                   *
 ***************************************************************************/

/// Location in textual code
struct Cursor {
	Cursor(const string& n="", unsigned l=1, unsigned c=0) : name(n), line(l), col(c) {}
	operator bool() const { return !(line == 1 && col == 0); }
	string str() const { return (format("%1%:%2%:%3%") % name % line % col).str(); }
	string   name;
	unsigned line;
	unsigned col;
};

/// Compilation error
struct Error {
	Error(Cursor c, const string& m) : loc(c), msg(m) {}
	const string what() const { return (loc ? loc.str() + ": " : "") + "error: " + msg; }
	const Cursor loc;
	const string msg;
};


/***************************************************************************
 * Backend Types                                                           *
 ***************************************************************************/

typedef const void* CType; ///< Compiled type (opaque)
typedef void*       CVal;  ///< Compiled value (opaque)
typedef void*       CFunc; ///< Compiled function (opaque)


/***************************************************************************
 * Garbage Collection                                                      *
 ***************************************************************************/

struct Object;

/// Type tag for an AST node (must be even and > 1 since LSb is used as mark)
enum Tag {
	T_UNKNOWN = 2,
	T_BOOL    = 4,
	T_FLOAT   = 6,
	T_INT32   = 8,
	T_STRING  = 10,
	T_SYMBOL  = 12,
	T_LITSYM  = 14,
	T_TUPLE   = 16,
	T_TVAR    = 18
};

/// Garbage collector
struct GC {
	typedef std::list<const Object*> Roots;
	typedef std::list<Object*>       Heap;
	explicit GC(size_t pool_size);
	~GC();
	void* alloc(size_t size);
	void  collect(const Roots& roots);
	void  addRoot(const Object* obj) { assert(obj); _roots.push_back(obj); }
	void  lock() { _roots.insert(_roots.end(), _heap.begin(), _heap.end()); }
	const Roots& roots() const { return _roots; }
private:
	void* _pool;
	Heap  _heap;
	Roots _roots;
};

/// Garbage collected object (including AST and runtime data)
struct Object {
	struct Header {
		uint32_t tag; ///< Least significant bit is mark
	};

	inline Tag  tag()        const { return (Tag)((header()->tag >> 1) << 1); }
	inline void tag(Tag t)         { header()->tag = (t | (marked() ? 1 : 0)); }
	inline bool marked()     const { return (header()->tag & 1); }
	inline void mark(bool b) const {
		if (b)
			header()->tag |= 1;
		else
			header()->tag = ((header()->tag >> 1) << 1);
	}

	static void* operator new(size_t size)  { return pool.alloc(size); }
	static void  operator delete(void* ptr) {}

	// Memory used with placement new MUST always be allocated with pool.alloc!
	static void* operator new(size_t size, void* ptr) { return ptr; }

	static GC pool;

private:
	/// Always allocated with pool.alloc, so this - sizeof(Header) is a valid Header*.
	inline Header* header() const { return (Header*)((char*)this - sizeof(Header)); }
};


/***************************************************************************
 * Abstract Syntax Tree                                                    *
 ***************************************************************************/

struct TEnv; ///< Type-Time Environment
struct CEnv; ///< Compile-Time Environment
struct ATuple;
struct ASymbol;

class AST;
extern ostream& operator<<(ostream& out, const AST* ast);

/// Base class for all AST nodes
struct AST : public Object {
	AST(Tag t, Cursor c=Cursor()) : loc(c) { this->tag(t); }
	inline bool operator==(const AST& o) const;
	inline bool operator!=(const AST& rhs) const { return !(operator==(rhs)); }

	string str() const { ostringstream ss; ss << this; return ss.str(); }

	template<typename T>
	T* as_a(Tag t) const { assert(tag() == t); return (T*)this; }

	template<typename T>
	T* to_a(Tag t) const { return (tag() == t) ? (T*)this : NULL; }

	const ATuple*  as_tuple()  const { return as_a<const ATuple>(T_TUPLE); }
	const ATuple*  to_tuple()  const { return to_a<const ATuple>(T_TUPLE); }
	const ASymbol* as_symbol() const { return as_a<const ASymbol>(T_SYMBOL); }
	const ASymbol* to_symbol() const { return to_a<const ASymbol>(T_SYMBOL); }

	Cursor loc;
};

/// Literal value
template<typename T>
struct ALiteral : public AST {
	ALiteral(Tag tag, T v, Cursor c) : AST(tag, c), val(v) {}
	const T val;
};

/// String, e.g. ""a""
struct AString : public AST {
	AString(Cursor c, const string& s) : AST(T_STRING, c), cppstr(s) {}
	const string cppstr;
};

/// Symbol, e.g. "a"
struct ASymbol : public AST {
	const char* sym() const { return _sym; }
private:
	friend class PEnv;
	const char* _sym;
	ASymbol(const char* s, Cursor c) : AST(T_SYMBOL, c), _sym(s) {}
};

/// Tuple (heterogeneous sequence of fixed length), e.g. "(a b c)"
struct ATuple : public AST {
	explicit ATuple(Cursor c) : AST(T_TUPLE, c), _fst(0), _rst(0) {}
	ATuple(const ATuple& exp) : AST(T_TUPLE, exp.loc), _fst(exp._fst), _rst(exp._rst) {}

	ATuple(const AST* fst, const ATuple* rst, Cursor c=Cursor())
		: AST(T_TUPLE, c), _fst(fst), _rst(rst) {}

	inline const AST*    fst()   const { return _fst; }
	inline const ATuple* rst()   const { return _rst; }
	inline const AST*    frst()  const { return _rst->_fst; }
	inline const AST*    rrst()  const { return _rst->_rst; }
	inline const AST*    frrst() const { return _rst->_rst->_fst; }

	bool empty() const { return _fst == 0 && _rst == 0; }

	size_t list_len() const {
		size_t ret = 0;
		for (const_iterator i = begin(); i != end(); ++i, ++ret) {}
		return ret;
	}

	const AST* list_last() const {
		for (const_iterator i = begin(); i != end();) {
			const_iterator next = i;
			++next;

			if (next == end())
				return *i;

			i = next;
		}

		return NULL;
	}

	void last(ATuple* ast) { _rst = ast; }

	struct const_iterator {
		explicit inline const_iterator(const ATuple* n) : node(n) {}
		inline const_iterator& operator++() {
			node = node->rst();
			return *this;
		}
		inline const_iterator operator++(int) {
			const const_iterator ret(node);
			node = node->rst();
			return ret;
		}
		inline bool operator==(const const_iterator& i) const {
			return node == i.node;
		}
		inline bool operator!=(const const_iterator& i) const {
			return !operator==(i);
		}
		inline const AST* operator*() { return node->fst(); }
		const ATuple* node;
	};

	const_iterator begin() const { if (empty()) return end(); return const_iterator(this); }
	const_iterator end()   const { return const_iterator(NULL); }

	const_iterator iter_at(unsigned index) const {
		const_iterator i = begin();
		for (unsigned idx = 0; idx != index; ++i, ++idx) {
			assert(i != end());
		}
		return i;
	}

	const AST* list_ref(unsigned index) const { return *iter_at(index); }

	const ATuple* replace(const AST* from, const AST* to) const;

	const ATuple* prot() const { return list_ref(1)->as_tuple(); }

private:
	const AST*    _fst;
	const ATuple* _rst;
};

inline ATuple* tup(Cursor c, const AST* ast, ...) {
	ATuple* const head = new ATuple(ast, 0, c);
	if (!ast)
		return head;
	
	ATuple* tail = head;
	va_list args;
	va_start(args, ast);
	for (AST* a = va_arg(args, AST*); a; a = va_arg(args, AST*)) {
		ATuple* const tup = new ATuple(a, NULL);
		tail->last(tup);
		tail = tup;
	}
	va_end(args);

	return head;
}

static bool
list_contains(const ATuple* head, const AST* child) {
	if (!head)
		return false;

	if (*head == *child)
		return true;

	FOREACHP(ATuple::const_iterator, p, head) {
		if (**p == *child)
			return true;

		const ATuple* tup = (*p)->to_tuple();
		if (tup && list_contains(tup, child))
			return true;
	}

	return false;
}

inline bool
list_equals(const ATuple* lhs, const ATuple* rhs)
{
	if (lhs == rhs)
		return true;
	else if (!lhs || !rhs)
		return false;
	
	ATuple::const_iterator l = lhs->begin();
	FOREACHP(ATuple::const_iterator, r, rhs)
		if (!(*(*l++) == *(*r)))
			return false;
	return true;
}

struct AType {
	static inline bool is_var(const AST* type)  { return type->tag() == T_TVAR; }
	static inline bool is_name(const AST* type) { return type->tag() == T_SYMBOL; }
	static inline bool is_expr(const AST* type) { return type->tag() == T_TUPLE; }

	static inline uint32_t var_id(const AST* type) {
		assert(is_var(type));
		return ((ALiteral<int32_t>*)type)->val;
	}
};

// Utility class for easily building lists from left to right
struct List {
	explicit List(ATuple* h=0) : head(h), tail(0) {}
	List(Cursor c, const AST* ast, ...) : head(0), tail(0) {
		push_back(ast);
		assert(*head->begin() == ast);
		head->loc = c;
		va_list args;
		va_start(args, ast);
		for (const AST* a = va_arg(args, const AST*); a; a = va_arg(args, const AST*))
			push_back(a);
		va_end(args);
	}
	void push_back(const AST* ast) {
		assert(ast);
		if (!head) {
			head = new ATuple(ast, NULL, Cursor());
		} else if (!tail) {
			ATuple* node = new ATuple(ast, NULL, Cursor());
			head->last(node);
			tail = node;
		} else {
			ATuple* node = new ATuple(ast, NULL, Cursor());
			tail->last(node);
			tail = node;
		}
	}
	void push_front(const AST* ast) {
		head = new ATuple(ast, head, Cursor());
	}
	operator ATuple*() const { return head; }
	ATuple* head;
	ATuple* tail;
};

inline const ATuple*
ATuple::replace(const AST* from, const AST* to) const
{
	List copy;
	FOREACHP(const_iterator, i, this) {
		if (*i == from) {
			copy.push_back(to);
		} else {
			const ATuple* tup = (*i)->to_tuple();
			copy.push_back(tup ? tup->replace(from, to) : (*i));
		}
	}
	copy.head->loc = loc;
	return copy;
}

template<typename T>
inline bool
literal_equals(const ALiteral<T>* lhs, const ALiteral<T>* rhs)
{
	return lhs && rhs && lhs->val == rhs->val;
}


inline bool
AST::operator==(const AST& rhs) const
{
	const Tag tag = this->tag();
	if (tag != rhs.tag())
		return false;

	switch (tag) {
	case T_BOOL:
		return literal_equals((const ALiteral<bool>*)this, (const ALiteral<bool>*)&rhs);
	case T_FLOAT:
		return literal_equals((const ALiteral<float>*)this, (const ALiteral<float>*)&rhs);
	case T_INT32:
	case T_TVAR:
		return literal_equals((const ALiteral<int32_t>*)this, (const ALiteral<int32_t>*)&rhs);
	case T_TUPLE:
	{
		const ATuple* me = this->as_tuple();
		const ATuple* rt = rhs.to_tuple();
		return list_equals(me, rt);
	}
	case T_STRING:
		return ((AString*)this)->cppstr == ((AString*)&rhs)->cppstr;
	case T_SYMBOL:
	case T_LITSYM:
		return ((ASymbol*)this)->sym() == ((ASymbol*)&rhs)->sym(); // interned
	case T_UNKNOWN:
		return this == &rhs;
	}
	return false;
}


/***************************************************************************
 * Lexical Environmment                                                    *
 ***************************************************************************/

/// Lexical Environment
template<typename V>
struct Env : public list< vector< pair<const char*, V> > > {
	typedef vector< pair<const char*, V> > Frame;
	Env() : list<Frame>(1) {}
	virtual ~Env() {}
	virtual void push(Frame f=Frame()) { list<Frame>::push_front(f); }
	virtual void pop()                 { list<Frame>::pop_front(); }
	const V& def(const ASymbol* k, const V& v) {
		for (typename Frame::iterator b = this->begin()->begin(); b != this->begin()->end(); ++b)
			if (b->first == k->sym())
				return (b->second = v);
		this->front().push_back(make_pair(k->sym(), v));
		return v;
	}
	V* ref(const ASymbol* key) {
		for (typename Env::iterator f = this->begin(); f != this->end(); ++f)
			for (typename Frame::iterator b = f->begin(); b != f->end(); ++b)
				if (b->first == key->sym())
					return &b->second;
		return NULL;
	}
	bool contains(const Frame& frame, const ASymbol* key) const {
		for (typename Frame::const_iterator b = frame.begin(); b != frame.end(); ++b)
			if (b->first == key->sym())
				return true;
		return false;
	}
	bool topLevel(const ASymbol* key) const { return contains(this->back(), key); }
	bool innermost(const ASymbol* key) const { return contains(this->front(), key); }
};

template<typename V>
ostream& operator<<(ostream& out, const Env<V>& env) {
	out << "(Env" << endl;
	for (typename Env<V>::const_reverse_iterator f = env.rbegin(); f != env.rend(); ++f) {
		out << "  (" << endl;
		for (typename Env<V>::Frame::const_iterator b = f->begin(); b != f->end(); ++b)
			cout << "    " << b->first << " " << b->second << endl;
		out << "  )" << endl;
	}
	out << ")" << endl;
	return out;
}


/***************************************************************************
 * Parser: S-Expressions (SExp) -> AST Nodes (AST)                         *
 ***************************************************************************/

/// Parse Time Environment (really just a symbol table)
struct PEnv : private map<const string, const char*> {
	PEnv() : symID(0) {}
	~PEnv() { FOREACHP(const_iterator, i, this) free(const_cast<char*>(i->second)); }
	string gensymstr(const char* s="b") { return (format("_%s%d") % s % symID++).str(); }
	ASymbol* gensym(const char* s="b") { return sym(gensymstr(s)); }
	ASymbol* sym(const string& s, Cursor c=Cursor()) {
		assert(s != "");
		const const_iterator i = find(s);
		if (i != end()) {
			return new ASymbol(i->second, c);
		} else {
			const char* str = strdup(s.c_str());
			insert(make_pair(s, str));
			return new ASymbol(str, c);
		}
	}

	const AST* parse(Cursor& cur, std::istream& in) throw(Error);
	const AST* expand(const AST* exp);

	typedef std::set<std::string> Primitives;
	Primitives primitives;

	unsigned symID;
};


/***************************************************************************
 * Typing                                                                  *
 ***************************************************************************/

/// Type constraint
struct Constraint : public pair<const AST*,const AST*> {
	Constraint(const AST* a, const AST* b)
		: pair<const AST*, const AST*>(a, b) {}
};

/// Type substitution
struct Subst : public list<Constraint> {
	Subst(const AST* s=0, const AST* t=0) {
		if (s && t) { assert(s != t); push_back(Constraint(s, t)); }
	}
	static Subst compose(const Subst& delta, const Subst& gamma);
	void add(const AST* from, const AST* to) {
		assert(from && to);
		push_back(Constraint(from, to));
	}
	const_iterator find(const AST* t) const {
		for (const_iterator j = begin(); j != end(); ++j)
			if (*j->first == *t)
				return j;
		return end();
	}
	const AST* apply(const AST* in) const {
		if (AType::is_expr(in)) {
			if (in->as_tuple()->empty())
				return in;
			List out;
			for (ATuple::const_iterator i = in->as_tuple()->begin(); i != in->as_tuple()->end(); ++i)
				out.push_back(apply(*i));
			if (out.head)
				out.head->loc = in->loc;
			return out.head;
		} else {
			const_iterator i = find(in);
			if (i != end()) {
				const AST* out = i->second;
				if (AType::is_expr(out))
					out = apply(out);
				return out;
			} else {
				return in;
			}
		}
	}
	bool contains(const AST* type) const {
		if (find(type) != end())
			return true;
		FOREACHP(const_iterator, j, this)
			if (*j->second == *type
			    || (AType::is_expr(j->second) && list_contains(j->second->as_tuple(), type)))
				return true;
		return false;
	}
};

inline ostream& operator<<(ostream& out, const Subst& s) {
	for (Subst::const_iterator i = s.begin(); i != s.end(); ++i)
		out << i->first << " => " << i->second << endl;
	return out;
}

/// Type constraint set
struct Constraints : public list<Constraint> {
	Constraints() : list<Constraint>() {}
	explicit Constraints(const Subst& subst) : list<Constraint>() {
		FOREACH(Subst::const_iterator, i, subst)
			push_back(Constraint(i->first, i->second));
	}
	Constraints(const_iterator begin, const_iterator end) : list<Constraint>(begin, end) {}
	void constrain(TEnv& tenv, const AST* o, const AST* t);
	Constraints& replace(const AST* s, const AST* t);
};

inline ostream& operator<<(ostream& out, const Constraints& c) {
	for (Constraints::const_iterator i = c.begin(); i != c.end(); ++i)
		out << i->first << " <= " << i->second << endl;
	return out;
}

/// Type-Time Environment
struct TEnv : public Env<const AST*> {
	explicit TEnv(PEnv& p)
		: penv(p)
		, varID(1)
		, Closure(penv.sym("Closure"))
		, Dots(penv.sym("..."))
		, Fn(penv.sym("Fn"))
		, List(penv.sym("List"))
		, Empty(penv.sym("Empty"))
		, Tup(penv.sym("Tup"))
		, U(penv.sym("U"))
	{
		Object::pool.addRoot(Fn);
	}
	const AST* fresh(const ASymbol* sym) {
		return def(sym, new ALiteral<int32_t>(T_TVAR, varID++, sym->loc));
	}
	const AST* var(const AST* ast=0) {
		if (!ast)
			return new ALiteral<int32_t>(T_TVAR, varID++, Cursor());

		assert(!AType::is_var(ast));
		Vars::iterator v = vars.find(ast);
		if (v != vars.end())
			return v->second;

		return (vars[ast] = new ALiteral<int32_t>(T_TVAR, varID++, ast->loc));
	}
	const AST** ref(const ASymbol* sym) {
		return ((Env<const AST*>*)this)->ref(sym);
	}
	const AST* named(const string& name) {
		return *ref(penv.sym(name));
	}
	static Subst buildSubst(const AST* fnT, const AST& argsT);

	typedef map<const AST*, const AST*> Vars;

	/// Discriminated Union Constructor
	struct Constructor {
		Constructor(const AST* x, const AST* t) : expr(x), type(t) {}
		const AST* expr;
		const AST* type;
	};

	typedef map<const std::string, Constructor> Tags;
	
	Vars     vars;
	Tags     tags;
	PEnv&    penv;
	unsigned varID;

	ASymbol* Closure;
	ASymbol* Dots;
	ASymbol* Fn;
	ASymbol* List;
	ASymbol* Empty;
	ASymbol* Tup;
	ASymbol* U;
};

Subst unify(const Constraints& c);


/***************************************************************************
 * Code Generation                                                         *
 ***************************************************************************/

/// Compiler backend
struct Engine {
	virtual ~Engine() {}

	typedef const vector<CVal> CVals;

	virtual CFunc startFn(CEnv&              cenv,
	                      const std::string& name,
	                      const ATuple*      args,
	                      const ATuple*      type) = 0;

	virtual void  finishFn(CEnv& cenv, CVal ret, const AST* retT) = 0;
	virtual CFunc getFn(CEnv& cenv, const std::string& name)      = 0;
	virtual void  eraseFn(CEnv& cenv, CFunc f)                    = 0;

	virtual CVal  compileCall(CEnv& cenv, CFunc f, const ATuple* fT, CVals& args)           = 0;
	virtual CVal  compileCast(CEnv& cenv, CVal v, const AST* t)                             = 0;
	virtual CVal  compileCons(CEnv& cenv, const char* tname, const ATuple* t, CVal rtti, CVals& f) = 0;
	virtual CVal  compileDot(CEnv& cenv, CVal tup, int32_t index)                           = 0;
	virtual CVal  compileGlobalSet(CEnv& cenv, const string& s, CVal v, const AST* t)       = 0;
	virtual CVal  compileGlobalGet(CEnv& cenv, const string& s, CVal v)                     = 0;
	virtual CVal  compileIfStart(CEnv& cenv, const AST* cond, const AST* type)              = 0;
	virtual CVal  compileIfThen(CEnv& cenv, CVal thenV)                                     = 0;
	virtual CVal  compileIfElse(CEnv& cenv, CVal elseV)                                     = 0;
	virtual CVal  compileIfEnd(CEnv& cenv)                                                  = 0;
	virtual CVal  compileLiteral(CEnv& cenv, const AST* lit)                                = 0;
	virtual CVal  compilePrimitive(CEnv& cenv, const ATuple* prim)                          = 0;
	virtual CVal  compileString(CEnv& cenv, const char* str)                                = 0;
	virtual CType compileType(CEnv& cenv, const char* name, const AST* exp)                 = 0;

	virtual void writeModule(CEnv& cenv, std::ostream& os) = 0;

	virtual const string call(CEnv& cenv, CFunc f, const AST* retT) = 0;
};

Engine* resp_new_llvm_engine();
Engine* resp_new_c_engine();

/// Compile-Time Environment
struct CEnv {
	CEnv(PEnv& p, TEnv& t, Engine* e, ostream& os=std::cout, ostream& es=std::cerr)
		: out(os), err(es), penv(p), tenv(t), repl(false), _engine(e)
	{}

	~CEnv() { Object::pool.collect(GC::Roots()); }

	typedef Env<CVal> Vals;

	Engine* engine() { return _engine; }
	void    push() { code.push(); tenv.push(); vals.push(); }
	void    pop()  { code.pop(); tenv.pop();  vals.pop();  }
	void    lock(const AST* ast) {
		Object::pool.addRoot(ast);
		if (type(ast))
			Object::pool.addRoot(type(ast));
	}
	const AST* resolveType(const AST* type) const {
		if (AType::is_name(type))
			return tenv.named(type->as_symbol()->sym());
		return type;
	}
	const AST* type(const AST* ast, const Subst& subst = Subst(), bool resolve=true) const {
		const AST*     ret = NULL;
		const ASymbol* sym = ast->to_symbol();
		if (sym) {
			const AST** rec = tenv.ref(sym);
			if (rec)
				ret = *rec;
		}
		if (!ret)
			ret = tenv.vars[ast];
		if (ret)
			ret = tsubst.apply(subst.apply(ret));
		if (resolve && ret)
			ret = this->resolveType(ret);
		return ret;
	}
	void def(const ASymbol* sym, const AST* c, const AST* t, CVal v) {
		code.def(sym, c);
		tenv.def(sym, t);
		vals.def(sym, v);
	}
	const AST* resolve(const AST* ast) {
		const ASymbol* sym = ast->to_symbol();
		const AST**    rec = code.ref(sym);
		return rec ? *rec : ast;
	}
	void setType(const AST* ast, const AST* type) {
		const AST* tvar = tenv.var();
		tenv.vars.insert(make_pair(ast, tvar));
		tsubst.add(tvar, type);
	}
	void setTypeSameAs(const AST* ast, const AST* typedAst) {
		tenv.vars.insert(make_pair(ast, tenv.vars[typedAst]));
	}

	ostream& out;
	ostream& err;
	PEnv&    penv;
	TEnv&    tenv;
	Vals     vals;
	Subst    tsubst;

	Env<const AST*> code;

	typedef map<const ATuple*, CFunc> Impls;
	Impls impls;

	CFunc findImpl(const ATuple* fn, const AST* type) {
		Impls::const_iterator i = impls.find(fn);
		return (i != impls.end()) ? i->second : NULL;
	}

	void addImpl(const ATuple* fn, CFunc impl) {
		impls.insert(make_pair(fn, impl));
	}

	map<string,string> args;

	map<string, CVal> globals;

	typedef map<const char*, CVal> CSyms;
	CSyms cSyms;

	bool repl;

	struct FreeVars : public std::vector<const ASymbol*> {
		FreeVars(const ATuple* f, const std::string& n) : fn(f), implName(n) {}
		const ATuple* const fn;
		const std::string   implName;
		int32_t index(const ASymbol* sym) {
			for (const_iterator i = begin(); i != end(); ++i)
				if ((*i)->sym() == sym->sym())
					return i - begin() + 1;

			push_back(sym);
			return size();
		}
	};
	typedef std::stack<FreeVars> LiftStack;
	LiftStack liftStack;

	typedef map<const ATuple*, std::string> Names;
	Names names;

	const std::string name(const ATuple* fn) const {
		Names::const_iterator i = names.find(fn);
		return (i != names.end()) ? i->second : "";
	}

	void setName(const ATuple* fn, const std::string& name) {
		names.insert(make_pair(fn, name));
	}
private:
	Engine* _engine;
};


/***************************************************************************
 * EVAL/REPL/MAIN                                                          *
 ***************************************************************************/

typedef list<const AST*> Code;

void pprint(std::ostream& out, const AST* ast, CEnv* cenv, bool types);
void initLang(PEnv& penv, TEnv& tenv);
int  eval(CEnv& cenv, Cursor& cursor, istream& is, bool execute);
int  repl(CEnv& cenv);

const AST* resp_cps(CEnv& cenv, const AST* ast, const AST* k) throw();

void       resp_constrain(TEnv& tenv, Constraints& c, const AST* ast) throw(Error);

typedef const AST* (RespPass)(CEnv& cenv, Code& code, const AST* ast);

const AST* resp_simplify(CEnv& cenv, Code& code, const AST* ast) throw();
const AST* resp_lift(CEnv& cenv, Code& code, const AST* ast) throw();
const AST* resp_flatten(CEnv& cenv, Code& code, const AST* ast) throw();
const AST* resp_depoly(CEnv& cenv, Code& code, const AST* ast) throw();
CVal       resp_compile(CEnv& cenv, const AST* ast) throw();

bool is_form(const AST* ast, const std::string& form);
bool is_primitive(const PEnv& penv, const AST* ast);

#endif // RESP_HPP