Show intermediate values

[rolyp]

We are able to visualize intermediate values that arise from transient selections in the convolution example, albeit with problems related to layout and interaction. These problems represent the next selection of tasks to be picked off.

In the convolution example, we want to be able to see the intermediate matrix used to compute a given cell of the output. To support this kind of use case, we need (the beginnings of) a notebook-like presentation of the program as a graph of cells. (This graph is in some sense an abstraction of the DDG.)

See also

• Orthogonal transient and persistent selections #913
• Remove trace-based slicing implementation #1214
• Forward slicing doesn't pick out intermediate matrices #1288
• Interact with intermediate values #1290
• Remove hardcoded intermediate queries #1291

[rolyp]

Some whiteboard notes from today, lots of our current todo's are somewhat related to this issue:

[rolyp]

I’m inclined to say this is an orthogonal requirement after all – linked inputs and linked outputs scenarios can easily exist within a “single” program (for linked outputs we just need some way of composing visualisations).

[rolyp]

Prezi‘s “nested presentations” could be a useful source of ideas.

[rolyp]

Renamed from “Cellular Fluid” and incorporated @JosephBond‘s description.

[rolyp]

I think convolution would work as a nice example here too: we could use different boundary methods (zero-padding vs. wrapping, etc) to demonstrate multiverses (#1183) and the intermediate arrays (one per output element) which have the same dimensions as the filter as the intermediate values of interest.

[JosephBond]

Expanding on @rolyp's most recent suggestion: the thing we use to perform early-stopping on a call to evalBwd instead analyses the structure of the Trace at the point of interest. If the Trace is the right structure, the early-stopper (not sure what to call it now) also returns the appropriate value in the computation of interest. For the 3 by 3 matrix, we will be looking for a pair of nested applications, ie something like (quot interMatrix) area

extract3by3 :: forall a. Ann a => Trace -> Val a -> Maybe (Val a)
extract3by3 (T.App t1@(T.App t1' t2' t3') t2 t3) v =
    case t1' × t2' of
        (T.AppForeign (ForeignTrace (opName × _)))  × (T.Matrix _elems (_ × _) (i × j) _) -> 
            if i == 3 && j ==  3 && opName == "quot" 
            then Just v
            else Nothing
        _ -> Nothing
extract3by3 _ _ = Nothing

This kind of structure is laborious to work out by hand, especially with the nested pattern matching. I wonder if its possible to automatically derive the Trace structure we are looking for by supplying the original expression, parsing it, and then - in evaluation - capturing the chunk of the trace we are looking for when going forward, since we have to perform forward evaluation anyway.

Edit: actually the structure is even more complex to manually derive, since the computation we are actually interested in inspecting is:

matrixSum interMatrix `quot` area

By recursing further up through the Trace to find that the first argument to quot came from evaluating matrixSum interMatrix we could do this. This is what spurred the idea of using the parser to derive the Trace fragment we are looking for, which then leaves us with the task of returning the appropriate value - in this case interMatrix.

[JosephBond]

The idea of extracting the fragment of the trace that specifies the creation of the intermediate value would rely on supplying extra information to loadFig. If we're going that route, why not supply that information in the evaluation of the program, perhaps as decoration attached to expression nodes, we could then record the collection of vertices related to a sub-computation during forwards evaluation with the graph, and include the mapping from that expression to it's vertices as part of the graph evaluation output. That way we can potentially avoid having to make use of the trace evaluation. I will think more on this.

[rolyp]

Problem formulation

Yesterday I proposed understanding the problem as “find the application matrixSum interMatrix `quot` area (or perhaps matrixSum interMatrix) where m’, n’ have “the supplied values”. I don’t think this really makes sense, because it’s not clear where we get the supplied values.

The specific intermediate value(s) of interest needs to be determined by the selection on the output, so that mousing over the output matrix reveals different intermediate values. We could implement some bespoke logic that queries the output matrix to determine the indices of selected cells, and then use a modified evalBwd (or eval) to identify the step in the computation where matrixSum interMatrix is called and m' and n' have those values, and return the value of interMatrix. But this mediation via explicit indices circumvents the slicing mechanism entirely and risks putting effort into something that doesn’t generalise at all. What if there are two output selections? What about persistent vs. transient selections? Perhaps a better starting point is to factor this problem through our existing slicing mechanism and deal with any problems that throws up.

Observations

• Walking the trace to pick out any “selected” intermediate values would slow things down again and defeat the purpose of having the graph. (This needs to be done interactively, not just as a one-off.)
• Current graph slicing interface doesn’t provide access to any reached intermediate values, but it could.
• Slicing back from an output cell (via graph or trace) won’t select the intermediate matrix, because matrix lookup discards the α on the matrix when returning the contents.
• Naively just adding an edge from the looked up contents to α might make more things “related” than we would want, but maybe that’s something we should explore and then try to fix in some other way. (For example by tagging this as a “why” [or “whence”] edge rather than a “how” edge.)

[JosephBond]

Naively adding a new edge for the lookup seems to fail, since the exact same lookup can be performed multiple times, naively including a call like extend α (singleton α') creates duplicate edges in which causes an error when the graph is converted from a collection of hyper-edges into an actual Graph. My understanding of a possible fix is:

• Add the ability to check if an edge exists in the MonadWithGraphAlloc type-class, to check if an edge exists already
• In the OpGraph for matrixLookup, perform this check, if the edge doesn't already exist, then run extend α (singleton α')

Alternatively:

• modify outMap (used in fromEdgeList) to accept multiple entries for the same node, unioning the sets of adjacent nodes

@rolyp do you have a preference for either of these? My gut reaction is that the second option makes more sense

[rolyp]

Yes weakening the addEdges constraint to allow for redundant edge information sounds reasonable. It could also be worth thinking about distinguishing different kinds of edge (in the List Hyperedge) so that “value” edges must be unique (since they explain how a value was created and a given value can only be created once), but “reference” edges need not (since we can do the same retrieval of an existing value multiple times).

For this initial experiment, let’s try just relaxing the constraint, but could you also add a “to do” to this task to revisit the idea of reinstating it (along the lines just sketched) if we do end up committing to this direction?

[JosephBond]

Relaxing the constraint breaks 8 tests, the convolution tests (inc linked-outputs/convolution) the array test, and compute-dtw for a mixture of reasons:

• array: doesn't satisfy graph fwd preserve top
• slicing/array/lookup: received an increased selection than expected (reasonably small one)
• slicing/convolution/edgeDetect,emboss,gaussian: G-Suffices but not T-suffices (selects every element in the matrix)
• slicing/dtw/compute-dtw: G-Suffices but not T-suffices
• slicing/dtw/average-series: almost the entire output selected with "doesn't satisfy graph fwd preserves top"
• linked-outputs/convolution: expected but not selected, with a fair amount of the matrix selected

[rolyp]

Let’s separate these into:

• invariant violations (things that appear to be reporting on something which is semantically incorrect)
• changes to slicing behaviour (which might be expected)

Could you also push your branch so I can take a look at the changes?

[JosephBond]

slicing/array/lookup, and linked-outputs/convolution both make sense to me as changes to slicing behaviour, do those other cases fall under the umbrella of invariant violations?

I've pushed now.

[JosephBond]

changing line 141 from
pure $ (erase r × (i × j)) × (Val (α ∧ α') v)
to just directly use the annotation on the matrix:
pure $ (erase r × (i × j)) × (Val α v)
Means 6/8 errors just become errors related to changes in the slicing behaviour, only array and slicing/dtw/average-series, which still get "doesn't satisfy graph fwd preservers top"

[JosephBond]

I've fixed the relaxation of the constraint on addEdges. On its own, this does not break any of the tests. so we can return our focus on the implementation of matrixLookup. The naive change where we extend the project value with a dependency on the matrix:

   op :: OpGraph
   op (Val α' (Matrix r) : Val _ (Constr c (Val _ (Int i) : Val _ (Int j) : Nil)) : Nil) | c == cPair = do
      let v@(Val α _) = matrixGet i j r
         extend α (singleton α')
      pure v
   op _ = throw "Matrix and pair of integers expected"

This change breaks the invariant that inputs are sinks on the convolution examples

[rolyp]

Ok, that makes some kind of sense. Let’s have a think about this.

[JosephBond]

Current iteration (with inputsAreSinks check disabled) has the following errors:

  ✖ "slicing/array/lookup"
  Error: bwd_expect:
  Expected
  let xs = [[1, 4, 8], [3, 2, 17], [0, ⸨14⸩, 6]];
      ys = [|nth2 i j xs|(i, j) in (3, 3)|] in
  ys ! ((3, 2))
  Received
  let xs = [[1, 4, 8], [3, 2, 17], [0, ⸨14⸩, 6]];
      ys = ⸨[|nth2 i j xs|(i, j) in (3, 3)|]⸩ in
  ys ! ((3, 2))

  ✖ "slicing/convolution/edgeDetect"
  Error: G-Suffices but not T-Suffices:
  0, ⸨-1⸩, ⸨2⸩, ⸨0⸩, ⸨-1⸩,
  ⸨0⸩, ⸨3⸩, ⸨-2⸩, ⸨3⸩, ⸨-2⸩,
  ⸨-1⸩, ⸨1⸩, ⸨-5⸩, ⸨0⸩, ⸨4⸩,
  ⸨1⸩, ⸨-1⸩, ⸨4⸩, ⸨0⸩, ⸨-4⸩,
  ⸨1⸩, ⸨0⸩, ⸨-3⸩, ⸨2⸩, ⸨0⸩

  ✖ "slicing/convolution/emboss"
  Error: G-Suffices but not T-Suffices:
  5, ⸨4⸩, ⸨2⸩, ⸨5⸩, ⸨2⸩,
  ⸨3⸩, ⸨1⸩, ⸨2⸩, ⸨-1⸩, ⸨-2⸩,
  ⸨3⸩, ⸨0⸩, ⸨1⸩, ⸨0⸩, ⸨-1⸩,
  ⸨2⸩, ⸨1⸩, ⸨-2⸩, ⸨0⸩, ⸨0⸩,
  ⸨1⸩, ⸨0⸩, ⸨-1⸩, ⸨-1⸩, ⸨-2⸩

  ✖ "slicing/convolution/gaussian"
  Error: G-Suffices but not T-Suffices:
  38, ⸨37⸩, ⸨28⸩, ⸨30⸩, ⸨38⸩,
  ⸨38⸩, ⸨36⸩, ⸨46⸩, ⸨31⸩, ⸨34⸩,
  ⸨37⸩, ⸨41⸩, ⸨54⸩, ⸨34⸩, ⸨20⸩,
  ⸨21⸩, ⸨35⸩, ⸨31⸩, ⸨31⸩, ⸨42⸩,
  ⸨13⸩, ⸨32⸩, ⸨35⸩, ⸨19⸩, ⸨26⸩

  ✖ linked-outputs/convolution
  Error: expected but not selected:
  (18, 15, 10, 10, 17,
    ⸨14⸩, ⸨9⸩, ⸨13⸩, ⸨9⸩, ⸨12⸩,
    12, 13, 19, 13, 5,
    10, 9, 6, 8, 17,
    6, 11, 15, 7, 8, ⸨18⸩, ⸨12⸩, ⸨13⸩, 9, 19,
                          ⸨20⸩, ⸨11⸩, ⸨24⸩, 9, 14,
                          ⸨15⸩, ⸨13⸩, ⸨20⸩, 11, 14,
                          7, 15, 15, 8, 20,
                          3, 10, 12, 3, 11)

These results were from a run where the implementation of matrixLookup had a mismatch in the semantics of the graph version and Fwd:

   op :: OpGraph
   op (Val α' (Matrix r) : Val _ (Constr c (Val _ (Int i) : Val _ (Int j) : Nil)) : Nil) | c == cPair = do
      let v@(Val α _) = matrixGet i j r
      extend α (singleton α')
      pure v
   op _ = throw "Matrix and pair of integers expected"

   fwd :: OpFwd (Raw MatrixRep × (Int × Int))
   fwd (Val α (Matrix r) : Val _ (Constr c (Val _ (Int i) : Val _ (Int j) : Nil)) : Nil) | c == cPair =
      let
         (Val α' v) = matrixGet i j r
      in
         pure $ (erase r × (i × j)) × (Val (α ∧ α') v)
   fwd _ = throw "Matrix and pair of integers expected"

The issue is that in the graph I added an edge between α' and α, but in the trace version I took (α ∧ α'). Changing the result of fwd to just copy the annotation on the matrix changes the errors to the following:

  ✖ "slicing/array/lookup"
  Error: bwd_expect:
  Expected
  let xs = [[1, 4, 8], [3, 2, 17], [0, ⸨14⸩, 6]];
      ys = [|nth2 i j xs|(i, j) in (3, 3)|] in
  ys ! ((3, 2))
  Received
  let xs = [[1, 4, 8], [3, 2, 17], [0, ⸨14⸩, 6]];
      ys = ⸨[|nth2 i j xs|(i, j) in (3, 3)|]⸩ in
  ys ! ((3, 2))

  ✖ "slicing/convolution/edgeDetect, emboss, gaussian" (all the same shape of error)
  Error: fwd_expect:
  Expected
  ⸨0⸩, -1, 2, 0, -1,
  0, 3, -2, 3, -2,
  -1, 1, -5, 0, 4,
  1, -1, 4, 0, -4,
  1, 0, -3, 2, 0
  Received
  ⸨0⸩, ⸨-1⸩, ⸨2⸩, ⸨0⸩, ⸨-1⸩,
  ⸨0⸩, ⸨3⸩, ⸨-2⸩, ⸨3⸩, ⸨-2⸩,
  ⸨-1⸩, ⸨1⸩, ⸨-5⸩, ⸨0⸩, ⸨4⸩,
  ⸨1⸩, ⸨-1⸩, ⸨4⸩, ⸨0⸩, ⸨-4⸩,
  ⸨1⸩, ⸨0⸩, ⸨-3⸩, ⸨2⸩, ⸨0⸩

  ✖ "slicing/dtw/compute-dtw"
  Error: fwd_expect:
  Expected
  ((1, 1) : (⸨(⸨2⸩, ⸨2⸩)⸩ : ((2, 3) : ((3, 4) : ((4, 5) : ((5, 6) : ((5, 7) : [])))))))
  Received
  (⸨(⸨1⸩, ⸨1⸩)⸩ : (⸨(⸨2⸩, ⸨2⸩)⸩ : (⸨(⸨2⸩, ⸨3⸩)⸩ : (⸨(⸨3⸩, ⸨4⸩)⸩ : (⸨(⸨4⸩, ⸨5⸩)⸩ : ((5, 6) : ((5, 7) : [])))))))

  ✖ linked-outputs/convolution
  Error: expected but not selected:
  (18, 15, 10, 10, 17,
    ⸨14⸩, ⸨9⸩, ⸨13⸩, ⸨9⸩, ⸨12⸩,
    12, 13, 19, 13, 5,
    10, 9, 6, 8, 17,
    6, 11, 15, 7, 8, ⸨18⸩, ⸨12⸩, ⸨13⸩, 9, 19,
                          ⸨20⸩, ⸨11⸩, ⸨24⸩, 9, 14,
                          ⸨15⸩, ⸨13⸩, ⸨20⸩, 11, 14,
                          7, 15, 15, 8, 20,
                          3, 10, 12, 3, 11)

[rolyp]

Tracking “intermediates”-related tasks as part of fluid 0.7.next rather than transparent-text going forward.