Diffing Program Semantics: Building a Runtime Trace Alignment Tool in Haskell

Introduction

In standard development, observing runtime state requires injecting print() or eprintln! calls. These are side effects. In Haskell, doing this forces pure domain logic into the IO monad, destroying equational reasoning and pure testability. trace-align solves this by separating observation from execution.

A Template Haskell splice – $(makeTraced 'myLoopFunction) – reads the AST of an existing function at compile time and synthesises a new version that runs inside a TraceM monad. TraceM is a plain Writer [TraceEvent] monad: no IO, no JSON, nothing touches stderr. The observation is a pure value, a list of events, passed directly to alignTraces in memory.

Execution Diffs as a Refactoring Tool

Unit tests check the final output. If the output is correct, CI passes. But what if a refactor introduces an unnecessary allocation in the middle of a loop, or evaluates a predicate in the wrong order but gets lucky on test inputs? Tracing execution diffs solves this. Run the old code, emit its intermediate states; run the new code, emit its intermediate states; align the timelines and diff them.

The pipeline is:

Program ⟶ Runtime execution ⟶ TraceEvent ⟶ State similarity ⟶ Alignment ⟶ Semantic diff

Each trace event records a snapshot of execution state. Mathematically, each state is a mapping \(\sigma : \text{Variable} \to \text{Value}\) and an execution is

trace-align compares these operational histories, not the final outputs.

Representing Runtime State

data Val
  = VNum Double
  | VStr Text
  | VList [Val]
  | VNull

type State = Map Text Val

data TraceEvent = TraceEvent
  { teLabel :: Text
  , teState :: State
  }

This is not merely a JSON representation – it is the semantic universe used by the alignment algorithm.

Formalising Equivalence with Typeclasses

Rather than hardcoding a scoreState function inside the algorithm, we introduce an Alignable typeclass, decoupling the policy of matching from the computation of similarity.

newtype Similarity = Similarity { getSimilarity :: Int }
  deriving (Eq, Ord, Show)

data MatchPolicy
  = Exact
  | Threshold Similarity
  deriving (Eq, Show)

class Alignable a where
  similarity    :: a -> a -> Similarity
  maxSimilarity :: a -> Similarity

matches :: Alignable a => MatchPolicy -> a -> a -> Bool
matches Exact         x y = similarity x y == maxSimilarity x
matches (Threshold t) x y = similarity x y >= t

By making State an instance of Alignable, the alignment algorithm becomes completely generic – it simply asks “do these two things match according to the policy?” Adding alignment for ASTNode or FeatureVector requires only a new instance; the core engine is unchanged.

Exact requires a perfect score. Threshold tolerates minor variations (a slightly reordered list) while catching catastrophic logic divergences. The next step is using GHC Generics to auto-derive Alignable instances for arbitrary Haskell records, moving the alignment from a stringly-typed runtime comparison to a compile-time structural one.

Module Architecture

The tool is decoupled into independent modules, composable in Main.hs or importable as a library.

Alignment.hs defines the typeclass-driven alignment logic (Alignable, MatchPolicy). StateMaps.hs defines the semantic universe (Val, State) and its Alignable instance. Parser.hs ingests JSONL streams into [TraceEvent]. Algorithm.hs implements greedy alignment and skip handling using MatchPolicy.

Because the alignment logic is pure, an external Haskell application can import these modules directly, feed them in-memory [TraceEvent] lists, and react to divergences without any serialisation.

Practical Application: jobpipe & CI/CD

trace-align is the verification layer for jobpipe, a hybrid ML job-ranking pipeline with a custom Rust DSL parsing job predicates against an AST and a Python layer handling probabilistic ranking and sentence-transformer embeddings. The boundary between deterministic Rust feature extraction and probabilistic Python ML must be exact.

Case Study: Discovering Rust’s HashSet Semantics

While integrating trace-align into jobpipe, a divergence was detected during a routine refactor of the feature extraction logic. The trace_diff output revealed:

[FAIL] DIVERGE feature_extract vs feature_extract
   Old State: fromList [("concepts",VList [VStr "(yc",VStr "is",VStr "href..."]),
   New State: fromList [("concepts",VList [VStr "href...",VStr "(yc",VStr "is"]),

The ML pipeline uses a bag-of-words model, where word order does not matter. Unit tests passed because the final ML weights were identical. However, trace-align flagged a hard divergence in the intermediate concepts array: the words were identical, but the order was completely shuffled.

By observing how the code acted, a developer learns the underlying language construct: the refactor changed concepts from a Vec<String> (which preserves insertion order) to a HashSet<String> (which uses a randomised SipHash for iteration). The tool teaches the developer that while HashSet is functionally correct for ML feature extraction, it introduces non-deterministic intermediate states, which could break deterministic testing or caching layers downstream.

CI/CD Integration

In GitLab CI, this becomes a semantic regression gate. Because the intermediate feature_extract step uses a HashSet, it will constantly trigger divergences. The CI script is tuned to only fail if the actual mathematical output of the pipeline diverges:

trace_check:
  stage: test
  script:
    - cargo run --bin jobpipe -- features old 2> old_trace.jsonl
    - cargo run --bin jobpipe -- features new 2> new_trace.jsonl
    - nix run gitlab:xameer/trace-align/v0.1.1 -- old_trace.jsonl new_trace.jsonl > diff.txt
    # Only fail if the final mathematical score diverged, ignoring HashSet ordering noise
    - if grep -q "\[FAIL\].*final_score" diff.txt; then exit 1; fi
  artifacts:
    when: on_failure
    paths: [diff.txt]

The question moves from “did the test pass?” to “did the refactor preserve the exact operational semantics?”

Roadmap

Manual trace instrumentation is current (v0.1). Planned stages: generic alignment via GHC Generics to auto-derive Alignable instances; AST instrumentation via Template Haskell walking the Rust AST at compile time; dynamic taint analysis tracking data flow through memory rather than matching variables by name; eBPF-backed runtime observation via Aya, hooking syscalls and memory allocations without source modification.

At every stage the goal is the same: compare program semantics rather than program text.

Conclusion

git diff answers “what changed?”

trace-align asks the harder question: did the program’s semantics change?

Copyright (C) 2013-2026 Xameer . All rights reserved.