How to use dynamic-extent declarations...
in [Lisp]
|
Prev: online shopping
Next: python admin abuse complaint
From: Paul Khuong on 3 Feb 2010 08:55 In article <82fx5ir7e1.fsf(a)netfonds.no>, "Frode V. Fjeld" <frode(a)netfonds.no> wrote: > > 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. Does this example not completely break the modularity barrier of functions, the exact same argument you use to argue against my interpretation of the specification's wording? A consequence of dynamic-extent applying to the example above, in (defun h () (let ((y (list 1 2 3))) (g y) y)) the whole list bound to y can still be stack allocated! When x (declared dynamic-extent) is bound to (1 2 3), the only reference to (2 3) is the head of (1 2 3), and similarly for (3). Thus, the whole list is otherwise inaccessible, and, when the execution of G terminates, all 3 conses are supposed to be inaccessible. The consequence is that a compiler is now allowed to stack-allocate the whole list, regardless of the binding to Y. Finally, what if the argument to G had instead been (list 1 (list 2) 3)? Would you expect the inner (list 2) to be heap allocated? What if it was instead (list* 1 (list 2 3)) or (cons 1 (cons (cons 2 nil) (cons 3 nil)))? Specifying the meaning of a dynamic-extent declaration (which, let us remember, applies to a *variable* and affects *all* the values ever bound to it) is a dubious effort at best. > 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. Args is bound to *a cons*. Everything else is convention. > (Also, I believe the CLHS examples are not to be considered > "letters of the law", strictly speaking.) They should give a pretty good hint at what the authors meant though... > It seems to me the issue narrows down to the precise semantics of > dynamic-extent for &rest-lists. It seems to me the problem is with &rest *lists*. A specialised (dx-by-default even!) ADT would have been more useful. Paul Khuong
From: Paul Khuong on 3 Feb 2010 09:04 In article <7st2tmFia8U1(a)mid.individual.net>, Pascal Costanza <pc(a)p-cos.net> wrote: > >>>> (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))) [...] > 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. Sounds like a job for compiler macros to me. Not only can do you all sorts of argument list parsing at compile-time, but you can also expand into something like: (let ((rest-list (make-list n))) (declare (dynamic-extent rest-list)) (setf ...) ; the macro should probably expand into direct calls to ; CONS in order to keep references to each cons. (%foo ... rest-list)) Paul Khuong
From: Pascal Costanza on 3 Feb 2010 11:14 On 03/02/2010 15:04, Paul Khuong wrote: > In article<7st2tmFia8U1(a)mid.individual.net>, > Pascal Costanza<pc(a)p-cos.net> wrote: >>>>>> (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))) > [...] >> 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. > > Sounds like a job for compiler macros to me. Not only can do you all > sorts of argument list parsing at compile-time, but you can also expand > into something like: > > (let ((rest-list (make-list n))) > (declare (dynamic-extent rest-list)) > (setf ...) ; the macro should probably expand into direct calls to > ; CONS in order to keep references to each cons. > (%foo ... rest-list)) Interesting idea. Thanks. 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: Duane Rettig on 3 Feb 2010 13:15 On Feb 3, 8:14 am, Pascal Costanza <p...(a)p-cos.net> wrote: > On 03/02/2010 15:04, Paul Khuong wrote: > > > > > > > In article<7st2tmFia...(a)mid.individual.net>, > > Pascal Costanza<p...(a)p-cos.net> wrote: > >>>>>> (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))) > > [...] > >> 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. > > > Sounds like a job for compiler macros to me. Not only can do you all > > sorts of argument list parsing at compile-time, but you can also expand > > into something like: > > > (let ((rest-list (make-list n))) > > (declare (dynamic-extent rest-list)) > > (setf ...) ; the macro should probably expand into direct calls to > > ; CONS in order to keep references to each cons. > > (%foo ... rest-list)) > > Interesting idea. Thanks. Interesting, yes, but not portable for its intention; it might work, but also it either might not work or it might have horrible performance: - The hand-waving over those "direct calls to CONS" really means that variables would be needed, and if the variables are not used somewhere then they become dead and the compiler can elide them. - If the variables are explicitly saved by being used in some artificial code (e.g. sent to some no-op function) then whatever that artificial means would be would be extra code added to the prologue of the function. Perhaps if non-consing is the absolute requirement here, that might be an acceptable solution. I've been following this conversation with interest, because it is a perplexing issue. The intention of dynamic-extent is understandable, and it is clear that the "otherwise inaccessible part" doctrine should apply to all parts of an object, which means it applies to trees as well as lists. What is not clear to me is whether in a philosophical sense a &rest argument is a single object or a list of objects. Obviously, to a function f with &rest x, x is a single object, but to a function g which calls f with arguments a, foo, and framis, all three of these arguments are unrelated and should not, in my opinion, be conflated as one object. I believe that the spec does support this philosophical view. Since it is the examples section that is under scrutiny, and provides the ambiguity, we should examine the text of the &rest example: " A variant of this is the so-called "stack allocated rest list" that can be achieved (in implementations supporting the optimization) by: (defun f (&rest x) (declare (dynamic-extent x)) ...) Note that although the initial value of x is not explicit, the f function is responsible for assembling the list x from the passed arguments, so the f function can be optimized by the compiler to construct a stack-allocated list instead of a heap-allocated list in implementations that support such. " Note that here the example is calling for the stack allocation of a _list_, not a structure, as it does in a second &rest example below it. Finally, let's remember what a declaration is: the dynamic-extent declaration is _not_ a request for stack allocation, but a _promise_ that the data conforms to the constraints of the declaration (in this case, the variable's content's extent is dynamic and not captured). Your original example assumes that there is a dynamic-extent component to the final structure of the &rest argument, and indeed you only return parts of that which are not part of that assumption. Whether the whole &rest argument is included as part of that dynamic-extent declaration, or whether just the top-level list is part of it, is interpretable by the CL implementation. (I believe that Allegro CL would always interpret a declaration on the &rest argument to pertain to its top-level list only). If your CL implementation interprets it the other way, then your dynamic-extent declaration is in error, because the truth of the promise is based on the assumption that only the top level list is involved in the declaration, which in the implementation in question becomes a false assumption. Duane
From: Duane Rettig on 3 Feb 2010 14:43
On Feb 3, 10:15 am, Duane Rettig <du...(a)franz.com> wrote: > Note that here the example is calling for the stack allocation of a > _list_, not a structure, as it does in a second &rest example below > it. Correcting what could be misunderstood logic; my unfortunate wording above might imply that the second example talks about stack-allocation of a structure. It does not; both &rest examples agree in dealing with lists. Duane |