Source
r/lisp•
-6502-

Is the cons cell really such a good idea?

What is so cool about the cons cell idea? Representing all lists that way is horrible for computers (so bad that even back then they had to invent tricks over that, like cdr-coded lists) and also horrible for humans (and indeed explicit code is required for not showing you or parsing explicitly all those chains).

From a conceptual point of view I don't see the cons cell really simpler than a fixed size dynamically allocated array. If I can understand a 2-cells entity then why not 3 or 4, or 1, or 0? Indeed a cons cell is just a special case of a fixed size array.

Linked lists are great (and fantastic for some use cases), but they're not as powerful as arrays providing O(1) indexed access. Building efficient complex structures is a lot easier with atoms and fixed-sized arrays than with just atoms and cons cells.

What am I missing?

Posted Aug 23, 2020, 4:35 PM UTC

2056
kazkylheku•

cons cells are the simplest example of a persistent data structure. Not persistent in the sense of mass storage, but with that other meaning: a persistent data structure is one we can extend using a pure functional operation. That means we efficiently calculate/construct a new object based on the existing object, without altering the existing one (and thus without having any effect on any code that holds the existing one).

cons cells are probably the only persistent data structure that can be implemented in a few simple lines of assembly language, which explains why they were discovered so early by the Lisp researchers.

If you have cons-cell based list like (1 2 3), not only does it cost next to nothing to turn it into (0 1 2 3), but the (1 2 3) part is not touched at all. New memory is allocated for just the cell that holds the 0.

Now persistent vectors and other structures are possible also, but those came decades after the cons cell, and have much more complicated internals, and use tradeoffs and costs that are not always clear. The cons cell has simple internals. The cost of everything you do with cons cells is obvious, especially if you open-code it yourself instead of relying on complex operations in library functions.

The other nice thing about cons cells is that given (0 1 2 3), you can obtain the suffix (1 2 3) without allocating any memory, just by chasing one pointer. This is very nice for recursion. A Lisp code walker that recurses over code hardly has to allocate any memory, if it isn't transforming the code.

Incidentally, null terminate C strings also have this property. The C library function strchr (look for a character in a string and return a pointer to it) could be written like this:

char *strchr(const char *s, int ch)
{
   if (*s == ch) /* including ch == 0 case */
     return s;
   if (*s)
     return strchr(s + 1, ch); /* tail call */
   return NULL; /* not found */
}

If s is a non-empty string in C, then s + 1 is also a string: the suffix of that string which removes one character. That's just like if l is a non-empty list in Lisp, then (cdr l) is the rest of that list. The above is a good way to dispatch clueless people who criticize null-terminated strings from an uninformed, one-sided perspective.

Yet one more advantage of cons cells is that they are all of the same size. This means that heap structures which are dedicated to cons cells are completely devoid of internal fragmentation. A Lisp image can churn cons cells all day long, and never fragment its memory by doing so.

cons cells can be made lazy, in fairly easy, straightforward ways.

So that is to say, you can express lists that are too large to fit into memory all at once, or that are even infinite.

For instance, this operation doesn't read all of /var/log/syslog:

0:sun-go:~/$ txr
This is the TXR Lisp interactive listener of TXR 242.
Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet.
1> (take 5 (file-get-lines "/var/log/syslog"))
("Aug 23 00:07:57 sun-go colord[910]: failed to get session [pid 4950]: No data available"
 "Aug 23 00:10:08 sun-go gnome-shell[2098]: Object .Gjs_AppIndicatorIconActor__1 (0x4c45460), has been already finalized. Impossible to set any property to it."
 "Aug 23 00:10:08 sun-go gnome-shell[2098]: Object .Gjs_AppIndicatorIconActor__1 (0x70d8d70), has been already finalized. Impossible to set any property to it."
 "Aug 23 00:10:08 sun-go org.gnome.Shell.desktop[2098]: == Stack trace for context 0x2603878 =="
 "Aug 23 00:10:08 sun-go org.gnome.Shell.desktop[2098]: #0     0xbfad43f0 I   resource:///org/gnome/gjs/modules/_legacy.js:83 (0x96688fa0 @ 87)")

it generates a lazy list of the lines of /var/log/syslog. Then the first five are taken from that.

Similarly, we can take the first five from the infinite list of integers starting with 1.

2> (take 5 (range 1))
(1 2 3 4 5)

The following expression runs in constant memory. It's looking for a particular large number in an infinite lazy list of integers, which is too large to fit into memory. As the find function marches down the list, it loses track of the beginning of the list, and so that part of the list is garbage collected. The part of the list not yet visited doesn't exist yet:

3> (find (expt 2 32) (range 1))

You can't do that with an array, unless you have some exceptionally remarkable array structure. (I.e. not related to the actual arrays in everyday languages that you know).

Cons cellls are useful simply as pairs also. In programing, we sometimes need to glue two items together as a pair, and the cons cell does that well in many situations. A lot of languages have a pair type. Haskell has a way to "cons" items together to make pairs. That's a bit like a cons cell. C++ has a std::pair template that is a bit like a cons cell. Scheme uses the "pair" terminology for cons cells. C++ having std::vector doesn't make std::pair useless.

45
S_Nathan•

As a practical side-note to this: The ability to do functional programming on such a simple datastructure is the reason why code is represented as lists. For macroexpansions (and for what compilers do in general) it is very important, or at least very useful, to work with functional code.

In macros in a modern lisp this is important because we never know how often a macro might be expanded.

So the lesson is: lists have their disadvantages for many applications, but they are an excellent choice to represent code. Representing code is what lists are mainly for, not number crunching or mass data wrangling.

7
-6502-OP•

The "changes" you can do are only PRE-pending an element to the list. Placing the value as element inside other values is possible with any representation using references.

Prepending is in my experience not such a common operation; actually more common is APPENDING at the end, not at the beginning, and that with cons cells is impossible without altering the content. Also very common is concatenation, but that also requires mutation or copy. Altering the content of cons cells is possible and the appending operation is so frequent that Lisp code quite often uses the push/nreverse approach (you build the result in reverse order you want it and then flip all the CDR links at once). The other way is traversing the whole list and mutate last cons cell like nconc does for all but last argument.

The very common need for mutation is IMO also the reason that in CL first returns the first element, and somewhat surprisingly last returns the last cons cell instead, not last element.

Static arrays cannot grow, but what you can do (and that basically all languages in a way or another support, including common lisp as vector-push-extend) is using static arrays with a fill pointer and reallocation.

Fill pointers and reallocation use more memory than the actual content you care about, but still even using a fixed 2 as grow factor the memory used in the worst case is the same as a linked list (and you have O(1) random access).

Linked cons cells lists only are special about sharing tails, and while for sure it's a use case, in my experience it's not such a common one (and nothing prevents you from building linked lists if you want them by using using 2-elements arrays).

When working in lisp implementations I simply found that in many cases you just share parts and that is the same for both cons-cells lists and arrays.

3†
thaynem•

Prepending is in my experience not such a common operation; actually more common is APPENDING at the end, not at the beginning

Consider that much of that experience is probably with data structures where appending is more efficient than prepending (for example, something like a Vector in c++ or an ArrayList in Java, where appending is amortized O(1), while prepending is always O(n)). An efficient algorithm in lisp may look different than what you are used to. In particular, data may be stored in the reverse order from what you would use if appending (which in some cases can even make recursion simpler) or you build up the list in reverse, and then reverse it when you are done building it to get it in the original order.

10
[deleted]•

[deleted]

5
kazkylheku•

Appending to a list is easily done with a tail pointer. Nodes for a linked list can be pre-allocated, so no memory management is required for enqueuing and dequeuing. For example in an OS kernel, you can embed the list link(s) into the process structure, so that enqueuing a process in a scheduler run queue or a wait queue requires no allocation. Even if you have to allocate a node, it comes from a recycled pool in which all the nodes are of the same size. No situation occurs where you have to relocate the entire list to another spot in memory because it has no room to grow in place. Allocating list nodes from a reserve list can be efficiently done with atomic operations, making it suitable for interrupt service routines.

nothing prevents you from building linked lists if you want them by using using 2-elements arrays

Ergonomics. Programmers do not want to see a list which looks like this:

#(1 #(2 #(3 #(4 nil))))

What would the following look like if it had to be written using the above notation?

(defmacro once-only ((&rest names) &body body)
  (let ((gensyms (loop for n in names collect (gensym))))
    `(let (,@(loop for g in gensyms collect `(,g (gensym))))
      `(let (,,@(loop for g in gensyms for n in names collect ``(,,g ,,n)))
        ,(let (,@(loop for n in names for g in gensyms collect `(,n ,g)))
           ,@body)))))

Moreover, array routines are of no help. Say I want the third item of the list. I cannot use (aref list 2); that is out of bounds. We need (aref (aref (aref list 1) 1) 0) which is in no way better than (car (cdr (cdr list))), not to mention (caddr list), not to mention (third list).

Nothing prevents you from constructing a system in which there is a special type tag for a 2-element array which gives it a different read/print notation, so the list looks like (1 2 3 4), and from providing a collection of operations geared toward list manipulation that work with those two-element lists, so that things are a lot nicer in those allegedly rare situations when list crop up.

2
[deleted]•

[deleted]

1
MashTheTrash•

where are range and take implemented?

1
death•

Obligatory Naggum post.

19
fnorduliciousλf.(λx.f (x x)) (λx.f (x x))•

Help fight MULE in GNU Emacs 20!

I wonder what that drama was about…

5
death•

I think he ranted on it in c.l.l so you can likely find it on the site I linked. As far as I recall, it was mostly about the added code complexity and degraded performance?

2
kazkylheku•

Speaking of complexity and degraded performance, he should also have taken on multi-byte, multi-encoding support in the GNU utilities.

2
republitard_2•

Wait a minute, is that Xah Lee he's responding to?

2
-6502-OP•

I remember reading somewhere about Naggum bad attitude but this is more than I expected :-) . I don't think I agree with everything he wrote in that post... (EDIT: I mean I agree with something, not with everything).

-3†
spreadLink•

You are very focused on the idea that a cons cell is just a node in a list.

Really, tho, a cons cell expresses the concept of a relation between two objects; in effect, it is a double pointer saying "these two things belong together".

That you can use that mechanism to chain many things in a list is almost incidental, as is the fact that you can chain trees out of cons cells. Other uses include:

  • associating two items in assoc sequences
  • storing two sequences to form a queue
  • constructing a rule with a head and a body

And so on and so forth.

11
theangeryemacsshibeλf.(λx.f (x x)) (λx.f (x x))•

If arrays give you better complexity for what you want to use, then use an array. That doesn't make cons-based lists better or worse, just different. Lists are convenient for making stacks (with pushing and popping), and can be done so without mutating or copying the entire stack, unlike a dynamic array.

10
[deleted]•

[deleted]

9
defunkydrummer '(ccl)•

This ability to do cons cells very efficiently on stock hardware was, I think, one of the things that killed Lisp machines. Was Lucid the first to do this?

I thought it had to do more with overcoming the slowness of type checks/type dispatching, which on Lisp Machines was aided by the hardware itself.

3
[deleted]•

[deleted]

2
lispm•

> Representing all lists that way is horrible for computers

Modern computers are like 1000 times faster than Lisp Machines from 40 years ago, which used cdr-coding for some lists.

> cdr-coded

it's just that basically only a few Lisp implementations from 40 years ago ever used that. I can't remember any implementation from the last 30 years to use it - there might be one, but I never heard of one.

> why not 3 or 4, or 1, or 0?

Maclisp had that, but the cons cell was used as the simplest way to create linked lists and related data structures.

http://www.maclisp.info/pitmanual/hunks.html

> powerful as arrays providing O(1) indexed access

That's why Lisp has arrays, too.

8
Aidenn0•

My understanding is that implementations stopped using CDR coding because implementations got arrays. For linear sequences vectors are better in just about every way. Structure sharing is the only advantage they have, and that doesn't seem to be used all that often in Lisp code.

Now for trees there are some advantages, and of course that's what they are used for in terms of representing lisp code.

2
lispm•

CDR coding was mainly used only on Lisp Machines with CPUs optimized (-> microcoded) for Lisp. These machines had also extensive array support in their Lisp implementations (actually more than what is provided by the Common Lisp standard, just read the chapter on Arrays in a Lispm manual).

CDR-Coding was introduced to save space and make Lisp systems faster in overall usage - in combination with extensive memory management systems designed to improve locality. Remember that machines were slow (half a MIPS originally), had very little RAM (possibly just 1 MB RAM, and later more) and possibly large virtual memory (factor ten sometimes). Compactness and locality of lists was very useful to save space and to improve locality (which then for example reduces virtual memory paging at runtime).

On stock hardware this was mostly not used, especially when main memory got larger (and cheaper) there was little need to do it. It might have saved, say, 30% of list memory - but it was not thought to be worth it to have a much more complicated memory management for lists.

https://www.cs.cmu.edu/Groups/AI/html/faqs/lang/lisp/part2/faq-doc-9.html

3
[deleted]•

[deleted]

3
-6502-OP•

Wow... those hunks are really strange; especially puzzling is the fact that you cannot change the size but yet somehow the hunk knows it (as a wild guess from the hunksize documentation it was by using a special sentinel value). My guess is also the hunk storage size was probably known from pointer tagging.

In my current implementation all GC objects have the same structure

  • a user-defined tag (normally a symbol)
  • a pointer to next GC object
  • the number of slots
  • the number of extra opaque bytes
  • all the slots
  • all opaque bytes

Long strings have no slots and just bytes, arrays have no bytes and just slots; bytes can be exchanged for slots providing a function equivalent to a fill-pointer (the garbage collector doesn't trace past the fill pointer because those are considered just bytes, not pointers).

Slots are 8 bytes and hold either a double-precision IEEE754 floating point number or (using NaN-tagging) other type of data like small integers, small strings, symbols or pointers to GC objects.

I'm not sure if I will implement special cases for small fixed arrays using pointer tagging (more or less what hunk probably did). I don't know yet how many small fixed arrays I'm going to need on average (regular function call requires no consing and code is compiled to a VM, it's compile only and not much code representation manipulation is present after program startup).

0†
theangeryemacsshibeλf.(λx.f (x x)) (λx.f (x x))•

not much code representation manipulation is present after program startup

Dare I ask, why not? Interactive environments are fun.

4
-6502-OP•

TL;DR: yes, but it's true that a running system tends to natural becoming a little more static. And, hopefully, a system is going to be used for much longer time and by much more users than during its development. For most systems optimizing performance for macroexpansion/compilation doesn't sound right.

Long version

Interactive environments sure are fun, and indeed the code data equivalence and absence of parse-time/compile-time/run-time arbitrary division is a very nice property that unfortunately is still missing from "mainstream" languages.

That said however, for my experience, once you start actually using the software the code changes a lot less and it's better to have efficient data structures for running the code more than having efficient data structures for manipulating the code.

Once the startup dust settles down there is sort of a "natural" division and data (e.g. chat messages, chess games, text documents) tends to become "static" from a structural point of view even if dynamic in values and code that tends to become instead totally static.

This division, taken to the extreme, is the C++/Java/You-name-it view where the code is totally static from design and an interpreter/compiler is not even present in a running system.

-- C++ digression --

In C++ (a language I know to some extent) for reasons not clear to me being able to say open a file at "compile time" is seen as a deadly liability, go figure. Over the years they started moving sloooooowly toward compile time computation, but unfortunately I don't see any possible path way to get to a reasonable point for C++ metaprogramming

The reason is that to have decent metacode IMO you need a uniform code structure, and C++ is instead a truly horrible mess of complexity and special cases at grammar, syntax and semantic level. Unfortunately I don't think C++ can be healed for metaprogramming, most of the choices made in the past prevent that possibility.

And there's even a cultural/philosophy problem. For example in recent standards there was much amazement and enjoyment about a feature (constexpr code) that represented code that could be executed both at "compile time" and at "run time". How impressive uh? ;-)

Next version however will probably introduce a new "feature" (consteval code) that once again is about making impossibile to mix the two and is for code that you want to be compile-time only.

In other words while they were starting to somewhat demolish the arbitrary wall between compile time and run time, still they keep adding more bricks to it (I'm not a common lisp expert but IMO eval-when is not something in the same category but more of a practical artifact and you can probably be happy and productive in Lisp without even having to know it exists).

-- end digression

After discovering Lisp approach I cannot like that view any more, but one has to admit that even if very suboptimal it cannot be said that it is a view that takes you nowhere. Most of existing code is written that way.

To recap in my opinion representing everything forever as s-expressions would be of a fantastic simplicity for development, but so-so for performance.

It is good (close to necessary) to have the ability to generate/mutate code at runtime, but practically speaking it's not in my opinion a good idea to prioritize for that.

The system I'm working on right now has a compiler that generates bytecode (a bytecode so low-level that could be translate easily to machine code, something I plan to do in the future) but I don't expect the compiler to use a big percentage of CPU time when the system is actually used (except during startup/update).

A big number of small lists are needed when reading/compiling, but optimizing for that in my opinion doesn't make much sense.

0
theangeryemacsshibeλf.(λx.f (x x)) (λx.f (x x))•

Well yeah, serious Lisp implementations compile to bytecode or machine code, but it's still possible to compile and insert new functions at runtime. That would require code manipulation of some sort, but mostly wouldn't hurt performance (except that you couldn't assume argument counts/lambda lists of functions, and couldn't inline without changing the semantics of the program).

And you wouldn't be wrong to say that programs become more static over time, but I think it'd really suck if you had to make a change to something and needed to continue with the same state without dynamic redefinition. Plan for the worst and all.

7
lispm•

once you start actually using the software the code changes a lot less and it's better to have efficient data structures for running the code

Lisp was heavily designed for exploratory programming, especially in fields where meta-programming or language programming was used. Often large parts of the language needed to be part of the running program, since Lisp, the program or both were developed while it was running.

Lisp is also used on scenarios where applications are scripted at runtime by users. Thus it can be an application development and scripting language at the same time. Sometimes a Lisp system is embedded inside a static program to make runtime extension useful (prominent example AutoLisp in AutoCAD).

Lisp then was used in development systems where there is non distinction between development time and runtime -> because they were or are targeting developers which run long-standing Lisp systems.

Mainly starting in the 80s the question of 'delivery' into static applications came up. Speed and memory usage (!) were a reason. But also the idea to deliver Lisp applications as typical delivery artefacts like executables.

There were two answers to that: delivery systems and new languages.

Thus delivery systems were developed, which create static applications out of dynamic Lisp programs. One approach is to use special delivery tools (see for example what Allegro CL and LispWorks are offering) or special compilers (see for example mocl and there are even a bunch of inhouse compilers doing the same).

The other option were new languages. Prominent example was Dylan, developed by Apple together with a bunch of companies/universities. One goal was to have an object-oriented Lisp (but not alien to typical programmers), which could be used to develop applications and deliver them -> an interpreter/compiler was not part of the runtime.

3
ckriesbeck•

CONS is critical to pattern matchers on recursive data structures, such as trees and graphs, and backward chaining deductive inference, as encountered in knowledge-based AI systems. The heart of both algorithms is a depth-first exploration of all possible matches, collecting bindings incrementally, backtracking often. This is cheap when you can add a binding in constant time and space. If you don't have CONS, you have to invent it, as noted in Greenspun's 10th rule -- which then means inventing a reader and printer for such data.

8
801ffb67•

Another side to this question would be:

Is exposing the cons cell really such a good idea ?

It's often a private abstraction, like java.util.LinkedList$Node. Clojure does not expose the cons cell either. It has a cons function but it is passed a list and returns a list. Digging into the implementation, Clojure's PersistentList actually is a cons cell. Its constructor takes two arguments: an object (the value) and a pointer to the rest of the list (a PersistentList too). Mhhh.... *Scratches head*.

7
-6502-OP•

What I was saying is just that as building brick an n-cell (with n fixed) is not conceptually more complex than the cons cell, but more useful for building complex data structures.

1
lispm•

> n-cell (with n fixed)

That's called a vector in Lisp. Otherwise one can build n-cell storage out of linked cons cells.

4
-6502-OP•

Code representation in classic lisp does the latter (what it wants are n-elements lists and uses cons cells chains to get them). I think the former (starting with n-elements lists as primitives) would have been more practical.

For example in interpreters I normally use a static array with 2n+1 entries as environment, with the extra element being the link to parent environment.

1
lispm•

> Code representation in classic lisp

Source code. Running code may be compiled (since ca. 1960) for example to machine code, which does not use lists.

> I think the former (starting with n-elements lists as primitives) would have been more practical.

'practical' is vague and undefined. What would be more practical for whom and what does 'practical' actually mean?

3
bjoli•

In the scheme world the mutability of the dynamic array becomes a problem since you can return to the same execution point several times using call/cc.

In the real world, they are often fast enough (just like python!!). The Linux kernel uses linked lists in places, and even though other data structures might be faster, they have a tendency to add complexity in ways that are not appreciated in the kernel.

There are implementations of persistent vectors or even rrb-trees that run just fine, but since the linked list is rarely the problem you only reach for them when there is an actual benefit. Frankly, I don't often write code that needs o(1) indexing, and when I do persistance is even more rarely needed.

I have read a fair share of clojure code. I have seldom seen code that really uses the persistent vectors in ways I couldn't just as easily do using linked lists. Yet people won't stop telling me about how amazing persistent vectors are. Most of the time so just think it is because they have a familiar interface.

HAMTs on the other hand I think is a great idea, because the whole point of those kinds of mappings are fast lookups.

5
joinr•

I have seldom seen code that really uses the persistent vectors in ways I couldn't just as easily do using linked lists

Random access on a persistent vector kicks lists the curb, conj at the end (no janky reversing needed), o(1) look ups on both ends, o(1) sub vectors, o(1) count, linear traversal is as fast. I've written a lot of production clojure, and there are definite use cases in production code where these attributes matter. The fact you get a familiar list like seq abstraction is great too. Perhaps the most useful bit is that conjing happens at the tail instead of prepending, so the order of elements conforms to insertion order right out of the box. In contrast, aside from lazy seqs (which are ubiquitous), I find the usage of explicit lists (outside of macros or expression generation) to be rare in practice (aside from the occasional algo where prepending is desired). Vectors end up being more useful in general, and aren't really dominated by lists except in rare cases, and retain persistence. They are generally a path of least resistance for comprehension and performance, hence their ubiquity.

2
bjoli•

I was spell-bound by pvectors when they came. They are cool as hell, and the RRB-tree superset of them is even cooler. What I have found though is that I rarely find data that I have to extend that also needs o(1)-ish random access.

I have a fast RRB-tree implementation for guile scheme that I am publishing whenever I have it battle tested, but... I never seems to find the use for them. The things they provide are 3: appendable, persistent and fast random access. I rarely need all three at the same time. Usually I build the data in one step and then work on it later. Lists are just fine for that.

For random access and persistance I usually use VLists (another bagwellian data structure) which has the same kind of big-O complexity but a lot lower general overhead.

2
joinr•

For random access and persistance I usually use VLists (another bagwellian data structure) which has the same kind of big-O complexity but a lot lower general overhead.

I remember running across those years ago when I was looking at alternate persistent array implementations to explore tradeoffs with pvector. I have a passing familiarity (have not used them in practice though).

If I read correctly, some operations are Log(n) worst case (or expected case e.g. for count/length). I mean Log(n) (assuming Log2(n)) and Log32(n) are both logarithmic, but I'd think the constant factors matter in practice. If they offered the same performance we would still be on balanced binary trees like Fset and similar earlier pure-functional collections though. I get the average case O(1) analysis for random indexed lookup from bagwell's paper; it's in a similar vein of the ~O(1) pitch for the Log32(n) lookup (I have nothing on hand to compare them in practice; would be interesting to see a tuned implementation vs. a HAMT backed pvector). Cache coherence benefits appear similar (chunks of contiguous arrays in both, except the HAMT uses uniform chunk sizes where the vlist apparently has blocks related with a geometrically decreasing size; based off the paper at least). I don't quite understand the claim for "a lot lower general overhead." Finding the index in a hamt-backed vector is fairly efficient (e.g. using bitmasks and bit comparisons to guide the branching). What general overhead is being reduced? Also are the vlist implementations (as in the paper) restricted to Log(n) for counting the length, or do practical implementations have a work around ?

I rarely need all three at the same time.

I kind of take for granted that I have all three with the pvec; o(1) subvecs are useful as well (seems like vlist could support this as well if it already supports ~O(1) average case lookup) . The only thing weak is the concatenation, which rrb-trees address (with some minor tradeoffs). I have not found myself in situations that call for fast concatenation and similar operations optimized by the rrb-trees (after about 10 years), but there are certainly people leveraging them.

Usually I build the data in one step and then work on it later. Lists are just fine for that.

Same with sequences in the case of Clojure. It's idiomatic to process things in their seq abstractions and "pour" them into the persistent structures (typically by way of transient mutation on your behalf) you'd like at the end e.g. for efficiency concerns. Only, no intermediate lists need be created (only the pieces that are lazily realized in situ, everything else is gc'd on the fly). With transducers, no intermediate structures are necessary at all, which is nice.

I noticed your remarks in this repo. I would not naively expect a 2x reduction in speed for random access lookups. If that ends up being the algorithmic cost of business (as opposed to an implementation detail), it could be a nice alternative in clojure (I couldn't find any implementations) for speed comparison.

1
Nyanraltotlapun•

o(1) look ups on both ends

You said something strange here.

1
joinr•

Depending on the structure, this is true. If it's <= 32 elements, the tail array is the head, tail array is always kept at the root of the hamt with o(1) access (entry 0 and 31 have same lookup time). If there are more than 32 elements, last 32 tail entries are still all accessible in o(1), head technically has to be looked up in child nodes in o(log_32(n)), so worse case for a billion entries, six array derefs.

2
Nyanraltotlapun•

Thanks for explanation it became clear for me now.

I was confused because for me "look up" and "access by position index" is very different operations.

2
defunkydrummer '(ccl)•

I don't see the cons cell really simpler than a fixed size dynamically allocated array.

Cons cells allow easy creation of variable length lists. Dynamically allocated variable length arrays are more complex.

And cons cells are not only useful for lists, they can be used for trees, etc.

4
hajovonta•

You are missing homoiconicity. I'm curious how would you conveniently represent code in fixed size dynamically allocated arrays.

3
kazkylheku•

With a whole lot of unnecessary heap-fragmenting copying whenever you wanted to do recursion of the form "process the first element of this syntax, and then recurse over the rest".

7
-6502-OP•

For example the function definition

(defun square (x)
    (* x x))

is represented as

 ________
|        |
| defun  |
|________|
|        |
| square |
|________|          _______
|        |         |       |
|   -------------> |   x   |
|________|         |_______|          _______
|        |                           |       |
|   -------------------------------> |   *   |
|________|                           |_______|
                                     |       |
                                     |   x   |
                                     |_______|
                                     |       |
                                     |   x   |
                                     |_______|

incidentally the Lisp simplified representation for lists is hiding you from the fact in a classical Lisp system that definition is internally represented with

(defun . (square . ((x . NIL) . ((* . (x . (x . NIL))) . NIL))))

(I'm NOT going to draw the ASCII art for that)

Sorry for the ASCII art but I don't understand how to paste images (pasting the image works but when I confirm the comment it just hangs forever in both chrome and firefox).

2
hajovonta•

So you would create an array of arrays (when creating nested structures)? Wouldn't it be too expensive to recreate them when I need to append to some of them? Or if we store only pointers to other arrays, how would it differ from cons?

How would we handle recursive functions? What about macros, which create structures at macroexpansion time, can we easily represent them?

3
-6502-OP•

Sorry I thought it was obvious but apparently it's not. I was talking about arrays of slots... in current implementation a slot is 8 bytes and can contain

  • a symbol
  • a number
  • a short string (up to 5 chars)
  • a pointer to native code
  • a pointer to a garbage collected object

garbage collected objects have a tag, zero or more slots and zero or more opaque bytes (ignored by the garbage collector when visiting an object for other referenced objects).

And yes... a cons cell is not very different from a gc object with two slots. I didn't deem cons cells important enough to be special cased out in the slot with a dedicated tag for them. I am representing lists for code manipulation with fixed arrays.

I simply don't find cons cell that beautiful, and this is what the whole thing was about.

1
joinr•

If you are working from first principles, it's an excellent idea that has both elegance and surprising mileage (picolisp is an example). At some point, other structures are desirable due to inherent limitations of cons cells and the algorithms and data structures they admit (assoc lists vs hash tables, linked lists vs arrays/vectors). Many use cases may never reach that point. For those that do, supplementing the humble cons cell with additional structures is often enough (e.g. to gain efficiency).

I think the emphasis on elegance and generality can lead to dogma though; cons cells / linked structures are great, but we need hash tables and arrays and the like (mechanically sympathetic stuff that enables efficient algorithms) these days too.

3
Falcon5757•

I skimmed the whole thread and didn't see a question I really wanted to ask. What do you mean by a "good idea"?

That just sounds so ridiculous. I can see 2 options here, maybe there are more that escape me.

Option 1: someone was selling to you the "cons cells is a best data structure ever written and shall be used everywhere" really hard. My suggestion in that case would be to ignore this person instead of asking "why do you think so" ........here. You want to ask so badly-- do it in person.

Option 2:not option 1 and then a good idea for what? I hope you realize pretty much nobody here uses cons cells or lists exclusively. But they are great for when you need a quick unnamed pair somehow, or just for the lisp code itself. With code, considering that there will literally never be more than say 1000 atoms in a cons-based tree, the speed is unimportant as well as any sort of quick O(1) amortized or not access to elements, esp considering that the whole thing happens at compile fucking time. On the other hand it is also convenient to process code recursively and do nice slices of parts of it with first, second, third, rest etc. Same reason why lists are untyped and shouldn't be -- code objects include symbols, strings, numbers of all sorts, other lists, literals for various objects (including custom ones) etc. I m pretty sure this isn't hard to get.

Option 3: ????????you wanted a flame war. If that's the case go f yourself. But if not, then I guess you don't have to.

There, hope this helps.

1
-6502-OP•

I simply think that as a starting point for building, a fixed n-elements cell is about the same complexity and simplifies things a lot.

Of course I didn't want a war, I simply wondered if there was something special that I was missing. My view is currently that cons cells are just an historical implementation detail artifact and they're not central to the Lisp concept.

1
Falcon5757•

They are not, I'm glad you realized that. I also agree that all the n-tuples are about the same in terms of concept complexity.

That said, I still think that cons cell is actually the simplest nothing possible, i.e. by trying to make syntax with say, 6-tuples (somehow) we would only complicate it without gaining anything useful in return at all. Same goes for vectors instead of lists.

1
markasoftware•

how would you cdadr without cons?

1
-6502-OP•

I know it may be shocking, but you can code away yourself to some interesting places without any of the very powerful CxxxxR functions.

I normally never implement CAR or CDR or CADR and friends, I however have first, second and so on (it actually amaze myself I once even used sixth in real Lisp code - a clear sign that something is very wrong with me).

Don't get me wrong... binary trees are really supercool (even if for my pay recently I've been used a lot more quadtrees as I'm currently working on multilayer 2D geometry problems); however despite the personal love I have for linked structures (since I was a kid, http://www.gripho.it/net.en.html ) code and problems that are better worked out using 1D arrays are much more common (sometimes just because current computer hardware works the way it works).

1
Nyanraltotlapun•

arrays providing O(1) indexed access

No, they don't.

P.S.

Need to add for proper context. On modern hardware you have no random access to memory. Access time, depending on place in array and its size, can wary in several ORDERS. And this is in ideal conditions where no other than yours app is running on hardware. In real world it became much much worse.

This is why view of arrays as universal solution to any problem is just wrong.

horrible for computers

By computers you meaning C processors and IBM-PC like architecture.

C processors a garbage. They a slowed progress by 50 years. C was a crime against humanity.

0†
Altruistic_Ask_2110•

I think the point of it is that it is an example of the smallest possible representation of data in bytes. I personally don't know of uses of it in real programs.

-5
kazkylheku•

Dear r/Lisp, I'm not, like, trolling or anything, but I will have you know that:

I personally don't know of uses of it in real programs.

13
[deleted]•

[deleted]

1
-6502-OP•

Not sure of what you exactly mean. A list represented as a chain of cons cells (like classical Lisp system do) requires twice the memory (half is data and half is pointers), and that's exactly the reason for CDR-coded list (https://en.wikipedia.org/wiki/CDR_coding).

0