How to use dynamic-extent declarations...
in [Lisp]
|
Prev: online shopping
Next: python admin abuse complaint
From: Paul Khuong on 2 Feb 2010 11:38 In article <82aavrskg8.fsf(a)netfonds.no>, "Frode V. Fjeld" <frode(a)netfonds.no> wrote: > Paul Khuong <pvk(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. > In other words, it seems to me that the question is not one of how > dynamic-extent works, but rather the interplay between inlining and > dynamic-extent declarations. Shouldn't you be able to declare something > inline without having to concern yourself with whether some particular > (or rather every) combination of caller and callee is compatible? It > seems clear to me that you want inlined forms to inherit e.g. type > declarations from the surrounding lexical environment, but less clear > that dynamic-extent declarations should be propagated. What you object to is fairly clearly described as the intent and meaning of dynamic-extent declarations in the CLHS. The OP's common misunderstanding does however make a strong argument for some extension providing a LEXICALLY-DYNAMIC-EXTENT declaration. I'll leave the details regarding compilation units to the readers. Paul Khuong
From: Tim Bradshaw on 2 Feb 2010 12:22 On 2010-02-02 16:33:31 +0000, Pascal J. Bourguignon said: > It's just that in that case, the compiler doesn't profit from the > dynamic-extent declaration, but if it was smarter or harder-working, > it could still allocate the argument specially. I think it can only do this if it knows (which, obviously, it can do) enough about LIST.
From: Pascal J. Bourguignon on 2 Feb 2010 14:25 Tim Bradshaw <tfb(a)tfeb.org> writes: > On 2010-02-02 16:33:31 +0000, Pascal J. Bourguignon said: > >> It's just that in that case, the compiler doesn't profit from the >> dynamic-extent declaration, but if it was smarter or harder-working, >> it could still allocate the argument specially. > > I think it can only do this if it knows (which, obviously, it can do) > enough about LIST. I imagine it doesn't need to know anything about LIST. It only needs to have a hook in the low-level allocator. Something like: (defvar *zone* (make-garbage-collected-heap)) (defun malloc (tag size) (allocate-in-zone *zone* tag size)) (defun cons (a d) (let ((k (malloc 'cons (size-of 'cons)))) (setf (car k) a (cdr k) d) k) ;; and similarly for other constructors. Then when compiling: (defun test () (caller (list 0))) it could check if the arguments are dynamically-scoped and generate in that case something like: (let ((old-zone *zone*) (*zone* (make-pascal-heap))) (unwind-protect (let ((arg (list 0))) ; bind dynamic-extend parameters. (let ((*zone* old-zone)) ; put back the gc heap. (caller arg))) (free-pascal-heap *zone*))) ; deletes all the objects allocated in that heap. -- __Pascal Bourguignon__
From: Duane Rettig on 2 Feb 2010 14:30 On Feb 2, 8:33 am, p...(a)informatimago.com (Pascal J. Bourguignon) wrote: > Pascal Costanza <p...(a)p-cos.net> writes: > > On 02/02/2010 16:40, Tim Bradshaw wrote: > >> On 2010-02-02 14:00:57 +0000, Pascal Costanza said: > > >>> There should be a 'shallow dynamic-extent' declaration that doesn't > >>> reach out for objects allocated at the call site... > > >> Does this happen when the function is not declared inline? > > > No, then everything is fine. > > ... _appears_ to be fine. > > It's just that in that case, the compiler doesn't profit from the > dynamic-extent declaration, You didn't actually try this, did you? but if it was smarter or harder-working, > it could still allocate the argument specially. If you try Pascal C's original example without the inline declaration, disassemble caller, then try it once more with the dynamic-extent declaration removed, you'll find that the compiler did indeed profit from the dynamic-extent declaration, even without the inline declaration. Duane
From: Paul Khuong on 2 Feb 2010 16:11
In article <87eil3xww0.fsf(a)informatimago.com>, pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: > I imagine it doesn't need to know anything about LIST. > > It only needs to have a hook in the low-level allocator. > > Something like: > > (defvar *zone* (make-garbage-collected-heap)) > > (defun malloc (tag size) (allocate-in-zone *zone* tag size)) > > (defun cons (a d) > (let ((k (malloc 'cons (size-of 'cons)))) > (setf (car k) a > (cdr k) d) > k) Nope. A function can cons stuff up without (only) returning it. A trivial example would be a cache system. Not *all* consing performed while computing a value that will be bound to a dx variable will end up being otherwise unreachable. Paul Khuong |