5 ms·
I'm amazed it literally has a class public final class Cons extends LispObject { public LispObject car; public LispObject cdr; } I wou
by chrisseaton 7y ago
I'm amazed it literally has a class
public final class Cons extends LispObject
{
public LispObject car;
public LispObject cdr;
}
I would have thought it would provide that abstraction to the programmer but use another representation internally. Chasing pointers like this on modern hardware is surely crazy?
- ken 7y agoLast I heard (years ago), some Lisp implementations had tried using arrays for non-branching cons chains, but found that performance wasn't actually better than actual conses in general.
- msla 7y agohttps://en.wikipedia.org/wiki/CDR_coding https://en.wikipedia.org/wiki/CDR_coding > In computer science CDR coding is a compressed data representation for Lisp linked lists. It was developed and patented by the MIT Artificial Intelligence Laboratory, and implemented in computer hardware in a number of Lisp machines derived from the MIT CADR. > CDR coding is in fact a fairly general idea; whenever a data object A ends in a reference to another data structure B, we can instead place the structure B itself there, overlapping and running off the end of A. By doing this we free the space required by the reference, which can add up if done many times, and also improve locality of reference, enhancing performance on modern machines. The transformation is especially effective for the cons-based lists it was created for; we free about half of the space for each node we perform this transformation on.
- aidenn0 7y agoCDR coding isn't really used because lisp now has standardied vectors, and one big reason to use lists over vectors is the ability to share structure.
- ts4z 7y agoA lot of things in Lisp force the implementation of lists as cons cells. It’s probably possible to do something different, but no one has, and the result won’t be a Common Lisp. (Consider that the detail of improper lists is enshrined in the language.)
- deleted 7y ago[deleted]
- lokedhs 7y agoCommon Lisp does have proper arrays as well, which can be used if the situation calls for it. As it turns out, arrays aren't actually used that much (except for strings of course) in CL code. Most lists are just a few elements long, and regular lists are perfect for that.
- dreamcompiler 7y agoI use arrays much more than lists, for the same reasons arrays are useful in any language. Plus they're dynamically resizable and you can map across them in Lisp just like lists. For many purposes arrays are a much better choice than lists in CL.
- lokedhs 7y agoDefinitely nothing wrong with that. When manipulating large sets of data, they are definitely necessary.
- ts4z 7y agoThe structure of a list is still exposed, and that decision is baked into the essence of Lisp. If you have a list, you cannot substitute a skip list or an array. If you have a skip list, it is (I think) not a language-level sequence and so things like rest and nth won’t work on it. Arrays, struts, all other things are possible, but the things that make Lisp Lisp mean that you may get a list where repeatedly calling cdr may result in something that is not listp (cons or nil). And that’s weird. It enables some things that are wonderful, but I think the Lisps are practically unique in conflating pairs and list elements.
- ts4z 7y agoI bet CL allows generalizing nth and cdr. My point is still that the list structure in Lisp is very baked into the language.
- p_l 7y agoBecause CONS cells aren't used only for lists, but are fundamental data type used as building blocks for few other things. As such, they are required to hold any value or reference possible, and aren't exactly amenable to different format. There is one technique which had somewhat large use, CDR-coding, based in the idea that you can tag a cell in a way that tells the system that the next field isn't a reference to a CONS cell, but the CAR of one, and thus linearize lists in memory. However, doing it fast requires a custom cpu so you can resolve this fast in transparent way, as well as it turned out to not give much benefit. However, widening gap between cpu and memory might make it attractive again...
- msla 7y agoIn addition to cons cells being forced in some scenarios, this is Common Lisp, not Lisp 1.5: Programmers who want performance for linear collections are expected to use data types like vectors, which are primitive and not implemented in terms of cons cells at all. http://www.gigamonkeys.com/book/collections.html http://www.gigamonkeys.com/book/collections.html > Vectors are Common Lisp's basic integer-indexed collection, and they come in two flavors. Fixed-size vectors are a lot like arrays in a language such as Java: a thin veneer over a chunk of contiguous memory that holds the vector's elements.2 Resizable vectors, on the other hand, are more like arrays in Perl or Ruby, lists in Python, or the ArrayList class in Java: they abstract the actual storage, allowing the vector to grow and shrink as elements are added and removed.
- lispm 7y agoWe're using object-oriented languages like Java on modern hardware, so pointer chasing is quite natural. Typical Java programs will do that all the time. In many ways the Java runtime is relatively similar to a Lisp runtime - it's just not tailored on the low-level to Lisp - for example cons cells for linked lists are not provided on the virtual machine level. Since lists in typical Lisp implementations are made with cons cells, some form of two element data structure is needed. Using Java objects has the drawback, that this is not the most efficient representation. Good Lisp implementations typically make sure that the cons cell has very little overhead: * cons cells are just objects made of two memory words without type tag. The tag is encoded in pointers to these cons cells. * cons cells can directly encode some simple data like fixnum integers, characters, ... * cons cells might be allocated in special memory regions and GCs might take special care OTOH, more efficient low-level representations like CDR-coding, which allows some lists to be represented in vector like ways is mostly not used in current implementations, since it was not see worth the effort anymore - it was thought worth on older systems with much small main memories than we have today. Smaller main memories than the caches on a modern CPU.
- ernst_klim 7y ago>Typical Java programs will do that all the time. True, especially considering that parametric polymorphism is done via "everything is a pointer" way (although I've heard something about introducing "value types" in Java in the future). Also Common Lisp's pairs are heterogeneous, polymorphic by nature, so I doubt there could be any other solution but pointers. For performant computations you would need unboxed arrays in Java, just as you would use SIMPLE-ARRAY in Common Lisp (which should be implemented efficiently in ABCL as well).