9 ms·

Csexp: S-Expressions over the Network

109 points by thefilmore 3y ago

JonChesterfield 3y ago
Doesn't say anything about cycles or what datatypes can be serialised. In general lisps _can't_ print arbitrary objects in a form that can be read back in. E.g. Welcome to Racket v7.9 [bc]. > (lambda (x) x) #<procedure> 7.9 doesn't have csexp, was curious what it would do with a function object but not quite curious enough to install a racket from outside the package manager. It seems relatively likely that racket would have some serialisation feature that can round trip arbitrary objects through a bytestring though initial guesses haven't worked out for me > (require racket/serialize) > (serializable? (lambda (x) x)) #f Still, being able to take some arbitrary closure and kick it over the network to another racket instance would be great. It's not immediately obvious that csexp can do that.
- nerdponx 3y ago
  Common Lisp has a reader macro for defining self-referential data structures: https://stackoverflow.com/a/605729 https://stackoverflow.com/a/605729 Maybe it wouldn't be so hard to extend this format to include a notation like that.
- qawwads 3y ago
  >Still, being able to take some arbitrary closure and kick it over the network to another racket instance would be great. It's not immediately obvious that csexp can do that. I'm stupid but once your list is reveived by the remote host, isn't executing it only an (eval) away?
  - jdkardia 3y ago
    I'm no lisper, but I'm pretty sure it'd take more than an eval because of the context a closure carries with it. if you were sending a pure, anonymous function, that would work fine. But if you're making a closure that makes use of any surrounding variables, libraries, or state, that's a non trivial set of information to transmit across the wire.
    - alexisread 3y ago
      I think this is where Delimited Dynamic binding would come in to play: https://okmij.org/ftp/papers/DDBinding.pdf https://okmij.org/ftp/papers/DDBinding.pdf I think that you would be able to freeze certain variables in the closure, and have others open eg. API_ENDPOINT variable might be configured to change between environments. Something like https://github.com/GiacomoCau/wat-js https://github.com/GiacomoCau/wat-js implements delimited continuations, ddbinding and algebraic effects (registered handlers for I/O etc) - pushing continuations over the network should be easier with these facilities.
  - EddieJLSH 3y ago
    Yeah that was my understanding, I've considered using this before (sending objects over the wire and eval'ing them) but never implemented it. Lisp seems very good for this sort of stuff.
- convolvatron 3y ago
  I used to do this on lispms...just `(lambda (x) ... ,z ...) assuming z is small what you would really do is make a lookup table and keep the closure locally and send a reference and forth. idk why we don't see this more, its a pretty straightforward way to lash together some programs
- correnos 3y ago
  The docs could do a better job of spelling it out, but csexp's really do only represent "trees of bytestrings". They're not a particularly rich format. If you're looking for "transfer this lambda over the network" semantics that's obviously a lot more complicated, but there's at least some research-project Schemes that've done it. The one I know of is Termite Scheme, which builds an Erlang-style distributed process model.
  - nerdponx 3y ago
    If that is indeed the case, then is it any better than an existing format like MessagePack?
    - JonChesterfield 3y ago
      I expect going digging would reveal that csexp is decades older than msgpack. As a format I agree it doesn't look great though. May 1997 for csexp. https://web.archive.org/web/20230219084819/http://people.csail.mit.edu/rivest/Sexp.txt https://web.archive.org/web/20230219084819/http://people.csa... Msgpack less clear, maybe 2008. JSON is 2000ish.
- aportnoy 3y ago
  > In general lisps _can't_ print arbitrary objects in a form that can be read back in. Hmm, why not?
  - JonChesterfield 3y ago
    I haven't worked on any of the classic lisp implementations but can speculate. I suppose the ratio of usefulness to difficulty of implementation doesn't work out. Mutable state with serialise/deserialise either breaks the aliasing or needs some way to keep the referenced variables alive (nasty interaction with garbage collection) and to re-establish aliasing on deserialise. Serialising a DAG to a tree tends to duplicate the previously shared nodes. There's then the question of whether deserialising the tree should re-establish the original sharing or some other sharing. Serialising a graph to a (finite) tree needs some notation to represent the cycles. It looks to me like mutable state is the blocker but I'd be interested in other opinions.
    - aportnoy 3y ago
      Yeah, something like "a" in the below code wouldn't have a "natural" serialization I don't think: (define a (list "a")) (set-cdr! a a)
  - cstrahan 3y ago
    How would one print a function with a free variable? Consider this (but imagine there is surrounding code which defines y): (lambda () y) How can we print this in such a way that preserves semantics? You can’t just print the original source definition, as y would then be undefined (or I suppose it could be defined to be whatever y is in scope at the deserialization call site or something thereabouts, but that wouldn’t guarantee that the deserialized function is equivalent to the other with respect to how it behaves, despite the source being identical). You can’t just inline the serialization of y, because the original function returns a particular reference, and there’s no guarantee that the rest of the dependent code will not expect a stable, unique (and possibly mutable/state-full) instance of this value. I suppose you could, on the side, also serialize the entire program state (or rather, at least the stack and heap), but then things get tricky when any object refers to something like an opaque pointer (even if you have an extent you can safely copy, you’d have to handle issues like different virtual addresses being mapped) or file descriptors, etc. But maybe all those challenges can be overcome — so I’ll ask: how would you go about serializing an arbitrary object in such a way that one could deserialize an equivalent object?
- zelphirkalt 3y ago
  The Racket webserver had serializable-lambda, but iirc it requires you to also make everything you use in it serializable (?). So it is kind of infactious like async in JS. You need to write your code with it in mind. Racketeers please correct me with an example of ad-hoc making a lambda serializable, if I am wrong about this.
Jtsummers 3y ago
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.
schemescape 3y ago
Is there anything similar for Common Lisp? For now, I’m using JSON because I’m paranoid about code injection attacks around print/read. I’ve seen a handful of libraries, but each one claims to protect against a different kind of attack, so that makes me think they might be vulnerable to the ones they don’t mention. Edit: I’m not sure if I understood this submission properly, but I’ll leave my question up since I’m still interested. Edit again: looks like someone asked this exact question on SO: https://stackoverflow.com/questions/34813891/how-do-you-securely-parse-untrusted-input-in-common-lisp https://stackoverflow.com/questions/34813891/how-do-you-secu...
- baq 3y ago
  JSON and this should be isomorphic if you squint a bit. You shouldn’t use eval for parsing sexps from the network in the same way you shouldn’t eval json in JavaScript (obvious yes I know but the solution is the same - use a parser instead)
  - schemescape 3y ago
    Right, that’s why I was asking if there was some sort of lossless encoding for simple Lisp types (“simple” I’m leaving undefined for now). For now, I encode everything as JSON, then decode back into lists, etc. on the other side (using cl-json). I was hoping there might be something more direct. But who knows, maybe the JSON libraries are so optimized they’re faster anyway!
- ducktective 3y ago
  Why would you want to transmit s-exps over a network? What's wrong with HTTPS or TCP/TLS?
  - schemescape 3y ago
    I meant over HTTPS.
    - EddieJLSH 3y ago
kazinator 3y ago
I did a length:data encoding in the fake Lisp-like library in cppawk. Haha. For instance cons(1, 1) produces "C1,1:12". Type code C followed by two decimal integers separated by a comma, terminated by colon, followed by the car/cdr data. The decimal integers give the lengths of the car and cdr part after the colon. https://www.kylheku.com/cgit/cppawk/tree/cppawk-cons.1 https://www.kylheku.com/cgit/cppawk/tree/cppawk-cons.1 The list (1 2 3) looks like "C1,12:1C1,6:2C1,0:3" . A cursory scan through the string tells us that there are three C's, so three cells in there. Note the C1,0:3 at the end: (3 . nil). nil is a zero length object: the empty string represents nil. So the cdr length of the last cell is zero.

109 points by thefilmore 3y ago

Doesn't say anything about cycles or what datatypes can be serialised. In general lisps _can't_ print arbitrary objects in a form that can be read back in. E.g. Welcome to Racket v7.9 [bc]. > (lambda (x) x) #<procedure> 7.9 doesn't have csexp, was curious what it would do with a function object but not quite curious enough to install a racket from outside the package manager. It seems relatively likely that racket would have some serialisation feature that can round trip arbitrary objects through a bytestring though initial guesses haven't worked out for me > (require racket/serialize) > (serializable? (lambda (x) x)) #f Still, being able to take some arbitrary closure and kick it over the network to another racket instance would be great. It's not immediately obvious that csexp can do that.

nerdponx 3y ago
Common Lisp has a reader macro for defining self-referential data structures: https://stackoverflow.com/a/605729 https://stackoverflow.com/a/605729 Maybe it wouldn't be so hard to extend this format to include a notation like that.
qawwads 3y ago
>Still, being able to take some arbitrary closure and kick it over the network to another racket instance would be great. It's not immediately obvious that csexp can do that. I'm stupid but once your list is reveived by the remote host, isn't executing it only an (eval) away?
- jdkardia 3y ago
  I'm no lisper, but I'm pretty sure it'd take more than an eval because of the context a closure carries with it. if you were sending a pure, anonymous function, that would work fine. But if you're making a closure that makes use of any surrounding variables, libraries, or state, that's a non trivial set of information to transmit across the wire.
  - alexisread 3y ago
    I think this is where Delimited Dynamic binding would come in to play: https://okmij.org/ftp/papers/DDBinding.pdf https://okmij.org/ftp/papers/DDBinding.pdf I think that you would be able to freeze certain variables in the closure, and have others open eg. API_ENDPOINT variable might be configured to change between environments. Something like https://github.com/GiacomoCau/wat-js https://github.com/GiacomoCau/wat-js implements delimited continuations, ddbinding and algebraic effects (registered handlers for I/O etc) - pushing continuations over the network should be easier with these facilities.
- EddieJLSH 3y ago
  Yeah that was my understanding, I've considered using this before (sending objects over the wire and eval'ing them) but never implemented it. Lisp seems very good for this sort of stuff.
convolvatron 3y ago
I used to do this on lispms...just `(lambda (x) ... ,z ...) assuming z is small what you would really do is make a lookup table and keep the closure locally and send a reference and forth. idk why we don't see this more, its a pretty straightforward way to lash together some programs
correnos 3y ago
The docs could do a better job of spelling it out, but csexp's really do only represent "trees of bytestrings". They're not a particularly rich format. If you're looking for "transfer this lambda over the network" semantics that's obviously a lot more complicated, but there's at least some research-project Schemes that've done it. The one I know of is Termite Scheme, which builds an Erlang-style distributed process model.
- nerdponx 3y ago
  If that is indeed the case, then is it any better than an existing format like MessagePack?
  - JonChesterfield 3y ago
    I expect going digging would reveal that csexp is decades older than msgpack. As a format I agree it doesn't look great though. May 1997 for csexp. https://web.archive.org/web/20230219084819/http://people.csail.mit.edu/rivest/Sexp.txt https://web.archive.org/web/20230219084819/http://people.csa... Msgpack less clear, maybe 2008. JSON is 2000ish.
aportnoy 3y ago
> In general lisps _can't_ print arbitrary objects in a form that can be read back in. Hmm, why not?
- JonChesterfield 3y ago
  I haven't worked on any of the classic lisp implementations but can speculate. I suppose the ratio of usefulness to difficulty of implementation doesn't work out. Mutable state with serialise/deserialise either breaks the aliasing or needs some way to keep the referenced variables alive (nasty interaction with garbage collection) and to re-establish aliasing on deserialise. Serialising a DAG to a tree tends to duplicate the previously shared nodes. There's then the question of whether deserialising the tree should re-establish the original sharing or some other sharing. Serialising a graph to a (finite) tree needs some notation to represent the cycles. It looks to me like mutable state is the blocker but I'd be interested in other opinions.
  - aportnoy 3y ago
    Yeah, something like "a" in the below code wouldn't have a "natural" serialization I don't think: (define a (list "a")) (set-cdr! a a)
- cstrahan 3y ago
  How would one print a function with a free variable? Consider this (but imagine there is surrounding code which defines y): (lambda () y) How can we print this in such a way that preserves semantics? You can’t just print the original source definition, as y would then be undefined (or I suppose it could be defined to be whatever y is in scope at the deserialization call site or something thereabouts, but that wouldn’t guarantee that the deserialized function is equivalent to the other with respect to how it behaves, despite the source being identical). You can’t just inline the serialization of y, because the original function returns a particular reference, and there’s no guarantee that the rest of the dependent code will not expect a stable, unique (and possibly mutable/state-full) instance of this value. I suppose you could, on the side, also serialize the entire program state (or rather, at least the stack and heap), but then things get tricky when any object refers to something like an opaque pointer (even if you have an extent you can safely copy, you’d have to handle issues like different virtual addresses being mapped) or file descriptors, etc. But maybe all those challenges can be overcome — so I’ll ask: how would you go about serializing an arbitrary object in such a way that one could deserialize an equivalent object?
zelphirkalt 3y ago
The Racket webserver had serializable-lambda, but iirc it requires you to also make everything you use in it serializable (?). So it is kind of infactious like async in JS. You need to write your code with it in mind. Racketeers please correct me with an example of ad-hoc making a lambda serializable, if I am wrong about this.

Jtsummers 3y ago

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.

schemescape 3y ago

Is there anything similar for Common Lisp? For now, I’m using JSON because I’m paranoid about code injection attacks around print/read. I’ve seen a handful of libraries, but each one claims to protect against a different kind of attack, so that makes me think they might be vulnerable to the ones they don’t mention. Edit: I’m not sure if I understood this submission properly, but I’ll leave my question up since I’m still interested. Edit again: looks like someone asked this exact question on SO: https://stackoverflow.com/questions/34813891/how-do-you-securely-parse-untrusted-input-in-common-lisp https://stackoverflow.com/questions/34813891/how-do-you-secu...

baq 3y ago
JSON and this should be isomorphic if you squint a bit. You shouldn’t use eval for parsing sexps from the network in the same way you shouldn’t eval json in JavaScript (obvious yes I know but the solution is the same - use a parser instead)
- schemescape 3y ago
  Right, that’s why I was asking if there was some sort of lossless encoding for simple Lisp types (“simple” I’m leaving undefined for now). For now, I encode everything as JSON, then decode back into lists, etc. on the other side (using cl-json). I was hoping there might be something more direct. But who knows, maybe the JSON libraries are so optimized they’re faster anyway!
ducktective 3y ago
Why would you want to transmit s-exps over a network? What's wrong with HTTPS or TCP/TLS?
- schemescape 3y ago
  I meant over HTTPS.
  - EddieJLSH 3y ago

kazinator 3y ago

I did a length:data encoding in the fake Lisp-like library in cppawk. Haha. For instance cons(1, 1) produces "C1,1:12". Type code C followed by two decimal integers separated by a comma, terminated by colon, followed by the car/cdr data. The decimal integers give the lengths of the car and cdr part after the colon. https://www.kylheku.com/cgit/cppawk/tree/cppawk-cons.1 https://www.kylheku.com/cgit/cppawk/tree/cppawk-cons.1 The list (1 2 3) looks like "C1,12:1C1,6:2C1,0:3" . A cursory scan through the string tells us that there are three C's, so three cells in there. Note the C1,0:3 at the end: (3 . nil). nil is a zero length object: the empty string represents nil. So the cdr length of the last cell is zero.