From 47debf8cc2197187a347b43a795120638b017d5f Mon Sep 17 00:00:00 2001 From: Felix Perktold Date: Sun, 21 Dec 2025 17:00:37 +0100 Subject: renamed enum values VALTYPE->VT, implemented lambdas, apply --- .gitignore | 1 + README.ORG | 1 + lisp.c | 116 +++++++++++++++++++++++++++++++++++++++++++------------------ lisp.h | 26 +++++++++----- test.c | 4 +-- 5 files changed, 105 insertions(+), 43 deletions(-) diff --git a/.gitignore b/.gitignore index 364238c..632497d 100644 --- a/.gitignore +++ b/.gitignore @@ -2,3 +2,4 @@ lex.yy.* lisp.tab.* main +test diff --git a/README.ORG b/README.ORG index 500e08b..8969629 100644 --- a/README.ORG +++ b/README.ORG @@ -5,3 +5,4 @@ using lex and yacc + [[https://github.com/AdhamAfis/yacc-parser-tutorial][yacc-parser-tutorial]] + [[https://en.wikipedia.org/wiki/S-expression][s-expressions]] + [[https://www.bowaggoner.com/writeups/jumpstart/flexbison/jumpstart_flexbison.pdf?utm_source][flex / bison jumpstart]] ++ [[https://github.com/Robert-van-Engelen/tinylisp/blob/main/tinylisp.pdf][tinylisp.pdf]] diff --git a/lisp.c b/lisp.c index 8b29423..357e94c 100644 --- a/lisp.c +++ b/lisp.c @@ -8,41 +8,56 @@ value *make_int(int i) { value *val = malloc(sizeof(value)); - val->type = VALTYPE_INT; + val->type = VT_INT; val->as.i = i; return val; } value *make_double(double d) { value *val = malloc(sizeof(value)); - val->type = VALTYPE_DOUBLE; + val->type = VT_DOUBLE; val->as.d = d; return val; } value *make_symbol(const char *s) { value *val = malloc(sizeof(value)); - val->type = VALTYPE_SYMBOL; + val->type = VT_SYMBOL; val->as.sym = s; return val; } value *make_string(const char *s) { value *val = malloc(sizeof(value)); - val->type = VALTYPE_STRING; + val->type = VT_STRING; val->as.str = s; return val; } value *make_nil() { value *val = malloc(sizeof(value)); - val->type = VALTYPE_NIL; + val->type = VT_NIL; return val; } +value *make_lambda(env *e, value *params, value *body) { + printf("making lambda:\n"); + value *l = malloc(sizeof(value)); + l->type = VT_LAMBDA; + l->as.lambda.params = params; + printf("params: "); + print_value(params); + l->as.lambda.body = body; + printf("\nbody: "); + print_value(body); + printf("\n"); + l->as.lambda.env = e; + return l; +} + value *cons(value *car, value *cdr) { value *val = malloc(sizeof(value)); - val->type = VALTYPE_PAIR; + val->type = VT_PAIR; val->as.pair.car = car; val->as.pair.cdr = cdr; return val; @@ -62,32 +77,40 @@ value *cdr(value *cons) { void *print_value(value *val){ char *str; switch (val->type) { - case VALTYPE_INT: + case VT_INT: printf("%d", val->as.i); break; - case VALTYPE_DOUBLE: + case VT_DOUBLE: printf("%f", val->as.d); break; - case VALTYPE_SYMBOL: + case VT_SYMBOL: printf("%s", val->as.sym); break; - case VALTYPE_STRING: + case VT_STRING: printf("\"%s\"", val->as.str); break; - case VALTYPE_NIL: + case VT_NIL: printf("()"); break; - case VALTYPE_PAIR: + case VT_PAIR: printf("("); print_value(val->as.pair.car); printf(" . "); print_value(val->as.pair.cdr); printf(")"); + break; + + case VT_LAMBDA: + printf("(λ "); + print_value(val->as.lambda.params); + printf(" "); + print_value(val->as.lambda.body); + printf(")"); default: } @@ -132,21 +155,21 @@ value *env_lookup(env *e, const char *sym) { value *eval(env *e, value *v) { value *found; - if (v->type == VALTYPE_NIL) { + if (v->type == VT_NIL) { return v; } - if (v->type == VALTYPE_SYMBOL && + if (v->type == VT_SYMBOL && (found = env_lookup(e, v->as.sym))) { return found; } - if (v->type == VALTYPE_SYMBOL) { + if (v->type == VT_SYMBOL) { printf("symbol %s not found\n", v->as.sym); return v; } - if (v->type == VALTYPE_PAIR) { + if (v->type == VT_PAIR) { return eval_pair(e, v); } @@ -154,24 +177,51 @@ value *eval(env *e, value *v) { } value *eval_pair(env *e, value *v) { - value *head = v->as.pair.car; - value *tail = v->as.pair.cdr; - - if (head->type == VALTYPE_SYMBOL && - tail->type == VALTYPE_PAIR) { - if(!strcmp(head->as.str, "define")) { - value *defargs = cdr(v); - value *defname = car(defargs); - value *defval = eval(e, car(cdr(defargs))); - - if (defname->type != VALTYPE_SYMBOL) { - printf("error, expected symbol, found: "); - print_value(defname); - printf("\n"); - return v; - } - env_define(e, defname->as.sym, defval); + value *head = car(v); + value *tail = cdr(v); + + value *head_eval = eval(e, head); + + if (head_eval->type == VT_LAMBDA) { + apply(head_eval, tail); + } + + if (!strcmp(head->as.str, "define")) { + value *defargs = tail; + value *defname = car(defargs); + value *defval = eval(e, car(cdr(defargs))); + + if (defname->type != VT_SYMBOL) { + printf("error, expected symbol, found: "); + print_value(defname); + printf("\n"); + return v; } + env_define(e, defname->as.sym, defval); + } + + if (!strcmp(head->as.str, "lambda") || + !strcmp(head->as.str, "\\") || + !strcmp(head->as.str, "λ")) { + value *params = car(tail); + value *body = car(cdr(tail)); + + return make_lambda(e, params, body); } return v; } + +value *apply(value *lval, value *args) { + env *sub_env = env_create(lval->as.lambda.env); + value *params = lval->as.lambda.params; + value *arg = args; + + while (params->type == VT_PAIR && arg->type == VT_PAIR) { + env_define(sub_env, + car(params)->as.sym, + eval(lval->as.lambda.env, car(arg))); + params = cdr(params); + arg = cdr(arg); + } + return eval(sub_env, lval->as.lambda.body); +} diff --git a/lisp.h b/lisp.h index 6ebf9a2..a43f750 100644 --- a/lisp.h +++ b/lisp.h @@ -1,16 +1,19 @@ #ifndef LISP_H #define LISP_H +typedef struct value value; +typedef struct env env; + typedef enum { - VALTYPE_INT, - VALTYPE_DOUBLE, - VALTYPE_SYMBOL, - VALTYPE_STRING, - VALTYPE_NIL, - VALTYPE_PAIR + VT_INT, + VT_DOUBLE, + VT_SYMBOL, + VT_STRING, + VT_NIL, + VT_PAIR, + VT_LAMBDA } val_type; -typedef struct value value; struct value { val_type type; union { @@ -22,6 +25,11 @@ struct value { value *car; value *cdr; } pair; + struct { + value *params; + value *body; + env *env; + } lambda; } as; }; @@ -30,6 +38,7 @@ value *make_double(double d); value *make_symbol(const char *sym); value *make_string(const char *str); value *make_nil(); +value *make_lambda(env *e, value *params, value *body); value *cons(value *car, value *cdr); value *car(value *cons); value *cdr(value *cons); @@ -37,7 +46,6 @@ value *cdr(value *cons); void *print_value(value *val); // environments, TODO: make this use hashtable // symbol->val -typedef struct env env; typedef struct env { const char *symbol; value *value; @@ -54,4 +62,6 @@ extern env *global_env; value *eval(env *e, value *val); value *eval_pair(env *e, value *val); +value *apply(value *lambda, value *args); + #endif diff --git a/test.c b/test.c index 0e462b9..9dfe8c6 100644 --- a/test.c +++ b/test.c @@ -22,7 +22,7 @@ env *global_env = NULL; void test_make_int() { value *v = make_int(42); - ASSERT(v->type == VALTYPE_INT, "make_int sets type"); + ASSERT(v->type == VT_INT, "make_int sets type"); ASSERT(v->as.i == 42, "make_int sets value"); } @@ -31,7 +31,7 @@ void test_cons_car_cdr() { value *b = make_int(2); value *p = cons(a, b); - ASSERT(p->type == VALTYPE_PAIR, "cons creates pair"); + ASSERT(p->type == VT_PAIR, "cons creates pair"); ASSERT(car(p)->as.i == 1, "car works"); ASSERT(cdr(p)->as.i == 2, "cdr works"); } -- cgit v1.2.3