Macros in Common Lisp, Scheme, and other languages
Software Scavenger
macro implementation in different programming languages. Any message
about differences in language communities, or whether such crossposted
threads can cause flamewars, or whether some languages are religions,
or whether some people are idiots, are off topic.
From my point of view, the purpose of macros is to improve the syntax
of the language. Other points of view are welcome too, as long as
they're about macros. All programming languages have annoying quirks.
The best programming languages make it easy to get rid of the quirks
that annoy you the most, by writing macros to extend the language
beyond the quirk.
What I like most about Common Lisp macros is that I can use the full
power of the language to implement macros, and that includes power
provided by other macros I write for that purpose.
The recently discussed DO-COMBINATIONS macro is easy in both Common
Lisp and Scheme, even though it's much harder in languages such as
C++. To give a hint of what I mean by using the power of macros to
make it easier to implement macros, here are a couple of Common Lisp
versions of DO-COMBINATIONS:
The first version uses existing features of Common Lisp, and doesn't
use any other user-written macros to improve its implementation:
(defmacro do-combinations (syms list &rest body)
(labels ((work (syms x)
(let ((y (gensym)))
(if (cdr syms)
`(loop as (,(car syms) . ,y) on ,x
do ,(work (cdr syms) y))
`(loop as ,(car syms) in ,x do ,@body)))))
(work syms list)))
Here's how it works: The macro implementation consists entirely of a
single labels form, with everything else inside that form. The
purpose of a labels form is to define local functions, local to the
labels form, for use within the labels form. Those functions can be
mutually recursive. In this case, we only define one local function,
named "work", which is recursive. After the function definitions of a
labels form is code to use its functions. In this case, that code
consists of a single call to work. The work function itself is
implemented with a single let form, with everything else inside that
let form. Gensym generates a symbol, which we refer to as "y", but
which will be something unique in the macro expansion, so it won't
conflict with any other symbols, such as the iteration variables. The
"if" asks whether there are at least two more iteration variables
(syms), which is asked by "cdr syms", and if so, it generates code for
a nested loop. Otherwise it generates code for the innermost loop of
the iteration.
The above macro is too short to really show anything about the
advantages and disadvantages of different macro implementation styles
etc. But we can get some hints, by paying attention to details that
might seem like nitpicking on this scale but would become much more
significant for bigger macros.
What I don't like about the above implementation is the labels form.
I just want to use it for one local function in this case, so why do I
have to give it so much syntax? Why the extra parentheses? Why do I
even have to name the function? And then use a whole new level of
nesting just for a local variable binding? So I might decide to come
up with my own version of labels which fits this particular task
better. Let's call it rabel, as a version of labels for a single
recursive function. (I'm sure we could come up with a better name if
we spent more time thinking about it, but that's not the issue here.)
In this "rabel" version of "labels", we only want to define one local
function, so why should we even bother to name it? Why not just give
it a default name such as "the-local-function"? Or better, a shorter
name, such as "locfunc"? Or maybe derive its name from the name of
the macro. "Rabe" for "rabel". Just like we might name such a thing
"babe" if the macro were named "babel".
And what about the excess parentheses? Since we only have one local
function, they don't need to be in a list, so that list doesn't need
any parentheses around it.
And what about the binding of the local variable, "y"? We should make
that part of the rabel form, so we don't have to add another level of
nesting. In fact, while we're at it, we could use a couple more local
variables to make things a little clearer. So the rabels form should
accept a list of local variable bindings. And I don't like the "let"
convention of putting the bindings in parentheses to indicate that
they have initializer expressions. I would rather just use nil to
indicate that they don't. E.g instead of (let ((a 1) (b 2) c)) I
would rather it were (let (a 1 b 2 c nil). So I think I will try that
style in my rabels form, or at least the first version of it.
Another thing that would be nice would be to get rid of the code after
the local function definition. It gives the code a cluttered look,
and in this case is not usef for anything but the initial call to the
local function. In fact for most uses of labels that code probably
does nothing but compute the arguments to the initial call to one of
the local functions in the labels form. So we might improve it by
putting that code at the beginning. In this case let's try giving it
as initializers to the formal arguments of the local function. In
other words, each local argument will consist of an argument name and
an expression to provide an initial value for that argument on the
initial call to the function. We can give the argument names and
expressions in a single list, because each argument will always be
followed by an expression. The scope of the expressions should be
outside the rabel form, because they might refer to a name which we
might want to reuse as an argument name.
Thus the rabel form would have a list of arguments and expressions,
then a list of local variable bindings, then the forms that make up
the body of the local function.
Given those changes, which admittedly have not been designed carefully
yet, let's see what the new version of DO-COMBINATIONS would look
like:
(defmacro do-combinations (syms list &rest body)
(rabel (syms syms x list)
(y (gensym) sym (car syms) more (cdr syms))
(if more `(loop as (,sym . ,y) on ,x do ,(rabe more y))
`(loop as ,sym in ,x do ,@body))))
Or with more vertical formatting:
(defmacro do-combinations (syms list &rest body)
(rabel (syms syms
x list)
(y (gensym)
sym (car syms)
more (cdr syms))
(if more
`(loop as (,sym . ,y) on ,x
do ,(rabe more y))
`(loop as ,sym in ,x
do ,@body))))
This whole discussion might seem silly, because do-combinations is not
complicated enough to be worth all this attention. But the point is
that by implementing macros such as rabel we extend the language to
make such things easier. Admittedly rabel is not the best example
because it only adds a very small improvement, but other such macros
could make much bigger improvements. If we want to implement
thousands of macros of the complexity of do-combinations, and also a
large number of much more complicated macros, we can make all that
work easier by having a lot of language extensions such as rabel.
What usually happens with a macro such as rabel is that it gets used
for a while and then discarded. Some other macro, newly created to
solve the same problem better, probably more generally, etc., might
take its place. But we get there in steps, and rabel is one of those
steps. Doing this kind of development, we have to be prepared to
spend a lot of time reworking/refactoring our code. Every time we
replace a macro with a better one, we have to update all usages of it.
But that's not as much work as it sounds like, and the results seem
worth it.
The more features we have in our programming language, including the
extensions we add to that language, the more likely we are to have
what we need when we need it. Having the features we need when we
need them is why we even care about the differences between
programming languages. The whole idea is to be able to program better
and faster, to be able to respond as quickly and effectively as
possible to any request for any software or improvement.
This is why macros seem like such a big deal to me, and why I think it
would be worthwhile to discuss them extensively month after month,
including discussing the differences in macro implementation in
different programming languages. If only we can keep it on topic, and
avoid all the off topic posts telling us this kind of discussion
always leads to flame wars etc. (Not that such off topic posts, nor
even the flame wars themselves, are much different from the normal
fare on these forums.)
Adrian B.
> The purpose of this thread is to discuss macros,
I want to thank you for starting this new thread. Everyone just went
totally mental when I tried asking about scheme macros in the other
thread.
> From my point of view, the purpose of macros is to improve the syntax
> of the language.
Do you mean they should be used to extend the language, or create mini
domain specific languages?
> What I like most about Common Lisp macros is that I can use the full
> power of the language to implement macros, and that includes power
> provided by other macros I write for that purpose.
Why didn't scheme macros follow this path? There must have been
perceived problems with CL macros that the scheme R5RS authors wanted
to avoid or overcome.
Thanks.
![Michael Sperber [Mr. Preprocessor]'s profile photo](http://lh3.googleusercontent.com/a-/ALV-UjW1Ug-7D5rvPAe0Dy8QWlBwdoMp8sHWFACGdNTzwJ9mF7CkTQ=s40-c)
Michael Sperber [Mr. Preprocessor]
Adrian> Why didn't scheme macros follow this path? There must have been
Adrian> perceived problems with CL macros that the scheme R5RS authors wanted
Adrian> to avoid or overcome.
Hygiene.
--
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla
peter_douglass
> Why didn't scheme macros follow this path? There must have been
> perceived problems with CL macros that the scheme R5RS authors wanted
> to avoid or overcome.
Scheme predates CL.
One of the distinguishing innovations that Scheme brought to Lisp was the
use of syntactic binding by default rather than dynamic binding by default.
(What this means is that the semantics of an expression can be determined
syntacticly, rather than requiring knowledge of the environment in which an
expression is used.). IOW, syntactic binding supports referential
transparency. Scheme macros follow the same philosophy of supporting
referential transparency by preventing name capture.
Common Lisp broke with prior non-Scheme Lisps by adopting syntactic binding
by default. However, it did not adopt the philophy of referential
transparency to the extent of Scheme -- particularly with respect to macros.
The argument being that name capture is sometimes a good thing, for example
in "retro-fitting" code.
--PeterD
Noel Welsh
> Why didn't scheme macros follow this path? There must have been
> perceived problems with CL macros that the scheme R5RS authors wanted
> to avoid or overcome.
>
You may like this page:
http://c2.com/cgi/wiki?LispMacros
In short, there are two Scheme macro systems in common use:
syntax-rules and syntax-case. syntax-rules is a strict subset of
syntax-case and cannot do everything CL macros can. This restriction
does not apply to syntax-case.
Noel
Software Scavenger
> Do you mean they should be used to extend the language, or create mini
> domain specific languages?
A domain specific language would normally be created by a combination
of macros and functions. The functions add the domain specific
features. The macros smooth the syntax to make those features easier
to use. A set of functions to create a domain specific language is
like an uncut diamond from a diamond mine. The set of macros to
smooth the syntax is like the cut and polish that makes that diamond a
gem.
Of course that's a loose analogy. Some macros could be considered
domain specific, such as do-combinations. Depending on how you define
a domain. And the purpose of do-combinations is not to polish or
improve the syntax, but to implement a specific algorithm. But that's
a rare exception, and it could be implemented by a function. Such a
function would take as one of its arguments a function to invoke once
per iteration, which would take the place of the "body" of a
do-combinations form.
So the general purpose of macros is to improve the syntax, but they
can also be used for other purposes such as to take the place of a
function in some situations.
Feuer
> So the general purpose of macros is to improve the syntax, but they
> can also be used for other purposes such as to take the place of a
> function in some situations.
Usually if they're not improving syntax they're improving efficiency.
Where the line is drawn is not always clear of course, but it may be
that you want the programmer to write a little macro code that expands
to a lot of core code that is much more efficient than doing everything
with functions. Compile-time computation can be useful.
David
Jean-Paul Roy
the application syntax, so we can put the keyword anywhere and not just
in the car of the special form ? [Say the macro expanser could find the
first keyword in a form...] I just heard of a paper in Sigplan Prog.
Lang. 2002 on something like such a syntax expander for Java by guys at
Rice ?
-jpr
Thant Tessman
> Is there any tentative macro system in Scheme which does not respect
> the application syntax, so we can put the keyword anywhere and not just
> in the car of the special form ? [...]
Years ago when I used Chez Scheme, it had an experimental macro system
that supported such a construct. I think they were called "singleton
keywords." I actually came up with a use for them as part of
(interestingly enough) optimizing the dispatch of multimethods when the
type was known or inferrable or something like that. Don't know if they
made it past the "experimental" stage, but I wouldn't be surprised if
they did.
-thant
Erik Naggum
| Compile-time computation can be useful.
But in this case, using /compiler-macros/ is the appropriate choice.
--
Erik Naggum, Oslo, Norway
Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.
Rainer Joswig
cubic...@mailandnews.com (Software Scavenger) wrote:
<...>
> From my point of view, the purpose of macros is to improve the syntax
> of the language.
<...>
This is only one possible use of Macros.
1) simple code transformations
2) embedded languages (with complex compilers)
3) shifting computational effort to macro expansion time
4) shifting computational effort to load time
5) create side-effects at macro expansion time.
6) create side-effects at load time
and more.
Just remember that the full Common Lisp environment is available at
read time, macro expansion time, compile time, load time, run time, ...
(Though it may not necessarily be the same Lisp environment).
And you can let the Lisp system execute code for you at those
occasions.
An example using Macintosh Common Lisp:
The file test1.lisp just contains the following form:
(foo)
Let's define a macro with code that runs at different times.
? (defmacro foo ()
#.(print "code executed at read time")
(print "code executed at macro expansion time")
`(progn
(eval-when (:compile-toplevel)
(print "code executed at compile time"))
(eval-when (:load-toplevel)
(print "code executed at load time"))
(defun bar ()
(print "code executed at run time")
(values))))
"code executed at read time"
FOO
? (compile-file "ccl:test1.lisp")
;Compiling "ccl:test1.lisp"...
"code executed at macro expansion time"
"code executed at compile time"
#P"ccl:test1.cfsl"
NIL
NIL
? (load *)
;Loading #P"ccl:test.cfsl"...
"code executed at load time"
#P"ccl:test.cfsl"
? (bar)
"code executed at run time"
Here is an example for 6).
See this function definition:
(defun foo (bar)
(funcall bar))
DEFUN is a macro. Let's macro-expand above in
Macintosh Common Lisp:
(PROGN
(EVAL-WHEN (:COMPILE-TOPLEVEL)
(CCL::NOTE-FUNCTION-INFO
'FOO
'(LAMBDA (BAR)
(DECLARE (CCL::GLOBAL-FUNCTION-NAME FOO))
(BLOCK FOO (FUNCALL BAR)))
NIL))
(CCL::%DEFUN (NFUNCTION FOO
(LAMBDA (BAR)
(DECLARE (CCL::GLOBAL-FUNCTION-NAME FOO))
(BLOCK FOO (FUNCALL BAR))))
'NIL)
'FOO)
When you compile (!) this code it notes that FOO is a function and
saves its defining form.
So, as one use of macros, Lisp IDEs also use these toplevel macros to
update development environment information. Obviously, user written
macros can exploit the same mechanism.
Rainer Joswig
P.M.
> * Feuer
> | Compile-time computation can be useful.
>
> But in this case, using /compiler-macros/ is the appropriate choice.
Hi Erik,
Can you explain what compiler-macros are and how they differ from
ordinary macros? Compile-time computation sounds a bit like template
metaprogramming in C++.
Thanks
Peter
Erik Naggum
| Can you explain what compiler-macros are and how they differ from
| ordinary macros?
There are two important differences. The first is that they are defined in
addition to the function, which remains available for normal calls. The
second is that they /may/ rewrite a function call at compile-time to
redirect the call to a different (such as a more type-specific) function or
to inline the operation with system- or implementation-specific forms. The
significance of the /may/ is that a compiler macro may decline to rewrite
the form, in which case the original function call remains.
An ordinary macro is, as you may know, always expanded and it is impossible
to call it indirectly. The compiler-macro combines the power of rewriting
with an actual function. A compiler-macro is more useful in the presence of
environment information, such that it can know the declared or inferred type
of variable bindings and act on such knowledge. One particularly nice way
to use compiler macros is in combination with keyword arguments; because
they can be expensive to use in functions that need only a subset of the
full functionality, a compiler macro can detect the actual keywords used and
call the applicable specialized function. E.g., the general function `member´
may have specialized functions according as the `:key´ or `:test´ arguments
reflect common usages, like `:key #'car´ or `:test #'string=´.
| Compile-time computation sounds a bit like template metaprogramming in C++.
Template meta-programming is compile-time computation, but I am not quite
sure how templates work. I have not programmed in C++ for about a decade,
and it was much less involved then.
Paul F. Dietz
> There are two important differences. The first is that they are defined in
> addition to the function, which remains available for normal calls. The
> second is that they /may/ rewrite a function call at compile-time to
> redirect the call to a different (such as a more type-specific) function or
> to inline the operation with system- or implementation-specific forms.
I've found myself wanting some way in CL to have declaration information
(types, optimization settings, dynamic extent, etc.) available at macro
expansion time, probably in macro environment argument. There are
ways to do this manually but they are awkward and incomplete.
Beyond that, it would be nice if CL macro forms could be analyzed in
some way before being expanded, so one could do type propagation before
or interleaved with macro expansion. This would have to involve additional
hints to the compiler, some kind of DEF-MACRO-SEMANTICS form. I'm not
familiar with how Scheme does macros; would this be easier in that world?
Paul
Erik Naggum
| Beyond that, it would be nice if CL macro forms could be analyzed in
| some way before being expanded, so one could do type propagation before
| or interleaved with macro expansion.
Since the compiler expands the macro and then works on the resulting code
with all type propagation from the environment available for the existing
bindings, I am not sure what this means.
The purpose of environment information is to make it possible to make
macro-expansion decisions in addition to the ones the compiler makes after
expansion.
Paul F. Dietz
> Since the compiler expands the macro and then works on the resulting code
> with all type propagation from the environment available for the existing
> bindings, I am not sure what this means.
>
> The purpose of environment information is to make it possible to make
> macro-expansion decisions in addition to the ones the compiler makes after
> expansion.
I understand this. The current scheme makes it hard for the user to
do some things that the compiler can do. For example, the user cannot
easily write a compiler macro that replaces some function call FOO
with FOO-ON-FIXNUM or FOO-ON-FLOAT according to the type of its
argument; a Lisp compiler, on the other hand, frequently does this
kind of type-specific implementation, but only on CL builtins and
then often not as completely as one might want.
Having variable type information available at macro expansion time
would go some way to allowing this (if FOO is called on a variable,
for example), but being able to propagate types before/during macro
expansion would allow more information to be used.
I realize that macros can expand to arbitrary code. My suggestion
was to allow some way for the user to provide a hint to the system
so it can propagate information through unexpanded macros. Perhaps
this could be limited to compiler macros, which should be written
to reflect the semantics of the equivalently named functions anyway.
Paul
Erik Naggum
| I understand this.
Sorry, that not clear to me from what you wrote.
| The current scheme makes it hard for the user to do some things that the
| compiler can do.
Precisely, but there are different ways to accomplish this. If the compiler
knows the type, you can let the macro expand to a `type-case´ form that the
compiler should optimize away. If the compiler cannot optimize it away, it
will be a run-time decision, instead, which may bloat the code but should
yield nearly the same performance benefits.
| I realize that macros can expand to arbitrary code. My suggestion was to
| allow some way for the user to provide a hint to the system so it can
| propagate information through unexpanded macros. Perhaps this could be
| limited to compiler macros, which should be written to reflect the semantics
| of the equivalently named functions anyway.
I think macros are used where compiler-macros should be used mainly because
the programmer does not know about compiler-macros. For some reason, they
are not covered in many Common Lisp texts.
Paul F. Dietz
> Precisely, but there are different ways to accomplish this. If the compiler
> knows the type, you can let the macro expand to a `type-case´ form that the
> compiler should optimize away. If the compiler cannot optimize it away, it
> will be a run-time decision, instead, which may bloat the code but should
> yield nearly the same performance benefits.
This would work, but I see some problems.
-- Lisp compilers (even commercial ones) often don't do optimizations
that they 'should' do, particularly type-based ones.
-- I have encountered post-macro-expansion code size limits in
a commercial Lisp compiler (where the compiler aborts or silently
generates wrong code if the routine being compiled is too big).
The code expansion from your suggestion would aggravate the problem.
-- One can imagine situations where this idea would lead to exponential
expansion of the code. For example, suppose we are expanding a mapping
function that takes N sequences as arguments. If we want to customize
depending on whether each argument is a vector or a list, there are 2^N
different possibilities (and if vector arguments' types have known length
then we can exploit this for even more cases.) One could restrain this
by setting a flag for each argument and checking it on each iteration
for each sequence to see whether the argument was a list or a vector, but
the performance impact there could be significant.
Paul
Thomas F. Burdick
> Erik Naggum wrote:
>
> > Since the compiler expands the macro and then works on the resulting code
> > with all type propagation from the environment available for the existing
> > bindings, I am not sure what this means.
> >
> > The purpose of environment information is to make it possible to make
> > macro-expansion decisions in addition to the ones the compiler makes after
> > expansion.
>
> I understand this. The current scheme makes it hard for the user to
> do some things that the compiler can do. For example, the user cannot
> easily write a compiler macro that replaces some function call FOO
> with FOO-ON-FIXNUM or FOO-ON-FLOAT according to the type of its
> argument; a Lisp compiler, on the other hand, frequently does this
> kind of type-specific implementation, but only on CL builtins and
> then often not as completely as one might want.
Yes, it is very handy to be able to write optimizations based on the
type inferencing that your compiler did. But it's also obvious that
this would be impossible to standardize without massively limiting the
implementation strategies of CL compilers. So, ask your vendor. I
would imagine that all compilers that perform optimizations based on
type inferencing, define these optimizations in a framework for the
compiler -- ie, they don't hard-code the optimizations into the
compiler. Your vendor may be able to tell you how to use this
framework for your own programs. If they can't, you might consider
switching vendors.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Joe Marshall
"Thomas F. Burdick" <t...@whirlwind.OCF.Berkeley.EDU> wrote in message
news:xcv1y85...@whirlwind.OCF.Berkeley.EDU...
>
> Yes, it is very handy to be able to write optimizations based on the
> type inferencing that your compiler did. But it's also obvious that
> this would be impossible to standardize without massively limiting the
> implementation strategies of CL compilers.
It is not obvious to me. This would imply that there are many
compilation strategies all of which lose various amounts of information
about the values of types.
This isn't to say that it wouldn't require a fair amount of work to
adapt a compiler to track the necessary type information. I would
imagine, however, that nearly every compilation technique could be
adapted to track *some* type information.
Erik Naggum
| This would work, but I see some problems.
All of them implementation restrictions. If we wish to make macros better by
augmenting them with environment information, that would require some work
to improve existing compilers. If not even the work necessary to remove the
implementation restrictions that you point out is sufficiently motivated by
the improvements that we could clearly obtain at the far side of availability
of better compilers, what would motivate the universal implementation of
environment information for macros? Do you see the effort required to add
environment information as significantly less than that required to fix the
problems you have encountered in existing compilers? If so, on what have
you based this assessment?
I think the current language is strong enough to do what we want to do with
Common Lisp, and that the macro system does not need improvement for any
/semantic/ reasons. However, there is a difference in /convenience/ that might
provide programmers with an impetus to change their ways when optimizing
their code if they had macros that could significantly simplify the task for
the compiler, and they could observe improvements in the compiled code.
However, I can hardly imagine such improvements to be disconnected, so one
who wanted to make type-sensitive improvements to Common Lisp code would
want a compiler that could do it with the current language.
As to the exponential growth, I do not understand the purpose of pointing
out hard problems before we even know where to go with simpler ones. What
matters is the conditions under which the solutions will scale well and under
which it would not. I would not be very surprised to see n-ary functions
fail to be optimizable with this scheme, but that should not deter us from
making improvements that would mainly improve less complex functions.
Frode Vatvedt Fjeld
> There are two important differences. The first is that they are
> defined in addition to the function, which remains available for
> normal calls.
Also remember that you can have compiler-macros for macros, not just
functions.
--
Frode Vatvedt Fjeld
Paul F. Dietz
> Yes, it is very handy to be able to write optimizations based on the
> type inferencing that your compiler did. But it's also obvious that
> this would be impossible to standardize without massively limiting the
> implementation strategies of CL compilers.
This is not at all clear to me. In particular, this would all be
happening at macro expansion time, so once macros are expanded and
you're into the compiler proper no constraints would remain on
the implementation. The type inferencing (if any) that occurs
during these expansions need not have any relation to that which
occurs during the compilation of the expanded code.
Paul
Thomas F. Burdick
You expect that someone is going to write a compiler that interleaves
macro expansion and type inference?!?! </exaggerated-indignation>.
If you read my post, you'll see that I carefully avoided referring to
exactly how those optimizations would work -- whether they'd be
similar to macroexpansion, or operate on a well-documented
representation the compiler uses, or what. Making this type of
optimizer work well in a system would mean doing things the compiler's
way, which is necessarily implementation-dependant.
Thomas F. Burdick
Well, I'm assuming you'd want this standardized interface to work on
s-expressions, right? The compiler that I'm working on currently
loses the s-expressions fairly early, and its optimizers work on a
couple of internal representations -- converting these back to Lisp
source code would be non-trivial, and would make writing the
optimizations unnecessarily difficult.
Brad Miller
> * Paul F. Dietz
> | This would work, but I see some problems.
>
> All of them implementation restrictions. If we wish to make macros
better by
> augmenting them with environment information, that would require some
work
> to improve existing compilers. If not even the work necessary to remove
the
> implementation restrictions that you point out is sufficiently motivated
by
> the improvements that we could clearly obtain at the far side of
availability
> of better compilers, what would motivate the universal implementation of
> environment information for macros? Do you see the effort required to
add
> environment information as significantly less than that required to fix
the
> problems you have encountered in existing compilers? If so, on what
have
> you based this assessment?
Note that fixing the current compilers fixes the particular problems that
Paul has encountered, while adding environment information potentially fixes
several other future problems as well, not to mention the ability to support
a /pragmatic/ level for expasnsion (context-aware macros).
Paul F. Dietz
> You expect that someone is going to write a compiler that interleaves
> macro expansion and type inference?!?! </exaggerated-indignation>.
> If you read my post, you'll see that I carefully avoided referring to
> exactly how those optimizations would work -- whether they'd be
> similar to macroexpansion, or operate on a well-documented
> representation the compiler uses, or what. Making this type of
> optimizer work well in a system would mean doing things the compiler's
> way, which is necessarily implementation-dependant.
No, I expect someone would write a macro expander that would
also be able to do type inference. It would have to work during
eval of uncompiled code, after all.
Look, why is this necessarily hard? Define type inference in a
sufficiently limited way and it's trivial (can only return a meaningful
type on declared variables, constants, and 'THE' expressions, perhaps).
Loosen that a bit and it becomes more difficult, but not necessarily hard
(propagates types up through forms, but not through assignments or
bindings.)
I repeat: the type inference that would be done during macro
expansion time need not have anything to do with the type
inference that is done on the expanded code by the compiler
proper.
In fact, if we're given the (rejected) environment manipulation proposal
in the CLHS, this could be done entirely by the *user*.
Paul
Koen Claessen
| You expect that someone is going to write a compiler
| that interleaves macro expansion and type
| inference?!?! </exaggerated-indignation>.
I have not read all of the other posts in this thread, so
the following might already have been discussed here, but
this is exactly what "Template Haskell" is supposed to do:
http://research.microsoft.com/Users/simonpj/
The idea is that a program may calculate its own
sub-expressions or toplevel declarations, which are then
pasted in by the compiler and type checked on the fly.
Really cool stuff!
/Koen.
Thomas F. Burdick
> "Thomas F. Burdick" wrote:
>
> > You expect that someone is going to write a compiler that interleaves
> > macro expansion and type inference?!?! </exaggerated-indignation>.
> > If you read my post, you'll see that I carefully avoided referring to
> > exactly how those optimizations would work -- whether they'd be
> > similar to macroexpansion, or operate on a well-documented
> > representation the compiler uses, or what. Making this type of
> > optimizer work well in a system would mean doing things the compiler's
> > way, which is necessarily implementation-dependant.
>
> No, I expect someone would write a macro expander that would
> also be able to do type inference. It would have to work during
> eval of uncompiled code, after all.
This is substantially less useful than what I was talking about -- to
the point of being a different subject. This discussion originated
with an idle wish of being able to take advantage of the compiler's
type knowledge when writing an expansion for a compiler macro. Given
that we're talking about optimizers analagous to compiler macros, no,
I don't think it should have to work for interpreted code.
> Look, why is this necessarily hard?
Because of its nature -- not all things are trivial, and this is an
example of one that's not.
> Define type inference in a sufficiently limited way and it's trivial
> (can only return a meaningful type on declared variables, constants,
> and 'THE' expressions, perhaps). Loosen that a bit and it becomes
> more difficult, but not necessarily hard (propagates types up
> through forms, but not through assignments or bindings.)
This is only a half-assed solution, and it puts some serious
constraints on the implementation, with very little payoff. If I
wanted to constantly write type declarations, I would be using a
statically-typed language, not a dynamically-typed one, with a good
type-inferencer in my implementation.
> I repeat: the type inference that would be done during macro
> expansion time need not have anything to do with the type
> inference that is done on the expanded code by the compiler
> proper.
>
> In fact, if we're given the (rejected) environment manipulation proposal
> in the CLHS, this could be done entirely by the *user*.
Then we'd have people idly wishing that they could take advantage of
the compiler's good type inference; and I'd have suggested that they
look to their vendors for advice on writing their own
implementation-specific optimizers ... which is not very far from
where we are now. The (pain : payoff) ratio is just too large.
Paul F. Dietz
> This is substantially less useful than what I was talking about -- to
> the point of being a different subject. This discussion originated
> with an idle wish of being able to take advantage of the compiler's
> type knowledge when writing an expansion for a compiler macro.
Looking back, I see that there is nowhere I said this. You are
mistaking your own intepretation of previous statements for
the actual content of those statements.
> > Define type inference in a sufficiently limited way and it's trivial
> > (can only return a meaningful type on declared variables, constants,
> > and 'THE' expressions, perhaps). Loosen that a bit and it becomes
> > more difficult, but not necessarily hard (propagates types up
> > through forms, but not through assignments or bindings.)
>
> This is only a half-assed solution, and it puts some serious
> constraints on the implementation, with very little payoff.
Half-assed is better than no ass at all. I disagree that the
payoff is minimal.
> If I wanted to constantly write type declarations, I would be using a
> statically-typed language, not a dynamically-typed one, with a good
> type-inferencer in my implementation.
But if one's goal is to improve performance of Lisp programs, switching
to another language is, by definition, a non-answer.
> > In fact, if we're given the (rejected) environment manipulation proposal
> > in the CLHS, this could be done entirely by the *user*.
>
> Then we'd have people idly wishing that they could take advantage of
> the compiler's good type inference; and I'd have suggested that they
> look to their vendors for advice on writing their own
> implementation-specific optimizers ... which is not very far from
> where we are now. The (pain : payoff) ratio is just too large.
Using undocumented vendor-specific features is nonportable, perhaps even
between different versions of the same vendor's software. Sorry, that's
not acceptable to me as a general solution. I dislike depending on
vendor-specific details of any kind, or even depending on the fact
their compiler may implement certain optimizations.
Paul
Thomas F. Burdick
> "Thomas F. Burdick" wrote:
>
> > This is substantially less useful than what I was talking about -- to
> > the point of being a different subject. This discussion originated
> > with an idle wish of being able to take advantage of the compiler's
> > type knowledge when writing an expansion for a compiler macro.
>
> Looking back, I see that there is nowhere I said this. You are
> mistaking your own intepretation of previous statements for
> the actual content of those statements.
FWIW, I was considering this branch of this thread to have this post
as its parent:
Message-ID: <3D79E7CD...@dls.net>
> > > Define type inference in a sufficiently limited way and it's trivial
> > > (can only return a meaningful type on declared variables, constants,
> > > and 'THE' expressions, perhaps). Loosen that a bit and it becomes
> > > more difficult, but not necessarily hard (propagates types up
> > > through forms, but not through assignments or bindings.)
> >
> > This is only a half-assed solution, and it puts some serious
> > constraints on the implementation, with very little payoff.
>
> Half-assed is better than no ass at all. I disagree that the
> payoff is minimal.
>
>
> > If I wanted to constantly write type declarations, I would be using a
> > statically-typed language, not a dynamically-typed one, with a good
> > type-inferencer in my implementation.
>
> But if one's goal is to improve performance of Lisp programs, switching
> to another language is, by definition, a non-answer.
I suppose the payoff depends on your style. I don't write type
declarations except where I need to. It might be because I'm
something of a compiler-nerd, but I expect the compiler to be able to
do useful type inference -- if it can't, it's wasting my (the user's)
time, and I should switch to a better implementation. Having to
pepper my code everywhere with type declarations will make it
difficult to read and modify, brittle, and sufficiently different that
I might as well be writing in a statically-typed language. If I wish
to keep my Lisp lispy, then the payoff would be very small -- if I'm
okay with brittle declarations everywhere, the payoff could be
greater, but it comes at too large of a cost.
> > > In fact, if we're given the (rejected) environment manipulation proposal
> > > in the CLHS, this could be done entirely by the *user*.
> >
> > Then we'd have people idly wishing that they could take advantage of
> > the compiler's good type inference; and I'd have suggested that they
> > look to their vendors for advice on writing their own
> > implementation-specific optimizers ... which is not very far from
> > where we are now. The (pain : payoff) ratio is just too large.
>
> Using undocumented vendor-specific features is nonportable, perhaps even
> between different versions of the same vendor's software. Sorry, that's
> not acceptable to me as a general solution. I dislike depending on
> vendor-specific details of any kind, or even depending on the fact
> their compiler may implement certain optimizations.
I said "look to their vendors for advice". Presumably the vendor
won't say "use this unsuported interface". As for demanding
portability, you can't have it both ways. If you want very efficient
code, you can have it, but the vast majority of the efficiency isn't
portable. This is true in every language I've seen -- I don't see why
Lisp should be any different. In fact, the wide variety of
implementation techniques and supported hardwares virtually guarantees
that you can't have both.
Bruce Hoult
t...@hurricane.OCF.Berkeley.EDU (Thomas F. Burdick) wrote:
> I don't write type declarations except where I need to. It might be
> because I'm something of a compiler-nerd, but I expect the compiler
> to be able to do useful type inference -- if it can't, it's wasting
> my (the user's) time, and I should switch to a better implementation.
> Having to pepper my code everywhere with type declarations will make
> it difficult to read and modify, brittle, and sufficiently different
> that I might as well be writing in a statically-typed language.
My style in Dylan is to declare types for most arguments of most
functions. This is largely documentation to myself, and there will
(initially) be a line somewhere saying...
define constant <employees> = <object>;
Or perhaps I might narrow it down as far as <collection> or even
<sequence>, but not initially all the way to <simple-object-vector>.
Numerical arguments might get declared as a type constant equal to
<number>, rather than <integer>.
Mostly it just makes the code easier to figure out later, but it also
makes it easier to tighten down the types later, if that turns out to be
useful.
-- Bruce
Sander Vesik
>
> -- One can imagine situations where this idea would lead to exponential
> expansion of the code. For example, suppose we are expanding a mapping
> function that takes N sequences as arguments. If we want to customize
> depending on whether each argument is a vector or a list, there are 2^N
> different possibilities (and if vector arguments' types have known length
> then we can exploit this for even more cases.) One could restrain this
> by setting a flag for each argument and checking it on each iteration
> for each sequence to see whether the argument was a list or a vector, but
> the performance impact there could be significant.
This is in case it really generates all the combinations - OTOH it could
look at how the function was being called and make only some of the
2^N cases. A ,trivial example (which would allow it to do even more
optimisation) is it being called as:
(func foo bar ... (cons something '()) ... baz)
>
> Paul
--
Sander
+++ Out of cheese error +++