3 ms·

See also: https://en.wikipedia.org/wiki/Canonical_S-expressions https://en.wikipedia.org/wiki/Canonical_S-expressions Canonical S-Expressions developed by Ron

See also: https://en.wikipedia.org/wiki/Canonical_S-expressions https://en.wikipedia.org/wiki/Canonical_S-expressions Canonical S-Expressions developed by Ron Rivest. I'm surprised that this page doesn't reference it as prior art since it seems to be very close to the same, if not the same, construct. https://web.archive.org/web/20070120051303/http://theory.lcs.mit.edu/~rivest/sexp.html https://web.archive.org/web/20070120051303/http://theory.lcs... https://web.archive.org/web/20061231133857/http://theory.lcs.mit.edu/~rivest/sexp.txt https://web.archive.org/web/20061231133857/http://theory.lcs...

koolba 3y ago
That looks surprisingly like bencode used by BitTorrent.
- neilv 3y ago
  That was my first thought (maybe because I was thinking about Racket, and happened to hack up a quick bencode parser in Scheme, https://www.neilvandyke.org/racket/bencode/ https://www.neilvandyke.org/racket/bencode/ ), but it's not just bencode. I think a lot of data encoding protocols that are for arbitrary non-app-specific data needing more structure than Unix shell tools lines&whitespace, and intended to be simple, but you still want to make them efficient to parse while streaming, end up like this. You have a few types, some values are variable length, historically you often choose ASCII character set (for human readability, portability to different platforms, passability of different gateways), and you might as well minimize parsing lookahead, so there's some likely ways you'll signal types and sizes in the stream. Google Protobufs (for another contemporary popular protocol) has somewhat different requirements, which leads to less-text result. But if you had those requirements (say, extensible types like in a traditional rich RPC mechanism, and maybe minimizing bandwidth), you might end up doing much the same thing. Or, today, you and GPT-4 might just punt on "micro-optimizations", and layer atop JSON or maybe still XML.
chubot 3y ago
Yes good call, I changed the broken Wikipedia links to the archive page - https://web.archive.org/web/20230228105200/https://people.csail.mit.edu/rivest/Sexp.txt https://web.archive.org/web/20230228105200/https://people.cs... Looks like it broke earlier this year, but the rest of his site is still up. It's very weird that there's already a "canonical" format for s-expressions, and then Racket apparently implemented something incompatible -- BUT WITH THE SAME NAME. They are both called "csexp". --- Rivest's draft is filled with a lot of words, but this looks like a clear incompatibility: A verbatim encoding of an octet string consists of four parts: -- the length (number of octets) of the octet-string, given in decimal most significant digit first, with no leading zeros. -- a colon ":" -- the octet string itself, verbatim. That's a length prefix. Also, unless my head is exploding, that's 3 parts, not 4. In contrast, the Racket library uses a length suffix: Spaces are removed and all strings are suffixed by their size and a colon : separator. That's super weird. This is really "the curse of Lisp" ... --- Of course maybe nobody actually uses Rivest's thing. But the length PREFIX is conventional so you know how much to allocate (netstrings, bencode, etc.) Not sure why they would go with a length suffix -- I've never heard of that. I could see making it incompatible to improve it, but it doesn't seem improved.
- imtringued 3y ago
  Length suffixes are for the truly insane.
- correnos 3y ago
  The "suffix" there is a docs mistake. if you look at the example csexp's on the page the lengths are prefixed. I think that the csexp's of this package are compatible with Rivest's format.
  - chubot 3y ago
    OK yeah, the 3:bag is easy to see. With netstrings, it's 3:bag, with a comma, which makes it a bit more readable over the wire. The extra level of Racket quoting was confusing me -- #"" and \" -- it would be nicer if they just wrote exactly what's transmitted over the wire. And still the page does seem like it's missing a reference. Both Rivest's page and this page seem a bit underdeveloped for a "canonical" format ...

koolba 3y ago

That looks surprisingly like bencode used by BitTorrent.

neilv 3y ago
That was my first thought (maybe because I was thinking about Racket, and happened to hack up a quick bencode parser in Scheme, https://www.neilvandyke.org/racket/bencode/ https://www.neilvandyke.org/racket/bencode/ ), but it's not just bencode. I think a lot of data encoding protocols that are for arbitrary non-app-specific data needing more structure than Unix shell tools lines&whitespace, and intended to be simple, but you still want to make them efficient to parse while streaming, end up like this. You have a few types, some values are variable length, historically you often choose ASCII character set (for human readability, portability to different platforms, passability of different gateways), and you might as well minimize parsing lookahead, so there's some likely ways you'll signal types and sizes in the stream. Google Protobufs (for another contemporary popular protocol) has somewhat different requirements, which leads to less-text result. But if you had those requirements (say, extensible types like in a traditional rich RPC mechanism, and maybe minimizing bandwidth), you might end up doing much the same thing. Or, today, you and GPT-4 might just punt on "micro-optimizations", and layer atop JSON or maybe still XML.

chubot 3y ago

Yes good call, I changed the broken Wikipedia links to the archive page - https://web.archive.org/web/20230228105200/https://people.csail.mit.edu/rivest/Sexp.txt https://web.archive.org/web/20230228105200/https://people.cs... Looks like it broke earlier this year, but the rest of his site is still up. It's very weird that there's already a "canonical" format for s-expressions, and then Racket apparently implemented something incompatible -- BUT WITH THE SAME NAME. They are both called "csexp". --- Rivest's draft is filled with a lot of words, but this looks like a clear incompatibility: A verbatim encoding of an octet string consists of four parts: -- the length (number of octets) of the octet-string, given in decimal most significant digit first, with no leading zeros. -- a colon ":" -- the octet string itself, verbatim. That's a length prefix. Also, unless my head is exploding, that's 3 parts, not 4. In contrast, the Racket library uses a length suffix: Spaces are removed and all strings are suffixed by their size and a colon : separator. That's super weird. This is really "the curse of Lisp" ... --- Of course maybe nobody actually uses Rivest's thing. But the length PREFIX is conventional so you know how much to allocate (netstrings, bencode, etc.) Not sure why they would go with a length suffix -- I've never heard of that. I could see making it incompatible to improve it, but it doesn't seem improved.

imtringued 3y ago
Length suffixes are for the truly insane.
correnos 3y ago
The "suffix" there is a docs mistake. if you look at the example csexp's on the page the lengths are prefixed. I think that the csexp's of this package are compatible with Rivest's format.
- chubot 3y ago
  OK yeah, the 3:bag is easy to see. With netstrings, it's 3:bag, with a comma, which makes it a bit more readable over the wire. The extra level of Racket quoting was confusing me -- #"" and \" -- it would be nicer if they just wrote exactly what's transmitted over the wire. And still the page does seem like it's missing a reference. Both Rivest's page and this page seem a bit underdeveloped for a "canonical" format ...