suppose I have an array, `my-array', that's non necessarily adjustable. suppose also that it doesn't have a fill pointer, etc. Say I want to create an array which is a copy of my-array, but such that it has a fill-pointer, is adjustable, etc. Also, I don't care about the original array (i.e. the method can be destructive).
What's the most efficient portable way to do this?
Right now, I am doing:
(setq b (make-array (length my-array) :displaced-to my-array :fill-pointer t :adjustable t))
< < suppose I have an array, `my-array', that's non necessarily < adjustable. suppose also that it doesn't have a fill pointer, etc. < Say I want to create an array which is a copy of my-array, but such < that it has a fill-pointer, is adjustable, etc. Also, I don't care < about the original array (i.e. the method can be destructive). < < What's the most efficient portable way to do this? < < Right now, I am doing: < < (setq b (make-array (length my-array) < :displaced-to my-array < :fill-pointer t < :adjustable t))
If you wanted a seperate copy of the array you could use replace. I think replace is very similiar to memcpy in C; it even takes care of overlapping correctly when both items to be replaced are eq.
Yeah. adjust-array works for non-adjustable arrays. It was un-intuitive to me, so I'd never bothered to check that point. But I noticed that it's non-destructive when you use it on non-adjustable arrays, which is somewhat weird. I guess that since it's not an error to use `adjust-array' on non-adjustable arrays, it's probably more efficient than what I did (e.g. a simple `displaced-to' in a `make-array').
However, using adjust-array to copy destructively a non-adjustable array opens up the question of whether to use `displaced-to' in the `adjust-array' form:
example: want to copy array-1, but make it adjustable, give it a fill-pointer, etc.
(setq array-2 (adjust-array array-1 (array-dimensions array-1) :fill-pointer t :adjustable t))
or
(setq array-2 (adjust-array array-1 (array-dimensions array-1) :fill-pointer t :adjustable t :displaced-to array-1))
This is highly uncertain to me. I'll guess that the latter one is more efficient, as it won't try to copy data over, which is what I was afraid of in the first place.
David Bakhash <ca...@bu.edu> writes: > Yeah. adjust-array works for non-adjustable arrays. It was > un-intuitive to me, so I'd never bothered to check that point. But I > noticed that it's non-destructive when you use it on non-adjustable > arrays, which is somewhat weird.
Think of it like DELETE. It's permitted to adjust the array, but may not always be able to and so is not (i.e., no longer) required to. We used to require it to work by side-effect, but that just led to needless program bugs. (So we traded them for another set of program bugs which we allege are not needless. :-) You're supposed to do (setq x (adjust-array x ...)) and are NOT supposed to just assume it reliably works by side-effect.
> > Yeah. adjust-array works for non-adjustable arrays. It was > > un-intuitive to me, so I'd never bothered to check that point. But I > > noticed that it's non-destructive when you use it on non-adjustable > > arrays, which is somewhat weird.
> to. We used to require it to work by side-effect, but that just > led to needless program bugs. (So we traded them for another set of > program bugs which we allege are not needless. :-) You're supposed to do > (setq x (adjust-array x ...)) > and are NOT supposed to just assume it reliably works by side-effect.
that's really a shame. Some fns really should work by side-effect, and that's one of them. But, in dealing with large strings which are by default not adjustable, w/ fill-pointers, if I want to "adjust" them to have these new properties, I really want a way which doesn't try to copy a string with (potentially) a number of elts in the many hundred to thousand(s).
So, at the end of the day, I went with:
(setq a (adjust-array a (array-dimensions a) :fill-pointer t :adjustable t :displaced-to a))
I suppose that the above not only is guaranteed to work safely, it should be as efficient as possible. I just didn't understand why this is any different from using `make-array' with `:displaced-to' set to the original one. They seem identical, and thus confusing -- esp. when it's critical that things be done efficintly.
> > We used to require it to work by side-effect, but that just > > led to needless program bugs. (So we traded them for another set of > > program bugs which we allege are not needless. :-) You're supposed to do > > (setq x (adjust-array x ...)) > > and are NOT supposed to just assume it reliably works by side-effect.
> that's really a shame. Some fns really should work by side-effect, and > that's one of them.
I think if you think about it, you'll realize this point of view is selfish. It's much easier for you to do
(defun davids-adjust-array (array &rest options-for-the-elite) (if (not (adjustable-array-p array)) (error "I'm not going to let you do this except by side-effect~ ~%even though I could provide you some help here.") (apply #'adjust-array options-for-the-elite)))
than it is for someone who has an application that can tolerate the other form to write something that would extend ADJUST-ARRAY. The solution we chose makes a number of (though not all) limitations of adjust-array go away with the addition of a simple SETQ. Your reaction is natural because you perhaps perceive that an incompatible change was made to accomodate this class of users; however, your program would have signaled an error in this case anyway, and the change was not to the "normal" situation for ADJUST-ARRAY but to the "exceptional" part. That seems a good trade to me. It still works RELIABLY by side-effect if it is able (i.e., if you have planned for it by using :ADJUSTABLE T).
> But, in dealing with large strings which are by > default not adjustable, w/ fill-pointers, if I want to "adjust" them to > have these new properties, I really want a way which doesn't try to copy > a string with (potentially) a number of elts in the many hundred to > thousand(s).
The problem is that you are pointing to a fixed block of storage in most implementations and trying to in-place extend it. e.g. +--------------------------------+ | header | cell1 | cell2 | cell3 | +--------------------------------+ to be +----------------------------------------+ | header | cell1 | cell2 | cell3 | cell4 | +----------------------------------------+ The problem is that this would write over the storage cell next to the array. An adjustable array uses wholly different storage in most implementations, usually of the form: +-----------------------------+ | header | pointer to storage | +-----------------------------+ In this case, you can adjust the array by just doing a conceptual rplacd of the storage. BUT NOTE: The implementation may still have to allocate a new storage block and copy the stuff behind your back. So the identity and side-effect thing is really a red herring. All adjustability is buying you is that the header to which you point doesn't lose its identity in the process. The pointer to storage may still look just like the original array and may still be unable to stretch and you'll be no better off.
Nothing substitutes for advance planning. That's a property of the universe, not of Lisp. The problem is that arrays are by their nature positional, and the nature of positional things is that they may be positioned next to other things who care about their positions, too. You can only push so far...
> So, at the end of the day, I went with:
> (setq a (adjust-array a (array-dimensions a) > :fill-pointer t > :adjustable t > :displaced-to a))
> I suppose that the above not only is guaranteed to work safely, it > should be as efficient as possible.
You're going to lose here if a is adjustable to begin with. You'll have made it point to itself. Think about what happens the second time through.
Also, even if you remove the :DISPLACED-TO, you may not win for the reasons I've cited above.
Personally, I think if you have the one and only one unique pointer to the array such that you can do the setq and it will really update all people who point to it, you're better off with a non-adjustable array and manual replacement of the array by copy-seq or something simpler. It will save you the memory indirect on the access. Both :adjustable and :displaced-to risk some speed on every access due to memory indirect and should not be done unless you need the functionality (e.g., you're communicating with modules who don't understand your storage convention and just want to use a common array abstraction).
> I just didn't understand why this > is any different from using `make-array' with `:displaced-to' set to the > original one. They seem identical, and thus confusing -- esp. when it's > critical that things be done efficintly.
:displaced-to enables sharing and can be cascaded to multiple levels of indirection. adjust-array is a limited form of the same which may buy some speed advantages for same. (I think in a system like the lisp machine with hardware gc pointer forwarding you can get better performance for adjustable arrays than the worst-case portable performance I described above; my recollection is that all arrays on the lispm--or nearly all--are adjustable... hence the funny verbiage about expressly adjustable and so on in the glossary; extra complication to abstract away from the specific properties of specific systems.)
Arrays are terribly complicated in programming in general. CL will provide a variety of services for you to hide the complication, but it doesn't free you from knowing what you are doing--it only frees you from doing the actual programming when it comes down to the details. To the extent that any doc I wrote obscures the intent, you have my apology. Sadly, for all the HyperSpec is legalistically true, this may be one of those points where the disclaimer up front about it not being a tutorial document needs to be taken seriously.
> Sadly, for all the HyperSpec is legalistically true, this may be one > of those points where the disclaimer up front about it not being a > tutorial document needs to be taken seriously.
It's obviously too long for a tutorial, but it's a very good extended man-page/glossary/index. The only part which I know for sure cannot be used as a tutorial is the CLOS part. Though thorough, there's no information there about _how_ CLOS programs should look (IMO). But I'm glad of it. I don't think that belongs in the HyperSpec. It's really handy, and though I have the back of Gram's Lisp book for simple things, I often need the HyperSpec to understand the internals better. (i.e. thanks).
In article <wkbtkmxgoo....@mit.edu>, David Bakhash <ca...@mit.edu> wrote: (...)
> (setq a (adjust-array a (array-dimensions a) > :fill-pointer t > :adjustable t > :displaced-to a))
> I suppose that the above not only is guaranteed to work safely, it > should be as efficient as possible. I just didn't understand why this > is any different from using `make-array' with `:displaced-to' set to the > original one. They seem identical, and thus confusing -- esp. when it's > critical that things be done efficintly.
MAKE-ARRAY always creates a new array object (i.e. one that is not EQ to anything else); ADJUST-ARRAY may or may not create a new object.
More importantly, how legal is it to have an array displaced to itself? (This must be one of my stupid evenings but I was not able to figure it out by myself.)
I would say that literature about Lisp comes in three layers (Gallia omnia...):
* books that teach Lisp (Winston & Horn, Norvig, whatever); * books that explain Lisp (CLtL); * books that define Lisp (HyperSpec).
And one ought to read literature from all three. Then one may become enlightened (being hit on the head with a thick InterLisp manual also helps I guess...).
In article <76e2ku$a1...@nnrp1.dejanews.com>, <vniko...@poboxes.com> wrote: >More importantly, how legal is it to have an array displaced to >itself? (This must be one of my stupid evenings but I was not >able to figure it out by myself.)
What could this possibly mean? A displaced array doesn't have any storage, it's simply an alias for another array. AREF has to follow the displacement links and find real storage cells eventually.
-- Barry Margolin, bar...@bbnplanet.com GTE Internetworking, Powered by BBN, Burlington, MA *** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups. Don't bother cc'ing followups to me.
In article <8Dwi2.44$%y.2...@burlma1-snr1.gtei.net>, Barry Margolin <bar...@bbnplanet.com> wrote:
> In article <76e2ku$a1...@nnrp1.dejanews.com>, <vniko...@poboxes.com> wrote: > >More importantly, how legal is it to have an array displaced to > >itself? (This must be one of my stupid evenings but I was not > >able to figure it out by myself.)
> What could this possibly mean? A displaced array doesn't have any storage,
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> it's simply an alias for another array. AREF has to follow the > displacement links and find real storage cells eventually.
That's what I am asking, since this example was posted recently:
(setq a (adjust-array a (array-dimensions a) ;; ^ ^ :fill-pointer t :adjustable t :displaced-to a)) ;; ^
Doesn't look right to me but I am not sure I am not missing anything.
In article <8Dwi2.44$%y.2...@burlma1-snr1.gtei.net>, Barry Margolin <bar...@bbnplanet.com> wrote:
> In article <76e2ku$a1...@nnrp1.dejanews.com>, <vniko...@poboxes.com> wrote: > >More importantly, how legal is it to have an array displaced to > >itself? (This must be one of my stupid evenings but I was not > >able to figure it out by myself.)
> What could this possibly mean? A displaced array doesn't have any storage,
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> it's simply an alias for another array. AREF has to follow the > displacement links and find real storage cells eventually.
That's what I am asking, since this example was posted recently:
(setq a (adjust-array a (array-dimensions a) ;; ^ ^ :fill-pointer t :adjustable t :displaced-to a)) ;; ^
Doesn't look right to me but I am not sure I am not missing anything.
vniko...@poboxes.com writes: > > What could this possibly mean? A displaced array doesn't have any storage, > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > > it's simply an alias for another array. AREF has to follow the > > displacement links and find real storage cells eventually.
I think what you meant was that if it wants to find real storage cells eventually, it needs to not be a circular arrangement. ;-)
> That's what I am asking, since this example was posted recently:
> (setq a (adjust-array a (array-dimensions a) > ;; ^ ^ > :fill-pointer t > :adjustable t > :displaced-to a)) > ;; ^
> Doesn't look right to me but I am not sure I am not missing anything.
Didn't look right to me either. Not sure it's illegal. But neither are circular lists and they're sometimes troublesome, too. Not every thing that's wrong to do is invalid in the spec; the same is true of life, btw.
In case you wondered if this was supposed to optimize out into a displacement to a's old underlying storage, there's no promise to that effect. Moreover, it wouldn't always be possible, which is why the array is being adjusted in the first place in many (perhaps most) cases--the underlying array is too small and needs to be discarded for a larger one. AND FINALLY, implementations are expressly forbidden from collapsing "unnecessary" levels of indirection in displaced arrays--that is, even if an implementation wanted to do something clever here (though I can't imagine anything that is both clever and unambiguously right), it would be forbidden to.
