Documentation

Determinize.Frontend.Infer

Affinity inference #

infer fills the omitted sample affinities of a resolved program with the greatest affinities that make it typable. It works in phases:

  1. Generation (generate): give every node a type over type variables and affinity variables, and record every use of subsumption as a cast in a Draft. The casts are the subtyping constraints (Draft.relations). A sample site gets a fresh affinity variable, or its requested affinity; an operand that the typing rules require to be G gets general.
  2. Shapes (unify): unify the shapes of the two sides of every constraint. Structural subtyping relates only types of the same shape.
  3. Decoration (UType.decorate): replace every type variable α by its most general shape, with the affinity variable leaf α position at each float. The remaining shape variables are unconstrained; read-back sets them to unit. Type variables with equal shapes still get different affinity variables.
  4. Decomposition (decompose): split every constraint between decorated types into atomic constraints between affinities: covariant, except in function arguments.
  5. Affinities (solveAffinities): the greatest solution of the atomic constraints.
  6. Read-back (Draft.program, Solution.type): the input with every site annotated by the solution, and its type.

Spec/Inference.lean states what infer guarantees. Every definition here is total, so that the proofs can unfold them.

Affinity variables: one for each float created during generation, and one for each float in the decorated shape of a type variable.

Instances For
    Equations
    • One or more equations did not get rendered due to their size.
    Instances For

      Types during inference, over type variables and affinity terms.

      Instances For
        Equations
        • One or more equations did not get rendered due to their size.
        Instances For

          The program with a type for every node, and a cast wherever its typing uses subsumption.

          Instances For
            Equations
            Instances For
              @[irreducible]

              The subtyping constraints: the type of every cast body is a subtype of the cast type.

              Equations
              Instances For

                Generation #

                @[reducible, inline]

                Generation draws type and affinity variables from one counter. It fails only on an unbound variable.

                Equations
                Instances For
                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For

                    Phase 1: the draft of e in the context Γ.

                    Equations
                    • One or more equations did not get rendered due to their size.
                    Instances For

                      Read-back #

                      The annotated node for the input node e with the given children, sampling at affinity m if it is a sample site.

                      Equations
                      Instances For
                        @[irreducible]

                        The input with every sample site annotated by the affinity of its type under ρ.

                        Equations
                        Instances For

                          Inference #

                          The outcome of phases 1 to 5: the draft, the most general shapes of its type variables, and the greatest solution of the affinity constraints.

                          Instances For

                            The type of a draft type in the solution. The shape variables left after decoration are unconstrained and become unit.

                            Equations
                            Instances For

                              Phases 1 to 5. Fails on an unbound variable, if the shapes have no unifier, or if the affinity constraints have no solution.

                              Equations
                              • One or more equations did not get rendered due to their size.
                              Instances For