| Safe Haskell | None |
|---|---|
| Language | GHC2024 |
Proarrow.Tools.SMC
Description
A HOAS front end for building morphisms in any symmetric monoidal category, with
Proarrow.Tools.CCC as its cartesian specialization. It grows with the structure of the target: traces,
duals, additives, and the polarised System L reading of inputs and outputs in a dialogue
category. A Term is indexed by its context, the variables it uses, so a variable is the
identity on its own type. Terms combine by merging their contexts, which reorders wires. A
variable used exactly once needs nothing more. One that two terms both use is copied, which needs
a CocommutativeComonoid on its type, and one that its binder's body does not use is discarded,
which needs a Comonoid. So the types ask for copying and discarding only where a term does it.
Copying a variable copies the value it stands for. A Haskell function that uses its argument
twice uses the term it is given twice, so in a category where copying is not natural, a term to
be shared should be bound to a variable first, with a bind in do notation.
Arrow application and tuple construction adapt terms from earlier binding depths automatically.
Other operations on raw terms may need recast when a variable is used both outside and inside
a binder: x ** lam (\z -> recast x ** z).
A binder's depth still determines its fresh variable ids. If that depth cannot be inferred
for a lambda passed to (-<), bind the lambda in do first.
Types are SYN expressions, interpreted in the target category by Interp. Their tensor is a
constructor, so patterns can determine its shape without inverting the target's ** type family.
Every variable has an id, the number of binders around it, and a context lists its variables
by descending id. Merging compares ids, so it only reduces where the depths are known, which is
the case for terms built directly inside toSMC. A reusable piece is compiled on its own with
toSMC and used with (-<) or lift; a piece without inputs takes unit. toSMC starts again at depth 0, so it
must not be used inside another term: a variable of that term used in it could be taken for one
of its own. Inside a term, bind with do notation instead.
The module also provides do notation, for use with QualifiedDo, and with RecursiveDo a
rec block traces, which needs a traced monoidal category for Term, or
Costrong Tensor p for
TermP p. Composition in the Int construction
(Proarrow.Category.Instance.IntConstruction) uses both: the two morphisms run side by side,
and the wires each needs from the other are fed back.
import Proarrow.Tools.SMC (SYN (..), lift, toSMC, (**))
import Proarrow.Tools.SMC qualified as SMC
Int @bp @bm @cp @cm f . Int @ap @am g =
Int $ toSMC @(F ap :** F cm) \x -> SMC.do
let g' = lift @(F ap :** F bm) @(F am :** F bp) g
f' = lift @(F bp :** F cm) @(F bm :** F cp) f
(ap, cm) <- x
rec ((am, bp), (bm, cp)) <- (g' (ap, bm), f' (bp, cm))
(am, cp)A bind takes its right hand side apart with a pattern, see Patterns below. In a rec block,
the variables that the block itself uses, bm and bp above, are fed back, and the ones the
rest of the do block uses are passed on to it. A variable that both use is copied, and one that
neither uses is discarded. GHC's translation of rec passes every variable of the block to its end again,
including the ones a later statement of the block already used, so only such blocks work where
no statement uses a variable bound by an earlier one. A block of a single statement always
qualifies, and a nested pattern lets one statement bind everything, as above. loop traces
without GHC's translation, so it has neither restriction, but the type of the fed back variable
has to be given.
The module is inspired by Bernardy and Spiwack,
Evaluating Linear Functions to Symmetric Monoidal Categories, whose
P k r a ports correspond to Term, encode to lift, decode to toSMC, (!:) to
(**) and split to split. Unlike their implementation, it keeps the context thinned instead
of computing in the cartesian structure and arguing afterwards that the result is monoidal.
Synopsis
- data SYN k
- type family Interp (s :: SYN k) :: k where ...
- class CategoryOf k => KnownObj (s :: SYN k)
- type Term (d :: Nat) (g :: Ctx k) (a :: SYN k) = TermP ((~>) :: CAT k) d g a
- data TermP (p :: CAT k) (d :: Nat) (g :: Ctx k) (a :: SYN k)
- class ToTerm (p :: CAT k) t (d :: Nat) (g :: Ctx k) (a :: SYN k) | p t -> g a
- toTerm :: ToTerm p t d g a => t -> TermP p d g a
- toSMC :: forall {k} (a :: SYN k) (b :: SYN k) t cont. (Monoidal k, Binds ((~>) :: CAT k) 0 ('[] :: [(Nat, SYN k)]) a b t cont) => (t -> cont) -> Interp a ~> Interp b
- toSMC1 :: forall {k} (a :: k) (b :: k) t cont. (Monoidal k, Binds ((~>) :: CAT k) 0 ('[] :: [(Nat, SYN k)]) ('F a) ('F b) t cont) => (t -> cont) -> a ~> b
- proc :: forall {k} (a :: SYN k) (b :: SYN k) t cont p. (MonoidalProfunctor p, Binds p 0 ('[] :: [(Nat, SYN k)]) a b t cont) => (t -> cont) -> p (Interp a) (Interp b)
- lift :: forall {k} (a :: SYN k) (b :: SYN k) (d :: Nat) (g :: Ctx k) p t. (Promonad p, ToTerm p t d g a) => p (Interp a) (Interp b) -> t -> TermP p d g b
- liftF :: forall {k} (a :: SYN k) (b :: k) t p (d :: Nat) (g :: Ctx k). (Promonad p, BuildTuple p t g a) => p (Interp a) b -> t -> TermP p d g ('F b)
- (-<) :: forall {k} (a :: SYN k) (b :: k) t p (d :: Nat) (g :: Ctx k). (Promonad p, BuildTuple p t g a) => p (Interp a) b -> t -> TermP p d g ('F b)
- returnA :: forall {k} p (a :: k). (Promonad p, Ob a) => p a a
- unit :: forall {k} (d :: Nat) (p :: CAT k). MonoidalProfunctor p => TermP p d ('[] :: [(Nat, SYN k)]) ('I :: SYN k)
- (**) :: forall {k} (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k) (a :: SYN k) (b :: SYN k) (p :: CAT k). (MonoidalProfunctor p, Merge g1 g2) => TermP p d g1 a -> TermP p d g2 b -> TermP p d (Union g1 g2) (a ':** b)
- split :: forall {k} (d :: Natural) (g :: Ctx k) (g' :: Ctx k) (r1 :: Ctx k) (r :: Ctx k) (a :: SYN k) (b :: SYN k) (c :: SYN k) (da :: Nat) (db :: Nat) (p :: CAT k). (Promonad p, MonoidalProfunctor p, KnownObj a, KnownObj b, BindVar (d + 1) b g' r1, BindVar d a r1 r, Merge r g) => TermP p d g (a ':** b) -> (TermP p da '['(d, a)] a -> TermP p db '['(d + 1, b)] b -> TermP p (d + 2) g' c) -> TermP p d (Union r g) c
- type Tuple (p :: CAT k) t (a :: SYN k) = BuildTuple p t (CtxOf t :: Ctx k) a
- class BuildTuple (p :: CAT k) t (g :: Ctx k) (a :: SYN k)
- recast :: forall {k} (a :: SYN k) (b :: SYN k) (d :: Nat) (d' :: Nat) (g :: Ctx k) (p :: CAT k). Interp a ~ Interp b => TermP p d g a -> TermP p d' g b
- lam :: forall {k} (d :: Nat) (r :: Ctx k) (a :: SYN k) (b :: SYN k) t cont. (Closed k, Binds ((~>) :: CAT k) d r a b t cont) => (t -> cont) -> Term d r (a ':-> b)
- class Apply (p :: CAT k) f x r | f -> p where
- (!) :: f -> x -> r
- dup :: forall {k} (s :: SYN k) (d :: Nat) (g :: Ctx k) (p :: k +-> k). (Profunctor p, Comonoid (Interp s)) => TermP p d g s -> TermP p d g (s ':** s)
- drop :: forall {k} (s :: SYN k) (d :: Nat) (g :: Ctx k) (p :: k +-> k). (Profunctor p, Comonoid (Interp s)) => TermP p d g s -> TermP p d g ('I :: SYN k)
- loop :: forall {k} {p :: k +-> k} (u :: SYN k) (b :: SYN k) (d :: Nat) (r :: Ctx k) t cont. (Costrong (Tensor :: k -> (k, k) -> Type) p, SymMonoidal k, KnownObj b, Binds p d r u (b ':** u) t cont) => (t -> cont) -> TermP p d r b
- type Up (a :: SYN k) = 'Not ('Not a)
- type Consumer (d :: Nat) (g :: Ctx k) (a :: SYN k) = Term d g ('Not a)
- type Command (d :: Nat) (g :: Ctx k) = Term d g ('Not ('I :: SYN k))
- type (:##) (a :: SYN k) (b :: SYN k) = 'Not ('Not a ':** 'Not b)
- cont :: forall {k} (d :: Nat) (r :: Ctx k) (a :: SYN k) t cont. (Dialogue k, Binds ((~>) :: CAT k) d r a ('Not ('I :: SYN k)) t cont) => (t -> cont) -> Term d r ('Not a)
- cut :: forall {k} {p :: k +-> k} (a :: SYN k) (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k). (Dialogue k, MonoidalProfunctor p, KnownObj a, Merge g1 g2) => ConsumerP p d g1 a -> TermP p d g2 a -> CommandP p d (Union g1 g2)
- (|>) :: forall {k} {p :: k +-> k} (a :: SYN k) (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k). (Dialogue k, MonoidalProfunctor p, KnownObj a, Merge g2 g1) => TermP p d g1 a -> ConsumerP p d g2 a -> CommandP p d (Union g2 g1)
- ret :: forall {k} {p :: k +-> k} (a :: SYN k) t (d :: Nat) (g :: Ctx k). (Dialogue k, Profunctor p, KnownObj a, BuildTuple p t g a) => t -> TermP p d g (Up a)
- thunk :: forall {k} {p :: CAT k} (n :: SYN k) (d :: Nat) (g :: Ctx k). TermP p d g n -> TermP p d g ('Dn n)
- force :: forall {k} {p :: CAT k} (n :: SYN k) (d :: Nat) (g :: Ctx k). TermP p d g ('Dn n) -> TermP p d g n
- annihilate :: forall {k} {p :: k +-> k} (a :: SYN k) (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k). (IsoMix k, MonoidalProfunctor p, KnownObj a, Merge g1 g2) => ConsumerP p d g1 a -> TermP p d g2 a -> TermP p d (Union g1 g2) ('I :: SYN k)
- classical :: forall {k} {p :: k +-> k} (a :: SYN k) (d :: Nat) (g :: Ctx k). (StarAutonomous k, Profunctor p, KnownObj a) => TermP p d g (Up a) -> TermP p d g a
- produce :: forall {k} {p :: CAT k} (a :: SYN k) (d :: Nat). (CompactClosed k, Promonad p, KnownObj a) => TermP p d ('[] :: [(Nat, SYN k)]) (a ':** 'Not a)
- sumOver :: forall {k} {p :: k +-> k} (a :: SYN k) (d :: Nat) (r :: Ctx k) (b :: SYN k) t cont. (Profunctor p, Frobenius (Interp a), Binds p d r a b t cont) => (t -> cont) -> TermP p d r b
- delta :: forall {k} {p :: k +-> k} (a :: SYN k) (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k). (MonoidalProfunctor p, Frobenius (Interp a), KnownObj a, Merge g1 g2) => TermP p d g1 a -> TermP p d g2 a -> TermP p d (Union g1 g2) ('I :: SYN k)
- (*^) :: forall {k} {p :: k +-> k} (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k) (a :: SYN k) (s :: SYN k) t. (MonoidalProfunctor p, KnownObj a, Merge g1 g2, Interp s ~ (Unit :: k), ToTerm p t d g1 s) => t -> TermP p d g2 a -> TermP p d (Union g1 g2) a
- (^*) :: forall {k} {p :: k +-> k} (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k) (a :: SYN k) (s :: SYN k) t. (MonoidalProfunctor p, KnownObj a, Merge g1 g2, Interp s ~ (Unit :: k), ToTerm p t d g2 s) => TermP p d g1 a -> t -> TermP p d (Union g1 g2) a
- with :: forall {k} (a :: SYN k) (b :: SYN k) (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k). (HasBinaryProducts k, Thin (Union g1 g2) g1, Thin (Union g1 g2) g2) => Term d g1 a -> Term d g2 b -> Term d (Union g1 g2) (a ':&& b)
- exl :: forall {k} {p :: k +-> k} (a :: SYN k) (b :: SYN k) (d :: Nat) (g :: Ctx k). (HasBinaryProducts k, Profunctor p, KnownObj a, KnownObj b) => TermP p d g (a ':&& b) -> TermP p d g a
- exr :: forall {k} {p :: k +-> k} (a :: SYN k) (b :: SYN k) (d :: Nat) (g :: Ctx k). (HasBinaryProducts k, Profunctor p, KnownObj a, KnownObj b) => TermP p d g (a ':&& b) -> TermP p d g b
- absorb :: forall {k} {p :: k +-> k} (s :: SYN k) (d :: Nat) (g :: Ctx k). (HasTerminalObject k, Profunctor p, KnownObj s) => TermP p d g s -> TermP p d g ('Top :: SYN k)
- inl :: forall {k} (a :: SYN k) (b :: SYN k) (d :: Nat) (g :: Ctx k) (p :: k +-> k). (Profunctor p, HasBinaryCoproducts k, KnownObj a, KnownObj b) => TermP p d g a -> TermP p d g (a ':|| b)
- inr :: forall {k} (a :: SYN k) (b :: SYN k) (d :: Nat) (g :: Ctx k) (p :: k +-> k). (Profunctor p, HasBinaryCoproducts k, KnownObj a, KnownObj b) => TermP p d g b -> TermP p d g (a ':|| b)
- caseOf :: forall {k} (a :: SYN k) (b :: SYN k) (c :: SYN k) (d :: Nat) (g :: Ctx k) (r1 :: Ctx k) (r2 :: Ctx k) t1 cont1 t2 cont2 (s :: SYN k) (p :: CAT k). (Distributive k, Promonad p, DistributiveProfunctor p, Sum s a b, KnownObj a, KnownObj b, Binds p d r1 a c t1 cont1, Binds p d r2 b c t2 cont2, Thin (Union r1 r2) r1, Thin (Union r1 r2) r2, Merge (Union r1 r2) g) => TermP p d g s -> (t1 -> cont1) -> (t2 -> cont2) -> TermP p d (Union (Union r1 r2) g) c
- ifThenElse :: forall {k} (a :: SYN k) (b :: SYN k) (c :: SYN k) (d :: Nat) (g :: Ctx k) (r1 :: Ctx k) (r2 :: Ctx k) t1 cont1 t2 cont2 (s :: SYN k) (p :: CAT k). (Distributive k, Promonad p, DistributiveProfunctor p, Sum s a b, KnownObj a, KnownObj b, Binds p d r1 a c t1 cont1, Binds p d r2 b c t2 cont2, Thin (Union r1 r2) r1, Thin (Union r1 r2) r2, Merge (Union r1 r2) g) => TermP p d g s -> (t1 -> cont1) -> (t2 -> cont2) -> TermP p d (Union (Union r1 r2) g) c
- class Interp s ~ Interp (a ':|| b) => Sum (s :: SYN k) (a :: SYN k) (b :: SYN k)
- absurd :: forall {k} {p :: k +-> k} (s :: SYN k) (c :: SYN k) (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k). (Distributive k, MonoidalProfunctor p, KnownObj s, KnownObj c, Merge g1 g2) => TermP p d g1 s -> TermP p d g2 ('Zero :: SYN k) -> TermP p d (Union g1 g2) c
- type Ctx k = [(Nat, SYN k)]
- class KnownCtx (g :: Ctx k)
- type family Union (g1 :: Ctx k) (g2 :: Ctx k) :: Ctx k where ...
- class (KnownCtx g1, KnownCtx g2) => Merge (g1 :: Ctx k) (g2 :: Ctx k)
- class (KnownCtx g, KnownCtx h) => Thin (g :: Ctx k) (h :: Ctx k)
- class KnownCtx r => BindVar (n :: Nat) (a :: SYN k) (g :: Ctx k) (r :: Ctx k) | n g -> r
- (>>=) :: Bind p m t cont r => m -> (t -> cont) -> r
- return :: forall k t (d :: Nat) (p :: CAT k). (Monoidal k, Promonad p, RecVars k t, KnownCtx (Vars k t)) => t -> Ret t (TermP p d (Vars k t) (Mul (Vars k t)))
- mfix :: forall {k} t (d :: Nat) (g :: Ctx k) (p :: CAT k). RecVars k t => (t -> Ret t (TermP p d g (Mul (Vars k t)))) -> Rec p d t g
- fail :: a
- class Bind (p :: CAT k) m t cont r | m -> p
- class (KnownObj a, KnownCtx g) => Binds (p :: CAT k) (n :: Nat) (g :: Ctx k) (a :: SYN k) (b :: SYN k) t cont
Types
Type expressions over the objects of k: an object of k, the unit, the tensor, the
internal hom and the negation, and the additives: the product and its unit Top, and the
coproduct and its unit Zero.
The negation gives the types a polarity: a type is negative when it is a Not, and positive
otherwise. A term of a positive type is a value, and a term of a negative type is a consumer
of what it negates. Up shifts a positive type to a negative one, and Dn a negative type to
a positive one, standing for the same object: a term of is a stored term of Dn nn.
Constructors
| F k | |
| I | |
| (SYN k) :** (SYN k) infixl 7 | |
| (SYN k) :-> (SYN k) infixr 5 | |
| Not (SYN k) | |
| Dn (SYN k) | |
| (SYN k) :&& (SYN k) infixl 6 | |
| Top | |
| (SYN k) :|| (SYN k) infixl 6 | |
| Zero |
Instances
| (Monoidal k, KnownObj a, a ~ b, KnownCtx g) => BindVarBy 'EQ n (a :: SYN k) ('(m, b) ': g :: [(Nat, SYN k)]) (g :: Ctx k) Source Github # | |
| (Monoidal k, Comonoid (Interp a), KnownObj a, KnownObj b, KnownCtx g) => BindVarBy 'GT n (a :: SYN k) ('(m, b) ': g :: [(Nat, SYN k)]) ('(m, b) ': g :: [(Nat, SYN k)]) Source Github # | |
| (Monoidal k, Comonoid (Interp a), KnownObj a) => BindVar n (a :: SYN k) ('[] :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # | |
| (KnownCtx r, BindVarBy (CmpNat n m) n a ('(m, b) ': g) r) => BindVar n (a :: SYN k) ('(m, b) ': g :: [(Natural, SYN k)]) (r :: Ctx k) Source Github # | |
| (SymMonoidal k, CocommutativeComonoid (Interp a), KnownObj a, a ~ b, Merge g1 g2, KnownCtx (Union g1 g2)) => MergeBy 'EQ ('(n, a) ': g1 :: [(Nat, SYN k)]) ('(m, b) ': g2 :: [(Nat, SYN k)]) Source Github # | A variable both contexts have is copied, one copy for each side. |
| (SymMonoidal k, Merge g1 ('(m, b) ': g2), KnownObj a, KnownObj b, Mul ('(n, a) ': Union g1 ('(m, b) ': g2)) ~ (Mul (Union g1 ('(m, b) ': g2)) ':** a)) => MergeBy 'GT ('(n, a) ': g1 :: [(Nat, SYN k)]) ('(m, b) ': g2 :: [(Nat, SYN k)]) Source Github # | |
| (Monoidal k, Merge ('(n, a) ': g1) g2, KnownObj a, KnownObj b, Mul ('(m, b) ': Union ('(n, a) ': g1) g2) ~ (Mul (Union ('(n, a) ': g1) g2) ':** b)) => MergeBy 'LT ('(n, a) ': g1 :: [(Nat, SYN k)]) ('(m, b) ': g2 :: [(Nat, SYN k)]) Source Github # | |
| (Monoidal k, KnownObj a, a ~ b, Thin g h) => ThinBy 'EQ ('(n, a) ': g :: [(Nat, SYN k)]) ('(m, b) ': h :: [(Nat, SYN k)]) Source Github # | |
| (Monoidal k, Comonoid (Interp a), KnownObj a, KnownObj b, Thin g ('(m, b) ': h)) => ThinBy 'GT ('(n, a) ': g :: [(Nat, SYN k)]) ('(m, b) ': h :: [(Nat, SYN k)]) Source Github # | |
| (SymMonoidal k, Unmerge g1 ('(m, b) ': g2), KnownObj a, KnownObj b, Mul ('(n, a) ': Union g1 ('(m, b) ': g2)) ~ (Mul (Union g1 ('(m, b) ': g2)) ':** a)) => UnmergeBy 'GT ('(n, a) ': g1 :: [(Nat, SYN k)]) ('(m, b) ': g2 :: [(Nat, SYN k)]) Source Github # | |
| (Monoidal k, Unmerge ('(n, a) ': g1) g2, KnownObj a, KnownObj b, Mul ('(m, b) ': Union ('(n, a) ': g1) g2) ~ (Mul (Union ('(n, a) ': g1) g2) ':** b)) => UnmergeBy 'LT ('(n, a) ': g1 :: [(Nat, SYN k)]) ('(m, b) ': g2 :: [(Nat, SYN k)]) Source Github # | |
| KnownCtx ('[] :: [(Nat, SYN k)]) Source Github # | |
Defined in Proarrow.Tools.SMC.Internal.Context Methods ctxCase :: (('[] :: [(Nat, SYN k)]) ~ ('[] :: [(Nat, SYN k)]) => r) -> (forall (n :: Nat) (a :: SYN k) (g' :: [(Nat, SYN k)]). (('[] :: [(Nat, SYN k)]) ~ ('(n, a) ': g'), KnownObj a, KnownCtx g') => r) -> r Source Github # withCtxOb :: Monoidal k => (Ob (Interp (Mul ('[] :: [(Nat, SYN k)]))) => r) -> r Source Github # | |
| (Monoidal k, KnownCtx g2) => Merge ('[] :: [(Nat, SYN k)]) (g2 :: Ctx k) Source Github # | |
| (Monoidal k, KnownCtx g2) => Unmerge ('[] :: [(Nat, SYN k)]) (g2 :: Ctx k) Source Github # | |
| Monoidal k => Thin ('[] :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # | |
| (KnownObj a, KnownCtx g) => KnownCtx ('(n, a) ': g :: [(Nat, SYN k)]) Source Github # | |
Defined in Proarrow.Tools.SMC.Internal.Context Methods ctxCase :: (('(n, a) ': g) ~ ('[] :: [(Nat, SYN k)]) => r) -> (forall (n0 :: Nat) (a0 :: SYN k) (g' :: [(Nat, SYN k)]). (('(n, a) ': g) ~ ('(n0, a0) ': g'), KnownObj a0, KnownCtx g') => r) -> r Source Github # withCtxOb :: Monoidal k => (Ob (Interp (Mul ('(n, a) ': g))) => r) -> r Source Github # | |
| (Monoidal k, KnownCtx ('(n, a) ': g1)) => Merge ('(n, a) ': g1 :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # | |
| (Monoidal k, Comonoid (Interp a), KnownObj a, Thin g ('[] :: [(Nat, SYN k)])) => Thin ('(n, a) ': g :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # | |
| (Monoidal k, KnownCtx ('(n, a) ': g1)) => Unmerge ('(n, a) ': g1 :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # | |
| (Monoidal k, KnownObj a, KnownObj b, KnownCtx g1, KnownCtx g2, MergeBy (CmpNat n m) ('(n, a) ': g1) ('(m, b) ': g2)) => Merge ('(n, a) ': g1 :: [(Natural, SYN k)]) ('(m, b) ': g2 :: [(Natural, SYN k)]) Source Github # | |
| (KnownObj a, KnownObj b, KnownCtx g, KnownCtx h, ThinBy (CmpNat n m) ('(n, a) ': g) ('(m, b) ': h)) => Thin ('(n, a) ': g :: [(Natural, SYN k)]) ('(m, b) ': h :: [(Natural, SYN k)]) Source Github # | |
| (Monoidal k, KnownObj a, KnownObj b, KnownCtx g1, KnownCtx g2, UnmergeBy (CmpNat n m) ('(n, a) ': g1) ('(m, b) ': g2)) => Unmerge ('(n, a) ': g1 :: [(Natural, SYN k)]) ('(m, b) ': g2 :: [(Natural, SYN k)]) Source Github # | |
| (Promonad p, KnownObj a) => RecVars k (TermP p d '['(n, a)] a) Source Github # | |
| type Vars k (TermP p d '['(n, a)] a) Source Github # | |
Defined in Proarrow.Tools.SMC.Internal.Do | |
type family Interp (s :: SYN k) :: k where ... Source Github #
The object of k a type expression stands for.
Equations
| Interp ('F a :: SYN k) = a | |
| Interp ('I :: SYN k) = Unit :: k | |
| Interp (a ':** b :: SYN k) = Interp a ** Interp b | |
| Interp (a ':-> b :: SYN k) = Interp a ~~> Interp b | |
| Interp ('Not a :: SYN k) = Dual (Interp a) | |
| Interp ('Dn a :: SYN k) = Interp a | |
| Interp (a ':&& b :: SYN k) = Interp a && Interp b | |
| Interp ('Top :: SYN k) = TerminalObject :: k | |
| Interp (a ':|| b :: SYN k) = Interp a || Interp b | |
| Interp ('Zero :: SYN k) = InitialObject :: k |
class CategoryOf k => KnownObj (s :: SYN k) Source Github #
Type expressions whose Interp is an object, given that their leaves are.
Minimal complete definition
Instances
| Monoidal k => KnownObj ('I :: SYN k) Source Github # | |
| HasTerminalObject k => KnownObj ('Top :: SYN k) Source Github # | |
| HasInitialObject k => KnownObj ('Zero :: SYN k) Source Github # | |
| KnownObj a => KnownObj ('Dn a :: SYN k) Source Github # | |
| (CategoryOf k, Ob a) => KnownObj ('F a :: SYN k) Source Github # | |
| (Dialogue k, KnownObj a) => KnownObj ('Not a :: SYN k) Source Github # | |
| (HasBinaryProducts k, KnownObj a, KnownObj b) => KnownObj (a ':&& b :: SYN k) Source Github # | |
| (Monoidal k, KnownObj a, KnownObj b) => KnownObj (a ':** b :: SYN k) Source Github # | |
| (Closed k, KnownObj a, KnownObj b) => KnownObj (a ':-> b :: SYN k) Source Github # | |
| (HasBinaryCoproducts k, KnownObj a, KnownObj b) => KnownObj (a ':|| b :: SYN k) Source Github # | |
Patterns
Wherever a function on terms receives an input, that is the function given to toSMC, lam,
loop and cont, the alternatives of with and caseOf, and the left of a bind in do
notation, the input arrives through a pattern: a variable, (), or a tuple of patterns. A
variable stands for the whole input, whatever its type, and is discarded if it is not used. ()
matches the unit I. A pair matches a tensor a and binds its two sides, and a tuple
of three to six is pairs nested to the left, as :** ba is. At a computation,
:** b :** c or Up (a :** b), a pair or Up I() pattern runs the computation and matches its
value, so the rest of the block must be of a negative type; a variable at a computation only
names it.
A pair also matches , binding terms of F (a ** b) and F a. The morphism and
uses of the pattern's variables determine the component objects.F b
Tuples build terms as well, the mirror image of taking them apart: ret of a tuple makes a pair
at a tensor into (**) of its parts and a pair at a computation into the computation of the
pair. The empty tuple () stands for unit, including inside larger tuples:
g -< (x, ()) supplies a variable alongside a unit.
A tuple can also be returned directly from a binder: toSMC (x, y) -> (y, x).
A tuple can also be the right hand side of a bind, including inside rec; it is converted
before binding. At least one component must be a term or arrow to identify the promonad.
Its components may themselves be tuples, variables, constants, or (); tuples of three
to six stand for pairs nested to the left, just as in patterns.
A constant arrow c :: Unit ~> a can be used directly alongside variables:
f -< (x, c), ret c, or as a component of a tuple returned by a binder. It uses no variables
and has the embedded type . In F ado notation, y <- c computes the constant
once and binds its result. Each unbound occurrence computes it independently.
At TermP p, a constant of the base category is lifted into the promonad through
arr; a constant already in p is used directly. The surrounding term
determines the target promonad. To bind a base-category constant in another promonad,
write x <- toTerm c: a bare x <- c determines its promonad from c itself.
A tuple bind takes its promonad from its first typed component.
c -< () remains an explicit way to construct a term in the constant's own promonad.
The operator (**) takes concrete terms, giving their types directly when inference needs help.
(-<) mirrors arrow application in Haskell's arrow notation. The wiring of
proc (x, y) -> do z <- f -< x returnA -< (z, y)
can be written as
toSMC \(x, y) -> SMC.do z <- f -< x returnA -< (z, y)
Here toSMC binds the input wires, and returnA is the identity morphism.
(-<) is infix liftF: f -< (x, y) applies f to x ** y and embeds its result by F.
Use lift for composite result syntax.
A tensor result can also be taken apart directly with a pattern:
toSMC \z -> SMC.do (x, y) <- f -< z returnA -< (y, x)
proc compiles the same way to an arrow of a promonad p instead of a morphism, such as an
Arr wrapping a Control.Arrow arrow. Then (-<) takes
arrows of p, variables are values of the category, and the computations run in the order
they are written: statements from top to bottom, the parts of a tuple from left to right.
Terms at p are TermP p. Most operations work at any p, using the category's pure
structure through profunctor mapping. inl and inr use the category's pure injections; caseOf
additionally needs DistributiveProfunctor p,
supplied by ArrowChoice for Arr. The
scrutinee may use (:||) or be a sum embedded by F, including a result of (-<). The
operations loop and rec blocks need Costrong
Tensor p, supplied by ArrowLoop for
Arr. with, lam, cont, and the special tuple and
bind rules at Up work at p = (, that is ~>)Term.
Terms
Symmetric monoidal categories
type Term (d :: Nat) (g :: Ctx k) (a :: SYN k) = TermP ((~>) :: CAT k) d g a Source Github #
A term whose computations are the morphisms of the category itself.
data TermP (p :: CAT k) (d :: Nat) (g :: Ctx k) (a :: SYN k) Source Github #
A term at binding depth d with context g and type a, whose computations are arrows of
the promonad p: an arrow of p from the tensor of the context to a. Variables and the
structure of contexts are morphisms of the category k, which p takes in with lmap and
rmap. At p = ( this is ~>)Term.
Instances
| BindPat p (TermP p d g a) () cont r => BindTerm (p :: CAT k) () (TermP p d g a) cont r Source Github # | |
| (Promonad p, MonoidalProfunctor p, Binds p d r a b t cont, Merge r g, r' ~ TermP p d (Union r g) b) => BindTerm (p :: CAT k) t (TermP p d g a) cont r' Source Github # | |
| BindPat p (TermP p d g a) (x, y) cont r => BindTerm (p :: CAT k) (x, y) (TermP p d g a) cont r Source Github # | |
| BindPat p (TermP p d g a) (x, y, z) cont r => BindTerm (p :: CAT k) (x, y, z) (TermP p d g a) cont r Source Github # | |
| BindPat p (TermP p d g a) (w, x, y, z) cont r => BindTerm (p :: CAT k) (w, x, y, z) (TermP p d g a) cont r Source Github # | |
| (KnownObj a, KnownObj b, Merge g1 g2, ToTerm p x d g2 a, r ~ TermP p d (Union g1 g2) b) => Apply (p :: CAT k) (TermP p d g1 (a ':-> b)) x r Source Github # | |
| (KnownObj a, KnownObj b, Merge g1 g2, f ~ (Interp a ~~> Interp b), ToTerm p x d g2 a, r ~ TermP p d (Union g1 g2) b) => Apply (p :: CAT k) (TermP p d g1 ('F f)) x r Source Github # | |
| (p ~ Hom k, Dialogue k, KnownObj y, Merge g r, Negative (TyOf cont :: SYN k) y, Binds p d r a (TyOf cont :: SYN k) t cont, r' ~ TermP p d (Union g r) ('Not y)) => Bind (p :: CAT k) (TermP p d g ('Not ('Not a))) t cont r' Source Github # | A computation on the right hand side runs first, and the rest of the block is negative. |
| BindTerm p t (TermP p d g a) cont r => Bind (p :: CAT k) (TermP p d g a) t cont r Source Github # | A term on the right hand side is taken apart by the pattern. Incoherent, so that it is chosen as soon as the right hand side is known, unless the right hand side is a computation. |
| (ToTerm p cont (d + PSize t) gc b, r ~ TermP p d gr b, Pat p t d g a gc b gr) => BindPat (p :: CAT k) (TermP p d g a) t cont r Source Github # | |
| TermP q d' g' a' ~ TermP p d g a => ToTerm (p :: CAT k2) (TermP q d' g' a') d (g :: Ctx k2) (a :: SYN k2) Source Github # | |
| (Bind p (TermP p d g a) t cont r', r ~ Ret tt r') => Bind (p :: CAT k) (TermP p d g a) t (Ret tt cont) r Source Github # | The statement of a |
| BindPat p (TermP p d g a) (v, w, x, y, z) cont r => BindTerm (p :: CAT k) (v, w, x, y, z) (TermP p d g a) cont r Source Github # | |
| BindPat p (TermP p d g a) (u, v, w, x, y, z) cont r => BindTerm (p :: CAT k) (u, v, w, x, y, z) (TermP p d g a) cont r Source Github # | |
| TupleProfunctor (TermP p d g a ': ts) (p :: CAT k) Source Github # | |
Defined in Proarrow.Tools.SMC.Internal.Do | |
| (Promonad p, KnownObj a) => RecVars k (TermP p d '['(n, a)] a) Source Github # | |
| t' ~ TermP p d' g a => AnyDepth (TermP p d g a) t' Source Github # | |
Defined in Proarrow.Tools.SMC.Internal.Do | |
| type Vars k (TermP p d '['(n, a)] a) Source Github # | |
Defined in Proarrow.Tools.SMC.Internal.Do | |
class ToTerm (p :: CAT k) t (d :: Nat) (g :: Ctx k) (a :: SYN k) | p t -> g a Source Github #
A term, a constant arrow from the monoidal unit, or a tuple of these.
Constants and the empty tuple use no variables; pairs merge their components' contexts.
Base-category constants enter a promonad through arr; arrows already in it are kept.
Converting a term here keeps its binding depth, unlike tuple construction.
Minimal complete definition
Instances
| (MonoidalProfunctor p, g ~ ('[] :: [(Nat, SYN k)]), a ~ ('I :: SYN k)) => ToTerm (p :: k +-> k) () d (g :: [(Nat, SYN k)]) (a :: SYN k) Source Github # | The empty tuple is the monoidal unit. |
| t ~ TermP p d g a => ToTerm (p :: CAT k) t d (g :: Ctx k) (a :: SYN k) Source Github # | |
| (MonoidalProfunctor p, ToTerm p x d g1 a1, ToTerm p y d g2 a2, Merge g1 g2, g ~ Union g1 g2, a ~ (a1 ':** a2)) => ToTerm (p :: k +-> k) (x, y) d (g :: Ctx k) (a :: SYN k) Source Github # | A pair combines its components as a tensor, merging their contexts. |
| (q x y ~ r (Unit :: k3) b, LiftArrow p r, g ~ ('[] :: [(Nat, SYN k3)]), a ~ 'F b) => ToTerm (p :: CAT k3) (q x y) d (g :: [(Nat, SYN k3)]) (a :: SYN k3) Source Github # | |
| ToTerm p ((x, y), z) d g a => ToTerm (p :: CAT k) (x, y, z) d (g :: Ctx k) (a :: SYN k) Source Github # | |
| ToTerm p ((w, x, y), z) d g a => ToTerm (p :: CAT k) (w, x, y, z) d (g :: Ctx k) (a :: SYN k) Source Github # | |
| ToTerm p ((v, w, x, y), z) d g a => ToTerm (p :: CAT k) (v, w, x, y, z) d (g :: Ctx k) (a :: SYN k) Source Github # | |
| TermP q d' g' a' ~ TermP p d g a => ToTerm (p :: CAT k2) (TermP q d' g' a') d (g :: Ctx k2) (a :: SYN k2) Source Github # | |
| ToTerm p ((u, v, w, x, y), z) d g a => ToTerm (p :: CAT k) (u, v, w, x, y, z) d (g :: Ctx k) (a :: SYN k) Source Github # | |
toTerm :: ToTerm p t d g a => t -> TermP p d g a Source Github #
Explicit conversion for helpers whose result must be a concrete term.
toSMC :: forall {k} (a :: SYN k) (b :: SYN k) t cont. (Monoidal k, Binds ((~>) :: CAT k) 0 ('[] :: [(Nat, SYN k)]) a b t cont) => (t -> cont) -> Interp a ~> Interp b Source Github #
Compile a function on terms to a morphism. The function receives the input through a pattern
(see Patterns), so () compiles a term without inputs and a tuple takes a tensor apart.
toSMC1 :: forall {k} (a :: k) (b :: k) t cont. (Monoidal k, Binds ((~>) :: CAT k) 0 ('[] :: [(Nat, SYN k)]) ('F a) ('F b) t cont) => (t -> cont) -> a ~> b Source Github #
proc :: forall {k} (a :: SYN k) (b :: SYN k) t cont p. (MonoidalProfunctor p, Binds p 0 ('[] :: [(Nat, SYN k)]) a b t cont) => (t -> cont) -> p (Interp a) (Interp b) Source Github #
Compile a function on terms to an arrow of the promonad p, as toSMC does for the morphisms
of the category, which are the case p = (. The terms' computations are arrows of ~>)p,
lifted with (-<) or lift, and run in the order they are written; variables are values,
which the category's structure copies and discards. This mirrors proc in Haskell's arrow
notation, whose Arrows extension must be disabled.
lift :: forall {k} (a :: SYN k) (b :: SYN k) (d :: Nat) (g :: Ctx k) p t. (Promonad p, ToTerm p t d g a) => p (Interp a) (Interp b) -> t -> TermP p d g b Source Github #
Lift an arrow of the promonad to a function on terms, constants or tuples: it runs after the input.
liftF :: forall {k} (a :: SYN k) (b :: k) t p (d :: Nat) (g :: Ctx k). (Promonad p, BuildTuple p t g a) => p (Interp a) b -> t -> TermP p d g ('F b) Source Github #
(-<) :: forall {k} (a :: SYN k) (b :: k) t p (d :: Nat) (g :: Ctx k). (Promonad p, BuildTuple p t g a) => p (Interp a) b -> t -> TermP p d g ('F b) infixr 0 Source Github #
unit :: forall {k} (d :: Nat) (p :: CAT k). MonoidalProfunctor p => TermP p d ('[] :: [(Nat, SYN k)]) ('I :: SYN k) Source Github #
The unit, which uses no variables.
(**) :: forall {k} (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k) (a :: SYN k) (b :: SYN k) (p :: CAT k). (MonoidalProfunctor p, Merge g1 g2) => TermP p d g1 a -> TermP p d g2 b -> TermP p d (Union g1 g2) (a ':** b) infixl 7 Source Github #
Two concrete terms side by side. A variable both use is copied. With effects, the left
term runs first. Use tuples to combine components through ToTerm.
split :: forall {k} (d :: Natural) (g :: Ctx k) (g' :: Ctx k) (r1 :: Ctx k) (r :: Ctx k) (a :: SYN k) (b :: SYN k) (c :: SYN k) (da :: Nat) (db :: Nat) (p :: CAT k). (Promonad p, MonoidalProfunctor p, KnownObj a, KnownObj b, BindVar (d + 1) b g' r1, BindVar d a r1 r, Merge r g) => TermP p d g (a ':** b) -> (TermP p da '['(d, a)] a -> TermP p db '['(d + 1, b)] b -> TermP p (d + 2) g' c) -> TermP p d (Union r g) c Source Github #
Take a tensor apart: the continuation gets a variable for each side.
type Tuple (p :: CAT k) t (a :: SYN k) = BuildTuple p t (CtxOf t :: Ctx k) a Source Github #
A term built from a tuple of terms, by the type it is expected to have: a term is itself,
() is the monoidal unit, a pair at a tensor is the tensor of its parts, and a pair at a
computation is the computation of the pair at Up aa. A tuple of three to six stands for pairs nested to the left, as in
patterns. The parts may come from different binding depths; the result adopts the depth
where it is used, and their contexts are merged.
class BuildTuple (p :: CAT k) t (g :: Ctx k) (a :: SYN k) Source Github #
Build a tuple with its context inferred alongside its type. Keeping the context a parameter allows constant arrows of an abstract category to use the empty context.
Minimal complete definition
Instances
| (MonoidalProfunctor p, a ~ ('I :: SYN k), g ~ ('[] :: [(Nat, SYN k)])) => BuildTuple (p :: k +-> k) () (g :: [(Nat, SYN k)]) (a :: SYN k) Source Github # | The empty tuple is the monoidal unit and uses no variables. |
| ToTerm p t (DepthOf t) g a => BuildTuple (p :: CAT k) t (g :: Ctx k) (a :: SYN k) Source Github # | A term keeps its context and type, adapting to the depth where it is used. Variable ids in the context are unchanged. |
| (MonoidalProfunctor p, a ~ (a1 ':** a2), BuildTuple p x g1 a1, BuildTuple p y g2 a2, Merge g1 g2, g ~ Union g1 g2) => BuildTuple (p :: k +-> k) (x, y) (g :: Ctx k) (a :: SYN k) Source Github # | A pair at a tensor is the tensor of its parts. |
| (Dialogue k, Profunctor p, KnownObj a, BuildTuple p (x, y) g a) => BuildTuple (p :: k +-> k) (x, y) (g :: Ctx k) ('Not ('Not a) :: SYN k) Source Github # | A pair at a computation is the computation of the pair at the value. |
| BuildTuple p ((x, y), z) g a => BuildTuple (p :: CAT k) (x, y, z) (g :: Ctx k) (a :: SYN k) Source Github # | |
| BuildTuple p ((w, x, y), z) g a => BuildTuple (p :: CAT k) (w, x, y, z) (g :: Ctx k) (a :: SYN k) Source Github # | |
| BuildTuple p ((v, w, x, y), z) g a => BuildTuple (p :: CAT k) (v, w, x, y, z) (g :: Ctx k) (a :: SYN k) Source Github # | |
| BuildTuple p ((u, v, w, x, y), z) g a => BuildTuple (p :: CAT k) (u, v, w, x, y, z) (g :: Ctx k) (a :: SYN k) Source Github # | |
recast :: forall {k} (a :: SYN k) (b :: SYN k) (d :: Nat) (d' :: Nat) (g :: Ctx k) (p :: CAT k). Interp a ~ Interp b => TermP p d g a -> TermP p d' g b Source Github #
Closed categories
lam :: forall {k} (d :: Nat) (r :: Ctx k) (a :: SYN k) (b :: SYN k) t cont. (Closed k, Binds ((~>) :: CAT k) d r a b t cont) => (t -> cont) -> Term d r (a ':-> b) Source Github #
A function: the body receives the argument through a pattern (see Patterns). This needs the category to be closed.
class Apply (p :: CAT k) f x r | f -> p where Source Github #
Function application. A variable both the function and its argument use is copied.
Explicit exponentials determine their result syntax. Embedded function objects, such as
results of (-<), take their result syntax from the surrounding term.
Instances
| (KnownObj a, KnownObj b, Merge g1 g2, ToTerm p x d g2 a, r ~ TermP p d (Union g1 g2) b) => Apply (p :: CAT k) (TermP p d g1 (a ':-> b)) x r Source Github # | |
| (KnownObj a, KnownObj b, Merge g1 g2, f ~ (Interp a ~~> Interp b), ToTerm p x d g2 a, r ~ TermP p d (Union g1 g2) b) => Apply (p :: CAT k) (TermP p d g1 ('F f)) x r Source Github # | |
CopyDiscard / Comonoids
dup :: forall {k} (s :: SYN k) (d :: Nat) (g :: Ctx k) (p :: k +-> k). (Profunctor p, Comonoid (Interp s)) => TermP p d g s -> TermP p d g (s ':** s) Source Github #
Copy a term whose type is a comonoid: (x1, x2) <- dup x. Using a variable twice copies it too,
but needs a CocommutativeComonoid; dup needs only a Comonoid, and its two copies come out
in the order of comult.
drop :: forall {k} (s :: SYN k) (d :: Nat) (g :: Ctx k) (p :: k +-> k). (Profunctor p, Comonoid (Interp s)) => TermP p d g s -> TermP p d g ('I :: SYN k) Source Github #
Discard a term whose type is a comonoid: () <- drop t. A variable that is not used is
discarded without it.
Traced monoidal categories
loop :: forall {k} {p :: k +-> k} (u :: SYN k) (b :: SYN k) (d :: Nat) (r :: Ctx k) t cont. (Costrong (Tensor :: k -> (k, k) -> Type) p, SymMonoidal k, KnownObj b, Binds p d r u (b ':** u) t cont) => (t -> cont) -> TermP p d r b Source Github #
Trace: the body receives the value fed back through a pattern (see Patterns), and returns it again next to the result. This needs the category to be traced.
Inputs and outputs
In a dialogue category, one with a tensorial negation Dual, a term of consumes an
Not aa: an output, seen as an input. Terms then read as in System L, the μμ̃-calculus, which treats
the two alike. A Term of a produces an a and a Consumer of a, a term of ,
consumes one; Not acut, or t , is the two meeting, a |> kCommand, a term of ; and
Not Icont is the one binder, which receives an a and runs a command with it, whether that a is
an input or the consumer of an output.
The types have a polarity: is negative, everything else positive. A term of a negative
type is given its consumer, so binding an output of a positive type Not aa with cont gives
, a computation that will produce an Up a = Not (Not a)a, and ret makes a value into
the computation that produces it. In do notation, binding a computation runs it, with the rest
of the block, which must be negative, as what happens next; this is where terms get an
evaluation order, which a symmetric monoidal category does not have by itself. Dn is the
shift the other way, the same object at positive polarity: thunk and force are identities
on the morphism, and a bind names a instead of running it. Patterns and tuples
at a computation are described under Patterns.Dn (Up a)
More structure in the category adds to this. In an isomix category a consumer and its value
join into the unit itself rather than into (Not Iannihilate). In a *-autonomous
category the negation is an involution, so a computation is its value again (classical) and
the polarities collapse. In a compact closed category a value and its consumer can also be
created from nothing (produce), which gives traces and bends wires back on themselves.
Dialogue categories
type Up (a :: SYN k) = 'Not ('Not a) Source Github #
The shift of a positive type to a negative one: a computation that produces an a. A term of
it is a consumer of consumers of a, so in a category with it is the
continuation passing type Dual a = a ~~> r(a -> r) -> r.
type (:##) (a :: SYN k) (b :: SYN k) = 'Not ('Not a ':** 'Not b) infixl 7 Source Github #
Par, the negation of the tensor of the negations, interpreted as Par.
cont :: forall {k} (d :: Nat) (r :: Ctx k) (a :: SYN k) t cont. (Dialogue k, Binds ((~>) :: CAT k) d r a ('Not ('I :: SYN k)) t cont) => (t -> cont) -> Term d r ('Not a) Source Github #
The binder of System L. cont \x -> c is a term of : it receives an Not aa through the
pattern x (see Patterns) and runs the command c with it.
What that a is depends on how the result is used. As a Consumer of a, the a is an input
and cont is μ̃: the seller in a shop receives the order, cont \(name, card, replyTo) -> …. As
a term of the negative type in its own right, the Not aa is the consumer of an output and
cont is μ, Haskell's callCC: a computation receives the consumer of its result,
Up bcont \k -> … |> k; a par b receives a consumer for each side, :## ccont \(kb, kc) -> …;
and a command, , receives nothing, Not Icont \() -> …. A consumer of a par is a
computation, which a nested pair pattern runs to get at the consumers of its sides.
cut :: forall {k} {p :: k +-> k} (a :: SYN k) (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k). (Dialogue k, MonoidalProfunctor p, KnownObj a, Merge g1 g2) => ConsumerP p d g1 a -> TermP p d g2 a -> CommandP p d (Union g1 g2) Source Github #
A consumer meets a producer: cut k t gives t to k, like applying a continuation.
(|>) :: forall {k} {p :: k +-> k} (a :: SYN k) (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k). (Dialogue k, MonoidalProfunctor p, KnownObj a, Merge g2 g1) => TermP p d g1 a -> ConsumerP p d g2 a -> CommandP p d (Union g2 g1) infixl 1 Source Github #
cut with the producer first, as System L writes ⟨t | k⟩: t |> k sends t into k.
ret :: forall {k} {p :: k +-> k} (a :: SYN k) t (d :: Nat) (g :: Ctx k). (Dialogue k, Profunctor p, KnownObj a, BuildTuple p t g a) => t -> TermP p d g (Up a) Source Github #
thunk :: forall {k} {p :: CAT k} (n :: SYN k) (d :: Nat) (g :: Ctx k). TermP p d g n -> TermP p d g ('Dn n) Source Github #
force :: forall {k} {p :: CAT k} (n :: SYN k) (d :: Nat) (g :: Ctx k). TermP p d g ('Dn n) -> TermP p d g n Source Github #
Isomix categories
annihilate :: forall {k} {p :: k +-> k} (a :: SYN k) (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k). (IsoMix k, MonoidalProfunctor p, KnownObj a, Merge g1 g2) => ConsumerP p d g1 a -> TermP p d g2 a -> TermP p d (Union g1 g2) ('I :: SYN k) Source Github #
Join a dual and its wire into nothing: the counit of the duality, which an isomix category has.
*-autonomous categories
classical :: forall {k} {p :: k +-> k} (a :: SYN k) (d :: Nat) (g :: Ctx k). (StarAutonomous k, Profunctor p, KnownObj a) => TermP p d g (Up a) -> TermP p d g a Source Github #
A computation as its value again: double negation elimination, which only a *-autonomous category has. There every type is equivalent to its shift, so the polarities collapse.
Compact closed categories
produce :: forall {k} {p :: CAT k} (a :: SYN k) (d :: Nat). (CompactClosed k, Promonad p, KnownObj a) => TermP p d ('[] :: [(Nat, SYN k)]) (a ':** 'Not a) Source Github #
A new pair of wires, a variable and its dual, from nothing: the unit of the duality. This needs the category to be compact closed.
Hypergraph categories: index notation
Index notation, as in Einstein summation, for a category whose index types are special
commutative Frobenius algebras, such as a hypergraph category. An index is a variable whose type
is such an object. Using an index more than once copies it, so every use sees the same value,
and sumOver binds an index that is summed over. delta says that two wires carry the same
value, which is how a morphism lifted onto an index is tied to another index: in Proarrow.Category.Instance.Mat,
is the entry of delta (f -< i) jf at i and j. A term of type I is a scalar, and
(*^) and (^*) multiply a term by one. An output index is a summed index that the term also
returns, so matrix multiplication is matMulT:
\i -> sumOver \k -> sumOver \j -> delta (f -< i) j *^ delta (g -< j) k *^ k
What the sum is depends on the category: in Mat it is the sum
of numbers, in FinRel it is "there is", and in the diagram
categories it is a wire with no end on the boundary.
sumOver :: forall {k} {p :: k +-> k} (a :: SYN k) (d :: Nat) (r :: Ctx k) (b :: SYN k) t cont. (Profunctor p, Frobenius (Interp a), Binds p d r a b t cont) => (t -> cont) -> TermP p d r b Source Github #
An index summed over: the binder's variable is fed by the unit of its type's monoid, which, copied to every use, is the sum over all the values the index can take. The body receives the index through a pattern (see Patterns).
delta :: forall {k} {p :: k +-> k} (a :: SYN k) (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k). (MonoidalProfunctor p, Frobenius (Interp a), KnownObj a, Merge g1 g2) => TermP p d g1 a -> TermP p d g2 a -> TermP p d (Union g1 g2) ('I :: SYN k) Source Github #
(*^) :: forall {k} {p :: k +-> k} (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k) (a :: SYN k) (s :: SYN k) t. (MonoidalProfunctor p, KnownObj a, Merge g1 g2, Interp s ~ (Unit :: k), ToTerm p t d g1 s) => t -> TermP p d g2 a -> TermP p d (Union g1 g2) a infixl 7 Source Github #
(^*) :: forall {k} {p :: k +-> k} (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k) (a :: SYN k) (s :: SYN k) t. (MonoidalProfunctor p, KnownObj a, Merge g1 g2, Interp s ~ (Unit :: k), ToTerm p t d g2 s) => TermP p d g1 a -> t -> TermP p d (Union g1 g2) a infixl 7 Source Github #
A term multiplied by a scalar on its right.
Additives
The additives share their context between alternatives, of which only one is used, so a variable that several alternatives use is not copied. One that an alternative does not use is discarded there.
with :: forall {k} (a :: SYN k) (b :: SYN k) (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k). (HasBinaryProducts k, Thin (Union g1 g2) g1, Thin (Union g1 g2) g2) => Term d g1 a -> Term d g2 b -> Term d (Union g1 g2) (a ':&& b) Source Github #
Both of two alternatives over the same variables: the product. This needs products.
exl :: forall {k} {p :: k +-> k} (a :: SYN k) (b :: SYN k) (d :: Nat) (g :: Ctx k). (HasBinaryProducts k, Profunctor p, KnownObj a, KnownObj b) => TermP p d g (a ':&& b) -> TermP p d g a Source Github #
The first alternative of a product.
exr :: forall {k} {p :: k +-> k} (a :: SYN k) (b :: SYN k) (d :: Nat) (g :: Ctx k). (HasBinaryProducts k, Profunctor p, KnownObj a, KnownObj b) => TermP p d g (a ':&& b) -> TermP p d g b Source Github #
The second alternative of a product.
absorb :: forall {k} {p :: k +-> k} (s :: SYN k) (d :: Nat) (g :: Ctx k). (HasTerminalObject k, Profunctor p, KnownObj s) => TermP p d g s -> TermP p d g ('Top :: SYN k) Source Github #
Use up a term into the unit of the product.
inl :: forall {k} (a :: SYN k) (b :: SYN k) (d :: Nat) (g :: Ctx k) (p :: k +-> k). (Profunctor p, HasBinaryCoproducts k, KnownObj a, KnownObj b) => TermP p d g a -> TermP p d g (a ':|| b) Source Github #
The left injection into a coproduct.
inr :: forall {k} (a :: SYN k) (b :: SYN k) (d :: Nat) (g :: Ctx k) (p :: k +-> k). (Profunctor p, HasBinaryCoproducts k, KnownObj a, KnownObj b) => TermP p d g b -> TermP p d g (a ':|| b) Source Github #
The right injection into a coproduct.
caseOf :: forall {k} (a :: SYN k) (b :: SYN k) (c :: SYN k) (d :: Nat) (g :: Ctx k) (r1 :: Ctx k) (r2 :: Ctx k) t1 cont1 t2 cont2 (s :: SYN k) (p :: CAT k). (Distributive k, Promonad p, DistributiveProfunctor p, Sum s a b, KnownObj a, KnownObj b, Binds p d r1 a c t1 cont1, Binds p d r2 b c t2 cont2, Thin (Union r1 r2) r1, Thin (Union r1 r2) r2, Merge (Union r1 r2) g) => TermP p d g s -> (t1 -> cont1) -> (t2 -> cont2) -> TermP p d (Union (Union r1 r2) g) c Source Github #
Case analysis on a coproduct. Each branch receives the contents of its alternative through a
pattern (see Patterns), and the variables of the term around it are shared between the
branches. This needs the tensor to distribute over the coproduct.
The sum may be written with (:||) or embedded by F, as in the result of (-<).
For Arr, this needs ArrowChoice
and runs only the selected branch.
ifThenElse :: forall {k} (a :: SYN k) (b :: SYN k) (c :: SYN k) (d :: Nat) (g :: Ctx k) (r1 :: Ctx k) (r2 :: Ctx k) t1 cont1 t2 cont2 (s :: SYN k) (p :: CAT k). (Distributive k, Promonad p, DistributiveProfunctor p, Sum s a b, KnownObj a, KnownObj b, Binds p d r1 a c t1 cont1, Binds p d r2 b c t2 cont2, Thin (Union r1 r2) r1, Thin (Union r1 r2) r2, Merge (Union r1 r2) g) => TermP p d g s -> (t1 -> cont1) -> (t2 -> cont2) -> TermP p d (Union (Union r1 r2) g) c Source Github #
caseOf as overloaded if syntax with RebindableSyntax. Import ifThenElse
unqualified and write if x then l -> ... else r -> .... The then branch handles
the left alternative and the else branch handles the right; each receives its payload.
absurd :: forall {k} {p :: k +-> k} (s :: SYN k) (c :: SYN k) (d :: Nat) (g1 :: Ctx k) (g2 :: Ctx k). (Distributive k, MonoidalProfunctor p, KnownObj s, KnownObj c, Merge g1 g2) => TermP p d g1 s -> TermP p d g2 ('Zero :: SYN k) -> TermP p d (Union g1 g2) c Source Github #
There is no term of Zero, so from one, together with the rest of the context, anything
follows.
Contexts
type Ctx k = [(Nat, SYN k)] Source Github #
A context: the variables a term uses, each with its id and type, by descending id.
class KnownCtx (g :: Ctx k) Source Github #
A context that is known to be empty or not, all the way down.
Instances
| KnownCtx ('[] :: [(Nat, SYN k)]) Source Github # | |
Defined in Proarrow.Tools.SMC.Internal.Context Methods ctxCase :: (('[] :: [(Nat, SYN k)]) ~ ('[] :: [(Nat, SYN k)]) => r) -> (forall (n :: Nat) (a :: SYN k) (g' :: [(Nat, SYN k)]). (('[] :: [(Nat, SYN k)]) ~ ('(n, a) ': g'), KnownObj a, KnownCtx g') => r) -> r Source Github # withCtxOb :: Monoidal k => (Ob (Interp (Mul ('[] :: [(Nat, SYN k)]))) => r) -> r Source Github # | |
| (KnownObj a, KnownCtx g) => KnownCtx ('(n, a) ': g :: [(Nat, SYN k)]) Source Github # | |
Defined in Proarrow.Tools.SMC.Internal.Context Methods ctxCase :: (('(n, a) ': g) ~ ('[] :: [(Nat, SYN k)]) => r) -> (forall (n0 :: Nat) (a0 :: SYN k) (g' :: [(Nat, SYN k)]). (('(n, a) ': g) ~ ('(n0, a0) ': g'), KnownObj a0, KnownCtx g') => r) -> r Source Github # withCtxOb :: Monoidal k => (Ob (Interp (Mul ('(n, a) ': g))) => r) -> r Source Github # | |
type family Union (g1 :: Ctx k) (g2 :: Ctx k) :: Ctx k where ... Source Github #
The context of two terms used side by side.
class (KnownCtx g1, KnownCtx g2) => Merge (g1 :: Ctx k) (g2 :: Ctx k) Source Github #
Split the tensor of the union of two contexts into the tensors of the two contexts. This is
where the wires are reordered, the only place swap is used, and where a variable that both
contexts have is copied.
Minimal complete definition
Instances
| (Monoidal k, KnownCtx g2) => Merge ('[] :: [(Nat, SYN k)]) (g2 :: Ctx k) Source Github # | |
| (Monoidal k, KnownCtx ('(n, a) ': g1)) => Merge ('(n, a) ': g1 :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # | |
| (Monoidal k, KnownObj a, KnownObj b, KnownCtx g1, KnownCtx g2, MergeBy (CmpNat n m) ('(n, a) ': g1) ('(m, b) ': g2)) => Merge ('(n, a) ': g1 :: [(Natural, SYN k)]) ('(m, b) ': g2 :: [(Natural, SYN k)]) Source Github # | |
class (KnownCtx g, KnownCtx h) => Thin (g :: Ctx k) (h :: Ctx k) Source Github #
Keep the variables of g that h has and discard the others, for an alternative of the
additives that does not use all the variables of the other. Every variable of h must be in
g.
Minimal complete definition
Instances
| Monoidal k => Thin ('[] :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # | |
| (Monoidal k, Comonoid (Interp a), KnownObj a, Thin g ('[] :: [(Nat, SYN k)])) => Thin ('(n, a) ': g :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # | |
| (KnownObj a, KnownObj b, KnownCtx g, KnownCtx h, ThinBy (CmpNat n m) ('(n, a) ': g) ('(m, b) ': h)) => Thin ('(n, a) ': g :: [(Natural, SYN k)]) ('(m, b) ': h :: [(Natural, SYN k)]) Source Github # | |
class KnownCtx r => BindVar (n :: Nat) (a :: SYN k) (g :: Ctx k) (r :: Ctx k) | n g -> r Source Github #
A binder's variable n on the right of r, what the body uses besides it, given the body's
context g: snoc if the body uses the variable, and its counit otherwise. The binder's
variable is the newest in scope, so it can only be at the head of g. The functional
dependency, rather than a type family, gives r, so that a binder costs one comparison of ids.
Minimal complete definition
Do notation
(>>=) :: Bind p m t cont r => m -> (t -> cont) -> r Source Github #
Bind the right hand side to the pattern of the continuation.
return :: forall k t (d :: Nat) (p :: CAT k). (Monoidal k, Promonad p, RecVars k t, KnownCtx (Vars k t)) => t -> Ret t (TermP p d (Vars k t) (Mul (Vars k t))) Source Github #
The end of a rec block: all its variables, as the tensor of their context.
mfix :: forall {k} t (d :: Nat) (g :: Ctx k) (p :: CAT k). RecVars k t => (t -> Ret t (TermP p d g (Mul (Vars k t)))) -> Rec p d t g Source Github #
The body of a rec block, to be traced by the bind after it.
GHC's translation of rec refers to fail, but pairs of variables always match.
class Bind (p :: CAT k) m t cont r | m -> p Source Github #
A bind in a do block: a term, constant or tuple taken apart by a pattern, or the variables
of a rec block.
Minimal complete definition
Instances
| (TupleProfunctor '[x, y] p, ToTerm p (x, y) d g a, Bind p (TermP p d g a) t cont r) => Bind (p :: CAT k) (x, y) t cont r Source Github # | Convert a tuple before binding it. At least one component must identify the promonad. |
Defined in Proarrow.Tools.SMC.Internal.Do | |
| (p ~ q, a ~ (Unit :: k), Bind p (TermP p d ('[] :: [(Nat, SYN k)]) ('F b)) t cont r) => Bind (p :: CAT k) (q a b) t cont r Source Github # | Bind a constant arrow, computing it once before the continuation. |
Defined in Proarrow.Tools.SMC.Internal.Do | |
| Bind p ((x, y), z) t cont r => Bind (p :: CAT k) (x, y, z) t cont r Source Github # | |
Defined in Proarrow.Tools.SMC.Internal.Do | |
| Bind p ((w, x, y), z) t cont r => Bind (p :: CAT k) (w, x, y, z) t cont r Source Github # | |
Defined in Proarrow.Tools.SMC.Internal.Do | |
| (Promonad p, MonoidalProfunctor p, Costrong (Tensor :: k -> (k, k) -> Type) p, SymMonoidal k, RecVars k t, AnyDepth t t', AnyDepth t' t, RecVars k t', ToTerm p cont (RecDepth d (Vars k t)) gc c, r ~ TermP p d (Union (Minus gc (Vars k t)) (Minus g (Vars k t))) c, Unmerge (Inter g (Vars k t)) (Minus g (Vars k t)), Union (Inter g (Vars k t)) (Minus g (Vars k t)) ~ g, Thin (Vars k t) (Union (Inter g (Vars k t)) (Inter gc (Vars k t))), Merge (Inter g (Vars k t)) (Inter gc (Vars k t)), Merge (Minus gc (Vars k t)) (Minus g (Vars k t)), Unmerge (Minus gc (Vars k t)) (Inter gc (Vars k t)), Union (Minus gc (Vars k t)) (Inter gc (Vars k t)) ~ gc) => Bind (p :: CAT k) (Rec p d t g) t' cont r Source Github # | The rest of the |
| (p ~ Hom k, Dialogue k, KnownObj y, Merge g r, Negative (TyOf cont :: SYN k) y, Binds p d r a (TyOf cont :: SYN k) t cont, r' ~ TermP p d (Union g r) ('Not y)) => Bind (p :: CAT k) (TermP p d g ('Not ('Not a))) t cont r' Source Github # | A computation on the right hand side runs first, and the rest of the block is negative. |
| BindTerm p t (TermP p d g a) cont r => Bind (p :: CAT k) (TermP p d g a) t cont r Source Github # | A term on the right hand side is taken apart by the pattern. Incoherent, so that it is chosen as soon as the right hand side is known, unless the right hand side is a computation. |
| Bind p ((v, w, x, y), z) t cont r => Bind (p :: CAT k) (v, w, x, y, z) t cont r Source Github # | |
Defined in Proarrow.Tools.SMC.Internal.Do | |
| (Bind p (TermP p d g a) t cont r', r ~ Ret tt r') => Bind (p :: CAT k) (TermP p d g a) t (Ret tt cont) r Source Github # | The statement of a |
| Bind p ((u, v, w, x, y), z) t cont r => Bind (p :: CAT k) (u, v, w, x, y, z) t cont r Source Github # | |
Defined in Proarrow.Tools.SMC.Internal.Do | |
class (KnownObj a, KnownCtx g) => Binds (p :: CAT k) (n :: Nat) (g :: Ctx k) (a :: SYN k) (b :: SYN k) t cont Source Github #
The pattern t of a binder: it takes apart the variable (n, a), and the binder's body
cont then gives a term at depth n + 1 with type b, whose context is g and possibly that
variable. Both the variable's type and the rest of the context must be known.
Minimal complete definition