betaFeedback

WorksComputer Science

Matching-Logic-Based Understanding of Polynomial Functors and their Initial/Final Models Revisited

Abstract

Many data types used in programming are initial algebras or final coalgebras of polynomial functors. We show how to specify them uniformly in matching logic, using the representation of polynomial functors as unary container functors X↦∑a:AXB[a]X\mapsto\sum_{a:A}X^{B[a]}. For each container functor, we give a matching logic theory of its initial algebra and one of its final coalgebra. Besides the no-junk and no-confusion axioms and their duals, these theories include axioms about the elements that represent functions, for the initial algebra, and a bisimilarity axiom and a realisation axiom, for the final coalgebra; the existence axioms use free set variables to range over all subsets of a model. We prove that, in every model, the algebra extracted from the model is an initial algebra (a W-type) and the extracted coalgebra is a final coalgebra (an M-type) of the container extracted from the model, i.e., the one given by the model's interpretation of the shapes and positions, and that such models exist. So the data types are captured relative to the interpretation of the sorts of shapes and positions, and absolutely whenever these sorts are fixed by auxiliary specifications, which we show for finite sets, products, dependent sums, and (co)inductive sorts built from them. We derive the induction, coinduction, and bisimulation principles as theorems, and illustrate the approach on lists and on Moore machines. This paper revises and substantially extends a paper published in EPTCS 389 (FROM 2023): several axioms are corrected, and the adequacy and satisfiability proofs are new.

Note on this version. This paper is a revised version of [15] (arXiv:2309.13798v1), which had a WIP status at that time. Several axioms and proof principles were corrected, the adequacy and satisfiability results were proved, and the case studies were completed. Appendix C lists the changes.

Introduction

It is known that many data types used in programming are defined as initial algebra or final coalgebra for an appropriate functor F:C→CF : \mathcal{C} \to\mathcal{C}, where C\mathcal{C} is a category of data types. In this paper we assume that C\mathcal{C} is the category of sets (see, e.g., [2]). If FF is bicontinuous, i.e., it preserves the colimits of ω\omega-sequences and the limits of ωop\omega^{op}-sequences, then the initial algebra (model) is obtained via colimit of the ω\omega-sequence

0→ ! F0→F ! FF0=F20→F2! F30→F3! ⋯(1)\mathbf{0} \xrightarrow{\ !\ } F\mathbf{0} \xrightarrow{F\,!\ } F F\mathbf{0}=F^2\mathbf{0} \xrightarrow{F^2!\ } F^3\mathbf{0} \xrightarrow{F^3!\ } \cdots \tag*{(1)}

where 0\mathbf{0} is the initial object in C\mathcal{C}, and 0→ ! X\mathbf{0} \xrightarrow{\ !\ } X is the unique arrow from the initial object [2], and the final coalgebra (model) is the limit of the ωop\omega^{op}-sequence

1← ! F1←F ! FF1=F21←F2! F31←F3! ⋯(2)\mathbf{1} \xleftarrow{\ !\ } F\mathbf{1} \xleftarrow{F\,!\ } F F\mathbf{1}=F^2\mathbf{1} \xleftarrow{F^2!\ } F^3\mathbf{1} \xleftarrow{F^3!\ } \cdots \tag*{(2)}

where 1\mathbf{1} is the final object in C\mathcal{C}, and 1← ! X\mathbf{1} \xleftarrow{\ !\ } X is the unique arrow to the final object [2].

This is a nice abstract framework, but, as we know, the evil is hidden in details. How the elements of the initial and final models look like for various concrete functors? How could they be handled in practice?

A possible answer can be obtained by capturing these objects in Matching Logic (ML), the logical foundation of the K Framework, where the program languages and the properties of their programs can be specified in a uniform way (see, e.g., [16, 10, 17, 8, 14]). First steps are done in [7], where the initial algebra semantics is captured in ML (see [9] for the journal version, which also derives induction and iteration principles), and in [8], where it is shown how examples of inductive/coinductive data types are fully specified in ML. Data types are usually parametric: lists depend on a set of elements, and, more generally, the data types considered in this paper depend on a set of shapes and a family of sets of positions (§ 2). We write DT(P)DT(P) for a data type with parameter sets PP, which are represented in ML by parameter sorts. We say that ML captures a (inductive/coinductive) data type DT(P)DT(P) if there is an ML theory ThML(DT)\mathrm{Th}^{\mathrm{ML}}(DT) such that:

  • from each ThML(DT)\mathrm{Th}^{\mathrm{ML}}(DT)-model MM we may extract a structure α(M)\alpha(M) that is isomorphic to DT(PM)DT(P_M), where PMP_M is the interpretation of the parameter sorts in MM, and

  • the deduction principles considered here for DTDT, namely induction for initial algebras, coinduction for final coalgebras, and the bisimulation principle for equality, can be expressed as theorems within ML using its proof system.

Other principles, such as iteration and primitive recursion, are outside the scope of this paper (see the Conclusion). In this paper, the first condition is established by the adequacy theorems, which are semantic statements about all models, and the second by derivations in the ML proof system; § 5.1 classifies all the results in this way. If, moreover, the theory captures the parameters themselves, i.e., PM≅PP_M \cong P in every model (e.g., for finite or inductively defined sets), then α(M)\alpha(M) is isomorphic to DT(P)DT(P) in every model. Without such axioms, a model may interpret the parameter sorts differently: for a constant functor with one shape and no positions, a model with two shapes yields a two-element initial algebra.

In this paper, we investigate how data types specified as initial FF-algebras or as final FF-coalgebras, where FF is a polynomial functor, can be captured in ML. The term “polynomial functor” is used in the literature for two different classes of functors:

  1. the classical polynomial functors (see, e.g., [18]): the smallest class of functors that includes the constant and the identity functors and is closed under sum, product, and exponentiation by a constant object;

  2. the (unary) container functors (see, e.g., [1, 3]): the functors of the form X↦∑a:AXB[a]X \mapsto\sum_{a:A} X^{B[a]}, where a:A→B[a]a:A \to B[a] is an AA-indexed family.

Every classical polynomial functor is naturally isomorphic to a container functor (§ 2.1). In this paper, polynomial functor means polynomial in the container sense, i.e., a unary container functor. In particular, everything we say applies to the classical polynomial functors.

The constant and the identity functors, together with their initial and final models, can be easily captured in ML. Moreover, if we exclude the exponent functor, then the initial algebra can be captured using the approach similar to that from [7]. The exponent functor complicates things. A possible approach for the classical definition is as follows: supposing that we have captured F1XF_1 X and F2XF_2 X by the ML theories (specifications) SPEC⁡(F1X)\operatorname{SPEC}(F_1 X) and resp. SPEC⁡(F2X)\operatorname{SPEC}(F_2 X), then use these specifications to build SPEC⁡(F1Xop⁡F2X)\operatorname{SPEC}(F_1 X\mathbin{\operatorname{op}} F_2 X), i.e., to obtain something like

SPEC⁡(F1Xop⁡F2X)=SPEC⁡(F1X)op⁡‾SPEC⁡(F2X)\operatorname{SPEC}(F_1 X\mathbin{\operatorname{op}} F_2 X)=\operatorname{SPEC}(F_1 X)\mathbin{\overline{\operatorname{op}}}\operatorname{SPEC}(F_2 X)

where op⁡‾\overline{\operatorname{op}} reflects opop to the level of ML specifications, and is yet to be defined. In order to accomplish that, we need a “uniform standard” definition for the specifications SPEC⁡(FX)\operatorname{SPEC}(F X).

The container functors already have a uniform standard definition, and therefore they are more tempting for our investigation. The results of this paper show that:

  • it is possible to specify unary container functors, together with their initial algebras and final coalgebras, as well-formed ML theories (Definition 4.1), which are satisfiable (Theorem B.2), for arbitrary unary containers, including the boundary cases of empty shape and position sets, empty exponent domains, infinite position sets, and empty initial algebras with non-empty final coalgebras (Section 4.9);

  • the specification of the initial algebra captures it (a semantic result): for every model MM, the algebra αμ(M)\alpha_\mu(M) extracted from MM is an initial algebra, isomorphic to the W-type of the shapes and positions of MM (Theorem 4.4); such models exist (Proposition 4.6);

  • the specification of the final coalgebra, which includes an axiom identifying bisimilar elements and an axiom ensuring that every behaviour is realised, captures it (a semantic result): for every model MM, the coalgebra αν(M)\alpha_\nu(M) extracted from MM is a final coalgebra, isomorphic to the M-type of the shapes and positions of MM (Theorem 4.15); such models exist (Proposition 4.18);

  • these results depend on how a model interprets the sorts of shapes and positions; when these sorts are given by finite sets, products, dependent sums, or (co)inductive sorts built from them, the isomorphisms hold with the intended shapes and positions in every model (Theorem 4.21); for parameter sets that are meant to be arbitrary, the results are relative to their interpretation;

  • the induction principle, the coinduction principle, and the bisimulation principle are derivable in the ML proof system, from the Knaster–Tarski rule and the axioms;

  • the ML reasoning can be used to understand better the intimate structure of the initial algebra and the final coalgebra.

The approach is instantiated on the lists example, in order to see the relationship with the classical approach of these data types, and on that of Moore machines, in order to see the (constant) exponential functor at work.

The paper is structured as follows. Section 2 recalls the classical polynomial functors and the unary container functors, and shows that the former class is included in the latter. Section 3 briefly recalls the main elements of matching logic, together with the theories of the equality and of the sorts. Section 4 includes the main contribution, showing how the unary container functors and their related concepts can be specified in matching logic. The instantiation of the general approach on the examples of lists and Moore machines are included in Section 5 and Section 6, respectively. The paper ends with some concluding remarks.

Polynomial Functors and Container Functors

This section briefly recalls (co)algebras of functors, the classical polynomial functors, and the container functors, and compares the two classes of functors. We consider only the particular case of the functors defined over the category of sets C\mathsf{C}.

Definition 2.1. [13] Given a functor F:C→CF : \mathsf{C} \to\mathsf{C}, an FF-algebra consists of an object XX in C\mathsf{C} and an arrow α:FX→X\alpha: F X \to X. An algebra morphism (X,α)→(X′,α′)(X,\alpha) \to(X',\alpha') is an arrow h:X→X′h : X \to X' in C\mathsf{C} such that h∘α=α′∘Fhh \circ\alpha= \alpha' \circ F h. An initial algebra for the functor FF is an initial object in the category of FF-algebras and FF-algebra morphisms.

Example 2.2 (Lists). The lists over a set of elements EE can be defined as an LstLst-algebra α:LstX→X\alpha: Lst X \to X for the functor Lst:C→CLst : \mathsf{C} \to\mathsf{C} given by LstX=1+E×XLst X = 1 + E \times X. Usually, such an algebra is defined by a constant

nil:1→Xnil:1 \to X and a binary operation cons:E×X→Xcons:E \times X \to X. The initial LstLst-algebra is isomorphic to the finite lists inductively defined [19] by the grammar

List::=nil∣cons(E,List)List ::= nil \mid cons(E,List)

We use μX.Lst X\mu X.Lst\ X or μLst\mu Lst to denote the initial model of the functor LstLst.

Definition 2.3. [13] Given a functor F:C→CF:\mathcal{C} \to\mathcal{C}, an FF-coalgebra consists of an object XX in C\mathcal{C} and an arrow γ:X→F X\gamma:X \to F\ X. A coalgebra morphism (X,γ)→(X′,γ′)(X,\gamma) \to(X',\gamma') is an arrow h:X→X′h:X \to X' in C\mathcal{C} such that Fh∘γ=γ′∘hFh \circ\gamma= \gamma' \circ h. A final coalgebra for the functor FF is a final object in the category of FF-coalgebras and FF-coalgebra morphisms.

Example 2.4 (Colists). The colists over a set of elements EE can be defined as an LstLst-coalgebra γ:X→Lst X\gamma:X \to Lst\ X, where LstLst is the functor used for lists (see Example 2.2). Usually, such a coalgebra is defined by

  • a total operation .?:X→{1,2}_.? : X \to\{1,2\} such that x.?=if γ(x)=ι1(⋆) then 1 else 2 fix.? = \text{if }\gamma(x)=\iota_1(\star)\text{ then }1\text{ else }2\text{ fi}, where ⋆\star is the unique element of 11, and

  • two partial operations: .hd:X⇀E_.hd:X \rightharpoonup E, and .tl:X⇀X_.tl:X \rightharpoonup X such that x.hd=ex.hd=e and x.tl=x′x.tl=x' iff x.?=2x.?=2 and γ(x)=ι2(⟨e,x′⟩)\gamma(x)=\iota_2(\langle e,x'\rangle).

The final coalgebra is isomorphic to the possible infinite lists coinductively defined by the grammar (LST) [19]. We use νX.Lst X\nu X.Lst\ X or νLst\nu Lst to denote the final model of the functor LstLst.

Example 2.5 (Moore machines). A Moore machine is an M\mathcal{M}-coalgebra α:X→M X\alpha:X \to\mathcal{M}\ X, where M\mathcal{M} is the functor M:X↦O×XI\mathcal{M}:X \mapsto O \times X^I, where II is the set of inputs and OO is the set of outputs. Usually, a Moore machine is defined by an output function out:X→Oout:X \to O and a transition function tr:X→XItr:X \to X^I [18]. The final coalgebra νX.MX\nu X.\mathcal{M}X is isomorphic to (out‾,tr‾):OI∗→O×(OI∗)I(\overline{out},\overline{tr}):O^{I^*} \to O \times(O^{I^*})^I, out‾(f)=f(ϵ)\overline{out}(f)=f(\epsilon), tr‾(f)=g\overline{tr}(f)=g with g(i)(w)=f(⟨i⟩⋅w)g(i)(w)=f(\langle i\rangle\cdot w) for i∈Ii \in I and w∈I∗w \in I^*, where ff is a function f:I∗→Of:I^* \to O, gg a function g:I→OI∗g:I \to O^{I^*}, ϵ\epsilon the empty sequence, and ⋅\cdot the concatenation of sequences.

Definition 2.6. [18] The class of classical polynomial functors is inductively defined as follows:

  • the constant functor AA (where AA is an object in C\mathcal{C}) is a classical polynomial functor;

  • the identity functor IDID is a classical polynomial functor;

  • the sum F1+F2F_1+F_2 of two classical polynomial functors F1F_1 and F2F_2 is a classical polynomial functor;

  • the product F1×F2F_1 \times F_2 of two classical polynomial functors F1F_1 and F2F_2 is a classical polynomial functor; and

  • the exponent FCF^C of a classical polynomial functor FF by an object CC, given by FCX=(FX)CF^C X=(F X)^C, is a classical polynomial functor.

References

  1. [1]Michael Gordon Abbott, Thorsten Altenkirch & Neil Ghani (2005): Containers: Constructing strictly positive types. Theor. Comput. Sci. 342(1), pp. 3–27, doi:10.1016/j.tcs.2005.06.002.DOI
  2. [2]Jiří Adámek (2003): On final coalgebras of continuous functors. Theor. Comput. Sci. 294(1/2), pp. 3–29, doi:10.1016/S0304-3975(01)00240-7.DOI
  3. [3]Thorsten Altenkirch, Neil Ghani, Peter G. Hancock, Conor McBride & Peter Morris (2015): Indexed containers. J. Funct. Program. 25, doi:10.1017/S095679681500009X.DOI
  4. [4]Thorsten Altenkirch & Peter Morris (2009): Indexed Containers. In: Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11-14 August 2009, Los Angeles, CA, USA, IEEE Computer Society, pp. 277–285, doi:10.1109/LICS.2009.33.DOI
  5. [5]Jeremy Avigad, Mario Carneiro & Simon Hudon (2019): Data Types as Quotients of Polynomial Functors. In John Harrison, John O’Leary & Andrew Tolmach, editors: 10th International Conference on Interactive Theorem Proving, ITP 2019, September 9-12, 2019, Portland, OR, USA, LIPIcs 141, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 6:1–6:19, doi:10.4230/LIPIcs.ITP.2019.6.DOI
  6. [6]Xiaohong Chen, Horațiu Cheval, Dorel Lucanu & Grigore Roșu (2026): A matching logic theory of multi-hole contexts. J. Log. Algebraic Methods Program. 151, p. 101151, doi:10.1016/J.JLAMP.2026.101151. Available at https://doi.org/10.1016/j.jlamp.2026.101151.
  7. [7]Xiaohong Chen, Dorel Lucanu & Grigore Roșu (2020): Initial Algebra Semantics in Matching Logic. Technical Report, University of Illinois at Urbana-Champaign. Available at http://hdl.handle.net/2142/107781.
  8. [8]Xiaohong Chen, Dorel Lucanu & Grigore Roșu (2021): Matching logic explained. Journal of Logical and Algebraic Methods in Programming 120, pp. 1–36, doi:10.1016/j.jlamp.2021.100638.DOI
  9. [9]Xiaohong Chen, Dorel Lucanu & Grigore Roșu (2026): A unifying logical foundation for initial algebra semantics and induction. Theor. Comput. Sci. 1077, p. 115981.DOI
  10. [10]Xiaohong Chen & Grigore Roșu (2019): Matching μ-logic. In: Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’19), IEEE, Vancouver, Canada, pp. 1–13, doi:10.1109/LICS.2019.8785675.DOI
  11. [11]Xiaohong Chen & Grigore Roșu (2020): A general approach to define binders using matching logic. Proc. ACM Program. Lang. 4(ICFP), pp. 88:1–88:32, doi:10.1145/3408970.
  12. [12]Herman Geuvers & Erik Poll (2007): Iteration and primitive recursion in categorical terms. In: Reflections on Type Theory, λ-Calculus, and the Mind. Essays Dedicated to Henk Barendregt on the Occasion of his 60th Birthday, Radboud University Nijmegen, pp. 101–114.
  13. [13]Bart Jacobs & Jan Rutten (2012): An introduction to (co)algebra and (co)induction. In Davide Sangiorgi & Jan J. M. M. Rutten, editors: Advanced Topics in Bisimulation and Coinduction, Cambridge tracts in theoretical computer science 52, Cambridge University Press, pp. 38–99. Available at http:// //www.cambridge.org/gb/knowledge/isbn/item6542021.
  14. [14]Zhengyao Lin, Xiaohong Chen, Minh-Thai Trinh, John Wang & Grigore Roşu (2023): Generating Proof Certificates for a Language-Agnostic Deductive Program Verifier. Proc. ACM Program. Lang. 7(OOPSLA1), pp. 56–84, doi:10.1145/3586029.DOI
  15. [15]Dorel Lucanu (2023): Matching-Logic-Based Understanding of Polynomial Functors and their Initial/Final Models. In: Proceedings of the 7th Working Formal Methods Symposium (FROM 2023), EPTCS 389, pp. 41–55, doi:10.4204/EPTCS.389.4.DOI
  16. [16]Grigore Roşu (2017): Matching logic. Logical Methods in Computer Science 13(4), pp. 1–61, doi:10.26338/LMCS-13(4:28)2017.
  17. [17]Grigore Roşu & Xiaohong Chen (2020): Matching logic: the foundation of the K framework (invited talk). In Jasmin Blanchette & Catalin Hritcu, editors: Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2020, New Orleans, LA, USA, January 20-21, 2020, ACM, p. 1, doi:10.1145/3372885.3378574.DOI
  18. [18]Jan J. M. M. Rutten (2000): Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249(1), pp. 3–80, doi:10.1016/S0304-3975(00)00056-6.DOI
  19. [19]Davide Sangiorgi (2012): An Introduction to Bisimulation and Coinduction. Cambridge University Press. A preliminary version of Chapter 2 from which we adapt material can be found at http://www.cs.unibo.it/~sangio/DOC_public/corsoFL.pdf.DOI
  20. [20]Dmitriy Traytel, Andrei Popescu & Jasmin Christian Blanchette (2012): Foundational, Compositional (Co)datatypes for Higher-Order Logic: Category Theory Applied to Theorem Proving. In: Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, June 25-28, 2012, IEEE Computer Society, pp. 596–605, doi:10.1109/LICS.2012.75.DOI

Paper details

vlnc:W_d65thcz9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents