sugar /blog/2020-12-06-sugar-compiler.html
)I've taken some of my future directions topics from the previous post and expanded on them. I'll be describing those in this post.
Since this compiler doesn't keep track of types, there are (will be) variants of many functions for specific types. I intend to use i32 and unsigned as the default for the functions without suffix and provide suffixed versions for all the types.Note: The new compiler (common lisp) source code is in /src/sugar.pt2
Lisp, and many languages, have so-called shortcutting and/or operators. These operators only evaluate the minimum set of their arguments required to decide on the true/false result.
This feature can be very useful for guarding function calls.
In this example if some-val is nil then
and will get false for the first argument. Since and is false if any argument is false and will now shortcut
and return false. It will not evaluate
(never-do-this-with-nil some-val), and that's good since never-do-this-with-nil would probably crash if called with nil.
(and some-val (never-do-this-with-nil some-val))
One can imagine a language treating and as a purely, mathematical, boolean, function. That language would first evaluate all arguments,
just like it does with any function, and then call the function to get true/false.
So how do these shortcut and/or operators actually work, if they are not functions? They compile to nested if-expressions, not a function call at all.
Here is an example of how and is compiled:
(and a b c) => (if a (if b c false) false)
We see that this and evaluates to false or 'c' (here we are using the concept that 0 is false and everything else is true, like C and Lisp*.
It's called a generalized boolean in Lisp).
So the total and expression will either return false or the value of 'c' (which may be false) and will stop evaluating arguments
after the first one returning false.
You may also notice the recursive nature of the transformation:
(and a _) => (if a _ false) (and x) => x
We can implement and as a lisp macro, that is, a function transforming a piece of sugar syntax/code "(and a b c)" into another
piece of sugar syntax/code "(if a ....)". (more on macros in an upcoming post). We can also make use of the recursive nature of the
transformation to implement the macro function.
Yes, sugar has macros, but so far they are only accessible to the compiler itself, internally, not user code.
Can we perform the same trick with or? Yes, almost; there is a complication.
To get the full Lisp-effect of and/or I would like to return the value of the final expression evaluated, not just 0 or 1 (true or false), and this causes a problem (but the trouble is, I think, worth it).
(or a b c) => (if a a (if b b c))
Maybe you can see the problem? I need to check the value of 'a', but then I need to return 'a' if it's not false (non-zero). In the case of
a real use of or 'a' might be something complex e.g. a function call which sends $200 to your bank account. If that call returns
true, I will then call it again when returning it from the if, thus sending you a further $200, which I had not intended.
My code looks like this
(yes, send-200-dollars must return false if it succeeds; awkward example)
(or (overdrawn?) (send-200-dollars) (print-failure))
But transformed to this, where you potentially get 2 calls to either of the first 2 functions.
(if (overdrawn?) (overdrawn?) (if (send-200-dollars) (send-200-dollars) (print-failure)))
Formally, this is a problem with any functions which have side-effects. The functions used in and/or must return a (generalized) boolean, but they are also allowed to have interesting side-effects.
This ability to have side-effects in and/or is a powerful Lisp feature and can be used to write some, nice, concise code. So we want to have it in sugar.
The solution is to evaluate each argument at most once and capture the result in a variable. In a Lisp macro we would do this with
let which allows introducing new scopes and variables anywhere, but wat/wasm (and hence sugar) only allow locals to be defined
at the start of a function.
We'd have to ask the user to remember to define and-or-helper-var in every function using and/or. That would be awkward.
The compromise solution I've made is to have a single hidden global variable which is used by the macro expanding or.
This should be safe, even for nested and/or constructs since the capture is only required after the true condition and no other code
can be evaluated before its use
(fingers crossed I haven't missed something).
Now we have this recursive definition for or.
(progn is just Lisp's way of sequencing expressions/statements. Like a {} block in C.)
(or a _) => (progn (set T a) (if T T _)) (or x) => x
Here we can see an example of the use of returning values in and/or rather than just 0/1.
(set r (or (this-maybe-good?) (what-about-this?) (last-chance-value)))
Each of these functions returns a different value and 'r' will end up containing the actual value decided upon.
There is a further complication.wat/wasm requires a special (result type) clause on if when we want to return a value from the branches, but this section is way too long already. See vprogn/vif below.I've added 2 new loop forms. Mostly just to test my internal macro system.
(while condition body...) (forever body...) ; example with break (forever ... (if some-case (break)) ...)
The forever loop requires break. So I've implemented break, break-if & continue. Normally wat/wasm requires
explicit labels for such things, but I generate labels in the compiler and keep them on a stack, so break, break-if & continue
can take the inner-most label from the stack (optionally you can specify explicit labels, to allow breaking out of multiple
loop levels). break-if could be written as
(if condition (break)) but wat/wasm has a special br_if instruction and break-if compiles to that as an optimization.
break, break-if & continue can be used in while & for too, tho continue won't update the counter in for
yet.
Thought for future: Maybe I should make counterparts to progn/if (vprogn/vif) which return values and drop the current optional result clause approach? Chose (if) when returning nothing from the branches and (vif) (or vif.f64 etc.) when using value-if.
Array access currently requires adding an index to a base pointer and then using (set*) or (get*) [or a typed variant thereof] and also remembering to multiply the index by 2,4 or 8 depending on the size of the array element i32/i64/f32/f64.
It would be nice to have Lisp's aref to do this for us.
Again I have to compromise here. Since sugar doesn't track types, I cannot know the element size in the compiler. The user must give it explicitly. As usual, I default to assuming i32 elements i.e. multiplier = 4.
This gives the following syntax:
(aref ptr idx multiplier) (aset ptr idx value mutiplier) or (aref ptr idx) (aset ptr idx value)
Example
(print (aref num-table i)) (aset num-table i new-value) (print (aref sin-lut i 8)) (aset sin-lut i (sin.f64 0.1231) 8)
This multiplier requirement is not ideal, but I still think I can write interesting code with sugar despite this lack.
Later I plan to implement the setf macro which allows dropping the aset operator, by inferring it from the inner aref.
(aset ptr idx val) => (setf (aref ptr idx) val)
While we can define immutable globals in wat/wasm, they do, in fact, take up space in the final .wasm file. It would be useful to be able to define compile-time constants which are symbolically replaced during compilation and don't actually appear as memory objects in the final output .wasm code.
Lisp uses (defconstant) for this concept and I will too.
(defconstant var type val) ; example (defconstant pi f64 3.14159) ;; useful in case the value of pi should ever change
I wanted to have constant-folding in the value argument but that's quite a big request for a compiler as simple as sugar.
I thought to cheat and use common-lisp's eval but that only allows the simplest sugar syntax like plus and multiply
and, importantly, it will not see any of the other defconstant's defined in the code. So, for now, defconstant
requires literal, numeric, values.
Lots of basic math operators were missing from the original sugar compiler code. I've added quite a few, but even more are still missing.