Lisp Macros, Delayed Evaluation and the Evolution of Smalltalk

Lisp user here. I'll chime in with another example of using macros for more than just delaying evaluation.

I wrote a library called Chancery[1] for procedurally generating strings (and other data). It's inspired by Tracery[2] but takes advantage of macros to make it easier to read and feel more like part of the language. I use it to write stupid Twitter bots like https://twitter.com/git_commands and https://twitter.com/rpg_shopkeeper for fun.

As an example let's say we want to generate a message about the loot we receive from a monster in a fantasy, D&D-style story. Maybe we'll start with some random weapons:

    (chancery:define-string weapon-type
      "sword"
      "spear"
      "lance"
      "flail"
      "mace")

    (weapon-type) ; => "mace"
    (weapon-type) ; => "sword"

This expands like so:

    (macroexpand-1
      '(chancery:define-string weapon-type
        "sword"
        "spear"
        "lance"
        "flail"
        "mace"))
    ; =>
    (DEFUN WEAPON-TYPE ()
      (CASE (CHANCERY::CHANCERY-RANDOM 5)
        (0 "sword")
        (1 "spear")
        (2 "lance")
        (3 "flail")
        (4 "mace")))

This simple case actually could be done just by delaying evaluation, as long as we get every body clause as a separate thunk. Now let's define a rule for generating the material of a weapon:

    (chancery:define-string (weapon-material :distribution :weighted)
      (100 "iron")
      (40 "steel")
      (5 "silver")
      (4 "gold")
      (1 "adamantine"))

This will generate the materials according to a weighted distribution, and macroexpands to:

    (DEFUN WEAPON-MATERIAL ()
      (CASE (CHANCERY::WEIGHTLIST-RANDOM #)
        (0 "iron")
        (1 "steel")
        (2 "silver")
        (3 "gold")
        (4 "adamantine")))

This case needs more than just delayed evaluation. If you receive `(100 "iron")` as an opaque thunk, where all you can do is evaluate it, there's no way to pull out the weight and body components.

If we add a few more rules, we can see more cases where we need to go beyond delayed evaluation:

    (defun currency-amount ()
      (+ 10 (random 100)))

    (chancery:define-string (currency-type :distribution :zipf)
      "copper"
      "silver"
      "gold"
      "platinum")

    (chancery:define-string loot
      #((weapon-material weapon-type) chancery:a)
      (currency-amount currency-type "coins"))

    (chancery:define-string discovery
      ("You open the chest and find" loot :. ".")
      ("You find" loot "in the monster's hidden stash.")
      ("You find nothing but dust and cobwebs."))

    (discovery) ; => "You find nothing but dust and cobwebs."
    (discovery) ; => "You find an iron sword in the monster's hidden stash."
    (discovery) ; => "You find 61 copper coins in the monster's hidden stash."
    (discovery) ; => "You open the chest and find a steel sword."

Macroexpanding the last one:

    (DEFUN DISCOVERY ()
      (CASE (CHANCERY::CHANCERY-RANDOM 3)
        (0 (CHANCERY::JOIN-STRING "You open the chest and find"
                                  (PRINC-TO-STRING #\ )
                                  (LOOT)
                                  "."))
        (1 (CHANCERY::JOIN-STRING "You find"
                                  (PRINC-TO-STRING #\ )
                                  (LOOT)
                                  (PRINC-TO-STRING #\ )
                                  "in the monster's hidden stash."))
        (2 (CHANCERY::JOIN-STRING "You find nothing but dust and cobwebs."))))

Here we can see the macro walking the lists and doing different things to each element: strings are included raw, symbols are turned into function calls, and the special keyword :. suppresses the usual joining space character inserted between everything. There's also some special handling of vectors, in the LOOT example, which I won't go into. This is more than just delayed evaluation — we're inspecting the actual structure of the code received by the macro at macroexpansion time. If all we had were an opaque thunk that we could evaluate later, we couldn't do this.

Delayed evaluation is enough for certain kinds of abstraction, like writing basic control structures, but isn't as powerful as full macros. Macros let you transform arbitrary code into other arbitrary code using the full power of the language.

[1]: https://sjl.bitbucket.io/chancery/ [2]: http://tracery.io/

Sounds very related to "shadow languages" ( https://gbracha.blogspot.com/2014/09/a-domain-of-shadows.htm... ) where we add a feature to our language in a very limited form, e.g. imports; then we end up wanting that feature to be a little more powerful, so we add some special case for that, e.g. conditional imports; then we want to use that feature some other way, so we add support for that, e.g. renaming imports; etc.

We end up with a language that has a complicated, limited, special-purpose second-language built in just to handle that feature.

The alternative is to try implementing the feature using existing facilities right from the start, e.g. making imports first-class values that can use the language's own conditionals, variable names, etc. for imports.

We can also go one step further and rather than just trying to re-use the existing language features as they are (e.g. conditionals, variables, etc.), we can ask what new feature could we use to build both the new functionality and the old functionality. That way, rather than e.g. using the built-in conditionals to implement conditional imports, we might decide to something more powerful than both, like macros, and use macros to implement conditional imports and replace the built-in conditionals :)

Considering the username of the person you are replying to, you might consider that they are very likely to have implemented macros in a lisp.

In common lisp, defining a macro defines a function that receives as its arguments the unevaluated forms passed to it plus (optionally) the lexical environment. This part is indeed "essentially a lambda without argument evaluation."

The magic isn't there, the magic is in the interpretation of the value it returns. It can return any arbitrary lisp forms. This allows macros to do far more than just delay evaluation. Pretty much anything that involves code walking is not possible with lambdas, for example. Some setf expanders would be impossible with lambdas as well.

In Lisp an interpreter means something slightly different: it means an interpreter for s-expressions. It's not about a virtual machine interpreter or similar.

A Lisp interpreter runs directly the s-expressions. This is independent from the idea of evaluation. Evaluation could be implemented by an interpreter or by a compiler.

For example using an interpreter:

  CL-USER 32 > (defun fak (n)
                 (if (zerop n)
                     1
                     (* n (fak (1- n)))))
  FAK

Let's break into the function if the argument N is 0:

  CL-USER 33 > (trace (fak :break (eql (first *traced-arglist*) 0)))
  (FAK)

  CL-USER 34 > (fak 5)
  0 FAK > ...
    >> N : 5
    1 FAK > ...
      >> N : 4
      2 FAK > ...
        >> N : 3
        3 FAK > ...
          >> N : 2
          4 FAK > ...
            >> N : 1
            5 FAK > ...
              >> N : 0

  Break on entry to FAK with *TRACED-ARGLIST* (0).
    1 (continue) Return from break.
    2 Continue with trace removed.
    3 Continue traced with break removed.
    4 Continue and break when this function returns.
    5 (abort) Return to top loop level 0.

  Type :b for backtrace or :c  to proceed.
  Type :bug-form "" for a bug report template or :? for other options.

  CL-USER 35 : 1 > :bq

  FAK  :n
  Interpreted call to FAK

  CL-USER 37 : 1 > :lambda
  (LAMBDA (N) (DECLARE (SYSTEM::SOURCE-LEVEL #))
              (DECLARE (LAMBDA-NAME FAK))
              (IF (ZEROP N) 1 (* N (FAK #))))

You see above the actual s-expression being executed for that stack frame. It's not executing any compiled or translated code. It's actually interpreting the source directly without any such step.

If we want, we could inspect, alter it with the usual Lisp functions and continue running.

  CL-USER 39 : 1 > (fifth *)
  (IF (ZEROP N) 1 (* N (FAK (1- N))))

  CL-USER 40 : 1 > (setf (third *) 2)
  2

  CL-USER 41 : 1 > **
  (IF (ZEROP N) 2 (* N (FAK (1- N))))

  CL-USER 42 : 1 > :c 1
            5 FAK 

> I still fail to see what (Common) Lisp runtime gives over JVM

More efficient data representation, more efficient execution, saving and loading of images, tailored GCs, mixing compiled and interpreted (see above) Lisp code, deeper runtime inspection, resumeable exceptions, efficient stack traces, efficient function calls, fast startup times, etc etc.

Something like Lisp, which may have a bunch of very dynamic parts, is hard to implement efficiently on the JVM. Clojure is designed to map better to the JVM.