The is an extension of the idea of versioned arrays where any object that holds data can be versioned. This provides a reasonably cheap method of storing objects without many differences between them.
What does it do?
Basically it allows you to treat any object in Common Lisp that can be mutated as an immutable object while only requiring O(N+m) space to store it and O(m) work to make the copy (where N is the size of the object and m is the number of edits differentiating the two objects). It accomplishes this by wrapping the object in a structure and storing one object and a versioning tree of all of the edits connecting the various versions. It works very well for problems where you are interested in a set of objects that are only a few edits apart. In fact, in this particular case, the asymptotic behavior is constant time, just like with normal mutable objects.
Objects are created normally and converted to versioned objects using the
version. Once an object has been “versioned,” it has essentially been
converted into a immutable data type with reasonable asymptotic access and
modification behavior. To access data within your versioned object, use the
vapply with the ordinary accessor function you would
use. New versions are made via the
vmodf macro, which behaves much like the
modf macro from the Modf library, which in turn is based on the
Where does this fit in?
You may have noticed that this library has a lot in common with Modf. That is because they are used to solve the same problem but for different limits of that problem. Modf is good for objects that can be modified with little copying, be they small or share structure with other versions. Think lists, binary trees, small arrays (less than 30 elements or so, depends on the implementation). Versioned-objects is useful for objects that are expensive to copy. Think arrays or hash tables with thousands to millions of elements/keys.
Where does this work?
The functionality in Versioned-Objects is rather straight forward and implemented in portable Common Lisp apart from the multi-threading stuff (which thanks to Bordeaux-Threads, should seamlessly go away on threadless install). No MOP tricks or heuristics are needed. I dare say that if you have an ANSI compliant Lisp, this should work. Even if you don’t, it might.
I test regularly (and mostly successfully) in SBCL, CMUCL, CCL, ECL, CLISP, and ABCL.
This library is asymptotically quite efficient (if you are using it for the right purpose) and “okay” in practice. Some un-scientific and anecdotal benchmarks suggest that a backtracking algorithm written using this is a factor of ~15 or so slower than a similar algorithm written in a destructive manner. This is on par with the performance of functional data structures.
There are some plans to speed things up for specific data types like arrays and hash tables. Also, I’m looking into speeding things up when you are trying to use it with objects with many edits separating them.
Keep in mind that this kicks the pants off actually copying your data, which is the other option if you insist on using a mutation only data structure like a Lisp array and insist on using it in a functional way.
This library involves mutation and thus “thread safety” and general contention for data access between all versions of the data is a concern. In fact, due to the odd nature of what we are doing (i.e. allowing the user to access the data using standard Lisp functions as opposed to special “versioned” accessor function), there is actually contention of the versioned object within a single thread due to the fact that the thread might want to access different versions at the same time. Some work has been done ensuring that you won’t have a deadlock situation, but more work needs to be done.
Ugh, something went horribly wrong!
Okay, calm down, we’ll get through this. This library is tricky to debug. The
very first thing to do is set
nil. That way introspection won’t actually modify your objects, thereby
removing or introducing new bugs. Then you might place traces on
This is an ASDF package.
Not many dependencies, yay:
Additional dependencies for the test suite:
This is a pretty simple piece of code so I am publishing it under the 3 clause BSD license. It follows:
Copyright (c) 2011, Zach Kost-Smith All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
- Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
- Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
- Neither the name of the <organization> nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.