Pickling Tasty Data

Serialization, deserialization

Serializing in its basic form – for pure data – means writing it out to a string such that it can be recovered from that string. (Bitstring, bytestring, Unicode string, even a bignum – the exact details do not matter. It also does not matter if it is a well packed encoding or a sparse encoding with lots of invalid strings that do not deserialize.)

Pickling is more general: it means serializing non-pure data by taking a snapshot of mutable data, preserving referential identity in the process (this is hard!), and doing your best with external references, and maybe giving up on functions.

Part of my argument is that serializing and pickling is very tied up in what data means!

Like, What is the essence of data? I hope it is something you can grasp fully, explain fully, and write out to a file and fully reconstruct in a new runtime context. (Mumble mumble: decidable equality, computation, countability.)

Equivalent vs equal

I think I have definitions of equal and equivalent that are useful.

Equality in the classical senseLeibniz equality, “Identity of indiscernibles” is going to be too strict, I argue, for the notion of data I want to consider. First of all, it is hard to compare values across runtimes, which is silly! Data does not only exist for an instant in time! And two mutable objects can be interchangeable even if they are not identical references.

This discrepancy happens as soon as you have mutable references, which you could tell apart if you have both to compare, but otherwise would act similar.

// Set up some data
let shared = [];
let v0 = { 0: shared, 1: [], 2: 2 };
v0[3] = v0;
let v1 = { 0: shared, 1: [], 2: 2 };
v1[3] = v1;
shared.push(v0, v1);

// I hope you agree that this characterizes
// the state of the data, most or less
for (let v of [v0, v1]) {
  // shared reference
  assert(v[0] === shared);
  // equivalent empty arrays,
  // though not equal
  assert(v[1].length === 0);
  // index 2 is 2
  assert(v[2] === 2);
  // self reference
  assert(v[3] === v);
}
// and they are referenced by shared in order
assert(shared[0] === v0);
assert(shared[1] === v1);

// they are not equal:
assert(v0 !== v1);

// but we can swap them, ...
[v0, v1] = [v1, v0];
// ... all references to them, ...
[v0[3], v1[3]] = [v1[3], v0[3]]; // yes, self references count
[shared[0], shared[1]] = [shared[1], shared[0]];
// ... and the immediate references they hold,
// since they have the same shallow structure
[v0[0], v1[0]] = [v1[0], v0[0]];
[v0[1], v1[1]] = [v1[1], v0[1]];
[v0[2], v1[2]] = [v1[2], v0[2]];
[v0[3], v1[3]] = [v1[3], v0[3]];
// this last one fixes up their self references again!

// Now we have the same observable state of the world!
for (let v of [v0, v1]) {
  // shared reference
  assert(v[0] === shared);
  // equivalent empty arrays,
  // though not equal
  assert(v[1].length === 0);
  // index 2 is 2
  assert(v[2] === 2);
  // self reference
  assert(v[3] === v);
}
// and they are still referenced by shared, in the
// order corresponding to the same variable names
assert(shared[0] === v0);
assert(shared[1] === v1);

// so we conclude that `v0` and `v1` are equivalent!

In Dhall, equal and equivalent happen to be the same!Citation needed. Unfortunately this is more a reflection of the rather stagnant notion of data in Dhall – no mutability, no references, no cyclic structures.

As soon as you have mutable references, equality and equivalence will not be the same.

(This is because you can always use test mutations to tell when two references are identical or not, so you cannot just outlaw referential equality and hope that they become indiscernable.)

And practically speaking, there are always wrinkles.

Strings

As a warm-up to thinking about references and pointers: Letʼs observe that immutable strings are treated specially by a lot of runtimes!

V8 has a lot of different representations of strings, and it is free to change representation between them, e.g. while garbage collecting. It is free to make these changes since they arenʼt observable from JavaScript (outside of performance characteristics).

Erlang likewise has immutable binaries (bytestrings) which serve similar purposes although they only support fast slicing (no fast concatenation). To get fast concatenation, users are expected to build up nested lists and flatten it out into one binary at the end of all the concatenation operations. (Luckily it is rare to want to index back into a binary as your are building it up, so this is acceptable for most use-cases.)

The thing that the Erlang garbage collector is specifically allowed to do is to delete old binaries whose contents are only partially referenced. Then it has the task of fixing up the references to those slices to refer to the new binaries with adjusted indices. This is definitely mutating data at some level (e.g. the level of raw memory), but it is not visible from Erlang at all.

Anyways, this is just a nicer example of stuff the runtime can do behind the scenes that has a very precise semantic description. It happens “behind the scenes” because changes occur in memory that do not effect equality, as seen from the language. As we start to think about references and managed pointers and external references and functions, it gets more complicated!

It is also a good warning to be careful about what “immutable” means: since every runtime uses mutation at some level, we only care about immutability as viewed from the language itself.

Mutability or purity

Mutability should be one of the first things you think of when you think about data, especially if you have had some exposure to ideas from Functional Programming (FP).

The really nice thing about pure languages like Haskell and PureScript is that they separate out mutable references from pure data, and dispense with mutable variables altogether. It affords us a much nicer toolbox for expressing these concepts, in theory and in code.

Functions

Functions are tough. When viewed from above (mathematically) and below (most runtime implementations), they cannot be sensibly serialized.

One thing that is always trueEven in non-Turing-complete languages! is that you cannot expect to know when two functions are equivalent. They may happen to be equivalent in a obvious way, but if they arenʼt, you cannot necessarily find out that they actually have distinct behavior. (In other words: equivalence is semidecidable [reference needed].)

If you have the original syntax defining the functions, you do have a snowballʼs chance in hell of deciding that two functions are equivalent, by doing some procedures to normalize the syntactic definitions of the functions. (One difficulty is that you will also have to keep track of closures, including captured variables and open variables.)

But once the syntax is forgotten (viz. at runtime), the best you can do is a pointer comparison, which is a very poor decider of equivalence.

The funny thing is that, although all functions start out as syntax, syntactic normalization is very rare for languages.

Only a few term-based languages like Dhall will always keep functions as syntaxThis is slightly unfair, considering that Dhall now uses NbE, but it amounts to the same thing., and only theorem provers like Agda/Lean/Rocq will keep the function syntax around for their core operation (whereas code extraction and runtime is almost entirely a separate issue).

(Aside: In theory you could defunctionalize a whole closed-system program right? At least for pure data? Maybe for mutable too?)

However, in languages like Agda, each function definition is considered distinct, so it might as well be a pointer check. (This is true for almost all theorem prover languages, certainly for recursively-defined functions – Dhall just avoids the issue by not having recursive functions!)

Fantasy

Languages that nobody actually runs. Theyʼre just too academic or something. (Joking.)

Real World

Okay maybe some people actually run these languages and interact with their runtimes.

// this is the “weird” JS `const`
// where the variable reference is
// constant, but the data is mutable!
const selfRef = [];
selfRef.push(selfRef);
console.log(selfRef[0] === selfRef);

console.log(JSON.stringify(selfRef));
// Uncaught TypeError: cyclic object value

const twin = {name: "Lo"};
const twins = [twin, twin];
const gemini = JSON.parse(JSON.stringify(twins));
twins[1].name = "Hi";
gemini[1].name = "Hi";
console.log(JSON.stringify(twins)); // [{name: "Hi"}, {name: "Hi"}]
console.log(JSON.stringify(gemini)); // [{name: "Lo"}, {name: "Hi"}]

Others

Pickling Nasal runtime values

Pickling consists of writing out a file that, when executed, returns an equivalent object. (The body of a file is simply a function. Plus all statements are expressions – they have a return value, although sometimes it is a pretty useless return value.)

• You initialize a hashmap of object ids that have been seen.
• For each object you see, you look at the hashmap:
  • If not, you add the reference to the hashmap, and add a variable to the file to save the reference in case you need it later.
  • If it exists, you insert code to reference the existing variable and stop walking the structure.
• For non-recursive data, you just set it directly.
• For recursive data (objects and arrays), to handle cyclic references you may need to initialize it to an empty value and add items via mutation. Thus when those items mention their (grand)parent, that reference already exists in a variable, and the rest of the structure will continue to be built as necessary.

In lieu of a hashmap, you could even use a list of objects, and traverse it in linear time to compare referential identity. This is possible in most dynamic languages, just really slow.

Functions, builtins, bootstrapping

I also tried to work on a bootstrapping system for Nasal. I never completed it.

Anyways, this is relevant because I did add bytecode decompilation for functions. You could already inspect bound scopes of closures, and callers and local scopes of the call stack. All that was left was builtins (which donʼt have bytecode).

If you have a contract with the bootstrapping system, you could look up the globally accessible names for the builtin functions that you could not decompile, and hopefully assume that equivalent builtin functions would live in those same spots on the next bootstrapping too.

The problem, still, is builtin external references, like files and such. Some could be supported on a case-by-case basis, but not everything.

Also, ideally you would airgapSorry, wrong word. the builtins, since some builtins are fake builtins. That is, they are wrappers over actual builtin functions, but you could only access those builtins through the closure of the wrapped function – so you might as well stop bytecode decompilation for the wrapped functions (by wrapping the decompiler!) and treat them as builtins.

Anyways, in theory you would almost be able to save the entire state of a running Nasal system and fully reconstitute it under an equivalent bootstrapped environment. At the very least, you would expect to be able to save complicated data with simple functions.

Equivalence

The pickling process points towards a method of determining equivalence. Obviously you should sort the file in some semantic way, and rename variables to less arbitrary things. Maybe normalize the bytecode for functions.

After that, you should just be able to compare your resulting files and use that as a notion of equivalence!

Alternatively, you could write out a direct algorithm: take two objects at runtime and walk them recursively with the same kind of hashmap trick, comparing at which paths you see the objects, and then just make sure the shared references appear at the same minimal-paths from the root across their sharings. (You want to avoid cyclic recursions, of course, which does mean you will only look at minimal paths.)

Iʼll call this … “graph equality”? “Stable equality”? It is what Iʼve meant by “equivalence” all along.

Ghost objects (foreigns), property tree

Nasal has a concept of “ghost” objects which are pointers to foreign objects, literally just C pointers with some associated data to help the garbage collector.

These are constructed by C APIs, and the only way to reconstruct them would be if you can call those APIs again to produce equivalent objects – which may not always be possible.

One of the main foreign interfaces of Nasal is FlightGearʼs property tree – a central store of important simulator values that is accessible from all of FlightGearʼs subsystems, not just Nasal. References to these nodes can be stored (making use of ghost objects) and manipulated through an API, in a way that is somewhat like accessing the DOM in JavaScript.

This is one type of ghost reference that could easily be handled by a pickling script: since the path of the node is available, you just have to serialize that, and then obtain the node again when deserializing. However, there still is some rough edges: what if the node doesnʼt exist when it is getting loaded again? It could be possibly recreated, but now the deserialization has side-effects, which is weird. Or a separate property tree could be created to sandbox the script, and relevant nodes created there.

Property trees can also be saved to XML and loaded from there, although there are various details that donʼt translate well regardless of serialization format. One example is properties that are managed by C++ code, instead of having their data be managed by the property tree – but those properties typically exist by the time Nasal is initialized.

So thereʼs always some details that need to be figured out or approximated when dealing with external APIs and data that is not managed in the language itself.

Strings

Nasal strings were actually a fun challenge. It has mutable strings!

It has immutable interned strings, which are cached in a global lookup table. This is used for identifiers (including object keys), to speed up comparisons.

It also has mutable strings (and I believe they can be mutated to be immutable? it is a little weird).

The referential identity of strings is not exposed – the equality operator ignores it. However, you can still determine whether two mutable strings are the same reference, by using test mutation: if you mutate one and the other stays the same, they are different references.

(You can even use missed fast comparisons to determine if a string is interned or not.)

Graph equality of mutable data

The only problem is that it is pretty expensive, it requires a lot of bookkeeping, and most people generally donʼt care – they are fine either writing the equality comparison they need, or settling for the standard deep equality.

However, it is very useful!

Like, as one example, this is literally what stable names are used for.

Constructors

As part of these musings on data, I subscribe to the idea that the only objects that should have constructors (at the level of data – obviously client code will want different abstractions) are objects that are constructed from external references, FFI.

Idk, constructors in the sense of mainstream OOP are mostly a distraction for this view of data I want to talk about. They just arenʼt good, arenʼt necessary, they get in the way – especially since the arguments to the constructors donʼt have to correspond to the runtime data of the object at all.

Uses of references

You really should not be able to ask for two references to be ordered against each other: it doesnʼt mean anything with regards to the meaning of the program (although it may record some historical data about how the program did happen to run). But you kind of should be able to put them into a map efficiently, and ordering/hashing is potentially important for that, but only if it can be stable.

Mark/sweep GC is good for stability of pointers (and thus comparisons). I think mark/compact still can preserve comparisons.

Weak references are interesting. Every time Iʼve wanted weak references, Iʼve always actually wanted to do them as reverse references: data stored on the key object, instead of in a map indexed by the key object. (Of course this may leak memory if the map you want to store is not long-term/global.)

Abstract model for GCable data

I think itʼs instructive to pin down a model of garbage collectable data in Haskell/PureScript, where we can talk about references separately from pure data structures.

This is enough to model the fragment of JavaScript values I said should be covered by the pickling function I sketched. (Well, you could easily add undefined.)

-- The managed heap for the runtime data.
-- I believe this is what rustaceans
-- call an arena?
newtype Heap s metadata shape = Heap
  (MVector s (RuntimeData shape, metadata))

data RuntimeData shape
  -- Runtime data is given by a pure shape
  -- (which needs to be `Traversable`!)
  -- which contains runtime references
  -- in a known way
  = RuntimeData (shape RuntimeRef)
  -- It can also be an external “ghost”
  -- reference that we have a function
  -- to destruct (or dereference, if
  -- it is shared data)
  | ExternalGhost Ptr (IO ())

-- A managed reference we control,
-- thus it is an opaque pointer
-- into the opaque memory heap
data RuntimeRef
  = ManagedOpaque Int
  deriving (Eq, Ord)
  -- ^ the user is allowed `Eq`
  --   but not `Ord`

-- An example shape for mutable data
-- in the spirit of JSON (the only
-- reason it is not JSON is that JSON
-- is immutable, being a serialization
-- format, strictly speaking)

-- A JSON value, either a plain value
-- or a reference to a mutable value
data JSONValue ref
  = Null
  | Number Scientific
  | String Text
  | ByRef ref
  deriving (Eq, Ord, Functor, Foldable, Traversable)

-- What data lies behind a mutable value?
data JSONShape ref
  = Array [JSONValue ref]
  | Object [(Text, JSONValue ref)]
  deriving (Eq, Ord, Functor, Foldable, Traversable)

-- If we take the immediate fixpoint,
-- without mutable references in the
-- loop, we get plain immutable JSON data,
-- except that it is lazy, so it is
-- potentially infinite
newtype JSON = JSON (JSONValue JSON)

data Idx
  = ArrayIdx Int
  | ObjectIdx Text

-- A machine for creating a graph in
-- the mutable JSON structure
data Machine ref
  = SetKey ref Text (JSONValue ref) (Machine ref)
  | Push ref (JSONValue ref) (Machine ref)
  | Get ref Idx (JSONValue ref -> Machine ref)
  | NewArray (ref -> Machine ref)
  | NewObject (ref -> Machine ref)
  | Return (JSONValue ref)

equal :: Eq ref =>
  JSONValue ref ->
  JSONValue ref ->
  Boolean
equal = (==)

-- Since Haskell is lazy,
-- JSON is a greatest fixpoint,
-- so, with some care, I believe
-- you could even reify recursive
-- data into the JSON type
-- (but `Eq` would not terminate)
snapshot ::
  (ref -> m (JSONShape ref)) ->
  JSONValue ref -> m JSON

deepEq ::
  (ref -> m (JSONShape ref)) ->
  JSONValue ref ->
  JSONValue ref ->
  m Boolean
deepEq read x y = do
  m <- snapshot read x
  n <- snapshot read y
  -- compare as JSON
  pure (m == n)

equivalent :: Ord ref =>
  (ref -> m (JSONShape ref)) ->
  JSONValue ref ->
  JSONValue ref ->
  m Boolean
equivalent read l0 r0 =
  runStateT (comparing [] (l0, r0)) empty
  where
  comparing ::
    [Idx] ->
    (JSONValue ref, JSONValue ref) ->
    StateT (Map ref [Idx], Map ref [Idx]) m Boolean
  comparing path (l, r) =
    -- Try to match up the values
    case zipMatch l r of
      -- They are both references
      Just (ByRef (ll, rr)) -> do
        -- First we check if we should short circuit
        -- if they have been seen before
        (seenL, seenR) <- get
        case (lookup ll seenL, lookup rr seenR) of
          -- Seen both
          (Just p1, Just p2) -> do
            -- We have to have seen them at the same path,
            -- since we are traversing in the same order
            pure (p1 == p2)
          -- Seen neither
          Nothing, Nothing -> do
            -- Keep track of where we saw this
            -- reference, separately for left and right
            -- (since it is valid for both to use the
            -- same reference for different purposes)
            modify
              (insert ll path *** insert rr path)
            -- Read the current values of the reference
            x <- lift (read ll)
            y <- lift (read rr)
            -- Try to match them up
            case zipMatch x y of
              -- Failed: different types
              Nothing -> pure False
              -- Similar arrays: recurse into children
              Just (Array xys) ->
                allM (uncurry comparing)
                  -- Add the index onto the path
                  (intoArray path <$> enumerate xys)
              -- Similar objects: recurse into children
              Just (Object xys) ->
                allM (uncurry comparing)
                  -- Add the key onto the path
                  (intoObject path <$> xys)
          -- Failed: seen one but not the other
          _, _ -> pure False
      -- Succeed if it is a pure value
      -- that is equal on both sides
      lr -> pure (isJust lr)

intoArray path = first $ \idx -> ArrayIdx idx : path
intoObject path = first $ \key -> ObjectIdx key : path

Hopefully you can see from the implementation of the equivalent function how two distinct references can still be interchangeable for all intents and purposes. We could write out this interchange formally, since all the references are visible on the heap, and then state some theorems about some functions.

However, for other processing, we donʼt even really need this arena/managed heap. We can use the Haskell runtime itself!

I havenʼt worked out the details (stable names?), but we should be able to reify the graph of a cyclic JSON value too.