Steve Cooper's Personal Blog

A lisp macro virgin tells all

I finished my first lisp macro, and I want to tell the world.

I’ll talk about what a lisp macro is, and what makes it unique in the world of programming, how it’s a technique only possible in lisp. I’ll then take you through an example.

So firstly, what’s a lisp macro, and why would you want to write one?

So, you may have seen lisp programs before, and you’ll recognise them instantly — Larry Wall, the inventor of [Perl][], said they had all the aesthetic appeal of a bowl of porridge mixed with toenail clippings;

(defun accumulate (combiner lst initial)
(let ((accum initial))
(dolist (i lst)
(setf accum (funcall combiner accum i)))
accum))

He has a point. They are butt-ugly. But hell, the best he came up with is [Perl][], so he can `$_@++` right off. (I’m pretty sure that’s valid Perl, too 😉 )

It’s ugly, in an aesthetic way, but it’s amazingly practical. It’s got an engineering beauty to it. If you look at that snippet above, you’ll notice that the whole program is made out of exactly three types of symbols;

* open parenthesis: `(`
* close parenthesis: `)`
* symbols, like `defun`, `accum` and `setf`

All simple lisp programs are like this. Just brackets to group stuff together, and stuff that needs grouping. Compare that with C#, where you might find;

* parenthesis for;
* function calls; `print(“hello”)`
* special forms; `using(OdbcConnection con = …)`
* semi-colon to end statements; `int x = 1;`
* curly brackets for;
* code blocks; `{ /* code block */ }`
* array initialisers; `string[] words = { “hello”, “world” };`
* square brackets for array indexing; `x[3] = 4`;

and the list goes on. I gave up because there are too many to list.

So lisp has this seriously small syntactic footprint. You can have a thing, or a group of things in brackets. It’s simple. It’s *so* simple that you can start doing crazy stuff in lisp that you just can’t do otherwise. That crazy stuff goes by the name of macros.

I can write a program that takes a chunk of lisp (remember, just a thing or a list of things), cuts it up, and reassembles it. That creates new lisp code.

So imagine you do a lot of work on three-dimensional arrays. You find yourself, over and over, writing nested loops that say;

for x in range(100):
for y in range(100):
for z in range(100):
# do something to matrix[x,y,z]

And frankly, you’re bored of typing it over and over. What you really want to do is something like;

for {x 100, y 100, z 100}:
# do something to matrix[x,y,z]

You want a brand new bit of syntax for multiple-value looping. Can you add it to python? Nope. C? Nope. Java? Nope.

But now look at the lisp version;

I could, theoretically, write this

(domanytimes (x 100 y 100 z 100)
body)

and, because it’s just a list of stuff, I can chop and change that into this new bit of lisp;

(dotimes (x 100)
(dotimes (y 100)
(dotimes (z 100)
body)))

I’ll show you how in a second, but notice what’s possible — I can write my own looping construct (`domanytimes`) and lisp will rewrite it into many simpler looping construct (the built-in `dotimes`).

Is that particularly special? Well, yeah. I’ve written new syntax. I’ve defined a new way of looping that is no different from the standard loops. I’ve basically added something new to the language. Lisp is now better at dealing with multi-dimensional loops. Try adding a new loop to ruby, or javascript. Make python understand

for x in range(100), y in range(100), z in range(100):
# body here

and you’ll find you can’t.

So I’ve made my version of lisp a bit better at handling loops. If I were writing database code, I could make lisp better at writing SQL statements or data access layers. C# recently got built-in DAL logic with [LINQ][], and it’s great, but only the C# team can write it. Whereas a lisper could write this sort of code;

(sql-select (ID NAME) from PROJECT where (DUEDATE > TODAY))

and it’s do basically the same thing as [LINQ][].

So that’s the why’s and wherefores. Here’s the how of the `domanytimes` macro.

`domanytimes` takes two parts; the loop variables `(x 100 y 100 z 100)` and whatever body you want to execute. We’re going to write a program that skims two elements from the front of the loop variables (say, `x` and `100`) and uses them to write a built-in `dotimes` loop; so a program which converts

(domanytimes (x 100 y 100) body)

into

(dotimes (x 100)
(domanytimes (y 100) body))

and then again to give you

(dotimes (x 100)
(dotimes (y 100)
body))

Here’s the `domanytimes` macro, in all it’s eye-bleeding horror;

(defmacro domanytimes (loop-list &body body)
“allows you to write (domanytimes (x 10 y 10) …)
instead of (dotimes (x 10) (dotimes (y 10)) body ))”
(if (eq (length loop-list) 0)
;; we have our form to execute
`(progn ,@body)
;; we have more loops to arrange
(let ((fst (car loop-list))
(snd (cadr loop-list))
(rst (cddr loop-list)))
`(dotimes (,fst ,snd)
(domanytimes ,rst ,@body)))))

There. Wasn’t that fun? 😉

It looks nasty, I know. All lisp looks nasty. But it’s actually created something new in the language. As far as I understand it, lisp has survived for fifty years basically because the macro system lets you write macros which can add any new kind of syntax you like. You can write knock up a set of macros to [implement OO][clos], and suddenly lisp is OO. You can know up macros for manipulating lazy lists, and suddenly lisp has a [lazy evaluation][lazy]. You can knock up data access layer macros, and it’s got a version of [LINQ][linq]. There seems to be nothing you can’t hack lisp into being.

And if you want to know how the hell that works, I’d recommend [Practical Common Lisp][pcl], which is online and free.

[linq]: http://msdn2.microsoft.com/en-gb/netframework/aa904594.aspx
[lazy]: http://en.wikipedia.org/wiki/Lazy_evaluation
[clos]: http://en.wikipedia.org/wiki/CLOS
[perl]: http://www.perl.com/
[pcl]: http://gigamonkeys.com/book/

Advertisement

Steve Cooper

,

26 responses to “A lisp macro virgin tells all”

  2. in ruby:

    domanytimes (x => 100, y => 100, z => 100) {
    #body
    }

    I know htis isn’t new syntax, but I’m wondering how many few cases there are where macros really give you something better than what you can do with meta programming in ruby.

    Reply

  3. you’ll find that you can’t

    Erm, wrong.

    in python (might be a bit shorter way, but this took me 20 seconds to puzzle out)

    for tup in ((xx,yy,zz) for xx in range(10) for yy in range(10) for zz in range(10)): print tup

    As a bonus, this one is a generator.

    Reply

  4. Jonathan Rockway: Clearly not the same thing.

    First the cosmetic stuff: in your perl solution you have the bounds of the iteration after the code. That’s harder to understand.

    But there’s another bug. You made the x, y and z variables dinamically bound (at least I think that’s what “our” does in perl). So you can’t capture the lexical environment in a lambda and just send it to the outside. That’s a big no-no.

    Reply

  5. @cory: ——–

    for tup in ((xx,yy,zz) for xx in range(10) for yy in range(10) for zz in range(10)): print tup

    So how does this really do what’s needed? First, you’ve got a fixed number of inner loops — in this case, three. How do you extend it to arbitrary length? The macro I gave takes any number of pairs. So you can use domanytimes for 2-, 3-, and 4-dimensional matrices by calling;

    (domanytimes (x 10 y 20) body)
(domanytimes (x 5 y 5 z 5) body)
(domanytimes (x 5 y 5 z 5 t 100) body)

    Also, how limited is the code you can pass in? Could you pass in variables declared outside the call? eg

    (let ((caption "Charity Calendar "))
    (domanytimes (month 12 year 2008)
        (create-calendar caption month year)))

    In this case, the ‘caption’ variable is used as a parameter. How do you def: something in python that will be able to use that variable?

    So the solution needs be a python construct called domanytimes (say, a function) which

    creates an arbitrary numbers of loops
    use variables declared outside the call to domanytimes
    executes arbitrary code

    @jay: ——–

    domanytimes (x => 100, y => 100, z => 100) { #body }

    So this is a function which takes a dictionary of loop variables and executes #body? Can the body include plain old references to the loop variables? that is, can you write;

    domanytimes (x => 100, y => 100, z => 100) {
    print x + y + z

    }

    @fil: ——–

    you can’t capture the lexical environment in a lambda and just send it to the outside. That’s a big no-no.

    I think that’s also the issue with cory’s python code (see the charity calendar code at the top of this comment.)

    Reply

  7. What are you using to edit your lisp code? I ask because its indented a bit strangely and lisp indentation is pretty standard.

    Reply

  9. @Ben:

    Thanks! I’m trying to document my way through both to clarify my own thinking, and because it’s harder to find beginner lisp stuff.

    @David:

    I’m using emacs (Peter Siebel’s LispBox distro) to develop, then I assembled my post in sublime text, which I’d recommend as a very pretty python-extensible text editor.

    One of the examples in the comments was just handwritten, so is probably a bit funny.

    @leppie:

    Very nice! And thanks for turning me on to IronLisp/IronScheme! Now all I have to do is convince my colleagues that they want to work in lisp, and I should make rapid lisp progress. 😉

    Reply

  12. this actually works 🙂 I had to separate the variable names from the values. The implementation is a little longer because DoManyTimes is a class and maintains state to pass to the block.

    DoManyTimes.run([3,3,3]) do |x,y,z|
    puts “#{x} #{y} #{z}”
    end

    You can use an arbitrary number of indices. DoManyTimes([10,10,10,10,10]) do {x,y,z,a,b| … end

    I’m sure there is a better way to do this in ruby, but I got sidetracked because I realized it would be a lot easier in javascript, I think 🙂

    Reply

  14. Your macro would be slightly prettier (and a little more Lisp-idiomatic) like this:

    <pre
    (defmacro domanytimes (loop-list &body body)
    (if (null loop-list)
    (progn ,@body)
    (destructuring-bind
    (fst rst . tail) loop-list    (dotimes (,fst , rst) (domanytimes ,tail ,@body)))))

    Untested, and I hope I got the markup right…

    Reply

  16. Try this one, which is more in the spirit of dotimes. If there are zero loop-list items, it runs the body once and returns nil. Else it works like yours except if there’s an extra single expression at the end of the loop-list it evaluates and returns it afterwards; else it returns nil.

    (defmacro domanytimes (loop-list &rest body)
  (if (oddp (length loop-list))
      `(progn (domanytimes ,(butlast loop-list 1) ,@body)
          ,(first (last loop-list)))
      (if loop-list
      `(dotimes ,(subseq loop-list 0 2)
         (domanytimes ,(rest (rest loop-list)) ,@body))
      `(progn ,@body))))
    Reply

  19. timbo: —

    I actually meant it this way round, since this is the form you’d see in an SQL statement. Inside a macro, you can rewrite the list

    '(DUEDATE > TODAY)

    into your second form, within the body of the macro. SQL programmers don’t get as thrown.

    Reply

  20. can’t u just do the same thing with a function that takes a closure as an arg. You would have the loop in this function call the closure.

    Reply

  21. jeff: —

    I don’t think so in all cases, but it certainly works for some.

    Also, it’s just prettier to write

    (domanytimes (x 10 y 10)
  (print (* x y))

    than it is to write

    (domanytimes (x 10 y 10)
    (lambda (a b) (print (* a b))))

    Reply

  22. @Steve:

    def domanytimes(*times)
    times.inject(lambda{|x| yield x}) {|old_lambda, val|
    lambda do |x|
    val.times do |y|
    old_lambda.call( x + [y] )
    end
    end
    }.call([])
    end

    domanytimes(2, 2, 2) {|(x,y,z)| puts “x: #{x}, y: #{y}, z:#{z}” } =>

    “x: 0, y: 0, z:0
    x: 0, y: 0, z:1
    x: 0, y: 1, z:0
    x: 0, y: 1, z:1
    x: 1, y: 0, z:0
    x: 1, y: 0, z:1
    x: 1, y: 1, z:0
    x: 1, y: 1, z:1”

    Takes some knowledge of ruby syntax to write, but the idea is fairly straightforward. The method expects a block with one parameter, so the base case is to simply yield that method (lambda {|x| yield x})

    For each argument given, we need to add another layer of looping, so we’ll define a function that accepts an argument, and then defines a for-loop, passing a mystery method the current value of the for loop and its argument in an array:

    (lambda {|x| val.times {|y| mystery_method.call( x + [y])}})

    Ruby’s Inject Method takes care of the rest of the magic, it expects a block accepting two parameters. For each value in ‘self’, it calls the block with whatever the last return of the block was as parameter 1, and the current value as parameter 2. We just have to pass in our base case as the initial value, and inject will use the lambda above to build an n-dimensional looping construct with the values given in the parameters.

    There is indeed more syntax involved here: there’s pipes for parameter passing and curly braces for blocks, but in the macro there’s graves, commas, and ‘@’ symbols interspersed throughout – syntax that shows up nowhere else in the lisp world. The extra syntax here is used on a daily basis in ruby.

    Reply

  23. Sorry, added some markup.

    
def domanytimes(*times)
  times.inject(lambda{|x| yield x}) {|old_lambda, val|
    lambda do |x|
      val.times do |y|
        old_lambda.call( x + [y] )
      end
    end
  }.call([])
end

domanytimes(2, 2, 2) {|(x,y,z)| puts "x: #{x}, y: #{y}, z:#{z}" }
    Reply
  24. import itertools

def ranges(*xs):
    return itertools.product(*map(range, xs))

for x, y, z in ranges(3, 3, 3):
    print x, y, z

    This requires Python 2.6 or later, although it’s easy enough to write itertools.product by hand if you have an earlier version.

    I’m not claiming that any new construct is this easy in Python. For instance, if you wanted to ignore certain kinds of exceptions thrown in your loop body, you’d be stuck writing

    for vars in iterable:
    try:
        do_stuff(vars)
    except FooError:
        pass
    Reply

  25. Actually as i call it “dynamic looping” can be implemented practically in any programming language which supports recursion. Something in the form:

    LoopManyTimes(LoopLevel, BottomLevel, … ) {
    If LoopLevel == BottomLevel
    // Do this and that
    Else
    // Call additional loop
    LoopManyTimes(LoopLevel+1, BottomLevel, …)
    }

    Recursion is still powerful tool 🙂
    Of course this doesn`t deny the fact that LISP macros is probably most powerful macro system in the world of programming languages.
    Good work,- keep it up !!

    Reply

  26. I think that many people here are missing the point. From what I understand, Steve is not trying to say that you can’t perform do-many-times in other languages, what he is saying is that other languages to not let you create your own syntactic form to let you use do-many-times with minimal effort, and that is very powerful.

    @Alex
    Regarding syntax, you are wrong in that backquote and company are not used outside of macros. they can be used anywhere, and indeed are useful in may other types of situations. and similar to the quote, they are just shorthand for longer sexps.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: