Lisp: Tears of Joy, Part 7

Time to Lisp

Lisp has been hailed as the world’s most powerful programming language. But only the top percentile of programmers use it because of its cryptic syntax and academic reputation. This is rather unfortunate, since Lisp isn’t that hard to grasp. If you want to be among the crème de la crème, this series is for you. This is the seventh article in the series, which began in June 2011.

Macros — can’t get enough of them!

You already know from my previous articles that macros are Lisp programs that generate other Lisp programs. The generated Lisp code has fully parenthesised notation, and so does the macro that generates the code. In the simplest case, a macro substitutes forms within a template, clearly establishing a visual correspondence between the generating code and the generated code.

Complex macros can use the full power of the Lisp language to generate code according to the macro parameters; often, a template form is wrapped in code that constructs appropriate sub-forms, but even this approach is just a typical pattern of use, and not a requirement (or restriction) of the Lisp macro facility.

To refresh our memories, let’s examine the mechanism by which the Lisp system translates code generated by a macro. You define a macro with a defmacro form; defmacro is like defun, but instead of returning values, the body of the defmacro returns a Lisp form. Your program ‘calls’ a macro the same way it calls a function, but the behaviour is quite different.

First, none of the macro’s parameters are evaluated…ever. Macro parameters are bound literally to the corresponding arguments in the macro definition. If you pass (* 7 (+ 3 2)) to a macro, the argument in the body of the macro definition is bound to the literal list (* 7 (+ 3 2)) and not the value 35.

Next, the macro expander is invoked, receiving all of the actual parameters bound to their corresponding arguments as named by the defmacro form. The macro expander is merely the body of the defmacro form, which is just Lisp code; the only catch is that the Lisp system expects the macro expander to return a Lisp form. The Lisp system then evaluates whatever form the macro expander returns.

A Lisp implementation may expand macros at different times. A macro could be expanded just once, when your program is compiled. Or it could be expanded on first use as your program runs, and the expansion could be cached for subsequent reuse. A properly written macro will behave the same under all of these implementations.

Let’s explore a real-world example of using a macro to extend Lisp into the problem domain. In addition to providing a macro expander, our new macro will automatically generate an environment that will be referenced by the expander. Our example will show how to move computations from run-time to compile-time, and how to share information computed at compile-time.

Let’s say you’re working on an interactive game that makes heavy use of the trigonometric function sin r in computing player motion and interaction. You’ve already determined that calling the Lisp function sin is too time-consuming; you also know that your program will work just fine with approximate results for the computation of sin r. You’d like to define a lookup-sin macro to do the table lookup at runtime and also hide the details of table generation, which would just clutter your program’s source code.

Your macro will be invoked as (lookup-sin radians divisions), where radians is always in the range of zero to one-half pi, and divisions is the number of discrete values available as the result of lookup-sin. At runtime, the macro expander will just compute the index into a lookup table, and return the value from the table. The table will be generated at compile-time (on most Lisp systems). Furthermore, only one table will ever be generated for a given value of divisions in the macro call.

;; This is where we cache all of the sine tables generated during compilation.
;; The tables stay around at runtime so they can be used for lookups.
(defvar *sin-tables* (make-hash-table)
    "A has table of tables of sine values. The hash is keyed by the number of entries in each sine table.")

;; This is a helper function for the lookup-sin macro. It is used only at compile
;; time.
(defun get-sin-table-and-increment (divisions)
    "Returns a sine lookup table and the number of radians quantised by each entry in the table. Tables of a given size are reused. A table covers angles from zero to pi/2 radians."
(let ((table (gethash divisions *sin-tables* :none))
      (increment (/ pi 2 divisions)))
    (when (eq table :none)
        ;; Uncomment the next line to see when a table gets created.

        ;; (print `|Making new table|)
        (setq table
            (setf (gethash divisions *sin-tables*)
                  (make-array
                    (1+ divisions)
                    :initial-element 1.0)))
        (dotimes (i divisions)
            (setf (aref table i)
                  (sin (* increment i)))))
     (values table increment)))

;; Macro calls the helper at compile time, and returns an AREF form to do the
;; lookup at runtime.
(defmacro lookup-sin (radians divisions)
    "Return a sine value via table lookup."
    (multiple-value-bind (table increment)
                         (get-sin-table-and-increment divisions)
        `(aref, table (round, radians, increment))))

Let us examine what is happening here. When this program runs, it executes just aref  (and associated round) to look up the sin r value.

> (pprint (macroexpand-1 `(lookup-sin (/ pi 4) 50)))

(AREF #(0.0D0 0.03141075907812829D0 0.06279051952931338D0 0.09410831331851433D0 0.12533323356430426D0 0.15643446504023087D0 0.18738131458572463D0 0.21814324139654257D0 0.2486898871648548D0 0.2789911060392293D0
        0.3090169943749474D0 0.3387379202452914D0 0.368124552684678D0 0.3971478906347806D0 0.4257792915650727D0 0.4539904997395468D0 0.4817536741017153D0 0.5090414157503713D0 0.5358267949789967D0 0.5620833778521306D0
        0.5877852522924731D0 0.6129070536529765D0 0.6374239897486898D0 0.6613118653236518D0 0.6845471059286887D0 0.7071067811865476D0 0.7289686274214116D0 0.7501110696304596D0 0.7705132427757893D0 0.7901550123756904D0
        0.8090169943749475D0 0.8270805742745618D0 0.8443279255020151D0 0.8607420270039436D0 0.8763066800438637D0 0.8910065241883678D0 0.9048270524660196D0 0.9177546256839811D0 0.9297764858882515D0 0.9408807689542256D0
        ...)
      (ROUND (/ PI 4) 0.031415926535897934D0))

Note that the macro call makes no mention of a lookup table. Tables are generated as needed by (and for) the compiler.

> (lookup-sin (/ pi 4) 50)
0.7071067811865476D0

In the macro expansion, the #(...) is the printed representation of the lookup table for 50 divisions of the quarter circle. This table is stored in the *sin-tables* hash table, where it is shared by every macro call to (lookup-sin angle 50). We don’t even have to do a hash lookup at runtime, because the macro expander has captured the free variable table from the multiple-value-bind form in lookup-sin.

Macros that define macros

Macros that define macros are used infrequently, partly because it’s hard to think of a good use for this technique, and partly because it’s difficult to get right. The following macro, based on an example in Paul Graham’s book On Lisp, can be used to define synonyms for the names of Lisp functions, macros, and special forms.

> (defmacro defsynonym (old-name new name)
"Define OLD-NAME to be equivalent to NEW-NAME when used in the first position of a Lisp form."
 `(defmacro, new-name (&rest args)
                    `(,`,old-name, @args)))
DEFSYNONYM

> (defsynonym make-pair cons)
MAKE-PAIR

> (make-pair `a `b)
(A . B)

Macros are always a little bit dangerous because code containing a macro call does not automatically get updated if you change the definition of the macro. You can always establish your own convention to help you remember that you need to recompile certain code after you change a macro definition. But there’s always the possibility that you’ll forget, or make a mistake.

Ultimately, the likelihood that you’ll inadvertently end up with code that was compiled with an old version of a macro is directly proportional to how often you’re likely to change the macro. A macro like defsynonym practically begs to be used again and again as you generate new code. If you change your mind about the old name to associate with a given new name, all of your previously compiled code will still refer to the old name that you had decided upon earlier.

I’ll leave you here to have fun with your macros.

In the next article, we’ll take a peek into Common Lisp Object System (CLOS) which allows you to build very sophisticated object-based systems. If you care to code with a strongly object-oriented mindset, you will probably find all the OOP language functionality you need in Common Lisp. CLOS has many advanced object-oriented features that you won’t find in many other places. Because of this, CLOS has often been used as a research tool for studying OOP ideas.

  • Linux For You

    Bessem Rebai Kindly post unrelated comments separately — that is open a new thread. While your announcement is great, we fail to understand how it’s related to the article on Lisp that’s shared here.

All published articles are released under Creative Commons Attribution-NonCommercial 3.0 Unported License, unless otherwise noted.
Open Source For You is powered by WordPress, which gladly sits on top of a CentOS-based LEMP stack.

Creative Commons License.