Re: Why doesn't Lisp automatically differentiate functions and macros?

hovik <hovik.melikyan@xxxxxxxxx> writes:

I'm in my very early stage of learning Lisp. I'm sure this is not a
new question, but I'd appreciate if you give me some directions on
understanding this. And it's purely theoretical.

So, what stops a Lisp machine from figuring automatically which
function is strictly a run-time function, and which could also be used
at compile-time? In other words, why bother distinguishing macros and
functions when writing programs if it can be done automatically?

It can't be done automatically. What can be done automatically is the very
small subset of things macros can do that you are thinking is all they can
or should do. I bet your error is in thinking the space of things that
you think macros are for is all they are able to do or commonly used for.

In fact, this kind of optimization, if possible at all, may be applied
to some other languages as well.

I think you're thinking of inline functions, which are related to
macros in some ways, but are really a different thing.

First, the compiler is supposed to "know" that any system call (e.g. I/
O, GUI, etc.) has side effects and thus all branches of the code that
invoke a syscall can be marked as run-time only.

This requires the compiler to know how to do things. But no matter how
smart the compiler is, assuming it isn't itself artificially intelligent
(in which case one might ask why it's still earning its money doing menial
tasks like compilation), the compiler is only going to do what the compiler
writer thought to program into it. Whereas Lisp macros leave control in
the hands of the programmer, so that person can always program additional
things that the compiler writer didn't think to, and that the person writing
the macro knows were otherwise left to chance.

Second, those languages that have global data can assume both reading
and writing globals a RT-only operation. Of course a deeper analysis
can be performed and there is a chance that in some situations a
global can be used at compile-time too.

Variable use analysis only barely scratches the surface of what macros
in Lisp can do. Lisp macros are full turing machines, and can do
arbitrary kinds of tasks, not all of which are flow-related. They can
process alternate syntaxes, do "automatic programming", take statistics,
recognize domain-dependent special cases that defy conventional declaration,
accomodate personal style taste that the compiler writer didn't agree with,
and so on.

If neither of these takes place in some branch of code, it can be
safely assumed that a branch can be available both at compile time and
run-time, if necessary.

While there are a certain number of things compilers can prove, there are
always a set of things that only the domain programmer will know and that
are impenetrable to a compiler written without knowledge of the domain code.
Read about the halting problem, for an example of how complicated this
issue is.

Is this correct? Or am I missing something? Maybe something specific
to just Lisp macros?

I would guess you're missing the significance of Lisp macros being
functions from program to program under the control of a Turing machine.
It's quite a bit more dramatic than your analysis, in my estimation.
Work with them for a while. Read some complicated macros, or study their
output. Sit around doing
(PPRINT (MACROEXPAND-1 '(LOOP ...)))
for various valid loops and ask yourself whether the loop syntax you've
chosen could just as well have been supported by automatic compiler analysis.

One useful reference is my 1980 paper on this general topic area:
http://www.nhplace.com/kent/Papers/Special-Forms.html
It's about a different dialect of Lisp than Common Lisp, but I've annotated
it a few places with helpful tips. If you find it incomprehensible in some
place, drop me a line explaining why and I'll add additional annotations.

.