Semântica computacional com Lean

10.1. Falando de árvores sintáticas🔗

namespace Parsing inductive ParseTree (α β : Type) where | ep | leaf (a : α) | branch (b : β) (ts : List (ParseTree α β)) deriving Repr, BEq def ParseTree.toText {α β : Type} [ToString α] [ToString β] : ParseTree α β → String | .ep => "[]" | .leaf a => toString a | .branch b ts => "[." ++ toString b ++ " " ++ " ".intercalate (ts.map toText) ++ "]" instance {α β : Type} [ToString α] [ToString β] : ToString (ParseTree α β) := ⟨ParseTree.toText⟩ def snowWhite : ParseTree String String := .branch "S" [.branch "NP" [.leaf "Snow White"], .branch "VP" [.branch "TV" [.leaf "loved"], .branch "NP" [.leaf "the dwarfs"]]] [.S [.NP Snow White] [.VP [.TV loved] [.NP the dwarfs]]] #eval IO.println snowWhite abbrev Pos := List Nat def pos {α β : Type} (p : ParseTree α β) : List Pos := let rec posFrom {α β : Type} : Nat → List (ParseTree α β) → List Pos | _, [] => [] | i, t :: ts => (pos t).map (i :: ·) ++ posFrom (i + 1) ts match p with | .ep => [[]] | .leaf _ => [[]] | .branch _ ts => [] :: posFrom 0 ts [[], [0], [0, 0], [1], [1, 0], [1, 0, 0], [1, 1], [1, 1, 0]]#eval pos snowWhite def subtree {α β : Type} : ParseTree α β → Pos → ParseTree α β | t, [] => t | .branch _ ts, i :: is => match ts[i]? with | some t => subtree t is | none => .ep | _, _ :: _ => .ep def subtrees {α β : Type} (t : ParseTree α β) : List (ParseTree α β) := (pos t).map (subtree t) [.VP [.TV loved] [.NP the dwarfs]] #eval IO.println (subtree snowWhite [1]) def posPairs {α β : Type} (t : ParseTree α β) : List (Pos × Pos) := (pos t).flatMap fun p => (pos t).map fun q => (p, q) def properDominance {α β : Type} (t : ParseTree α β) : List (Pos × Pos) := (posPairs t).filter fun (p, q) => p ≠ q && p <+: q def dominance {α β : Type} (t : ParseTree α β) : List (Pos × Pos) := (posPairs t).filter fun (p, q) => p <+: q [([], [0]), ([], [0, 0]), ([], [1]), ([], [1, 0]), ([], [1, 0, 0]), ([], [1, 1]), ([], [1, 1, 0]), ([0], [0, 0]), ([1], [1, 0]), ([1], [1, 0, 0]), ([1], [1, 1]), ([1], [1, 1, 0]), ([1, 0], [1, 0, 0]), ([1, 1], [1, 1, 0])]#eval properDominance snowWhite
Exercício★★(imm-dominance)

A posição p domina imediatamente q quando p domina propriamente q e não há posição r, diferente das duas, tal que p domina r e r domina q. Defina immDominance e confira o resultado na árvore snowWhite.

def declaration uses `sorry`immDominance {α β : Type} (t : ParseTree α β) : List (Pos × Pos) := sorry theorem declaration uses `sorry`immDominance_snowWhite : immDominance snowWhite = [([], [0]), ([], [1]), ([0], [0, 0]), ([1], [1, 0]), ([1], [1, 1]), ([1, 0], [1, 0, 0]), ([1, 1], [1, 1, 0])] := ⊢ immDominance snowWhite = [([], [0]), ([], [1]), ([0], [0, 0]), ([1], [1, 0]), ([1], [1, 1]), ([1, 0], [1, 0, 0]), ([1, 1], [1, 1, 0])] All goals completed! 🐙
def sisters : Pos → Pos → Bool | [i], [j] => i != j | i :: is, j :: js => i == j && sisters is js | _, _ => false def sisterhood {α β : Type} (t : ParseTree α β) : List (Pos × Pos) := (posPairs t).filter fun (p, q) => sisters p q [([0], [1]), ([1], [0]), ([1, 0], [1, 1]), ([1, 1], [1, 0])]#eval sisterhood snowWhite def relComp {γ : Type} [BEq γ] (r s : List (γ × γ)) : List (γ × γ) := (r.flatMap fun (x, y) => (s.filter fun (w, _) => y == w).map fun (_, z) => (x, z)).eraseDups def cCommand {α β : Type} (t : ParseTree α β) : List (Pos × Pos) := relComp (sisterhood t) (dominance t) [([], []), ([], [0]), ([], [0, 0]), ([], [1]), ([], [1, 0]), ([], [1, 0, 0]), ([], [1, 1]), ([], [1, 1, 0]), ([0], [0]), ([0], [0, 0]), ([0, 0], [0, 0]), ([1], [1]), ([1], [1, 0]), ([1], [1, 0, 0]), ([1], [1, 1]), ([1], [1, 1, 0]), ([1, 0], [1, 0]), ([1, 0], [1, 0, 0]), ([1, 0, 0], [1, 0, 0]), ([1, 1], [1, 1]), ([1, 1], [1, 1, 0]), ([1, 1, 0], [1, 1, 0])]#eval dominance snowWhite [([0], [1]), ([0], [1, 0]), ([0], [1, 0, 0]), ([0], [1, 1]), ([0], [1, 1, 0]), ([1], [0]), ([1], [0, 0]), ([1, 0], [1, 1]), ([1, 0], [1, 1, 0]), ([1, 1], [1, 0]), ([1, 1], [1, 0, 0])]#eval cCommand snowWhite def branchingPos {α β : Type} (t : ParseTree α β) : List Pos := let ps := pos t ps.filter fun p => ps.contains (p ++ [0]) && ps.contains (p ++ [1]) [[], [1]]#eval branchingPos snowWhite
Dois lemas sobre posições irmãstheorem sisters_length (p r : Pos) (h : sisters p r = true) : p.length = r.length := p:Posr:Posh:sisters p r = true⊢ List.length p = List.length r induction p generalizing r with r:Posh:sisters [] r = true⊢ [].length = List.length r All goals completed! 🐙 i:Natis:List Natih:∀ (r : Pos), sisters is r = true → is.length = List.length rr:Posh:sisters (i :: is) r = true⊢ (i :: is).length = List.length r cases r with i:Natis:List Natih:∀ (r : Pos), sisters is r = true → is.length = List.length rh:sisters (i :: is) [] = true⊢ (i :: is).length = [].length All goals completed! 🐙 i:Natis:List Natih:∀ (r : Pos), sisters is r = true → is.length = List.length rj:Natjs:List Nath:sisters (i :: is) (j :: js) = true⊢ (i :: is).length = (j :: js).length cases is with i:Natj:Natjs:List Natih:∀ (r : Pos), sisters [] r = true → [].length = List.length rh:sisters [i] (j :: js) = true⊢ [i].length = (j :: js).length cases js with i:Natj:Natih:∀ (r : Pos), sisters [] r = true → [].length = List.length rh:sisters [i] [j] = true⊢ [i].length = [j].length All goals completed! 🐙 i:Natj:Natih:∀ (r : Pos), sisters [] r = true → [].length = List.length rk:Natks:List Nath:sisters [i] (j :: k :: ks) = true⊢ [i].length = (j :: k :: ks).length All goals completed! 🐙 i:Natj:Natjs:List Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → (i' :: is').length = List.length rh:sisters (i :: i' :: is') (j :: js) = true⊢ (i :: i' :: is').length = (j :: js).length cases js with i:Natj:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → (i' :: is').length = List.length rh:sisters (i :: i' :: is') [j] = true⊢ (i :: i' :: is').length = [j].length All goals completed! 🐙 i:Natj:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → (i' :: is').length = List.length rk:Natks:List Nath:sisters (i :: i' :: is') (j :: k :: ks) = true⊢ (i :: i' :: is').length = (j :: k :: ks).length i:Natj:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → (i' :: is').length = List.length rk:Natks:List Nath:(i == j) = true ∧ sisters (i' :: is') (k :: ks) = true⊢ (i :: i' :: is').length = (j :: k :: ks).length All goals completed! 🐙 theorem sisters_not_prefix (p r : Pos) (h : sisters p r = true) : ¬ p <+: r := p:Posr:Posh:sisters p r = true⊢ ¬p <+: r induction p generalizing r with r:Posh:sisters [] r = true⊢ ¬[] <+: r All goals completed! 🐙 i:Natis:List Natih:∀ (r : Pos), sisters is r = true → ¬is <+: rr:Posh:sisters (i :: is) r = true⊢ ¬i :: is <+: r cases r with i:Natis:List Natih:∀ (r : Pos), sisters is r = true → ¬is <+: rh:sisters (i :: is) [] = true⊢ ¬i :: is <+: [] All goals completed! 🐙 i:Natis:List Natih:∀ (r : Pos), sisters is r = true → ¬is <+: rj:Natjs:List Nath:sisters (i :: is) (j :: js) = true⊢ ¬i :: is <+: j :: js cases is with i:Natj:Natjs:List Natih:∀ (r : Pos), sisters [] r = true → ¬[] <+: rh:sisters [i] (j :: js) = true⊢ ¬[i] <+: j :: js cases js with i:Natj:Natih:∀ (r : Pos), sisters [] r = true → ¬[] <+: rh:sisters [i] [j] = true⊢ ¬[i] <+: [j] All goals completed! 🐙 i:Natj:Natih:∀ (r : Pos), sisters [] r = true → ¬[] <+: rk:Natks:List Nath:sisters [i] (j :: k :: ks) = true⊢ ¬[i] <+: j :: k :: ks All goals completed! 🐙 i:Natj:Natjs:List Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rh:sisters (i :: i' :: is') (j :: js) = true⊢ ¬i :: i' :: is' <+: j :: js cases js with i:Natj:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rh:sisters (i :: i' :: is') [j] = true⊢ ¬i :: i' :: is' <+: [j] All goals completed! 🐙 i:Natj:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rk:Natks:List Nath:sisters (i :: i' :: is') (j :: k :: ks) = true⊢ ¬i :: i' :: is' <+: j :: k :: ks i:Natj:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rk:Natks:List Nath:i = j ∧ sisters (i' :: is') (k :: ks) = true⊢ ¬i :: i' :: is' <+: j :: k :: ks i:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rk:Natks:List Nath:sisters (i' :: is') (k :: ks) = true⊢ ¬i :: i' :: is' <+: i :: k :: ks i:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rk:Natks:List Nath:sisters (i' :: is') (k :: ks) = true⊢ ¬(i = i ∧ i' :: is' <+: k :: ks) i:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rk:Natks:List Nath:sisters (i' :: is') (k :: ks) = trueleft✝:i = ihp:i' :: is' <+: k :: ks⊢ False All goals completed! 🐙
Exercício★★★(c-command-dominance)

Suponha que p c-comanda q: uma irmã r de p domina q. Prove que p não domina q e que q não domina p.

Dica: um prefixo de q que não é mais longo do que outro prefixo de q é prefixo dele (List.prefix_of_prefix_length_le), e um prefixo do mesmo comprimento é a própria lista (List.IsPrefix.eq_of_length).

theorem declaration uses `sorry`cCommand_not_dominates (p r q : Pos) (hs : sisters p r = true) (hd : r <+: q) : ¬ p <+: q := p:Posr:Posq:Poshs:sisters p r = truehd:r <+: q⊢ ¬p <+: q All goals completed! 🐙 theorem declaration uses `sorry`cCommand_not_dominated (p r q : Pos) (hs : sisters p r = true) (hd : r <+: q) : ¬ q <+: p := p:Posr:Posq:Poshs:sisters p r = truehd:r <+: q⊢ ¬q <+: p All goals completed! 🐙
Exercício★★(mutual-c-command)

O c-comando não é simétrico, mas o c-comando mútuo é: p e q se c-comandam mutuamente quando p c-comanda q e q c-comanda p. Defina mutualCCommand e confira, na árvore snowWhite, que ele coincide com a relação de irmãs.

def declaration uses `sorry`mutualCCommand {α β : Type} (t : ParseTree α β) : List (Pos × Pos) := sorry theorem declaration uses `sorry`mutualCCommand_snowWhite : mutualCCommand snowWhite = sisterhood snowWhite := ⊢ mutualCCommand snowWhite = sisterhood snowWhite All goals completed! 🐙
def precede : Pos → Pos → Bool | i :: is, j :: js => i < j || (i == j && precede is js) | _, _ => false def precedence {α β : Type} (t : ParseTree α β) : List (Pos × Pos) := (posPairs t).filter fun (p, q) => precede p q [([0], [1]), ([0], [1, 0]), ([0], [1, 0, 0]), ([0], [1, 1]), ([0], [1, 1, 0]), ([0, 0], [1]), ([0, 0], [1, 0]), ([0, 0], [1, 0, 0]), ([0, 0], [1, 1]), ([0, 0], [1, 1, 0]), ([1, 0], [1, 1]), ([1, 0], [1, 1, 0]), ([1, 0, 0], [1, 1]), ([1, 0, 0], [1, 1, 0])]#eval precedence snowWhite
Exercício★★(imm-precedence)

Defina a precedência imediata, a partir da precedência, do mesmo modo que a dominância imediata foi definida a partir da dominância. Confira o resultado na árvore snowWhite.

def declaration uses `sorry`immPrecedence {α β : Type} (t : ParseTree α β) : List (Pos × Pos) := sorry theorem declaration uses `sorry`immPrecedence_snowWhite : immPrecedence snowWhite = [([0], [1]), ([0], [1, 0]), ([0], [1, 0, 0]), ([0, 0], [1]), ([0, 0], [1, 0]), ([0, 0], [1, 0, 0]), ([1, 0], [1, 1]), ([1, 0], [1, 1, 0]), ([1, 0, 0], [1, 1]), ([1, 0, 0], [1, 1, 0])] := ⊢ immPrecedence snowWhite = [([0], [1]), ([0], [1, 0]), ([0], [1, 0, 0]), ([0, 0], [1]), ([0, 0], [1, 0]), ([0, 0], [1, 0, 0]), ([1, 0], [1, 1]), ([1, 0], [1, 1, 0]), ([1, 0, 0], [1, 1]), ([1, 0, 0], [1, 1, 0])] All goals completed! 🐙
Exercício★★(command)

Defina command supondo que o S mais próximo é sempre a raiz da árvore. Confira o resultado na árvore snowWhite.

def declaration uses `sorry`command {α β : Type} (t : ParseTree α β) : List (Pos × Pos) := sorry theorem declaration uses `sorry`command_snowWhite : (command snowWhite).length = 28 := ⊢ (command snowWhite).length = 28 All goals completed! 🐙
end Parsing