4 ms·

Another flaw in JSON is that there's no built-in way to connote referential integrity. Which is another way of saying that JSON can represent trees but not arbi

Another flaw in JSON is that there's no built-in way to connote referential integrity. Which is another way of saying that JSON can represent trees but not arbitrary graphs. Here's a circular list for example in Common Lisp: #1='(foo bar baz #1#) [Printing that is a good way to overflow your stack] More usefully, here is an employee who is an acting supervisor of himself: '(:employee #1="Frank Smith" :supervisor #1#) There are ways around this problem in JSON but it requires a bespoke parser. In Common Lisp it's built in to the reader.

skissane 4y ago
Self-reference causes a lot of issues. Sometimes I wonder if it should just be prohibited, forcing everything to be a directed acyclic graph. If a language has only immutable data structures, it is easy to make it so that self-reference becomes impossible, just by making sure your primitives for constructing values don't permit cycles to be constructed. Even if you allow mutable data structures, it is still possible. For mutable compound heap objects (i.e. heap objects which possibly container pointers to other heap objects), they can have a back-pointer pointing to their parent. If you think about it, you can flesh out some rules about how to manipulate these objects which will make cyclic references impossible. When the rules are violated, rather than failing the operation, you could just add a pointer to a deep copy instead. (Not completely deep, you can still share rather than copy non-compound heap objects, such as strings–sharing non-compound objects can't produce cycles.) Banning direct self-reference doesn't mean nothing can ever refer to itself, just not directly. So, you couldn't have #1='(employee :name "Frank Smith" :supervisor #1#). But you could have something like '(employee :id 1 :name "Frank Smith" :supervisor (ref :to employee :id 1)). At a physical level there is no self-reference, but at a logical level there still is. Similarly, one would want to allow cyclic references via a symbol, so a symbol can occur in its own binding. So not completely banning self-reference, just limiting it, in the hope that limiting it will limit the issues it causes. I think, using the strategies I've outlined above, reference counting will work as a garbage collection strategy, without the possibility of memory leaks from cyclic references. (Allowing a symbol's binding to refer to itself will not leak memory, since a bound symbol should still exist even if nobody refers to it; to deallocate it, you have to explicitly unbind it, which will remove the binding, breaking the self-reference and allowing the reference count to fall to zero.)
- JonChesterfield 4y ago
  Causes problems with functions though as you lose straightforward recursion. That leaves you with either define creating cycles, or introducing letrec to create cycles, or the dubious beauty of the Y combinator. The acyclic heap is a great property for most data but it's annoying for representing programs. It might be reasonable to restrict letrec to creating functions, and ensure they're all statically allocated, which would give an acyclic data heap with direct representation of functions.
  - skissane 4y ago
    I still think cycles should be allowed via symbols – just not directly. Allowing cycles via symbols tends to be less of a problem: (1) you don't want to garbage collect bound symbols, and once the symbol is unbound the cycle is broken (it would remove the ability to treat environments as first class objects, but maybe the other advantages are worth that cost); (2) printing values generally just prints the symbol name not its binding; (3) very often when you recurse through a data structure, you don't recurse into the binding of symbols contained in it, so that entails a significant reduction in the potential for infinite recursion bugs. It does mean you can't have an anonymous function which recurses, but that's a relatively rare use case. And actually, if you introduce some kind of special syntax which refers to "this lambda", you can even permit direct recursion of anonymous functions. Mutually recursive anonymous functions would be harder to support–maybe not impossible to support, but such an obscure use case it probably isn't worth thinking about.
- kazinator 4y ago
  The referential integrity dreamcompiler refers to isn't just for cycles in the structure, but for substructure sharing. Substructure sharing still occurs in a DAG, unless you rule it out also (e.g. with some strict one reference ownership model or whatever). In the absence of cycles, it is still useful to have a notation which says "these two objects in the DAG are actually the same node". If you implement that, the detection of cycles is almost free, because the assumption that a duplicate node appearing in the print is not a descendant of the previous one doesn't simplify the printing or reading algorithms very much. In order to print this #1=(... #1#) you have to determine that the given object occurs inside itself. In order to print (#1=(whatever) #1#), you have to determine that the given object occurs later in a sibling expression. Knowing that #1# will not occur inside (whatever) doesn't help all that much with anything; it doesn't help you decide whether or not the #1= prefix needs to be printed. If anything if the restrictions were reversed, it would be simpler: if the only substructure sharing that were allowed was backward references, that helps. Because then we know that the (whatever) object can only occur again inside (whatever), and not after it. To detect nothing but cycles, without caring about other sharing, we just have to maintain an object path across the recursion so that for every visited object we can ask "is this object already in the path from root to here?" If so we have a backreference. The sibling case is harder. You can have situations like: ((((#1=(foo)))) (((#1#)))) Deep inside the left item in the list there is an object which occurs again deep in the right item. We need to put the objects we are visiting into a hash, which is pretty expensive. > Just by making sure your primitives for constructing values don't permit cycles to be constructed. But lambda calculus teaches us that if all we have is functions being passed to functions and binding arguments we can build a circular reference. See the middle word of the domain in the browser address bar. So you have to further dumb things down from there if you want to absolutely eliminate cycles in the object graph. (You can have it so that you don't care about function-induced cycles (only the garbage collector does) by not having any printed notation or other API that traverses the internals of a function. The application can still build a graph using functions, but is "on its own" as far as providing its own functions for operating on it, and serializing it and whatnot.)

skissane 4y ago

Self-reference causes a lot of issues. Sometimes I wonder if it should just be prohibited, forcing everything to be a directed acyclic graph. If a language has only immutable data structures, it is easy to make it so that self-reference becomes impossible, just by making sure your primitives for constructing values don't permit cycles to be constructed. Even if you allow mutable data structures, it is still possible. For mutable compound heap objects (i.e. heap objects which possibly container pointers to other heap objects), they can have a back-pointer pointing to their parent. If you think about it, you can flesh out some rules about how to manipulate these objects which will make cyclic references impossible. When the rules are violated, rather than failing the operation, you could just add a pointer to a deep copy instead. (Not completely deep, you can still share rather than copy non-compound heap objects, such as strings–sharing non-compound objects can't produce cycles.) Banning direct self-reference doesn't mean nothing can ever refer to itself, just not directly. So, you couldn't have #1='(employee :name "Frank Smith" :supervisor #1#). But you could have something like '(employee :id 1 :name "Frank Smith" :supervisor (ref :to employee :id 1)). At a physical level there is no self-reference, but at a logical level there still is. Similarly, one would want to allow cyclic references via a symbol, so a symbol can occur in its own binding. So not completely banning self-reference, just limiting it, in the hope that limiting it will limit the issues it causes. I think, using the strategies I've outlined above, reference counting will work as a garbage collection strategy, without the possibility of memory leaks from cyclic references. (Allowing a symbol's binding to refer to itself will not leak memory, since a bound symbol should still exist even if nobody refers to it; to deallocate it, you have to explicitly unbind it, which will remove the binding, breaking the self-reference and allowing the reference count to fall to zero.)

JonChesterfield 4y ago
Causes problems with functions though as you lose straightforward recursion. That leaves you with either define creating cycles, or introducing letrec to create cycles, or the dubious beauty of the Y combinator. The acyclic heap is a great property for most data but it's annoying for representing programs. It might be reasonable to restrict letrec to creating functions, and ensure they're all statically allocated, which would give an acyclic data heap with direct representation of functions.
- skissane 4y ago
  I still think cycles should be allowed via symbols – just not directly. Allowing cycles via symbols tends to be less of a problem: (1) you don't want to garbage collect bound symbols, and once the symbol is unbound the cycle is broken (it would remove the ability to treat environments as first class objects, but maybe the other advantages are worth that cost); (2) printing values generally just prints the symbol name not its binding; (3) very often when you recurse through a data structure, you don't recurse into the binding of symbols contained in it, so that entails a significant reduction in the potential for infinite recursion bugs. It does mean you can't have an anonymous function which recurses, but that's a relatively rare use case. And actually, if you introduce some kind of special syntax which refers to "this lambda", you can even permit direct recursion of anonymous functions. Mutually recursive anonymous functions would be harder to support–maybe not impossible to support, but such an obscure use case it probably isn't worth thinking about.
kazinator 4y ago
The referential integrity dreamcompiler refers to isn't just for cycles in the structure, but for substructure sharing. Substructure sharing still occurs in a DAG, unless you rule it out also (e.g. with some strict one reference ownership model or whatever). In the absence of cycles, it is still useful to have a notation which says "these two objects in the DAG are actually the same node". If you implement that, the detection of cycles is almost free, because the assumption that a duplicate node appearing in the print is not a descendant of the previous one doesn't simplify the printing or reading algorithms very much. In order to print this #1=(... #1#) you have to determine that the given object occurs inside itself. In order to print (#1=(whatever) #1#), you have to determine that the given object occurs later in a sibling expression. Knowing that #1# will not occur inside (whatever) doesn't help all that much with anything; it doesn't help you decide whether or not the #1= prefix needs to be printed. If anything if the restrictions were reversed, it would be simpler: if the only substructure sharing that were allowed was backward references, that helps. Because then we know that the (whatever) object can only occur again inside (whatever), and not after it. To detect nothing but cycles, without caring about other sharing, we just have to maintain an object path across the recursion so that for every visited object we can ask "is this object already in the path from root to here?" If so we have a backreference. The sibling case is harder. You can have situations like: ((((#1=(foo)))) (((#1#)))) Deep inside the left item in the list there is an object which occurs again deep in the right item. We need to put the objects we are visiting into a hash, which is pretty expensive. > Just by making sure your primitives for constructing values don't permit cycles to be constructed. But lambda calculus teaches us that if all we have is functions being passed to functions and binding arguments we can build a circular reference. See the middle word of the domain in the browser address bar. So you have to further dumb things down from there if you want to absolutely eliminate cycles in the object graph. (You can have it so that you don't care about function-induced cycles (only the garbage collector does) by not having any printed notation or other API that traverses the internals of a function. The application can still build a graph using functions, but is "on its own" as far as providing its own functions for operating on it, and serializing it and whatnot.)