Re: Runtime macros

Randall Randall wrote:

I've heard talk occasionally about "first class macros" in this newsgroup,
and in other places around the Lisp world, such as Paul Graham's essays
regarding Arc.  Since other people have complained that macros in Common
Lisp are already first class, I wonder what term they would like us to
use for macros that may be passed around as functions may be and used in
that way?  Perhaps "runtime macro"?


Ummm, I went down that path a few years ago, and started implementing
things.  What with one thing and another, once you decide you want
truly first-class macros, if you keep pushing, I think you inevitably
wind up with no macros at all - just a radically extended function
call semantics that allows first-class functions to do any of the
things that CL or scheme use macros for.

Certainly that's what happened with my toy-lisp.  I won't bore you
with all the details of how it's evolved from the time I was just
trying to make better macros, but what I've currently got has
lazy calling semantics (in that promises are passed instead of
computed arguments).

The macrology-like aspects of function calls happen because the
promises are transparent objects.  You can use accessors on them
to get the literal form that's being evaluated, or the environment
in which the form is scoped.  So you can pass an "invalid" call
to a function as an argument (for example a cond clause) and if
it unpacks the forms, manipulates them into shape using runtime
code, and then calls eval on its computed forms with the argument
environment, the "invalid" call never gets evaluated and the macro-
ish magic happens instead.

Ordinary functions just evaluate their arguments from left to
right before continuing; but functions can be defined using
extra syntax in the lambda list with args (promises) they
don't evaluate, and use accessors on those to get the literal
forms of the arguments and environments of each argument, and
do any arbitrary thing with them.

When I first got it running it was doing the code manipulations
and "interpreting" every time a function that used it was called,
and I still have to generate code that does everything "the hard
way" so I can fall back to it if the optimizations' runtime
constraints are violated. But for a lot of cases, (ie, "sane
use") the runtime constraints are never violated and I never
have to fall back on the unoptimized versions.

The system inlines and constant-propagates fairly aggressively,
and as long as nobody mutates source code, inlining and
constant propagation gets you a long way toward not having to
do the code manipulations on each call.  But the minute somebody
assigns to source code (appending a quoted list from source for
example) I have to throw out everything that depended on the
constant-sourcecode constraint and fall back on the unoptimized
versions.  That's a major pain, btw; it may get better if I
find a way to keep track of *which* source code is mutated and
don't worry about stuff that's not reachable from the argument
forms. But then I wind up doing reachability checks for every
macro use whenever source code is mutated, and that's also a
major pain.

Other than that, what's still expensive are the dynamic cases:
If the system can't prove that a variable is "pure" (ie, never
mutated) then when that variable is called as a function, no
optimized forms are used.  Likewise when functions are called
from higher-order functions or the argument forms are dynamically
computed.

And, unfortunately, I haven't got any optimizations working
at all across module boundaries.  I've tried several times and
I'm still working on figuring out why it always messes up.  I'm
pretty sure its a solvable problem, but I haven't solved it yet.

Anyway, the short version of the story is, it's working and it's
pretty cool -- but it's only cheap in the same cases that ordinary
macros are cheap.  Get outside those bounds and you watch all your
work of optimizing wind up in the toilet.

While I've read that runtime macros would be a problem to implement for
the compiler writer, it seems to me that it carries only the same
problems as having EVAL in the language.


It's considerably more pervasive than that.  In any case where
you can't know whether a given function has "standard" or "extended"
semantics, you can't make optimizations that depend on one or
the other.  And that means all the interesting cases. it makes
higher-order functions, closures, and functions stored in structures
substantially more expensive to call, and motivates me to build
multiple executable versions of the same function; one that I can
keep calling as long as none of its constraints are violated, and
one that I fall back to the minute the optimized form becomes
invalid.

In any case, if we had runtime
macros, an interesting further development of that would be if we
allowed macros to determine if they were replaced by their result in the
way that CL macros are now. 

Been there, did that.  Mutable source code.  Not a good idea.
Use lazy semantics instead and let the macros get their arg
forms through promise accessors and work with explicit calls
to eval using the caller environment. Much cleaner, but still
messy as all getout.

I don't know if this has been done in a Lisp before. If so, could someone
point me in the direction of the Lisp in question? 

Well, aside from the toy system I've got, which is not ready for
primetime, you could look at 3-Lisp, which I've only recently
been pointed at myself.

If not, you may be
wondering why someone would want that.  In CL, you can put declarations
in the source to assist the compiler in creating optimized code.  Such
declarations clutter the code a lot, often mostly obscuring the actual
algorithm, and it would be nice to have a perfectly intelligent compiler
that always knew what kind of type would result from evaluating any form
or symbol (for those cases where the type didn't vary from run to run;


Um.  Haven't touched that; the toy system is "unityped" so far.
However, your idea is pretty darned ambitious.  I think one of
the only ways to do it is to provide alternate execution paths
for your "optimized" code and for situations that don't match
its assumed entry conditions in terms of types.  So in a case where
foo calls baz and bar, and baz and bar both call foobar and foobaz,
you could have a version of foo that you call if all three of its
arguments are integers, which then calls the integer versions of
baz and bar, which in turn call the integer versions of foobaz and
foobar, all with no further typechecks. But you'd also need a unitype
version of foo that gets called if a particular foo-call doesn't
qualify for the optimized treatment, and it would need more general
forms of baz and bar with typechecks, etc.

No doubt I'll quickly be informed if my rambling doesn't make sense... :) 

It makes sense... but it's a long road.  And it can work, but it
still sounds like you've got some pretty woolley ideas about how
and are likely to be disappointed to some extent by the harsh
and even probabilistic/heuristic realities.

The only way I've been able to get anywhere in terms of optimizing
this stuff is to just "assume" the best, but keep the unoptimized
versions around in case some dynamic situation violates the
assumptions so you can fall back on it.  There are multiple
versions of every function, source forms still in the system at
runtime, and lots of code that checks constraint integrity so I
can tell which versions to use.  When it works out it's nice, but
in the worst case, it's no faster than interpreted code (and in
fact somewhat slower because of the baroque function call semantics
and the fact that it keeps spending effort keeping track of
constraints and *trying* to get a grip on some optimizations it
can make...).

A few weeks ago I redefined 'cons' while a program was running,
replacing it with a "special" function that doesn't force its
second argument (good for making lazy structures, etc).  'cons'
is inlined everywhere, and there's a list of optimized functions
to invalidate a mile long attached to the binding.  So when the
binding changed, it went down the list invalidating every
compiled function that inlined cons, and the system ground
to a near-halt for several minutes as it tried to continue the
program using the "fallback" versions, and interleaved that
with recompiling everything.  (function calls to unoptimized
functions trigger recompilation/reoptimization of that function
stochastically, about every tenth call...).  All the compilation
work done up to that point, went down the toilet.  And to make
this work, you just have to be okay with throwing a lot of CPU
cycles down the toilet and starting over when somebody violates
a constraint like that.

				Bear

.

Relevant Pages

  • Re: Macro that expand differently depending on the function calling it.
    ... different implementation dependent optimizations: MIPS, ... So use two macros. ... mips16 and thumb, dont even bother replying. ... is the place to discus those extensions. ...
    (comp.lang.c)
  • Re: Runtime macros
    ... Since other people have complained that macros in Common ... Lisp are already first class, I wonder what term they would like us to ... the compiler writer, it seems to me that it carries only the same problems as having EVAL in the language. ... you can't make optimizations that depend on one or ...
    (comp.lang.lisp)
  • Re: Improve automatically generated code
    ... And which compiler optimizations will ... optimizations be preferred (e.g. by changing default optimization ... Then make them macros and store them in a .h file, ... On x86 systems, you can generate _asm code "in the raw", without an ...
    (comp.dsp)
  • Re: The lack of a boolean data type in C
    ... The names I chose for my macros make it perfectly clear what ... to do any optimizations specifically designed for bit arrays. ... compiler worry about how best to optimise it. ...
    (comp.lang.c)
  • Re: Data Type Converter
    ... >> in C is done with macros. ... Without such methods the source code ... My primary goal is a C to Delphi converter, ... But there exist no restrictions on the number of back-ends for that converter, ...
    (comp.lang.pascal.delphi.misc)
Loading