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
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.
>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?
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.
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.
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.
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
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.
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.
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?
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.
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".
> 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?
It is correct that usually Lisps do not have a print-read consistency for every object, just objects that someone has decided to care about. Most Common Lisps are like this. However, note that many of them have image saving. Image saving traverses the heap and serializes every object. That includes lexical closures. Their code vector, environment vector(s): everything is traversed. It's just not a printed notation!
If some object isn't printable and someone wants it badly to be, it can be arranged somehow.
It boils down to pragmatics.
Foreign objects (FFI handles holding foreign pointers) are going to be tricky; you would need some hooking mechanism to try to do something meaningful.
Image saving already cannot do some things, like saving open network connections such that they come up connected in a restarted image.
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.
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.
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.
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.
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.
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.
> 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.
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.
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)
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!
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?
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.
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
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.
45 comments
[ 0.20 ms ] story [ 101 ms ] threadMaybe it wouldn't be so hard to extend this format to include a notation like that.
I'm stupid but once your list is reveived by the remote host, isn't executing it only an (eval) away?
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.
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.
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
May 1997 for csexp. https://web.archive.org/web/20230219084819/http://people.csa...
Msgpack less clear, maybe 2008. JSON is 2000ish.
Hmm, why not?
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.
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?
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.
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?
https://docs.racket-lang.org/web-server-internal/closure.htm...
It is correct that usually Lisps do not have a print-read consistency for every object, just objects that someone has decided to care about. Most Common Lisps are like this. However, note that many of them have image saving. Image saving traverses the heap and serializes every object. That includes lexical closures. Their code vector, environment vector(s): everything is traversed. It's just not a printed notation!
If some object isn't printable and someone wants it badly to be, it can be arranged somehow.
It boils down to pragmatics.
Foreign objects (FFI handles holding foreign pointers) are going to be tricky; you would need some hooking mechanism to try to do something meaningful.
Image saving already cannot do some things, like saving open network connections such that they come up connected in a restarted image.
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...
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.
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.
With netstrings, it's
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 ...
Namely interoperability between Lisps
https://github.com/slime/slime/blob/master/swank.lisp
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
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...
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!
https://github.com/salewski/cl-safe-read/blob/master/README....
Escaping strings and parsing floating point numbers isn’t something I enjoy.
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
I’ll look at them more closely.
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
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.