21

I'm learning Scheme from the SICP and I'm getting the impression that a big part of what makes Scheme and, even more so, LISP special is the macro system. But, since macros are expanded at compile-time, why don't people make equivalent macro systems for C/Python/Java/whatever? For example, one could bind the python command to expand-macros | python or whatever. The code would still be portable to people who don't use the macro system, one would just expand the macros before publishing code. But I don't know of anything like that except templates in C++/Haskell, which I gather aren't really the same. What about LISP, if anything, makes it easier to implement macro systems?

  • 3
    "The code would still be portable to people who don't use the macro system, one would just expand the macros before publishing code." -- just to warn you, this tends not to work well. Those other people would be able to run the code, but in practice macro-expanded code is often difficult to comprehend, and usually difficult to modify. It is in effect "badly-written" in the sense that the author hasn't tailored the expanded code for human eyes, they tailored the real source. Try telling a Java programmer you run your Java code through the C preprocessor and watch what colour they turn ;-) – Steve Jessop Feb 23 '15 at 17:51
  • 1
    Macros need to execute though, at that point you're already writing an interpreter for the language. – Mehrdad Feb 23 '15 at 18:04
29

Many Lispers will tell you that what makes Lisp special is homoiconicity, which means that the code's syntax is represented using the same data structures as other data. For example, here's a simple function (using Scheme syntax) for calculating the hypotenuse of a right-angled triangle with the given side lengths:

(define (hypot x y)
  (sqrt (+ (square x) (square y))))

Now, homoiconicity says that the code above is actually representable as a data structure (specifically, lists of lists) in Lisp code. Thus, consider the following lists and see how they "glue" together:

  1. (define #2# #3#)
  2. (hypot x y)
  3. (sqrt #4#)
  4. (+ #5# #6#)
  5. (square x)
  6. (square y)

Macros allow you to treat the source code as just that: lists of stuff. Each of those 6 "sublists" contain either pointers to other lists, or to symbols (in this example: define, hypot, x, y, sqrt, +, square).


So, how can we use homoiconicity to "pick apart" syntax and make macros? Here's a simple example. Let's reimplement the let macro, which we'll call my-let. As a reminder,

(my-let ((foo 1)
         (bar 2))
  (+ foo bar))

should expand into

((lambda (foo bar)
   (+ foo bar))
 1 2)

Here's an implementation using Scheme "explicit renaming" macros:

(define-syntax my-let
  (er-macro-transformer
    (lambda (form rename compare)
      (define bindings (cadr form))
      (define body (cddr form))
      `((,(rename 'lambda) ,(map car bindings)
          ,@body)
        ,@(map cadr bindings)))))

The form parameter is bound to the actual form, so for our example, it would be (my-let ((foo 1) (bar 2)) (+ foo bar)). So, let's work through the example:

  1. First, we retrieve the bindings from the form. cadr grabs the ((foo 1) (bar 2)) portion of the form.
  2. Then, we retrieve the body from the form. cddr grabs the ((+ foo bar)) portion of the form. (Note that this is intended to grab all the subforms after the binding; so if the form were

    (my-let ((foo 1)
             (bar 2))
      (debug foo)
      (debug bar)
      (+ foo bar))
    

    then the body would be ((debug foo) (debug bar) (+ foo bar)).)

  3. Now, we actually build the resultant lambda expression and call using the bindings and body we have collected. The backtick is called a "quasiquote", which means to treat everything inside the quasiquote as literal datums, except the bits after the commas ("unquote").
    • The (rename 'lambda) means to use the lambda binding in force when this macro is defined, rather than whatever lambda binding might be around when this macro is used. (This is known as hygiene.)
    • (map car bindings) returns (foo bar): the first datum in each of the bindings.
    • (map cadr bindings) returns (1 2): the second datum in each of the bindings.
    • ,@ does "splicing", which is used for expressions that return a list: it causes the list's elements to be pasted into the result, rather than the list itself.
  4. Putting all that together, we get, as a result, the list (($lambda (foo bar) (+ foo bar)) 1 2), where $lambda here refers to the renamed lambda.

Straightforward, right? ;-) (If it's not straightforward for you, just imagine how difficult it would be to implement a macro system for other languages.)


So, you can have macro systems for other languages, if you have a way to be able to "pick apart" source code in a non-clunky way. There are some attempts at this. For example, sweet.js does this for JavaScript.

† For seasoned Schemers reading this, I intentionally chose to use explicit renaming macros as a middle compromise between defmacros used by other Lisp dialects, and syntax-rules (which would be the standard way to implement such a macro in Scheme). I don't want to write in other Lisp dialects, but I don't want to alienate non-Schemers who aren't used to syntax-rules.

For reference, here's the my-let macro that uses syntax-rules:

(define-syntax my-let
  (syntax-rules ()
    ((my-let ((id val) ...)
       body ...)
     ((lambda (id ...)
        body ...)
      val ...))))

The corresponding syntax-case version looks very similar:

(define-syntax my-let
  (lambda (stx)
    (syntax-case stx ()
      ((_ ((id val) ...)
         body ...)
       #'((lambda (id ...)
            body ...)
          val ...)))))

The difference between the two is that everything in syntax-rules has an implicit #' applied, so you can only have pattern/template pairs in syntax-rules, hence it's fully declarative. In contrast, in syntax-case, the bit after the pattern is actual code that, in the end, has to return a syntax object (#'(...)), but can contain other code too.

  • 2
    An advantage you haven't mentioned: yes, there are attempts in other languages, such as sweet.js for JS. However, in lisps, writing a macro is done in the same language as writing a function. – Florian Margaine Feb 23 '15 at 7:57
  • Right, you can write procedural (versus declarative) macros in Lisp languages, which is what allows you to do really advanced stuff. BTW, this is what I like about Scheme macro systems: there are multiple to choose from. For simple macros, I use syntax-rules, which is purely declarative. For complicated macros, I can use syntax-case, which is partly declarative and partly procedural. And then there's explicit renaming, which is purely procedural. (Most Scheme implementations will provide either syntax-case or ER. I've not seen one that provides both. They're equivalent in power.) – Chris Jester-Young Feb 23 '15 at 12:57
  • Why do macros have to modify the AST? Why can't they work at a higher level? – Elliot Gorokhovsky Feb 23 '15 at 16:36
  • 1
    So then why is LISP better? What makes LISP special? If one can implement macros in js, surely one can implement them in any other language as well. – Elliot Gorokhovsky Feb 23 '15 at 18:18
  • 3
    @RenéG as I said in my first comment, a big advantage is that you're still writing in the same language. – Florian Margaine Feb 24 '15 at 17:50
23

A dissenting opinion: Lisp's homoiconicity is far less of a useful thing than most Lisp fans would have you believe.

To understand syntactic macros, it's important to understand compilers. The job of a compiler is to turn human-readable code into executable code. From a very high-level perspective, this has two overall phases: parsing and code generation.

Parsing is the process of reading code, interpreting it according to a set of formal rules, and transforming it into a tree structure, generally known as an AST (Abstract Syntax Tree). For all the diversity among programming languages, this is one remarkable commonality: essentially every general-purpose programming language parses into a tree structure.

Code generation takes the parser's AST as its input, and transforms it into executable code via the application of formal rules. From a performance perspective, this is a much simpler task; many high-level language compilers spend 75% or more of their time on parsing.

The thing to remember about Lisp is that it's very, very old. Among programming languages, only FORTRAN is older than Lisp. Way back in the day, parsing (the slow part of compiling) was considered a dark and mysterious art. John McCarthy's original papers on the theory of Lisp (back when it was just an idea that he never thought could actually be implemented as a real computer programming language) describes a somewhat more complex and expressive syntax than the modern "S-expressions everywhere for everything" notation. That came about later, when people were trying to actually implement it. Because parsing was not well-understood back then, they basically punted on it and dumbed down the syntax into a homoiconic tree structure in order to make the parser's job utterly trivial. The end result is that you (the developer) have to do a lot of the parser's work for it by writing the formal AST directly into your code. Homoiconicity doesn't "make macros so much easier" as much as it makes writing everything else that much harder!

The problem with this is that, especially with dynamic typing, it's very difficult for S-expressions to carry much semantic information around with them. When all of your syntax is the same type of thing (lists of lists), there isn't much in the way of context provided by the syntax, and so the macro system has very little to work with.

Compiler theory has come a long way since the 1960s when Lisp was invented, and while the things it accomplished were impressive for its day, they look rather primitive now. For an example of a modern metaprogramming system, have a look at the (sadly underappreciated) Boo language. Boo is statically typed, object-oriented, and open-source, so every AST node has a type with a well-defined structure that a macro developer can read the code to. The language has a relatively simple syntax inspired by Python, with various keywords that give intrinsic semantic meaning to the tree structures built from them, and its metaprogramming has an intuitive quasiquote syntax to simplify the creation of new AST nodes.

Here's a macro I created yesterday when I realized I was applying the same pattern to a bunch of different places in GUI code, where I would call BeginUpdate() on a UI control, perform an update in a try block, and then call EndUpdate():

macro UIUpdate(value as Expression):
    return [|
        $value.BeginUpdate()
        try:
            $(UIUpdate.Body)
        ensure:
            $value.EndUpdate()
    |]

The macro command is, in fact, a macro itself, one that takes a macro body as input and generates a class to process the macro. It uses the name of the macro as a variable that stands in for the MacroStatement AST node that represents the macro invocation. The [| ... |] is a quasiquote block, generating the AST that corresponds to the code within, and inside the quasiquote block, the $ symbol provides the "unquote" facility, substituting in a node as specified.

With this, it's possible to write:

UIUpdate myComboBox:
   LoadDataInto(myComboBox)
   myComboBox.SelectedIndex = 0

and have it expand to:

myComboBox.BeginUpdate()
try:
   LoadDataInto(myComboBox)
   myComboBox.SelectedIndex = 0
ensure:
   myComboBox.EndUpdate()

Expressing the macro this way is simpler and more intuitive than it would be in a Lisp macro, because the developer knows the structure of MacroStatement and knows how the Arguments and Body properties work, and that inherent knowledge can be used to express the concepts involved in a very intuitive way. It's also safer, because the compiler knows the structure of MacroStatement, and if you try to code something that isn't valid for a MacroStatement, the compiler will catch it right away and report the error instead of you not knowing until something blows up on you at runtime.

Grafting macros onto Haskell, Python, Java, Scala, etc isn't difficult because these languages aren't homoiconic; it's difficult because the languages are not designed for them, and it works best when your language's AST hierarchy is designed from the ground up to be examined and manipulated by a macro system. When you're working with a language that was designed with metaprogramming in mind from the beginning, macros are much simpler and easier to work with!

  • 4
    Joy to read, thank you! Do non-Lisp macros stretch as far as changing syntax? Because one of the strength of Lisp is the syntax is all the same, thus it is easy to add a function, conditional statement, whatever because they are all the same. While with non-Lisp languages one thing differs from another -- if... does not look like a function call for example. I don't know Boo, but imagine Boo didn't have pattern matching, could you introduce it with its own syntax as macro? My point is -- any new macro in Lisp feels 100% natural, in other languages they work, but you can see the stitches. – greenoldman Feb 23 '15 at 7:20
  • 4
    The story as I have always read it is a bit different. An alternative syntax to s-expression was planned but work on it was delayed because programmers had already started to use s-expressions and found them convenient. So the work on the new syntax was eventually forgotten. Can you please cite the source that indicates the shortcomings of compiler theory as the reason for using s-expressions? Also, the Lisp family kept evolving for many decades (Scheme, Common Lisp, Clojure) and most dialects decided to stick to s-expressions. – Giorgio Feb 23 '15 at 7:58
  • 5
    "simpler and more intuitive": sorry, but I don't see how. "Updating.Arguments[0]" is not meaningful, I'd rather have a named argument and let the compiler check itselfs if the number of arguments matches: pastebin.com/YtUf1FpG – coredump Feb 23 '15 at 10:09
  • 8
    "From a performance perspective, this is a much simpler task; many high-level language compilers spend 75% or more of their time on parsing." I would've expected looking for and applying optimizations to take up most of the time (but I've never written a real compiler). Am I missing something here? – Doval Feb 23 '15 at 12:53
  • 5
    Unfortunately your example does not show that. It's primitive to implement in any Lisp with macros. Actually this is one of the most primitive macros to implement. This makes me suspect that you don't know much about macros in Lisp. "Lisp's syntax is stuck in the 1960s": actually macro systems in Lisp have made a lot of progress since 1960 (In 1960 Lisp did not even have macros!). – Rainer Joswig Feb 23 '15 at 19:53
3

I'm learning Scheme from the SICP and I'm getting the impression that a big part of what makes Scheme and, even more so, LISP special is the macro system.

How so? All the code in SICP is written in macro-free style. There are no macros in SICP. Only in a footnote on page 373 are macros ever mentioned.

But, since macros are expanded at compile-time

They aren't necessarily. Lisp provides macros in both interpreters and compilers. Thus there might not be a compile-time. If you have a Lisp interpreter, macros are expanded at execution time. Since many Lisp systems have a compiler on board, one can generate code and compile it at runtime.

Let's test that using SBCL, a Common Lisp implementation.

Let's switch SBCL to the Interpreter:

* (setf sb-ext:*evaluator-mode* :interpret)

:INTERPRET

Now we define a macro. The macro prints something when it is called for code expanded. The generated code does not print.

* (defmacro my-and (a b)
    (print "macro my-and used")
    `(if ,a
         (if ,b t nil)
         nil))

Now let's use the macro:

MY-AND
* (defun foo (a b) (my-and a b))

FOO

See. In above case Lisp does nothing. The macro is not expanded at definition time.

* (foo t nil)

"macro my-and used"
NIL

But at runtime, when the code is used, the macro is expanded.

* (foo t t)

"macro my-and used"
T

Again, at runtime, when the code is used, the macro is expanded.

Note that SBCL would expand only once when using a compiler. But various Lisp implementations also provide interpreters - like SBCL.

Why are macros easy in Lisp? Well, they aren't really easy. Only in Lisps, and there are many, which have macro support built in. Since many Lisps come with extensive machinery for macros, it looks like it is easy. But macro mechanisms can be extremely complicated.

  • I've been reading a lot about Scheme around the web as well as reading SICP. Also, aren't Lisp expressions compiled before they're interpreted? They at least must be parsed. So I guess "compile-time" should be "parse-time". – Elliot Gorokhovsky Feb 24 '15 at 0:27
  • @RenéG Rainer's point, I believe, is that if you eval or load code in any Lisp language, macros in those will get processed too. Whereas if you use a preprocessor system as proposed in your question, eval and the like won't benefit from the macro expansion. – Chris Jester-Young Feb 24 '15 at 16:49
  • @RenéG Also, "parse" is called read in Lisp. This distinction is important, because eval works on actual the list data structures (as mentioned in my answer), not on the textual form. So you can use (eval '(+ 1 1)) and get back 2, but if you (eval "(+ 1 1)"), you get back "(+ 1 1)" (the string). You use read to get from "(+ 1 1)" (a string of 7 characters) to (+ 1 1) (a list with one symbol and two fixnums). – Chris Jester-Young Feb 24 '15 at 16:52
  • @RenéG With that understanding, macros do not work at read-time. They work at compile-time in the sense that if you have code like (and (test1) (test2)), it will get expanded into (if (test1) (test2) #f) (in Scheme) just the once, when the code is loaded, rather than each time the code is run, but if you do something like (eval '(and (test1) (test2))), that will compile (and macro-expand) that expression appropriately, at runtime. – Chris Jester-Young Feb 24 '15 at 17:01
  • @RenéG Homoiconicity is what allows Lisp languages to eval on the list structures instead of the textual form, and for those list structures to be transformed (via macros) prior to execution. Most languages' eval works on text strings only, and their capabilities for syntax modification are much more lacklustre and/or cumbersome. – Chris Jester-Young Feb 24 '15 at 17:13
1

Homoiconicity makes it much much easier to implement macros. The idea that code is data and data is code makes it possible to more or less (barring accidental capture of identifiers, solved by hygienic macros) to freely substitute one for the other. Lisp and Scheme make this easier with their syntax of S-expressions which are uniformly structured and thus easy to turn into ASTs which form the basis of Syntactic Macros.

Languages without S-Expressions or Homoiconicity will run into trouble implementing Syntactic Macros though it can still certainly be done. Project Kepler is attempting to introduce them to Scala for instance.

The largest issue with syntax macros usage aside from non-homoiconicity, is the issue of arbitrarily generated syntax. They offer tremendous flexibility and power but at the price that your source code may no longer be as easy to understand or maintain.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.