Rekonstrukt Progress: MIDI Drum Machine, Turnkey Application Support

I made quite some progress on rekonstrukt during the last few weeks, and I can happily report that this whole "build a system from scratch" has not turned into a full time occupation, but is very doable as an after work thing. I'd certainly be interested in lifting the effort to a more, say, professional scale in the future, but for the time being, it is nice to both have something to play with in the evening and still maintain a family and a professional life.

Implementing a MIDI drum machine in hardware

One of the application areas that I am currently interested in is music hardware. I'm into electronic music, and even though I am not much of an artist (that'd be hardly compatible with a family and a professional life), I like playing around with and building gear. For a start, I created a drum machine in VHDL. It is a very simple 8 track, 16 beats drum machine, but it runs fully autonomous and requires no CPU, other than for setting up the pattern, tempo and notes. Suffice to say, the drum machine is clocked tightly. There is no interrupt latency to consider, and the CPU is free for the user interface.

This is an interesting experiment in that what I have basically done is create a special purpose processor that plays rythms. This processor is very restricted, but it performs the task that it has been created for efficiently and without a lot of overhead. Certainly, the same thing can be done in software and development times might have been shorter, yet the real time aspect of the problem makes the details rather hard to get right.

The drum machine is rather limited, though, as it can only play 16th notes. I may be implementing a MIDI file player in VHDL in the future, which will be able to play tracks of arbitary complexity. The 16th structured grid of the drum machine will then only be implemented in software.

Turnkey application support

The drum machine actually works well and makes real noises, but getting the software into the running rekonstrukt system on the FPGA started to bother me. There were two ways of getting Forth words into the FPGA: One could either add them to the code that is cross compiled and placed in ROM, or one could upload the source code through the serial port onto the running FPGA. Putting random code into ROM, in addition to the limited amount of space available, has the down side that variables cannot be created in the usual Forth way, by just defining a word and leaving some space in the word's body free as storage for the variable value. Instead, variables in ROM need to be explictly allocated in RAM, which is at least cumbersome. Uploading through the serial port is not a viable option for deploying applications - After all, the device needs to work when switched on.

The easiest way to load data into the rekonstrukt system is to include it in the FPGA configuration bitstream as initialization vector for the FPGA. Block RAM that is used to implement both the ROM and the RAM of rekonstrukt, and block RAM can be initialized from the configuration bitstream.

The binary image for the ROM is created using cross compilation on the host system. The contents of the RAM blocks that are used for the rekonstrukt system RAM is normally not considered by Maisforth. During system startup, the dictionary pointer is normally initialized so that new words are created in RAM right above the 768 bytes that are reserved for system use.

In order to support loading application code into rekonstrukt with the FPGA bitstream, I modified the COLD word which is called to initialize the Forth system. COLD now calls the new DICT-FROM-RAM word which checks whether the RAM contains application code (consisting of dictionary entries in the Forth vocabulary) and, if so, includes these words in the dictionary of the starting Forth system. In addition, I implemented a new TURNKEY vectored word that is called upon system startup. The default TURNKEY action prints the version and copyright herald and then enters the text interpreter loop. Applications can implement whatever code in their turnkey word.

To create a FPGA configuration bitstream with RAM initialization vectors with application code, I modified the usim mc6809 simulator so that it can dump a core image of the running simulated Forth system to a file on the host. Dumping a core can be initiated from Forth. I have implemented hooks to the SWI2 (Software Interrupt 2) instruction so that the Forth can "call back" into the host, initiating the file dump. This process can be fully automated, so creating preinitialized FPGA bitstreams is possible from the Makefile in the forth/ subdirectory of the rekonstrukt source tree.

To sum up: It is now possible to create FPGA configuration bitstreams containing the hardware description, the Forth core and the application code and have the application run automatically after the bitstream has been loaded. I am still using block RAM for all of rekonstrukt's memory, so a lot of the block RAM resources of the FPGA are currently consumed. My next plan is to port rekonstrukt to the Avnet Spartan-3A Evaluation Kit. At $49, this board is cheap and Avnet also offers a 1 Megabyte SRAM add-on board, costing $20. I will try to implement a small boot loader that fits into 1 block RAM which initializes the external SRAM from either the serial or the parallel Flash ROM. That way, most of the block RAM will be available to the application.

Der Chaos Computer Club feiert seinen großartigen Erfolg!

Heute hat das Bundesverfassungsgericht seine Entscheidung zu der Klage zweier Bürger gegen den Einsatz von Wahlcomputern bei der Bundestagswahl 2005 bekanntgegeben. Dieser Einsatz war nicht rechtmäßig, und der CCC bejubelt dies nun als großartigen Erfolg seiner Kampagne. Über das Urteil selbst möchte ich mir als Nichtjurist keine größeren Gedanken machen, über das Gejubel des CCC jedoch schon:

Der CCC versteht sich ja als sowas wie das NGO der Computer-Experten. In der Öffentlichkeit wird er als kompetent, engagiert und politsch wachsam wahrgenommen. Wann immer es gilt, die angeblichen bürgerlichen Rechte von Menschen im Netz zu schützen, erklärt sich der CCC für zuständig. So auch hier: Ausgehend von einer Aktion holländischer Hacker wurde eine Kampagne gegen Wahlcomputer losgetreten: Wahlcomputer seien grundsätzlich schlecht, weil nicht transparent, und deswegen gehören sie verboten. In einigen Bundesländern ist das schon passiert, und jetzt scheint es auch im Bund bald so weit zu sein: Wahlen in Deutschland haben mit Stift und Zettel zu geschehen, denn alles andere, wir wissen es dank der fleißigen Hacker, ist "unsicher".

Als Konsequenz dürfen wir also in Zukunft nicht darauf hoffen, mehr direkte Demokratie mit Hilfe elektronischer Verfahren zu realisieren. Diskutieren, ja. Entscheiden? Nur mit Stimmzetteln. Und das haben wir nun ausgerechnet den Leuten zu verdanken, die am Liebsten an Ihren Computern herumhängen, sich ihr Leben mit dem Internet organisieren und sich mehr und mehr über die elektronischen Medien definieren.

Herzlichen Glückwunsch, lieber CCC!

P.S.: Weniger polemisch und fundierter hat Till Westermeyer seine Gedanken zu diesem Thema veröffentlicht. Danke dafür!

Hardware/Software Co-Design - What it means with rekonstrukt

One of my primary goals with the rekonstrukt project is to create a hardware/software co-design environment that cuts down on turnaround times and gives me, the designer, flexibility to test and try out things at various levels. Here is what this means in practice:

rekonstrukt consists of the MC6809 microprocessor running Maisforth. The microprocessor can be implemented in three ways:

• In the usim software emulator, which is written in C++ and runs on my workstation. In this mode, the emulator needs be extended in C++ if I want to emulate more of the hardware that the real implementation provides. This mode has fast turnaround times (the simulated 6809 is way faster than the real hardware) and is useful to try out algorithms, learn Forth and the like. It is not timing accurate.
• In the Active-HDL simulator, again running on my workstation. In this mode, the actual VHDL implementation of rekonstrukt is simulated. The simulation is still fast enough to run small pieces of actual Forth code. It is a good mode to pinpoint hardware and timing issues, and Active-HDL has great flexibility with respect to setting breakpoints and inspecting the simulated state, which helps a great deal with diagnosing issues.
• On the FPGA. The interactive nature of Forth means that this way is often most productive. By actually trying out things, I can quickly gain confidence in my design or explore ideas, getting immediate feedback. In this mode, the logic analyzer is the crucial tool to verify waveforms and timings, and it is not that suitable for pinpointing problems that are inside the FPGA.

In all three modes, it is possible to recompile the Forth kernel and put it into operation in a few seconds. The usim simulator directly works with the ROM image that the cross compiler generates, the VHDL simulator can load a pre-initialized ROM image in VHDL format, and the new ROM image can also be merged with a completely synthesized FPGA bit stream. Thus, synthesizing the hardware is required only when changes need to be tried out on the real hardware. Trying out firmware changes only requires running the Forth cross compiler and restarting the simulator or downloading the bitstream to the target hardware.

Synthesizing rekonstrukt on my workstation takes about 10 minutes, but as the design is split into partitions, changes to individual parts of the hardware does not require a full synthesis run. Incremental runs take only about 3 minutes. Sure, I'd love to see that be faster, but it is bearable

I love this shit :)

ACIA fixed, S3E SK sucks

In the last two weeks, I was making good progress with my attempt to fully support the Spartan-3E starter kit by Maisforth. I had to improve my SPI controller slightly so that it works better for programming the serial Flash, worked on implementing the (ancient) standard Block I/O vocabulary so that the serial Flash can be used like a floppy disk in the old days and almost got the beautiful vibe full screen block editor to work.

One thing that was began to bother me a lot was the development cycle for Forth programs: I use Emacs to edit stuff, then copy and paste it to the real hardware. As my programs grow, this begins to take considerable time, but for some reason I could not send the data through the serial port at full speed: Maisforth reproduceably lost characters, and I had to insert a small delay after each character sent which made uploads slow. Too slow.

Thus, I went to pinpoint the reason for this character loss. At first, I thought that what I saw was a problem related to the lack of flow control. The serial port on the Spartan-3E Starter Kit is only equipped with RX and TX signals, so no hardware flow control is possible and software flow control is not implemented. After some investigation and experiments it became clear to me, though, that the problem was not flow control related. Both hardware (RTS/CTS) and software (XON/XOFF) flow control work under the assumption that data is buffered in larger chunks, but my character loss happened even when I sent short bursts at full speed to the FPGA.

The problem really was related to the lack of double buffering in the transmitter of the System09 UART. This meant that the transmitter signalled the "transmit buffer full" condition for the whole duration of the actual send operation, even though the data had already been copied from the transmit buffer to the shift register. As the serial port echo in Maisforth is generated by Forth itself, processing of every character and sending it back out through the serial port introduced a pause between every character echoed, which quickly caused problems when characters to be echoed came in at full serial port speed.

The fix for the problem was to introduce double buffering. As soon as the character to be transmitted has been copied over to the transmitter shift register, the UART module now signals the host that the transmit buffer is available for the next character to be sent. This made the problem disappear as Forth echo processing can now take place while the previous character echo is transmitted. Given the slow serial port and the high clock rate of System09, there now is plenty of time for all processing needed.

The Spartan-3E Starter Kit sucks

Well, not really. It is a nice cheap board with a good load of on-board peripherals, useful documentation and nice example designs, but it also has severe limitations: The on-board FPGA is a XC3S500E, which has 40 kByte of block RAM. In my current Maisforth setup, I use 16k for the Forth kernel ROM, 16k for RAM, and 6k for the VGA controller. This leaves only 2k free, so that makes playing with table based waveform synthesis really hard. What I hoped for was that I could put the Forth kernel and the board support Forth library into the parallel NOR flash of the S3ESK and map the Flash into the 6809 address space.

The show stopper for this plan is the fact that data bit 0 of the NOR flash is shared with the SPI bus data signal. Thus, one can either access the flash or the SPI, but not both at the same time. Seemingly, the idea is to copy the contents of the NOR flash into SDRAM and then run from there, but I'm still reluctant to try getting the SDRAM to work. The easy path is blocked, though, and maybe using SDRAM is the best option.

Rekonstrukt - A "New" Forth Machine

I have been a Fan of Forth since the 1980ies, and when I picked up my FPGA stuff a few weeks, I decided to put some more effort into getting a complete Forth based FPGA system to run before turning back to the SECD reimplementation project. This new Forth machine is called "Rekonstrukt", and I have created a Google Code project to publish the source code.

My last FPGA productivity rush ended with Maisforth running on the Spartan-3E Starter Kit. Maisforth is a ANS-like 8 bit Forth originally written by Albert Nijhof for the somewhat obscure MC6809 based computer called "Maiskastje" built by a dutch computer club a few years ago. Porting Maisforth to System09 was rather easy; all that was needed was a little tweaking of the serial I/O routines so that the System09 MC6850-lookalike serial port was properly handled.

My next goal is to support most of the Hardware that the Spartan-3E Starter Kit has to offer by Forth. This will require some VHDL hacking in order to implement the low level interfaces as well as implementing Forth libraries.

Implementing a SPI controller

I started by implementing an SPI interface. SPI is a serial bus protocol for moderately high speed connections between devices inside one system. On the Spartan-3E board, the analog capture unit, analog preamplifier, digital to analog converter, serial flash and platform flash chips are all connected to one shared SPI bus. It would be possible to operate this bus by bit-banging in software, but this would be rather slow. In hardware, it is easily possible to operate the SPI bus at a bit rate of 10 Mhz.

While other open source VHDL SPI controllers exist, none of them easily interfaced with the "proprietary" bus protocol of System09. I took this as an opportunity to freshen up my VHDL and FPGA design skills. Again, I learned that it does not make sense to synthesize to the real hardware before simulation has shown that the design basically works, but that successful simulation does not automatically mean that the design works in the real hardware. With the help of some regulars in the #fpga IRC channel on freenode.net, I got the SPI controller to run.

Implementing vectorized I/O in Maisforth

System09 comes with a VGA controller that provides for a 80x25 text console, named vdu8. vdu8 is register based, i.e. to write a character onto the screen, the host CPU needs to write the screen position where the character should go into the cursor address registers, then write the character to be shown into the data registers. In order to make vdu8 useable as I/O device for Forth, a small terminal emulator is needed that interprets standard control sequences like Linefeed, Carriage Return and Backspace properly so that it can be used to handle EMIT calls.

The VGA console should be useable as an alternative to the serial console and switching between the two should be possible at run time. The common technique to achieve that is to make the words that need to be switched between alternative implementations be vectored, or "deferred" words. What this means is that a pointer to the word that actually implements the word is stored in the word that is being called by the system, and this pointer can be modified at run time in order to switch to the desired implementation.

Normally, the Forth compiler performs a name lookup when compiling a word, not when executing it. Thus, once a word has been compiled, the addresses of the words that are being called are fixed, and the implementations of these words cannot be changed in retrospect.

For normal, RAM based operation, implementing deferred words is quite simple:

: alias ( xt -- ) create , does> @ execute ;
: noop ( -- ) ;
: defer (  -- ) ['] noop alias ;
: is ( xt  -- ) ' >body ! ;

alias is used to set up an alias for a word. defer is used to set up an alias for the do-nothing word alias. The implementation of such a word can later be changed using the is word.

This works well for RAM based Forth in which the , word can be used to compile a number into the dictionary and change that later. For a ROM based Forth like Maisforth, the default dictionary is read only and as we are interested in vectorizing words that are used by the system, the vectors need to be put somewhere else. Maisforth provides for a "user space" for this purpose. The "user space" is located in RAM at the beginning of the address space, and the IVEC word can be used to allocate a cell from that space in the cross compiler. When adding new user vectors, the USERBYTES constant needs to be increased so that the cross compiler knows the changed memory layout. I did not find out how I could get the vectors initialized automatically by the cross compiler, so I added a new 'EMIT vector initialized to 0 which would be called in the (EMIT word, and changed the COLD word to intialize the 'EMIT vector when rekonstrukt starts.

More information about vectorized functions can be found in Leo Brodie's excellent book Starting Forth in the Chapter Under the Hood.

Trying Clojure...

I am becoming increasingly frustrated by Common Lisp's age. On the one hand, history makes it what it is: Mature, well-documented, thoroughly understood and practical. On the other, it fails to keep up with current system designs, lacking convenient native support for rich data structures, infrastructure access and parallel programming. No programming language choice is without tradeoffs and in that respect, and I'll still chose Common Lisp in many situations. Realistically, though, Common Lisp cannot be the only language in my tool chest. For browser work, Javascript is much more practical, and for parallel programming, I'm on the lookout.

On my last visit in Cambridge, I attended the Boston Lisp Meeting. The presentation scheduled was about the new Lisp dialect the Clojure by Rich Hickey, who is the creator of this language.

Parallel programming is one of the areas that Clojure wants to make easier. It does so by making all data structure immutable and by language-level abstractions for concurrent data access. In that respect, it is similar to Erlang as it requires a functional programming style everywhere. Unlike Erlang, which puts almost all operations with side effects behind a common message passing interface, Clojure exposes the full Java API to programs. Thus, side effects can be produced everywhere, except in algorithms implemented in Clojure.

Clojure wants to be a Lisp, but it explicitly does not try to be backwards compatible. This opened a rather large design space to Rich Hickey, and some of the choices he made really do make sense. He specifies a reader, yet his reader does not intern symbols. That is a big win, as it allows the reader to actually work with arbitary Clojure source files. In Common Lisp, one needs to re-implement a full reader which does not intern symbols if one wants to read Common Lisp source files. This is kind of ironic, as the "Code is Data" mantra that we keep repeating does not really reflect what is possible in practice.

Rich managed to make me enthusiastic about Clojure, and I decided to give it a spin with a real project that I wanted to conduct anyway: I am a Twitter user, and I would like to be notified of new posts to Planet Lisp on Twitter. The program would read the Planet's RSS feed using a HTTP request, determine if new items have been posted and update the Twitter status of the Planet Lisp Twitter account that I have set up for this purpose.

Getting the development environment up

My laptop runs Windows, but I do most of my Lisp development in a VMware running FreeBSD. As Clojure is hosted on the Java virtual machine, I decided to avoid the indirection and use Windows as my native platform. Clojure support for Slime is available, so I can stay in my familiar environment. A very recent CVS checkout of Slime is required, which took me a little while to figure out.

Processing XML

It took me a another while to discover what the proper way to process XML in Clojure is. An XML parser is included with the base distribution, but there is no information in the documentation how one would actually work with the data structure that is generated by the parser. For my application, I wanted to iterate over certain elements in the XML and extract a few subelements in a loop. An evaluator for XPath expressions would have suited the job, but obviously that is not the Clojure way to do it.

In Clojure, XML does not receive any special treatment. The parser reads it into a tree, and processing is performed using functions that process trees. As simple as it may sound, I had a hard time finding a practical example of how this was supposed to work. Chris Houser finally got me on the right track when he pointed me to his zip_filter package. zip_filter is a tool for filtering data out of trees, and it can work with trees produced by Clojure's XML parser.

Once I had figured this out, things were very easy. The Planet Lisp RSS feed can be read into an XML tree with

(clojure.zip/xml-zip (clojure.xml/parse "http://planet.lisp.org/rss20.xml"))

and one can extract data out of the parsed tree using path expressions:

(clojure.contrib.zip-filter.xml/xml-> xml :channel :item)

This certainly is concise and elegant, and I like the fact that XML is kept out of the program's way. Note that I've included the namespace prefixes in the examples above so that they can be copied and pasted. Normally, one would import these namespaces so that shorter or no namespace needs to be specified to access the symbols.

Making HTTP requests

In order to update the Twitter status, a HTTP POST request to Twitter must be made. A HTTP client which is based on the java.net.HttpsURLConnection class is available from the Files section of the Clojure Google Group. It is not a polished product and required some minor tweaking, but after that, fetching something using HTTP is as easy as

(http-client/url-do "http://planet.lisp.org/" "GET" {})

Reading and writing files

The Twitter gateway needs to persistently store the list of articles that it has found on Planet Lisp in order to decide which of the current articles are new. Clojure is a Lisp and thus can read and write its own data structures easily, so all it takes is calling a few functions. As in the XML case, the hard part was figuring out what the proper functions are, as the documentation is sparse. I found Stuart Halloway's Blog in which he publishes a number of articles describing how the examples from Peter Seibel's book Practical Common Lisp can be implemented in Clojure. The Simple Database example pretty much does the same thing that I required, so I looked at that. Unfortunately, the "spit" function that is the complement to "slurp" and writes a string to a named file did not appear to exist in the clojure namespace. It took a little grepping to find it in clojure.contrib.duck-streams, and referenced from there, it works as expected.

Functional glue

Having all the required components in place, it was time to come up with the real code. As data structures are immutable in Clojure, the challenge was to express the required loop so that both the new persistent state and the list of new postings would be maintained. I came up with a recursive function with two accumulators:

(defn poll
  "Poll planet lisp, check for new postings, update Twitter status when new postings have appeared"
  []
  (save-data
   (let [old-data (load-data)
         process
         (fn [items new-data new-items]
           (if items
             (let [item (first items)
                   guid (first (xml-> item :guid text)) ]
               (recur (rest items)
                      (conj new-data guid)
                      (if (old-data guid)
                        new-items
                        (conj new-items (first (xml-> item :title text))))))
             (do
               (maybe-post-twit new-items)
               new-data)))]
     (process (xml-> (feed-to-zip "http://planet.lisp.org/rss20.xml")
                     :channel :item)
              #{} []))))

To Scheme programmers, this style should be familiar. I find it not terrible myself, although one could certainly push things around to suit taste.

The Verdict

I was sceptical when I first read about Clojure. I am sceptical of new languages in general, and new Lisp family members always make me think "why?" first. Rich Hickey's presentation got me interested because he gave very good reasoning for his design choices. He also is a very good presenter and could easily withstand an audience of die-hard Lispers that included people who have played an active role in the creation of Common Lisp. But that is the singer, not the song.

The good

The fixed reader, vastly improved data structure support, access to a host of libraries and concurrency support all make a good case for Clojure. It is Lisp in many respects, and in the uncompromised macro facility opens up the extensibility that I am used to from Common Lisp.

The bad

Clojure is not multi-paradigm in the sense that Common Lisp is: A functional programming style is required, and there is no way around that. Making the comma be white space is somewhat of an arbitary decision, that does not match the other design choices that seem to be grounded better.

The ugly

The error messages that the compiler produces are mostly useless. Debugging is hard, as no tracing facility and no breakpoints are available - Or maybe they are, but I could not find them in the documentation. The overall immaturity of the language shows frequently, and I have spent hours looking for code examples and finding my way through something that is very much in flux.

My Conclusion

I like Clojure, as it seems to fill my need for a language that supports concurrency and makes it possible to write modern desktop applications, while still being a Lisp. I will use it for another project I have been planning to do in Erlang. For general exploratory development, Clojure is not yet a good choice as the development environment is too immature.

I am not buying Rich Hickey's claim that classic object oriented programming is bad because it does not support concurrency. I begin thinking of object oriented systems more as active databases that allow modeling of complex, interconnected and persistent data structures. Such structures are managable with a pure sequential execution model, and one should refrain from mixing that with tasks that are inherently concurrent.

Finally: My Twitter gateway for Planet Lisp exists, but I have not yet been able to deploy it. Getting Java to run on FreeBSD/amd64 has proven to be kind of a challenge. I will have this sorted out soon, so feel free to follow planet_lisp.

Revisiting SECD and the power of Lisp

While visiting the ICFP Conference 2008, I was discussing my SECD microprocessor reimplementation project with my co-worker Kilian. The SECD is a classic virtual machine architecture supporting functional programming languages invented by Peter J. Landin in the early 1960ies. It is a relatively unusual architecture in that it is commonly described by transformations of the machine state represented as four registers containing cons cells. In fact, the virtual machine's memory conceptionally consists of linked cons cells, not of a vector of words that is addressed by integer addresses. Jia-Huai You of University of Alberta has a good description of how the SECD virtual machine works.

Quoting SECD: DESIGN ISSUES, here is the specification of the SECD virtual machine. There is one line for each machine instruction, describing the state of the four machine registers before and after the particular instruction has been executed:

While we were discussing my hardware project, Kilian suggested that we should implement a SECD in Common Lisp in order to bridge some time that we had until the next break. Given that Lisp supports lists nicely, we chose to use Lisp lists to represent the SECD memory. We first fooled around with imperative code that mimicked the required state transformations, but soon realised that it would be much easier to directly transform the specification for each machine instruction into executable Lisp. Following common practice, we started writing down how we wanted to type in the specification for each of the SECD instructions. As an example, the LD instruction would be defined by this:

(define-instr 1 LD
  (s e (LD (m . n) . c) d)
  `((,(locate m n e) . ,s) ,e ,c ,d))

The literal "1" is the op code, the "LD" is the symbolic name of the instruction, the first list is the state before the instruction is executed (with the four list elements representing the state of the four registers), and the rest specifying the code to execute for the instruction. The executed code again returns a four element list representing the new state of the machine registers.

We then wrote a macro to transform this specification syntax into Lisp code. Our DEFINE-INSTR macro uses the first list as an argument to DESTRUCTURING-BIND, binding all the names that we then use in the transformed state:

(defmacro define-instr (code name pre post)
  (let ((name* (intern (format nil "~A-INSTR" name))))
    `(progn
       (setf (gethash ,code *instr-hash*) ',name*)
       (defun ,name* ()
         (multiple-value-setq (s e c d)
           (destructuring-bind ,pre (list s e c d)
             (assert (= ,name ,code))
             (values-list ,post)))))))

We were quite happy with our virtual machine, and we were able to run several of the precompiled SECD "binaries" from the ancient LispKit software collection. Getting the macro right and implementing the 21 instructions took little time, and it was easy to, say, instrument the macro for tracing or augmenting it with checks to make sure that we got the original syntax right. It would certainly be possible to polish the macro more - for example, having to specify the mnemonic of the operation twice is not so pretty. We just meant to create something that we could use to explore the behavior of the SECD architecture, so we did not care polishing.

The next day, I attended an introductory Erlang workshop and as I had some prior knowledge of Erlang (Programming Erlang by Joe Armstrong is a good read), I decided to try implementing a SECD VM in Erlang instead of doing the exercises suggested by the lecturer. Erlang has built-in pattern matching, so I used a transliteration scheme of the VM specification very similar to what I used in Lisp. Also, Erlang has lists, so representing the SECD memory as Erlang lists should be a one to one match, too.

So, here is the CAR instruction implemented in Erlang:

secd(S = [ [ CAR | _ ] | _ ],
     E,
     [ ?CAR | C ],
     D) ->
    secd([ CAR | S ],
         E,
         C,
         D);

In Erlang, function dispatch is based on pattern matching, and there is total flexibility to match structures and bind variables to what has matched. For example, in the implementation of the car operation above, we bind the variable S to the previous stack contents, and at the same time bind the variable CAR to the car of the cons cell that is sitting on top of the stack.

The Erlang version of the VM grew well, and the source code looked as nice as the Lisp version. Yet, as I tried to implement the the RAP instruction, I faced a major stumbling block.

The RAP instruction is used to support recursive function calls and works by replacing a previously created dummy environment on the stack, called OMEGA, by one which contains all the functions that are visible in the recursive scope. The specification uses RPLACA to denote that replacement operation, and that is what we used in our Lisp implementation of SECD, too:

(define-instr 7 RAP
  (((c* . e*) v . s) (om . e) (rap . c) d)
  (progn
    (assert (equal om 'omega))
    `(nil ,(rplaca e* v) ,c* (,s ,e ,c . ,d))))

When trying to implement RAP in Erlang, I got stuck because there are no destructive operations on lists. Not in the standard API, and seemingly not in the system API either. So, the Erlang SECD looks nice, only it does not run. Frankly, our Lisp based SECD has bugs, too, and I am not totally sure whether the problem is not in the RAP instruction.

Curiously, getting the RAP instruction right is harder than one wants to expect: In the SECD hardware implementation that I worked on, I used the original microcode of the SECD chip developed at the University of Calgary as part of a verification project. I found two major bugs in this microcode which, ironically, was part of the file set that compromises the proof that the SECD hardware implementation was correct according to its abstract specification. One bug was the garbage collector which did not work at all, and the other was in the RAP instruction which did not work either. I have trouble not concluding something regarding academia in general from these findings.

Anyway.... this was another time when I realized how much I like Common Lisp and why it will propably not be replaced by another language anytime soon. Common Lisp is teh tool of choice for my exploratory programming, as it does not have a terrible lot of restrictions, yet supports some advanced programming abstractions. There are domains where Common Lisp does not have much to offer, though. Concurrent programming currently is the one area where the lack of support in Common Lisp hurts me most. Erlang may be my cure, and I hope to look into Lisp Flavoured Erlang in order to spare myself the arcane syntax that Erlang provides by default.