super secret hq

LISP in Go


I’m keen on learning Go. I’ve kicked around the sample programs and understand the syntax. I can write code that compiles but I’m not yet to the point where I feel comfortable programming it. You could say that I know that grammar but not the idioms.

I’m going to change that by writing a good sized program in Go. I love LISP, so that’s a natural choice for me. Luckily for me, Leo Howell wrote a very nice series of articles on building a LISP interpreter in C. I’ve gone through that and think that I understand it well enough to rework it in Go. There’s enough to it that I should learn how to express myself in Go.

I’m keen on learning Go, so I am building Leo’s interpreter with it. It’s a good opportunity since there’s a lot more to it than the typical “Hello, Universe” examples. Luckily, I understand the interpreter well enough that the challenge will be expressing myself in Go. (Well, I think that I understand it; this will prove it.)

As a bonus, I watched Rob Pike’s lecture on lexing with goroutines, and that looks like a lot of fun to try.

I plan to follow Leo’s outline, so feel free to compare against the original.

The Forth Interpreter Loop


In the Forth Programmer’s Handbook, Conklin and Rather outline the basics of the Forth interpreter:

while true
  get next lexeme
  lookup lexeme in dictionary
  if word is found
      execute word
      if there is stack underflow
          display "stack empty"
          reset stacks and intepreter
  elsif lexeme is numeric
      convert to binary
      push result onto stack
      display "unknown word"
      reset stacks and intepreter

Branching In False Forth


Most programming languages support conditional logic by using a some form of “if condition then codeBlock1 else codeBlock2 end-if.” The “else codeBlock2” is usually optional.

The “condition” evaluates to either true or false. If the condition evaluates to true, the code in the first block is executed. Otherwise, the code in the second block is executed (assuming that it is present).

Most programming languages support conditional logic by using a some form of “if condition then codeBlock1 else codeBlock2 end-if.” The “else codeBlock2” is usually optional.

REPL in Forth


Many interpreters implement a read, evaluate/execute, print loop (also known as “REPL”) when interacting with the user. The REPL fetches code to evaluate, passes it to the interpreter to evaluate and execute, then prints the output to the console.

A Toy Forth Interpreter


I think that it’s a good idea to start small and build using test cases. It’s tough to do that in a blog, though, because there’s a lot of overhead to carry around. So, I’ll start small and desk check frequently.

A Non-Typed Message Passing Structure


As I was drifting off to sleep last night, this popped into my head. I didn’t feel like getting up to write it down. It was a pleasant surprise that I remembered it when I woke up.

It’s a set of structures for setting up a message passing language that supports single inheritance. Kind of like Smalltalk or Objective-C.

Single Line Comments


Before starting the parser, let’s modify the lexer to accept comments.

For our purposes, a comment is two semi-colons followed by all the text up to (but not including) the new-line character.

A Better Forth Scanner


This scanner is more robust. It detects errors with unterminated quoted text. It also recognizes escapes inside the quoted text. It doesn’t do anything with the escapes because it’s just a scanner.

If you compare the code to the prior version, you should notice that I changed the name from “scanner” to “lexer.” I made the change to more accurately reflect what the code should be doing.

I also added in a “line” variable to track the current line in the input buffer. That’s useful to know when displaying error messages.

A False Forth Scanner


Two languages that I keep returning to, like a moth to the flame, are LISP and Forth. I have the SwiftForth compiler on my system, along with Clozure CL. I like both, but neither of them are embeddable in a C program, so the next set of posts will be on writing a very simple Forth interpreter that I’ll call “False Forth” because it is not a “true” Forth.

The grammar for False Forth is very simple:



I’m now using Octopress to generate this web site, with rsync to deploy, and Disqus to handle comments. My first impression is that I’m impressed with how easily this went.

I’m running OS X and refuse to use MacPorts, so things are usually not very simple. This was incredibly easy. The documents were up to date and worked without fail. I encountered many problems with Jekyll and Nanoc due to package versions. The Octopress install uses the “bundle” command, which is dealing with all those ruby issues.

Parsing McCarthy's S-Expressions


This article builds a top-down recursive parser for simple s-expressions. S-expressions are used to represent data and code in LISP. We’re not going to build a full-blown LISP interpreter here, just a parser for s-expressions.

I’m basing this grammar on the LISP 1.5 Programmer’s Manual written by McCarthy, Abrahams, Edwards, Hart & Levin. It accepts both s-expressions and list notation. A s-expression is the basic form in LISP. It consists of atoms and dotted pairs. Here are some examples:

A Recursive Descent Parser, Part 1


An easy type of parser to build is the recursive descent parser. It gets its name from the fact that it starts at the top of the grammar and calls functions to accept parts of the grammar. It’s easy to write because there are simple rules for turning every production in the grammar into a function. Writing one can be tedious, though, especially if there are a lot of productions.

The type of parser that we’re going to write works for LL(1) grammars only, which means that we only need to look one symbol ahead in order to know which production to follow. It also means that no two productions start with the same symbol.

The parser is built from the top-down. That means that it starts with the first rule in the grammar and uses the next available symbol to determine which production rule to parse. It then calls a function to parse that production rule.

A Change Of Plans


I’d planned on using a desktop calculator as the interpreter for the tutorials, but I’m finding it too boring. It’s usually a good idea to stick with something simple and build from it, but I’m building an interpreter for another project that I’m working on. I think that showing the process, warts and all, has value, too. When I’m done, maybe I’ll do a “best of” article that deletes the dead ends and rotten wood from the project.

Our First Grammar


The first language that we’re going to write an interpreter for is “salc,” a simple calculator. We will eventually turn salc into a full-fledged calculator, but for now we’re focusing on simplicity.

This version of salc will add single-digit numbers. Like most calculators, salc will accumulate results, so something like “1 + 2 + 3” will total to 6. Unlike normal calculators, salc will only print the result when asked. Whenever salc sees the equals sign, it will print out the current total.

From this description, the inputs

A Formal Language For Grammars


In the previous article, we described salc, a simple calculator. The description was presented very informally. In this article, we’re going to look at how describe the language formally. By formally, we mean that we’ll give a set of rules to identify valid programs. Those rules define the grammar for the language.