I’ve just picked up the opening chapters of Let Over Lambda, which describes itself as a book on macro programming – particularly Common Lisp macro programming. One of the early macros given in the book is unit-of-time which looks like this:

(defmacro unit-of-time (value unit)
  `(* ,value
      ,(case unit
         ((s) 1)
         ((m) 60)
         ((h) 3600)
         ((d) 86400))))

In Common Lisp (in so far as I’ve been able to gather in one evening), macros are expanded in an imperative fashion using the built-in CL list manipulation functions. That is, if I call

(unit-of-time 5 m)

CL will bind the integer 5 to parameter value, and the symbol m to unit, then evaluate the list expression inside the macro, in this case giving (* 5 60). That is to say, (unit-of-time 5 m) is replaced with (* 5 60), and the latter is then evaluated at runtime to give the final result. Within a defmacro definition you can use the built-in CL functions – in this case, quasiquotation and the case form – to manipulate source code passed into the macro and transform it into something else. You’re directly manipulating source code by using defmacro.

Scheme’s syntax-rules macro system takes a more declarative approach to macros and provides a pattern-matching language for transforming source expressions into lower-level function calls. A Scheme implementation of the above might look like this:

(define-syntax unit-of-time (syntax-rules ()
  ((unit-of-time value unit)
   (* value (case 'unit
              ((s) 1)
              ((m) 60)
              ((h) 3600)
              ((d) 86400))))))

Superficially this looks almost the same, but there’s an important difference lurking beneath the surface. Whereas the CL macro will expand (unit-of-time 5 m) as (* 5 60), the Scheme version will expand it as:

(* 5 (case 'm
       ((s) 1)
       ((m) 60)
       ((h) 3600)
       ((d) 86400)))

That is, Scheme slots the macro parameters into a template, which is used to replace the original expression. You don’t manipulate the source yourself, you use this templating system to declare transformation patterns. Now a smart compiler might spot that that case expression evaluates to a constant and optimise it, but suppose we’re using a toy interpreter that we’re rather fond of but isn’t all that clever. We want to make Scheme inline the conversion factor. We’d need to write the macro like this:

(define-syntax unit-of-time (syntax-rules (s m h d)
  ((unit-of-time value s) value)
  ((unit-of-time value m) (* value 60))
  ((unit-of-time value h) (* value 3600))
  ((unit-of-time value d) (* value 86400))))

This way, Scheme will pick one of the matching patterns and use the corresponding template with the factor hard-coded. The s case even avoids an unnecessary multiplication.

Still it’s clear that CL is better suited to some types of macro writing: it gives you full access to the source code as a Lisp data structure that you can manipulate with Lisp’s list processing library. Scheme only allows certain rigid transformations using its pattern language, making certain things awkward to express. However, Common Lisp’s power is blunted slightly by most Lisps’ distinction between compile time and run time. Your code is first compiled, one stage of which is expansion of all macros, and once this is finished the expanded source is executed. This means that a defmacro can only use functions that are built into the CL environment. User-defined functions are not available until run time and so cannot be used to manipulate source code.

Heist, being the naïve so-and-so that it is, only has run time. Macro calls are expanded as they are encountered at run time, their expansions being inlined into the source tree once processed. Macros, special forms, built-in and user-defined functions all have first-class status, and are implemented as different types of Function that we call as we evaluate code. This means, if you were to add defmacro to Heist, it would be called at run time and therefore have access to any user-defined function.

So let’s go and implement it. The latest Heist update (0.3.2) added the ability to easily load Ruby files from Scheme land, meaning I can write a Ruby file called defmacro.rb and load it in Scheme using (load "defmacro"). In your Ruby files you can use define and syntax to add functions to the Scheme environment.

To begin with, we’re going to need a new class to model CL-style macros. It should inherit from the Heist Function class so it receives all the references it needs from the interpreter; we just need to override the call method to implement defmacro behaviour.

class CommonLispMacro < Heist::Runtime::Function
  def call(context, cells)
    scope = Heist::Runtime::Scope.new(@scope)
    cells.to_a.each_with_index do |cell, i|
      scope[@formals[i]] = cell
    end
    expression = @body.map { |e| Heist.evaluate(e, scope) }.last
    Expansion.new(expression)
  end
end

A quick walk-through: Heist will call this type of function with context (an object representing the scope the function call is made from) and cells which is a Lisp list of the unevaluated argument expressions to the function. Heist Function objects have a @scope, which is the scope they are defined in, an array of the names of their arguments in @formals and a Lisp list of the expressions they contain in @body. We begin by making a new Scope in which to evaluate the function’s innards. Then we take the unevaluated argument expressions and assign them in the new scope using the variable names from @formals. We evaluate all the expressions in @body and return the last one, wrapped in an Expansion. The @body should return a list structure that could be evaluated as Scheme source code.

What’s this Expansion object? Well, we don’t want the expanded expression to be the macro call’s return value. We want Heist to insert this new expression into the source code, replacing the old expression, and then evaluate it to get the final value. To make this happen, we need to return an object of type Macro::Expansion, and this object should have an expression method. Heist takes care of all the rewriting and further evaluation as long as your function returns one of these. Our Expansion class is just a dumb wrapper around an expression and doesn’t need to do a lot of the expansion work that Heist’s macro system usually does.

class CommonLispMacro
  class Expansion < Heist::Runtime::Macro::Expansion
    attr_reader :expression
    def initialize(expression)
      @expression = expression
    end
  end
end

With these defined, all that’s left is to provide a front-end for making these functions from Scheme. In Heist, a Function is constructed using the current scope, a list of argument names and the function body.

syntax('defmacro') do |scope, cells|
  scope[cells.car] = CommonLispMacro.new(scope, cells.cdr.car, cells.cdr.cdr)
end

In the expression (defmacro foo (one two) (* one two)), cells.car refers to foo, cells.cdr.car to (one two) and cells.cdr.cdr to ((* one two)) – remember the body can contain more than one expression. Now you can drop the above Ruby in defmacro.rb, boot up Heist and use CL-style macros:

(load "defmacro")

(defmacro unit-of-time (value unit)
  `(* ,value
      ,(case unit
             ((s) 1)
             ((m) 60)
             ((h) 3600)
             ((d) 86400))))

(unit-of-time 5 s)
; => 5

(unit-of-time 5 m)
; => 300