Determinism, Canonical Form, and Identity

Determinism is a property of interpretation. It is not a claim that the outside world has no effects.

Determinism begins with complete inputs

The pure interpreter takes four inputs together: the chart, its bindings, the current snapshot, and the event. Given the same four inputs, it returns the same StepResult. A chart without its bindings is not a complete interpretation input, and a snapshot without the event does not name a step to interpret.

The fold produces a next snapshot, a serializable emit plan, and a trace. External effects stay outside that fold. Emit actions add deferred plan intents, and a runtime handles those intents after the chart decision has crossed its commit boundary. This separation keeps an effect from changing which transition the same fold selects.

The macrostep page owns the walk through microsteps and atomic commit. This page owns the identity and canonical-form rules that make the inputs and outputs comparable. The testing, simulation, and conformance page owns simulator-based verification of those rules.

Order is data where behavior depends on it

Canonical form does not mean sorting every array. Authored state order, transition order, and action order remain intact because they affect configuration, selection, entry and exit, and action execution. Reordering any of them can change the chart while leaving the individual values unchanged.

Normalization belongs to collections whose order is not behavior. Declared reference names are ordered lexicographically within each reference group. Object keys are also ordered lexicographically during canonical JSON serialization. The rule is simple: normalize membership where membership is the meaning, and preserve authored order where order is the meaning.

That distinction is why a canonical chart can be stable without becoming a sorted rewrite of the author's document. Canonicalization never reorders authored state, transition, or action order.

Canonical JSON is the document authority

Chart.toCanonicalJson serializes the complete canonical chart document. It uses lexicographic object keys, two-space indentation, and one trailing newline. Undefined object properties are omitted. null, non-finite numbers, and unsupported value types are rejected instead of being silently assigned a representation.

The complete document includes its formatVersion stamp. That stamp tells a decoder which interchange format it is reading. The document is therefore a precise record of the chart value, including the metadata needed to interpret that format.

The canonical document is not a pretty-printed view layered on top of a different authority. It is the authority for the chart's serialized form. The hash rule below deliberately derives a second, structure-only byte sequence from it, so readers should not confuse a document with the identity derived from its structure.

Chart hashes use structure-only identity bytes

Chart.hash canonicalizes the chart, removes formatVersion from that canonical value, and serializes the remaining structure with the same canonical JSON formatting laws. It encodes those bytes as UTF-8, hashes them with SHA-256, and renders the result with a sha256- prefix followed by 64 lowercase hexadecimal digits.

The complete canonical document and the hash preimage are deliberately distinct. The document records the format stamp. The structure-only identity bytes do not, so a format stamp change alone does not change the chart's structural identity. The result identifies a chart definition's structure. It is not an instance identifier and must not be used as one.

This is also why the hash inspector below is concept-labeled. It will show the relationship between the document and the structure-only derivation when that future vignette is real. It does not print or rely on a concrete identity value in this page.

Concept vignette: hash inspector. A future hash inspector will let a reader change canonical chart structure and observe the asserted equality or inequality of the derived identity. This placeholder is a concept, not a live engine element.

Keyed sends identify message intent

An authored event that implements Effect's PrimaryKey protocol receives a stable, backend-safe message identity before it crosses an engine boundary. The derivation is versioned and domain-separated. Its exact preimage is the UTF-8 encoding of:

motive/keyed-send/v1\nJSON.stringify([eventTag, primaryKey])

The JSON tuple is important. It preserves the boundary between the event tag and the authored primary key, so two different pairs cannot become one pair by concatenating strings. JSON escaping also preserves embedded NULs and lone UTF-16 surrogates before UTF-8 encoding.

The rendered identity has a fixed length of 71 bytes. Its sha256- prefix and 64 lowercase hexadecimal digits fit the engine message-identity boundary without restricting the authored primary-key length. The /v1 derivation is immutable. A future derivation change must use a new versioned domain.

This identity names message intent, not chart structure. Repeated sends with the same event tag and authored primary key converge on the same durable step. A chart hash answers a question about a chart definition; a keyed-send identity answers a question about one authored message intent.

Identity does not strengthen delivery semantics

Stable identity makes redelivery and deduplication comparable. It does not make an external effect exactly once. The fold can publish one chart decision and one deferred intent, while the handler effect that consumes that intent remains an at-least-once operation.

So the safe conclusion from a repeated keyed-send identity is narrow: the same message intent can be recognized again. It is not evidence that a payment, notification, write, or any other external effect ran exactly once. Identity supports the boundary around delivery; it does not move that boundary or change the execution semantics beyond it.

Verification examples

These witnesses assert the failure directions without printing any chart hash or keyed-send identity. The canonical-form witness shows equal canonical output for reordered reference groups, and unequal output when authored state or transition order changes. It also checks that the complete document keeps its format stamp and that the rendered hash has the specified shape.

import { Effect } from "effect";
import { Chart, FormatVersion } from "@motive/motive";

const draft: Chart.AtomicNode = {
  id: "Draft",
  kind: "Atomic",
  transitions: [
    {
      event: "Approve",
      actions: [
        { kind: "Raise", event: "Approved" },
        { kind: "Assign", ref: "markApproved" },
      ],
    },
    { event: "Reject" },
  ],
};

const sent: Chart.FinalNode = { id: "Sent", kind: "Final" };

const orderedChart: Chart.Chart = {
  formatVersion: FormatVersion.current,
  id: "Order",
  kind: "Compound",
  refs: {
    assigns: ["markApproved"],
    guards: ["isReady"],
    sends: ["sendFirst", "sendSecond"],
  },
  subscriptions: {
    Alerts: ["Delivered", "Queued"],
    Audit: ["Written"],
  },
  initial: ["Draft"],
  children: [draft, sent],
};

const reorderedRefsChart: Chart.Chart = {
  ...orderedChart,
  refs: {
    sends: ["sendSecond", "sendFirst"],
    guards: ["isReady"],
    assigns: ["markApproved"],
  },
  subscriptions: {
    Audit: ["Written"],
    Alerts: ["Queued", "Delivered"],
  },
};

const reorderedStatesChart: Chart.Chart = {
  ...orderedChart,
  children: [sent, draft],
};

const reorderedTransitionsChart: Chart.Chart = {
  ...orderedChart,
  children: [{ ...draft, transitions: [...draft.transitions!].reverse() }, sent],
};

export const verifyCanonicalForm = Effect.gen(function* () {
  const document = Chart.toCanonicalJson(orderedChart);
  if (!document.endsWith("\n")) throw new Error("canonical JSON needs a trailing newline");
  if (!document.includes('"formatVersion"')) {
    throw new Error("the complete chart document keeps its format stamp");
  }

  if (Chart.toCanonicalJson(orderedChart) !== Chart.toCanonicalJson(reorderedRefsChart)) {
    throw new Error("unordered reference groups should canonicalize equally");
  }
  if (Chart.toCanonicalJson(orderedChart) === Chart.toCanonicalJson(reorderedStatesChart)) {
    throw new Error("authored state order must remain semantic");
  }
  if (Chart.toCanonicalJson(orderedChart) === Chart.toCanonicalJson(reorderedTransitionsChart)) {
    throw new Error("authored transition order must remain semantic");
  }

  const expected = yield* Chart.hash(orderedChart);
  const sameStructure = yield* Chart.hash(reorderedRefsChart);
  const changedStructure = yield* Chart.hash(reorderedStatesChart);
  if (!/^sha256-[0-9a-f]{64}$/.test(expected) || expected.length !== 71) {
    throw new Error("chart identity must have the fixed SHA-256 rendering");
  }
  if (expected !== sameStructure) throw new Error("equivalent structure must hash equally");
  if (expected === changedStructure) throw new Error("changed structure must hash differently");
});

The keyed-send witness keeps tuple boundaries distinct and checks the two string-encoding edge cases that matter at this boundary. Equality is asserted for repetition. Inequality is asserted for a different tuple, an embedded NUL, and a lone surrogate versus the replacement character.

import { Effect } from "effect";
import { StatechartEngine } from "@motive/motive";

export const verifyKeyedSendIdentity = Effect.gen(function* () {
  const first = yield* StatechartEngine.deriveEventPrimaryKey("ab", "c");
  const repeated = yield* StatechartEngine.deriveEventPrimaryKey("ab", "c");
  const otherTuple = yield* StatechartEngine.deriveEventPrimaryKey("a", "bc");
  const embeddedNul = yield* StatechartEngine.deriveEventPrimaryKey("ab", "c\u0000d");
  const loneSurrogate = yield* StatechartEngine.deriveEventPrimaryKey("ab", "\ud800");
  const replacementCharacter = yield* StatechartEngine.deriveEventPrimaryKey("ab", "\ufffd");

  if (!/^sha256-[0-9a-f]{64}$/.test(first) || first.length !== 71) {
    throw new Error("keyed-send identity must have the fixed SHA-256 rendering");
  }
  if (first !== repeated) throw new Error("repeated keyed sends must converge");
  if (first === otherTuple) throw new Error("tuple boundaries must remain distinct");
  if (embeddedNul.includes("\u0000")) throw new Error("encoded identity must not contain a NUL");
  if (loneSurrogate === replacementCharacter) {
    throw new Error("lone surrogates must remain distinct from replacement characters");
  }
});