changeset 170:18598163e3ef

Add linked list implementation and cons operator
author Mike Pavone <pavone@retrodev.com>
date Tue, 13 Aug 2013 21:58:03 -0700
parents 075b1e71feff
children 869399ff7faa
files cbackend.js compiler.js modules/list.tp parser.js runtime/object.h runtime/progfoot.inc samples/slist.tp
diffstat 7 files changed, 93 insertions(+), 9 deletions(-) [+]
line wrap: on
line diff
--- a/cbackend.js	Fri Aug 09 21:01:11 2013 -0700
+++ b/cbackend.js	Tue Aug 13 21:58:03 2013 -0700
@@ -14,7 +14,9 @@
 
 function getOpMethodName(opname)
 {
-	var optoMeth = {'+': 'ADD_', '-': 'SUB_', '*': 'MUL_', '/': 'DIV_', '%': 'MOD_', '=': 'EQ_', '!=': 'NEQ_', '<': 'LT_', '>': 'GT_', '>=': 'GEQ_', '<=': 'LEQ_', '.': 'CAT_', '&&':'if', '||':'ifnot'};
+	var optoMeth = {'+': 'ADD_', '-': 'SUB_', '*': 'MUL_', '/': 'DIV_', '%': 'MOD_',
+	                '=': 'EQ_', '!=': 'NEQ_', '<': 'LT_', '>': 'GT_', '>=': 'GEQ_', '<=': 'LEQ_',
+					'.': 'CAT_', '&&':'if', '||':'ifnot', '|': 'CONS_'};
 	if (opname in optoMeth) {
 		return optoMeth[opname];
 	} else {
@@ -24,7 +26,11 @@
 
 op.prototype.toC = function(isReceiver) {
 	var method = getOpMethodName(this.op);
-	return 'mcall(' + getMethodId(method) + '/* operator ' + method + ' */, 2, (object *)' + this.left.toC() + ', ' + this.right.toC() + ')\n';
+	if (this.op == '|') {
+		return 'mcall(' + getMethodId(method) + '/* operator ' + method + ' */, 2, (object *)' + this.right.toC() + ', ' + this.left.toC() + ')\n';
+	} else {
+		return 'mcall(' + getMethodId(method) + '/* operator ' + method + ' */, 2, (object *)' + this.left.toC() + ', ' + this.right.toC() + ')\n';
+	}
 };
 op.prototype.toCLLExpr = function(vars) {
 	var opmap = {'=': '==', 'xor': '^'};
@@ -181,7 +187,7 @@
 
 listlit.prototype.toC = function() {
 	var ret = 'make_list(' + this.val.length;
-	for (var i = 0; i < this.val.length; i++) {
+	for (var i = this.val.length-1; i >= 0; i--) {
 		ret += ', ' + this.val[i].toC();
 	}
 	return ret + ')';
@@ -845,7 +851,7 @@
 
 function processUsedToplevel(toplevel)
 {
-	var alwaysused = ['true', 'false'];
+	var alwaysused = ['true', 'false', 'list'];
 	var ret = '';
 	var modulenum = 0;
 	var visited = {};
@@ -895,6 +901,8 @@
 	var rest = 'object * mainModule() {\n' + moduleinit + '\tmain_module = ' + obj.toCModuleInstance() + ';\n\treturn main_module;\n}\n';
 	return '#include "runtime/proghead.inc"\n' +
 		'#define METHOD_ID_MAIN ' + getMethodId('main') + '\n' +
+		'#define METHOD_ID_EMPTY ' + getMethodId('empty') + '\n' +
+		'#define METHOD_ID_CONS ' + getMethodId(getOpMethodName('|')) + '\n' +
 		forwarddec + toplevelcode + rest + '#include "runtime/progfoot.inc"\n';
 }
 
--- a/compiler.js	Fri Aug 09 21:01:11 2013 -0700
+++ b/compiler.js	Tue Aug 13 21:58:03 2013 -0700
@@ -99,7 +99,7 @@
 	if (!(name in this.names)) {
 		throw new Error('symbol ' + name + ' not found at toplevel');
 	}
-	if (name == 'true' || name == 'false') {
+	if (name == 'true' || name == 'false' || name == 'list') {
 		return 'module_' + name;
 	}
 	if (!this.names[name].modulevar) {
@@ -232,7 +232,7 @@
 			if (nestedcall) {
 				this.closedover[name] = true;
 				this.passthruenv = false;
-			} 
+			}
 			if (name in this.closedover) {
 				var ret = {
 					type: 'closedover',
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/modules/list.tp	Tue Aug 13 21:58:03 2013 -0700
@@ -0,0 +1,48 @@
+{
+	_empty <- #{
+		length <- { 0 }
+		empty? <- { true }
+		fold:with <- :acc :fun { acc }
+		foldr:with <- :acc :fun { acc }
+		map <- :fun { self }
+		| <- :val {
+			list node: val withTail: self
+		}
+		. <- :right { right }
+	}
+	#{
+		empty <- { _empty }
+		node:withTail <- :_val :_tail {
+			#{
+				value <- { _val }
+				tail <- { _tail }
+				empty? <- { false }
+				length <- {
+					fold: 0 with: :acc val { acc + 1 }
+				}
+				fold:with <- :acc :fun {
+					cur <- self
+					while: { not: (cur empty?)} do: {
+						acc <- fun: acc (cur value)
+						cur <- cur tail
+					}
+					acc
+				}
+				foldr:with <- :acc fun {
+					fun: (_tail foldr: acc with: fun) _val
+				}
+				map <- :fun {
+					node: (fun: _val) withTail: (_tail map: fun)
+				}
+				| <- :val {
+					node: val withTail: self
+				}
+				. <- :right {
+					foldr: right with: :tail val {
+						node: val withTail: tail
+					}
+				}
+			}
+		}
+	}
+}
--- a/parser.js	Fri Aug 09 21:01:11 2013 -0700
+++ b/parser.js	Tue Aug 13 21:58:03 2013 -0700
@@ -80,7 +80,9 @@
 'hws = ([ \\t] / "/*" ([^*] / "*" ! "/")* "*/" )*;' +
 'expr = e:(funcall / methcall / opexpr) ws { return e; };' +
 'opexpr = left:compareop pieces:(hws ("&&" / "||") hws compareop)* { if (pieces.length) { var cur = new op(left, pieces[0][1], pieces[0][3]); for (var i = 1; i < pieces.length; i++) { cur = new op(cur, pieces[i][1], pieces[i][3]); } return cur; } else { return left; } };'+
-'compareop = left:addsub pieces:(hws ("<=" / ">=" / "<" / ">" / "=" / "!=") hws addsub)* { if (pieces.length) { var cur = new op(left, pieces[0][1], pieces[0][3]); for (var i = 1; i < pieces.length; i++) { cur = new op(cur, pieces[i][1], pieces[i][3]); } return cur; } else { return left; } };'+
+'compareop = left:maybecons pieces:(hws ("<=" / ">=" / "<" / ">" / "=" / "!=") hws maybecons)* { if (pieces.length) { var cur = new op(left, pieces[0][1], pieces[0][3]); for (var i = 1; i < pieces.length; i++) { cur = new op(cur, pieces[i][1], pieces[i][3]); } return cur; } else { return left; } };'+
+'maybecons = consop / addsub;' +
+'consop = left:addsub hws "|" hws right:maybecons { return new op(left, "|", right); };'+
 'addsub = left:muldiv pieces:(hws ("+"/"-"/"xor"/"and"/"or"/".") hws muldiv)* { if (pieces.length) { var cur = new op(left, pieces[0][1], pieces[0][3]); for (var i = 1; i < pieces.length; i++) { cur = new op(cur, pieces[i][1], pieces[i][3]); } return cur; } else { return left; } };'+
 'muldiv = left:primlitsym pieces:(hws ("*"/"/"/"%") hws primlitsym)* { if (pieces.length) { var cur = new op(left, pieces[0][1], pieces[0][3]); for (var i = 1; i < pieces.length; i++) { cur = new op(cur, pieces[i][1], pieces[i][3]); } return cur; } else { return left; } };'+
 'primlitsym = hws val:(float / hex / binary / int / string / symbol / object / array / list / lambda / "(" ws expr:expr hws ")" { return expr; }) { return val; };' +
@@ -95,7 +97,7 @@
 'object = "#{" ws messages:(assignment / funexpr)* "}" { return new object(messages); };' +
 'array = "#[" ws els:opexpr* "]" { return new arraylit(els); };' +
 'list = "[" ws els:opexpr* "]" { return new listlit(els); };' +
-'opsym = name:("&&" / "||" / "<=" / ">=" / "<" / ">" / "=" / "!=" / "+" / "-" / "." / "*" / "/" / "%") { return new symbol(name); };' +
+'opsym = name:("&&" / "||" / "<=" / ">=" / "<" / ">" / "=" / "!=" / "+" / "-" / "." / "*" / "/" / "%" / "|") { return new symbol(name); };' +
 'assignment = ws sym:(symbol / opsym) hws "<-" expr:expr ws { return new assignment(sym, expr); }' +
 'lambda = args:((& ":") argname+  )? "{" ws exprs:(assignment / expr)* "}" { return new lambda(args[1], exprs); };' +
 'argname = init:":"? chars:[a-zA-Z_!?@]+ trailing:[a-zA-Z_!?@0-9]* hws { return new symbol(init + chars.join("") + trailing.join("")); };' +
--- a/runtime/object.h	Fri Aug 09 21:01:11 2013 -0700
+++ b/runtime/object.h	Tue Aug 13 21:58:03 2013 -0700
@@ -37,5 +37,6 @@
 object * make_object(obj_meta * meta, void * parent, int num_props, ...);
 object * make_lambda(void * env, closure_func func);
 object * make_array(uint32_t num_els, ...);
+object * make_list(uint32_t num_els, ...);
 
 #endif //OBJECT_H_
--- a/runtime/progfoot.inc	Fri Aug 09 21:01:11 2013 -0700
+++ b/runtime/progfoot.inc	Tue Aug 13 21:58:03 2013 -0700
@@ -16,7 +16,7 @@
 {
 	va_list els;
 	int i;
-	array * arr = alloc_array(num_els);	
+	array * arr = alloc_array(num_els);
 	va_start(els, num_els);
 	for (i = 0; i < num_els; i++)
 		arr->data[i] = va_arg(els, object *);
@@ -24,6 +24,18 @@
 	return &(arr->header);
 }
 
+object * make_list(uint32_t num_els, ...)
+{
+	va_list els;
+	int i;
+	object * cur = mcall(METHOD_ID_EMPTY, 1, module_list);
+	va_start(els, num_els);
+	for (i = 0; i < num_els; i++)
+		cur = mcall(METHOD_ID_CONS, 2, cur, va_arg(els, object *));
+	va_end(els);
+	return cur;
+}
+
 object * make_lambda(void * env, closure_func func)
 {
 	lambda * ret = GC_MALLOC(sizeof(lambda));
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/samples/slist.tp	Tue Aug 13 21:58:03 2013 -0700
@@ -0,0 +1,13 @@
+#{
+	sum <- :l {
+		l fold: 0 with: :acc el {
+			acc + el
+		}
+	}
+	main <- {
+		print: (string: (sum: [])) . "\n"
+		print: (string: (sum: [1 2 3 4])) . "\n"
+		print: (string: (sum: 1 | 2 | 3 | 4 | [])) . "\n"
+		print: (string: (sum: [1 2] . [3 4])) . "\n"
+	}
+}