Re-Tracable graphs

[phipsgabler]

Make graphs reusable or updateable: recording more than one trace over same IR, or update parts for new runs?

graph = track(f, 1, 2)
retrace!(graph, f, 1, 2)  # allow different inputs?
retrace!(graph)           # or only record changes due to stochastic control flow?

What should happen, then? Maybe simply replace nodes that change by a SplitNode, containing the alternatives (function calls with different results, branches with differnt conditions)?

In principle, this could be the basic for something like concolic execution.

[phipsgabler]

Might also be combined with #39. Possible steps:

1) Introduce some form of abstraction, that makes the graph independent of the actual values (either by making them optional in TapeExpr, or by providing an additional, almost duplicate structure). 2) Add an additional ForkNode to express multiple possible execution paths from a point. 3) (Maybe?) Provide some kind of tree zipper to efficiently change focus within the structure.

[yebai]

I wonder whether it is possible to introduce a pair of marker functions to indicate checkpoints for retracing. These marker functions have similar functionality to consume and produce in the Libtask library, and should allow the user to selectively re-create a fresh trace from a certain marker point (equivalent to continuation or forking), while re-using the parts of a trace before the branching point. This allows us to implement the resampling step of particle samplers efficiently. For a concrete example, see https://github.com/TuringLang/Libtask.jl#getting-started

[phipsgabler]

You mean for marking in the source code that is to be traced? Something like the following?

> f(x) = (print("x"); x) + fork(rand())

> trace = track(ForkCtx(), f, 1)
"x"
f(1) = 1.456456
  @1: f
  @2: 1
  @3: print("x") = nothing
  [Fork]
    [Run 1]
      @4: rand() = 0.456456
      @5: @2 + @4 = 1.456456
      return @5 = 1.456456

> track(ForkCtx(trace), f, 1)   # no execution of print here!
f(1) = 1.234234
  @1: f
  @2: 1
  @3: print("x") = nothing
  [Fork]
    [Run 1]
      @4: rand() = 0.456456
      @5: @2 + @4 = 1.456456
      return @5 = 1.456456
    [Run 2]
      @4: rand() = 0.234234
      @5: @2 + @4 = 1.234234
      return @5 = 1.234234

[yebai]

Looks correct, but it needs to be more general if I understand your example currently, e.g. it should allow operations after the fork call, instead of wrapping everything inside the fork call. For example:

f(x) = (print("x"); x) + (fork(); rand() + rand())

All the rand calls after fork need to be re-traced to get a correct implementation.

Besides, we need to consider duplicating variables that are shared by forked traces, but that's relatively easy once we can fork traces.

[phipsgabler]

Looks correct, but it needs to be more general if I understand your example currently, e.g. it should allow operations after the fork call, instead of wrapping everything inside the fork call.

Of course. I always tend to forget cases that are not purely functional!

Besides, we need to consider duplicating variables that are shared by forked traces, but that's relatively easy once we can fork traces.

Right. I have a feeling that all of this will essentially end up to become very similar CPS transformation. (In fact, I was already doodling around to explore how to formulate IR blocks as continuations. There might be some deeper connection here. I definitely need to read up on them.)