Python syntax in Lisp and Scheme (macro tangent)

[Matthew Danish]

On Mon, Oct 06, 2003 at 10:19:46AM +0000, gregm at cs.uwa.edu.au wrote:
> In comp.lang.functional Marco Baringer <mb at bese.it> wrote:
> : gregm at cs.uwa.edu.au writes:
> :> Really? Turing-completeness and all that... I presume you mean "cannot
> :> so easily be added as functions", but even that would surprise me.
> 
> : well you can pass around code full of lambdas so most macros (expect
> : the ones which perform hairy source transformations) can be rewritten
> : as functions, but that isn't the point. Macros are about saying what
> : you mean in terms that makes sense for your particular app.
> 
> OK, so in some other application, they might allow you to extend the
> syntax of the language to encode some problem domain more naturally?

Right.

> 
> :> OK, that's _definitely_ just a filter:
> : no it's not, and the proof is that it wasn't written as a filter.
> 
> He was saying that this could not be done in Python, but Python has
> a filter function, AFAIK.

He meant the way it was expressed.  Java can ``do'' it too, but it's not
going to look as simple.

> 
> : For whatever reason the author of that snippet decided that the code
> : should be written with WITH-COLLECTOR and not as a filter, some
> : languages give you this option, some don't, some people think this is
> : a good thing, some don't.
> 
> Naturally. I'm against extra language features unless they increase
> the expressive power, but others care more for ease-of-writing and
> less for ease-of-reading and -maintaining than I do.

Then you should like macros, because ease-of-reading and -maintaining is
precisely why I use them.  Like with functions, being able to label
common abstractions is a great maintainability boost.

You don't write ((lambda (x) ...) 1) instead of (let ((x 1)) ...), right?

> :> : DO-FILE-LINES and WITH-COLLECTOR are macros, and they can't be implemented
> :> : any other way because they take variable names and code as arguments.
> :> What does it mean to take a variable-name as an argument? How is that
> :> different to taking a pointer? What does it mean to take "code" as an
> :> argument? Is that different to taking a function as an argument?
> : You are confusing the times at which things happen. A macro is
> : expanded at compile time,
> 
> OK, yep. It should have occurred to me that that was the difference.
> So now the question is "what does that give you that higher-order
> functions don't?".
> : Another trivial example:
> : <IF-BIND>
> 
> : Macros allow me to say what I _mean_, not what the compiler wants.
> 
> Interesting. It would be interesting to see an example where it allows
> you to write the code in a less convoluted way, rather than the three
> obfuscating (or would the non-macro Lisp versions be just as obfuscated?
> I know Lisp is fine for higher-order functions, but I guess the IF-BIND
> stuff might be hard without pattern-matching.) examples I've seen so far.

Here's an example that I am currently using:

(definstruction move ((s register) (d register))
  :sources (s)
  :destinations (d)
  :template "movl `s0, `d0"
  :class-name move-instruction)

1. This expands into a 
     (defmethod make-instruction-move ((s register) (d register)) ...)
   which itself is called indirectly, but most importantly it allows the
   compiler to compile a multiple-dispatch method statically rather than
   trying to replicate that functionality at runtime (which would require
   parsing a list of parameters supplied by the &rest lambda-list keyword,
   not to mention implementing multiple-dispatch).

2. Sources and destinations can talk about variable names rather than indices
   into a sequence.  (Templates cannot because they need the extra layer of
   indirection--the source and destination lists are subject to change in
   this system currently.  Well, I suppose it could be worked out anyway,
   perhaps if I have time I will try it).

3. Originally I processed the templates at run-time, and upon profiling
   discovered that it was the most time-consuming function by far.  I modified
   the macro to process the template strings statically and produce a
   function which could be compiled with the rest of the code, and the
   overhead completely disappeared.  I can imagine a way to do this with
   functions: collect a list of functions which take the relevant values
   as arguments, then map over them and apply the results to format.
   This is less efficient because
     (a) you need to do some extra steps, which the macro side-steps by
         directly pasting the code into the proper place, and
     (b) FORMATTER is a macro which lets you compile a format string into
         a function, and this cannot be used in the functional version,
         since you cannot say (FORMATTER my-control-string) but must supply
         a string statically, as in (FORMATTER "my control string").
         Could FORMATTER be implemented functionally?  Probably, but either
         you require the use of the Lisp compiler at run-time, which is
         certainly possible though heavyweight usually, or you write a 
         custom compiler for that function.  If you haven't figured it out
         yet, Lispers like to leverage existing resources =)

4. The macro arranges all the relevant information about a machine instruction
   in a simple way that is easy to write even if you don't understand
   the underlying system.  If you know anything about assembly language,
   it is probably pretty easy to figure out what information is being encoded.


Here's another fun macro which I've been using as of yesterday afternoon,
courtesy of Faré Rideau:

(match s
  ...
  ((ir move (as temp (ir temp _)) b)
    (reorder-stm (list b)
                 (mlambda ((list b) ;; match + lambda
                           (make-ir-move temp b)))))
  ...)

MATCH performs ML/Erlang-style pattern matching with a Lispy twist: patterns
are of the form: literal, variable, or (designator ...) where designator is a
symbol specified by some defining construct.

I wrote this to act like the ML `as' [meta-?]pattern:

(define-macro-matcher as
    ;; I think this lambda should be folded into the macro, but whatever
    #'(lambda (var pat)
        (multiple-value-bind (matcher vars)
            (pattern-matcher pat)
          (values `#'(lambda (form)
                       (m%and (funcall ,matcher form)
                              (setf ,var form)))
                  (merge-matcher-variables (list vars (list var)))))))

for example, which at macro-expansion time computes the pattern-matching code
of the pat argument, adds var to the list of variables (used by MATCH), and
creates a function which first checks the pattern and then sets the supplied
(lexical) variable var to the value of the form at this point the form at this
point.  Calling PATTERN-MATCHER yourself is quite enlightening on this:

* (pattern-matcher '(as x 1))
#'(LAMBDA (FORM)
    (M%AND (FUNCALL #'(LAMBDA (#:FORM) (M%WHEN (EQL #:FORM '1))) FORM)
           (SETF X FORM)))
(X)

MATCH (really implemented in terms of IFMATCH) computes this at macro-expansion
and the Lisp statically compiles it afterwards.  Of course, MATCH could be
implemented functionally, but consider the IR matcher that
  (a) looks up the first parameter in a table (created by another macro) to
      see if it is a valid IR type and get the slot names
  (b) which are used to create slot-accessing forms that can be optimized
      by a decent CLOS implementation when the slot-name is a literal value
      (as when constructed by the macro, something a functional version
      could not do).

Not to mention that a functional version would have to look something like:

(match value
       '(pattern involving x, y, and z) #'(lambda (x y z) ...)
       ... ...)

Rather annoying, don't you think?  The variables need to be repeated.
  
The functional version would have to create some kind of structure to hold the
bound variable values and construct a list to apply the consequent function
with.  The macro version can get away with modifying lexical variables.

Also the macro version can be extended to support multiple value forms, which
in Lisp are not first-class (but more efficient than returning lists).


A third quick example:

(ir-sequence
  (make-ir-move ...)
  (make-ir-jump ...)
  ...)

Which transforms a list of values into a list-like data structure.  I wrote
this originally as a macro, because in my mind it was a static transformation.
I realized later that it could be implemented as a function, without changing
any uses, but I didn't because
  (a) I wasn't using it with higher-order functions, or situations demanding
      them.
  (b) It would now have to cons a list every call and do the transformation;
      added overhead and the only gain being that it was now a function which
      I never even used in a functional way.  Rather questionable.
  (c) I can always write a separate functional version if I need it.


Basically, this boils down to:

* Macros can do ``compile-time meta-programming'' or whatever the buzzword
  is these days, and those above are some real-life examples.
  This allows for compiler optimization and static analysis where desired.
* Macros make syntax much more convenient and less cluttered.  I really
  don't understand the people who think that macros make things harder to read.
  It is far better to have clear labelled markers in the source code rather
  than having to sort through boilerplate to figure out the intended meaning
  of code.  Just because I understand lambda calculus doesn't mean I want to 
  sort through nested lambdas just to use some functionality, every time.
  If you are afraid because you are unsure of what the macro does, or its
  complete syntax, MACROEXPAND-1 is your friend.  That, and an editor with
  some hot-keys to find source/docs/expansion/etc.

-- 
; Matthew Danish <mdanish at andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."