Causal graphs and tracing

A state-oriented system is all about the value of its states and the ways in which that state can change (in reaction to other that) and can drive changes in other states (that react to it). In such systems, it is natural to consider what “causes” a state to change. The setting to answer such questions is the “causal graph” of a program. A causal graph is a directed (potentially cyclic) graph who's

• vertices are of the form (O, M) where O is an object and M is a message
• edges are of the form ((O', M'), (O, M)) such that O' in the processing of M' sends M to O.

In this setting, how can we attempt to answer what causes a state to change? Static analysis can reveal "causal paths" terminating at (O, M), where O is the object representing the state and M is the message which the object processes to modify its state. It cannot, however, reveal whether such a path will actually be taken during the execution of the program. On the other hand, runtime analysis can reveal what causal paths are actually taken during the execution of the program, but cannot necessarily prove exhaustively all possible causal paths.

Runtime causal analysis, typically called "tracing", is already ubiquitous in software. At the most basic level, traces are emitted by the program during execution. These could be logs printed to the console or file, for example. These traces are reconstructed, typically by a separate program, into what is effectively a causal graph. Various enhancements can be made to cover corner cases. You could emit “spans”, basically when you enter and exit a context, to understand when nested calls return to their callers. You could also trace across asynchronous/process/machine boundaries by sending a trace ID along with the request to couple independently-collected traces. In terms of performance, tracing can be made quite performant. The most obvious option is to toggle tracing collection during runtime. But many systems are performant enough to be always-on. They often write traces in a binary format, or write to a database.

Accumulating a causal context as messages pass between objects in an OOP system is another possibility. We take inspiration from networking, where we conceptually think of a packet traveling through the network topology. There is even a notion of a trace packet, where network devices will essentially record that they processed the packet before forwarding it. The result is a packet that contains within it the information of how it traversed the network topology. We’d like to compare messages to packets. Semantically, we propose sending an accumulating "trace record" along with messages in the trace path.

Concretely, imagine a TraceRecord data structure, storing a stack of TraceStamp's, each of which records information like the object ID, message received, and timestamp. Imagine a Message data structure which contains the message and recipient object ID. When an object receives a message, it takes the TraceRecord of that message and pushes a TraceStamp onto it (recording its ID, the message it received, and when it received it). If (during the processing of the message) it needs to send a message to another object, it does so, bundling a copy of the TraceRecord with it.

A powerful possibility is for messages, and by extension TraceRecord's, to be runtime objects accessible to the program. For example, we can keep record of past values of a state and the sequence of events that led to that value being set. (This is similar in spirit to “data provenance” tables in databases, which record who changed a given entry for example.) Another example is having an object’s response to a message depend on who sent it, at any level of the causal chain. It's worth noting the parallels with continuations, which are the analagous concept for execution context. In particular, continuations reify the current execution context (stack, registers, etc.) while TraceRecord's reify the current causal context.

As a practical matter, we need to avoid TraceRecord's accumulating endlessly. We could define “terminal” behavior: do not propogate TraceRecord's when sending messages. Or “transparent” behavior: do not insert a (your own) TraceStamp when propogating TraceRecord's. These could be object-, procedure-, or even block-level annotation. We should also place a hard limit on the length of the TraceRecord. If the limit is hit, we can silently wrap, warn, or crash (like a stack overflow).

Language-level support for traced messages is ultimately essential to providing the facility broadly without tanking performance. If the compiler can prove a TraceRecord is never accessed from when it is started to when it is terminated, then it does not actually need to carry the TraceRecord with messages along that path (it can optimize it out). In a JIT setting, if we optimize as such then we can deoptimize of changes come in that do access the TraceRecord along the path. Furthermore, most execution environments run code in an environment where execution is synchronous / sequential, e.g. a thread. In such environments, only a single causal chain would be accumulating at a time. This suggests trace records can be stored in a single global, thread-local variable. When a new causal chain starts, we don’t need to free or reallocate anything, just start writing over the old traces. And if the compiler can deduce the maximal causal chain length, for instance, it can preallocate enough space from the start, and potentially put it on the stack.

The following is a basic example in Objective-C. As mentioned above, a bespoke language would be able to remove most of the boilerplate, allow more customizability, and further optimizations.

#import <stdio.h>

#import <Foundation/Foundation.h>

typedef struct {
  id obj;
  Class class;
  SEL sel;
} TraceStamp;

typedef struct {
  TraceStamp * stamps;
  int num_elts;
  int capacity;
} TraceBuffer;

static _Thread_local TraceBuffer trace_buffer;

void
trace_buffer_init( void ) {
  const int initial_buffer_capacity = 64;
  trace_buffer.stamps = malloc( initial_buffer_capacity * sizeof( TraceStamp ) );
  assert( trace_buffer.stamps != NULL );
  trace_buffer.num_elts = 0;
  trace_buffer.capacity = initial_buffer_capacity;
}

void
trace_buffer_reset( void ) {
  trace_buffer.num_elts = 0;
}

void
trace_buffer_debugprint( void ) {
  printf( "TraceBuffer( size=%d, capacity=%d, stamps=[ ",
          trace_buffer.num_elts,
          trace_buffer.capacity );
  for( int i=0; i < trace_buffer.num_elts; ++i ) {
    const TraceStamp * stamp = &trace_buffer.stamps[ i ];
    printf( "(obj=%p, class=%s, sel=%s), ",
            ( void * )stamp->obj,
            [NSStringFromClass( stamp->class ) UTF8String],
            [NSStringFromSelector( stamp->sel ) UTF8String] );
  }
  printf( "] )" );
}

@interface NSObject (Tracing)
- (void)trace_stamp:(SEL)sel;
@end

@implementation NSObject (Tracing)
- (void)trace_stamp:(SEL)sel {
  if( trace_buffer.num_elts >= trace_buffer.capacity ) {
    trace_buffer.stamps = realloc( trace_buffer.stamps, trace_buffer.capacity * 2 );
    assert( trace_buffer.stamps != NULL );
    trace_buffer.capacity *= 2;
  }
  TraceStamp * stamp = &trace_buffer.stamps[ trace_buffer.num_elts ];
  stamp->obj = self;
  stamp->class = [self class];
  stamp->sel = sel;
  trace_buffer.num_elts += 1;
}
@end

#define TRACE_STAMP() [self trace_stamp:_cmd]

@interface ObjC : NSObject
- (void)baz;
@end

@interface ObjB : NSObject
@property (strong, nonatomic, readwrite) ObjC * objc;
- (void)bar;
@end

@interface ObjA : NSObject
@property (strong, nonatomic, readwrite) ObjB * objb;
- (void)foo;
@end

@implementation ObjA : NSObject
- (void)foo {
  TRACE_STAMP();
  [[self objb] bar];
}
@end

@implementation ObjB : NSObject
- (void)bar {
  TRACE_STAMP();
  [[self objc] baz];
}
@end

@implementation ObjC : NSObject
- (void)baz {
  printf("Hello, world!\n");
}
@end

int
main( void ) {
  trace_buffer_init();

  ObjC * objc = [ObjC new];
  ObjB * objb = [ObjB new];
  [objb setObjc:objc];
  ObjA * obja = [ObjA new];
  [obja setObjb:objb];

  trace_buffer_reset();
  [obja foo];
  trace_buffer_debugprint();
  printf( "\n" );

  trace_buffer_reset();
  [objb bar];
  trace_buffer_debugprint();
  printf( "\n" );

  return 0;
}

Output:

make && ./main
clang -lobjc -framework Foundation -Wall -Wextra -Wpedantic -Werror main.m -o main
Hello, world!
TraceBuffer( size=2, capacity=64, stamps=[ (obj=0x102865a70, class=ObjA, sel=foo), (obj=0x10285cd50, class=ObjB, sel=bar), ] )
Hello, world!
TraceBuffer( size=1, capacity=64, stamps=[ (obj=0x10285cd50, class=ObjB, sel=bar), ] )