From d6d72af4eaf62f69d209177e674ed898d314db9f Mon Sep 17 00:00:00 2001 From: Elijah Cohen Date: Sun, 21 Jul 2024 15:43:08 -0500 Subject: [PATCH] rewrote for consistency among pointer use, started stuff --- ideas.org | 8 ++++++++ src/dict.c | 39 ++++++++++++++++++++++++++++++++++++++ src/dict.h | 20 ++++++++++++++++++++ src/eval.c | 26 ++++++++++++++++++++++++++ src/parser.c | 46 +++++++-------------------------------------- src/sexpr.c | 53 +++++++++++++++++++++++++++++----------------------- src/sexpr.h | 6 +++--- src/test.c | 42 ++++++++++++++++++++--------------------- src/types.h | 15 ++++++++++++--- 9 files changed, 166 insertions(+), 89 deletions(-) create mode 100644 src/dict.c create mode 100644 src/dict.h create mode 100644 src/eval.c diff --git a/ideas.org b/ideas.org index 2915181..3b6a1e7 100644 --- a/ideas.org +++ b/ideas.org @@ -51,3 +51,11 @@ or I could just make a fully-functional forth of sorts how do i implement closures? how do i make sure things actually evaluate once they've got enough arguments? maybe have a closure as a struct containing the builtin's opcode, plus a list of args, plus a down-counter for how many args until execution triggers? + +i think i need to revive my idea of using fexprs as well as normal functions +potentially store closures as just attaching arguments to functions in some sort of structure? as in +struct builtin: +uint opcode +uint args +uint args_left +sexpr* arglist diff --git a/src/dict.c b/src/dict.c new file mode 100644 index 0000000..7ff7bb5 --- /dev/null +++ b/src/dict.c @@ -0,0 +1,39 @@ + + +#include "sexpr.h" +#include "dict.h" + +#define HT_SIZE (2<<16) + + +// okay, doing an incredibly /incredibly/ naive dict implementation for now, +// proper hash tables come later + +// wait, this naive method can totally just be done in sexprs that I already have + +Sexpr* init_dict() { + return from_nil(); +} + +Sexpr* append_to_dict(Sexpr* dict, Sexpr* key, Sexpr* value) { + // assumes dict well-formed, returns new dict + Sexpr* new = cons(key, value); + return cons(new, dict); +} + + + + + +uint64_t hash(char* s) { + uint64_t hash = 0; + uint64_t p = 31; + uint64_t p_to_pow = 1; + uint64_t m = HT_SIZE; + if(s==NULL) return hash; + while(*s != '\0') { + hash = (hash + p_to_pow*(*s - 'A'+1)) % m; + p_to_pow = (p_to_pow*p) % m; + } + return hash; +} diff --git a/src/dict.h b/src/dict.h new file mode 100644 index 0000000..612078a --- /dev/null +++ b/src/dict.h @@ -0,0 +1,20 @@ +#ifndef _DICT_H +#define _DICT_H + +#include "types.h" +#include +#include + +// everything needed for the dictionary + +// key type is string, value type is sexpr, hash range is uint64_t + +typedef struct KV_Pair { + uint64_t key; + Sexpr* val; +} KV_Pair_t; + +uint64_t hash(char* s); + + +#endif diff --git a/src/eval.c b/src/eval.c new file mode 100644 index 0000000..9d68efe --- /dev/null +++ b/src/eval.c @@ -0,0 +1,26 @@ + +#include +#include + +#include "types.h" +#include "sexpr.h" + + +Sexpr* eval(Sexpr* s) { + // non-null s + // generally assumes that a sexpr passed to this is well-formed (ie no inapt NULLS) + // question: does a completed builtin get evaluated here? + if(s == NULL) return NULL; // not needed if assumptions accurate, but yknow + if(s->type == SYM) { + // look up the value in the lookup table + return s; + } + if(s->type != CONS) { + return s; + } // from now on: type is cons + if(cdr(s) == NULL) { + return car(s); + } // from now on: a function of some sort is being called + + return NULL; +} diff --git a/src/parser.c b/src/parser.c index cdf5826..55e8380 100644 --- a/src/parser.c +++ b/src/parser.c @@ -78,7 +78,7 @@ Sexpr* vals_parse(Sexpr* tokens) { Sexpr* out = from_nil(); Sexpr* next = NULL; while(tokens->type != NIL) { - char* s = car(*tokens)->value.s; + char* s = car(tokens)->value.s; if(is_u64(s)) { uint64_t u; sscanf(s, "%" SCNu64, &u); @@ -88,43 +88,11 @@ Sexpr* vals_parse(Sexpr* tokens) { next = from_sym(s); } out = cons(next, out); - tokens = cdr(*tokens); + tokens = cdr(tokens); } return out; } -Sexpr* cons_parse_bork(Sexpr* tokens) { - // dunno if it reverses yet - //Sexpr* out = from_nil(); - Sexpr* curr = from_nil(); - Sexpr* nesting_stack = from_nil(); - while(tokens->type != NIL) { - if(tokens->type == SYM) { - printf("issym\n"); - } - if(tokens->type == SYM && strcmp("(", car(*tokens)->value.s)==0) { - printf("open\n"); - nesting_stack = cons(curr, nesting_stack); - curr = from_nil(); - } - else if(tokens->type == SYM && strcmp(")", car(*tokens)->value.s)==0) { - printf("close\n"); - if(nesting_stack->type ==NIL) { - printf("unbalanced parens...?\n"); - return NULL; - } - curr = cons(curr, car(*nesting_stack)); - nesting_stack = cdr(*nesting_stack); - } - else { - // uhh just append to front? yeah ig - curr = cons(car(*tokens), curr); - tokens = cdr(*tokens); - } - } - // todo free nesting stack here - return curr; -} Sexpr* cons_parse(Sexpr* tokens) { Sexpr* reversed = reverse(tokens); @@ -133,21 +101,21 @@ Sexpr* cons_parse(Sexpr* tokens) { Sexpr* curr_head = from_nil(); Sexpr* curr_car; while(reversed->type != NIL) { - curr_car = car(*reversed); + curr_car = car(reversed); Sexpr_Type cartype = curr_car->type; if(cartype == SYM && strcmp(")", curr_car->value.s)==0) { heads_stack = cons(curr_head, heads_stack); curr_head = from_nil(); } else if(cartype == SYM && strcmp("(", curr_car->value.s)==0) { - Sexpr* prev_head = car(*heads_stack); + Sexpr* prev_head = car(heads_stack); curr_head = cons(curr_head, prev_head); - heads_stack = cdr(*heads_stack); + heads_stack = cdr(heads_stack); } else { curr_head = cons(curr_car, curr_head); } - reversed = cdr(*reversed); + reversed = cdr(reversed); } return curr_head; } @@ -158,7 +126,7 @@ Sexpr* parse(char* s) { Sexpr* tokens = tokenize(s); //printf("t: %s\n", sprint_sexpr(*tokens)); Sexpr* vals = vals_parse(tokens); - printf("v: %s\n", sprint_sexpr(*vals)); + //printf("v: %s\n", sprint_sexpr(vals)); Sexpr* done = cons_parse(vals); //printf("c: %s\n", sprint_sexpr(*done)); return done; diff --git a/src/sexpr.c b/src/sexpr.c index 6e3a896..01286af 100644 --- a/src/sexpr.c +++ b/src/sexpr.c @@ -39,11 +39,11 @@ Sexpr* cons(Sexpr* car, Sexpr* cdr) { return s; } -Sexpr* car(Sexpr s) { - return s.value.c->car; +Sexpr* car(Sexpr* s) { + return s->value.c->car; } -Sexpr* cdr(Sexpr s) { - return s.value.c->cdr; +Sexpr* cdr(Sexpr* s) { + return s->value.c->cdr; } @@ -54,56 +54,63 @@ Sexpr* reverse(Sexpr* s) { } Sexpr* out = from_nil(); while(s->type != NIL) { - out = cons(car(*s), out); - s = cdr(*s); + out = cons(car(s), out); + s = cdr(s); } return out; } -char* sprint_sexpr(Sexpr s) { +char* sprint_sexpr(Sexpr* s) { + if(s == NULL) printf("SHIT IT'S NULL\n"); + // assumes not null size_t nbytes; char* out; - if(s.type == NIL) { + if(s->type == NIL) { out = malloc(4*sizeof(char)); strcpy(out, "nil"); return out; } - else if(s.type == T) { + else if(s->type == T) { out = malloc(2*sizeof(char)); strcpy(out, "t"); return out; } - else if(s.type == SYM) { - out = malloc(sizeof(char)*(strlen(s.value.s)+1)); - strcpy(out, s.value.s); + else if(s->type == SYM) { + out = malloc(sizeof(char)*(strlen(s->value.s)+1)); + strcpy(out, s->value.s); return out; } - else if(s.type == BUILTIN) { + else if(s->type == FUN) { out = malloc(6*sizeof(char)); - strcpy(out, ""); + strcpy(out, ""); return out; } - else if(s.type == UINT) { - nbytes = snprintf(NULL, 0, "%" PRIu64 "", s.value.u) + 1; + else if(s->type == FEXP) { + out = malloc(7*sizeof(char)); + strcpy(out, ""); + return out; + } + else if(s->type == UINT) { + nbytes = snprintf(NULL, 0, "%" PRIu64 "", s->value.u) + 1; out = malloc(nbytes*sizeof(char)); - snprintf(out, nbytes, "%" PRIu64 "", s.value.u); + snprintf(out, nbytes, "%" PRIu64 "", s->value.u); return out; } - else if(s.type == CONS) { - Sexpr curr_cell = s; + else if(s->type == CONS) { + Sexpr* curr_cell = s; size_t currsize = 2; out = malloc(currsize*sizeof(char)); out[0] = '('; out[1] = '\0'; - while(curr_cell.type == CONS) { - char* carstr = sprint_sexpr(*car(curr_cell)); + while(curr_cell->type == CONS) { + char* carstr = sprint_sexpr(car(curr_cell)); currsize += strlen(carstr) + 1; // trailing space/close paren out = realloc(out, currsize); strcat(out, carstr); strcat(out, " "); - curr_cell = *cdr(curr_cell); + curr_cell = cdr(curr_cell); } - if(curr_cell.type == NIL) { + if(curr_cell->type == NIL) { out[currsize-2] = ')'; out[currsize-1] = '\0'; return out; diff --git a/src/sexpr.h b/src/sexpr.h index cfeca9a..4bc42d3 100644 --- a/src/sexpr.h +++ b/src/sexpr.h @@ -12,12 +12,12 @@ Sexpr* from_uint(uint64_t u); Sexpr* cons(Sexpr* car, Sexpr* cdr); -Sexpr* car(Sexpr s); +Sexpr* car(Sexpr* s); -Sexpr* cdr(Sexpr s); +Sexpr* cdr(Sexpr* s); Sexpr* reverse(Sexpr* s); -char* sprint_sexpr(Sexpr s); +char* sprint_sexpr(Sexpr* s); #endif diff --git a/src/test.c b/src/test.c index 5e747ed..01277d0 100644 --- a/src/test.c +++ b/src/test.c @@ -12,24 +12,24 @@ void test_basics() { printf("testing basics...\n"); Sexpr* nil = from_nil(); - printf("nil: %s\n", sprint_sexpr(*nil)); + printf("nil: %s\n", sprint_sexpr(nil)); Sexpr* sym = from_sym("testsym"); - printf("sym: %s\n", sprint_sexpr(*sym)); + printf("sym: %s\n", sprint_sexpr(sym)); Sexpr* cons1 = cons(sym, nil); Sexpr* cons2 = cons(nil, sym); - printf("cons1: %s\n", sprint_sexpr(*cons1)); - printf("cons2: %s\n", sprint_sexpr(*cons2)); + printf("cons1: %s\n", sprint_sexpr(cons1)); + printf("cons2: %s\n", sprint_sexpr(cons2)); Sexpr* sym2 = from_sym("nothersym"); - printf("sym2: %s\n", sprint_sexpr(*sym2)); + printf("sym2: %s\n", sprint_sexpr(sym2)); Sexpr* cons3 = cons(sym2, cons2); - printf("cons2: %s\n", sprint_sexpr(*cons2)); - printf("cons3: %s\n", sprint_sexpr(*cons3)); + printf("cons2: %s\n", sprint_sexpr(cons2)); + printf("cons3: %s\n", sprint_sexpr(cons3)); Sexpr* cons4 = cons(sym2, cons1); - printf("cons4: %s\n", sprint_sexpr(*cons4)); + printf("cons4: %s\n", sprint_sexpr(cons4)); Sexpr* cons5 = cons(cons4, cons4); - printf("cons5: %s\n", sprint_sexpr(*cons5)); + printf("cons5: %s\n", sprint_sexpr(cons5)); Sexpr* ui = from_uint(54362); - printf("ui: %s", sprint_sexpr(*ui)); + printf("ui: %s\n", sprint_sexpr(ui)); } void test2() { @@ -44,32 +44,32 @@ void test2() { cc = cons(c, cc); cc = cons(b, cc); cc = cons(a, cc); - printf("all: %s\n", sprint_sexpr(*cc)); + printf("all: %s\n", sprint_sexpr(cc)); } void test_parsing() { printf("testing parsing...\n"); - printf("basic: %s\n", sprint_sexpr(*from_sym("hello"))); + printf("basic: %s\n", sprint_sexpr(from_sym("hello"))); Sexpr* t1 = tokenize("a b c d e f g"); - printf("t1: %s\n", sprint_sexpr(*reverse(t1))); + printf("t1: %s\n", sprint_sexpr(reverse(t1))); Sexpr* t2 = tokenize("(a b (c d) e)"); - printf("t1: %s\n", sprint_sexpr(*reverse(t2))); + printf("t1: %s\n", sprint_sexpr(reverse(t2))); - printf("%s\n", sprint_sexpr(*reverse(tokenize("a b c d ef g")))); + printf("%s\n", sprint_sexpr(reverse(tokenize("a b c d ef g")))); } void test_parser() { printf("parsing again...\n"); - printf("_: %s\n", sprint_sexpr(*parse("457"))); - printf("_: %s\n", sprint_sexpr(*parse("a b c d e"))); - printf("_: %s\n", sprint_sexpr(*parse("(a b (3 2 (5) c) d (e f) g)"))); + printf("_: %s\n", sprint_sexpr(parse("457"))); + printf("_: %s\n", sprint_sexpr(parse("a b c d e"))); + printf("_: %s\n", sprint_sexpr(parse("(a b (3 2 (5) c) d (e f) g)"))); } void run_tests(){ - //test_basics(); - //test2(); - //test_parsing(); + test_basics(); + test2(); + test_parsing(); test_parser(); } diff --git a/src/types.h b/src/types.h index 50845fe..b5a881a 100644 --- a/src/types.h +++ b/src/types.h @@ -8,13 +8,12 @@ #include #include -typedef uint64_t Builtin; typedef char* Symbol_t; typedef void* Nil_t; typedef void* Truth_t; typedef enum Sexpr_Type { - UINT, SYM, BUILTIN, NIL, T, CONS + UINT, SYM, BUILTIN, NIL, T, CONS, FEXP, FUN } Sexpr_Type; // to be used rarely, mainly only in eval i think typedef struct Cons { @@ -22,10 +21,20 @@ typedef struct Cons { struct Sexpr* cdr; } Cons_t; +typedef struct Closure { + uint64_t opcode; + uint64_t num_args; + uint64_t len_args; + struct Sexpr* arglist; +} Closure_t; +typedef Closure_t Fexpr_t; +typedef Closure_t Fun_t; + typedef struct Sexpr { Sexpr_Type type; union { - Builtin b; + Fexpr_t x; + Fun_t f; uint64_t u; Symbol_t s; Cons_t* c; -- 2.39.2