4 ms·

I disagree. The difference between a dict and a list of key-value pairs should be left as an implementation detail in the receiver, not specified in the protoco

by tlb 6y ago

I disagree. The difference between a dict and a list of key-value pairs should be left as an implementation detail in the receiver, not specified in the protocol. S-expressions get this right. If the receiver knows they'll be doing a lot of lookup, they can build an indexed structure. If not, they can use something like assoc (which does a linear scan). The linear scan is probably faster with less than 5 entries anyway.

thelazydogsback 6y ago
But you won't know at parse-time how to tread the item. Below we have duplicate "keys" and an atom in the middle of a k/v list -- what do we do here? Are the dup keys an error, or do we make a multi-map? Do we throw away the atom or assume it's a key with a nil value? ((k1 v1)(k1 v2) ... (k4532 v4532) anAtom (k4533 v4533) ...) It's stuff like this that makes Erlang/Elixir really weird -- it needs to look at the format of every item first to determine what it's going to be or how it's going to be printed. (Is it bunch of numbers, or a string? Is it a dictionary, or just a list of keys and values?)
- chriswarbo 6y ago
  > But you won't know at parse-time how to tread[sic] the item. I would follow the advice from LangSec ( http://langsec.org http://langsec.org ) and "parse, don't validate" ( https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-va... ): - Parsing isn't just turning bytes into some generic tree representation (JSON/SAX/s-expr/etc.); it also includes subsequent domain/application specific input handling, e.g. constructing custom objects, checking certain invariants, etc. Note that we don't need custom objects; but we should still be checking the required invariants of our 'List[Tuple[String, Bool]]', or whatever. - Parsing should be done up-front, processing should use its output; e.g. we shouldn't be passing around generic types like 'JsonObject', 'AssocList', etc. (unless our application is generic JSON/s-expr processor, of course!). Note that we can still do streaming/lazy processing, with data parsed on-demand, but we should be careful about what side-effects might be performed part-way-through a broken input (this would apply to any approach though, e.g. hitting invalid bytes part way through some JSON) Examples like your broken assoc-list will hence be spotted at parse time; maybe not at the bytes->tree step, but certainly at the tree->domain-model step.
  - thelazydogsback 6y ago
    I agree that that is how a parsing & instantiating framework should be built, and you should be able to hook in at any level -- but the reality is that normally when one consumes such data you are using both functions at the same time - de-serializing. Having list vs. set vs map notations is both syntax (for parsing) and really a form of meta-data, making explicit what promises are made of the data, and therefore hinting at which data-structs you may want to instantiate from the data. I suppose that ideally the meta-data should be a separate, optional statement made about the data, but that's not the M.O. for any common formats.
kevincox 6y ago
There is a difference between semantics and implementation. There is nothing forcing you to turn a JSON object into a hash table. You can easily store it into a list of pairs. However the semantics are obvious, this is a mapping, order doesn't matter and there shouldn't be duplicates. If you just see a list of pairs it is less obvious what is meant. That being said you can easily argue that the JSON data types aren't expressive enough to capture many common semantics so you end up needing external documentation anyways.
codeflo 6y ago
I think we mostly agree, but would put it a bit differently. First, I think performance is a bit of a red-herring in this discussion. If a linear scan is really faster for five entries, a good dictionary implementation could simply switch to that. Second, and more to the point, there’s a obviously a semantic difference between a list of pairs and a dictionary. That’s always going to be part of the “protocol” - whether your serialization format is capable of expressing that or not. However, and I think this is where we agree, there are lots of semantic distinctions that JSON can’t express (dates vs. strings, to pick an example I encounter often). So in many cases, you’re going to have a deserialization step anyway that validates the JSON values and converts them into the objects you actually want to use in your application. Why, among all the semantic distinctions that JSON doesn’t capture, is the list/dictionary distinction so special that it needs this kind of syntactic support in a serialization format? (BTW, for JSON, the answer is obviously rooted in JavaScript’s type system. But while that makes it particularly nice to use JSON to serialize JavaScript objects, the context here is its use as a general-purpose serialization format.)
- HelloNurse 6y ago
  There's a difference between a list of pairs, which is the one that is equivalent to a dictionary, and a list of lists that all happen to have length 2; and between an unordered multiset and an ordered list.

by tlb 6y ago

thelazydogsback 6y ago

But you won't know at parse-time how to tread the item. Below we have duplicate "keys" and an atom in the middle of a k/v list -- what do we do here? Are the dup keys an error, or do we make a multi-map? Do we throw away the atom or assume it's a key with a nil value? ((k1 v1)(k1 v2) ... (k4532 v4532) anAtom (k4533 v4533) ...) It's stuff like this that makes Erlang/Elixir really weird -- it needs to look at the format of every item first to determine what it's going to be or how it's going to be printed. (Is it bunch of numbers, or a string? Is it a dictionary, or just a list of keys and values?)

chriswarbo 6y ago
> But you won't know at parse-time how to tread[sic] the item. I would follow the advice from LangSec ( http://langsec.org http://langsec.org ) and "parse, don't validate" ( https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-va... ): - Parsing isn't just turning bytes into some generic tree representation (JSON/SAX/s-expr/etc.); it also includes subsequent domain/application specific input handling, e.g. constructing custom objects, checking certain invariants, etc. Note that we don't need custom objects; but we should still be checking the required invariants of our 'List[Tuple[String, Bool]]', or whatever. - Parsing should be done up-front, processing should use its output; e.g. we shouldn't be passing around generic types like 'JsonObject', 'AssocList', etc. (unless our application is generic JSON/s-expr processor, of course!). Note that we can still do streaming/lazy processing, with data parsed on-demand, but we should be careful about what side-effects might be performed part-way-through a broken input (this would apply to any approach though, e.g. hitting invalid bytes part way through some JSON) Examples like your broken assoc-list will hence be spotted at parse time; maybe not at the bytes->tree step, but certainly at the tree->domain-model step.
- thelazydogsback 6y ago
  I agree that that is how a parsing & instantiating framework should be built, and you should be able to hook in at any level -- but the reality is that normally when one consumes such data you are using both functions at the same time - de-serializing. Having list vs. set vs map notations is both syntax (for parsing) and really a form of meta-data, making explicit what promises are made of the data, and therefore hinting at which data-structs you may want to instantiate from the data. I suppose that ideally the meta-data should be a separate, optional statement made about the data, but that's not the M.O. for any common formats.

kevincox 6y ago

There is a difference between semantics and implementation. There is nothing forcing you to turn a JSON object into a hash table. You can easily store it into a list of pairs. However the semantics are obvious, this is a mapping, order doesn't matter and there shouldn't be duplicates. If you just see a list of pairs it is less obvious what is meant. That being said you can easily argue that the JSON data types aren't expressive enough to capture many common semantics so you end up needing external documentation anyways.

codeflo 6y ago

I think we mostly agree, but would put it a bit differently. First, I think performance is a bit of a red-herring in this discussion. If a linear scan is really faster for five entries, a good dictionary implementation could simply switch to that. Second, and more to the point, there’s a obviously a semantic difference between a list of pairs and a dictionary. That’s always going to be part of the “protocol” - whether your serialization format is capable of expressing that or not. However, and I think this is where we agree, there are lots of semantic distinctions that JSON can’t express (dates vs. strings, to pick an example I encounter often). So in many cases, you’re going to have a deserialization step anyway that validates the JSON values and converts them into the objects you actually want to use in your application. Why, among all the semantic distinctions that JSON doesn’t capture, is the list/dictionary distinction so special that it needs this kind of syntactic support in a serialization format? (BTW, for JSON, the answer is obviously rooted in JavaScript’s type system. But while that makes it particularly nice to use JSON to serialize JavaScript objects, the context here is its use as a general-purpose serialization format.)

HelloNurse 6y ago
There's a difference between a list of pairs, which is the one that is equivalent to a dictionary, and a list of lists that all happen to have length 2; and between an unordered multiset and an ordered list.