News for hackers. Stuff that matters.
Re:Csexp: S-Expressions over the Network by Jtsummers on Sunday June 11, 2023 @02:02PM (#36283849)
See also: 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...

https://web.archive.org/web/20061231133857/http://theory.lcs...

Re:Csexp: S-Expressions over the Network by koolba on Sunday June 11, 2023 @02:40PM (#36284292)
That looks surprisingly like bencode used by BitTorrent.
Re:Csexp: S-Expressions over the Network by neilv on Sunday June 11, 2023 @03:05PM (#36284530)
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/ ), 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, 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.

Re:Csexp: S-Expressions over the Network by chubot on Sunday June 11, 2023 @03:18PM (#36284644)
Yes good call, Rivest's page is archived here - https://web.archive.org/web/20230228105200/https://people.cs...

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.

Re:Csexp: S-Expressions over the Network by correnos on Sunday June 11, 2023 @03:33PM (#36284795)
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.
Re:Csexp: S-Expressions over the Network by chubot on Sunday June 11, 2023 @03:44PM (#36284882)
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 ...

Re:Csexp: S-Expressions over the Network by correnos on Sunday June 11, 2023 @03:51PM (#36284942)
So, "canonical" here means "for a given tree of data this is one unambiguous binary representation for it," which is a useful property for crypto signatures. It does not mean "this is a blessed way to write sexp's", though folks can be forgiven for not realizing that since the docs here don't say much about the when's or why's of use.
Re:Csexp: S-Expressions over the Network by chubot on Sunday June 11, 2023 @09:04PM (#36287378)
Yeah that's one property you want, but "over the network" leaves me wanting a bit more

Namely interoperability between Lisps

Re:Csexp: S-Expressions over the Network by mclide on Monday June 12, 2023 @01:16PM (#36297149)
Re:Csexp: S-Expressions over the Network by imtringued on Sunday June 11, 2023 @03:32PM (#36284785)
Length suffixes are for the truly insane.
Re:Csexp: S-Expressions over the Network by adastra22 on Sunday June 11, 2023 @08:25PM (#36287143)
Rivest’s thing is used in a bunch of RSA crypto standards. You are probably using it right now as part of your SSL stack.
Re:Csexp: S-Expressions over the Network by DonaldPShimoda on Sunday June 11, 2023 @11:20PM (#36288076)
> 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.

The OP link is not part of the Racket language or its standard library. It is simply the documentation for a package written by a member of the community and hosted on Racket's official package platform — like putting something on PyPI if you're familiar with the Python ecosystem.

The package itself is listed over here [0], which links us to the source code [1], which in turn attempts to link to a URL that suggests the idea is due to Rivest [2], but that URL has apparently died.

[0] https://pkgs.racket-lang.org/package/csexp

[1] https://gitlab.com/spritely/racket-csexp

[2] https://people.csail.mit.edu/rivest/Sexp.txt