[HN Gopher] Csexp: S-Expressions over the Network
___________________________________________________________________
Csexp: S-Expressions over the Network
Author : thefilmore
Score : 64 points
Date : 2023-06-11 16:28 UTC (6 hours ago)
(HTM) web link (docs.racket-lang.org)
(TXT) w3m dump (docs.racket-lang.org)
| JonChesterfield wrote:
| 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.
| convolvatron wrote:
| 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
| aportnoy wrote:
| > In general lisps _can't_ print arbitrary objects in a form
| that can be read back in.
|
| Hmm, why not?
| cstrahan wrote:
| 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?
| aportnoy wrote:
| In the original LISP with dynamic scoping I think it would
| be fair to serialize that expression as is: "just use
| whatever value is bound to 'y' at the time of evaluation,
| if any".
| endgame wrote:
| > How can we print this in such a way that preserves
| semantics?
|
| Maybe try something like normalisation-by-evaluation, but
| if you go to look up a free variable, replace that lookup
| with a little bit of syntax tree instead?
| aportnoy wrote:
| Everything is an object that is either a cons cell or an
| atom. Associate the address of each object with a unique
| index.
|
| Serialize each object as a pair (index, obj), where 'index'
| maps back to the original address where the object was
| stored, and 'obj' is a pair of indices if the object is a
| cons cell, or the appropriate representation (string
| literal, integer, etc.) if the object is an atom.
|
| Then to deserialize allocate a memory location for every
| index and load the objects as is. Then replace the indices
| with the corresponding (new) addresses.
| aportnoy wrote:
| This definitely isn't "printing" in the original sense,
| just a serialization algorithm.
| JonChesterfield wrote:
| 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 wrote:
| Yeah, something like "a" in the below code wouldn't have a
| "natural" serialization I don't think:
| (define a (list "a")) (define b (list "b"))
| (set-cdr! a b) (set-cdr! b a)
| nerdponx wrote:
| Common Lisp has a reader macro for defining self-referential
| data structures: https://stackoverflow.com/a/605729
|
| Maybe it wouldn't be so hard to extend this format to include a
| notation like that.
| correnos wrote:
| 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 wrote:
| If that is indeed the case, then is it any better than an
| existing format like MessagePack?
| qawwads wrote:
| >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 wrote:
| 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 wrote:
| I think this is where Delimited Dynamic binding would come
| in to play: 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
| 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 wrote:
| 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.
| Jtsummers wrote:
| 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...
| koolba wrote:
| That looks surprisingly like bencode used by BitTorrent.
| neilv wrote:
| 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,
| 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 wrote:
| Yes good call, I changed the broken Wikipedia links to the
| archive page -
| 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 wrote:
| Length suffixes are for the truly insane.
| correnos wrote:
| 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.
| [deleted]
| chubot wrote:
| 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 ...
| correnos wrote:
| 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.
| schemescape wrote:
| 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-secu...
| fiddlerwoaroof wrote:
| I think this should be safe: https://github.com/phoe/safe-read
|
| This doesn't provide such functionality out of the box, but it
| makes it pretty trivial to produce a custom READ that only has
| the features you want:
| https://github.com/s-expressionists/Eclector
|
| It's not exactly the right input format, and has a couple
| outstanding performance issues, but I wrote a parser for EDN
| which should be safe against code injection:
| https://github.com/fiddlerwoaroof/cl-edn
| schemescape wrote:
| Thanks! safe-read and this other one are what I'd seen
| before: https://github.com/mabragor/cl-secure-read
|
| I'll look at them more closely.
| ducktective wrote:
| Why would you want to transmit s-exps over a network? What's
| wrong with HTTPS or TCP/TLS?
| schemescape wrote:
| I meant over HTTPS.
| EddieJLSH wrote:
| What's the realistic issue with code injection over HTTPS
| TCP parsing into expected messages? If it is an issue for
| your system, can't you try read into some expected shape
| and throw an error if it doesn't parse to circumvent that?
| schemescape wrote:
| I was specifically talking about Common Lisp's print/read
| functions which are not safe for untrusted input:
|
| https://github.com/salewski/cl-safe-
| read/blob/master/README....
| stefncb wrote:
| The solution is to not use the reader and instead write a
| parser yourself. S-Expressions are really simple, you should be
| able to do that quite easily.
| schemescape wrote:
| I was hoping it was easy enough that someone had already done
| it :)
|
| Escaping strings and parsing floating point numbers isn't
| something I enjoy.
| baq wrote:
| 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 wrote:
| 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!
___________________________________________________________________
(page generated 2023-06-11 23:00 UTC)