Merge applications into a common AST base type (ASTCall).

Merge parsing of calls.


git-svn-id: http://svn.drobilla.net/resp/llvm-lisp@7 ad02d1e2-f140-0410-9f75-f8b11f17cedd

2 files changed, 122 insertions, 173 deletions

diff --git a/build.sh b/build.sh
index 2c94acd..d983233 100755
--- a/build.sh
+++ b/build.sh
@@ -1,6 +1,5 @@
 #!/bin/sh
 CXXFLAGS="-O0 -g -Wall -Wextra -Wno-unused-parameter"
 
-g++ $CXXFLAGS ll.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o ll
-#./ll
+g++ $CXXFLAGS ll.cpp `llvm-config --cppflags --ldflags --libs core jit native` -lm -O3 -o ll
 
diff --git a/ll.cpp b/ll.cpp
index 7e64b2c..cc13b31 100644
--- a/ll.cpp
+++ b/ll.cpp
@@ -122,81 +122,67 @@ readExpression(std::istream& in)
 
 struct CEnv; ///< Compile Time Environment
 
-/// Base class for all AST nodes.
+/// Base class for all AST nodes
 struct AST {
 	virtual ~AST() {}
 	virtual Value* Codegen(CEnv& cenv) = 0;
 	virtual bool evaluatable() const { return true; }
 };
 
-/// Definition, e.g. (def x 2) or (def (square y) (* y y))
-struct ASTDefinition : public AST {
-	ASTDefinition(const string& n, AST* v) : _name(n), _val(v) {}
+/// Numeric literal, e.g. "1.0"
+struct ASTNumber : public AST {
+	ASTNumber(double val) : _val(val) {}
 	virtual Value* Codegen(CEnv& cenv);
 private:
-	string _name;
-	AST*   _val;
+	double _val;
 };
 
-
-/// Primitive (builtin function)
-struct ASTPrimitive : public AST {
-	ASTPrimitive(Instruction::BinaryOps o, vector<AST*>& a)
-		: _op(o), _args(a) {}
+/// Symbol, e.g. "a"
+struct ASTSymbol : public AST {
+	ASTSymbol(const string& name) : _name(name) {}
 	virtual Value* Codegen(CEnv& cenv);
 private:
-	Instruction::BinaryOps _op;
-	AST*                   _lhs;
-	vector<AST*>           _args;
+	string _name;
 };
 
-
-/// Variable reference (i.e. symbol), e.g. "a".
-struct ASTVariable : public AST {
-	ASTVariable(const string& name) : _name(name) {}
+/// Function call/application, e.g. "(func arg1 arg2)"
+struct ASTCall : public AST {
+	ASTCall(const string& n, vector<AST*>& a) : _name(n), _args(a) {}
 	virtual Value* Codegen(CEnv& cenv);
-private:
-	string _name;
+protected:
+	string       _name;
+	vector<AST*> _args;
 };
 
-/// Numeric literal, e.g. "1.0".
-struct ASTNumber : public AST {
-	ASTNumber(double val) : _val(val) {}
+/// Definition special form, e.g. "(def x 2)" or "(def (next y) (+ y 1))"
+struct ASTDefinition : public ASTCall {
+	ASTDefinition(const string& n, vector<AST*> a) : ASTCall(n, a) {}
 	virtual Value* Codegen(CEnv& cenv);
-private:
-	double _val;
 };
 
-/// Function call, e.g. "(func arg1 arg2)".
-struct ASTCall : public AST {
-	ASTCall(const string& f, vector<AST*>& a) : _func(f), _args(a) {}
+/// Conditional special form, e.g. "(if cond thenexp elseexp)"
+struct ASTIf : public ASTCall {
+	ASTIf(const string& n, vector<AST*>& a) : ASTCall(n, a) {}
 	virtual Value* Codegen(CEnv& cenv);
-private:
-	string       _func;
-	vector<AST*> _args;
 };
 
-/// Conditional (special form "if"), e.g. "(if cond thenexp elseexp)".
-struct ASTIf : public AST {
-	ASTIf(AST* c, AST* t, AST* e) : _cond(c), _then(t), _else(e) {}
+/// Primitive (builtin arithmetic function)
+struct ASTPrimitive : public ASTCall {
+	ASTPrimitive(const string& n, vector<AST*>& a) : ASTCall(n, a) {}
 	virtual Value* Codegen(CEnv& cenv);
-private:
-	AST* _cond;
-	AST* _then;
-	AST* _else;
 };
 
 /// Function prototype
 struct ASTPrototype : public AST {
-	ASTPrototype(bool foreign, const string& n, const vector<string>& a)
-			: _foreign(foreign), _name(n), _args(a) {}
+	ASTPrototype(bool foreign, const string& n, const vector<string>& p)
+			: _foreign(foreign), _name(n), _params(p) {}
 	virtual bool evaluatable() const { return false; }
 	Value*       Codegen(CEnv& cenv) { return Funcgen(cenv); }
 	Function*    Funcgen(CEnv& cenv);
 private:
 	bool           _foreign;
 	string         _name;
-	vector<string> _args;
+	vector<string> _params;
 };
 
 /// Function definition
@@ -216,82 +202,28 @@ private:
  * Parser - Transform S-Expressions into AST nodes                         *
  ***************************************************************************/
 
-#define SPECIAL_IF      "if"
-#define SPECIAL_DEFINE  "def"
-#define SPECIAL_FOREIGN "foreign"
-
-static const std::string& head(const SExp& exp)
-{
-	static const std::string empty = "";
-	if (exp.type == SExp::LIST
-			&& !exp.list.empty()
-			&& exp.list.front().type == SExp::ATOM)
-		return exp.list.front().atom;
-	else
-		return empty;
-}
-
 static AST* parseExpression(const SExp& exp);
 
-/// identifierexpr ::= identifier
-static AST* parseIdentifierExpr(const SExp& exp)
-{
-	assert(exp.type == SExp::ATOM);
-	return new ASTVariable(exp.atom);
-}
-
 /// numberexpr ::= number
-static AST* parseNumberExpr(const SExp& exp)
+static AST*
+parseNumber(const SExp& exp)
 {
 	assert(exp.type == SExp::ATOM);
 	return new ASTNumber(strtod(exp.atom.c_str(), NULL));
 }
 
-/// ifexpr ::= ("if" expression expression expression)
-static AST* parseIfExpr(const SExp& exp)
-{
-	assert(head(exp) == SPECIAL_IF);
-	list<SExp>::const_iterator i = exp.list.begin();
-	++i;
-	
-	AST* cond      = parseExpression(*i++);
-	AST* then      = parseExpression(*i++);
-	AST* otherwise = parseExpression(*i++);
-
-	return new ASTIf(cond, then, otherwise);
-}
-
-/// callexpr ::= (expression [...])
-static AST* parseCallExpr(const SExp& exp)
+/// identifierexpr ::= identifier
+static AST*
+parseSymbol(const SExp& exp)
 {
-	assert(head(exp) != "");
-	list<SExp>::const_iterator i = exp.list.begin();
-	const string& name = i->atom;
-
-	vector<AST*> params;
-	for (++i; i != exp.list.end(); ++i)
-		params.push_back(parseExpression(*i));
-	
-	if (name.length() == 1) {
-		switch (name[0]) {
-		case '+': return new ASTPrimitive(Instruction::Add, params);
-		case '-': return new ASTPrimitive(Instruction::Sub, params);
-		case '*': return new ASTPrimitive(Instruction::Mul, params);
-		case '/': return new ASTPrimitive(Instruction::FDiv, params);
-		case '%': return new ASTPrimitive(Instruction::FRem, params);
-		case '&': return new ASTPrimitive(Instruction::And, params);
-		case '|': return new ASTPrimitive(Instruction::Or, params);
-		case '^': return new ASTPrimitive(Instruction::Xor, params);
-		}
-	}
-
-	return new ASTCall(name, params);
+	assert(exp.type == SExp::ATOM);
+	return new ASTSymbol(exp.atom);
 }
 
 /// prototype ::= (name [arg*])
-static ASTPrototype* parsePrototype(bool foreign, const SExp& exp)
+static ASTPrototype*
+parsePrototype(bool foreign, const SExp& exp)
 {
-	assert(head(exp) != "");
 	list<SExp>::const_iterator i = exp.list.begin();
 	const string& name = i->atom;
 	
@@ -305,53 +237,52 @@ static ASTPrototype* parsePrototype(bool foreign, const SExp& exp)
 	return new ASTPrototype(foreign, name, args);
 }
 
-/// definition ::= ("def" prototype expression)
-static AST* parseDefinition(const SExp& exp)
+/// callexpr ::= (expression [...])
+static AST*
+parseCall(const SExp& exp)
 {
-	assert(head(exp) == SPECIAL_DEFINE);
-	list<SExp>::const_iterator i = exp.list.begin();
-	++i;
+	if (exp.list.empty())
+		return NULL;
 
-	if (i->type == SExp::LIST) {
+	list<SExp>::const_iterator i = exp.list.begin();
+	const string& name = i->atom;
+	
+	if (name == "def" && (++i)->type == SExp::LIST) {
 		ASTPrototype* proto = parsePrototype(false, *i++);
 		AST*          body  = parseExpression(*i++);
 		return new ASTFunction(proto, body);
-	} else {
-		const string& name  = i->atom;
-		AST*          value = parseExpression(*++i);
-		return new ASTDefinition(name, value);
 	}
-}
 
-/// foreign ::= ("foreign" prototype expression)
-static ASTPrototype* parseForeign(const SExp& exp)
-{
-	assert(head(exp) == SPECIAL_FOREIGN);
-	list<SExp>::const_iterator i = exp.list.begin();
-	++i;
+	vector<AST*> args;
+	for (++i; i != exp.list.end(); ++i)
+		args.push_back(parseExpression(*i));
+	
+	if (name.length() == 1) {
+		switch (name[0]) {
+		case '+': case '-': case '*': case '/':
+		case '%': case '&': case '|': case '^':
+			return new ASTPrimitive(name, args);
+		}
+	} else if (name == "if") {
+		return new ASTIf(name, args);
+	} else if (name == "def") {
+		return new ASTDefinition(name, args);
+	} else if (name == "foreign") {
+		return parsePrototype(true, *++i++);
+	}
 
-	return parsePrototype(true, *i++);
+	return new ASTCall(name, args);
 }
 
-static AST* parseExpression(const SExp& exp)
+static AST*
+parseExpression(const SExp& exp)
 {
 	if (exp.type == SExp::LIST) {
-		const string& form = head(exp);
-		if (exp.list.empty()) {
-			return NULL;
-		} else if (form == SPECIAL_IF) {
-			return parseIfExpr(exp);
-		} else if (form == SPECIAL_DEFINE) {
-			return parseDefinition(exp);
-		} else if (form == SPECIAL_FOREIGN) {
-			return parseForeign(exp);
-		} else {
-			return parseCallExpr(exp);
-		}
+		return parseCall(exp);
 	} else if (isalpha(exp.atom[0])) {
-		return parseIdentifierExpr(exp);
+		return parseSymbol(exp);
 	} else if (isdigit(exp.atom[0])) {
-		return parseNumberExpr(exp);
+		return parseNumber(exp);
 	} else {
 		throw SyntaxError("Illegal atom");
 	}
@@ -386,12 +317,14 @@ struct CEnv {
 	map<string, Value*>    env;
 };
 
-Value* ASTNumber::Codegen(CEnv& cenv)
+Value*
+ASTNumber::Codegen(CEnv& cenv)
 {
 	return ConstantFP::get(APFloat(_val));
 }
 
-Value* ASTVariable::Codegen(CEnv& cenv)
+Value*
+ASTSymbol::Codegen(CEnv& cenv)
 {
 	map<string, Value*>::const_iterator v = cenv.env.find(_name);
 	if (v == cenv.env.end())
@@ -399,32 +332,35 @@ Value* ASTVariable::Codegen(CEnv& cenv)
 	return v->second;
 }
 
-Value* ASTDefinition::Codegen(CEnv& cenv)
+Value*
+ASTDefinition::Codegen(CEnv& cenv)
 {
 	map<string, Value*>::const_iterator v = cenv.env.find(_name);
 	if (v != cenv.env.end()) throw SyntaxError("Symbol redefinition");
-	Value* valCode = _val->Codegen(cenv);
+	if (_args.empty())       throw SyntaxError("Empty definition");
+	Value* valCode = _args[0]->Codegen(cenv);
 	cenv.env[_name] = valCode;
 	return valCode;
 }
 
-Value* ASTCall::Codegen(CEnv& cenv)
+Value*
+ASTCall::Codegen(CEnv& cenv)
 {
-	// Look up the name in the global module table.
-	Function* f = cenv.module->getFunction(_func);
-	if (f == 0) throw SyntaxError("Undefined function");
+	Function* f = cenv.module->getFunction(_name);
+	if (!f)                            throw SyntaxError("Undefined function");
 	if (f->arg_size() != _args.size()) throw SyntaxError("Illegal arguments");
 
-	vector<Value*> args;
-	for (size_t i = 0, e = _args.size(); i != e; ++i)
-		args.push_back(_args[i]->Codegen(cenv));
+	vector<Value*> params;
+	for (size_t i = 0; i != _args.size(); ++i)
+		params.push_back(_args[i]->Codegen(cenv));
 
-	return cenv.builder.CreateCall(f, args.begin(), args.end(), "calltmp");
+	return cenv.builder.CreateCall(f, params.begin(), params.end(), "calltmp");
 }
 
-Value* ASTIf::Codegen(CEnv& cenv)
+Value*
+ASTIf::Codegen(CEnv& cenv)
 {
-	Value* condV = _cond->Codegen(cenv);
+	Value* condV = _args[0]->Codegen(cenv);
 
 	// Convert condition to a bool by comparing equal to 0.0.
 	condV = cenv.builder.CreateFCmpONE(
@@ -442,7 +378,7 @@ Value* ASTIf::Codegen(CEnv& cenv)
 
 	// Emit then value.
 	cenv.builder.SetInsertPoint(thenBB);
-	Value* thenV = _then->Codegen(cenv);
+	Value* thenV = _args[1]->Codegen(cenv);
 
 	cenv.builder.CreateBr(mergeBB);
 	// Codegen of 'Then' can change the current block, update thenBB
@@ -451,7 +387,7 @@ Value* ASTIf::Codegen(CEnv& cenv)
 	// Emit else block.
 	parent->getBasicBlockList().push_back(elseBB);
 	cenv.builder.SetInsertPoint(elseBB);
-	Value* elseV = _else->Codegen(cenv);
+	Value* elseV = _args[2]->Codegen(cenv);
 
 	cenv.builder.CreateBr(mergeBB);
 	// Codegen of 'Else' can change the current block, update elseBB
@@ -467,10 +403,11 @@ Value* ASTIf::Codegen(CEnv& cenv)
 	return pn;
 }
 
-Function* ASTPrototype::Funcgen(CEnv& cenv)
+Function*
+ASTPrototype::Funcgen(CEnv& cenv)
 {
 	// Make the function type, e.g. double(double,double)
-	vector<const Type*> argsT(_args.size(), Type::DoubleTy);
+	vector<const Type*> argsT(_params.size(), Type::DoubleTy);
 	FunctionType* FT = FunctionType::get(Type::DoubleTy, argsT, false);
 
 	Function* f = Function::Create(
@@ -487,24 +424,22 @@ Function* ASTPrototype::Funcgen(CEnv& cenv)
 		if (!f->empty()) throw SyntaxError("Function redefined");
 
 		// If F took a different number of args, reject.
-		if (f->arg_size() != _args.size())
+		if (f->arg_size() != _params.size())
 			throw SyntaxError("Function redefined with mismatched arguments");
 	}
 
-	// Set names for all arguments.
-	size_t i = 0;
-	for (Function::arg_iterator a = f->arg_begin(); i != _args.size();
-	        ++a, ++i) {
-		a->setName(_args[i]);
-
-		// Add arguments to variable symbol table.
-		cenv.env[_args[i]] = a;
+	// Set names for all arguments and add to environment.
+	Function::arg_iterator a = f->arg_begin();
+	for (size_t i = 0; i != _params.size(); ++a, ++i) {
+		a->setName(_params[i]);
+		cenv.env[_params[i]] = a;
 	}
 
 	return f;
 }
 
-Function* ASTFunction::Funcgen(CEnv& cenv)
+Function*
+ASTFunction::Funcgen(CEnv& cenv)
 {
 	Function* f = _proto->Funcgen(cenv);
 
@@ -526,21 +461,36 @@ Function* ASTFunction::Funcgen(CEnv& cenv)
 	return 0; // Never reached
 }
 
-Value* ASTPrimitive::Codegen(CEnv& cenv)
+Value*
+ASTPrimitive::Codegen(CEnv& cenv)
 {
+	Instruction::BinaryOps op;
+	assert(_name.length() == 1);
+	switch (_name[0]) {
+	case '+': op = Instruction::Add; break;
+	case '-': op = Instruction::Sub; break;
+	case '*': op = Instruction::Mul; break;
+	case '/': op = Instruction::FDiv; break;
+	case '%': op = Instruction::FRem; break;
+	case '&': op = Instruction::And; break;
+	case '|': op = Instruction::Or; break;
+	case '^': op = Instruction::Xor; break;
+	default: throw SyntaxError("Unknown primitive");
+	}
+	
 	vector<Value*> params;
 	for (vector<AST*>::const_iterator a = _args.begin(); a != _args.end(); ++a)
 		params.push_back((*a)->Codegen(cenv));
 
 	switch (params.size()) {
 	case 0:
-		throw SyntaxError("Primitive expects at least 1 argument\n");
+		throw SyntaxError("Primitive expects at least 1 argument");
 	case 1:
 		return params[0];
 	default:
-		Value* val = cenv.builder.CreateBinOp(_op, params[0], params[1]);
+		Value* val = cenv.builder.CreateBinOp(op, params[0], params[1]);
 		for (size_t i = 2; i < params.size(); ++i)
-			val = cenv.builder.CreateBinOp(_op, val, params[i]);
+			val = cenv.builder.CreateBinOp(op, val, params[i]);
 		return val;
 	}
 }
@@ -551,7 +501,8 @@ Value* ASTPrimitive::Codegen(CEnv& cenv)
  ***************************************************************************/
 
 /// Read-Eval-Print-Loop
-static void repl(CEnv& cenv, ExecutionEngine* engine)
+static void
+repl(CEnv& cenv, ExecutionEngine* engine)
 {
 	while (1) {
 		std::cout << "> ";
@@ -599,7 +550,6 @@ main()
 
 	std::cout << "Generated code:" << endl;
 	module->dump();
-
 	return 0;
 }