Commits

Martin Voelkle  committed d21f85e

moved garbage collector, added user-defined methods

  • Participants
  • Parent commits 42e5521
  • Branches master

Comments (0)

Files changed (13)

File libusl/src/CMakeLists.txt

 set(libusl_SOURCES
+interpreter.cpp
 lexer.cpp
+memory.cpp
 position.cpp
 token.cpp
 tokenizer.cpp
 tree.cpp
+types.cpp
 usl.cpp
-interpreter.cpp
 )
 
 include_directories(${libusl_SOURCE_DIR}/include)

File libusl/src/code.h

 #ifndef BYTECODE_H
 #define BYTECODE_H
 
-#include <string>
 #include "interpreter.h"
+#include <cassert>
 
 
 struct Code
 	
 	void execute(Thread* thread)
 	{
-		thread->topFrame().stack.push_back(value);
+		thread->frames.back().stack.push_back(value);
 	}
 	
 	Value* value;
 	
 	void execute(Thread* thread)
 	{
-		Thread::Frame& frame = thread->topFrame();
+		Thread::Frame& frame = thread->frames.back();
 		frame.stack.push_back(frame.scope->lookup(local));
 	}
 	
 
 struct ApplyCode: Code
 {
-	ApplyCode(const std::string& method, size_t argCount):
-		method(method),
+	ApplyCode(const std::string& name, size_t argCount):
+		name(name),
 		argCount(argCount)
 	{}
 	
 	void execute(Thread* thread)
 	{
 		// fetch receiver
-		Value* receiver = *(thread->topFrame().stack.end() - argCount - 1);
+		Value* receiver = *(thread->frames.back().stack.end() - argCount - 1);
 		
 		// fetch method
-		Method* method = receiver->proto->lookup(this->method);
+		Method* method = receiver->prototype->lookup(name);
 		assert(argCount == method->args.size());
 		
 		method->execute(thread);
 	}
 		
-	const std::string method;
+	const std::string name;
 	size_t argCount;
 };
 
 	
 	void execute(Thread* thread)
 	{
-		Thread::Frame& frame = thread->topFrame();
+		Thread::Frame& frame = thread->frames.back();
 		Thread::Frame::Stack& stack = frame.stack;
-		size_t stackSize = stack.size();
-		frame.scope->locals[local] = stack[--stackSize];
-		stack.resize(stackSize);
+		frame.scope->locals[local] = stack.back();
+		stack.pop_back();
 	}
 	
 	const std::string local;
 };
 
+struct PopCode: Code
+{
+	void execute(Thread* thread)
+	{
+		thread->frames.back().stack.pop_back();
+	}
+};
+
+struct MethodCode: Code
+{
+	MethodCode(UserMethod* method):
+		method(method)
+	{}
+	
+	void execute(Thread* thread)
+	{
+		Thread::Frame& frame = thread->frames.back();
+		frame.stack.push_back(new Scope(thread->heap, method, frame.scope));
+	}
+	
+	UserMethod* method;
+};
+
+struct ReturnCode: Code
+{
+	void execute(Thread* thread)
+	{
+		Value* value = thread->frames.back().stack.back();
+		thread->frames.pop_back();
+		thread->frames.back().stack.push_back(value);
+	}
+};
+
 #endif // ndef BYTECODE_H

File libusl/src/interpreter.cpp

 #include "interpreter.h"
 #include "types.h"
 
-using namespace std;
-using namespace __gnu_cxx;
+void Thread::markForGC()
+{
+	using namespace std;
+	using namespace __gnu_cxx;
+	
+	// mark all frames in stack
+	for_each(frames.begin(), frames.end(), mem_fun_ref(&Frame::markForGC));
+}
 
 void Thread::Frame::markForGC()
 {
+	using namespace std;
+	using namespace __gnu_cxx;
+	
 	// mark all variables in frame
 	for_each(stack.begin(), stack.end(), mem_fun(&Value::markForGC));
 	scope->markForGC();
 }
-
-void Thread::markForGC()
-{
-	// mark all frames in stack
-	for_each(frames.begin(), frames.end(), mem_fun_ref(&Frame::markForGC));
-}
-
-void Thread::garbageCollect()
-{
-	// mark all objects in heap
-	markForGC();
-	
-	// filter copy, delete unrefs
-	Heap toKeep;
-	for (size_t i = 0; i < heap.size(); i++)
-	{
-		if (heap[i]->marked)
-			toKeep.push_back(heap[i]);
-		else
-			delete heap[i];
-	}
-	
-	// clean heap
-	heap.resize(toKeep.size());
-	copy(toKeep.begin(), toKeep.end(), heap.begin());
-	for_each(heap.begin(), heap.end(), mem_fun(&Value::clearGCMark));
-}
-

File libusl/src/interpreter.h

 
 struct Scope;
 struct Value;
+struct Heap;
 
 struct Thread
 {
 		void markForGC();
 	};
 	
-	typedef std::vector<Value*> Heap;
 	typedef std::vector<Frame> Frames;
 	
-	Heap heap;
+	Heap* heap;
 	Frames frames;
 	
+	Thread(Heap* heap):
+		heap(heap)
+	{}
+	
 	void markForGC();
-	void garbageCollect();
-	Frame &topFrame() { return *frames.rbegin(); }
 };
 
 #endif // ndef INTERPRETER_H

File libusl/src/lexer.cpp

 #include "lexer.h"
 
+#include <cassert>
+
 const Token::Type Lexer::tokenTypes[] =
 {
 	Token::Type(SPACE,   "a space",                 "[[:blank:]]+"),
 	Token::Type(RBRACE,  "an end of sequence",      "\\}"),
 	Token::Type(COMMA,   "a comma",                 ","),
 	Token::Type(COMMENT, "a comment",               "\\([\"\'])(\\\\|[^\\])*\\([\"\'])"),
-	Token::Type(CR,      "a new line",              "\n"),
+	Token::Type(NL,      "a new line",              "\n"),
 	Token::Type(END,     "the end of the text",     "$"),
-	Token::Type(ERROR,   "an invalid token",        ""),
 };
+
+Token Lexer::_next()
+{
+	Token token = Tokenizer::next();
+	while ((token.type->id == SPACE) || (token.type->id == COMMENT))
+		token = Tokenizer::next();
+	if (token.type == 0)
+	{
+		assert(false); // TODO
+	}
+	return token;
+}

File libusl/src/lexer.h

 		RBRACE,
 		COMMA,
 		COMMENT,
-		CR,
+		NL,
 		END,
-		ERROR,
 		TOKENTYPES,
 	};
 	
 	}
 	
 private:
-	Token _next()
-	{
-		Token token = Tokenizer::next();
-		while ((token.type->id == SPACE) || (token.type->id == COMMENT))
-			token = Tokenizer::next();
-		return token;
-	}
+	Token _next();
 	
 public:
 	Token token;

File libusl/src/memory.cpp

+#include "memory.h"
+#include "interpreter.h"
+#include "types.h"
+
+using namespace std;
+using namespace __gnu_cxx;
+
+void Heap::garbageCollect(Thread* thread)
+{
+	// mark all objects in heap
+	thread->markForGC();
+	
+	// filter copy, delete unrefs
+	Values marked;
+	for (size_t i = 0; i < values.size(); i++)
+	{
+		if (values[i]->marked)
+			marked.push_back(values[i]);
+		else
+			delete values[i];
+	}
+	
+	// clean heap
+	swap(values, marked);
+	for_each(values.begin(), values.end(), mem_fun(&Value::clearGCMark));
+}
+

File libusl/src/memory.h

+#ifndef MEMORY_H
+#define MEMORY_H
+
+#include <stack>
+#include <vector>
+
+struct Value;
+struct Thread;
+
+struct Heap
+{
+	typedef std::vector<Value*> Values;
+	
+	Values values;
+	
+	void garbageCollect(Thread* thread);
+};
+
+#endif // ndef MEMORY_H

File libusl/src/tree.cpp

 #include "tree.h"
 #include "code.h"
 
-void ConstNode::generate(CodeVector* code)
+void ConstNode::generate(UserMethod* method)
 {
-	code->push_back(new ConstCode(value));
+	method->body.push_back(new ConstCode(value));
 }
 
-void LocalNode::generate(CodeVector* code)
+void LocalNode::generate(UserMethod* method)
 {
-	code->push_back(new LocalCode(local));
+	method->body.push_back(new LocalCode(local));
 }
 
-void ApplyNode::generate(CodeVector* code)
+void ApplyNode::generate(UserMethod* method)
 {
-	receiver->generate(code);
+	receiver->generate(method);
 	for (size_t i = 0; i < args.size(); i++)
-		args[i]->generate(code);
-	code->push_back(new ApplyCode(method, args.size()));
+		args[i]->generate(method);
+	method->body.push_back(new ApplyCode(name, args.size()));
 }
 
-void ValueNode::generate(CodeVector* code)
+void ValueNode::generate(UserMethod* method)
 {
-	value->generate(code);
-	code->push_back(new ValueCode(local));
+	value->generate(method);
+	method->body.push_back(new ValueCode(local));
 }

File libusl/src/tree.h

 #include "types.h"
 
 struct Code;
-typedef std::vector<Code*> CodeVector;
 
 struct Node
 {
 	virtual ~Node() {}
-	virtual void generate(CodeVector* code) = 0;
+	virtual void generate(UserMethod* method) = 0;
 };
 
-struct ConstNode: Node
+struct ExpressionNode: Node
+{};
+
+struct ConstNode: ExpressionNode
 {
 	ConstNode(Value* value):
 		value(value)
 	{}
 	
-	void generate(CodeVector* code);
+	void generate(UserMethod* method);
 	
 	Value* value;
 };
 
-struct LocalNode: Node
+struct LocalNode: ExpressionNode
 {
 	LocalNode(const std::string& local):
 		local(local)
 	{}
 	
-	void generate(CodeVector* code);
+	void generate(UserMethod* method);
 	
 	std::string local;
 };
 
-struct ApplyNode: Node
+struct ApplyNode: ExpressionNode
 {
 	ApplyNode(Node* receiver, const std::string& method):
 		receiver(receiver),
-		method(method)
+		name(name)
 	{}
 	
-	void generate(CodeVector* code);
+	void generate(UserMethod* method);
 	
 	Node* receiver;
-	const std::string method;
+	const std::string name;
 	std::vector<Node*> args;
 };
 
 		value(value)
 	{}
 	
-	void generate(CodeVector* code);
+	void generate(UserMethod* method);
 	
 	const std::string local;
 	Node* value;

File libusl/src/types.cpp

+#include "types.h"
+#include "interpreter.h"
+
+#include <cassert>
+
+void UserMethod::execute(Thread* thread)
+{
+	Thread::Frames& frames = thread->frames;
+	Thread::Frame::Stack& stack = frames.back().stack;
+	
+	size_t argsSize = args.size();
+	
+	// create a new scope
+	Scope* receiver = dynamic_cast<Scope*>(*(stack.rbegin() + argsSize));
+	assert(receiver != 0);
+	Scope* scope = new Scope(thread->heap, this, receiver);
+	
+	// copy arguments
+	Thread::Frame::Stack::const_iterator arg = stack.end() - argsSize;
+	for (size_t i = 0; i < argsSize; ++i)
+	{
+		scope->locals[args[i]] = *arg;
+		++arg;
+	}
+	
+	// pop arguments and receiver
+	stack.resize(stack.size() - argsSize - 1);
+	
+	frames.push_back(scope);
+}

File libusl/src/types.h

 #ifndef TYPES_H
 #define TYPES_H
 
-#include <cassert>
+#include "memory.h"
+
 #include <map>
 #include <string>
 #include <vector>
 #include <ext/functional>
-#include "interpreter.h"
 
 struct Prototype;
-
 struct Value
 {
-	Prototype* proto;
+	Prototype* prototype;
 	bool marked;
 	
-	Value(Thread *thread, Prototype* proto):
-		proto(proto)
+	Value(Heap* heap, Prototype* prototype):
+		prototype(prototype)
 	{
 		marked = false;
-		if (thread)
-			thread->heap.push_back(this);
+		if (heap)
+			heap->values.push_back(this);
 	}
 	
 	virtual ~Value() { }
 	Prototype* parent;
 	Methods methods;
 	
-	Prototype(Thread *thread, Prototype* parent):
-		Value(thread, 0), parent(parent)
+	Prototype(Heap* heap, Prototype* parent):
+		Value(heap, 0), parent(parent)
 	{ // TODO: MetaPrototype
 	}
 	
 		for_each(methods.begin(), methods.end(), compose1(mem_fun(&Value::markForGC), select2nd<map<string, Value*>::value_type>()));
 	}
 	
-	Method* lookup(const std::string &method) const
+	virtual Method* lookup(const std::string &method) const
 	{
-		Methods::const_iterator methodIt = methods.find(method);
-		if (methodIt != methods.end())
-		{
-			return methodIt->second;
-		}
-		else if (parent != 0)
-		{
-			return parent->lookup(method);
-		}
-		else
-		{
-			assert(false); // TODO
-			//throw UnknownMethodException(method);
-		}
+		return methods.find(method)->second;
 	}
 };
 
 	
 	Args args;
 	
-	Method(Thread *thread, Prototype* parent):
-		Prototype(thread, parent)
+	Method(Heap* heap, Prototype* parent):
+		Prototype(heap, parent)
+	{
+	}
+	
+	virtual void execute(Thread* thread) = 0;
+};
+
+struct Code;
+struct UserMethod: Method
+{
+	typedef std::vector<Code*> Body;
+	
+	Body body;
+	
+	UserMethod(Heap* heap, Prototype* parent):
+		Method(heap, parent)
 	{
 		methods["."] = this;
 	}
 	
-	virtual void execute(Thread* stack) = 0;
+	void execute(Thread* thread);
 };
 
 struct Scope: Value
 	Scope* parent;
 	Locals locals;
 	
-	Scope(Thread *thread, Method* method, Scope* parent):
-		Value(thread, method),
+	Scope(Heap* heap, UserMethod* method, Scope* parent):
+		Value(heap, method),
 		parent(parent)
 	{
 		locals["."] = this;
 	
 	Value* lookup(const std::string& name) const
 	{
-		Locals::const_iterator localIt = locals.find(name);
-		if (localIt != locals.end())
-		{
-			return localIt->second;
-		}
-		else if (parent != 0)
-		{
-			return parent->lookup(name);
-		}
-		else
-		{
-			return 0;
-		}
+		return locals.find(name)->second;
 	}
-
+	
+	UserMethod* method()
+	{
+		return static_cast<UserMethod*>(prototype);
+	}
 };
 
 #endif // ndef TYPES_H

File libusl/src/usl.cpp

 #include "lexer.h"
 #include "tree.h"
 #include "code.h"
+#include "memory.h"
 #include <cassert>
 #include <memory>
 #include <vector>
 
 using namespace std;
 
-struct Class: Method
+struct Class: UserMethod
 {
 	vector<string> fields;
 };
 
 struct Object: Scope
 {
-	Object(Thread *thread, Class* klass, Scope* parent):
-		Scope(thread, klass, parent)
+	Object(Heap* heap, Class* klass, Scope* parent):
+		Scope(heap, klass, parent)
 	{
 		transform(klass->fields.begin(), klass->fields.end(), inserter(locals, locals.begin()), bind2nd(ptr_fun(make_pair<string, Value*>), 0));
 	}
 		void execute(Thread* thread)
 		{
 			// check number of arguments
-			Thread::Frame::Stack& stack = thread->topFrame().stack;
+			Thread::Frame::Stack& stack = thread->frames.back().stack;
 			size_t stackSize = stack.size();
 			
 			Integer* thatInt = dynamic_cast<Integer*>(stack[--stackSize]);
 			assert(thisInt);
 			// todo check thatInt type
 			
-			stack[stackSize++] = new Integer(thread, thisInt->value + thatInt->value);
+			stack[stackSize++] = new Integer(thread->heap, thisInt->value + thatInt->value);
 			
 			stack.resize(stackSize);
 		}
 		}
 	} integerPrototype;
 	
-	Integer(Thread *thread, int value):
-		Value(thread, &integerPrototype),
+	Integer(Heap* heap, int value):
+		Value(heap, &integerPrototype),
 		value(value)
 	{
 		this->value = value;
 	}
 };
 
-
 Integer::IntegerPrototype Integer::integerPrototype;
 Integer::IntegerAdd Integer::integerAdd;
 
 
+struct LookupNode: ExpressionNode
+{
+	LookupNode(const string& name):
+		name(name)
+	{}
+	
+	void generate(UserMethod* method)
+	{
+		assert(false);
+	}
+	
+	const string name;
+};
+
+struct BlockNode: Node
+{
+	typedef vector<Node*> Statements;
+	
+	void generate(UserMethod* method)
+	{
+		for (Statements::const_iterator it = statements.begin(); it != statements.end(); ++it)
+		{
+			Node* statement = *it;
+			statement->generate(method);
+			if (dynamic_cast<ExpressionNode*>(statement) != 0)
+			{
+				// if the statement is an expression, its result is ignored
+				method->body.push_back(new PopCode());
+			}
+		}
+		value->generate(method);
+	}
+	
+	void end(Value* nil)
+	{
+		if (!statements.empty() && dynamic_cast<ExpressionNode*>(statements.back()) != 0)
+		{
+			value = statements.back();
+			statements.pop_back();
+		}
+		else
+		{
+			value = new ConstNode(nil);
+		}
+	}
+	
+	Statements statements;
+	Node* value;
+};
+
 struct Parser: Lexer
 {
-	Parser(const char* src):
+	Parser(const char* src, Heap* heap):
 		Lexer(src),
-		Nil(0, 0),
-		nil(0, &Nil)
+		heap(heap),
+		Nil(new Prototype(heap, 0)),
+		nil(new Value(heap, Nil))
 	{}
 	
-	Node* statement(Scope* scope)
+	BlockNode* parse()
+	{
+		return statements();
+	}
+	
+	BlockNode* statements()
+	{
+		newlines();
+		auto_ptr<BlockNode> block(new BlockNode());
+		while (true)
+		{
+			switch (tokenType())
+			{
+			case END:
+			case RBRACE:
+				block->end(nil);
+				return block.release();
+			}
+			block->statements.push_back(statement());
+			newlines();
+		}
+	}
+	
+	Node* statement()
 	{
 		switch (tokenType())
 		{
-			case VAL:
+		case VAL:
 			{
 				next();
 				string name = identifier();
 				accept(ASSIGN);
-				scope->locals[name] = &nil;
-				return new ValueNode(name, expression(scope));
+				newlines();
+				return new ValueNode(name, expression());
 			}
+		default:
+			return expression();
+		}
+	}
+	
+	Node* expression()
+	{
+		auto_ptr<Node> node(simple());
+		while (true)
+		{
+			switch (tokenType())
+			{
+			case ID:
+				node = apply(node, identifier());
+				break;
+			case LPAR:
+				node = apply(node, ".");
+				break;
 			default:
-				return expression(scope);
+				return node.release();
+			}
+		}
+	}
+	
+	auto_ptr<ApplyNode> apply(auto_ptr<Node> receiver, const string& method)
+	{
+		auto_ptr<ApplyNode> node(new ApplyNode(receiver.release(), method));
+		node->args.push_back(simple());
+		return node;
+	}
+	
+	Node* simple()
+	{
+		switch (tokenType())
+		{
+		case ID:
+			{
+				return new LookupNode(identifier());
+			}
+		case NUM:
+			{
+				string str = token.string();
+				next();
+				int value = atoi(str.c_str());
+				return new ConstNode(new Integer(heap, value));
+			}
+		case LPAR:
+			{
+				next();
+				// TODO: tuples
+				accept(RPAR);
+				assert(false);
+			}
+		case LBRACE:
+			{
+				next();
+				auto_ptr<Node> block(statements());
+				accept(RBRACE);
+				return block.release();
+			}
+		default:
+			return new ConstNode(nil);
+		}
+	}
+	
+	void newlines()
+	{
+		while (tokenType() == NL)
+		{
+			next();
 		}
 	}
 	
 		next();
 	}
 	
-	Node* expression(Scope* scope)
-	{
-		auto_ptr<Node> node(simple(scope));
-		while (true)
-		{
-			std::string method;
-			switch (tokenType())
-			{
-				case ID:
-					method = token.string();
-					next();
-					break;
-				case LPAR:
-					method = ".";
-					break;
-				default:
-					return node.release();
-			}
-			auto_ptr<ApplyNode> apply(new ApplyNode(node.release(), method));
-			apply->args.push_back(simple(scope));
-			node = apply;
-		}
-	}
-	
-	Node* simple(Scope* scope)
-	{
-		switch (tokenType())
-		{
-			case ID:
-			{
-				const string name(token.string());
-				next();
-				Value* value = scope->lookup(name);
-				if (value != 0)
-				{
-					return new LocalNode(name);
-				}
-				else
-				{
-					assert(false);
-				}
-			}
-			case NUM:
-			{
-				string str = token.string();
-				next();
-				int value = atoi(str.c_str());
-				return new ConstNode(new Integer(0, value));	// todo insert into gc or in const table, right now this is LEAK
-			}
-			case LPAR:
-				next();
-				// TODO
-			default:
-				assert(false);
-		}
-	}
-	
-	Prototype Nil;
-	Value nil;
+	Heap* heap;
+	Prototype* Nil;
+	Value* nil;
 };
 
-struct Root: Method
-{
-	Root():
-		Method(0, 0)	// todo check garbage collectable itude
-	{}
-	
-	void execute(Thread* thread)
-	{
-		assert(false);
-	}
-} root;
-
 int main(int argc, char** argv)
 {
-	Parser parser("val x = 21 + 21");
-	Node* node = parser.statement(new Scope(0, &root, 0));	// todo check garbage collectable, this is LEAKY
+	Heap heap;
+	
+	Parser parser("val x = 21 + 21\n", &heap);
+	Node* node = parser.parse();
 /*
 	ApplyNode* node = new ApplyNode(new ConstNode(new Integer(2)), "+");
 	node->args.push_back(new ConstNode(new Integer(1)));
 */
 	
-	CodeVector code;
-	node->generate(&code);
+	UserMethod root(&heap, 0);
+	node->generate(&root);
 	
-	Thread t;
-	t.frames.push_back(Thread::Frame(new Scope(&t, &root, 0)));
+	Thread thread(&heap);
+	thread.frames.push_back(Thread::Frame(new Scope(&heap, &root, 0)));
 	
-	while (t.topFrame().nextInstr < code.size())
+	while (thread.frames.front().nextInstr < root.body.size())
 	{
-		code[t.topFrame().nextInstr++]->execute(&t);
-		cout << "size: " << t.topFrame().stack.size() << endl;
-		if (t.topFrame().stack.size() > 0)
-			cout << "[0]: " << dynamic_cast<Integer*>(t.topFrame().stack[0])->value << endl;
-		if (t.topFrame().stack.size() > 1)
-			cout << "[1]: " << dynamic_cast<Integer*>(t.topFrame().stack[1])->value << endl;
+		Thread::Frame& frame = thread.frames.back();
+		frame.scope->method()->body[frame.nextInstr++]->execute(&thread);
+		cout << "stack size: " << thread.frames.back().stack.size() << endl;
 	}
 	
-	cout << "x = " << dynamic_cast<Integer*>(t.topFrame().scope->locals["x"])->value << endl;
-	cout << "heap size: " << t.heap.size() << "\n";
+	cout << "x = " << dynamic_cast<Integer*>(thread.frames.back().scope->locals["x"])->value << endl;
+	
+	cout << "heap size: " << heap.values.size() << "\n";
 	cout << "garbage collecting\n";
-	t.garbageCollect();
-	cout << "heap size: " << t.heap.size() << "\n";
+	heap.garbageCollect(&thread);
+	cout << "heap size: " << heap.values.size() << "\n";
 }