Do macros require compilation?

[luserdroog]

I was reading in the documentation for PicoLisp and came across
a statement that PicoLisp does not have macro /because/ it does
not compile. "No compiler -- no macros!"

Is this "true" generally? Are there no pure interpreters which
implement macros? Is is weird or difficult or clunky for those
that do if it's rare?

I have an idea that I can implement macros in my interpreter by
adding FEXPRs, assuming I can figure out how to implement them.
First challenge is that I don't have property lists for atoms.
So either I add those first or make FEXPRs some other way.
Do that sound reasonable?

Any other thoughts or advice I should consider in my little
lisp interpreter project?

Code has been updated to be more shorter and more functional.
https://github.com/luser-dr00g/sexp.c/blob/master/sexp.c
Turning some attention to the actual user language now.

[Jeff Barnett]

Whether and how you do macros in an interpretive system has a lot to do
with how you value consistency versus speed. Here are a few issues to
consider:

1. Is there a guarantee as to what environment the macro expansion
operates in? For example, if the expansion calls a function, how is that
call resolved or if the expansion references a special (or non special
variable), how is the binding found? In fact how do you determine if the
reference is to a special or other binding?

2. If the answer to 1 is in some constant or near constant environment,
you may associate the expansion with the form that was expanded using,
for example a hash table. So you can look up the expansion which you
only do once.

3. Can Lisp code be mutated by the running program? If so, you can't use
an EQ hash table in 2 above. Even the form operator can be changed by
mutation.

4. If mutation is possible and you don't use a hash table, e,g,, you
store the macro in place of the original code, there are other problems,
e.g., mutation is now to the expanded.

5. If expansion is dependent on the local environment (see 1 above and
think about MACROLET), two forms EQ or even EQUAL may have different
expansions. Then the idea of using a hash table (see 2 above) really
goes to hell unless you can encode context in the key along with the
form.

6. ETC.

In short, it's a really good idea to either completely specify the
expansion rules, including context, in your implementation or put (very
well written) contextual constraints on what can and what cannot be
expanded consistently and predictably.

You must also decide if interpretive and compiled code should have
identical semantics. In a few Lisps I implemented many years ago, EVAL
called the compiler, ran the fragment, then marked the compiled chunk
for GC.
--
Jeff Barnett

[Kaz Kylheku]

On 2019-01-31, luserdroog <mij...@yahoo.com> wrote:
> I was reading in the documentation for PicoLisp and came across
> a statement that PicoLisp does not have macro /because/ it does
> not compile. "No compiler -- no macros!"
>
> Is this "true" generally? Are there no pure interpreters which
> implement macros? Is is weird or difficult or clunky for those
> that do if it's rare?

There are Lisps that both interpret and compile that consistently
use macros for both situations.

There are Lisps that were AST-interpreted and had macros, before
becoming compiled. For instance GNU Emacs Lisp had macros before
Zawinski developed the byte compiler.

My TXR Lisp had macros for quite a number of years before I developed a
compiler and VM for it. The interpreter is critically required by the
implementation; the compiler won't bootstrap without it. And the
compiler is written using the full macro system, so it cannot be
interpreted without macros.

CLISP is a CL implementaton that has an interpreter. It also bootstraps
using that interpreter. Functions are interpreted by default and must be
explicitly compiled, or COMPILE-FILE must be used. Its LOAD function
has a compiling mode.

Implementing an expansion pass in an interpreter, even though
it may be motivated by macros, will prove beneficial.

For instance, the following diagnostic come from the code walker that
performs macro expansion:

This is the TXR Lisp interactive listener of TXR 208.
Quit with :quit or Ctrl-D on empty line. Ctrl-X ? for cheatsheet.
1> (defun a (x)
(+ x y))
** warning: (expr-1:2) unbound variable y

The code isn't compiled; we didn't do (compile 'a).

In an interpreter without macros, there would be no expansion pass, and
so the opportunity for this kind of static check wouldn't arise.

The opportunity arises from the fact that the macro system supports
local macros (both symbol and operator macros), and so the expander
performs a detailed code walk that passes down information about the
lexical scope. It knows that x has a binding, but y doesn't.

The expander can perform some small optimizations also, like reducing
progn forms that contain trivial side-effect-free forms:

2> (expand '(progn 1 2 3 4 5))
5

An expander can easily do simple source-level optimizations like
arithmetic strength reduction, constant folding and dead code
elimination, which do benefit interpretation. Of course, compilation is
best for speed, but if all you have is interpretation, faster is better
than slower, nonetheless.

Macros are superior to fexprs for extending the language, because
a reduction from some new syntax to an existing syntax that is known
to be well implemented is easier to validate than a new fexpr.
We can inspect what the macro is doing without running the
program which uses the macro.

A fexpr can use another fexpr as a subroutine, thereby providing
syntactic sugar around that target fexpr; but that has to be debugged by
running instances of the syntax.

I would argue that if a fexpr massages its input syntax and calls
another fexpr, that fexpr "wants" to be macro. If the fexpr massages the
input syntax in a fixed way, it's basically wasting time doing the
equivalent of macro expansion on each call. Such a situation shows that
even in a fexpr-based environment, macros would in fact be beneficial;
a macros can then be thought of as a staged pre-computation of what
would be a fexpr.

[Robert Munyer]

If your interpreter processes function definitions through some kind
of code walker before saving them, I'd say that adding macros would be
an all-around win.

If your interpreter doesn't pre-process function definitions at all,
macros will have a tendency to save human time but waste computer time,
because individual macro expressions will be expanded more than once.

I used such an interpreter before Common Lisp, and it was accepted
practice to write macros that used RPLACA and RPLACD to mutate their
own callers' source code to prevent repeated expansion!

Kaz Kylheku wrote:
> On 2019-01-31, luserdroog <mij...@yahoo.com> wrote:

>> Is this "true" generally? Are there no pure interpreters which
>> implement macros?

Not true. You can add macros to one of McCarthy's tiny LISP
interpreters from the 1960s, in just a few lines of code, and it's
still a pure interpreter. Try it.

>> Is is weird or difficult or clunky for those
>> that do if it's rare?

Possibly true, depending on how you define "pure". If you believe
that code-walking at function definition time makes an interpreter
impure, then yes, "weird/difficult/clunky" is a fair assessment,
because of the repeated expansion problem that I mentioned above.

> Macros are superior to fexprs for extending the language, because

[snip]

I agree with Mr. Kylheku. You should implement macros.

One consideration that I think no one has mentioned: debugging.
Macros and FEXPRs and built-in special forms all affect debugging,
in different ways.

--
-- Robert Munyer code below generates e-mail address

(format nil "~(~{~a~^ ~}~)" (reverse `(com dot munyer at ,(* 175811 53922))))

[Rob Warnock]

Robert Munyer <rob...@not-for-mail.invalid> wrote:
+---------------

| If your interpreter processes function definitions through some kind
| of code walker before saving them, I'd say that adding macros would be
| an all-around win.
|
| If your interpreter doesn't pre-process function definitions at all,
| macros will have a tendency to save human time but waste computer time,
| because individual macro expressions will be expanded more than once.

+---------------

I know of several implementations, both Scheme & CL, which don't
do any pre-processing of function definitions at definition time
(execution of the DEFINE/DEFUN) except store the source, but rather
delay the pre-processing until the first use/call of the function.
This can significantly speed up interactive or "scripting"-type
applications where you might have a large number of functions in a
file, only a subset of which are used in any one run of the program.

On the other hand, since you really need to do a full code-walk of
CL code at *some* point before executing any of it -- if only to
separate lexical variables from dynamic variables declared *after*
first use [hint: formal parameters], doing macro expansion *once*
during the code walk is a "freebie", more or less.

+---------------

| I used such an interpreter before Common Lisp, and it was accepted
| practice to write macros that used RPLACA and RPLACD to mutate their
| own callers' source code to prevent repeated expansion!

+---------------

ISTR that ANSI CL explicitly forbids this. Let's see... Oh, yes:

3.1.2.1.2.2 Macro Forms
...
The consequences are undefined if a macro function
destructively modifies any part of its form argument.
...
The following X3J13 cleanup issue, not part of the
specification, applies to this section:
* SELF-MODIFYING-CODE:FORBID

Note that the latter issue cross-references a similar issue
with compiler macros:

3.2.2.1.1 Purpose of Compiler Macros
...
The consequences are undefined if a compiler macro function
destructively modifies any part of its form argument.


-Rob

-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <http://rpw3.org/>
San Mateo, CA 94403

[Barry Margolin]

In article <q367dr$6co$1...@dont-email.me>, rp...@rpw3.org (Rob Warnock)
wrote:

> Robert Munyer <rob...@not-for-mail.invalid> wrote:

>
> +---------------

> | I used such an interpreter before Common Lisp, and it was accepted
> | practice to write macros that used RPLACA and RPLACD to mutate their
> | own callers' source code to prevent repeated expansion!
> +---------------

I also remember that practice. In MacLisp there was a function called
DISPLACE that was something like:

(defun displace (destination source)
(setf (car destination) (car source)
(cdr destination) (cdr source))
source)

And I think there was a DEFMACRO-DISPLACE macro that was like DEFMACRO,
but automatically displaced the original call.

>
> ISTR that ANSI CL explicitly forbids this. Let's see... Oh, yes:

MacLisp had no such restriction. Common Lisp is generally compiled, so
it's not necessary. We didn't bother worrying about efficiency in
non-compiled implementations.

--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

[luserdroog]

On Thursday, January 31, 2019 at 1:00:12 AM UTC-6, Kaz Kylheku wrote:

> I would argue that if a fexpr massages its input syntax and calls
> another fexpr, that fexpr "wants" to be macro. If the fexpr massages the
> input syntax in a fixed way, it's basically wasting time doing the
> equivalent of macro expansion on each call. Such a situation shows that
> even in a fexpr-based environment, macros would in fact be beneficial;
> a macros can then be thought of as a staged pre-computation of what
> would be a fexpr.

Thanks for all the insights everyone. Of course my temperament is such
that I've already veered off on another tangent. I will re-read the
messages in this thread in more detail before proceeding further with
either macros or $vau. For the present, I've made some headway implementing
parser combinators in postscript. The code for that (very "lispy" postscript
IMO) has been posted in comp.lang.postscript.