Chuangjie Xu, November 2026

We construct a Spector bar recursor for each bar-continuous control functional.

Following the approach of Paulo Oliva and Silvia Steila in "A direct proof of
Schwichtenberg's bar recursion closure theorem" (2018, Theorem 2.4), we derive
Spector's bar recursion from general bar recursion.

Oliva and Steila construct a System T term for the recursor from a System T
term for the control. Here we construct an Agda term for the recursor from
a witness that the control is bar continuous.

TODO. Investigate whether Spector bar recursors for bar-continuous control
functionals can be obtained more simply from the modified bar recursors
constructed in InductiveBars.ModifiedBarRecursion. Berger and Oliva's
result that Spector's bar recursion is definable from modified bar recursion
("Modified bar recursion", 2006, Theorem 6.5) suggests a possible route.

\begin{code}

{-# OPTIONS --without-K --safe #-}

open import MLTT.Spartan hiding (𝓀 ; 𝓦)
open import UF.FunExt using (Fun-Ext ; dfunext)

module InductiveBars.SpectorBarRecursion
 (fe : Fun-Ext)
 {𝓀 : Universe}
 (A : 𝓀 Μ‡)
 where

open import MLTT.List
open import Naturals.Order

open import InductiveBars.Sequences hiding (pad)
open import InductiveBars.Basics
open import InductiveBars.Continuity A β„•

\end{code}

A witness of `V controls-recursion-at s` describes the possible recursive
calls starting at s. Along each branch, recursion stops at the first
extension of s that belongs to V.

\begin{code}

data _controls-recursion-at_ {π“₯ : Universe} (V : List A β†’ π“₯ Μ‡)
 : List A β†’ 𝓀 βŠ” π“₯ Μ‡
 where
 stop     : {s : List A}
          β†’ s ∈ V
          β†’ V controls-recursion-at s
 continue : {s : List A}
          β†’ s βˆ‰ V
          β†’ ((a : A) β†’ V controls-recursion-at (s ++ [ a ]))
          β†’ V controls-recursion-at s

\end{code}

For decidable V, if V bars s, then V controls recursion at s.

\begin{code}

bars-implies-controls-recursion-at
 : (V : List A β†’ π“₯ Μ‡) β†’ ((s : List A) β†’ is-decidable (s ∈ V))
 β†’ (s : List A) β†’ V bars s β†’ V controls-recursion-at s
bars-implies-controls-recursion-at V dec s (hit p) = stop p
bars-implies-controls-recursion-at V dec s (step Ο†) =
 cases stop (Ξ» q β†’ continue q ih) (dec s)
 where
  ih : (a : A) β†’ V controls-recursion-at (s ++ [ a ])
  ih a = bars-implies-controls-recursion-at V dec (s ++ [ a ]) (Ο† a)

\end{code}

We evaluate recursively on a witness of `V controls-recursion-at s`.
The following definition shows how the witness determines when to stop
and when to continue.

\begin{code}

module _ {𝓦 : Universe} (X : 𝓦 Μ‡) where

 eval : {V : List A β†’ π“₯ Μ‡}
      β†’ (List A β†’ X) β†’ (List A β†’ (A β†’ X) β†’ X)
      β†’ (s : List A) β†’ V controls-recursion-at s β†’ X
 eval G H s (stop _) = G s
 eval G H s (continue _ Ο†) = H s (Ξ» a β†’ eval G H (s ++ [ a ]) (Ο† a))

\end{code}

Evaluation is independent of the control witness, even when V is not
proposition-valued, because evaluation does not use the data carried by
stop witnesses. We use this independence to verify the recursion equations.

\begin{code}

 eval-witness-independent
  : {V : List A β†’ π“₯ Μ‡}
  β†’ (G : List A β†’ X) (H : List A β†’ (A β†’ X) β†’ X)
  β†’ (s : List A) (c c' : V controls-recursion-at s)
  β†’ eval G H s c = eval G H s c'
 eval-witness-independent G H s (stop p) (stop q) = refl
 eval-witness-independent G H s (stop p) (continue q ψ) = 𝟘-elim (q p)
 eval-witness-independent G H s (continue p Ο†) (stop q) = 𝟘-elim (p q)
 eval-witness-independent G H s (continue p Ο†) (continue q ψ)
  = ap (H s) (dfunext fe ih)
  where
   ih : (a : A)
      β†’ eval G H (s ++ [ a ]) (Ο† a) = eval G H (s ++ [ a ]) (ψ a)
   ih a = eval-witness-independent G H (s ++ [ a ]) (Ο† a) (ψ a)

\end{code}

If V controls recursion at every finite sequence, we can construct
a general bar recursor for V in the sense of Oliva and Steila, using
the above evaluation function.

\begin{code}

 BarRecursor : 𝓀 βŠ” 𝓦 Μ‡
 BarRecursor = (List A β†’ X) β†’ (List A β†’ (A β†’ X) β†’ X) β†’ List A β†’ X

 gbr : {B : List A β†’ π“₯ Μ‡}
     β†’ ((s : List A) β†’ B controls-recursion-at s)
     β†’ BarRecursor
 gbr d G H s = eval G H s (d s)

 general-bar-recursor-spec
  : {B : List A β†’ π“₯ Μ‡} (d : (s : List A) β†’ B controls-recursion-at s)
  β†’ (G : List A β†’ X) (H : List A β†’ (A β†’ X) β†’ X) (s : List A)
  β†’ (s ∈ B β†’ gbr d G H s = G s)
  Γ— (s βˆ‰ B β†’ gbr d G H s = H s (Ξ» a β†’ gbr d G H (s ++ [ a ])))
 general-bar-recursor-spec {B = B} d G H s = base-case , step-case
  where
   unique : (e : B controls-recursion-at s) β†’ gbr d G H s = eval G H s e
   unique e = eval-witness-independent G H s (d s) e
   base-case : s ∈ B β†’ gbr d G H s = G s
   base-case p = unique (stop p)
   step-case : s βˆ‰ B β†’ gbr d G H s = H s (Ξ» a β†’ gbr d G H (s ++ [ a ]))
   step-case q = unique (continue q (Ξ» a β†’ d (s ++ [ a ])))

\end{code}

Now we switch to Spector's bar recursion.

Spector's recursion, controlled by a functional Y : (β„• β†’ A) β†’ β„•, stops at
input s when Y (pad s) < length s. Here pad s extends s to an infinite
sequence by repeating a fixed element aβ‚€ : A after its last entry. So we
assume a given aβ‚€ : A throughout the development of Spector bar recursion.

\begin{code}

 module _ (aβ‚€ : A) where

  private
   pad : List A β†’ β„• β†’ A
   pad = pad-with aβ‚€

  stopping-prefixes : ((β„• β†’ A) β†’ β„•) β†’ List A β†’ 𝓀₀ Μ‡
  stopping-prefixes Y s = Y (pad s) <β„• length s

\end{code}

A bar of determining prefixes gives a bar of stopping prefixes.

This result is due to the fact that, once s determines Y, all extensions
of s by Y (pad s) + 1 entries satisfy the stopping condition.

\begin{code}

  determining-prefix-gives-stopping-level
   : (Y : (β„• β†’ A) β†’ β„•) (s : List A)
   β†’ s determines Y
   β†’ (t : List A) β†’ length t = succ (Y (pad s))
   β†’ (s ++ t) ∈ stopping-prefixes Y
  determining-prefix-gives-stopping-level Y s det t l
   = transport (_≀ℕ length u) e' r
   where
    u : List A
    u = s ++ t
    e : Y (pad u) = Y (pad s)
    e = det (pad u) (pad s)
            (extends-++ (pad u) s t (pad-extends u)) (pad-extends s)
    e' : length t = succ (Y (pad u))
    e' = l βˆ™ (ap succ e) ⁻¹
    r : length t ≀ℕ length u
    r = length-++-right s t

  determining-bar-implies-stopping-bar
   : (Y : (β„• β†’ A) β†’ β„•) (s : List A)
   β†’ (determining-prefixes Y) bars s β†’ (stopping-prefixes Y) bars s
  determining-bar-implies-stopping-bar Y s (hit det)
   = bars-from-level (stopping-prefixes Y) s (succ (Y (pad s)))
      (determining-prefix-gives-stopping-level Y s det)
  determining-bar-implies-stopping-bar Y s (step Ο†) = step ih
   where
    ih : (a : A) β†’ stopping-prefixes Y bars (s ++ [ a ])
    ih a = determining-bar-implies-stopping-bar Y (s ++ [ a ]) (Ο† a)

\end{code}

If Y is bar continuous, its stopping prefixes control recursion at every
finite sequence.

\begin{code}

  bar-continuity-implies-stopping-prefixes-control-recursion
   : (Y : (β„• β†’ A) β†’ β„•) β†’ is-bar-continuous Y
   β†’ (s : List A) β†’ (stopping-prefixes Y) controls-recursion-at s
  bar-continuity-implies-stopping-prefixes-control-recursion Y b s =
   bars-implies-controls-recursion-at (stopping-prefixes Y) dec s
    (determining-bar-implies-stopping-bar Y s
      (bar-continuity-implies-bar-continuityβ€³ Y b s))
   where
    dec : (u : List A) β†’ is-decidable (u ∈ stopping-prefixes Y)
    dec u = <-decidable (Y (pad u)) (length u)

\end{code}

Instantiate the general recursor and its equations with Spector's
stopping predicate.

\begin{code}

  sbr : (Y : (β„• β†’ A) β†’ β„•) β†’ is-bar-continuous Y β†’ BarRecursor
  sbr Y b = gbr (bar-continuity-implies-stopping-prefixes-control-recursion Y b)

  spector-bar-recursor-spec
   : (Y : (β„• β†’ A) β†’ β„•) (b : is-bar-continuous Y)
   β†’ (G : List A β†’ X) (H : List A β†’ (A β†’ X) β†’ X) (s : List A)
   β†’ (Y (pad s) <β„• length s
        β†’ sbr Y b G H s = G s)
   Γ— (length s ≀ℕ Y (pad s)
        β†’ sbr Y b G H s = H s (Ξ» a β†’ sbr Y b G H (s ++ [ a ])))
  spector-bar-recursor-spec Y b G H s
   using (base-case , step-case) ←
     general-bar-recursor-spec
       (bar-continuity-implies-stopping-prefixes-control-recursion Y b) G H s
   = base-case , step-case'
   where
    step-case' : length s ≀ℕ Y (pad s)
               β†’ sbr Y b G H s = H s (Ξ» a β†’ sbr Y b G H (s ++ [ a ]))
    step-case' q = step-case (bigger-or-equal-not-less (length s) (Y (pad s)) q)

\end{code}

Moreover, the above Spector bar recursor is independent of the witness
that the control functional is bar continuous.

\begin{code}

  sbr-witness-independent
   : (Y : (β„• β†’ A) β†’ β„•) (b b' : is-bar-continuous Y)
   β†’ (G : List A β†’ X) (H : List A β†’ (A β†’ X) β†’ X) (s : List A)
   β†’ sbr Y b G H s = sbr Y b' G H s
  sbr-witness-independent Y b b' G H s = eval-witness-independent G H s c c'
   where
    c c' : stopping-prefixes Y controls-recursion-at s
    c  = bar-continuity-implies-stopping-prefixes-control-recursion Y b s
    c' = bar-continuity-implies-stopping-prefixes-control-recursion Y b' s

\end{code}