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?
In fact, this kind of optimization, if possible at all, may be applied
to some other languages as well.
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.
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.
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.
Is this correct? Or am I missing something? Maybe something specific
to just Lisp macros?
Thanks,
--
hm
From: Dan Bensen
Subject: Re: Why doesn't Lisp automatically differentiate functions and macros?
Date:
Message-ID: <f0ok5m$l1g$1@wildfire.prairienet.org>
hovik wrote:
> 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?
Because it can't. The only differences between functions and macros
are external, i.e. when they're called and what is and is not evaluated.
On the inside, functions and macros are identical. A macro is just
a function that's called at compile time, whose arguments are not
evaluated, and whose return value is evaluated. There's no way that
can be automatically inferred.
> 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.
> Second, those languages that have global data can assume both reading
> and writing globals a RT-only operation.
No, you can do computation and I/O at compile time:
(defvar x 0)
(defmacro print-incf-x ()
(incf x)
(format t "x = ~D~%" x))
(print-incf-x)
=>
x = 1
> Is this correct? Or am I missing something? Maybe something specific
> to just Lisp macros?
Yes, definitely. No other language has this ability, except maybe Qi,
which is still new and experimental.
--
Dan
www.prairienet.org/~dsb/
From: Kent M Pitman
Subject: Re: Why doesn't Lisp automatically differentiate functions and macros?
Date:
Message-ID: <umz0wyonf.fsf@nhplace.com>
hovik <··············@gmail.com> 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.
On Apr 26, 2:17 am, Kent M Pitman <······@nhplace.com> wrote:
> I would guess you're missing the significance of Lisp macros being
> functions from program to program under the control of a Turing machine.
Just a side note, but they're even more exciting than that, they're
under the control of a full general-purpose programming language. For
example, as part of a series of SQL query generating macros, the
functions called during expansion would (optionally) query the
database and issue compile-time warnings if they found a mismatch
between the query and the schema. Wonderfully useful for refactoring
either side.
From: Harald Hanche-Olsen
Subject: Re: Why doesn't Lisp automatically differentiate functions and macros?
Date:
Message-ID: <pco7irzd7hv.fsf@shuttle.math.ntnu.no>
+ Kent M Pitman <······@nhplace.com>:
| 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),
8)
| 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.
Hmm. Are you really thinking of compiler macros here?
That's one dark corner of CL that I haven't explored yet.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell
From: Kent M Pitman
Subject: Re: Why doesn't Lisp automatically differentiate functions and macros?
Date:
Message-ID: <u3b2nskes.fsf@nhplace.com>
Harald Hanche-Olsen <······@math.ntnu.no> writes:
> + Kent M Pitman <······@nhplace.com>:
>
> | 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),
>
> 8)
>
> | 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.
>
> Hmm. Are you really thinking of compiler macros here?
> That's one dark corner of CL that I haven't explored yet.
Compiler macros are ways of specifically optimizing something with
functional semantics, so that the primary description is functional
and the user can write ways of optimizing extra stuff. A good example
use for compiler macros would be writing a way to optimize a keyword
function into non-keyword calls. I believe CLIM uses (or could use,
if it doesn't) a bunch of this, since it's full of keyword functions
that don't want the overhead of keyword calling at runtime. Or you
might write something that applied algebraic techniques to simplify
certain argument patterns. Compiler macros just provide an extra
degree of oversight, but are theoretically something that if they got
ignored should not change semantics ... unlike regular macros which
are generally not backed up by an alternate implementation. (The
equivalent of a macro backed up by an alternate implementation would
be a "special form". See my "special forms" paper for a discussion of
those. But in CL, there are no user-defined special forms.)
But, that said, compiler macros are probably in the range of things the
OP felt could be inferred automatically, since at least they're talking
about operators with functional semantics.
I really meant regular macros, like LOOP, that could look at a
particular set of loop keywords and decide to compile the loop in a
specific way that was special to that particular combination... something
I doubt many compilers are up to.
Also, whether regular or compiler macros, you might have a special
knowledge in some macro that your function only took even numbers, or
that some function you wrote had commutative arguments, or that the
argument forms must always have no side effects. The compiler can't
"infer" such effects, but since you have program control, you can often
force such implications.
(message (Hello 'hovik)
(you :wrote :on '(25 Apr 2007 13:55:10 -0700))
(
h> So, what stops a Lisp machine from figuring automatically which
h> function is strictly a run-time function, and which could also be used
h> at compile-time? In other words, why bother distinguishing macros and
h> functions when writing programs if it can be done automatically?
because macros are completely different from functions, they are (mostly)
NOT made for efficiency, but for extending functionality.
h> First, the compiler is supposed to "know" that any system call (e.g. I/
h> O, GUI, etc.) has side effects and thus all branches of the code that
h> invoke a syscall can be marked as run-time only.
you'd like to precompute as much as possible?
i think it won't add much performance in real world applications
h> Is this correct? Or am I missing something? Maybe something specific
h> to just Lisp macros?
no, in other languages macros are typically used for extending
functionality, but not for precomputing stuff.
btw, C/C++ compilers precompute stuff quite well (it's easier in C/C++
because of static types), but it has nothing common with macros.
it might be somehow connected with inline functions..
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"I am everything you want and I am everything you need")
hovik <··············@gmail.com> wrote:
+---------------
| 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?
+---------------
First, there are more "times" in Common Lisp than just "run-time" and
"compile time". At a minimum, you also need to consider "read time"
and "macro expansion time". [And it is probably "macro expansion time"
you are really interested in when comparing compilation & executing.]
See at least the following sections of the CLHC for definitions of
and interactions between the various "times" and the various startup,
evaluation, compilation, and run-time environments.
http://www.alu.org/HyperSpec/Body/sec_2-2.html
2.2 Reader Algorithm
http://www.alu.org/HyperSpec/Body/sec_3-2-1.html
3.2.1 Compiler Terminology
http://www.alu.org/HyperSpec/Body/sec_3-2-2-2.html
3.2.2.2 Minimal Compilation
http://www.alu.org/HyperSpec/Body/sec_3-2-2-3.html
3.2.2.3 Semantic Constraints
http://www.alu.org/HyperSpec/Body/sec_3-1-2-1-2-2.html
3.1.2.1.2.2 Macro Forms
http://www.alu.org/HyperSpec/Body/speope_eval-when.html
Special Operator EVAL-WHEN
Note that because the CLHS forbids macro functions from
modifying their argument forms [see Issue SELF-MODIFYING-CODE
<http://www.alu.org/HyperSpec/Issues/iss301-writeup.html>],
many CL implementations perform at least "Minimal Compilation"
[see CLHS 3.2.2.2, above] even on "interpreted" code, so macros
don't have to be re-expanded over & over again in interpreted
loops [or any other code executed more than once].
+---------------
| In other words, why bother distinguishing macros and
| functions when writing programs if it can be done automatically?
+---------------
It can't.
+---------------
| 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.
+---------------
Uh... Common Lisp macro functions *can* do system calls at macro
expansion time!! This might be at compile time or even at read time
[assuming *READ-EVAL* is true]. Macros can read & write files,
make database calls across a network, or anything else that a
function can do. What's different about macros is not *what*
they do, but *when* they do it and how the return value from
them is used... namely, as program *source* to be included in
the program being macroexpanded instead of the original macro
form present in the source.
Said another way, macros are programs within your programs that
write part of your programs for you. Or to lift from Sam Steingold's
and Martin Rodgers's sometime signatures, macros let you write
code that writes code that writes code for you.
+---------------
| Second, those languages that have global data can assume both
| reading and writing globals a RT-only operation.
+---------------
Uh... Not necessarily. It is quite possible for Lisp macros to
create/modify global data at compile time.
+---------------
| 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.
+---------------
Sometimes, and sometimes not -- it depends. Again, you really need
to study the various "times" that occur in a Common Lisp program,
including how you can conditionally test for and/or temporarily
change the "time", such as the EVAL-WHEN operator mentioned above.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Thomas A. Russ
Subject: Re: Why doesn't Lisp automatically differentiate functions and macros?
Date:
Message-ID: <ymi647jyong.fsf@sevak.isi.edu>
hovik <··············@gmail.com> writes:
I'll try not to repeat stuff from Kent's excellent reply.
> 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?
Well, for starters functions and macros do fundamentally different
things. Functions are used to COMPUTE VALUES and macros are used to
PRODUCE SOURCE CODE. The real problem is that you can't really tell
just from the output which is which. In other words, if I were to
invoke the following:
(list '+ 4 5) ==> (+ 4 5)
did I produce a data value or did I produce code? How should the
compiler treat this value? Should it be a list value or should it be
in-lined as code and then evaluted to produce 9? How does the compiler
decide this question?
> In fact, this kind of optimization, if possible at all, may be applied
> to some other languages as well.
>
> 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.
Well, that adds additional limits to what your macro is allowed to do.
Sometimes it is useful to be able to print during macro-expansion,
either for didactic purposes or to help you debug what is going on in a
macro expansion. Certain other "system calls" (whatever they are) may
also be useful to figure out how to modify a particular macro expansion.
> 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.
Well, there certainly is a chance that data may want to be stored at
macro-expansion time, particularly if you want to do something that
involves interacting macros where the definition stores information that
is used in further macro expansions. One such example, is a little
bit-flags hack I came up with to provide a symbolic interface to boolean
values encoded into fixnums -- both for speed and space savings. (See
below).
> 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.
Well, it's not clear what it means to have it available at both times.
Does the compiler compile the resulting form AND return it? That would
seem to be a bit odd.
> Is this correct? Or am I missing something? Maybe something specific
> to just Lisp macros?
No, there is a lot you are missing. Some of this is specific to Lisp
macros, but in general, I don't think you can come up with a compiler
smart enough to know whether (for example) an arbitary string is meant
to be data or a program.
============
;;; -*- Mode: LISP; Syntax: Common-lisp; Package: KBCLASSES; Base: 10. -*-
(eval-when (compile eval load)
(defparameter *bit-marker-alist* nil)
(defun calculate-bit-position (metatype marker)
(let ((pos (position marker (cdr (assoc metatype *bit-marker-alist*)))))
(if pos
pos
(error "~S is not a valid flag for ~S" marker metatype))))
(defun calculate-bit-values (metatype markers)
(let ((result 0))
(declare (fixnum result))
(loop for marker in markers
do (setf result
(the fixnum
(logior
result
(the fixnum
(ash 1 (calculate-bit-position metatype marker)))))))
result) )
) ; END EVAL-WHEN
(defmacro def-bit-flags (metatype &rest markers)
(if (> (length markers)
(integer-length most-positive-fixnum))
(error "Can't fit ~D ~S markers into a fixnum" (length markers) metatype)
`(eval-when (compile eval load)
(push (cons ,metatype ',(copy-list markers)) *bit-marker-alist*))) )
(defmacro set-bit-flags (location metatype &rest flags)
`(setf ,location (the fixnum (logior (the fixnum ,location)
(the fixnum ,(calculate-bit-values
metatype flags))))) )
(defmacro clear-bit-flags (location metatype &rest flags)
`(setf ,location (the fixnum (logandc2 (the fixnum ,location)
(the fixnum ,(calculate-bit-values
metatype flags))))) )
(defmacro test-bit-flags (location metatype &rest flags)
;; If the first of flags is :or, then do an or test, otherwise do an
;; and test;
(when (eql (first flags) :and) (pop flags))
(cond ((eql (first flags) :or) ;; Faster than logtest:
`(not (= 0 (the fixnum (logand (the fixnum ,(calculate-bit-values metatype (cdr flags)))
(the fixnum ,location))))))
((cdr flags)
(let ((flagValue (calculate-bit-values metatype flags)))
`(= (the fixnum (logand (the fixnum ,flagValue) (the fixnum ,location)))
(the fixnum ,flagValue)) ))
(t `(logbitp (the fixnum ,(calculate-bit-position metatype (car flags)))
(the fixnum ,location)))) )
(defun expand-bit-flags (encodedFlags metatype)
(loop for symbol in (cdr (assoc metatype *bit-marker-alist*))
for position upfrom 0
when (logbitp (the fixnum position) (the fixnum encodedFlags))
collect symbol))
#|
(def-bit-flags :instance
:skolem :user-defined-name :incoherent :discarded :abandoned-by-merge)
;; Macroexpand to test these:
(test-bit-flags (flags instance) :instance :or :skolem :discarded)
(test-bit-flags (flags instance) :instance :skolem :discarded)
(expand-bit-flags 9 :instance) ; => '(:skolem :discarded)
(expand-bit-flags 16 :instance) ; => '(:abandoned-by-merge)
(expand-bit-flags 31 :instance)
; => '(skolem :user-defined-name :incoherent :discarded :abandoned-by-merge)
(expand-bit-flags 32 :instance) ; => NIL
(defvar *test* 0)
(set-bit-flags *test* :instance :incoherent :user-defined-name) ; => 6
(test-bit-flags *test* :instance :incoherent) ; => T
(test-bit-flags *test* :instance :incoherent :skolem) ; => NIL
(test-bit-flags *test* :instance :and :incoherent :skolem) ; => NIL
(test-bit-flags *test* :instance :or :incoherent :skolem) ; => T
(test-bit-flags *test* :instance :incoherent :user-defined-name) ; => T
(test-bit-flags *test* :instance :and :incoherent :user-defined-name) ; => T
(test-bit-flags *test* :instance :incoherent :user-defined-name :discarded)
; => NIL
|#
--
Thomas A. Russ, USC/Information Sciences Institute
On Apr 26, 4:55 am, hovik <··············@gmail.com> wrote:
> 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?
Hmm. Wait a minute. Are you referring to the syntax for defining
functions and macros?
(defun function (foo bar) ...)
(defmacro macro (foo bar) ...)
?
Yes, they're both functions. However, in Lisp the difference between
"compile-time" and "run-time" has been blurred. Lisp allows Lisp code
to run any time during the transformation of source into actual
actions done by the computer. You can:
1. Define code that runs when Lisp is parsing the input stream of
characters. (read macros)
2. Define code that runs just before Lisp tries to figure out what
you want to do. (macros)
3. Define code that runs when Lisp is turning your code into machine
code. (compiler macros)
4. Define code that is, well, what you really want to do.
(functions)
The difference between defun and defmacro is where you want to place
the code you're writing. For defun, the function is run when you
actually call it in a piece of code it's in. For defmacro, the
function is run at the point where Lisp has the entire expression and
is trying to figure out what it means.
>
> In fact, this kind of optimization, if possible at all, may be applied
> to some other languages as well.
>
> 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.
>
> 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.
>
> 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.
>
> Is this correct? Or am I missing something? Maybe something specific
> to just Lisp macros?
I think you're confusing Lisp macros with optimization. What you
described is what nearly every decent compiler (for nearly every
decent language) has been doing for more than a decade now. It's
called "constant propagation."
Optimization can be done by Lisp macros. In addition, it can also:
1. Transform syntax. You want infix operators for math? You can
write an infix macro for math! (This is the main reason for Lisp
Macros)
2. Reduce retyping. If you have a bunch of very similar code, except
that, say, you use different functions in about the same places, you
can write a macro.