From 92a1c58179183493647959838c8ad13975ece47c Mon Sep 17 00:00:00 2001
From: Bad Diode <bd@badd10de.dev>
Date: Fri, 8 Oct 2021 17:53:28 +0200
Subject: Change list representation to be a linked list

---
 src/bootstrap/main.c | 90 ++++++++++++++++++++++++++++++++--------------------
 1 file changed, 55 insertions(+), 35 deletions(-)

diff --git a/src/bootstrap/main.c b/src/bootstrap/main.c
index 241697a..a8e39f5 100755
--- a/src/bootstrap/main.c
+++ b/src/bootstrap/main.c
@@ -211,7 +211,6 @@ typedef enum ObjectType {
     OBJ_TYPE_SYMBOL,
     OBJ_TYPE_STRING,
     OBJ_TYPE_PAIR,
-    OBJ_TYPE_LIST,
 } ObjectType;
 
 typedef struct Object {
@@ -235,13 +234,6 @@ typedef struct Object {
             struct Object *cdr;
         };
 
-        // OBJ_TYPE_LIST
-        struct {
-            // NOTE: Probably want to do this as a linked list using pairs.
-            struct Object **list;
-            size_t list_n;
-        };
-
         // OBJ_TYPE_SYMBOL
         struct {
             char *symbol;
@@ -250,6 +242,12 @@ typedef struct Object {
     };
 } Object;
 
+//
+// Singletons.
+//
+
+Object *empty_list;
+
 Object *
 make_fixnum(ssize_t num) {
     Object *obj = malloc(sizeof(Object));
@@ -303,25 +301,24 @@ Object *
 make_empty_list(void) {
     Object *obj = malloc(sizeof(Object));
     obj->type = OBJ_TYPE_NIL;
-    obj->list = NULL;
-    obj->list_n = 0;
     return obj;
 }
 
-void
-push_obj_to_list(Object *list, Object **obj) {
-    assert(list != NULL);
-    assert(list->type == OBJ_TYPE_NIL || list->type == OBJ_TYPE_LIST);
-
-    if (obj == NULL || *obj == NULL) {
-        return;
-    }
+Object *
+make_procedure(Object *(*proc)(struct Object *args)) {
+    Object *obj = malloc(sizeof(Object));
+    obj->type = OBJ_TYPE_PROCEDURE;
+    obj->proc = proc;
+    return obj;
+}
 
-    if (list->type == OBJ_TYPE_NIL) {
-        list->type = OBJ_TYPE_LIST;
-    }
-    list->list = realloc(list->list, (list->list_n + 1) * sizeof(struct Object *));
-    list->list[list->list_n++] = *obj;
+Object *
+cons(Object *car, Object *cdr) {
+    Object *obj = malloc(sizeof(Object));
+    obj->type = OBJ_TYPE_PAIR;
+    obj->car = car;
+    obj->cdr = cdr;
+    return  obj;
 }
 
 bool
@@ -389,15 +386,20 @@ build_ast(Tokens *tokens) {
         }
         if (token->start[0] == '(') {
             if (tokens->n > 0 && tokens->start[0].start[0] == ')') {
-                return make_empty_list();
+                return empty_list;
             }
 
-            Object *list = make_empty_list();
-            Object *next_obj = NULL;
+            Object *next_obj = build_ast(tokens);
+            if (next_obj == NULL) {
+                return NULL;
+            }
+            Object *root = cons(next_obj, empty_list);
+            Object *list = root;
             while (tokens->n > 0 && (next_obj = build_ast(tokens)) != NULL) {
-                push_obj_to_list(list, &next_obj);
+                list->cdr = cons(next_obj, empty_list);
+                list = list->cdr;
             }
-            return list;
+            return root;
         }
 
         // OBJ_TYPE_STRING
@@ -416,6 +418,22 @@ build_ast(Tokens *tokens) {
     return NULL;
 }
 
+void display(Object *root);
+
+void
+display_pair(Object *root) {
+    display(root->car);
+    if (root->cdr->type == OBJ_TYPE_PAIR) {
+        printf(" ");
+        display_pair(root->cdr);
+    } else if (root->cdr->type == OBJ_TYPE_NIL) {
+        return;
+    } else {
+        printf(" . ");
+        display(root->cdr);
+    }
+}
+
 void
 display(Object *root) {
     if (root == NULL) {
@@ -442,14 +460,9 @@ display(Object *root) {
         case OBJ_TYPE_SYMBOL: {
             printf(":%.*s", (int)root->symbol_n, root->symbol);
         } break;
-        case OBJ_TYPE_LIST: {
+        case OBJ_TYPE_PAIR: {
             printf("(");
-            for (size_t i = 0; i < root->list_n; i++) {
-                display(root->list[i]);
-                if ((i + 1) < root->list_n) {
-                    printf(" ");
-                }
-            }
+            display_pair(root);
             printf(")");
         } break;
         default: {
@@ -460,8 +473,15 @@ display(Object *root) {
 
 #define REPL_PROMPT "bdl> "
 
+void
+init(void) {
+    // Initialize singletons.
+    empty_list = make_empty_list();
+}
+
 int
 main(void) {
+    init();
     printf("BDL REPL (Press Ctrl-C to exit)\n");
     while (true) {
         printf(REPL_PROMPT);
-- 
cgit v1.2.1