Arrows and Signal Processing

(import stdlib/arrow.tur)

;; arr: lift a function (identity for the function Arrow)
(let [add1   (arr (fn [x] (+ x 1)))
      double (arr (fn [x] (* x 2)))]

  ;; >>> : compose left-to-right: add1 first, then double
  (let [pipeline (>>> add1 double)]
    (println (pipeline 5))))   ; => 12

(import stdlib/arrow.tur)

(let [add1       (arr (fn [x] (+ x 1)))
      first-add1 (arrow-first add1)    ; apply add1 to fst, pass snd through
      p          (Pair 5 10)]
  (println (first-add1 p)))            ; => Pair(6, 10)

(let [both (par-comp 0 0 0 0 (fn [x] (+ x 1)) (fn [x] (* x 2)))]
  (both (Pair 3 4)))   ; => Pair(4, 8)

(let [split (arrow-split 0 0 0 (fn [x] (+ x 1)) (fn [x] (* x 2)))]
  (split 3))   ; => Pair(4, 6)

((arrow-const 42) 999)        ; => 42  (ignores input)
(tuple2-1st (arrow-dup 7))    ; => 7   (Tuple2(7, 7))

(load "stdlib/arrow.tur")

(defn add1 [x : int] : int (+ x 1))
(defn mul2 [x : int] : int (* x 2))

(defn main [] : int
  (let [h (>>> add1 mul2)]      ; >>> dispatches to Arrow [(->)]
    (println (h 3)))            ; => 8
  (let [g (<<< add1 mul2)]      ; reverse composition, only on this surface
    (println (g 3)))            ; => 7  (add1(mul2(3)))
  0)

arr is eta-expanded in the instance ((fn [x] (f x)), not the bare f) so the dispatched result carries a concrete arrow type and is directly callable; see docs/archive/history/instance-method-returning-untyped-param-loses-result-type.md.

Category -- identity and composition

Category is the base of the hierarchy: an identity arrow ident and forward composition comp (comp f g runs f, then g). comp is a distinct method name from Arrow's >>>, so the two coexist without an operator collision.

ident is nullary -- there is no argument to dispatch on, so it resolves by return-type / unique-instance dispatch (the mechanism from return-type-dispatch-nullary-arrow-methods-plan). With only the (->) instance in scope, a bare (ident) resolves uniquely:

(load "stdlib/arrow.tur")

(defn add1 [x : int] : int (+ x 1))

(defn main [] : int
  (let [i (ident)] (println (i 41)))        ; identity arrow      => 41
  (let [h (comp (ident) add1)] (println (h 41)))  ; left identity  => 42
  (let [h (comp add1 (ident))] (println (h 41)))  ; right identity => 42
  0)

Once a second Category instance is in scope (e.g. Kleisli below), a bare (ident) is ambiguous -- ascribe it to pick the head: (:: (ident) :Kleisli).

ArrowZero honestly: the Kleisli arrow (stdlib/kleisli.tur)

The (->) arrow has no ArrowZero instance because a total function a -> b with no input cannot conjure an inhabitant of b. The honest home for zero-arrow is an arrow whose codomain has a zero. stdlib/kleisli.tur provides one: Kleisli A B = A -> Option B, where none is the zero.

(load "stdlib/kleisli.tur")

(defn safe-recip [x : int] : int (if (= x 0) (none) (some (/ 100 x))))
(defn add1m      [x : int] : int (some (+ x 1)))

(defn main [] : int
  ;; Category [Kleisli]: ident = \a -> some a; comp threads Option-bind
  (let [fg (:: (comp (kleisli safe-recip) (kleisli add1m)) :Kleisli)
        r  (k-apply fg 5)]
    (println (unwrap-or r -1)))          ; (100/5)+1 => 21

  ;; none short-circuits composition
  (let [fg (:: (comp (kleisli safe-recip) (kleisli add1m)) :Kleisli)
        r  (k-apply fg 0)]
    (println (some? r)))                 ; safe-recip 0 -> none => false

  ;; ArrowZero [Kleisli]: the honest zero arrow, \_ -> none
  (let [z (:: (zero-arrow) :Kleisli)]
    (println (some? (k-apply z 99))))    ; => false
  0)

Kleisli is the worked second Category instance the hierarchy needs; it is also the reason ArrowZero stays declared-but-uninstantiated at (->).

Ascription-disambiguated arrows ((:: (ident) :Kleisli), etc.) are ordinary unrestricted values and may be reused freely.

ArrowChoice over Either

ArrowChoice routes an arrow over one arm of a binary sum. It builds on the Either sum type (stdlib/either.tur, from docs/archive/history/sum-types-either-plan.md); left acts on Left and passes Right through, +++ fans two arrows over the two arms, and ||| collapses both arms to a common result:

(load "stdlib/arrow.tur")

(defn add1 [x : int] : int (+ x 1))
(defn mul2 [x : int] : int (* x 2))

(defn main [] : int
  (let [c (||| add1 mul2)]
    (println (c (Left 10)))     ; add1(10) => 11
    (println (c (Right 7))))    ; mul2(7)  => 14
  0)

ArrowLoop -- feedback

arrow-loop feeds part of an arrow's output back as input: given an arrow a (b, d) (c, d) it produces a b c, wiring the d output round to the d input. In Haskell that knot is tied by laziness. Turmeric is strict, so the d slot cannot simply be the value the same run is about to produce -- and the fix is to hand the looped arrow a LoopCell in slot 1 instead of a bare value. The cell splits "the value is written" from "the value is read", which is all laziness was buying:

LoopCell  =  { filled : int64, value : int64 }   ; two words on the heap

Three combinators fill the cell at three different times. They share one protocol -- slot 1 is always a LoopCell -- so a single looped arrow works under all three.

Reading the cell:

Lazy feedback (knot-tying)

The looped arrow's c output is defined by the d output of the same run -- it parks the cell handle in c and the consumer forces it afterwards:

(load "stdlib/arrow.tur")

;; c = the feedback cell itself; d = b * 10, known only at the end of the run.
(defn park-cell [p] : int
  ```c typedef struct { int64_t e1; int64_t e2; } P;
  P *s = (P *)(intptr_t)p;
  P *r = (P *)malloc(sizeof(P));
  r->e1 = s->e2;
  r->e2 = s->e1 * 10;
  return (int64_t)(intptr_t)r; ```)

(defn main [] : int
  (let [lp (arrow-loop park-cell)
        c  (loop-cell-of (lp 7))]
    (println (loop-cell-force c)))   ; => 70
  0)

An arrow that forces the cell during the run has demanded its own output; that is a genuine error, and it panics with <<loop>> rather than quietly reading a sentinel. Guard with loop-cell-ready? when a miss is expected.

Fixpoint feedback

;; newton: d' = (d + b/d)/2, c = d -- iterate to floor(sqrt(b)).
((arrow-loop-fix newton 1 32) 144)    ; => 12

fuel is a bound, not an assertion: a non-converging arrow spends its passes and returns the last c rather than hanging.

Delayed feedback

;; sum-step: d' = c = d + b -- a running total, seeded at 0.
(let [acc (arrow-loop-delay sum-step 0)]
  (acc 1) (acc 2) (acc 3))            ; => 1, 3, 6

The returned arrow is stateful: it owns one cell, so each call advances the same feedback line. Call arrow-loop-delay again for an independent one.

Writing the looped arrow

The arrow layer runs on an erased two-slot heap pair of int64, so a looped arrow written in Turmeric takes and returns that carrier and ascribes at the edges:

(load "stdlib/tuple.tur")

(defn prev-step [p : int] : int             ; unit delay: emit the previous b
  (let [t (:: p (Tuple2 int int))
        b (tuple2-1st t)
        d (loop-cell-force (loop-cell-of (tuple2-2nd t)))]
    (:: (tuple2 d b) :int)))

An inline-C arrow redeclares the cell layout locally, the same way the pair helpers in stdlib/arrow.tur redeclare P:

typedef struct { int64_t filled; int64_t value; } LC;

Declaring the arrow directly over (Tuple2 int int) works too, and computes the same values -- the compiler bridges the by-value aggregate to the carrier at the fat-box boundary:

(defn prev-step [t : (Tuple2 int int)] : (Tuple2 int int)
  (tuple2 (loop-cell-force (loop-cell-of (tuple2-2nd t)))
          (tuple2-1st t)))

(That crossing used to return garbage and then segfault; see docs/archive/arrow-struct-typed-arrow-abi.md. tests/fixtures/arrow-struct-typed-arrow now asserts the two spellings agree under every member of the family.)

Fixtures: arrow-loop-lazy-feedback, arrow-loop-fix, arrow-loop-delay, arrow-struct-typed-arrow, and arrow-instance-loop-nonrecursive (the degenerate case, where the arrow ignores d entirely).

Both surfaces agree

The dispatch surface computes the same values as the bare functions for (->) -- tests/fixtures/arrow-instance-vs-bare runs the same pipeline both ways and asserts identical output. The dispatch fixtures (arrow-instance-stdlib-basic, -choice, -loop-nonrecursive, -apply, -closure-capture) lock the typeclass path, including capturing closures flowing through the instance dictionary.

Signals and Signal Functions

Where the Signal/SF library lives: the worked implementation is the tur-signal spice in ../turmeric-spices/spices/signal/ (see docs/archive/history/tur-signal-rebuild-plan.md for the rebuild plan and acceptance state). The code samples below are written against stdlib/signal/... paths; there is no stdlib/signal/ in this repo, so treat them as the conceptual surface -- the same names are exported by signal/core, signal/osc, signal/filter, signal/shaper, signal/envelope, and signal/compose in the spice.

stdlib/signal/core.tur introduces the Signal abstraction:

Signal a  =  Time -> a
SF a b    =  Signal a -> Signal b

A Signal is just a function from time to a value. A Signal Function (SF) transforms one signal into another. Because SF is itself a function (Signal a -> Signal b), the bare-function arrow combinators apply without any extra machinery: arr, >>>, arrow-first, and arrow-second all work on SFs out of the box.

Core signal constructors

(import stdlib/signal/core.tur)

;; constant: ignore time, always return the same value
(let [dc (constant 5.0)]
  (dc 0.0)    ; => 5.0
  (dc 99.0))  ; => 5.0

;; time-signal: identity -- returns the time at each sample
(time-signal 2.5)   ; => 2.5

;; sample: evaluate a signal at a point in time
(sample (constant 3.0) 1.0)   ; => 3.0

;; map-signal: lift a function to pointwise operation over a signal
(let [louder (map-signal (fn [x] (* x 2.0)) (constant 0.5))]
  (louder 0.0))   ; => 1.0

(let [prod (pair-signals (constant 1.0) (constant 2.0))]
  (prod 0.0))   ; => Pair(1.0, 2.0)

(import stdlib/signal/core.tur)
(import stdlib/signal/dsp.tur)

(let [dummy  (constant ())
      ;; sine oscillator: freq Hz, initial phase in radians
      a440   (sine 440.0 0.0)
      ;; square wave: freq, duty cycle [0,1]
      sq     (square 220.0 0.5)
      ;; sawtooth wave: freq
      saw    (sawtooth 110.0)
      ;; triangle wave (stdlib/signal/dsp.tur -- if available)
      tri    (triangle 55.0)]

  ;; An oscillator SF is called with a (usually dummy) input signal
  ;; and returns the output signal.
  ((a440 dummy) 0.001))

;; low-pass: exponential moving average.
;; alpha in (0,1) -- lower alpha = more smoothing (shorter cutoff)
(let [lp  (low-pass 0.1)
      sig (constant 1.0)
      out (lp sig)]
  (out 0.0)    ; starts at 0 (filter state is zero-initialised)
  (out 0.001))

;; high-pass: subtract the low-passed signal from the input
(let [hp  (high-pass 0.1)
      out (hp sig)]
  (out 0.001))

(let [sig    ((sine 440.0 0.0) (constant ()))

      ;; gain: scale every sample by a constant
      gained ((gain 0.5) sig)

      ;; mix: weighted blend of a pair signal
      ;; alpha=0 -> all first, alpha=1 -> all second
      blended ((mix 0.3) (pair-signals sig (constant 0.0)))

      ;; add: sample-wise sum of a pair signal
      summed  ((add) (pair-signals sig sig))]
  ...)

(import stdlib/signal/core.tur)
(import stdlib/signal/dsp.tur)

(let [dummy (constant ())
      input ((sine 440.0 0.0) dummy)

      ;; Signal graph:
      ;;   sine 440 Hz
      ;;     -> gain 0.5
      ;;     -> low-pass (alpha 0.1)
      ;;     -> DC offset +0.1
      ;;     -> clip [-0.8, 0.8]
      chain (>>> (>>> (>>> (gain 0.5)
                           (low-pass 0.1))
                      (offset 0.1))
                 (clip -0.8 0.8))

      output (chain input)]

  (output 0.0)
  (output 0.001)
  (output 0.002))

(let [dummy     (constant ())
      raw       ((sine 440.0 0.0) dummy)

      ;; Branch A: full signal
      branch-a  raw

      ;; Branch B: low-passed version
      branch-b  ((low-pass 0.05) raw)

      ;; Mix 50/50
      output    ((mix 0.5) (pair-signals branch-a branch-b))]

  (output 0.001))

(let [dummy  (constant ())
      a440   ((sine 440.0 0.0) dummy)   ; root
      e660   ((sine 660.0 0.0) dummy)   ; perfect fifth
      summed ((add) (pair-signals a440 e660))
      out    ((gain 0.5) summed)]       ; normalise

  (out 0.001))