proarrow
Safe HaskellNone
LanguageGHC2024

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

Types

data SYN k Source Github #

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 Dn n is a stored term of n.

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

Instances details
(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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

bindVarBy :: (Interp (Mul g) ** Interp a) ~> Interp (Mul ('(m, b) ': g)) 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

bindVarBy :: (Interp (Mul ('(m, b) ': g)) ** Interp a) ~> Interp (Mul ('(m, b) ': g)) Source Github #

(Monoidal k, Comonoid (Interp a), KnownObj a) => BindVar n (a :: SYN k) ('[] :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

bindVar :: (Interp (Mul ('[] :: [(Nat, SYN k)])) ** Interp a) ~> Interp (Mul ('[] :: [(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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

bindVar :: (Interp (Mul r) ** Interp a) ~> Interp (Mul ('(m, b) ': g)) 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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

mergeBy :: Interp (Mul (UnionBy 'EQ ('(n, a) ': g1) ('(m, b) ': g2))) ~> (Interp (Mul ('(n, a) ': g1)) ** Interp (Mul ('(m, b) ': g2))) Source Github #

(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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

mergeBy :: Interp (Mul (UnionBy 'GT ('(n, a) ': g1) ('(m, b) ': g2))) ~> (Interp (Mul ('(n, a) ': g1)) ** Interp (Mul ('(m, b) ': g2))) 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

mergeBy :: Interp (Mul (UnionBy 'LT ('(n, a) ': g1) ('(m, b) ': g2))) ~> (Interp (Mul ('(n, a) ': g1)) ** Interp (Mul ('(m, b) ': g2))) 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

thinBy :: Interp (Mul ('(n, a) ': g)) ~> Interp (Mul ('(m, b) ': h)) 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

thinBy :: Interp (Mul ('(n, a) ': g)) ~> Interp (Mul ('(m, b) ': h)) 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

unmergeBy :: (Interp (Mul ('(n, a) ': g1)) ** Interp (Mul ('(m, b) ': g2))) ~> Interp (Mul (UnionBy 'GT ('(n, a) ': g1) ('(m, b) ': g2))) 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

unmergeBy :: (Interp (Mul ('(n, a) ': g1)) ** Interp (Mul ('(m, b) ': g2))) ~> Interp (Mul (UnionBy 'LT ('(n, a) ': g1) ('(m, b) ': g2))) Source Github #

KnownCtx ('[] :: [(Nat, SYN k)]) Source Github # 
Instance details

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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

merge :: Interp (Mul (Union ('[] :: [(Nat, SYN k)]) g2)) ~> (Interp (Mul ('[] :: [(Nat, SYN k)])) ** Interp (Mul g2)) Source Github #

(Monoidal k, KnownCtx g2) => Unmerge ('[] :: [(Nat, SYN k)]) (g2 :: Ctx k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

unmerge :: (Interp (Mul ('[] :: [(Nat, SYN k)])) ** Interp (Mul g2)) ~> Interp (Mul (Union ('[] :: [(Nat, SYN k)]) g2)) Source Github #

Monoidal k => Thin ('[] :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

thin :: Interp (Mul ('[] :: [(Nat, SYN k)])) ~> Interp (Mul ('[] :: [(Nat, SYN k)])) Source Github #

(KnownObj a, KnownCtx g) => KnownCtx ('(n, a) ': g :: [(Nat, SYN k)]) Source Github # 
Instance details

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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

merge :: Interp (Mul (Union ('(n, a) ': g1) ('[] :: [(Nat, SYN k)]))) ~> (Interp (Mul ('(n, a) ': g1)) ** Interp (Mul ('[] :: [(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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

thin :: Interp (Mul ('(n, a) ': g)) ~> Interp (Mul ('[] :: [(Nat, SYN k)])) Source Github #

(Monoidal k, KnownCtx ('(n, a) ': g1)) => Unmerge ('(n, a) ': g1 :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

unmerge :: (Interp (Mul ('(n, a) ': g1)) ** Interp (Mul ('[] :: [(Nat, SYN k)]))) ~> Interp (Mul (Union ('(n, a) ': g1) ('[] :: [(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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

merge :: Interp (Mul (Union ('(n, a) ': g1) ('(m, b) ': g2))) ~> (Interp (Mul ('(n, a) ': g1)) ** Interp (Mul ('(m, b) ': g2))) 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

thin :: Interp (Mul ('(n, a) ': g)) ~> Interp (Mul ('(m, b) ': h)) 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

unmerge :: (Interp (Mul ('(n, a) ': g1)) ** Interp (Mul ('(m, b) ': g2))) ~> Interp (Mul (Union ('(n, a) ': g1) ('(m, b) ': g2))) Source Github #

(Promonad p, KnownObj a) => RecVars k (TermP p d '['(n, a)] a) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Associated Types

type Vars k (TermP p d '['(n, a)] a) 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

type Vars k (TermP p d '['(n, a)] a) = '['(n, a)]

Methods

recVars :: TermP p d '['(n, a)] a Source Github #

type Vars k (TermP p d '['(n, a)] a) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

type Vars k (TermP p d '['(n, a)] a) = '['(n, a)]

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

withSynOb

Instances

Instances details
Monoidal k => KnownObj ('I :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Syntax

Methods

withSynOb :: (Ob (Interp ('I :: SYN k)) => r) -> r Source Github #

HasTerminalObject k => KnownObj ('Top :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Syntax

Methods

withSynOb :: (Ob (Interp ('Top :: SYN k)) => r) -> r Source Github #

HasInitialObject k => KnownObj ('Zero :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Syntax

Methods

withSynOb :: (Ob (Interp ('Zero :: SYN k)) => r) -> r Source Github #

KnownObj a => KnownObj ('Dn a :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Syntax

Methods

withSynOb :: (Ob (Interp ('Dn a)) => r) -> r Source Github #

(CategoryOf k, Ob a) => KnownObj ('F a :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Syntax

Methods

withSynOb :: (Ob (Interp ('F a)) => r) -> r Source Github #

(Dialogue k, KnownObj a) => KnownObj ('Not a :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Syntax

Methods

withSynOb :: (Ob (Interp ('Not a)) => r) -> r Source Github #

(HasBinaryProducts k, KnownObj a, KnownObj b) => KnownObj (a ':&& b :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Syntax

Methods

withSynOb :: (Ob (Interp (a ':&& b)) => r) -> r Source Github #

(Monoidal k, KnownObj a, KnownObj b) => KnownObj (a ':** b :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Syntax

Methods

withSynOb :: (Ob (Interp (a ':** b)) => r) -> r Source Github #

(Closed k, KnownObj a, KnownObj b) => KnownObj (a ':-> b :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Syntax

Methods

withSynOb :: (Ob (Interp (a ':-> b)) => r) -> r Source Github #

(HasBinaryCoproducts k, KnownObj a, KnownObj b) => KnownObj (a ':|| b :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Syntax

Methods

withSynOb :: (Ob (Interp (a ':|| b)) => r) -> r 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 :** b and binds its two sides, and a tuple of three to six is pairs nested to the left, as a :** b :** c is. At a computation, Up (a :** b) or Up I, a pair or () 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 F (a ** b), binding terms of F a and F b. The morphism and uses of the pattern's variables determine the component objects.

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 F a. In do 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

Instances details
BindPat p (TermP p d g a) () cont r => BindTerm (p :: CAT k) () (TermP p d g a) cont r Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

bindTerm :: 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

bindTerm :: TermP p d g a -> (t -> 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

bindTerm :: TermP p d g a -> ((x, y) -> 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

bindTerm :: TermP p d g a -> ((x, y, z) -> 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

bindTerm :: TermP p d g a -> ((w, x, y, z) -> 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Closed

Methods

(!) :: 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Closed

Methods

(!) :: 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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: TermP p d g ('Not ('Not a)) -> (t -> cont) -> r' Source Github #

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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: TermP p d g a -> (t -> cont) -> r Source Github #

(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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Pattern

Methods

bindPat :: 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Term

Methods

toTerm :: TermP q d' g' a' -> TermP p d g a 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 rec block, whose continuation is its return.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: TermP p d g a -> (t -> Ret tt cont) -> r Source Github #

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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

bindTerm :: TermP p d g a -> ((v, w, x, y, z) -> 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

bindTerm :: TermP p d g a -> ((u, v, w, x, y, z) -> cont) -> r Source Github #

TupleProfunctor (TermP p d g a ': ts) (p :: CAT k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

(Promonad p, KnownObj a) => RecVars k (TermP p d '['(n, a)] a) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Associated Types

type Vars k (TermP p d '['(n, a)] a) 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

type Vars k (TermP p d '['(n, a)] a) = '['(n, a)]

Methods

recVars :: TermP p d '['(n, a)] a Source Github #

t' ~ TermP p d' g a => AnyDepth (TermP p d g a) t' Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

type Vars k (TermP p d '['(n, a)] a) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

type Vars k (TermP p d '['(n, a)] a) = '['(n, a)]

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

toTerm

Instances

Instances details
(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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Term

Methods

toTerm :: () -> TermP p d g a Source Github #

t ~ TermP p d g a => ToTerm (p :: CAT k) t d (g :: Ctx k) (a :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Term

Methods

toTerm :: t -> TermP p d g a 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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Term

Methods

toTerm :: (x, y) -> TermP p d g a Source Github #

(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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Term

Methods

toTerm :: q x y -> TermP p d g a 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Term

Methods

toTerm :: (x, y, z) -> TermP p d g a 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Term

Methods

toTerm :: (w, x, y, z) -> TermP p d g a 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Term

Methods

toTerm :: (v, w, x, y, z) -> TermP p d g a 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Term

Methods

toTerm :: TermP q d' g' a' -> TermP p d g a 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Term

Methods

toTerm :: (u, v, w, x, y, z) -> TermP p d g a 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 #

toSMC with both boundary objects embedded by F. The surrounding morphism type determines the input and output objects, so their type applications can be omitted. Use toSMC when a boundary needs other syntax, such as a function or computation type.

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 #

Lift an arrow onto a term or tuple of terms, with its result embedded by F. The result object is inferred from the arrow. Use lift for composite result syntax.

(-<) :: 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 #

Arrow application, mirroring f -< x in Haskell's arrow notation. This is infix liftF: the input may be a term or tuple, and the result is embedded by F. The Arrows extension must be disabled, since it reserves this symbol.

returnA :: forall {k} p (a :: k). (Promonad p, Ob a) => p a a Source Github #

The identity morphism, named as in Haskell's arrow notation. An alias for id; returnA -< x embeds the input by F.

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 Up a is the computation of the pair at a. 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

tuple

Instances

Instances details
(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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Pattern

Methods

tuple :: forall (d :: Nat). () -> TermP p d g a Source Github #

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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Pattern

Methods

tuple :: forall (d :: Nat). t -> TermP p d g a Source Github #

(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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Pattern

Methods

tuple :: forall (d :: Nat). (x, y) -> TermP p d g a Source Github #

(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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Pattern

Methods

tuple :: forall (d :: Nat). (x, y) -> TermP p d g ('Not ('Not a)) Source Github #

BuildTuple p ((x, y), z) g a => BuildTuple (p :: CAT k) (x, y, z) (g :: Ctx k) (a :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Pattern

Methods

tuple :: forall (d :: Nat). (x, y, z) -> TermP p d g a 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Pattern

Methods

tuple :: forall (d :: Nat). (w, x, y, z) -> TermP p d g a 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Pattern

Methods

tuple :: forall (d :: Nat). (v, w, x, y, z) -> TermP p d g a 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Pattern

Methods

tuple :: forall (d :: Nat). (u, v, w, x, y, z) -> TermP p d g a 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 #

The same morphism at another type expression for the same object, and at any depth: between F (a ** b) and F a :** F b, say, so that a pattern can take it apart, or between a type and its Dn. The polarity may change, the morphism does not.

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.

Methods

(!) :: f -> x -> r infixl 8 Source Github #

Instances

Instances details
(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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Closed

Methods

(!) :: 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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Closed

Methods

(!) :: 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 Not a consumes an a: 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 Not a, consumes one; cut, or t |> k, is the two meeting, a Command, a term of Not I; and cont 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: Not a is negative, everything else positive. A term of a negative type is given its consumer, so binding an output of a positive type a with cont gives Up a = Not (Not a), a computation that will produce an 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 Dn (Up a) instead of running it. Patterns and tuples at a computation are described under Patterns.

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 I (annihilate). 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 Dual a = a ~~> r it is the continuation passing type (a -> r) -> r.

type Consumer (d :: Nat) (g :: Ctx k) (a :: SYN k) = Term d g ('Not a) Source Github #

type Command (d :: Nat) (g :: Ctx k) = Term d g ('Not ('I :: SYN k)) Source Github #

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 Not a: it receives an a 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 Not a in its own right, the a is the consumer of an output and cont is μ, Haskell's callCC: a computation Up b receives the consumer of its result, cont \k -> … |> k; a par b :## c receives a consumer for each side, cont \(kb, kc) -> …; and a command, Not I, receives nothing, cont \() -> …. 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 #

A value as the computation that produces it: double negation introduction, and the return of a do block in the continuation reading. It also reads as a producer of a handed over as a consumer of Not a. The value can be given as a Tuple of terms, built by the type expected.

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 #

Store a term of a negative type as a value: the same morphism at the positive type Dn n, which a bind names instead of running. This is call by push value's thunk, recast to Dn.

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 #

A stored term at its negative type again, where a bind runs it. This is call by push value's force, recast from Dn.

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, delta (f -< i) j is the entry of f 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 #

The Kronecker delta: the scalar that says two wires of an index type carry the same value. It is the cap of the Frobenius algebra, counit . mappend.

(*^) :: 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 #

A term multiplied by a scalar on its left. The scalar's type interprets to Unit, including both I and F Unit. At I it is the product of two scalars.

(^*) :: 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.

class Interp s ~ Interp (a ':|| b) => Sum (s :: SYN k) (a :: SYN k) (b :: SYN k) Source Github #

A sum with components a and b: either a :|| b or a coproduct embedded by F.

Instances

Instances details
s ~ (a ':|| b) => Sum (s :: SYN k) (a :: SYN k) (b :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Additive

(z ~ (x || y), a ~ 'F x, b ~ 'F y) => Sum ('F z :: SYN k) (a :: SYN k) (b :: SYN k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Additive

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.

Minimal complete definition

ctxCase, withCtxOb

Instances

Instances details
KnownCtx ('[] :: [(Nat, SYN k)]) Source Github # 
Instance details

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 # 
Instance details

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.

Equations

Union ('[] :: [(Nat, SYN k)]) (g2 :: Ctx k) = g2 
Union (g1 :: Ctx k) ('[] :: [(Nat, SYN k)]) = g1 
Union ('(n, a) ': g1 :: [(Nat, SYN k)]) ('(m, b) ': g2 :: [(Nat, SYN k)]) = UnionBy (CmpNat n m) ('(n, a) ': g1) ('(m, b) ': g2) 

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

merge

Instances

Instances details
(Monoidal k, KnownCtx g2) => Merge ('[] :: [(Nat, SYN k)]) (g2 :: Ctx k) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

merge :: Interp (Mul (Union ('[] :: [(Nat, SYN k)]) g2)) ~> (Interp (Mul ('[] :: [(Nat, SYN k)])) ** Interp (Mul g2)) Source Github #

(Monoidal k, KnownCtx ('(n, a) ': g1)) => Merge ('(n, a) ': g1 :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

merge :: Interp (Mul (Union ('(n, a) ': g1) ('[] :: [(Nat, SYN k)]))) ~> (Interp (Mul ('(n, a) ': g1)) ** Interp (Mul ('[] :: [(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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

merge :: Interp (Mul (Union ('(n, a) ': g1) ('(m, b) ': g2))) ~> (Interp (Mul ('(n, a) ': g1)) ** Interp (Mul ('(m, b) ': g2))) 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

thin

Instances

Instances details
Monoidal k => Thin ('[] :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

thin :: Interp (Mul ('[] :: [(Nat, SYN k)])) ~> Interp (Mul ('[] :: [(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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

thin :: Interp (Mul ('(n, a) ': g)) ~> Interp (Mul ('[] :: [(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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

thin :: Interp (Mul ('(n, a) ': g)) ~> Interp (Mul ('(m, b) ': h)) 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

bindVar

Instances

Instances details
(Monoidal k, Comonoid (Interp a), KnownObj a) => BindVar n (a :: SYN k) ('[] :: [(Nat, SYN k)]) ('[] :: [(Nat, SYN k)]) Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

bindVar :: (Interp (Mul ('[] :: [(Nat, SYN k)])) ** Interp a) ~> Interp (Mul ('[] :: [(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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Context

Methods

bindVar :: (Interp (Mul r) ** Interp a) ~> Interp (Mul ('(m, b) ': g)) Source Github #

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.

fail :: a Source Github #

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

Instances details
(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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: (x, y) -> (t -> cont) -> r Source Github #

(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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: q a b -> (t -> cont) -> r Source Github #

Bind p ((x, y), z) t cont r => Bind (p :: CAT k) (x, y, z) t cont r Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: (x, y, z) -> (t -> cont) -> r Source Github #

Bind p ((w, x, y), z) t cont r => Bind (p :: CAT k) (w, x, y, z) t cont r Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: (w, x, y, z) -> (t -> cont) -> r Source Github #

(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 do block after a rec block, which traces it. The variables of the block that the block itself uses are fed back, the ones the rest uses are passed on, a variable that both use is copied, and one that neither uses is discarded. The rest gets the variables anew, with the same ids, so that it can use them at its own depth.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: Rec p d t g -> (t' -> cont) -> 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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: TermP p d g ('Not ('Not a)) -> (t -> cont) -> r' Source Github #

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.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: TermP p d g a -> (t -> cont) -> r Source Github #

Bind p ((v, w, x, y), z) t cont r => Bind (p :: CAT k) (v, w, x, y, z) t cont r Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: (v, w, x, y, z) -> (t -> cont) -> r 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 rec block, whose continuation is its return.

Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: TermP p d g a -> (t -> Ret tt cont) -> r Source Github #

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 # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Do

Methods

(>>=) :: (u, v, w, x, y, z) -> (t -> cont) -> r Source Github #

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

bound

Instances

Instances details
(Promonad p, KnownObj a, KnownCtx g, BindPat p (TermP p (n + 1) '['(n, a)] a) t cont (TermP p (n + 1) g' b), BindVar n a g' g) => Binds (p :: CAT k) n (g :: Ctx k) (a :: SYN k) (b :: SYN k) t cont Source Github # 
Instance details

Defined in Proarrow.Tools.SMC.Internal.Pattern

Methods

bound :: (t -> cont) -> p (Interp (Mul g) ** Interp a) (Interp b) Source Github #