Penetrating my cerebrum with Lisp
May 21st, 2009 1:40:20 pm pst by 
Sterling Camden
I’ve been casually studying Lisp for years now, and gathering a much better understanding of programming languages in the process. I finished reading Paul Graham’s On Lisp earlier this year. But the only way to truly grok a language is to use it to write something fairly complex. Lisp is often stereotyped as being designed for highly abstract academic problems – and what could be more abstract and academic than writing an interpreter for Brainfuck?
While it may sound über-geekish to be able to say that my first real program in Lisp was an interpreter, I cheat a little bit here because Brainfuck is such a simple language to interpret (for a computer, anyway). I also didn’t build in Brainfuck as an extension of Lisp the way most DSLs are written in Lisp – primarily because the comma and period characters are reserved for the Lisp compiler, and overloading the functions + and – wouldn’t be such a good idea, either.
So, you can feed my interpreter its code as a series of strings or as a list of symbols. The string form is probably preferable, because the symbols have to be prefixed with ‘bf’ to avoid the collisions I mentioned above.
In the downloadable code below, brainfuck.lisp contains all of the functions for the Brainfuck interpreter, and bf.lisp is a command-line interface for it. I developed it using CLISP, but it should be compatible with most Common Lisp implementations. Usage:
clisp bf.lisp <bf-file>*
where <bf-file> is a file containing Brainfuck code. If you supply more than one file, they are executed within the same machine as if they were one continuous file.
This brought me face-to-face with the problem of retrieving command-line arguments in Common Lisp, which isn’t standard across implementations. I found a work-around for that in the Common Lisp Cookbook, but it didn’t handle CLISP. After a little research, I was able to modify it to include support for CLISP:
(defun get-command-args ()
(or
#+SBCL *posix-argv*
#+LISPWORKS system:*line-arguments-list*
#+CMU extensions:*command-line-words*
#+clisp EXT:*ARGS*
nil))If you want to call the Brainfuck machine from within Lisp, here are a few important functions:
(make-bf-machine) => bf-machine
(bf-add-string bf-machine code) => code-stream
(bf-add-list bf-machine code) => code-stream
(bf-step bf-machine) => current-cell-value
(bf-run bf-machine) => final-cell-value
(bf-current-instruction bf-machine) => current-instruction
The last one is important if you intend to step through a program, because it yields nil when there are no more instructions.
Since bf-add-list doesn’t validate the symbols it receives, it provides an opportunity for Lisp code injection. You can pass it any symbol that represents a function that takes a bf-machine as its only argument. For example, 'print might be handy for debugging. The bf-add-string function doesn’t have the same facility/vulnerability, because it filters out non-Brainfuck characters.
Notes on the Brainfuck implementation
First, let me address each of the points in Daniel Cristofani’s Epistle to the Implementors:
- Greetings back atcha, Daniel.
- Duly perused.
- This implementation treats EOL as a 10. That was a freebie from using CLISP.
- EOF on input leaves the current cell unchanged.
- Non-Brainfuck characters are dutifully ignored.
- I have not added any extensions to the language – nor have I implemented the “traditionally sanctioned” # and ! extensions.
- This implementation provides a logically infinite array of cells – in both directions. Thus, if you shift left from cell 0, you will receive a new cell 0 containing a zero, and all other cells are shifted to the right. The maximum value that can be stored in any cell is dependent on the capacity of numbers in the version of Common Lisp – which appears to be 64-bit floating point.
- It’s fascinating!
My implementation passes all of the tests that Daniel suggests, with the exception of being more lenient on:
- The two bounds-checking tests, which run forever (or presumably until memory is exhausted, but I didn’t have the patience for that).
- The two unmatched bracket tests. When my implementation reaches the end of the code stream while hunting for a matching bracket, it just ends.
I also tested most of the programs that Daniel supplies. I particularly like his Fibonacci generator, which is incredibly concise for a version that outputs successive values in ASCII.
Finally, since there’s no finer way to screw up your noggin than with alcohol, try the programs at 99 Bottles of Beer.
Posted in Brainfuck, Lisp, Wildly popular | 
11 Comments » RSS 2.0 | Sphere it!
Subscribe by Email
[...] Penetrating my cerebrum with LispA Brainfuck interpreter in Common Lisp — how do you spell geeky?Tags: brainfuck lisp interpreters [...]
[...] just couldn’t leave it alone. The charm of learning two languages at once by writing an interpreter for one using the other consumed my attention. Furthermore, I had left the door open for adding debugging facilities, [...]
CL-LAUNCH provides a consistent way to access command-line arguments across many different CLs.
Thanks for the tip, Zach. For anyone interested, here’s a link: http://www.cliki.net/cl-launch
Many new lispers make the mistake of using macros when functions will do. You’ve done so as well, i blame Graham
.
;;; Macros for accessing current state
;;;
(defmacro bf-current-instruction (engine)
`(car (bf-future-code ,engine)))
(defmacro bf-current-cell (engine)
`(car (bf-right-cells ,engine)))
One hint is that, if you’re evaluating all your arguments, you’ve likely got a function on your hands. Also, never reach for a macro first… try to solve the problem using a functional solution and only add syntax if you really need it … a lot of the time you’ll find you don’t.
Macros are a powerful tool, and using poweful tools improperly is dangerous! Also, you lose the advantages of first class functions… you cannot pass macros as arguments.
Why didn’t you use a simple function? Too much On Lisp on the brain?
(defun bf-current-cell (engine) (car (br-right-cells engine)))
I also noticed your preference for recursion (using labels) over iteration. This strikes me as a graham-ism as well, though it might jsut be your background.
Anyways, sorry if i sound critical, it’s good code besides a few minor points, and it wouldn’t take much to transform it to idiomatic CL. Keep it up!
Thanks for the pointers – this is my first serious effort with Lisp.
In this case, I used macros much the same way I would use them in C or Synergy/DE — as a syntactic shortcut for inline code. Doesn’t a function add a call overhead that is consumed by the compile phase for a macro?
My use of recursion was definitely a “that’s what I was told I should do” to be more Lispish. Personally, I think loops might be simpler — except in the one case of nested [] processing (hunting for the nested one, not the match to the initial one).
Thanks again!
Macros are not for inlining code, they are for syntactic abstraction.
First off, don’t worry about performance of function calls … this is Lisp, function calls are highly optimized and almost never your bottleneck.
Second, don’t prematurely optimize. Lisp usually provides you with excellent tools to profile your application. I highly doubt the function call overhead for those two accessors are the bottleneck for this program.
Third, if it turns out that, after careful profiling, inlining the code would help, you use DECLARE INLINE and inline the functions directly rather than use a macro.
As for recursion being ‘lispish’.. well you’ve been misinformed!
Using the best tool for the job is lispish, and very often that tool is a LOOP. There are certain problems that lend themselves to recursive solutions, but equally many that are iterative by nature. Recursing is slower and uses more memory than the equivalent loop as well, so use a loop where a loop is what’s needed 
Undoing the damage graham does to new lispers is a never ending task!
As Drew says, you should never use macros when functions suffice.
Inlining is done with
(proclaim '(inline bf-current-cell))
C macros are nowhere near Lisp macros, so apart from the name, you shouldn’t see them as having anything in common.
OK, you guys convinced me. I have updated the download with some changes. The only instances of recursion that I kept are (1) processing nested [] matching and (2) processing arguments for inserting code in the debugger (because trying to convert that into a loop seemed very inelegant — contrast the append, which converted easily).
I also got rid of my macros, which revealed a reason why I had them: I can’t do a setf on the result of a function. But I sacrificed that shortcut for the ability of a client program to pass the function around if it needs to.
Thanks for the pointers.
> I can’t do a setf on the result of a function
Well, technically you’re correct, because SETF operates on PLACES, and FUNCTIONs return VALUES … but, you’re missing out on the miracle of lisp … everything is open to the programmer, including the assignment machinery!
(defun (setf bf-current-cell) (value engine)
(setf (car (bf-right-cells engine)) value))
As for converting loops, you’ve got the right idea. If it’s cleaner to do it recursively, you do so. If anything, ‘common lisp style’ often uses LOOP and recursion in the same function
.
Don’t get caught up on trying to be ‘lispy’, especially if your idea of what ‘lispy’ is comes from Paul Graham. CL includes loop and does not mandate tail recursion, for example… so what is more ‘lispy’?
The code looks great now, clear and idiomatic. Great job!
(smacks forehead in V-8 moment)
Brilliant! I’ve added the (setf bf-current-cell) function and used that abstraction on the +, -, and , operators.
Thanks again for the help!