I recently added the boolean operators and, or and not to lispBM. When evaluating (and a b) it is desirable that if a evaluates to false (nil in lispBM), b is not evaluated at all. Likewise for (or a b) we don't want b to be evaluated if a turns out being true (t in lispBM).
Function application in lispBM has the property that all of the arguments are evaluated beforehand and then the function is applied. So this new wish when it comes to these boolean operations does not fit that well into the patterns already established.
Since many other functions can take an arbitrary number of arguments, I thought it would be nice if also and and or works when given zero or more arguments. So that is another feature on the wish list.
Below is an example of applying and to zero or more arguments.
# (and)
t
# (and 't)
t
# (and 't 't)
t
# (and 't 't 'nil)
nil
And the property of not evaluating further arguments if not needed can be illustrated like this.
# (and 't 'nil (print "hello"))
nil
Notice that hello is not printed.
The first step in adding more built in fundamental operations to lispBM is to add new symbols that can be used to identify them.
The symbols for the boolean operators are given IDs within the range of special symbols. The Another Lisp for Microcontrollers test holds a bit more information on this range of symbol IDs. Below the changes to symrepr.h are listed.
#define SYM_AND 0x110FFFF
#define SYM_OR 0x111FFFF
#define SYM_NOT 0x112FFFF
static inline UINT symrepr_and(void) { return SYM_AND; }
static inline UINT symrepr_or(void) { return SYM_OR; }
And the following is added to the add_default_symbols function in symrepr.c to associate a textual name with each of the symbols.
res = res && symrepr_addspecial("and", SYM_AND);
res = res && symrepr_addspecial("or", SYM_OR);
res = res && symrepr_addspecial("not", SYM_NOT);
The not operator is implemented just as all other fundamental operations as a case in fundamental.c. It takes one argument and if that argument is nil it returns t otherwise it returns nil. Actually all of these boolean operations are implemented to treat nil as false and anything else as true. So (not 5) evaluates to nil and (and 2 3) evaluates to t.
The and and or operators will need some special attention to be able to get the short-circuiting behavior.
So to add short-circuiting boolean operators, what came to mind for me was to add new and and specific continuations for evaluating the arguments in a way suitable for short-circuiting. The new argument evaluating continuations come in two shapes, that either continues to evaluate arguments as long as they come out true (and) and one shape that evaluates while they come out false (or). So two new continuation IDs are added to the list for, AND and OR.
#define DONE 1
#define SET_GLOBAL_ENV 2
#define BIND_TO_KEY_REST 3
#define IF 4
#define PROGN_REST 5
#define APPLICATION 6
#define APPLICATION_ARGS 7
#define AND 8
#define OR 9
In the entry point function for evaluation, the run_evalfunction, the case that deals with function application is left unchanged. Currently this case looks as follows:
FATAL_ON_FAIL(done,
push_u32_4(&ctx->K,
ctx->curr_env,
enc_u(0),
cdr(ctx->curr_exp),
enc_u(APPLICATION_ARGS)));
ctx->curr_exp = head; // evaluate the function
continue;
It sets the curr_exp up to evaluate the function. For example, in the case of a lambda this means that the next thing to do for the evaluator is to turn the lambdainto a closure. But before that a continuation is pushed that describes what to do with the arguments, this is the APPLICATION_ARGS continuation.
I chose to leave this code unchanged and instead differentiate between short-circuitable operators and non, inside of the APPLICATION_ARGS function.
Inside of the apply_continuation function and the APPLICATION_ARGS case there, we check if the function (with is now evaluated or at least looked up), is one of the short-circuitable function and or or. If that is a case a new continuation is created to deal with the arguments, in the case of an and operator the AND continuation is pushed onto the stack and the first argument is set up to be evaluated next. Likewise in the or case, the OR continuation is pushed and the next thing to evaluate is the first element.
/* Deal with short-circuiting operators */
if (type_of(arg) == VAL_TYPE_SYMBOL &&
dec_sym(arg) == symrepr_and()) {
if (type_of(rest) == VAL_TYPE_SYMBOL &&
rest == NIL) {
*app_cont = true;
return enc_sym(symrepr_true());
} else {
FATAL_ON_FAIL(*done, push_u32_3(&ctx->K, env, cdr(rest), enc_u(AND)));
ctx->curr_exp = car(rest);
ctx->curr_env = env;
return NONSENSE;
}
}
if (type_of(arg) == VAL_TYPE_SYMBOL &&
dec_sym(arg) == symrepr_or()) {
if (type_of(rest) == VAL_TYPE_SYMBOL &&
rest == NIL) {
*app_cont = true;
return enc_sym(symrepr_nil());
} else {
FATAL_ON_FAIL(*done, push_u32_3(&ctx->K, env, cdr(rest), enc_u(OR)));
ctx->curr_exp = car(rest);
ctx->curr_env = env;
return NONSENSE;
}
}
The above code means that if we are processing the arguments to a short-circuitable operator we will jump over and continue along the AND or OR continuations instead.
In the case of AND, arguments should be evaluated as long as they result in something considered true.
case AND: {
VALUE env;
VALUE rest;
pop_u32_2(&ctx->K, &rest, &env);
if (type_of(arg) == VAL_TYPE_SYMBOL &&
dec_sym(arg) == symrepr_nil()) {
*app_cont = true;
return enc_sym(symrepr_nil());
}
if (type_of(rest) == VAL_TYPE_SYMBOL &&
rest == NIL) {
*app_cont = true;
return enc_sym(symrepr_true());
} else {
FATAL_ON_FAIL(*done, push_u32_3(&ctx->K, env, cdr(rest), enc_u(AND)));
ctx->curr_exp = car(rest);
ctx->curr_env = env;
return NONSENSE;
}
}
For the ORcase, we evaluate arguments as long as they result in false. The first argument to result in true terminates the continued evaluation of arguments and we can treat the result as true. If we run out of arguments without encountering true, the result is false.
case OR: {
VALUE env;
VALUE rest;
pop_u32_2(&ctx->K, &rest, &env);
if (type_of(arg) != VAL_TYPE_SYMBOL ||
dec_sym(arg) != symrepr_nil()) {
*app_cont = true;
return enc_sym(symrepr_true());
}
if (type_of(rest) == VAL_TYPE_SYMBOL &&
rest == NIL) {
*app_cont = true;
return enc_sym(symrepr_nil());
} else {
FATAL_ON_FAIL(*done, push_u32_3(&ctx->K, env, cdr(rest), enc_u(OR)));
ctx->curr_exp = car(rest);
ctx->curr_env = env;
return NONSENSE;
}
}
And that's it, the next section holds an example that would be awkward to write without access to or.
It is nice to finally be able to write some slightly more substantial lispBM programs such as sumtree below. I have noticed that as soon as wiring a slightly more involved program, new bug surface. Which is a lot of fun. One of the main reason for tormenting oneself with trying to implement this is that it is an never ending source problems to solve and that they are all right on the boundary of what I can handle when it comes to difficulty and complexity.
The sumtree function sums up the values located at the leaves of a tree. A leaf should hold some valid lispBM number type. The sum is computed by recursing on the car and `cdr, reaching a number terminates the recursion and returns the number upwards in the call hierarchy to added to the running sum.
Oh, I think that perhaps I should really call is-number, numberp or number-p. We'll see, it should be part of the default library (the prelude) later.
(define is-number
(lambda (x)
(or (= (type-of x) type-i28)
(= (type-of x) type-u28)
(= (type-of x) type-float)
(= (type-of x) type-i32)
(= (type-of x) type-u32))
))
(define sumtree
(lambda (x)
(if (is-number x)
x
(if (= x 'nil)
0
(let ((a (sumtree (car x)))
(b (sumtree (cdr x))))
(+ a b)
)))))
Please contact me with questions, suggestions or feedback at blog (dot) joel (dot) svensson (at) gmail (dot) com or join the google group .
© Copyright 2020 Bo Joel Svensson
This page was generated using Pandoc.