Docs / Semantics / Composition / LiftRel

Relations lifted through types and effects

import Linglib.Semantics.Composition.LiftRel · namespace Interpreter

A relation between two families of base domains extends to every type: at the truth values it is equivalence, at a function type it relates functions that take related arguments to related values, and at a computation type it is the relation its effect lifts. Each operation of an effect respects the lifted relations, so every mode does, and the relation is a logical relation between the two structures of the effect-driven grammar: related lexicons give every derivation related values.

Main definitions

TODO

The basic lemma of logical relations is the statement that terms stay inside a substructure, at the product of two structures. The many-sorted layer has neither products nor substructures.

References

Declarations

L49–59

A relation between two families of base domains, at a type.

def Ty.LiftRelL63–70
{B : Type} {D D' : B → Type} (r : (b : B) → D b → D' b → Prop) (a : Ty B) :
Dom D a → Dom D' a → Prop

Built from ,

Used by Eff.DatumRel, Eff.rel_lower, Mode.rel_eval, Application.rel_eval, PredicateModification.rel_eval, EventIdentification.rel_eval, application.isLogicalRel, effectGrammar.isLogicalRel

L72–77

Where the rules of a grammar respect a relation between base domains, every mode over them does.

theorem Mode.rel_evalL179–209
{B : Type} {D D' : B → Type} {r : (b : B) → D b → D' b → Prop} {G : ManySorted.Language (Ty B)} [M : G.Structure (Ty.Dom D)] [M' : G.Structure (Ty.Dom D')] (hG : ∀ {l r' u : Ty B} (b : G.Binary l r' u), Relator.LiftFun (Ty.LiftRel r l) (Relator.LiftFun (Ty.LiftRel r r') (Ty.LiftRel r u)) (fun (x : Ty.Dom D l) (y : Ty.Dom D r') => ManySorted.Language.Structure.funMap b (x, y)) fun (x : Ty.Dom D' l) (y : Ty.Dom D' r') => ManySorted.Language.Structure.funMap b (x, y)) {l r' u : Ty B} (m : Mode G.Binary l r' u) :
Relator.LiftFun (Ty.LiftRel r l) (Relator.LiftFun (Ty.LiftRel r r') (Ty.LiftRel r u)) (eval D m) (eval D' m)

Built from

L233–239

A logical relation between two structures for a grammar, lifted from a relation between base domains, is one between the two structures of the effect-driven grammar over it, so related lexicons give every derivation related values.

theorem effectGrammar.isLogicalRelL241–248
{B : Type} {D D' : B → Type} {r : (b : B) → D b → D' b → Prop} {G : ManySorted.Language (Ty B)} [M : G.Structure (Ty.Dom D)] [M' : G.Structure (Ty.Dom D')] (h : M.IsLogicalRel M' (Ty.LiftRel r)) :

Built from