3 ms·

Common Lisp uses cons cells. So do a bunch of older Lisps whose design fed into the design of Common Lisp. That's all. There's nothing else special about cons c

Common Lisp uses cons cells. So do a bunch of older Lisps whose design fed into the design of Common Lisp. That's all. There's nothing else special about cons cells in my mind. Cons cells are not the important point--at least not for me. The important point in this context is that expressions are represented by something better (that is, more conveniently-structured) than flat text strings, and that the representation be a standard data structure in the language, and that operations on source code are implemented by APIs that are exposed as standard parts of the language. As far as I'm concerned, if a language does that, then it's nailed this particular part of being Lispy. There are some other parts, but that discussion is outside the scope of this one.

jaggederest 3y ago
The fancy word is "homoiconicity" but that is more about appearance. Homostructural? Homotypic? I think it's also important, at least in my opinion, that that data structure be extremely simple, and cons cells are about as simple as you can get. When you start adding "Well a vector is different than a string, n-tuple, or array, so your code has to figure out which one it is dealing with", that's when you run into issues. You could step back and just go object oriented, but at it's core an object is just a struct with a pointer to a function table and/or dictionary data, so we're right back at "cons cell if you squint". Internally it may be sped up but conceptually "everything is a small integer value or a cons cell" maps pretty closely to how I think about low level data structures. something something build your own arbitrary precision floating point number... (123 (0 (123 nil))) ~= 123.123 ~= "{\0{" ~= [123, 0, 123]
- mikelevins 3y ago
  There's a decent argument for keeping such a foundational data structure as simple as possible, but there's also a decent argument for not making it too simple. Cons cells are certainly very simple. They're so simple that, as Moon once observed to me, there's no place on them to hang metadata. For example, if your source code is made of cons cells, you might wish that they had some sort of metadata slot so that you could use it to keep track of where a given hunk of source code came from. You can't though. You have to kludge up some out-of-band solution for things like that. We were talking about my hobby Lisp, Bard. He liked that it separated protocol from representation, so you could have Lists that were made of something other than cons cells. In fact, in Bard your Lists can be made of anything you like, as long as it participates in the List protocol. In particular, they can be made of something that has some place to hang metadata. Rich Hickey of course also gave a bunch of Clojure's data structures places to hang metadata, possibly for similar reasons.
  - kazinator 3y ago
    Secret meta-data in a cons cell is not out of the question. In TXR Lisp, cons cells are four pointer-sized fields wide. So one field is not used. Almost. The field is used in the hash table implementation in which entries are conses. It sticks the hash code in there. That hash code is a pointer sized word with no tag; the garbage collector can safely ignore it. The extra field is currently not used for tracking source location information, though it could be. Source location info is instead tracked in an external hash table. (The table is configured with weak semantics, so when the code becomes garbage, the entries vaporize.) That representation could change in the future. It would mean that when the garbage collector traverses conses, it has to look at that hidden field of each one. And each time we allocate a fresh cons cell, we have to make sure it is initialized. I'd have to benchmark it. Associating expressions with source location info is a cost that we bear only when processing source code. If we shoehorn it into conses, then there is some nonzero cost to all cons cell processing, whether we are scanning code or not. An important problem is that meta-data attached to cons cells (whether internal or external) is not copied across traditional tree-structure rewriting operations. TXR Lisp's expander does some work behind the the scenes to propagate location info, like from macro calls to their expansions. The parser has a flag for whether to attach the info to objects in the first place. It's on by default if we are reading code, but not when reading data. Outside of the expander, a few places in the compiler have to be aware of this (when the compiler performs its own tree-writing outside of the macro framework). Overall I'm satisfied with the reporting. From time to time I see a bug: an error occurs for which source location info isn't available but should be. I didn't give it character precision: I think that compiler messages that report line number and character column are too rococo for my taste. If you can't figure out the problem from a line number, maybe your code is stuffing too much into one line of code.
    - mikelevins 3y ago
      Associating expressions with source location info is a cost that we bear only when processing source code. If we shoehorn it into conses, then there is some nonzero cost to all cons cell processing, whether we are scanning code or not. That's true only because cons cells have a specific representation, but they don't have to. Bard classes are defined by protocols, not representations. If I remember right, that's what Moon liked: because Bard's classes were defined by protocol and not representation, source code could be made of lists, and could have a place to hang metadata, without imposing that cost on other lists, because lists were not any specific representation; they were just any representation for which the list protocol was defined.
eduction 3y ago
The original question was why people don’t consider Clojure a lisp. By your yardstick, it is clearly a lisp. As far as I can tell the only argument against it being is that it does not specifically use cons cells.
- mikelevins 3y ago
  I did not intend to classify Clojure as "not a Lisp". I didn't intend to comment on Clojure at all, specifically, so commenting on this particular thread was an ill-conceived choice on my part. I wanted to describe the source-code peculiarity because it hadn't been discussed elsewhere in the comments and I think it's important in what you might call old-fashioned Lispiness. I should have chosen another place for my comment. Sorry about that.

jaggederest 3y ago

The fancy word is "homoiconicity" but that is more about appearance. Homostructural? Homotypic? I think it's also important, at least in my opinion, that that data structure be extremely simple, and cons cells are about as simple as you can get. When you start adding "Well a vector is different than a string, n-tuple, or array, so your code has to figure out which one it is dealing with", that's when you run into issues. You could step back and just go object oriented, but at it's core an object is just a struct with a pointer to a function table and/or dictionary data, so we're right back at "cons cell if you squint". Internally it may be sped up but conceptually "everything is a small integer value or a cons cell" maps pretty closely to how I think about low level data structures. something something build your own arbitrary precision floating point number... (123 (0 (123 nil))) ~= 123.123 ~= "{\0{" ~= [123, 0, 123]

mikelevins 3y ago
There's a decent argument for keeping such a foundational data structure as simple as possible, but there's also a decent argument for not making it too simple. Cons cells are certainly very simple. They're so simple that, as Moon once observed to me, there's no place on them to hang metadata. For example, if your source code is made of cons cells, you might wish that they had some sort of metadata slot so that you could use it to keep track of where a given hunk of source code came from. You can't though. You have to kludge up some out-of-band solution for things like that. We were talking about my hobby Lisp, Bard. He liked that it separated protocol from representation, so you could have Lists that were made of something other than cons cells. In fact, in Bard your Lists can be made of anything you like, as long as it participates in the List protocol. In particular, they can be made of something that has some place to hang metadata. Rich Hickey of course also gave a bunch of Clojure's data structures places to hang metadata, possibly for similar reasons.
- kazinator 3y ago
  Secret meta-data in a cons cell is not out of the question. In TXR Lisp, cons cells are four pointer-sized fields wide. So one field is not used. Almost. The field is used in the hash table implementation in which entries are conses. It sticks the hash code in there. That hash code is a pointer sized word with no tag; the garbage collector can safely ignore it. The extra field is currently not used for tracking source location information, though it could be. Source location info is instead tracked in an external hash table. (The table is configured with weak semantics, so when the code becomes garbage, the entries vaporize.) That representation could change in the future. It would mean that when the garbage collector traverses conses, it has to look at that hidden field of each one. And each time we allocate a fresh cons cell, we have to make sure it is initialized. I'd have to benchmark it. Associating expressions with source location info is a cost that we bear only when processing source code. If we shoehorn it into conses, then there is some nonzero cost to all cons cell processing, whether we are scanning code or not. An important problem is that meta-data attached to cons cells (whether internal or external) is not copied across traditional tree-structure rewriting operations. TXR Lisp's expander does some work behind the the scenes to propagate location info, like from macro calls to their expansions. The parser has a flag for whether to attach the info to objects in the first place. It's on by default if we are reading code, but not when reading data. Outside of the expander, a few places in the compiler have to be aware of this (when the compiler performs its own tree-writing outside of the macro framework). Overall I'm satisfied with the reporting. From time to time I see a bug: an error occurs for which source location info isn't available but should be. I didn't give it character precision: I think that compiler messages that report line number and character column are too rococo for my taste. If you can't figure out the problem from a line number, maybe your code is stuffing too much into one line of code.
  - mikelevins 3y ago
    Associating expressions with source location info is a cost that we bear only when processing source code. If we shoehorn it into conses, then there is some nonzero cost to all cons cell processing, whether we are scanning code or not. That's true only because cons cells have a specific representation, but they don't have to. Bard classes are defined by protocols, not representations. If I remember right, that's what Moon liked: because Bard's classes were defined by protocol and not representation, source code could be made of lists, and could have a place to hang metadata, without imposing that cost on other lists, because lists were not any specific representation; they were just any representation for which the list protocol was defined.

eduction 3y ago

The original question was why people don’t consider Clojure a lisp. By your yardstick, it is clearly a lisp. As far as I can tell the only argument against it being is that it does not specifically use cons cells.

mikelevins 3y ago
I did not intend to classify Clojure as "not a Lisp". I didn't intend to comment on Clojure at all, specifically, so commenting on this particular thread was an ill-conceived choice on my part. I wanted to describe the source-code peculiarity because it hadn't been discussed elsewhere in the comments and I think it's important in what you might call old-fashioned Lispiness. I should have chosen another place for my comment. Sorry about that.