5 ms·

Neat! I've commented about this very problem before on several of the many threads regarding "object pipes", ie. REPLs. http://news.ycombinator.com/item?id=103

Neat! I've commented about this very problem before on several of the many threads regarding "object pipes", ie. REPLs. http://news.ycombinator.com/item?id=1033623 http://news.ycombinator.com/item?id=1033623 http://news.ycombinator.com/item?id=1566325 http://news.ycombinator.com/item?id=1566325 http://news.ycombinator.com/item?id=2527217 http://news.ycombinator.com/item?id=2527217 Since that last comment, I've been working a bunch with Clojure, which has a far more expressive variant of JSON, as well as some heavy duty work with Google's Protocol Buffers. A few points: 1) Piping non-serializable objects is a BAD IDEA. That's not a shell, that's a REPL. And even in a REPL, you should prefer inert data, a la Clojure's immutable data structures. 2) Arbitrary bit streams is, fundamentally, unbeatable. It's completely universal. Some use cases really don't want structured data. Consider gzip: you just want to take bytes in and send bytes out. You don't necessarily want typed data in the pipes, you want typed pipes, which may or may not contain typed data. This is the "format negotiation" piece that is mentioned in the original post. I'd like to see more details about that. 3) There seems to be some nebulous lowest common denominator of serializable data. So many things out there: GVariant, Clojure forms, JSON, XML, ProtoBuf, Thirft, Avro, ad infinitum. If everything talks its own serialization protocol, then none of the "do one thing well" benefits work. Every component needs to know every protocol. One has to "win" in a collaborative shell environment. I need to study GVariant more closely. 4) Whichever format "wins", it needs to be self-describing. A table format command can't work on field names, unless it has the field names! ProtoBufs and Thrift are out, because you need to have field names pre-compiled on either side of the pipe. Unless, of course, you start with a MessageDescriptor object up front, which ProtoBufs support and Avro has natively, but I digress: Reflection is necessary. It's not clear if you need header descriptors a la MessageDescriptor/Avro, or inline field descriptions a la JSON/XML/Clojure. Or a mix of both? 5) Order is critical. There's a reason these formats are called "serializable". Clojure, for example, provides sets using the #{} notation. And, like JSON, supports {} map notation. Thrift has Maps and Sets too. ProtoBufs, however, don't. On purpose. And it's a good thing! The data is going to come across the pipe in series, so a map or set doesn't make sense. Use a sequence of key-value-pairs. It might even be an infinite sequence! It's one thing to support un-ordered data when printing and reading data. It's another thing entirely to design a streaming protocol around un-ordered data. Shells need a streaming protocol. 6) Going back to content negotiation, this streaming protocol might be able to multiplex types over a single stream. Maybe gzip sends a little structured metadata up front, then a binary stream. ProtoBufs label all "bytes" fields with a size, but you might not know the size in advanced. Maybe you need two synchronized streams on which you can multiplex a control channel? That is, each pipe is two pipes. One request/response pair and the other a modal byte stream vs typed message stream. Overall. This is the nicest attempt at this idea I've seen yet. I've been meaning to take a crack at it myself, but refused to do it without enough time to re-create the entire standard Unix toolkit plus my own shell ;-)

alexlarsson 14y ago
Regarding order. The dtools approach uses a stream (i.e. potentially infinite) of variants. Each variant is a self contained typed data chunk which is by itself not "streamable" (i.e. you have to read all of it). The data chunk is strongly typed and the type is self-described. The supported primitive types are: bool, byte, int16, uint16, int32, uint32, int64, uint64, double, utf8 string (+ some dbus specific things). These can be recursively combined with: arrays (of same type), tuples, dicts (primitive type -> any type map), maybe type, and variant type In my dps example I generate a stream of dictionaries mapping from string to variant (i.e. any type). The type of each item in the map differs. For instance cmdvec is an array of strings, whereas euid is an uint32.
- snprbob86 14y ago
  Thanks. I looked at the GVariant page a bunch too. It seems like the encoding is a steam of {type, value} pairs, where values can contain per-type headers as well. Protobufs, on the other hand, use {field, wire-type, value} where field is required to have an externally known type to parse value, but wire-type is sufficient to determine the length of value, so you can skip unknown fields (used for backwards compatible protocols). In theory, required fields could omit field and wire-type, but Protobufs deemed it more complexity than justifies the space and performance impact. Primitive values like integers are totally expected in any such format like this. Their salient feature being that they're of known length. I'm a little more leery about "arrays" or other data structures of variable length which are encoded with a known length. Consider Pascal strings {length, [chars]} vs C strings {[chars], NULL}. The later lends itself much better to streaming protocols, but the former is far simpler to work with when you have a complete dataset. I ran into this situation with a Protobuf I was designing where the first attempt had a message with a repeated field, but it became obvious that I wanted a begin message, a repeated message of singular fields, and then an end message, to allow a fast-start on the send, which didn't require to know the full data set length up front. There are, however, situations where you do want the length up front. For example, if you need to allocate space to put things. You can get faster parsing if you know the total message size immediately. In general, however, I don't think it matters all that much with modern languages and hardware. This is one reason why Clojure has both lists and vectors. Lists are lazy head/tail pairs and (count some-vector) is a constant time operation. Unfortunately, Clojure's reader doesn't seem to offer streaming reads of lists (I may be wrong about this). The bigger issue with unbounded values is that they are more difficult to work with in most languages. Haskell, Lisps, and other functional languages fair far better than most, but once you start mixing fixed-sized messages with known fields, with variable-sized sequences, you wind up with a situation like {x, [ys], z} where a piece of code wants to look at z before looking at ys. If that tuple is represented as an associative structure {:x 1, :ys [2 3], :z 4} then it's suddenly very confusing that it's an ORDERED map and all sorts of assumptions go out the window. Even more fundamentally: Source code is a serialized protocol. You write down text and the order of the characters on the page have meaning. Sometimes, that order may be over-specified, but regardless, humans see order and make assumptions from it, even when order doesn't matter.

alexlarsson 14y ago

Regarding order. The dtools approach uses a stream (i.e. potentially infinite) of variants. Each variant is a self contained typed data chunk which is by itself not "streamable" (i.e. you have to read all of it). The data chunk is strongly typed and the type is self-described. The supported primitive types are: bool, byte, int16, uint16, int32, uint32, int64, uint64, double, utf8 string (+ some dbus specific things). These can be recursively combined with: arrays (of same type), tuples, dicts (primitive type -> any type map), maybe type, and variant type In my dps example I generate a stream of dictionaries mapping from string to variant (i.e. any type). The type of each item in the map differs. For instance cmdvec is an array of strings, whereas euid is an uint32.

snprbob86 14y ago
Thanks. I looked at the GVariant page a bunch too. It seems like the encoding is a steam of {type, value} pairs, where values can contain per-type headers as well. Protobufs, on the other hand, use {field, wire-type, value} where field is required to have an externally known type to parse value, but wire-type is sufficient to determine the length of value, so you can skip unknown fields (used for backwards compatible protocols). In theory, required fields could omit field and wire-type, but Protobufs deemed it more complexity than justifies the space and performance impact. Primitive values like integers are totally expected in any such format like this. Their salient feature being that they're of known length. I'm a little more leery about "arrays" or other data structures of variable length which are encoded with a known length. Consider Pascal strings {length, [chars]} vs C strings {[chars], NULL}. The later lends itself much better to streaming protocols, but the former is far simpler to work with when you have a complete dataset. I ran into this situation with a Protobuf I was designing where the first attempt had a message with a repeated field, but it became obvious that I wanted a begin message, a repeated message of singular fields, and then an end message, to allow a fast-start on the send, which didn't require to know the full data set length up front. There are, however, situations where you do want the length up front. For example, if you need to allocate space to put things. You can get faster parsing if you know the total message size immediately. In general, however, I don't think it matters all that much with modern languages and hardware. This is one reason why Clojure has both lists and vectors. Lists are lazy head/tail pairs and (count some-vector) is a constant time operation. Unfortunately, Clojure's reader doesn't seem to offer streaming reads of lists (I may be wrong about this). The bigger issue with unbounded values is that they are more difficult to work with in most languages. Haskell, Lisps, and other functional languages fair far better than most, but once you start mixing fixed-sized messages with known fields, with variable-sized sequences, you wind up with a situation like {x, [ys], z} where a piece of code wants to look at z before looking at ys. If that tuple is represented as an associative structure {:x 1, :ys [2 3], :z 4} then it's suddenly very confusing that it's an ORDERED map and all sorts of assumptions go out the window. Even more fundamentally: Source code is a serialized protocol. You write down text and the order of the characters on the page have meaning. Sometimes, that order may be over-specified, but regardless, humans see order and make assumptions from it, even when order doesn't matter.