Blog 2020/1/12
<- previous | index | next ->
Let's learn how to write a Lisp interpreter in C!
In this part, we implement funcion application.
Lisp stands for "list processing", which means that every list is treated like a function call.
The first element of the list is assumed to be the operator, and the rest of the elements are the operands.
The operator is applied to the operands, and thus (+ 1 1) evaluates to 2.
When a list is evaluated, the first element must be one of three things:
- a special-form,
- (something which evaluates to) a user-defined function (also called a lambda),
- (something which evaluates to) a built-in function (also called a primitive function).
Our first built-in function is bi_add() (bi being a bit of Hungarian notation),
which we will bind to the symbol +:
builtins.c (error handling elided):
/* Built-in addition, i.e. `(+ 1 2 3)`.
Calculates the sum of argsp into resultp.
Promotes CLong to CDouble where needed.
Returns 0 or error. */
int bi_add(List* argsp, Form** resultpp, List* envp) {
long accuml = 0;
double accumd = 0.0;
bool long_mode = true;
bool double_mode = false;
bool mode = long_mode;
while (!is_list_empty(argsp)) {
Form* argp = argsp->datap;
if (is_clong(argp)) {
long l = ((CLong*)argp)->value;
if (mode == long_mode) {
accuml += l;
} else {
accumd += (double)l;
}
} else if (is_cdouble(argp)) {
double d = ((CDouble*)argp)->value;
if (mode == double_mode) {
accumd += d;
} else {
/* switch to double-mode. */
mode = double_mode;
accumd = (double)accuml + d;
}
} else {
return E_bi_add__unsupported_arg_type;
}
argsp = argsp->nextp;
continue;
}
if (mode == long_mode) {
CLong* clp;
new_clong(&clp, accuml);
*resultpp = (Form*)clp;
return 0;
} else {
CDouble* cdp;
new_cdouble(&cdp, accumd);
*resultpp = (Form*)cdp;
return 0;
}
}Note that bi_add() promotes integers to doubles when it is given mixed-type arguments. Thus (+ 1 3.14159) evaluates to 4.14159.
In order to bind a built-in function in the environment, we need to be able to represent it as a Lisp form.
For this, we add another struct:
struct CFunc_ {
FormType type;
int (*f)(List*, Form**, List*);
};
typedef struct CFunc_ CFunc;In the above, f is a pointer to a function
which takes a List*, a Form**, and another List*,
and returns an int.
I use cdecl.org to deal with function pointers in C.
Notice that this matches the function signature of bi_add().
That's no coincidence: all of our built-in functions will need to share a common signature.
We update form_eq() to handle CFunc.
All we have to do is compare the two C-function pointers:
return a == b;
} else if (is_nil(a)) {
return true;
+ } else if (is_cfunc(a)) {
+ CFunc* af = (CFunc*)a;
+ CFunc* bf = (CFunc*)b;
+ return af->f == bf->f;
} else {
assert(false);
}We update eval_list() to perform function application:
it evaluates the operator, evaluates the operands, then calls apply().
eval.c (error handling elided):
}
/* this is a regular function call. */
- /* for now, we just return the list. */
- *resultpp = (Form*)lp;
- return 0;
+ Form* op_evaledp;
+ List* args_evaledp;
+ eval_form(op_formp, &op_evaledp, envp);
+ eval_forms(argsp, &args_evaledp, envp);
+ return apply(op_evaledp, args_evaledp, resultpp, envp);
}
Our initial implementation of apply() is very simple: it calls the C function with the supplied arguments:
/* Function application: apply the operator to the arguments.
Returns 0 or error. */
static int apply(Form* opp, List* argsp, Form** resultpp, List* envp) {
if (is_cfunc(opp)) {
CFunc* cfp = (CFunc*)opp;
return (cfp->f)(argsp, resultpp, envp);
} else {
return E_apply__bad_op_type;
}
}And eval_forms() is simply a convenience loop around eval_form():
eval.c (error handling elided):
/* Evaluate a list of forms.
Returns 0 or error. */
static int eval_forms(List* formsp, List** resultspp, List* envp) {
List* resultsp = g_emptylist;
while (!is_list_empty(formsp)) {
Form* resultp;
eval_form(formsp->datap, &resultp, envp);
list_push(&resultsp, resultp);
formsp = formsp->nextp;
continue;
}
*resultspp = resultsp;
return 0;
}We update new_default_env() to bind + to our bi_add() built-in:
assert(env_bind_nil(envp, "nil") == 0);
assert(env_bind_cbool(envp, "true", g_true) == 0);
assert(env_bind_cbool(envp, "false", g_false) == 0);
+ assert(env_bind_cfunc(envp, "+", bi_add) == 0);
return envp;
}
forms.c (error handling elided):
/* Convenience function to push a built-in C function into the env.
Returns 0 or error. */
int env_bind_cfunc(List* envp, char* key, int (*f)(List*, Form**, List*)) {
Symbol* keyp;
new_symbol(&keyp, key);
CFunc* valuep;
new_cfunc(&valuep, f);
return env_bind(envp, keyp, (Form*)valuep);
}We update print_form() to handle CFunc:
return print_cbool(cbp, fp);
} else if (is_nil(formp)) {
return print_nil(fp);
+ } else if (is_cfunc(formp)) {
+ CFunc* cfp = (CFunc*)formp;
+ return print_cfunc(cfp, fp);
} else {
assert(false);
}printer.c (error handling elided):
/* Prints the CFunc in cfp into fp.
Returns 0 or errno. */
static int print_cfunc(CFunc* cfp, FILE* fp) {
fprintf(fp, "<C function @%p>", cfp->f);
return 0;
}Finally, we can call functions!
$ ./lisp
> (+ 1 1)
2
>
Glorious!
$ ./lisp
> (bind a 2)
> (bind b 3)
> (+ a b)
5
>
We also have a printable representation for CFunc values:
$ ./lisp
> +
<C function @0x1038c4060>
>
In part 12, we'll implement the quote special form.