Part 2: Notes, reflections, and story-telling regarding chapters 9 and 10 of Build Your Own Lisp). Previous post here.

I got back to rolling around in parenthesis in the last few days. It’s been a little while. Let’s tackle this one, first person, present-tense.


I crack the digital spine of Build Your Own Lisp. It’s been two or three weeks since I crushed the first 8 chapters, humming the champion’s sonata of understanding to myself. I head over to chapter 9, so very, very confident:

The final result of this chapter will only differ slightly in behaviour from the previous chapter. This is because we are going to spend time changing how things work internally. This is called re-factoring and it will make our life a lot easier later on. Like preparation for a meal, just because we’re not putting food onto plates it doesn’t mean we’re wasting time. Sometimes the anticipation is even better than eating!

Oh, refactoring! I love doing that. I love talking about doing that. Since I’m a Clean Coder™ and Raucous Refactorer™ this will be great fun! My eyes skim down to the next H1 anchor on the aged yellow page of the site:

Pointers

I gulp. A single bead of sweat forms at the base of my neck. I think about all the smart people on Hacker News watching me closely, perhaps muttering incantations or curses on an approaching javascripter webspirit about to party with memory management. From the bottom of a post a severely downvoted comment post bubbles up about irrelevance, failure, and how I’ll probably destroy my own computer. I wipe away my sweat, casting away the demons of negativity on the internet.

I consult the motivational poster above my desk, it’s a photo of a cat hanging from an ethernet cable. The 12 point font reads:

Hang in there. New things can be challenging. Stay positive. No self-fulfilling prophecies. Things don’t have to click right away. If you don’t get the big things, you’ll get the small things. If you don’t get anything, go for a walk. Think about getting some plants, they clean the air. Onwards!.

I lower my head back to my screen, invigorated and enthused.

A Small but Handy Revelation

To store the program we will need to create an internal list structure that is built up recursively of numbers, symbols, and other lists. In Lisp, this structure is commonly called an S-Expression standing for Symbolic Expression. We will extend our lval structure to be able to represent it. The evaluation behaviour of S-Expressions is the behaviour typical of Lisps, that we are used to so far. To evaluate an S-Expression we look at the first item in the list, and take this to be the operator. We then look at all the other items in the list, and take these as operands to get the result.

Storing a program? Storing a program. Huh. OH. STORING A PROGRAM.

The sound of blocks falling into place ring out in my empty warehouse. Oh right. I’ve written a basic REPL in the chapters thus far, but I’m only really starting to now see my Lisp code as going through a reader and then an evaluator. Until now, I hadn’t really thought of a program as living in memory before it was executed. I shift my eyes left to right to see if anybody notices. I smile a little at myself, perhaps at an imaginary meetup surrounded by schemers happily racketing about incredible macros and entire languages they’ve built, leaning so hard on a parenthesis that it looks like it might snap. Damn.

In the meantime, I’m just starting to see my lisp for what it is: a little garage that I feed a bunch of lego blocks to, which then get recursively organized into a nice little car. But things are still vague. I hear some whirring sounds as things get assembled into a special box that I don’t have a name for yet, but I do know it’s an Awesome Sick Time in there. The garage door opens and a nice little Evaluated car comes out. Cool.

First we are going to read in the program and construct an lval* that represents it all. Then we are going to evaluate this lval* to get the result of our program. This first stage should convert the abstract syntax tree into an S-Expression, and the second stage should evaluate this S-Expression using our normal Lisp rules.

But, somewhere inside that garage, I avoid a beast I fear will take me down a rabbit hole. A double pointer. I silently mouth a bad word.

typedef struct lval {
  int type;
  long num;
  /* Error and Symbol types have some string data */
  char* err;
  char* sym;
  /* Count and Pointer to a list of "lval*"; */
  int count;
  struct lval** cell;
} lval;

I return to the text, avoiding the unknown: a possible garage with lists of other garages within it. Maybe I’ll return to that later.

S-Expressions are variable length lists of other values. As we learnt at the beginning of this chapter we can’t create variable length structs, so we are going to need to use a pointer. We are going to create a pointer field cell which points to a location where we store a list of lval*. More specifically pointers to the other individual lval. Our field should therefore be a double pointer type lval**. A pointer to lval pointers. We will also need to keep track of how many lval* are in this list, so we add an extra field count to record this.

Oh yeah totally cool. I skim past the hard scary parts, and start thinking about whether I’ve (mis)used double, nay triple, nay QUADRUPLE pointers in my own life, explaining my bad memory as of late.

I switch gears, leaning back in the comfort of some great analogies describing the Stack and the Heap respectively:

The Stack is the memory where your program lives. It is where all of your temporary variables and data structures exist as you manipulate and edit them. Every time you call a function a new area of the stack is put aside for it to use. Into this area are put local variables, copies of any arguments passed to the function, as well as some bookkeeping data such as who the caller was, and what to do when finished. When the function is done the area it used is unallocated, ready for use again by someone else.

I like to think of the stack as a building site. Each time we need to do something new we corner off a section of space, enough for our tools and materials, and set to work. We can still go to other parts of the site, or go off-site, if we need certain things, but all our work is done in this section. Once we are done with some task, we take what we’ve constructed to a new place and clean up that section of the space we’ve been using to make it

I Imagine the Heap like a huge U-Store-It. We can call up the reception with malloc and request a number of boxes. With these boxes we can do what we want, and we know they will persist no matter how messy the building site gets. We can take things to and from the U-Store-It and the building site. It is useful to store materials and large objects which we only need to retrieve once in a while. The only problem is we need to remember to call the receptionist again with free when we are done. Otherwise soon we’ll have requested all the boxes, have no space, and run up a huge bill.

A C Macro

I move on, starting to build builtin functions for my little lisp. And what’s this? I get to write error handling with a C Macro ?! I gently course correct and back burner my curiousity on how C macros work.

#define LASSERT(args, cond, err) \
  if(!(cond)) {lval_del(args); return lval_err(err);}

// declare eval
lval* lval_eval (lval* v);

lval* builtin_head(lval* a) {
  /* // Error checking ... */
  LASSERT(a, a->count ==1, "Function 'head' passed too many args!")
  LASSERT(a, a->cell[0]->type == LVAL_QEXPR, "Function 'head' passed incorrect type.")
  LASSERT(a, a->cell[0]->count != 0, "Function 'head' passed {}!")

  lval* v = lval_take(a, 0);

  while(v->count > 1) {lval_del(lval_pop(v, 1));}
  return v;
}

So I’m creating my lisp’s built in head (or car to some). This involves doing some error checking before running our internal functions—in this case lval_pop, which I eye warily due to its use of the & symbol.

I write more builtin_* functions, and feel the furrows of my brow release, finally ceasing to pester my wild, untamed eyebrows. I find comfort in repetition: making “built_in” functions that remind me of simpler times: list, head, tail, join … when we read in the program, I guess we are just linking up the built in functions with the correspond keywords, feeding the lisp val as the argument:

// Builtin case'r
lval* builtin(lval* a, char* func) {
  if (strcmp("list", func) == 0) {return builtin_list(a);}
  if (strcmp("head", func) == 0) {return builtin_head(a);}
  if (strcmp("tail", func) == 0) {return builtin_tail(a);}
  if (strcmp("join", func) == 0) {return builtin_join(a);}
  if (strcmp("eval", func) == 0) {return builtin_eval(a);}
  if (strstr("+-/*", func)) {return builtin_op(a, func);}
  lval_del(a);
  return lval_err("Unknown Function!");
}

Q Expressions

Ah, next I’ll add some Q-expressions:

In this chapter we’ll implement a new type of Lisp Value called a Q-Expression.

This stands for quoted expression, and is a type of Lisp Expression that is not evaluated by the standard Lisp mechanics. When encountered by the evaluation function Q-expressions are left exactly as they are. This makes them ideal for a number of purposes. We can use them to store and manipulate other Lisp values such as numbers, symbols, or other S-Expressions themselves.

My eyes narrow and I shake it to the beats I’m listening to, the unending cacophony of parens clashing against each other with no winner in sight.

I release my shoulders. Not too scary. The cat poster above is maybe giving me the thumbs up, but I daren’t look and spoil the magic.

BYOL lines up an excellent 4 step-process for adding features to a language:

Acronym wise, SRPS doesn’t hold up as well as REPL, but somehow I can’t help but feel that the two could be, if not related, at least good friends.

After following through chapter 10, I cast make on my code, and after fixing some forgotten syntax additions and inclusions of the new Q_EXPR var, things compile and work:

~/Development/byol [master] λ ./parsing
Teesy Lisp Version 0.0.0.0.5
All dreams emanate from the Paren Chamber.
((((((((((((((((((hi))))))))))))))))))
Press Ctrl+c to Exit

lispy> eval {+ 1 3 5 7 9}
eval {+ 1 3 5 7 9}
25
lispy> 

Closing

I sit back, smiling at the collection of little treasures I’ve accumulated. It’s not all there, but I’m slowly building my garage.

One last quote, lovely, regarding refactoring and pulling things together even when they don’t make sense:

Some of you who have gotten this far in the book may feel uncomfortable with how it is progressing. You may feel you’ve managed to follow instructions well enough, but don’t have a clear understanding of all of the underlying mechanisms going on behind the scenes.

If this is the case I want to reassure you that you are doing well. If you don’t understand the internals it’s because I may not have explained everything in sufficient depth. This is okay.

To be able to progress and get code to work under these conditions is a great skill in programming, and if you’ve made it this far it shows you have it.

In programming we call this plumbing. Roughly speaking this is following instructions to try to tie together a bunch of libraries or components, without fully understanding how they work internally.

It requires faith and intuition. Faith is required to believe that if the stars align, and every incantation is correctly performed for this magical machine, the right thing will really happen. And intuition is required to work out what has gone wrong, and how to fix things when they don’t go as planned.

Unfortunately these can’t be taught directly, so if you’ve made it this far then you’ve made it over a difficult hump, and in the following chapters I promise we’ll finish up with the plumbing, and actually start programming that feels fresh and wholesome.

Keep those (parens))))) tuned here for another post.