How to use dynamic-extent declarations...
in [Lisp]
|
Prev: online shopping
Next: python admin abuse complaint
From: Paul Khuong on 3 Feb 2010 14:48 In article <bfa93c21-9f4d-4111-8119-711934618bad(a)t31g2000prh.googlegroups.com>, Duane Rettig <duane(a)franz.com> wrote: > On Feb 3, 8:14�am, Pascal Costanza <p...(a)p-cos.net> wrote: > > On 03/02/2010 15:04, Paul Khuong wrote: > > > 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. You misunderstand the hand-waving. The comment about keeping references to the conses is only in order to avoid having to walk the list when (SETF CAR)-ing through it. There is no need for any additional work to make the construct safe. For instance, while (let ((list (make-list 3))) ; at the time LIST is bound, (declare (dynamic-extent list)) ; only the toplevel list is (setf (first list) 1 ; reachable through it. (second list) 2 (third list) 3) (%foo ... list)) would work (the contents of the dx list are not infected with dx-ness), it's an obvious optimisation to instead (let* ((third (list nil)) (second (cons nil third)) (first (cons nil second))) (declare (dynamic-extent third second first)) (setf (car first) 1 (car second) 2 (car third) 3) (%foo ... first)) Paul Khuong
From: Pascal J. Bourguignon on 3 Feb 2010 17:04 Tim Bradshaw <tfb(a)tfeb.org> writes: > 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 I have a problem with this. It works because 1 is a fixnum. But what about: (dxfc #'car (1+ most-positivie-fixnum) 2 3) ? Shouldn't the bignum be of dynamic-extent too? Then shouldn't this function call be an error too? What about implementations who internalize some bignums? What about implementations who box fixnums? > 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? Or perhaps the (&rest args) (declare (dynamic-extent arg)) case is a special case (the wording of CLHS tend to mean that the list args is built by the callee, and that anything that is allocated by the caller is not covered by this declaration. -- __Pascal Bourguignon__
From: Frode V. Fjeld on 3 Feb 2010 17:42 > In article <82fx5ir7e1.fsf(a)netfonds.no>, > "Frode V. Fjeld" <frode(a)netfonds.no> wrote: >> (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. Paul Khuong <pvk(a)pvk.ca> writes: > 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? Not in my opinion, no. > 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! Inlining g into f, I would expect the compiler to at some stage see something more or less equivalent to this: (defun f () (let ((x (list 1 2 3))) (declare (dynamic-extent x)) ... <body of g>)) Doing the same thing for g and your h: (defun h () (let ((y (list 1 2 3))) (let ((x y)) (declare (dynamic-extent x)) ... <body of g>) y)) I see no reason why the compiler should consider the (list 1 2 3) in this case to be dynamic-extent, and I don't think that I've said anything to that effect. > 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. I don't understand. When x is bound to (1 2 3) that list is already extant, so there is no opportunity at that point to consider any allocation mechanism. > 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. I don't think exchanging (list 1 2 3) above with any of these alternatives changes anything. I think this example is more relevant to the issue of &rest-lists, the variable b here playing the part of an &rest: (defun foo () (let ((a (list 0))) (let ((b (list a))) (declare (dynamic-extent b)) ...) ...)) It seems to me that by your interpretation, this (list 0) can be stack-allocated? I would disagree. -- Frode V. Fjeld
From: Tim Bradshaw on 4 Feb 2010 05:41 On 2010-02-03 22:04:22 +0000, Pascal J. Bourguignon said: > I have a problem with this. It works because 1 is a fixnum. Well, I chose immediate objects deliberately :-) > But what about: > > (dxfc #'car (1+ most-positivie-fixnum) 2 3) > > ? > > Shouldn't the bignum be of dynamic-extent too? > Then shouldn't this function call be an error too? > What about implementations who internalize some bignums? > What about implementations who box fixnums? I think this is an error, yes. If the implementation interns bignums then I think that this then becomes the same case as my stashing-list case: unless the implementation can *prove* that the function which returns the structure which may be dx, then it should not treat it as dx (so in that case it's OK in fact, but clearly you can not rely on this). Note that it would require, I think, a significantly heroic implementation to actually run into trouble in this case I think, because it would either have to make a stack-allocted copy of the bignum (and why would it do that?), or cause 1+ to call some special version of the bignum allocator. (I can see this is much easier where there is a direct call to LIST in the arguments to APPLY).
From: Pascal Costanza on 4 Feb 2010 07:14
On 03/02/2010 19:15, Duane Rettig wrote: > 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: The spec may or may not support this philosophical view. However, what is important when writing portable code is that you have to expect that some implementations _may_ take the more 'aggressive' (for lack of a better term) interpretation. Since the spec is at least ambiguous in this regard, you cannot blame them, so you have to account for that fact. As long as you write code for one particular implementation, you can of course check that implementation's documentation and then base your decisions on what it does and does not promise to do for dynamic-extent declarations. What can always be enlightening in such discussions is to read what CLtL2 has to say about such issues - more often than not, there is more text, or different wordings, that reveal something about the original intentions of a construct that got added to Common Lisp. With regard to dynamic-extent, it has the following to say: "The dynamic-extent declaration should be used with great care. It makes possible great performance improvements in some situations, but if the user misdeclares something and consequently the implementation returns a pointer into the stack (or stores it in the heap), an undefined situation may result and the integrity of the Lisp storage mechanism may be compromised. Debugging these situations may be tricky. Users who have asked for this feature have indicated a willingness to deal with such problems; nevertheless, I do not encourage casual users to use this declaration." (cf. Section 9.2) That was exactly the mistake I made in my code: I used dynamic-extent declarations too casually and too liberally, when their intention was clearly to be used for fine-tuning performance when something has been identified as a bottleneck. If a dynamic-extent declaration on a &rest argument list turns out to be a win in a particular situation, it's probably also possible to rearrange the code in such a way that the problem I sketched in my OP doesn't show up. I understand Paul's comments as suggesting one possible such way, not as a replacement for dynamic-extent for casual use. 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/ |