Hacker | Engineer

A friend of mine pointed me toward a wonderful Master’s Thesis about using Bluespec SystemVerilog (BSV) to develop an H.264 hardware video decoder. The introduction provides a clear overview of why C-based reference designs fall over for things like H.264 encoding/decoding, and the body of the paper demonstrates how to apply BSV to serious problems.

My professor in Computer Hardware Design this semester, when asked about BSV, dismissed it with something along the lines of “kids invent new HDLs all the time, but real men use VHDL or Verilog.” I’m getting the impression this is a prevalent believe in the electrical engineering world. Instead of moving forward and developing better and better tools, electrical engineers get stuck with old technology that is rarely optimal for the job. Things like BSV come along with the potential to completely change the market, but nobody notices because they’re too busy solving the same problems over and over again in lower-level languages.

Bluespec SystemVerilog provides some of the kind of abstraction I’m going for with Computer.Build. It’s a great tool, and I’m totally using it for Advanced Computer Hardware Design next semester. Unfortunately, it fall short of supporting metaprogramming. Why in the world would you want metaprogramming with hardware? For the same reasons you do it in software! Syntactic abstraction makes problem and solution definitions more concise and closer to the actual problem domain. This paper talks about exactly why this is crucial for H.264 decoding, but it applies everywhere. The C implementations just pass around huge shared memory structures, but this isn’t how the actual process of H.264 decoding works. BSV provides some great abstractions that get much closer to the problem, and for this application may be the best tool for the job.

I’m going for even more with Computer.Build, though. My goal is to allow the development of a multitude of DSLs for defining different kinds of hardware. For one-off solutions, you’re probably better off with BSV, but Computer.Build is intended to solve entire classes of problems in a manner only doable with DSLs or some other kind of language-level abstraction.

Abstraction is a fundamental component of software development and computer science. Metaprogramming is abstraction at the source-code level. Ruby (and the popular web framework Rails) popularized first-order metaprogramming, but it was certainly not the first language to support it. Lisp is arguably the most powerful language for metaprogramming, but most Lisps are weighed down by decades of legacy and limited libraries. Clojure is a modern take on Lisp implemented atop the Java Virtual Machine. Both Clojure and Ruby allow for metaprogramming and the creation of Domain-Specific Languages (DSLs), making them good candidates for the creation of Computer.Build: A DSL for defining microprocessors.

Computer.Build will be a high-level language for defining computer processors and their instruction set. Most computer hardware design today happens in VHDL or Verilog, neither of which support metaprogramming. Bluespec is an interesting step, but it still doesn’t allow for the level of abstraction Computer.Build requires. As such, an intermediate representation between Computer.Build and VHDL or Verilog must be created, forcing two layers of metaprogramming. The high-level Computer.Build code will be compiled/translated/evaluated to an intermediate hardware description language, which is then translated to VHDL. The end goal is an easy-to-use, high-level language for defining microprocessors that can be compiled into an FPGA design and run in hardware.

As a computer science research project, Computer.Build will be implemented in both Ruby and Clojure. The high-level DSL will have two variants, although they will achieve functional parity and look fairly similar. Computer.Build will require metaprogramming and code generation, both valuable features in a language. The primary goal of Computer.Build is to compare and contrast the metaprogramming facilities available in Ruby and Clojure, while the secondary goal is to create a useful tool for rapidly prototyping microprocessors. There is some potential for using Computer.Build to optimize key parts of a program by compiling them to hardware, allowing for massive speedup for some specific applications.

I will develop Computer.Build during the Spring 2010 semester at Rensselaer Polytechnic Institute under the supervision of Mukkai Krishnamoorthy, a professor at RPI, supervisor of Rensselaer Center for Open Source, and a great mentor to me. By the end of the semester, I will produce a technical paper comparing and contrasting the metaprogramming facilities in Ruby and Clojure. I will also share my progress here, at Hacker|Engineer, as I reach significant milestones or make interesting discoveries. The code will be published on Github under a license to be determined.

I love Ruby. As yet another Java convert, I enjoy Ruby’s expressiveness and simplicity, not to mention Rails. Lately I’ve been playing more with developing domain-specific languages in Ruby, and as Matz pointed out in his RubyConf keynote a couple of weeks ago, Ruby is great for building DSLs. As I start out on my next project, though, I’m beginning to understand why Lisp people go so crazy about macros. Basically, it’s all about the metaprogramming.

I see DSLs as 1st-order metaprogramming. You’re writing code that writes code, but you stop there. Rails does an amazing job of this, most notably in ActiveRecord relations (has_many, belongs_to, etc). As it turns out, many programming problems can be solved more elegantly with metaprogramming, and you generally only need one order of it. Instead of expressing the solution in basic language constructs, you go one level up and use a DSL. Not all problems, however, lend themselves to 1st-order metaprogramming. This is where macros come in: they’re nth-order metaprogramming.

Let’s say I want to design CPUs in FPGAs. I’m doing this for a class next semester, and the language we get to use, VHDL, is terrible at abstraction. So, I’m going to design a DSL for defining processors. Instead of working from the ground up, I’m going to start at the top and work down. Here’s what I’d like to write to build a simple little CPU.

Now, how am I going to get an FPGA from this? First off, I need to generate something more low-level that looks more like VHDL. Then, I’m going to need to translate that into actual VHDL so I can use an FPGA design tool like Quartus to get the end result. Now, how would I go about writing this? Well, I already started a bit, and the first step was a Ruby DSL for generating VHDL. But wait, I’ve got another DSL on top of that for the computer! Now what? Unfortunately, the backend for Ruby DSLs can get a bit messy, so trying to layer them is going to be a significant effort. Let’s take a step back here, though, and look at what I’m doing. What I really want here is 2nd-order metaprogramming. It can be done with two layers of 1st-order metaprogramming, but is there a better way?

Enter Lisp. Now, I’m not very experienced with Lisp yet, but that’s going to change now that I’ve recognized the significance. In a Lisp dialect, I could define my computer quite similarly to the Ruby above. Then, I use macros to decompose the “data” into something else closer to my goal. I can keep doing this until I’ve created a “data” structure that contains the code I want to execute, then I execute it! Layering the metaprogramming becomes a simple process of keeping track of the macros transforming the code, but they’re completely independent and loosely coupled. No more nasty DSL backend. No more struggling with code generation and parsing (How would you handle the “x+y” part of the above in a code-generating DSL?). This project is going to happen, but it’s going to happen in Clojure.

Lisp natively supports nth-order metaprogramming. In fact, from what I can tell, that’s pretty much the only thing it has going for it. The code/data duality of Lisp is somewhat akin to the wave/particle duality we encounter in physics. You can just accept it and move on, but to really understand things you must embrace the duality. This can be a big leap for a procedural programmer who tends toward languages like C, but I see it as the next step in my growth as a software developer. With nth-order metaprogramming, you can define the problem in code and work forward from there toward the solution, using as many layers of metaprogramming as you need. Often this is only one layer (thus Ruby’s awesomeness), but the flexibility to add another layer of metaprogramming when you need it can be well worth the learning curve required to pick up a language like Clojure.