No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
In the paper
- page 140 of the paper of lax-157538, Transducers
Definition
A regular term (Definition C.5.3 of Transducers) is an expression built by applying combinators to atomic terms. The atomic terms are the identity , the projections and , the co-projections and , distributivity , the list constructor and deconstructor , reverse , concatenation , split , and group prefix multiplication for a group whose underlying set is a finite type. The combinators are composition, pairing , co-pairing , and map . Every regular term defines a type-to-type function; Theorem C.5.4 relates the functions so defined to the regular functions under string representation.
Lean source view on GitHub
| 1 | import Mathlib.Algebra.Group.Defs |
| 2 | import Mathlib.Data.Finite.Defs |
| 3 | import Lax709149.Types |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Regular terms |
| 8 | type: definition |
| 9 | --- |
| 10 | A *regular term* (Definition C.5.3 of *Transducers*) is an expression built by |
| 11 | applying combinators to atomic terms. The atomic terms are the identity |
| 12 | , the projections and , the |
| 13 | co-projections and , distributivity |
| 14 | , the list constructor |
| 15 | and deconstructor |
| 16 | , reverse , concatenation |
| 17 | , split , and group |
| 18 | prefix multiplication for a group whose underlying set is a |
| 19 | finite type. The combinators are composition, pairing , |
| 20 | co-pairing , and map . |
| 21 | Every regular term defines a type-to-type function; Theorem C.5.4 relates the |
| 22 | functions so defined to the regular functions under string representation. |
| 23 | |
| 24 | # Formalization notes |
| 25 | |
| 26 | `RegTerm A B` is the syntax, indexed by the source and target types, and |
| 27 | `RegTerm.eval` the semantics. Split cuts its input at the entries from `B`, and |
| 28 | group prefix multiplication maps a list to its prefix products; its constructor |
| 29 | carries the group structure on the elements of `G` and the finiteness of that |
| 30 | type, which the book requires and which the regularity of its semantics needs. |
| 31 | `IsRegularTermFun f` says that some term evaluates to `f`. |
| 32 | -/ |
| 33 | |
| 34 | namespace Lax709149.RegularTerms |
| 35 | |
| 36 | open Lax709149.Types |
| 37 | |
| 38 | /-- The prefix products of a list: the `i`-th entry of the output is the product of |
| 39 | the first `i` entries of the input. -/ |
| 40 | def prefixProd {M : Type} [Monoid M] (l : List M) : List M := (l.scanl (· * ·) 1).tail |
| 41 | |
| 42 | /-- Split: the input is cut at its entries from `B`; the output is the block of |
| 43 | entries from `A` before the first cut, and the cutting entries each with the block |
| 44 | that follows it. -/ |
| 45 | def splitList {A B : Type} : List (A ⊕ B) → List A × List (B × List A) |
| 46 | | [] => ([], []) |
| 47 | | Sum.inl a :: l => ((splitList l).1.cons a, (splitList l).2) |
| 48 | | Sum.inr b :: l => ([], (b, (splitList l).1) :: (splitList l).2) |
| 49 | |
| 50 | /-- The syntax of regular terms: atomic terms and combinators. -/ |
| 51 | inductive RegTerm : Ty → Ty → Type |
| 52 | /-- Identity `A → A`. -/ |
| 53 | | id (A : Ty) : RegTerm A A |
| 54 | /-- First projection `A × B → A`. -/ |
| 55 | | fst (A B : Ty) : RegTerm (.prod A B) A |
| 56 | /-- Second projection `A × B → B`. -/ |
| 57 | | snd (A B : Ty) : RegTerm (.prod A B) B |
| 58 | /-- Left co-projection `A → A + B`. -/ |
| 59 | | inl (A B : Ty) : RegTerm A (.sum A B) |
| 60 | /-- Right co-projection `B → A + B`. -/ |
| 61 | | inr (A B : Ty) : RegTerm B (.sum A B) |
| 62 | /-- Distributivity `A × (B + C) → (A × B) + (A × C)`. -/ |
| 63 | | distr (A B C : Ty) : RegTerm (.prod A (.sum B C)) (.sum (.prod A B) (.prod A C)) |
| 64 | /-- The list constructor `1 + A × A* → A*`. -/ |
| 65 | | cons (A : Ty) : RegTerm (.sum .one (.prod A (.list A))) (.list A) |
| 66 | /-- The list deconstructor `A* → 1 + A × A*`. -/ |
| 67 | | uncons (A : Ty) : RegTerm (.list A) (.sum .one (.prod A (.list A))) |
| 68 | /-- Reverse `A* → A*`. -/ |
| 69 | | reverse (A : Ty) : RegTerm (.list A) (.list A) |
| 70 | /-- Concatenation `A** → A*`. -/ |
| 71 | | concat (A : Ty) : RegTerm (.list (.list A)) (.list A) |
| 72 | /-- Split `(A + B)* → A* × (B × A*)*`. -/ |
| 73 | | split (A B : Ty) : RegTerm (.list (.sum A B)) (.prod (.list A) (.list (.prod B (.list A)))) |
| 74 | /-- Group prefix multiplication `G* → G*`, for a group on a finite type. -/ |
| 75 | | pref (G : Ty) (grp : Group G.Elt) (hfin : Finite G.Elt) : RegTerm (.list G) (.list G) |
| 76 | /-- Composition. -/ |
| 77 | | comp {A B C : Ty} : RegTerm A B → RegTerm B C → RegTerm A C |
| 78 | /-- Pairing. -/ |
| 79 | | pair {A B C : Ty} : RegTerm A B → RegTerm A C → RegTerm A (.prod B C) |
| 80 | /-- Co-pairing. -/ |
| 81 | | copair {A B C : Ty} : RegTerm A C → RegTerm B C → RegTerm (.sum A B) C |
| 82 | /-- Map. -/ |
| 83 | | map {A B : Ty} : RegTerm A B → RegTerm (.list A) (.list B) |
| 84 | |
| 85 | /-- The function defined by a regular term. -/ |
| 86 | def RegTerm.eval : {A B : Ty} → RegTerm A B → A.Elt → B.Elt |
| 87 | | _, _, .id _ => fun x => x |
| 88 | | _, _, .fst _ _ => fun x => x.1 |
| 89 | | _, _, .snd _ _ => fun x => x.2 |
| 90 | | _, _, .inl _ _ => fun x => Sum.inl x |
| 91 | | _, _, .inr _ _ => fun x => Sum.inr x |
| 92 | | _, _, .distr _ _ _ => fun x => |
| 93 | Sum.elim (fun b => Sum.inl (x.1, b)) (fun c => Sum.inr (x.1, c)) x.2 |
| 94 | | _, _, .cons _ => fun x => Sum.elim (fun _ => []) (fun p => p.1 :: p.2) x |
| 95 | | _, _, .uncons _ => fun l => match l with |
| 96 | | [] => Sum.inl () |
| 97 | | a :: l' => Sum.inr (a, l') |
| 98 | | _, _, .reverse _ => fun l => l.reverse |
| 99 | | _, _, .concat _ => fun l => l.flatten |
| 100 | | _, _, .split _ _ => fun l => splitList l |
| 101 | | _, _, .pref _ grp _ => fun l => @prefixProd _ (@Group.toDivisionMonoid _ grp).toMonoid l |
| 102 | | _, _, .comp s t => fun x => t.eval (s.eval x) |
| 103 | | _, _, .pair s t => fun x => (s.eval x, t.eval x) |
| 104 | | _, _, .copair s t => fun x => Sum.elim s.eval t.eval x |
| 105 | | _, _, .map t => fun l => l.map t.eval |
| 106 | |
| 107 | /-- A type-to-type function is defined by a regular term. -/ |
| 108 | def IsRegularTermFun {A B : Ty} (f : A.Elt → B.Elt) : Prop := ∃ t : RegTerm A B, t.eval = f |
| 109 | |
| 110 | end Lax709149.RegularTerms |
| 111 |
Formalization notes
is the syntax, indexed by the source and target types, and the semantics. Split cuts its input at the entries from , and group prefix multiplication maps a list to its prefix products; its constructor carries the group structure on the elements of and the finiteness of that type, which the book requires and which the regularity of its semantics needs. says that some term evaluates to .
Builds on
Used by
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments