Remembering information during compilation
in [Lisp]
|
Prev: Lisp sucks!
Next: grabbing key presses
From: Spiros Bousbouras on 21 Nov 2009 07:42 On 21 Nov, 12:10, p...(a)informatimago.com (Pascal J. Bourguignon) wrote: > > Clearly, the expectation of naïve users such as me about a > macroexpand-all function would be that it expands to the same special > operators as macroexpand or macroexpand-1. Whereas a more sophisticated user would read the documentation instead of trying to figure out from just the name what it does. I wonder what the expectations of a naive user would be with regards to car or labels. > I'd say that expanding to the special operators of the implementation > is a specific need, and would need a more specific function, such as > EXPAND-ALL-TO-IMPLEMENTATION-SPECIAL-OPERATORS. And there is another "specific need" : macroexpand-all to things defined in the standard but not below. So user macros would be expanded but as soon as we reach standard macros then these would not be expanded regardless of whether they are implemented as special forms or not. This would be useful for debugging. -- Who's your mama ?
From: Spiros Bousbouras on 21 Nov 2009 11:03 On 18 Nov, 08:00, Pascal Costanza <p...(a)p-cos.net> wrote: > Spiros Bousbouras wrote: > > On 17 Nov, 20:15, Pascal Costanza <p...(a)p-cos.net> wrote: > >> Spiros Bousbouras wrote: > > >>> Is there any established way for how such parallel > >>> expansion/compilation is supposed to work ? Intuitively it seems to > >>> me that in the scenario you're describing the implementation ought to > >>> create one copy of a for the compilation and another for any > >>> expansions which are not part of the compilation. If it doesn't do > >>> that what makes you think that even your code will work correctly ? > >>> There may be clashes with the use of new-cell-value. > >> Huh? new-cell-value is lexically bound, so it's guaranteed to have its > >> own binding per invocation. > > > Guaranteed by what ? This situation is not covered by the standard , > > is it ? > > Lexical bindings? Of course they are covered by the standard. I was of course referring to the interaction between multithreading and lexical bindings. *That* is not covered by the standard. > > In any case in my code the variable a is also lexically bound. > > But you're performing side effects on this lexically bound variable, > which may lead to race conditions when multiple threads expand this one > macro. This is then a situation of concurrent write accesses to shared > memory, which usually need to be synchronized. In a 'pure binding' > (purely functional) situation, you don't have these problems. > > Yes, _multithreading_ is not covered by the standard, Which brings us back to what I ask above: Is there any established way for how such parallel expansion/compilation is supposed to work ? To put it otherwise you're saying that my code violates some rules but yours doesn't but you're not saying what these rules are , how universal they are among implementations and where one could read about those rules. And it's not clear what you mean by "side effects". Are you saying that things like setf are completely forbidden in the code which does the expansion ? > but there are > numerous multithreaded Common Lisp implementations, so if you want your > code to be portable, you better take that into account. No , if I want my code to be portable I only need to take into account the standard and possible bugs/non-conformances in the implementations. Portability *and* thread safety on the other hand , is a much more severe requirement. Having said that it still seems likely to me that my code will work everywhere yours will and that any multithreading Lisp implementation worth its salt will create separate copies of the variable a for each thread or synchronise access automatically. -- Never attribute to conspiracy what can adequately be explained by shared attitudes.
From: Duane Rettig on 21 Nov 2009 12:42 On Nov 21, 3:24 am, Spiros Bousbouras <spi...(a)gmail.com> wrote: > On 21 Nov, 10:13, p...(a)informatimago.com (Pascal J. Bourguignon) > wrote: > > > > > > > Spiros Bousbouras <spi...(a)gmail.com> writes: > > > I don't see why macroexpand-all cannot just return the dolist form > > > itself if dolist is implemented as a special form. > > > Because section "3.1.2.1.2.2 Macro Forms" says so. > > > DOLIST is specified to be a macro and as mentionned by section > > "3.1.2.1.2.2 Macro Forms": > > > An implementation is free to implement a Common Lisp special > > operator as a macro. An implementation is free to implement any > > macro operator as a special operator, but only if an equivalent > > definition of the macro is also provided. > > > it can be implemented as a special operator, however, in that case the > > implementation must provide a macro definition expanding (eventually) > > only to standard special operators, for the benefit of code walkers. > > But the standard does not mention macroexpand-all so it can behave > any way it likes. Furthermore it's not unreasonable that it would not > expand something which the implementation offers as a special form > even if the standard says is a macro. You'd have to figure out how to implement this in your macroexpand-all function. Ultimately, this function will be implemented by calling either macroexpand or macroexpand-1 at various times. The issue of wether to macroexpand a special-form is a hard one, and one that should be examined carefully at a lower level than the level you to are discussing here - i.e. you are discussing "what" should happen, when we need to deal with the "why" first wrt special operators. Special operators are really black-boxes, but the concepts need to be well-understood before it can be decided what to do with them. > Or macroexpand-all could be > designed to take an additional argument by which the programmer can > switch between "expand everything the standard says is a macro" and > "expand everything that this implementation actually (only) > implements as a macro". > > But more to the point earlier in the thread Tobias said: > > How does MACROEXPAND-ALL help the speed of compilation? Using > it, the implementation has to walk the syntax tree twice. > > Do you know that it can in fact lead to an _impairment_ of > runtime speed because implementation which would previously > implement some macros as special forms cannot do so? > > Even now as I reread it it seems to be saying that just by making > available macroexpand-all an implementation is prevented from > implementing some macros as special forms. But I think what he meant > was that if a piece of code uses macroexpand-all then when compiling > this code an implementation can no longer use the special form > version of a macro (if it has one) and has to use instead the actual > macro expansion. So yes , I see how macroexpand-all can cause an > impairment of *runtime* speed even when it is only called during > compilation. But this could be solved by offering a switch as I > mention above. Yes, this comes close to an understanding of why special operators are identified as such, and why the spec allows implementations to make special operators out of macros. The issue is this: A function is a first-class object that can be identified as the operator for a function call form. As an implementor, it is easy for me to get my compiler back-end to grab a call to (foo 10) and make it something else, performing the functionality of foo without actually calling foo. This allows for a faster implementation of foo's functionality. However, a macro is not a stopping point for macroexpand, and so the compiler back-end never sees the macro form - it only sees an implementation of the macro in terms of lower-level (including recursive) definitions - either function call forms or special forms. But if a macroexpansion process were to always expand past special forms, then your lowest level implementation would always and only be function forms. This is not only inefficient, it is ludicrous. It is why the spec doesn't require the standard special operators to also have macro definitions (though Allegro CL does provide macro definitions for all special operators). So let's take a specific CASE (pun intended): Consider the following definition: (defun foo (x) (declare (optimize speed (safety 0))) (case x ((1 3 5 7 9) 'hi) ((2 4 6 8 27) 'bye) (t 'nope))) Note that a macroexpand of the case form normally turns into a cond: CL-USER(1): (pprint (macroexpand '(case x ((1 3 5 7 9) 'hi) ((2 4 6 8 27) 'bye) (t 'nope)))) (LET () (COND ((OR (EQL '1 X) (EQL '3 X) (EQL '5 X) (EQL '7 X) (EQL '9 X)) 'HI) ((OR (EQL '2 X) (EQL '4 X) (EQL '6 X) (EQL '8 X) (EQL '27 X)) 'BYE) (T 'NOPE))) CL-USER(2): However, if we compile it (this one happens to be on x86-64) we get something completely different than a cond statement: CL-USER(2): (compile (defun foo (x) (declare (optimize speed (safety 0))) (case x ((1 3 5 7 9) 'hi) ((2 4 6 8 27) 'bye) (t 'nope)))) FOO NIL NIL CL-USER(3): (disassemble 'foo) ;; disassembly of #<Function FOO> ;; formals: X ;; constant vector: 0: NOPE 1: HI 2: BYE ;; code start: #x1000994588: 0: 48 c1 cf 03 ror rdi,$3 4: 48 83 ff 1b cmp rdi,$27 8: 0f 87 86 00 00 jnbe 148 00 14: 48 8d 15 0b 00 leaq rdx,[rip+11] ; 32 00 00 21: 48 63 04 ba movslq rax,[rdx+rdi*4+0] 25: 48 03 c2 addq rax,rdx 28: ff e0 jmp *eax 30: 66 90 .align 4 32: 74 00 00 00 .long $116 ; 0: 148 36: 7f 00 00 00 .long $127 ; 1: 159 40: 86 00 00 00 .long $134 ; 2: 166 44: 7f 00 00 00 .long $127 ; 3: 159 48: 86 00 00 00 .long $134 ; 4: 166 52: 7f 00 00 00 .long $127 ; 5: 159 56: 86 00 00 00 .long $134 ; 6: 166 60: 7f 00 00 00 .long $127 ; 7: 159 64: 86 00 00 00 .long $134 ; 8: 166 68: 7f 00 00 00 .long $127 ; 9: 159 72: 74 00 00 00 .long $116 ; 10: 148 76: 74 00 00 00 .long $116 ; 11: 148 80: 74 00 00 00 .long $116 ; 12: 148 84: 74 00 00 00 .long $116 ; 13: 148 88: 74 00 00 00 .long $116 ; 14: 148 92: 74 00 00 00 .long $116 ; 15: 148 96: 74 00 00 00 .long $116 ; 16: 148 100: 74 00 00 00 .long $116 ; 17: 148 104: 74 00 00 00 .long $116 ; 18: 148 108: 74 00 00 00 .long $116 ; 19: 148 112: 74 00 00 00 .long $116 ; 20: 148 116: 74 00 00 00 .long $116 ; 21: 148 120: 74 00 00 00 .long $116 ; 22: 148 124: 74 00 00 00 .long $116 ; 23: 148 128: 74 00 00 00 .long $116 ; 24: 148 132: 74 00 00 00 .long $116 ; 25: 148 136: 74 00 00 00 .long $116 ; 26: 148 140: 86 00 00 00 .long $134 ; 27: 166 144: 00 00 00 00 .long $0 148: 49 8b 7e 36 movq rdi,[r14+54] ; NOPE 152: f8 clc 153: 4c 8b 74 24 10 movq r14,[rsp+16] 158: c3 ret 159: 49 8b 7e 3e movq rdi,[r14+62] ; HI 163: f8 clc 164: eb f3 jmp 153 166: 49 8b 7e 46 movq rdi,[r14+70] ; BYE 170: f8 clc 171: eb ec jmp 153 173: 90 nop CL-USER(4): The first question is: if case is a macro, and it expands into a cond statement, how does the compiler get the macroexpansion to stop when it sees a special-operator? And isn't this precisely the kind of thing you're trying to do? The other question (and it is not rhetorical) is: if you are able to get macroexpansion to stop at a special operator, what will you do with the form you get back? There might be a number of things you can do with it, but since you have now a form that is no longer defined in terms of lower-level CL operators, but instead in terms of a black box that only the compiler knows how to implement, what will you do with the form? Duane
From: Pascal Costanza on 22 Nov 2009 08:14 Spiros Bousbouras wrote: >> Yes, _multithreading_ is not covered by the standard, > > Which brings us back to what I ask above: Is there any established > way for how such parallel expansion/compilation is supposed to work ? > To put it otherwise you're saying that my code violates some rules > but yours doesn't but you're not saying what these rules are , how > universal they are among implementations and where one could read > about those rules. And it's not clear what you mean by "side > effects". Are you saying that things like setf are completely > forbidden in the code which does the expansion ? No, I'm saying that side effects are known to be potential sources for race conditions, while binding constructs are known to avoid race conditions. >> but there are >> numerous multithreaded Common Lisp implementations, so if you want your >> code to be portable, you better take that into account. > > No , if I want my code to be portable I only need to take into > account the standard and possible bugs/non-conformances in the > implementations. Portability *and* thread safety on the other hand , > is a much more severe requirement. > > Having said that it still seems likely to me that my code will work > everywhere yours will and that any multithreading Lisp implementation > worth its salt will create separate copies of the variable a for each > thread or synchronise access automatically. One of the two options is a bet, the other isn't. I know which of the two I prefer. Good luck with your code, though. Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Spiros Bousbouras on 24 Nov 2009 13:54
On Sat, 21 Nov 2009 09:42:45 -0800 (PST) Duane Rettig <duane(a)franz.com> wrote: > On Nov 21, 3:24 am, Spiros Bousbouras <spi...(a)gmail.com> wrote: > > > But the standard does not mention macroexpand-all so it can behave > > any way it likes. Furthermore it's not unreasonable that it would not > > expand something which the implementation offers as a special form > > even if the standard says is a macro. > > You'd have to figure out how to implement this in your macroexpand-all > function. I'm not writing a macroexpand-all function. The possibility occurred to me and I considered starting a thread on the subject (and I may still do) but I imagine it cannot be done portably. I was simply saying that it would be convenient if the standard included a macroexpand-all function so that every conforming implementation would have it. > Ultimately, this function will be implemented by calling > either macroexpand or macroexpand-1 at various times. If one wants to do it portably then perhaps it's unavoidable that macroexpand or macroexpand-1 would have to be used. But if the implementation does it then it doesn't have such a restriction. > The issue of > wether to macroexpand a special-form is a hard one, and one that > should be examined carefully at a lower level than the level you to > are discussing here - i.e. you are discussing "what" should happen, > when we need to deal with the "why" first wrt special operators. In programming one usually starts with what one wants to achieve. I have explained during the course of the thread why I would want macroexpand-all but I suspect you haven't read the whole thread. In my opening post I gave a specific piece of code but I used the name minimal-compile instead of macroexpand-all because at the time I hadn't come across the name macroexpand-all. I was informed in this thread that macroexpand-all is an established (albeit non-standard) name for the functionality I want and I also came across the information that SBCL offers macroexpand-all so here's a working piece of code: ; Working but SBCL specific because of sb-cltl2:macroexpand-all and ; (require "sb-cltl2") (require "sb-cltl2") (let ((a 0)) (defmacro memory (&rest body) (prog2 (incf a) (sb-cltl2:macroexpand-all `(symbol-macrolet ((cell ,a)) ,@body)) (decf a)))) If macroexpand-all expands recursively user defined macros and the arguments given to macros defined by the implementation but does not expand the macros provided by the implementation then the above will still work. So for example if I do (macroexpand-all '(memory ... (when test-form form))) and I get (<expansion of memory> (when <expansion of test-form> <expansion of form>)) instead of (<expansion of memory> (<expansion of when> <expansion of test-form> <expansion of form>)) it is still adequate for my purposes. That's why I didn't have to concern myself with the issue of which standard macros the implementation implements as special forms. [...] > However, a macro is not a stopping point for macroexpand, and so the > compiler back-end never sees the macro form - it only sees an > implementation of the macro in terms of lower-level (including > recursive) definitions - either function call forms or special forms. > But if a macroexpansion process were to always expand past special > forms, then your lowest level implementation would always and only be > function forms. This is not only inefficient, it is ludicrous. Beyond ludicrous isn't it actually unworkable ? Function forms evaluate all their arguments but some times you don't want all the arguments evaluated. > It is > why the spec doesn't require the standard special operators to also > have macro definitions (though Allegro CL does provide macro > definitions for all special operators). You mean that if I do (some-allegro-specific-package:macroexpand-all '(when test-form form)) I will get something which only has function calls ? I'd love to know how you manage this. [...] > The first question is: if case is a macro, and it expands into a cond > statement, how does the compiler get the macroexpansion to stop when > it sees a special-operator? And isn't this precisely the kind of > thing you're trying to do? As I've said I'm not actually writing a macroexpand-all function but it seems to me that this particular issue can be easily solved portably: (defun macroexpand-all (form) (if (and (consp form) (special-operator-p (first form))) ; It's a special operator so it doesn't need to be expanded ...)) > The other question (and it is not rhetorical) is: if you are able to > get macroexpansion to stop at a special operator, what will you do > with the form you get back? There might be a number of things you can > do with it, but since you have now a form that is no longer defined in > terms of lower-level CL operators, but instead in terms of a black box > that only the compiler knows how to implement, what will you do with > the form? I can think of at least 2 possibilities: 1) Pass the form to the compiler for further compilation. See the example above. 2) Inspect the form visually for debugging purposes. So let's say for example that my code defines macros mac1 and mac2 and that the expansion of mac2 is influenced by whether it is called within the scope of a mac1 call. In order to verify that the interaction between mac1 and mac2 works correctly I may want to do something like (macroexpand-all '(mac1 (defun name (args) (mac2)))) and verify that I get the kind of expansion that I want. For this it does not help me in any way if defun itself gets expanded because I only want to verify that mac1 and mac2 expand to the right thing. On the contrary the result will probably be clearer if defun does not get expanded than if it gets expanded to some implementation specific symbols which would be unfamiliar to me. So , come to think of it , a macroexpand-all intended as a debugging tool would be more useful if it accepted a key argument called :test. This would be a function which accepts 1 argument which should be a symbol and returns true or false. macroexpand-all would only try to expand symbols for which the test function returns true (or all the symbols if no test function was given). So for the example above you would do (macroexpand-all '(mac1 (defun name (args) (mac2))) :test #'(lambda (item) (find item '(mac1 mac2)))) -- THE COURT: I forbid her from singing during the trial. I will not permit singing in this Courtroom. http://www.law.umkc.edu/faculty/projects/ftrials/Chicago7/Collins.html |