start implementing mark&sweep

6 files changed, 116 insertions, 4 deletions

diff --git a/Makefile b/Makefile
index 3b7dee5..944c62e 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 LEX     = flex
 YACC    = bison
 CC      = gcc -g
-CFLAGS  = -DYYDEBUG=1 -fPIC
+CFLAGS  = -DYYDEBUG=1 -fPIC -rdynamic
 LIBS    = -lreadline -lfl -lm
 OBJS	= lisp.o lisp.tab.o lex.yy.o
 
diff --git a/README.ORG b/README.ORG
index a1353af..ad059ac 100644
--- a/README.ORG
+++ b/README.ORG
@@ -8,3 +8,4 @@ using lex and yacc
 + [[https://github.com/Robert-van-Engelen/tinylisp/blob/main/tinylisp.pdf][tinylisp.pdf]]
 + [[https://w3.pppl.gov/info/readline/A_Short_Completion_Example.html][pppl.gov readline]]
 + [[https://web.mit.edu/6.001/6.037/sicp.pdf][SICP]]
++ [[https://www.youtube.com/watch?v=c32zXYAK7CI][Garbage Collection (Mark & Sweep) - Computerphile]]
diff --git a/lisp.c b/lisp.c
index 792fabe..891d371 100644
--- a/lisp.c
+++ b/lisp.c
@@ -9,10 +9,14 @@
 #include "lex.yy.h"
 #include "lisp.tab.h"
 
+reg *global_reg = NULL;
+
 value *make_int(int i) {
 	value *val = malloc(sizeof(value));
 	val->type = VT_INT;
 	val->as.i = i;
+	val->reachable = 0;
+	reg_add(val);
 	return val;
 }
 
@@ -20,6 +24,8 @@ value *make_double(double d) {
 	value *val = malloc(sizeof(value));
 	val->type = VT_DOUBLE;
 	val->as.d = d;
+	val->reachable = 0;
+	reg_add(val);
 	return val;
 }
 
@@ -27,6 +33,8 @@ value *make_symbol(const char *s) {
 	value *val = malloc(sizeof(value));
 	val->type = VT_SYMBOL;
 	val->as.sym = strdup(s);
+	val->reachable = 0;
+	reg_add(val);
 	return val;
 }
 
@@ -34,6 +42,8 @@ value *make_string(const char *s) {
 	value *val = malloc(sizeof(value));
 	val->type = VT_STRING;
 	val->as.str = strdup(s);
+	val->reachable = 0;
+	reg_add(val);
 	return val;
 }
 
@@ -42,6 +52,9 @@ value *make_nil() {
 	if (!NIL) {
 		NIL = malloc(sizeof(value));
 		NIL->type = VT_NIL;
+		NIL->reachable = 1;
+		NIL->as.pair.car = NIL; //might be bogus
+		NIL->as.pair.cdr = NIL; //might be bogus
 	}
 	return NIL;
 }
@@ -52,6 +65,8 @@ value *make_lambda(env *e, value *params, value *body) {
 	l->as.lambda.params = params;
 	l->as.lambda.body = body;
 	l->as.lambda.env = e;
+	l->reachable = 0;
+	reg_add(l);
 	return l;
 }
 
@@ -59,6 +74,7 @@ value *make_procedure(value *(*fn) (env *, value *)) {
 	value *val = malloc(sizeof(value));
 	val->type = VT_PROCEDURE;
 	val->as.procedure.fn = fn;
+	reg_add(val);
 	return val;
 }
 
@@ -66,6 +82,7 @@ value *make_error(const char *s) {
 	value *val = malloc(sizeof(value));
 	val->type = VT_ERROR;
 	val->as.err = strdup(s);
+	reg_add(val);
 	return val;
 }
 
@@ -83,6 +100,7 @@ value *make_thunk(env *e, value *expr) {
 	val->as.thunk.expr = expr;
 	val->as.thunk.cached = NULL;
 	val->as.thunk.env = e;
+	reg_add(val);
 	return val;
 }
 
@@ -105,6 +123,7 @@ value *cons(value *car, value *cdr) {
 	val->type = VT_PAIR;
 	val->as.pair.car = car;
 	val->as.pair.cdr = cdr;
+	reg_add(val);
 	return val;
 }
 
@@ -128,7 +147,7 @@ value *cdr(value *cons) {
 
 value *reverse(value *list) {
 	value *reversed = make_nil();
-	for(value *a = list; a->type == VT_PAIR; a = cdr(a)) {
+	for (value *a = list; a->type == VT_PAIR; a = cdr(a)) {
 		reversed = cons(car(a), reversed);
 	}
 	return reversed;
@@ -195,7 +214,7 @@ void print_value(value *val) {
 			break;
 
 		case VT_PROCEDURE:
-			printf("<procedure>\n");
+			printf("<procedure>");
 			break;
 
 		case VT_ERROR:
@@ -425,3 +444,77 @@ value *procedure_load_module(env *e, value *args) {
 int is_integer(double x) {
 	return floor(x) == x && isfinite(x);
 }
+
+reg *reg_add(value *val) {
+	reg *new = malloc(sizeof(reg));
+	new->value = val;
+	new->next = global_reg;
+	global_reg = new;
+	return new;
+}
+
+int mark_val(value *val) {
+	if(!val) {
+		return 0;
+	}
+	//println_value(val);
+	switch (val->type) {
+		case VT_INT:
+		case VT_DOUBLE:
+		case VT_SYMBOL:
+		case VT_STRING:
+		case VT_ERROR:
+		case VT_PROCEDURE:
+			val->reachable = 1;
+			return 1;
+
+		case VT_PAIR:
+			printf("inside pair\n");
+			val->reachable = 1;
+			return 1 + mark_val(val->as.pair.car)
+			         + mark_val(val->as.pair.cdr);
+			break;
+
+		case VT_LAMBDA:
+			printf("test\n");
+			val->reachable = 1;
+			return 1 + mark_val(val->as.lambda.params)
+			         + mark_val(val->as.lambda.body);
+			         + mark_env(val->as.lambda.env);
+			break;
+
+		case VT_THUNK:
+			val->reachable = 1;
+			return 1 + mark_val(val->as.thunk.expr)
+			         + mark_val(val->as.thunk.cached);
+			         + mark_env(val->as.thunk.env);
+			break;
+
+		case VT_NIL:
+		default:
+			return 0;
+	}
+}
+
+int mark_env(env *envi) {
+	int count=0;
+	for (env *e = envi; e; e = e->next) {
+		if (e->value) {
+			count += mark_val(e->value);
+		}
+	}
+	printf("mark_env count: %d\n", count);
+	return count;
+}
+
+int sweep() {
+	for (reg *r = global_reg; r; r = r->next) {
+		if (r->value->reachable) {
+			printf("reachable:");
+			println_value(r->value);
+		} else {
+			printf("unreachable:");
+			println_value(r->value);
+		}
+	}
+}
diff --git a/lisp.h b/lisp.h
index a747b8d..c857b02 100644
--- a/lisp.h
+++ b/lisp.h
@@ -3,6 +3,7 @@
 
 typedef struct value value;
 typedef struct env env;
+typedef struct reg reg;
 
 // environments, TODO: make this use hashtable
 // symbol->val
@@ -16,7 +17,6 @@ typedef struct env {
 env *env_create(env *parent);
 env *env_define(env *e, const char *sym, value *val);
 value *env_lookup(env *e, const char *sym);
-
 extern env *global_env;
 
 value *eval_pair(env *e, value *val);
@@ -25,4 +25,16 @@ value *apply(value *lambda, value *args);
 
 value *procedure_load_module(env *e, value *args);
 
+typedef struct reg {
+	value *value;
+	reg *next;
+} reg;
+
+reg *reg_add(value *val);
+void free_value(reg *r);
+extern reg *global_reg;
+int mark_env(env *e);
+int mark_val(value *v);
+int sweep();
+
 #endif
diff --git a/lisp_api.h b/lisp_api.h
index 90e05e1..9527551 100644
--- a/lisp_api.h
+++ b/lisp_api.h
@@ -48,6 +48,7 @@ struct value {
 			env *env;
 		} thunk;
 	} as;
+	int reachable;
 };
 
 value *make_int(int i);
diff --git a/main.c b/main.c
index 84d585c..695b7d7 100644
--- a/main.c
+++ b/main.c
@@ -92,6 +92,8 @@ void init_readline() {
 }
 
 int main(int argc, char **argv) {
+	// init global value register
+	global_reg = NULL;
 	// init global env
 	global_env = env_create(NULL);
 	env_define(global_env, "load_module", make_procedure(procedure_load_module));
@@ -139,6 +141,9 @@ int main(int argc, char **argv) {
 			prompt = "   ";
 		}
 		free(line);
+		int marked = mark_env(global_env); //maybe do this somewhere else?
+		printf("marked: %d\n", marked);
+		sweep();
 	}
 	return 0;
 }