The Operad of Wiring Diagrams

David I. Spivak · 2013 · arxiv arXiv:1305.0297

Prereqs: basic comfort with typed functions. 🍞 Fritz 2020 helps but isn't required.

A wiring diagram is a box with typed input and output ports. Composing boxes means plugging outputs into inputs — the types must match. This is the syntax layer: how components connect, before you decide what they compute.

Boxes and ports

A box has typed input ports and typed output ports. It's an interface specification — no implementation yet. Think of a function signature without the body.

Boxes compose by wiring outputs to inputs. The types constrain which wirings are legal — you can't plug a "type Z" output into a "type X" input. The composite is itself a box, with its own input and output ports. This is operadic composition: boxes all the way down.

Scheme

; A box is a typed interface: input ports -> output ports
; We represent a box as (name inputs outputs)

(define (make-box name ins outs)
  (list 'box name ins outs))

(define box-A (make-box 'filter '(signal) '(filtered)))
(define box-B (make-box 'amplify '(filtered) '(output)))

(display box-A) (newline)
(display box-B) (newline)
; box-A: signal -> filtered
; box-B: filtered -> output
; The output type of A matches the input type of B.

Supplier assignment

Wiring a diagram means assigning a supplier to each input port. Every input must get its value from exactly one output port (or from an external input of the outer box). The assignment must respect types: a port of type T can only be wired to an output of type T.

Scheme

; Supplier assignment: each input port gets one source
; A wiring is a function from input ports to output ports

(define (wire outer-ins inner-boxes connections)
  ; connections: list of (target-box target-port source-box source-port)
  (map (lambda (c)
    (let ((tgt (list-ref c 0)) (tp (list-ref c 1))
          (src (list-ref c 2)) (sp (list-ref c 3)))
      (list tgt tp '<- src sp)))
  connections))

(define wiring
  (wire '(signal)
        '(filter amplify)
        '((filter signal outer signal)
          (amplify filtered filter filtered))))

(for-each (lambda (w) (display w) (newline)) wiring)
; filter.signal <- outer.signal
; amplify.filtered <- filter.filtered

Composing boxes

The operad operation: given an outer box with inner boxes wired together, collapse the inner structure into a single box. The composite box has the outer box's interface. The internal wiring is hidden — encapsulation.

Scheme

; Composing boxes: wire inner boxes, collapse to one
; The composite has the outer interface

(define (compose-boxes outer-ins outer-outs inner-wiring)
  ; Inner wiring is hidden; result is just outer interface
  (list 'composite outer-ins outer-outs
        (length inner-wiring) 'internal-wires))

(define pipeline
  (compose-boxes '(signal) '(output)
    '((filter.signal <- outer.signal)
      (amplify.filtered <- filter.filtered)
      (outer.output <- amplify.output))))

(display pipeline) (newline)
; (composite (signal) (output) 3 internal-wires)
; From outside: signal -> output. Interior is hidden.

Operadic composition is associative

The key property: composing (A then B) then C gives the same wiring diagram as composing A then (B then C). The wiring diagram operad is a genuine operad — composition is associative and there's an identity (the box that passes all ports through unchanged).

Scheme

; Associativity: (A;B);C = A;(B;C)
; We check that composing three stages is order-independent

(define (pipe f g) (lambda (x) (g (f x))))

(define stage-a (lambda (x) (+ x 1)))
(define stage-b (lambda (x) (* x 2)))
(define stage-c (lambda (x) (- x 3)))

; Left-associated: (A;B);C
(define left ((pipe (pipe stage-a stage-b) stage-c) 5))
; Right-associated: A;(B;C)
(define right ((pipe stage-a (pipe stage-b stage-c)) 5))

(display "((A;B);C)(5) = ") (display left) (newline)
(display "(A;(B;C))(5) = ") (display right) (newline)
(display "equal? ") (display (= left right))
; Associativity holds — this is the operad law.

Notation reference

Paper	Scheme	Meaning
X = (X_in, X_out)	(make-box name ins outs)	Box with typed ports
φ: Y_in → X_out ∐ Z_in	supplier assignment	Wiring function
W(X; Y₁,…,Yₙ)	(compose-boxes ...)	Wiring diagram with n inner boxes
id_X	(lambda (x) x)	Identity box (pass-through)
∘	(pipe f g)	Operadic composition

Neighbors

Other paper pages

🍞 Fritz 2020 — the semantics (Markov categories) that fills these boxes
🍞 Capucci 2021 — cybernetic lenses as wiring diagrams with feedback
🍞 Hedges 2018 — game theory via compositional diagrams

Foundations (Wikipedia)

Translation notes

The examples on this page use lists and symbols to represent typed ports and wiring. Spivak's paper works with operads in the category of typed finite sets — the supplier assignment is a genuine function between coproducts. For example: the wiring diagram above connects two boxes with string labels. In the paper, the same construction uses typed finite sets with a function φ from inner input ports to the disjoint union of outer inputs and other boxes' outputs. The compositional structure is identical. The set-theoretic precision is not.

Every example is Simplified.

Ready for the real thing? arxiv

Read the paper. Start at §2 for the operad definition, §3 for propagation of properties through wiring.

Framework connection: The Natural Framework pipeline is a wiring diagram in Spivak's operad — the operad gives the syntax of how stages connect, while Markov categories give the semantics. (The Natural Framework)

← Sato 2023 · 10 of 21 by june.kim Jacobs 2014 · 12 of 21 →