Blog 2020/1/13
<- previous | index | next ->
Let's learn how to write a Lisp interpreter in C!
Finally, the moment we've been waiting for! Lambda: user-defined, first-class, anonymous functions.
We create another struct to represent a lambda:
struct Lambda_ {
FormType type;
List* paramsp;
List* bodyp;
List* envp;
};
typedef struct Lambda_ Lambda;The lambda (lambda (a b) (+ a b)) consists of:
- the formal parameters:
aandb - the statements in the body:
(+ a b) - the environment in which the lambda was created
We add a lambda clause to eval_list():
return sf_cond(argsp, resultpp, envp);
} else if (strcmp(op_symp->valuep, "scope") == 0) {
return sf_scope(argsp, resultpp, envp);
+ } else if (strcmp(op_symp->valuep, "lambda") == 0) {
+ return sf_lambda(argsp, resultpp, envp);
}
}
sf_lambda captures the environment in which the lambda was created:
eval.c (some error handling elided):
/* The 'lambda' special-form.
Creates a user-defined anonymous function.
Returns 0 or error. */
static int sf_lambda(List* argsp, Form** resultpp, List* envp) {
if (list_len(argsp) < 2) {
return E_sf_lambda__bad_arg_count;
}
if (!is_list(argsp->datap)) {
return E_sf_lambda__arg2_not_list;
}
List* paramsp = (List*)(argsp->datap);
List* bodyp = argsp->nextp;
Lambda* lp;
new_lambda(&lp, paramsp, bodyp, envp);
*resultpp = (Form*)lp;
return 0;
}Most of the work happens in apply():
- push a new scope onto the environment and bind the formal parameters to the arguments
- evaluate each statement of the lambda body
- return the value of the last statement
eval.c (some error handling elided):
if (is_cfunc(opp)) {
CFunc* cfp = (CFunc*)opp;
return (cfp->f)(argsp, resultpp, envp);
+ } else if (is_lambda(opp)) {
+ Lambda *lp = (Lambda*)opp;
+ /* create the local environment and bind the args to the params. */
+ List* lenvp = lp->envp;
+ env_push_scope(&lenvp);
+ List* paramsp = lp->paramsp;
+ while (!is_list_empty(paramsp)) {
+ Symbol* keyp = (Symbol*)(paramsp->datap);
+ if (is_list_empty(argsp)) {
+ return E_apply__bad_arg_count_1;
+ }
+ Form* valuep = argsp->datap;
+ env_bind(lenvp, keyp, valuep);
+ paramsp = paramsp->nextp;
+ argsp = argsp->nextp;
+ continue;
+ }
+ if (!is_list_empty(argsp)) {
+ return E_apply__bad_arg_count_2;
+ }
+
+ /* evaluate each line of the body. */
+ List* bodyp = lp->bodyp;
+ Form* resultp;
+ while (!is_list_empty(bodyp)) {
+ Form* statementp = bodyp->datap;
+ int err = eval_form(statementp, &resultp, lenvp);
+ if (err && err != E_did_not_produce_a_value) {
+ return err;
+ }
+ bodyp = bodyp->nextp;
+ continue;
+ }
+ if (resultp == NULL) {
+ return E_did_not_produce_a_value;
+ } else {
+ *resultpp = resultp;
+ return 0;
+ }
} else {
return E_apply__bad_op_type;
}We update print_form() to handle Lambdas:
} else if (is_cfunc(formp)) {
CFunc* cfp = (CFunc*)formp;
return print_cfunc(cfp, fp);
+ } else if (is_lambda(formp)) {
+ Lambda* lp = (Lambda*)formp;
+ return print_lambda(lp, fp);
} else {
assert(false);
}print_lambda() prints out the formal parameters, e.g. (lambda (a b) (+ a b)) prints as <Lambda(a,b)>:
printer.c (error handling elided):
/* Prints the Lambda in lp into fp.
Returns 0 or errno. */
static int print_lambda(Lambda* lp, FILE* fp) {
fputs("<Lambda(", fp);
List* paramsp = lp->paramsp;
while (!is_list_empty(paramsp)) {
Symbol* symp = (Symbol*)(paramsp->datap);
fprintf(fp, "%s", symp->valuep);
bool is_last = is_list_empty(paramsp->nextp);
if (!is_last) {
fputs(",", fp);
}
paramsp = paramsp->nextp;
}
fputs(")>", fp);
return 0;
}We can create a lambda:
$ ./lisp
> (lambda (x) (+ x x))
<Lambda(x)>
We can call a lambda:
> ((lambda (x) (+ x x)) 2)
4
We can bind a lambda:
> (bind double (lambda (x) (+ x x)))
> (double 4)
8
We can write a lambda which takes a lambda and returns a lambda:
> (bind twice (lambda (f) (lambda (x) (f (f x)))))
> ((twice double) 4)
16
We can even pass that lambda into itself! 🤯🤯🤯
> (((twice twice) double) 4)
64
If we expose form_eq() as a built-in, we could implement fibonacci!
Add a bi_eq() built-in:
/* Built-in equality, i.e. `(== 1 1 1)`.
Calculates the equality of the given forms.
Returns 0 or error. */
int bi_eq(List* argsp, Form** resultpp, List* envp) {
if (list_len(argsp) < 2) {
return E_bi_eq__bad_arg_count;
}
bool accum = true;
Form* a = argsp->datap;
argsp = argsp->nextp;
while (!is_list_empty(argsp)) {
Form* b = argsp->datap;
accum = accum && form_eq(a, b);
if (accum == false) {
break;
} else {
argsp = argsp->nextp;
continue;
}
}
if (accum == true) {
*resultpp = (Form*)g_true;
} else {
*resultpp = (Form*)g_false;
}
return 0;
}and bind it to == during new_default_env():
assert(env_bind_cbool(envp, "false", g_false) == 0);
assert(env_bind_cbool(envp, "else", g_true) == 0);
assert(env_bind_cfunc(envp, "+", bi_add) == 0);
+ assert(env_bind_cfunc(envp, "==", bi_eq) == 0);
return envp;
}
Now with lambda, cond, + and ==, we can write a fibonacci implementation:
$ ./lisp
> (bind fib
(lambda (n)
(cond
(== n 1) 1
(== n 2) 1
else (+ (fib (+ n -1)) (fib (+ n -2))))))
> (fib 10)
55
>
😎😎😎
This is all I have for the moment, but in future parts I'd like to look at:
- revisit
bind(currently no distinction betweendefineandset!) - implement a meta-circular evaluator
- macros
- ditching the a-list in favor of a hash table\
- symbol interning
- tail-call optimization
- implementing a garbage collector
- implementing vector and hast table literals
- implementing persistent data structures