How to use dynamic-extent declarations...
in [Lisp]
|
Prev: online shopping
Next: python admin abuse complaint
From: Frode V. Fjeld on 3 Feb 2010 04:33 > On 03/02/2010 09:26, Frode V. Fjeld wrote: >> Where, precisely? I fail to see anything relevant on the dynamic-extent >> reference page. I suspect that the CLHS fails to address the perhaps >> somewhat esoteric problem we're dealing with here. Pascal Costanza <pc(a)p-cos.net> writes: > There is an example in the entry for dynamic-extent. Look for the > paragraph starting with "Most compilers would probably not stack > allocate the argument to g in f [...]" That's this example: (defun g (x) (declare (dynamic-extent x)) ...) (defun f () (g (list 1 2 3))) I don't think this is equivalent to your example. Here, the value of X is declared not to escape from G, and so long as that is true there is no problem. Your example was effectively this: (defun i (&rest args) (declare (dynamic-extent args)) ...) (defun h () (i (list 1 2 3))) Here, even if ARGS (i.e. the cdr-chain of cons-cells) never exits I, you'll still have a problem if using sbcl. I don't think this CLHS example was intended to adress the problem at hand. (Also, I believe the CLHS examples are not to be considered "letters of the law", strictly speaking.) It seems to me the issue narrows down to the precise semantics of dynamic-extent for &rest-lists. Consider first: (let ((x (list <foo>))) (declare (dynamic-extent x)) ...) The singleton list can clearly be stack-allocated, but what about whatever is allocated in <foo>? If <foo> can be somehow shown to be otherwise inaccessible, it can also be stack-allocated, which is reasonable. Now, here's a similar case, assuming inlining: (defun f (&rest args) (declare (dynamic-extent args)) ...) (defun g () (f <bar>)) It seems to me that Paul Khuong's position is that <bar> can be stack-allocated, because the CLHS wording that allows <foo> to be stack-allocated also applies to <bar>. If this is true, I would wager that this was not intentional on the part of the CLHS editors (because of the way it uncharacteristically breaks function modularity), and that the CL community would do well to consider it one of the CLHS buglets. -- Frode V. Fjeld
From: Tim Bradshaw on 3 Feb 2010 05:05 On 2010-02-02 22:57:46 +0000, Pascal J. Bourguignon said: > Tim Bradshaw <tfb(a)tfeb.org> writes: >> >> It needs to know that LIST (or, really >> MY-NON-CL-DEFINED-FUNCTION-RETURNING-A-LIST) does not hang onto any of >> the structure it returns. If it does then that part of the structure >> is not otherwise inaccessible. Obviously it can know this for LIST, >> but it can not know this in general. > > Yes, correct. I spent some time (failing to sleep and) thinking about this last night, and I think I am now somewhat confused. If we consider something like this: (defun dxfc (f &rest l) (declare (dynamic-extent l)) (funcall f l)) Then I think it is clear that: (dxfc #'car 1 2 3) => 1 ; and this is all fine (dxfc #'identity 1 2 3) => error ; and this is not fine But there are then all sorts of odd cases: (apply #'dxfc #'identity (list 1 2 3)) => ? I think this would be bad in two cases: 1. If the compiler is really aggressive, and works out that it knows all about LIST, and arranges life so that a stack-allocated list is created. 2. If the rest list does not share with what LIST returns (it is allowed but not required to share). Then for something like: (apply #'dxfc #'identity (my-function-returning-a-list ...)) => ? I think this would be bad only if the rest list does not share with what the function returns, or (I suppose) if the compiler can do enough analysis to work out that the function returns a result which is otherwise inaccessible. Does that seem right? --tim
From: Alessio Stalla on 3 Feb 2010 05:45 On Feb 3, 9:52 am, Pascal Costanza <p...(a)p-cos.net> wrote: > On 02/02/2010 17:38, Paul Khuong wrote: > > > > > In article<82aavrskg8....(a)netfonds.no>, > > "Frode V. Fjeld"<fr...(a)netfonds.no> wrote: > > >> Paul Khuong<p...(a)pvk.ca> writes: > > >>> At the time the&rest list is bound, everything it contains is > >>> "otherwise accessible". > > >> Agreed, my statement was quite mistaken. Thanks for the explanation. > > > [...] > > >> I agree wrt. your example. However, Pascal's original example was this: > > >> (defun definer (x) > >> (list x)) > > >> (declaim (inline caller)) > > >> (defun caller (&rest args) > >> (declare (dynamic-extent args) > >> (optimize (speed 3) (debug 0) (safety 0) > >> (compilation-speed 0))) > >> (apply #'definer args)) > > >> (defun test () > >> (caller (list 0))) > > >> The question as I understand it is whether the last (list 0) can be > >> stack-allocated. This form is outside the (lexical) scope of the > >> dynamic-extent declaration. I suspect what happens is that inlining > >> "caller" causes (list 0) to be treated as it's in that lexical scope? So > >> if there was no inlining, there would be no error? > > > This is a side-effect of inlining. As the CLHS points out, the limit is > > only what static analyses and the runtime allow you to guarantee. > > > (defun g (x) (declare (dynamic-extent x)) ...) > > (defun f () (g (list 1 2 3))) > > > Most compilers would probably not stack allocate the argument to g > > in f because it would be a modularity violation for the compiler to > > assume facts about g from within f. Only an implementation that was > > willing to be responsible for recompiling f if the definition of g > > changed incompatibly could legitimately stack allocate the list > > argument to g in f. > > > Here, because of, e.g., automatic recompilation, F can assume that G's > > one argument has been declared dynamic-extent. In Costanza's orignal > > example, it is because of inlining that SBCL can assume that the&rest > > list in CALLER has been declared dynamic-extent. However, even without > > inlining, a sufficiently flexible runtime would allow for the exact same > > optimisation. The bug lies not in our compilers but in our assumptions. > > Ok, understood by now. Thanks a lot for your excellent explanations. > > But this effectively means that I can never use dynamic-extent > declarations for &rest arguments, can I? > > (defun foo (... &rest args) > (declare (dynamic-extent args)) > ...) > > Since it is always possible that client code calls this with freshly > allocated data: > > (foo ... (list 1) (list 2)) > > And since compilers are allowed to cross module (function) boundaries > when optimizing for dynamic-extent, this is never safe. Never say never ;) > Or are there circumstances where I can use dynamic-extent for &rest args > safely? You can indeed use it safely, provided that you guarantee that no rest argument (or part of its structure) escapes from your function. There's really no difference from other arguments. I.e. the problem is not &rest nor inlining per se, it's that your function returns a value that shares structure with something which has been stack-allocated. Alessio
From: Pascal Costanza on 3 Feb 2010 05:53 On 03/02/2010 11:45, Alessio Stalla wrote: > On Feb 3, 9:52 am, Pascal Costanza<p...(a)p-cos.net> wrote: >> On 02/02/2010 17:38, Paul Khuong wrote: >> >> >> >>> In article<82aavrskg8....(a)netfonds.no>, >>> "Frode V. Fjeld"<fr...(a)netfonds.no> wrote: >> >>>> Paul Khuong<p...(a)pvk.ca> writes: >> >>>>> At the time the&rest list is bound, everything it contains is >>>>> "otherwise accessible". >> >>>> Agreed, my statement was quite mistaken. Thanks for the explanation. >> >>> [...] >> >>>> I agree wrt. your example. However, Pascal's original example was this: >> >>>> (defun definer (x) >>>> (list x)) >> >>>> (declaim (inline caller)) >> >>>> (defun caller (&rest args) >>>> (declare (dynamic-extent args) >>>> (optimize (speed 3) (debug 0) (safety 0) >>>> (compilation-speed 0))) >>>> (apply #'definer args)) >> >>>> (defun test () >>>> (caller (list 0))) >> >>>> The question as I understand it is whether the last (list 0) can be >>>> stack-allocated. This form is outside the (lexical) scope of the >>>> dynamic-extent declaration. I suspect what happens is that inlining >>>> "caller" causes (list 0) to be treated as it's in that lexical scope? So >>>> if there was no inlining, there would be no error? >> >>> This is a side-effect of inlining. As the CLHS points out, the limit is >>> only what static analyses and the runtime allow you to guarantee. >> >>> (defun g (x) (declare (dynamic-extent x)) ...) >>> (defun f () (g (list 1 2 3))) >> >>> Most compilers would probably not stack allocate the argument to g >>> in f because it would be a modularity violation for the compiler to >>> assume facts about g from within f. Only an implementation that was >>> willing to be responsible for recompiling f if the definition of g >>> changed incompatibly could legitimately stack allocate the list >>> argument to g in f. >> >>> Here, because of, e.g., automatic recompilation, F can assume that G's >>> one argument has been declared dynamic-extent. In Costanza's orignal >>> example, it is because of inlining that SBCL can assume that the&rest >>> list in CALLER has been declared dynamic-extent. However, even without >>> inlining, a sufficiently flexible runtime would allow for the exact same >>> optimisation. The bug lies not in our compilers but in our assumptions. >> >> Ok, understood by now. Thanks a lot for your excellent explanations. >> >> But this effectively means that I can never use dynamic-extent >> declarations for&rest arguments, can I? >> >> (defun foo (...&rest args) >> (declare (dynamic-extent args)) >> ...) >> >> Since it is always possible that client code calls this with freshly >> allocated data: >> >> (foo ... (list 1) (list 2)) >> >> And since compilers are allowed to cross module (function) boundaries >> when optimizing for dynamic-extent, this is never safe. > > Never say never ;) > >> Or are there circumstances where I can use dynamic-extent for&rest args >> safely? > > You can indeed use it safely, provided that you guarantee that no rest > argument (or part of its structure) escapes from your function. > There's really no difference from other arguments. I.e. the problem is > not&rest nor inlining per se, it's that your function returns a value > that shares structure with something which has been stack-allocated. OK, sounds reasonable. I have used dynamic-extent declarations on &rest arguments a lot for the kind of forwarding functions I sketched in my OP. If dynamic-extent (or a similar declaration) would be guaranteed to cover only the conses that make up the &rest argument itself, this would be a useful idiom with what I believe to be a potentially interesting performance gain. Since in general I don't know what the functions that I forward to do with their arguments, I can't use dynamic-extent in those cases. That's a pity. But I now understand why. 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: Waldek Hebisch on 3 Feb 2010 07:22
Paul Khuong <pvk(a)pvk.ca> wrote: > > "otherwise", i.e. not in any sense by going through the binding that was > > declared dynamic-extent. > > No. At the time the &rest list is bound, everything it contains is > "otherwise accessible". What about the following variation: (defmacro safe-caller(x) `(let ((xx ,x)) (caller ,x))) (defun test () (safe-caller (list 0))) in sbcl (at least 1.0.32) calling test still gives error. My interetation of HyperSpec is that `(list 0)' is accesible via xx, so compiler should not stack allocate it. Of course one possible meaning of "otherwise inaccessible part" could be "compiler optimized out all other visible references to it", but that IMHO would make dynamict extent inherently unsafe. -- Waldek Hebisch hebisch(a)math.uni.wroc.pl |