I disagree. The difference between a dict and a list of key-value pairs should be left as an implementation detail in the receiver, not specified in the protocol.
S-expressions get this right. If the receiver knows they'll be doing a lot of lookup, they can build an indexed structure. If not, they can use something like assoc (which does a linear scan). The linear scan is probably faster with less than 5 entries anyway.
But you won't know at parse-time how to tread the item.
Below we have duplicate "keys" and an atom in the middle of a k/v list -- what do we do here? Are the dup keys an error, or do we make a multi-map? Do we throw away the atom or assume it's a key with a nil value?
It's stuff like this that makes Erlang/Elixir really weird -- it needs to look at the format of every item first to determine what it's going to be or how it's going to be printed. (Is it bunch of numbers, or a string? Is it a dictionary, or just a list of keys and values?)
- Parsing isn't just turning bytes into some generic tree representation (JSON/SAX/s-expr/etc.); it also includes subsequent domain/application specific input handling, e.g. constructing custom objects, checking certain invariants, etc. Note that we don't need custom objects; but we should still be checking the required invariants of our 'List[Tuple[String, Bool]]', or whatever.
- Parsing should be done up-front, processing should use its output; e.g. we shouldn't be passing around generic types like 'JsonObject', 'AssocList', etc. (unless our application is generic JSON/s-expr processor, of course!). Note that we can still do streaming/lazy processing, with data parsed on-demand, but we should be careful about what side-effects might be performed part-way-through a broken input (this would apply to any approach though, e.g. hitting invalid bytes part way through some JSON)
Examples like your broken assoc-list will hence be spotted at parse time; maybe not at the bytes->tree step, but certainly at the tree->domain-model step.
I agree that that is how a parsing & instantiating framework should be built, and you should be able to hook in at any level -- but the reality is that normally when one consumes such data you are using both functions at the same time - de-serializing. Having list vs. set vs map notations is both syntax (for parsing) and really a form of meta-data, making explicit what promises are made of the data, and therefore hinting at which data-structs you may want to instantiate from the data. I suppose that ideally the meta-data should be a separate, optional statement made about the data, but that's not the M.O. for any common formats.
There is a difference between semantics and implementation. There is nothing forcing you to turn a JSON object into a hash table. You can easily store it into a list of pairs. However the semantics are obvious, this is a mapping, order doesn't matter and there shouldn't be duplicates. If you just see a list of pairs it is less obvious what is meant.
That being said you can easily argue that the JSON data types aren't expressive enough to capture many common semantics so you end up needing external documentation anyways.
I think we mostly agree, but would put it a bit differently.
First, I think performance is a bit of a red-herring in this discussion. If a linear scan is really faster for five entries, a good dictionary implementation could simply switch to that.
Second, and more to the point, there’s a obviously a semantic difference between a list of pairs and a dictionary. That’s always going to be part of the “protocol” - whether your serialization format is capable of expressing that or not.
However, and I think this is where we agree, there are lots of semantic distinctions that JSON can’t express (dates vs. strings, to pick an example I encounter often). So in many cases, you’re going to have a deserialization step anyway that validates the JSON values and converts them into the objects you actually want to use in your application. Why, among all the semantic distinctions that JSON doesn’t capture, is the list/dictionary distinction so special that it needs this kind of syntactic support in a serialization format?
(BTW, for JSON, the answer is obviously rooted in JavaScript’s type system. But while that makes it particularly nice to use JSON to serialize JavaScript objects, the context here is its use as a general-purpose serialization format.)
There's a difference between a list of pairs, which is the one that is equivalent to a dictionary, and a list of lists that all happen to have length 2; and between an unordered multiset and an ordered list.
Did the author know what an alist is (hint: check out he assoc function). In any case though, there’s no huge difference between the two. The graph structure semantics are assigned by the generator and consumer code.
Just because the standard lisp reader is readily available doesn't mean you should use it for anything else than code or small chunks of trusted data. Was there ever a question of using regular s-expressions in the same way as json? I don't think I have ever heard people suggest that. Most people either talk about using (read ...) to read trusted config files (which is fine) or to define an s-expression format to address specifically the complaints of the article.
As others have pointed out, there is nothing stopping a lisp reader from reading an alist as a hash-table. That is an implementation detail...
Indeed, feeding network-supplied input to a lisp reader is asking for trouble. In principle you can configure a reader to ignore read macros, but every lisp dialect has different footguns.
But they're great for application data storage. HN stores everything as s-expressions.
I’ve used both json and a cutdown version of sexps (there are no types like numbers or symbols, all atoms are strings so "foo" and foo are the same sexp) a lot.
I felt like sexps were much better for humans to write as you don’t need to quote everything. Maybe this could be fixed in a json extension which allows words to be read as strings of themselves but if you extend json you lose any interoperability. Json also doesn’t have comments.
There are some arguments for or against alists/plists instead of json “dictionaries”. An obvious point is that only one of these allows for non-string keys. A weak concern I have is about using “the wrong type”, eg if you use an array you sort of imply an ordering, and an object an unordered mapping, so should you put unordered data like a set in an array or should you have a map full of null values?
In recent years, languages with tagged unions like haskell or rust have become more popular. I feel like there’s no satisfying way to write such a thing as json (relying on field names to disambiguate is only sometimes possible and feels tricky to read, having an object with a tag field or an array of [tag, value] feels unnatural. With a sexp you can just write it with a list of tag and args but because everything is lists, it doesn’t feel so unnatural.
This isn’t related to json vs sexps but having a difference between "123" and 123 in your text format kind of sucks. Either the parser will reject one or go to the trouble of parsing both or there’s a semantic difference between them which feels worse. A case it matters in json is that if your number isn’t a double you may want to put it in a string so other json reading programs don’t turn it into a double and round it to a different value.
> Maybe this could be fixed in a json extension which allows words to be read as strings of themselves but if you extend json you lose any interoperability.
I worked on a product that did this for its storage file syntax, and the issue around interoperability was a huge drag. Both on us, and also on our customers. By nature of the product the customers often wanted to generate the files themselves, but generally didn't because they lacked tools to do so.
I don’t know how universal this is, but at least in my mind there is a clear semantic difference between 123 and "123". 123 is a number in the mathematical sense, maybe counting or measuring something. It probably makes sense to do arithmetic on it (addition, multiplication, etc.). "123" is a number in the other sense: some kind of identifier that happens to consist of numerical digits; something like a phone number, zip code, serial number, etc. It doesn’t make sense to perform arithmetic with it. And if it happens to begin with a "+" or a "0" then it’s not ok to just drop that character.
JSON is the best interchange format ever invented. I don't understand why anyone would want to change it. It's:
- Simple
- Human and machine readable
- Compatible
- Searchable
- Debuggable
- Relatively fast encoding/decoding
- Small size
I think Protocol Buffers is yet another misguided attempt to reinvent the wheel. If you did a pros and cons analysis on Protocol Buffers, you'd quickly realize that you lose in simplicity, lose on human readability, lose on compatibility (since it can introduce a reliance on specific type systems which different services will have to agree with), it's less searchable, less debuggable... The only benefit of Protocol Buffers over JSON is that in some languages it's a bit faster to encode and decode... In some environments the speed difference is negligible.
I can't think of any use case where ProtoBuf would be superior. I still don't understand how it could have become so popular. I guess it has Google's name behind it; that must be why.
JSON is by far not the universal exchange format. There are plenty of use cases where JSON is not well suited, such as:
- regular/tabular data where JSON fails at processing speed and/or compressibility. One of the most efficient ways to store for instance a table/array of numbers is packing them as binary IEEE754 stream.
- encapsulation of other code. Ever put HTML in a string within JSON? It's terrible to read and maintain for a human due to all the escaping. If you ever embedded SVG into XML/HTML or XML/HTML in JSX, you know how easy it can be if you don't have to break your head about escaping.
- Obviously there is a need for binary json (there exist a lot of proposals/standards). That's quite similar to protocol buffers. The reason is always something about performance.
- Also there are folks arguing since decades about JSON vs. XML vs. YAML vs. TOML vs .... There are lot of different opinions, and it is hard to say some is superiour to the other.
Trying to standardize binary as a flexible and general purpose interchange format is unwise IMO. UDP and TCP (and other protocols at that level) are about as far as we can standardize binary formats - This is as specific as they can be whilst still being generally applicable to a wide range of use cases.
My problem with ProtoBuf is that you can't impose more a more rigid structure and get more compatibility at the same time. A more rigid (statically typed) structure is inherently less compatible/interoperable (requires more integration effort, not less; harder to debug, not human readable, not searchable etc... More integration effort = less compatible, less interoperable).
This completely misses the point imo. S-expressions are a simple and fast way to serialise data, which is then deserialised according to some schema. It's not up to s-expressions (or json) to represent the end object being deserialised.
Funny to see this article—I was interning at a company that used S-expressions instead of JSON internally right around the time this post was written. (Seeing it for the first time now though.)
All I can say is that in practice, s-expressions worked way better than JSON. Easy to read as a human, more flexible than JSON, reasonable syntax for working with alternatives (ie variants or sum types) and, of course, comments.
Here's one thing that stood out to me in particular: you could encode formatted text in a way that was pretty easy to read even without formatting:
(Here is a sentence with (i some words) (b emphasized) in (i (b different)) ways.)
I forget if this was exactly the syntax they supported, but it was something like that. You could do something similar with JSON, but it would be way more verbose and harder to parse visually.
Another massive advantage: structural editing in Emacs with Paredit is incredible. Once you get the hang of it, it's way faster and less prone to typos than "normal" text editing.
If I ever start my own company, I'd definitely be tempted to standardize on S-expressions as our human-readable format for serialization and config data.
Great comment! Can you share some information about the toolchain used around S-expressions this way? Did you really write literals in that way without quoting, etc.?
I like S-expressions (data and/or code in S-expressions) a lot and would like to use it more.
> Here's one thing that stood out to me in particular: you could encode formatted text in a way that was pretty easy to read even without formatting:
> (Here is a sentence with (i some words) (b emphasized) in (i (b different)) ways.)
That's feels a little like XML, just without attributes and untyped end-tags.
I've never really understood the hate for XML and the preference for stuff like JSON. I'm a little biased towards XML because my company uses it heavily and I got very familiar with it early in my career, but it seems to make good trade offs for most use-cases where you'd want to use structured text.
> That's feels a little like XML, just without attributes
Attributes:
(p :class 'center'
(div ...))
> and untyped end-tags.
The end tags are implied by the start tag. Why do you need an end tag? It's just another way to mess up. The following situation is not possible using S-Expressions:
> The end tags are implied by the start tag. Why do you need an end tag? It's just another way to mess up.
It helps with legibility and error-checking of hand-authored documents (at least in documents with varied tags). It doesn't look like fun to figure out where to insert something in a pages-long document with sections that like like ))))))))))))).
It's not another way to mess up, it's another way to make sure you wrote what you meant.
> It doesn't look like fun to figure out where to insert something in a pages-long document with sections that like like ))))))))))))).
What kind of editor doesn't support jumping between braces? The version of Vi that shipped with 2BSD in 1979, supports that feature[0]. Both Gedit and Notepad++ highlight matching braces. Sure, if you're doing your editing in Notepad, you might have a problem, but pretty much every other editor either highlights, supports jumping between them, or both.
The implementation of XML is a total overcomplicated disaster in many languages (cough cough Java cough cough). The design and implementation of XML namespaces has all the hallmarks of design-by-committee (where everyone in the committee is an "Enterprise Architect'), but in practice I can't tell you the number of times I've wanted to murder the masochists that overcomplicated namespaces. Don't even get me started on the total shit-show that is XML Schema.
Want another example of how XML sucks, just look at all the "XML Canonicalizations" that are necessary in the XML Signature spec because there is so much ambiguity when it comes to the canonical form of a document in XML.
Basically, the early '00s were kind of a wasteland of all these overcomplicated "Enterprise" specs (I feel like the "Java Pet Store" EJB example perfectly highlights the insanity of that period - layers and layers of unnecessary complexity, and BTW your performance is complete shit), and XML is a bit part of that before the industry as a whole realized how unnecessary a lot of that complexity is.
> the industry as a whole realized how unnecessary a lot of that complexity is
The industry didn't, new players did and backed new simpler tech. But that tech itself has, as a result of the same forces in the industry that haven't gone anywhere (and in many cases have some good reasons), progressively had much of the same complication attached to it that XML once had.
> Funny to see this article—I was interning at a company that used S-expressions instead of JSON internally right around the time this post was written. (Seeing it for the first time now though.)
Weirdly long-winded way of saying you worked at Jane Street.
I do use s-expressions converted from JSON for some API work that I do. While I am not suggesting replacing json with s-expressions, I find it easier to manipulate them.
if you want to experiment with using s-expressions and your language doesn't already have a parser/generator, you can find a number of simple parsers/generators on rosettacode:
40 comments
[ 3.3 ms ] story [ 90.6 ms ] threadS-expressions get this right. If the receiver knows they'll be doing a lot of lookup, they can build an indexed structure. If not, they can use something like assoc (which does a linear scan). The linear scan is probably faster with less than 5 entries anyway.
((k1 v1)(k1 v2) ... (k4532 v4532) anAtom (k4533 v4533) ...)
It's stuff like this that makes Erlang/Elixir really weird -- it needs to look at the format of every item first to determine what it's going to be or how it's going to be printed. (Is it bunch of numbers, or a string? Is it a dictionary, or just a list of keys and values?)
I would follow the advice from LangSec ( http://langsec.org ) and "parse, don't validate" ( https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-va... ):
- Parsing isn't just turning bytes into some generic tree representation (JSON/SAX/s-expr/etc.); it also includes subsequent domain/application specific input handling, e.g. constructing custom objects, checking certain invariants, etc. Note that we don't need custom objects; but we should still be checking the required invariants of our 'List[Tuple[String, Bool]]', or whatever.
- Parsing should be done up-front, processing should use its output; e.g. we shouldn't be passing around generic types like 'JsonObject', 'AssocList', etc. (unless our application is generic JSON/s-expr processor, of course!). Note that we can still do streaming/lazy processing, with data parsed on-demand, but we should be careful about what side-effects might be performed part-way-through a broken input (this would apply to any approach though, e.g. hitting invalid bytes part way through some JSON)
Examples like your broken assoc-list will hence be spotted at parse time; maybe not at the bytes->tree step, but certainly at the tree->domain-model step.
That being said you can easily argue that the JSON data types aren't expressive enough to capture many common semantics so you end up needing external documentation anyways.
First, I think performance is a bit of a red-herring in this discussion. If a linear scan is really faster for five entries, a good dictionary implementation could simply switch to that.
Second, and more to the point, there’s a obviously a semantic difference between a list of pairs and a dictionary. That’s always going to be part of the “protocol” - whether your serialization format is capable of expressing that or not.
However, and I think this is where we agree, there are lots of semantic distinctions that JSON can’t express (dates vs. strings, to pick an example I encounter often). So in many cases, you’re going to have a deserialization step anyway that validates the JSON values and converts them into the objects you actually want to use in your application. Why, among all the semantic distinctions that JSON doesn’t capture, is the list/dictionary distinction so special that it needs this kind of syntactic support in a serialization format?
(BTW, for JSON, the answer is obviously rooted in JavaScript’s type system. But while that makes it particularly nice to use JSON to serialize JavaScript objects, the context here is its use as a general-purpose serialization format.)
As others have pointed out, there is nothing stopping a lisp reader from reading an alist as a hash-table. That is an implementation detail...
But they're great for application data storage. HN stores everything as s-expressions.
I felt like sexps were much better for humans to write as you don’t need to quote everything. Maybe this could be fixed in a json extension which allows words to be read as strings of themselves but if you extend json you lose any interoperability. Json also doesn’t have comments.
There are some arguments for or against alists/plists instead of json “dictionaries”. An obvious point is that only one of these allows for non-string keys. A weak concern I have is about using “the wrong type”, eg if you use an array you sort of imply an ordering, and an object an unordered mapping, so should you put unordered data like a set in an array or should you have a map full of null values?
In recent years, languages with tagged unions like haskell or rust have become more popular. I feel like there’s no satisfying way to write such a thing as json (relying on field names to disambiguate is only sometimes possible and feels tricky to read, having an object with a tag field or an array of [tag, value] feels unnatural. With a sexp you can just write it with a list of tag and args but because everything is lists, it doesn’t feel so unnatural.
This isn’t related to json vs sexps but having a difference between "123" and 123 in your text format kind of sucks. Either the parser will reject one or go to the trouble of parsing both or there’s a semantic difference between them which feels worse. A case it matters in json is that if your number isn’t a double you may want to put it in a string so other json reading programs don’t turn it into a double and round it to a different value.
I worked on a product that did this for its storage file syntax, and the issue around interoperability was a huge drag. Both on us, and also on our customers. By nature of the product the customers often wanted to generate the files themselves, but generally didn't because they lacked tools to do so.
- Simple
- Human and machine readable
- Compatible
- Searchable
- Debuggable
- Relatively fast encoding/decoding
- Small size
I think Protocol Buffers is yet another misguided attempt to reinvent the wheel. If you did a pros and cons analysis on Protocol Buffers, you'd quickly realize that you lose in simplicity, lose on human readability, lose on compatibility (since it can introduce a reliance on specific type systems which different services will have to agree with), it's less searchable, less debuggable... The only benefit of Protocol Buffers over JSON is that in some languages it's a bit faster to encode and decode... In some environments the speed difference is negligible.
I can't think of any use case where ProtoBuf would be superior. I still don't understand how it could have become so popular. I guess it has Google's name behind it; that must be why.
- regular/tabular data where JSON fails at processing speed and/or compressibility. One of the most efficient ways to store for instance a table/array of numbers is packing them as binary IEEE754 stream.
- encapsulation of other code. Ever put HTML in a string within JSON? It's terrible to read and maintain for a human due to all the escaping. If you ever embedded SVG into XML/HTML or XML/HTML in JSX, you know how easy it can be if you don't have to break your head about escaping.
- Obviously there is a need for binary json (there exist a lot of proposals/standards). That's quite similar to protocol buffers. The reason is always something about performance.
- Also there are folks arguing since decades about JSON vs. XML vs. YAML vs. TOML vs .... There are lot of different opinions, and it is hard to say some is superiour to the other.
My problem with ProtoBuf is that you can't impose more a more rigid structure and get more compatibility at the same time. A more rigid (statically typed) structure is inherently less compatible/interoperable (requires more integration effort, not less; harder to debug, not human readable, not searchable etc... More integration effort = less compatible, less interoperable).
All I can say is that in practice, s-expressions worked way better than JSON. Easy to read as a human, more flexible than JSON, reasonable syntax for working with alternatives (ie variants or sum types) and, of course, comments.
Here's one thing that stood out to me in particular: you could encode formatted text in a way that was pretty easy to read even without formatting:
(Here is a sentence with (i some words) (b emphasized) in (i (b different)) ways.)
I forget if this was exactly the syntax they supported, but it was something like that. You could do something similar with JSON, but it would be way more verbose and harder to parse visually.
Another massive advantage: structural editing in Emacs with Paredit is incredible. Once you get the hang of it, it's way faster and less prone to typos than "normal" text editing.
If I ever start my own company, I'd definitely be tempted to standardize on S-expressions as our human-readable format for serialization and config data.
I like S-expressions (data and/or code in S-expressions) a lot and would like to use it more.
Incidentally for the grandparent's comment about formatting, I would use something slightly different:
This is similar to what is used for some of the html-to-S-expression conversions.Since it was designed as a data format (comparable to JSON) rather than a programming-language syntax, there's a lot less need for quoting.
[1]: https://github.com/janestreet/universe/tree/master/sexp
[2]: https://github.com/janestreet/universe/tree/master/sexplib
> (Here is a sentence with (i some words) (b emphasized) in (i (b different)) ways.)
That's feels a little like XML, just without attributes and untyped end-tags.
I've never really understood the hate for XML and the preference for stuff like JSON. I'm a little biased towards XML because my company uses it heavily and I got very familiar with it early in my career, but it seems to make good trade offs for most use-cases where you'd want to use structured text.
Attributes:
> and untyped end-tags.The end tags are implied by the start tag. Why do you need an end tag? It's just another way to mess up. The following situation is not possible using S-Expressions:
It helps with legibility and error-checking of hand-authored documents (at least in documents with varied tags). It doesn't look like fun to figure out where to insert something in a pages-long document with sections that like like ))))))))))))).
It's not another way to mess up, it's another way to make sure you wrote what you meant.
What kind of editor doesn't support jumping between braces? The version of Vi that shipped with 2BSD in 1979, supports that feature[0]. Both Gedit and Notepad++ highlight matching braces. Sure, if you're doing your editing in Notepad, you might have a problem, but pretty much every other editor either highlights, supports jumping between them, or both.
[0]: Grep for `.iP "%" 15` in this document from the Minnie archive of the 2BSD source code: https://minnie.tuhs.org/cgi-bin/utree.pl?file=2BSD/doc/vi/vi...
Want another example of how XML sucks, just look at all the "XML Canonicalizations" that are necessary in the XML Signature spec because there is so much ambiguity when it comes to the canonical form of a document in XML.
Basically, the early '00s were kind of a wasteland of all these overcomplicated "Enterprise" specs (I feel like the "Java Pet Store" EJB example perfectly highlights the insanity of that period - layers and layers of unnecessary complexity, and BTW your performance is complete shit), and XML is a bit part of that before the industry as a whole realized how unnecessary a lot of that complexity is.
The industry didn't, new players did and backed new simpler tech. But that tech itself has, as a result of the same forces in the industry that haven't gone anywhere (and in many cases have some good reasons), progressively had much of the same complication attached to it that XML once had.
Weirdly long-winded way of saying you worked at Jane Street.
It addresses most of the authors problems while _also having s-expressions_, e.g.:
There are parsers for many popular languages, and a language already entirely based on it: Clojure.[0] https://github.com/edn-format/edn
For those interested, here is a detailed comparison of Lisp JSON conversion libraries https://sabracrolleton.github.io/json-review.
http://rosettacode.org/wiki/S-Expressions
there is also a good discussion on what issues need to be considered on the talk page:
http://rosettacode.org/wiki/Talk:S-Expressions