Docs / Semantics / Composition / PredicateAbstraction

Predicate abstraction

import Linglib.Semantics.Composition.PredicateAbstraction

Heim and Kratzer interpret a constituent relative to an assignment, and the index a moved phrase leaves abstracts over the value the assignment gives it. A language with predicate abstraction is the sum of a language of rules and abstraction over each index, and from a structure for the language it has one whose values depend on an assignment: sisters combine at one assignment, and an abstract is a function of the value the assignment is modified to give the index. A logical relation between two structures for the language lifts to the two, and raising a constituent of the bound type changes nothing.

Main definitions

References

Declarations

Abstraction over indices typed by Γ, as a language over the types.

@[reducible] def Interpreter.abstractionL48–50
{B : Type} (Γ : ℕ → Ty B) :

Built from

Used by Interpreter.abstraction.index, ManySorted.Language.withAbstraction, Interpreter.abstraction.structure

Used in Semantics/Composition/Extension

A language of rules with predicate abstraction over indices typed by Γ.

@[reducible, inline] abbrev ManySorted.Language.withAbstractionL64–67
{B : Type} (L : Language (Interpreter.Ty B)) (Γ : ℕ → Interpreter.Ty B) :

Built from

Used by ManySorted.Language.withAbstraction.structure, ManySorted.Language.withAbstraction.binders, ManySorted.Language.withAbstraction.realize_bind, ManySorted.Language.withAbstraction.realize_raise, Interpreter.withAbstraction

Used in Semantics/Composition/Interpret, Champollion2016b, HeimKratzer1998, Ogihara1989, Percus2000 and 1 more

Assignments A of values in the domains D to indices typed by Γ: the value an assignment gives an index, an assignment modified at an index, and the value of function type that a function is.

structure Interpreter.AssignmentsL73–82
{B : Type} (A : Type) (D : Ty B → Type) (Γ : ℕ → Ty B) :
  • get : A → (n : ℕ) → D (Γ n)

    The value an assignment gives an index.

  • set : A → (n : ℕ) → D (Γ n) → A

    An assignment modified to give an index a value.

  • lam {a b : Ty B} : (D a → D b) → D (a.fn b)

    The value of function type that a function is.

Used by Interpreter.Assignments.total, Interpreter.abstraction.structure, Interpreter.abstraction.funMap_index, ManySorted.Language.withAbstraction.structure, ManySorted.Language.withAbstraction.isLogicalRel, ManySorted.Language.withAbstraction.realize_bind, ManySorted.Language.withAbstraction.realize_raise

Used in Semantics/Composition/CallByValue, HeimKratzer1998

L96–100

The values of a language with predicate abstraction relative to an assignment: the rules of the language apply at one assignment, and the abstract over an index is the function of the value the assignment is modified to give it.

@[instance_reducible] def ManySorted.Language.withAbstraction.structureL117–122
{B : Type} {Γ : ℕ → Interpreter.Ty B} {L : Language (Interpreter.Ty B)} {A : Type} {D : Interpreter.Ty B → Type} [M : L.Structure D] (E : Interpreter.Assignments A D Γ) :
(L.withAbstraction Γ).Structure fun (a : Interpreter.Ty B) => A → D a

Built from , ,

Used by ManySorted.Language.withAbstraction.isLogicalRel, ManySorted.Language.withAbstraction.realize_bind, ManySorted.Language.withAbstraction.realize_raise

Used in Semantics/Composition/Interpret, HeimKratzer1998

A logical relation between two structures for a language, with a relation between their assignments that modification and abstraction respect, is a logical relation between the two structures relative to assignments.

theorem ManySorted.Language.withAbstraction.isLogicalRelL124–139
{B : Type} {Γ : ℕ → Interpreter.Ty B} {L : Language (Interpreter.Ty B)} {A A' : Type} {D D' : Interpreter.Ty B → Type} [M : L.Structure D] [M' : L.Structure D'] {R : (a : Interpreter.Ty B) → D a → D' a → Prop} (h : M.IsLogicalRel M' R) {E : Interpreter.Assignments A D Γ} {E' : Interpreter.Assignments A' D' Γ} (Q : A → A' → Prop) (hset : ∀ (g : A) (g' : A') (n : ℕ) (v : D (Γ n)) (v' : D' (Γ n)), Q g g' → R (Γ n) v v' → Q (E.set g n v) (E'.set g' n v')) (hlam : ∀ {a b : Interpreter.Ty B} (F : D a → D b) (F' : D' a → D' b), (∀ (v : D a) (v' : D' a), R a v v' → R b (F v) (F' v')) → R (a.fn b) (E.lam F) (E'.lam F')) :
(«structure» E).IsLogicalRel («structure» E') fun (a : Interpreter.Ty B) (v : A → D a) (v' : A' → D' a) => ∀ (g : A) (g' : A'), Q g g' → R a (v g) (v' g')

Built from ,

Substitution and raising

A derivation with another substituted for a trace has the value the derivation has at the assignment modified to give the trace's index the value of what is substituted. Raising a constituent of the bound type is therefore β-expansion and changes nothing: scope is taken only where the trace is of another type than what moved.

L152–158

Substitution in a derivation is evaluation at a modified assignment: where each item's substitute has the value the item has once the assignment gives the index n the value val, and the derivation abstracts over no index that is n or that val depends on, the derivation has, with the substitutes for its items, the value it has at the assignment so modified.

theorem ManySorted.Language.withAbstraction.realize_bindL163–200
{B : Type} {Γ : ℕ → Interpreter.Ty B} {L : Language (Interpreter.Ty B)} {A : Type} {D W : Interpreter.Ty B → Type} [M : L.Structure D] (E : Interpreter.Assignments A D Γ) (ρ : {a : Interpreter.Ty B} → W a → A → D a) (θ : {a : Interpreter.Ty B} → W a → (L.withAbstraction Γ).Deriv W a) (n : ℕ) (val : A → D (Γ n)) (hθ : ∀ {a : Interpreter.Ty B} (w : W a) (g : A), Term.realize («structure» E) (fun {s : Interpreter.Ty B} => ρ) (θ w) g = ρ w (E.set g n (val g))) (hcomm : ∀ (g : A) (m : ℕ) (u : D (Γ m)) (v : D (Γ n)), m ≠ n → E.set (E.set g n v) m u = E.set (E.set g m u) n v) {σ : Signature (Interpreter.Ty B)} (d : (L.withAbstraction Γ).Term W σ) (hd : ∀ m ∈ binders d, m ≠ n ∧ ∀ (g : A) (u : D (Γ m)), val (E.set g m u) = val g) (g : A) :
(Term.realize («structure» E) (fun {s : Interpreter.Ty B} => ρ) (d.bind fun {s : Interpreter.Ty B} => θ)).app g = (Term.realize («structure» E) (fun {s : Interpreter.Ty B} => ρ) d).app (E.set g n (val g))

Built from , , ,

Raising is β-expansion: where a rule applies an abstract to a value of the bound type by substitution, a constituent of that type combined with the abstract over the index of its traces has the value of the derivation with the constituent in their place.

theorem ManySorted.Language.withAbstraction.realize_raiseL202–224
{B : Type} {Γ : ℕ → Interpreter.Ty B} {L : Language (Interpreter.Ty B)} {A : Type} {D W : Interpreter.Ty B → Type} [M : L.Structure D] (E : Interpreter.Assignments A D Γ) (ρ : {a : Interpreter.Ty B} → W a → A → D a) (θ : {a : Interpreter.Ty B} → W a → (L.withAbstraction Γ).Deriv W a) (n : ℕ) {b : Interpreter.Ty B} (ba : L.Binary (Γ n) ((Γ n).fn b) b) (hβ : ∀ (v : D (Γ n)) (F : D (Γ n) → D b), Structure.funMap ba (v, E.lam F) = F v) (a : (L.withAbstraction Γ).Deriv W (Γ n)) (hθ : ∀ {c : Interpreter.Ty B} (w : W c) (g : A), Term.realize («structure» E) (fun {s : Interpreter.Ty B} => ρ) (θ w) g = ρ w (E.set g n (Term.realize («structure» E) (fun {s : Interpreter.Ty B} => ρ) a g))) (hcomm : ∀ (g : A) (m : ℕ) (u : D (Γ m)) (v : D (Γ n)), m ≠ n → E.set (E.set g n v) m u = E.set (E.set g m u) n v) (d : (L.withAbstraction Γ).Deriv W b) (hd : ∀ m ∈ binders d, m ≠ n ∧ ∀ (g : A) (u : D (Γ m)), Term.realize («structure» E) (fun {s : Interpreter.Ty B} => ρ) a (E.set g m u) = Term.realize («structure» E) (fun {s : Interpreter.Ty B} => ρ) a g) :

Built from , , ,

An interpreter with predicate abstraction: an index admits abstraction over it, and any other node what the interpreter admits.

def Interpreter.withAbstractionL234–241
{B : Type} {L : ManySorted.Language (Ty B)} (I : Interpreter L Node) (Γ : ℕ → Ty B) :

The definition is too large to print here; read it in the source.

Built from

Used in Semantics/Composition/Extension, Semantics/Composition/Interpret, Barker2027, Champollion2016b, HeimKratzer1998 and 2 more