The metrical grid

The metrical grid is the prominence dual of the prosodic word: a column of marks over each syllable, taller standing for greater relative prominence (primary > secondary > unstressed). This file is organised as a small tower of objects, each adding structure to the plain grid and each connected to the plainer one below by a forgetful map:

Marks        rendered rows of marks; the Continuous Column Constraint lives here
  ↑ rows                                    (Prince 1983's autonomous grid)
Grid         column heights — the pure rhythmic grid
  ↑ toGrid                                   (add the head terminal)
MarkedGrid   a grid whose columns carry the head-spine (Liberman & Prince's head terminals)
  ↑ project                                  (the RPPR)
Tree         the bracketed grid — brackets at all layers (Hayes 1995 §3.5)

The projection Grid.project is Liberman and Prince's (1977) Relative Prominence Projection Rule: a homomorphism from the tree into the head-marked grid, built from a small algebra (cell/juxtapose/promote/clear). The grid readers (columns, terminals, headTerminals, headHeights) are the forgetful maps out of it. What the forgetful map onto the pure grid drops is theorem-shaped: constituency (Grid.ofTree_not_injective; the grid underdetermines bracketing, Hayes 1995 §3.8) and, under recursion, order-invariant culminativity (Grid.not_culminative_under_recursion).

Main definitions

• Grid / Grid.peak / Grid.IsCulminative — the pure grid (column heights) and its invariants.
• Marks / Marks.IsContinuous / Grid.rows — the rendered grid and the Continuous Column Constraint, which holds for any rendered grid by construction.
• MarkedGrid / Grid.project — the head-marked grid and the RPPR projection from a tree.
• Tree.columns / Tree.headTerminals / Tree.headHeights / Tree.IsHeaded — the grid readers.

Main results

• Grid.ofTree_isContinuous — the Continuous Column Constraint, by construction (free); Marks.isContinuous_iff reads it column by column.
• Grid.isCulminative_of_forall_lt / Grid.IsCulminative.eq_of_eq_peak — a strict unique maximum is culminative, and a culminative grid has one peak column.
• Grid.peak_toProsTree — head-preservation for a foot (its grid peaks at the head σ).
• Tree.headHeights_eq_peak — on a non-recursive headed word the head terminal's height is the grid peak: metrical primary stress is the tallest column.
• Grid.ofTree_not_injective / Grid.not_culminative_under_recursion — what the projection forgets: constituency, and order-invariant culminativity under recursion.
• Grid.head_below_peak_under_recursion / Grid.head_below_peak_unlayered — the peak can desert the head terminal under recursion or without Layeredness.

References

• [LP77]
• [Pri83]
• [HV87]
• [Hay95b]
• [IM09]

The tower carriers

The four objects of the tower (see the module header): the rendered Marks, the pure Grid, and the head-marked grid MarkedGrid built from Columns. Operations follow, one namespace each.

@[reducible, inline]

abbrev Prosody.Marks : Type

A rendered metrical grid is a list of rows of head-marks, bottom row first.

Equations

• Prosody.Marks = List (List Bool)

@[reducible, inline]

abbrev Prosody.Grid : Type

A metrical grid ([Hay95b] §3.2) records the beat count (column height) over each position, left to right. Absolute heights carry no significance; only relative prominence does.

Equations

• Prosody.Grid = List ℕ

structure Prosody.Column (α : Type u_1) : Type u_1

One column of a marked grid records the σ-leaf it sits over, its mark count (height), and whether it lies on the current head-spine (the head terminal so far, [LP77]).

• terminal : α

  The σ-leaf under this column.

• height : ℕ

  The column height = number of grid marks.

• onSpine : Bool

  Whether this column is (so far) the head terminal.

@[reducible, inline]

abbrev Prosody.MarkedGrid (α : Type u_1) : Type u_1

A grid whose columns carry the head-spine (the head terminals, [LP77]) — the pure grid plus a head marking. It deliberately does not record the full bracketing (that is Tree; Grid.ofTree_not_injective is the honest statement that heights lose it).

Equations

• Prosody.MarkedGrid α = List (Prosody.Column α)

Marks: the Continuous Column Constraint

def Prosody.Marks.rowSubmask (upper lower : List Bool) : Bool

Whether one row is a submask of the row below.

Equations

• Prosody.Marks.rowSubmask upper lower = (upper.zip lower).all fun (p : Bool × Bool) => !p.1 || p.2

def Prosody.Marks.IsContinuous (m : Marks) : Prop

The Continuous Column Constraint ([Pri83]; [Hay95b] §3.4.2 (9)) says that no column has a gap. It is a violable predicate on an arbitrary rendered grid.

Equations

• m.IsContinuous = List.IsChain (fun (lower upper : List Bool) => Prosody.Marks.rowSubmask upper lower = true) m

@[instance_reducible]

instance Prosody.Marks.instDecidableIsContinuous (m : Marks) : Decidable m.IsContinuous

Equations

• m.instDecidableIsContinuous = id inferInstance

theorem Prosody.Marks.isContinuous_iff {m : Marks} : m.IsContinuous ↔ ∀ (r : ℕ) (hr : r + 1 < List.length m) (i : ℕ) (hi : i < m[r + 1].length) (hi' : i < m[r].length), m[r + 1][i] = true → m[r][i] = true

Read column by column, continuity says that a mark in a row sits over a mark in the row below.

The head-marked grid: the marked-grid algebra

def Prosody.MarkedGrid.toGrid {α : Type u_1} (b : MarkedGrid α) : Grid

Forgetting the marking gives the underlying pure grid of column heights.

Equations

• b.toGrid = List.map (fun (x : Prosody.Column α) => x.height) b

def Prosody.MarkedGrid.terminals {α : Type u_1} (b : MarkedGrid α) : List α

The terminals under the columns, left to right.

Equations

• b.terminals = List.map (fun (x : Prosody.Column α) => x.terminal) b

def Prosody.MarkedGrid.headHeights {α : Type u_1} (b : MarkedGrid α) : Grid

The head-spine columns' heights — the head terminals' prominences.

Equations

• b.headHeights = List.map (fun (x : Prosody.Column α) => x.height) (List.filter (fun (x : Prosody.Column α) => x.onSpine) b)

def Prosody.MarkedGrid.headTerminals {α : Type u_1} (b : MarkedGrid α) : List α

The head-spine terminals — the head terminals.

Equations

• b.headTerminals = List.map (fun (x : Prosody.Column α) => x.terminal) (List.filter (fun (x : Prosody.Column α) => x.onSpine) b)

def Prosody.MarkedGrid.cell {α : Type u_1} (x : α) : MarkedGrid α

A single terminal is one column of height 1, on its own head-spine.

Equations

• Prosody.MarkedGrid.cell x = [{ terminal := x, height := 1, onSpine := true }]

def Prosody.MarkedGrid.juxtapose {α : Type u_1} (bs : List (MarkedGrid α)) : MarkedGrid α

Juxtapose sibling constituents.

Equations

• Prosody.MarkedGrid.juxtapose bs = bs.flatten

def Prosody.MarkedGrid.promote {α : Type u_1} (b : MarkedGrid α) : MarkedGrid α

In the head-projection step of the RPPR ([LP77]) a head edge raises the head by one grid mark, bumping every head-spine column.

Equations

• b.promote = List.map (fun (c : Prosody.Column α) => { terminal := c.terminal, height := c.height + if c.onSpine = true then 1 else 0, onSpine := c.onSpine }) b

def Prosody.MarkedGrid.clear {α : Type u_1} (b : MarkedGrid α) : MarkedGrid α

Across a weak edge heights freeze and the head-spine marking is dropped.

Equations

• b.clear = List.map (fun (c : Prosody.Column α) => { terminal := c.terminal, height := c.height, onSpine := false }) b

def Prosody.MarkedGrid.edge {α : Type u_1} (isHead : Bool) (b : MarkedGrid α) : MarkedGrid α

On one edge of the descent a head edge projects and any other clears the spine.

Equations

• Prosody.MarkedGrid.edge isHead b = if isHead = true then b.promote else b.clear

@[simp]

theorem Prosody.MarkedGrid.edge_true {α : Type u_1} (b : MarkedGrid α) : edge true b = b.promote

@[simp]

theorem Prosody.MarkedGrid.edge_false {α : Type u_1} (b : MarkedGrid α) : edge false b = b.clear

The algebra of the marked grid

@[simp]

theorem Prosody.MarkedGrid.toGrid_cell {α : Type u_1} (x : α) : (cell x).toGrid = [1]

@[simp]

theorem Prosody.MarkedGrid.headHeights_cell {α : Type u_1} (x : α) : (cell x).headHeights = [1]

@[simp]

theorem Prosody.MarkedGrid.headTerminals_cell {α : Type u_1} (x : α) : (cell x).headTerminals = [x]

@[simp]

theorem Prosody.MarkedGrid.toGrid_clear {α : Type u_1} (b : MarkedGrid α) : b.clear.toGrid = b.toGrid

@[simp]

theorem Prosody.MarkedGrid.headHeights_clear {α : Type u_1} (b : MarkedGrid α) : b.clear.headHeights = []

@[simp]

theorem Prosody.MarkedGrid.headTerminals_clear {α : Type u_1} (b : MarkedGrid α) : b.clear.headTerminals = []

@[simp]

theorem Prosody.MarkedGrid.headHeights_promote {α : Type u_1} (b : MarkedGrid α) : b.promote.headHeights = List.map (fun (x : ℕ) => x + 1) b.headHeights

@[simp]

theorem Prosody.MarkedGrid.headTerminals_promote {α : Type u_1} (b : MarkedGrid α) : b.promote.headTerminals = b.headTerminals

@[simp]

theorem Prosody.MarkedGrid.toGrid_juxtapose {α : Type u_1} (bs : List (MarkedGrid α)) : (juxtapose bs).toGrid = List.flatMap (fun (x : MarkedGrid α) => x.toGrid) bs

@[simp]

theorem Prosody.MarkedGrid.headHeights_juxtapose {α : Type u_1} (bs : List (MarkedGrid α)) : (juxtapose bs).headHeights = List.flatMap (fun (x : MarkedGrid α) => x.headHeights) bs

@[simp]

theorem Prosody.MarkedGrid.headTerminals_juxtapose {α : Type u_1} (bs : List (MarkedGrid α)) : (juxtapose bs).headTerminals = List.flatMap (fun (x : MarkedGrid α) => x.headTerminals) bs

@[simp]

theorem Prosody.MarkedGrid.headHeights_edge {α : Type u_1} (b : MarkedGrid α) (h : Bool) : (edge h b).headHeights = if h = true then List.map (fun (x : ℕ) => x + 1) b.headHeights else []

@[simp]

theorem Prosody.MarkedGrid.headTerminals_edge {α : Type u_1} (b : MarkedGrid α) (h : Bool) : (edge h b).headTerminals = if h = true then b.headTerminals else []

Grid: peak, the RPPR projection, and the readers

The pure grid: peak, culminativity, rendering

def Prosody.Grid.peak (g : Grid) : ℕ

The prominence peak is the height of the tallest column.

Equations

• g.peak = List.foldr max 0 g

@[simp]

theorem Prosody.Grid.peak_nil : peak [] = 0

theorem Prosody.Grid.le_peak {g : Grid} {h : ℕ} (hh : h ∈ g) : h ≤ g.peak

Every column is at most the peak.

theorem Prosody.Grid.peak_le {g : Grid} {n : ℕ} (h : ∀ x ∈ g, x ≤ n) : g.peak ≤ n

The peak is bounded by any common bound on the columns.

@[simp]

theorem Prosody.Grid.peak_reverse {g : Grid} : peak (List.reverse g) = g.peak

theorem Prosody.Grid.getD_le_peak {g : Grid} (i : ℕ) : List.getD g i 0 ≤ g.peak

Every column height, read with default 0, is at most the peak.

def Prosody.Grid.IsCulminative (g : Grid) : Prop

A grid is culminative ([LP77]; [Hay95b]) when exactly one column is tallest. This is strictly stronger than having a unique head terminal (IsHeaded), since two columns can tie.

Equations

• g.IsCulminative = (List.countP (fun (x : ℕ) => x == g.peak) g = 1)

@[instance_reducible]

instance Prosody.Grid.instDecidableIsCulminative (g : Grid) : Decidable g.IsCulminative

Equations

• g.instDecidableIsCulminative = id inferInstance

theorem Prosody.Grid.isCulminative_of_forall_lt {g : Grid} {i : ℕ} (hi : i < List.length g) (h : ∀ (j : ℕ) (hj : j < List.length g), j ≠ i → g[j] < g[i]) : g.IsCulminative

A column strictly taller than every other is the unique peak.

theorem Prosody.Grid.IsCulminative.eq_of_eq_peak {g : Grid} (hc : g.IsCulminative) {i j : ℕ} (hi : i < List.length g) (hj : j < List.length g) (hpi : g[i] = g.peak) (hpj : g[j] = g.peak) : i = j

Two columns at the peak of a culminative grid are the same column.

def Prosody.Grid.rows (g : Grid) : Marks

Rendering a grid as stacked rows of marks puts a mark in row r over every column taller than r.

Equations

• g.rows = List.map (fun (r : ℕ) => List.map (fun (x : ℕ) => decide (r < x)) g) (List.range g.peak)

@[simp]

theorem Prosody.Grid.length_rows {g : Grid} : List.length g.rows = g.peak

@[simp]

theorem Prosody.Grid.length_getElem_rows {g : Grid} {r : ℕ} (hr : r < List.length g.rows) : g.rows[r].length = List.length g

@[simp]

theorem Prosody.Grid.getElem_rows {g : Grid} {r i : ℕ} (hr : r < List.length g.rows) (hi : i < g.rows[r].length) : g.rows[r][i] = decide (r < g[i])

theorem Prosody.Grid.rows_isContinuous (g : Grid) : g.rows.IsContinuous

The Continuous Column Constraint is free. Every rendered grid satisfies it, because a column is a solid stack of marks by construction — continuity is the shape of a histogram, not a theorem about trees ([Hay95b] §3.4.2).

The RPPR projection

def Prosody.Tree.projectStep (a : Constituent) (ps : List (Constituent × MarkedGrid Tree)) : Constituent × MarkedGrid Tree

One RPPR step pairs the node's label with its grid, so a parent can read the head flag off each child.

Equations

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

def Prosody.Tree.project (t : Tree) : MarkedGrid Tree

The Relative Prominence Projection Rule ([LP77]) is a homomorphism Tree → MarkedGrid. A σ-leaf is one cell, and any other node juxtaposes its children, projecting across head edges and clearing the spine across the rest.

Equations

• t.project = (RoseTree.fold Prosody.Tree.projectStep t).2

@[simp]

theorem Prosody.Tree.project_node (a : Constituent) (cs : List Tree) : project (RoseTree.node a cs) = if a.level = Level.syl ∧ cs = [] then MarkedGrid.cell (RoseTree.node a []) else MarkedGrid.juxtapose (List.map (fun (c : Tree) => MarkedGrid.edge (RoseTree.value c).isHead c.project) cs)

Reading the grid off a tree (the forgetful maps)

def Prosody.Tree.terminals (t : Tree) : List Tree

The σ-leaves of a tree, left to right, form the terminal tier the grid sits over.

Equations

• t.terminals = t.project.terminals

def Prosody.Tree.columns (t : Tree) : Grid

In the grid-column heights ([LP77]) each σ-leaf's height is 1 plus the contiguous run of head edges ending at it.

Equations

• t.columns = t.project.toGrid

def Prosody.Tree.headTerminals (t : Tree) : List Tree

The head terminals ([LP77]) are the σ-leaves reached from the root by all head edges.

Equations

• t.headTerminals = t.project.headTerminals

def Prosody.Tree.headHeights (t : Tree) : Grid

The head terminals' prominences are the live cells' heights.

Equations

• t.headHeights = t.project.headHeights

def Prosody.Tree.IsHeaded (t : Tree) : Prop

A tree is headed when it has a unique head terminal.

Equations

• t.IsHeaded = (List.length t.headHeights = 1)

@[instance_reducible]

instance Prosody.Tree.instDecidableIsHeaded (t : Tree) : Decidable t.IsHeaded

Equations

• t.instDecidableIsHeaded = id inferInstance

def Prosody.Grid.ofTree (t : Tree) : Marks

The metrical grid of a tree, as stacked rows.

Equations

• Prosody.Grid.ofTree t = t.columns.rows

theorem Prosody.Grid.ofTree_isContinuous (t : Tree) : (ofTree t).IsContinuous

Grid.ofTree always satisfies the Continuous Column Constraint ([Pri83]; [Hay95b]), free from Grid.rows_isContinuous, since a projected grid is a histogram.

The reader recursions

Each reader is a homomorphism out of the marked-grid algebra, so on a node it is the juxtaposition of the children's readings, projected across head edges. These fuse project_node with the algebra once, so the downstream proofs never re-walk the fold.

theorem Prosody.Tree.columns_node (a : Constituent) (cs : List Tree) : columns (RoseTree.node a cs) = if a.level = Level.syl ∧ cs = [] then [1] else List.flatMap (fun (c : Tree) => (MarkedGrid.edge (RoseTree.value c).isHead c.project).toGrid) cs

theorem Prosody.Tree.headHeights_node (a : Constituent) (cs : List Tree) : headHeights (RoseTree.node a cs) = if a.level = Level.syl ∧ cs = [] then [1] else List.flatMap (fun (c : Tree) => if (RoseTree.value c).isHead = true then List.map (fun (x : ℕ) => x + 1) c.headHeights else []) cs

theorem Prosody.Tree.headTerminals_node (a : Constituent) (cs : List Tree) : headTerminals (RoseTree.node a cs) = if a.level = Level.syl ∧ cs = [] then [RoseTree.node a []] else List.flatMap (fun (c : Tree) => if (RoseTree.value c).isHead = true then c.headTerminals else []) cs

The head terminals compute the head-terminal relation

inductive Prosody.Tree.IsHeadTerminal : Tree → Tree → Prop

leaf is a head terminal of t, reached from the root by an all-head descent.

• leaf {a : Constituent} (ha : a.level = Level.syl) : IsHeadTerminal (RoseTree.node a []) (RoseTree.node a [])
• head {a : Constituent} {cs : List (RoseTree Constituent)} {c leaf : Tree} : c ∈ cs → (RoseTree.value c).isHead = true → c.IsHeadTerminal leaf → IsHeadTerminal (RoseTree.node a cs) leaf

theorem Prosody.Tree.headTerminal_sound {t leaf : Tree} (h : leaf ∈ t.headTerminals) : t.IsHeadTerminal leaf

By soundness of headTerminals ([LP77]), every head terminal the projection computes really is one, reached from the root by an all-head descent. (The decide-verified lists give the converse concretely, so the full iff is not needed.)

Head-preservation: the foot commuting square

Reading a Foot's grid recovers its head — the height-1 core of the transport story: its column heights are 2 at the head σ and 1 elsewhere, so the grid peaks at 2.

theorem Prosody.Tree.columns_toProsTree {S : Type u_1} (w : S → Syllable.Weight) (f : Foot S) : (Foot.toProsTree w f).columns = f.toGrid

By head-preservation for a foot ([LP77]), projecting a foot's prosodic tree recovers its metrical grid, the commuting square columns ∘ toProsTree = toGrid.

theorem Prosody.Tree.peak_toProsTree {S : Type u_1} (w : S → Syllable.Weight) (f : Foot S) : (Foot.toProsTree w f).columns.peak = 2

A foot's grid peaks at 2 — its head σ carries the primary mark ([LP77]).

What the grid forgets

The forgetful map onto the pure grid is one-way: it drops constituency (ofTree_not_injective; [Hay95b] §3.8 argues for bracketing precisely because the grid underdetermines it) and, under recursion, order-invariant culminativity (not_culminative_under_recursion).

theorem Prosody.Grid.ofTree_not_injective : ¬Function.Injective ofTree

The grid render is not injective, since it forgets constituency. A σ parsed under a foot and the same σ left bare render to the same grid ([Hay95b] §3.8).

theorem Prosody.Tree.not_culminative_under_recursion : ∃ (t : Tree), IsWord t ∧ ¬t.columns.IsCulminative

Recursion can break culminativity. A word recursively dominating another word, each heading its own σ, has two equally tall columns and no unique peak.

The word peak is the head terminal

On a non-recursive headed word the grid peak is the head terminal ([LP77]): metrical primary stress is the tallest column. Recursion is the sole obstruction, and — this being [Hay95b] §3.4.2(C)'s "the higher grid mark may only be assigned to a syllable that already bears stress" — the peak sits atop a foot head.

theorem Prosody.Tree.headHeights_sublist_columns (t : Tree) : List.Sublist t.headHeights t.columns

Head-terminal heights are a sublist of the columns.

theorem Prosody.Tree.headHeight_le_peak {t : Tree} {h : ℕ} (hh : h ∈ t.headHeights) : h ≤ t.columns.peak

Every head-terminal height is at most the peak.

theorem Prosody.Tree.mem_toGrid_edge {h : Bool} {b : MarkedGrid Tree} {c : ℕ} (hc : c ∈ (MarkedGrid.edge h b).toGrid) : c ∈ b.toGrid ∨ c ∈ (MarkedGrid.edge h b).headHeights

An edge column is either a child column or a head height of the edge — the algebraic split that replaces the foot-internal case analysis.

theorem Prosody.Tree.col_le_two_or_head {t : Tree} (hw : IsWord t) (hr : noRec t = 0) (c : ℕ) : c ∈ t.columns → c ≤ 2 ∨ c ∈ t.headHeights

In a word every column is ≤ 2 unless it is a head-terminal height — the genuine non-recursion content, now one algebraic split (mem_toGrid_edge) plus the height bound.

theorem Prosody.Tree.two_le_head {t : Tree} (hw : IsWord t) (hr : noRec t = 0) {h : ℕ} (hh : h ∈ t.headHeights) : 2 ≤ h

In a word the head terminal sits below ω, so its height is at least 2.

theorem Prosody.Tree.headHeights_eq_peak {t : Tree} (hw : IsWord t) (hh : t.IsHeaded) (hr : noRec t = 0) : t.headHeights = [t.columns.peak]

On a non-recursive headed word the head terminal is the grid peak ([LP77]), so metrical primary stress is the tallest column.

theorem Prosody.Tree.head_below_peak_under_recursion : ∃ (t : Tree), IsWord t ∧ t.IsHeaded ∧ t.columns.IsCulminative ∧ t.headHeights ≠ [t.columns.peak]

Under recursion the peak can desert the head terminal, even when culminative ([IM09] for recursive ω; the peak≠head-terminal consequence is a property of this model).

theorem Prosody.Tree.head_below_peak_unlayered : ∃ (t : Tree), t.IsHeaded ∧ noRec t = 0 ∧ ¬IsWord t ∧ t.headHeights ≠ [t.columns.peak]

Without Layeredness the peak can desert the head terminal too.