If you forget for a moment that it's used as syntax in LISP, S-expressions are pretty neat.
Most programming languages use a mix of arrays, structures, vectors, lists, tuples, tables and/or objects to represent and handle data structures. Each of them are similar yet different aggregate structures. With S-expressions, however, there are only pairs or atomic data (doesn't contain a reference to any other value). What are lists? Ordered pairs. What are tuples? Lists. What are vectors? Lists. What are structs? Tuples with compile-time field-labels (implicit accessor procedures).
Now, some of you are complaining ``lists have linear complexity''! Well, ordered pairs only have to behave as linked pairs. They can be allocated in sequential memory locations for constant lookup. CDR-coding makes this automatic and the job of the GC (and CDR-coding is simple if cdrs aren't writable (like arrays or tuple suffixes)).
Good languages only need one tool for creating composite structures: ordered pairs.
Real Lisp S-expressions also contain data types other than pairs: symbols, strings, numbers, vectors, structs, ...
Vector example: #(1 2 3 4 ..). When this is read, it constructs an array in memory which is indexable in O(1) time.
I think you best skip this Anatomy of Lisp bullshit.
Name:
Anonymous2012-02-28 4:32
>>1
I prefer arrays of arbitrary references. The representation is better for parallelism.
Name:
Anonymous2012-02-28 5:33
Ordered pairs are no silver bullet data structure but they're good as a very cheap glue in garbage collected environment for small pieces of data. Big nearly-static homogenous arrays are implemented as native arrays on most Common Lisps and they're my favourite. Many programs can be reduced to destructive transformations on such arrays and it's easy to debug and parallelise (as >>3 said) and performs extremely well with current cache architectures. I think some call it ``data-oriented design''.
Back on topic, Lisp is great not because it uses lists as its only representation of data (it doesn't); it's because it uses them for code and provides the programmer with all the necessary glue for meta-programming: explicit progns and fully programmable hooks into the reader. Abstracting lists as lists in the way described in >>1 is a gross underuse of Lisp's abilities.
Summary: abstract code instead of data whenever possible.
Name:
Anonymous2012-02-28 13:51
>>2,4
But it's not about lisp, or AoL or even lists. It's about simplicity and minimalism. Why have a mulititude of almost identical building blocks to build arbitrary data structures when one is enough? Imagine an implementation of lisp (or something else) where lists were as efficient as arrays (primitive support for list-ref) or structs. Would you not think that anything other than lists would be redundant? You could build the rest on top of it easily.
Ordered pairs does not necessarily mean nodes containing two pointers. It only have to behave that way. Again, make the cdrs immutable and a pair will have much of the same semantics as an element in an array.
>>2
Symbols, strings and numbers are atomic values. I'm talking about composite types.
Name:
Anonymous2012-02-28 16:03
>>1
Sexprs are the worst possible garbage as a surface syntax for a programming language, perhaps just as bad as verbose and complex bullshit like COBOL or simply unreadable Forth. For that, I tell you to fuck off and die.
But I agree on the rest of your post.
Name:
Anonymous2012-02-28 16:22
>>6
M-expressions were supposed to be the way people programmed in Lisp. S-exprs were just meant to be an internal data structure, and the reason why hardly anyone uses Lisp. If Lisp had an ALGOL-like syntax like it was meant to, it would be much more popular than it is now. This is why people who create their own languages should never release any experimental features to the public until they're finished. Unfinished ideas and implementation details end up getting used in real programs and by the time the developer wants to change things it's too late. It's much easier to add than remove.
Name:
Anonymous2012-02-28 16:57
>>7 M-expressions
Still quite difficult to read. The only way to fix it reliably is to make [spoiler]optional indentation[spoiler] significant.
>>1
wow. no wonder where lua got the whole "one data structure for everything!!!" from.
you all make me sick
Name:
Anonymous2012-03-01 14:55
One important thing to note is that an external/literal representation is also good to have along with the internal. It makes IPC and persistence very natural.
An alternative to S-exprs as both an internal and external representation is JSON. It has both arrays and objects/maps, which is redundant, but that might be worth it for how you program in JavaScript and access and manipulate data. Other values, such as functions, have no canonical representation as objects and arrays, and is not a part of JSON, so not everything can be represented in it.
Then of course there are other textual (and binary) formats for storing data externally, such as XML, CSV and of course source code in languages that have a formal grammar. But the difference is that you need libraries with functions and special data structures and trees for reading, traversing and otherwise using the data stored in these kinds of ways.
On the other hand, since S-expressions are part of the language, with pairs and atomic values as primitives, no tools are required to transform data from the external to the internal representation (apart from read and write). You just use the data as anything else you have in your program. Your primitive operators alredy know what it is and how to use it. (Parsing on the structural level might be necessary, as always.) It's easy to not just share a byte stream between processes but any kind of data that can be represented with S-expressions. Forget CORBA, which doesn't map the data format neatly to any kind of structure within the source language, and Java RMI because it's Java. We only need one representation, S-expressions, and we only need one composite data structure, ordered pairs.