🧩

Lean4 で CCG パーサを実装する

に公開
2026/02/06
1件

Lean 4 で組合せ範疇文法 (CCG : Combinatory Categorial Grammar) の簡易パーサを実装します。CKY ライクなチャートパースで導出木を列挙し、#eval でその場で動かして眺めます。

この記事は Lean で「証明する」話ではなく、Lean を「プログラミング言語として使う」話です。ただし、CCG の導出にはある種の証明のような雰囲気もあり、Lean との親和性が高い話題かと思います。

対象読者:

  • Lean や Haskell などの関数型言語に興味があり、なんとなく読み書きできる人
  • 自然言語処理や形式文法、パーサの構築に興味がある人
  • 「Lean = 証明支援」というイメージはあるが、プログラミング用途も覗いてみたい人

この記事でやること

CCG の簡易的パーサを Lean 4 で実装します。CKY ライクなアルゴリズムでチャートパースをして、導出木を列挙します。

Lean でのプログラミング上のポイントは以下の通りです。

  1. inductive や infix で DSL 的な表記や AST (抽象文法木) を自然に作れる
  2. Option / List / HashMap と do 構文 / for / let mut で、探索 + DP を素直に書ける

CCG の概要

CCG は、単語に「範疇 (Category)」を割り当てて、「組合せ規則」により文を構成する単語や語句の範疇の合成を繰り返し、最終的に範疇 S (文) に到達するかを見る形式文法です。

範疇

範疇は語句の統語的な役割を示すラベルです。証明支援系になじみがある人には、ある種の型もしくは命題だと思うとよいです(Lambek 計算)。
範疇は、基底範疇と関数型範疇からなります。

  • 基底範疇 : N, NP, S など (直感的にはそれぞれ、名詞、名詞句、文に相当)
  • 関数型範疇 : 二つの範疇を演算子 /, \backslash で結合したもの
    例 : NP/N, S\backslash NP, S\backslash NP/NP など

関数型範疇については直感的には次のようにとらえるとよいです。

  • NP/N を持つ語句は、右に N が来ると合成されて NP になる (例 : 冠詞)
  • S\backslash NP を持つ語句は、左に NP が来ると合成されて S になる (例 : 自動詞)

なお、演算子 /, \backslash は左結合するものとし、例えば S\backslash NP/NP は (S\backslash NP)/NP と読みます。

組合せ規則

隣接して並ぶ複数(もしくは単一)の範疇を組み合わせて、新たな範疇を作る規則です。

代表的なものを以下に示します。

  • 順関数適用 [>] X/Y \ \ \ Y \Rightarrow X
  • 逆関数適用 [<] Y \ \ \ X\backslash Y \Rightarrow X
  • 順関数合成 [>B] X/Y \ \ \ Y/Z \Rightarrow X/Z
  • 逆関数合成 [<B] Y\backslash Z \ \ \ X\backslash Y \Rightarrow X\backslash Z
  • 順型繰り上げ [>T] X \Rightarrow T/(T\backslash X)
  • 逆型繰り上げ [<T] X \Rightarrow T\backslash(T/X)

これらの規則で文を構成する単語や語句の範疇を組み合わせ、その過程を表す導出木を作っていくのが CCG の基本です。

CCG での導出の例

CCG で文の範疇を導出する様子を、"Keats eats apples" の解析を例にしてみていきます。
まず、文中の各単語に対して範疇を割り当てます。

  • "Keats" \vdash NP
  • "eats" \vdash S\backslash NP/NP
  • "apples" \vdash NP

これらの範疇を組合せ規則で組み合わせて、文の範疇を導出していきます。導出木を自然演繹での証明図の記法を用いて次のように表せます。

"Keats eats apples"の導出木
CCG での "Keats eats apples" の範疇の導出

まず、"eats" の範疇 S\backslash NP/NP と "apples" の範疇 NP とを順関数適用[>]で組み合わせて範疇 S\backslash NP を作り、次に "Keats" の範疇 NP とを逆関数適用[<]で組み合わせて最終的に S を得ます。
なお、"Keats eats apples" には次のような別導出も存在します。

"Keats eats apples"の導出木
CCG での "Keats eats apples" の範疇の別導出

こちらでは、"Keats" の範疇 NP を型繰り上げ[>T]を用いて S/(S\backslash NP) に持ち上げてから、関数合成[>B]と関数適用[>]を行って S を得ています。

このように、同じ文(語・語句)に複数の導出があり得る(曖昧性)のが、CCG の特徴のひとつです。

CCG パーサの実装

CCG パーサを実装していきます。
全体のコードは下記リンクの Lean Playground で動かせます。Playground の下のほうで、

#eval parse lexicon1 "Keats eats apples"

のように打つと、"Keats eats apples" をパースした導出木の一覧が infoview に表示されます。

全体構成

プログラムの全体的な構成は以下の通りです。コード中 section でブロック分けしています。

  1. Utility : トークン分割や文字列補助
  2. Category : 範疇 Cat の定義
  3. Rules : Binary/Unary 規則 (関数適用、合成、型繰り上げ)
  4. Tree : 導出木 Tree の定義
  5. Applying : 木に規則を適用して新しい木を生成
  6. Parsing : CKYライクなアルゴリズムでチャートを埋める
  7. Example : 実行例

0. Lean でプログラムを書くための Tips

Lean でプログラミングするときに知っておくとよい Tips を挙げておきます。

  1. #eval はその場で実行評価できる
    • #eval <term> で評価結果を表示できる
    • 型を ToString のクラスインスタンスとしておくと表示をカスタマイズできる
  2. inductive / structure / abbrev でデータ定義する
    • inductive : 列挙型・再帰データ (AST など)
    • structure : レコード
    • abbrev : 型エイリアス
  3. Option と List で探索を書くとよい
    • 失敗は none にする
    • 複数候補は List を使う
    • map / flatMap / filterMap と組み合わせて「列挙+失敗除去」を自然に書ける
  4. Id.run do / let mut / for で手続き型のスタイルで書ける
    • let mut で可変な変数を宣言
    • for で繰り返し

1. Utility : トークン分割など

abbrev Token := String -- 語(token)の型

def String.toTokens (str : String) : List Token :=
  str.splitOn.filter (· ≠ "")

abbrev で Token を String の別名にしておくと、型注釈で「この項はトークン(単語)なんだな」と意図が伝わりやすくなります。

また、String 型の項 sentence に対して sentence.toTokens とすると、上記で定義した関数を使って String.toTokens sentence と解釈されます (フィールド表記で関数を呼び出せます)。

2. Category : 範疇を inductive で定義する

まず、関数型範疇を構成するときの演算子 /, \backslash を表現する列挙型 Dir を inductive を使って定義します。

/-- 関数適用の向き -/
inductive Dir : Type
  | Fwd -- /
  | Bwd -- \
  deriving BEq

deriving BEq により == が使えるようになります。組合せ規則適用で「範疇が一致するか」を見るのに必要になります。

範疇を表す型を Cat として定義します。inductive によって、基底範疇(S, NP, N)を列挙的に、関数型範疇を再帰的に表現できます。

/-- 範疇 Cat -/
inductive Cat : Type
  | S  
  | NP 
  | N 
  | Fun : Dir → Cat → Cat → Cat -- 関数型範疇 x/y or x\y
  deriving BEq

例えば Cat.Fun .Bwd .S .NP は S\backslash NP を表す Cat 型の項となります。

infix で中置演算子記号 />, \> を定義して、CCG の記法に寄せておきます。
(\\> となっているのはバックスラッシュのエスケープのためです)

/-- 関数型範疇の記法 -/
infixl:70 " /> "   => Cat.Fun Dir.Fwd -- x/y を x /> y で表記
infixl:70 " \\> "  => Cat.Fun Dir.Bwd -- x\y を x \> y で表記

こうしておくと、.S \> .NP /> .NP のように、ほぼ CCG の見た目で範疇を書けます。

Cat を ToString 型クラスのインスタンスにする

Dir や Cat を ToString 型クラスのインスタンスとしておくと、#eval でそれらの項を評価したときに、infoview で良い感じに表示されます。

def Dir.toString : Dir → String
  | .Fwd => "/"
  | .Bwd => "\\"

instance : ToString Dir where
  toString := Dir.toString

def Cat.toString : Cat → String
  | .S  => "S"  | .NP => "NP"  | .N  => "N"
  | .Fun d x y =>
    match x, y with
    | .Fun .., .Fun .. => x.toString ++ d.toString ++ "(" ++ y.toString ++ ")"
    | .Fun .., _       => x.toString ++ d.toString ++ y.toString
    | _      , .Fun .. => x.toString ++ d.toString ++ "(" ++ y.toString ++ ")"
    | _      , _       => x.toString ++ d.toString ++ y.toString

instance : ToString Cat where
  toString := Cat.toString

#eval .S /> (.S \> .NP) -- S/(S\NP) と表示される

3. Rules : 規則を「適用関数 + 列挙型」で表す

範疇の部分ができたので、次は組合せ規則をコードに落とします。

3.1 組合せ規則の適用は Option Cat で返す

3.1.1 関数適用規則

順関数適用[>]を行う fapp は Option Cat 型の項を返す関数として定義します。引数の構造に対するパターンマッチングで書くことができます。

/-- Forward functional application
  [>] x/y y ⟹ x -/
def fapp : Cat → Cat → Option Cat
  | .Fun .Fwd x y, y' => if y == y' then some x else none
  | _, _  => none

適用失敗時に none を返すようにしています。これによって後で、「全ルールを試して成功した結果だけを拾う」といった処理が filterMap を使うだけでできるようになります。

逆関数適用[<]を行う関数 bapp も同様に定義します。

3.1.2 関数合成規則

今回は X/Y \ \ Y/Z \Rightarrow X/Z のような合成規則に加えて、X/Y \ \ Y/W/Z \Rightarrow X/W/Z のような深い合成も含む一般化関数合成規則を実現します。
順(一般化)関数合成規則[>B]を行う関数 fcompGen は次のように定義できます。

/-- Generalized forward functional composition
  [>B] x/y y/$/z ⟹ x/$/z -/
def fcompGen : Cat → Cat → Option Cat
  | .Fun .Fwd x y, .Fun .Fwd y' z =>
    if y == y' then
      some (x /> z)
    else
      match fcompGen (x /> y) y' with
      | some x' => some (x' /> z)
      | none => none
  | _, _ => none

y == y' が成り立つケースが通常の関数合成規則となります。より深い合成は再帰によって実現しています。

逆関数合成規則[<B]を行う関数 bcompGen も同様に定義します。

3.1.3 型繰り上げ規則

型繰り上げ規則は上記の規則と異なり、範疇を一つだけ取って変換する unary 規則です。
型繰り上げ規則を無制限に適用すると導出木が際限なく増えます。ここでは、NP だけを対象に、

  • NP \Rightarrow S/(S\backslash NP)
  • NP \Rightarrow S\backslash (S/NP)

の形に制限します。

順型繰り上げ規則[>T]を行う関数 fraiseは次のように定義できます。

/-- Forward Type rising
  [>T] x ⟹ t/(t\x) : 今回は x = NP, t = S に限定する -/
def fraise (x : Cat := .NP) (t : Cat := .S) : Cat → Option Cat
  | .NP => some (t /> (t \> x))
  | _ => none

ここで (x : Cat := .NP) のように書くと、デフォルト引数を設定できます。

逆型繰り上げ規則[<T]を行う関数 braise も同様に定義します。

組合せ規則の一覧を示す列挙型 (規則名と実装を結びつける)

組合せ規則には、

  • 2 つの範疇を取るもの (binary) : 関数適用規則、関数合成規則
  • 1 つの範疇を取るもの (unary) : 型繰り上げ規則

の 2 種類がありました。
それぞれの適用規則の一覧を表す列挙型 BinaryRule と UnaryRule を定義し、さらにそれらの要素のリスト binaryRules と unaryRules を定義しておきます。

inductive BinaryRule : Type
  | Fa | Ba | Fc | Bc -- [>], [<], [>B], [<B]

inductive UnaryRule : Type
  | Ft | Bt -- [>T], [<T]

def binaryRules : List BinaryRule := [.Fa, .Ba, .Fc, .Bc]
def unaryRules  : List UnaryRule  := [.Ft, .Bt]

列挙型の要素と先に定義した規則の実装とを対応付けます。

def BinaryRule.applyBinary : BinaryRule → Cat → Cat → Option Cat
  | .Fa => fapp
  | .Ba => bapp
  | .Fc => fcompGen
  | .Bc => bcompGen

def UnaryRule.applyUnary : UnaryRule → Cat → Option Cat
  | .Ft => fraise
  | .Bt => braise

こうしておくと、後で「すべてのルールを試す」いった処理が map / filterMap で自然に書けます。

4. Tree : 導出木を inductive で定義する

導出木 Tree は帰納型として inductive を使って定義できます。

inductive Tree : Type
  | leaf   (tok : Token)    (c : Cat)  -- 単語の範疇
  | binary (r : BinaryRule) (c : Cat) (lt rt : Tree) -- binary 規則の適用
  | unary  (r : UnaryRule)  (c : Cat) (t : Tree)     -- unary 規則の適用(型繰り上げ)

木の範疇をすぐ取り出せるよう Tree.cat を用意しておきます。

def Tree.cat : Tree → Cat
  | .leaf _ c => c
  | .binary _ c _ _ => c
  | .unary _ c _ => c

説明は省きますが、Tree もToStringの型インスタンスにして、導出木がきれいに表示されるようにしておきます。

5. Applying : 規則適用を列挙として書く

「2 つの範疇に全 binary 規則を試し、成功した結果だけ拾う」という処理は filterMap を使って書けます。

def tryBinaryRules (lc rc : Cat) : List (BinaryRule × Cat) :=
  binaryRules.filterMap fun r ↦
    (r.applyBinary lc rc).map (r, ·)

combineTree は、その結果を Tree.binary に包んで新しい導出木を作ります。

def combineTree (lt rt : Tree) : List Tree :=
  let applied := tryBinaryRules lt.cat rt.cat
  applied.map fun (r, c) ↦ .binary r c lt rt

unary 規則を適用する raiseTree も同様に以下のように定義できます。

def tryUnaryRules (c : Cat) : List (UnaryRule × Cat) :=
  unaryRules.filterMap fun r ↦
    (r.applyUnary c).map (r, ·)

def raiseTree (t : Tree) : List Tree :=
  let applied := tryUnaryRules t.cat
  applied.map fun (r, c) ↦ .unary r c t

6. Parsing : HashMap チャートで CKY ライクな DP を行う

パーサ実装のメイン部分です。句構造解析で用いられる CKY (Cocke-Kasami-Younger) アルゴリズムをベースとした動的計画法 (DP : Dynamic Programming) で解析していきます。

アルゴリズムを説明します。
トークン列 toks = ["Keats", "eats", "an", "apples"] を考えます (トークン長 len = 4)。このトークン列に対して図のようなチャートを考えます。

"Keats eats an apple" のチャート
"Keats eats an apple" のチャート

チャートは「開始位置 i (0-index)から長さ span の区間」ごとにセルを持ち、セル (span, i) は、トークン i から i+span-1 の部分(長さ span)を覆う導出木のリストを保持するものとします。
各セルの導出木は、そのセルを頂点とするピラミッドの下の部分の導出木を使うことによって構築することができます。例えば、セル (3,0) "Keats eats an" の導出木は、セル (2, 0) "Keats eats" の導出木と (1,2) "an" の導出木を binary 規則で組み合わせて作れます(セル (1,0) "Keats" と (2,1) "eats an" との組み合わせもあります)。セル (2,0) の導出木もその下のセル (1,0) と (1,1) を組み合わせて作れます。
したがって、一番下層 span = 1 のセルから導出木を作り、順番に上の層のセルの導出木を構築しすることで、最終的に頂点のセル (len, 0)、すなわちトークン列全体の導出木のリストを得ることができます。

6.1 範疇辞書 Lexicon とチャート Chart を HashMap で定義する

範疇辞書とチャートを HashMap を使って定義します。
そのため、ファイルの先頭で Std.Data.HashMap をインポートしておきます。

import Std.Data.HashMap

範疇辞書の型 Lexicon はトークンを key として、そのトークンの範疇のリストを value とする HashMap として定義します。

/-- 範疇辞書の型 -/
abbrev Lexicon := Std.HashMap Token (List Cat)

def Lexicon.getCats (lex : Lexicon) (t : Token) : List Cat :=
  lex.getD t []

トークンからその範疇のリストを得る getCats も定義しました。getD は key がなければデフォルト値を返します。よって、辞書にない未知語は [] を返します。
具体的な範疇辞書は 7. Example において例を示します。

チャートの型 Chart は、(span, i) を key として、そのセルの導出木のリストを value とする HashMap とします。

/-- chart の型
  key = (span, i), value = 「i から span トークン分の部分の導出木のリスト」
-/
abbrev Chart := Std.HashMap (Nat × Nat) (List Tree) -- key : (span, i)

def Chart.getTrees (chart : Chart) (span_i : Nat × Nat) : List Tree :=
  chart.getD span_i []

なお、HashMapの key にできる条件は「BEq と Hashable の型インスタンスになっている」ことです。String や Nat、Nat × Nat は標準でそれらが揃っているのでそのまま使えます。

6.2 fillChart : Id.run do + let mut で DP を書く

CKY 風のアルゴリズムでチャートを埋めていきます。大まかにやることは次の通りです。

  1. span = 1 :
    • 各トークン t について、範疇辞書 lex から leaf を作る
    • leaf に unary 規則を適用した木を追加
  2. span \ge 2 :
    • 分割点 k を動かして combineTree で木を作る
    • そこに unary 規則を適用した木を追加

Lean では do 記法によって、ローカルに手続型のスタイルでプログラムを書けます。

/-- ## CKY パーシング -/
def fillChart (lex : Lexicon) (toks : List Token)  : Chart := Id.run do
  let len := toks.length
  let mut chart : Chart := {}
  -- リーフノードを作成 + 型繰り上げ適用 (span = 1)
  let span : Nat := 1
  for (t, i) in toks.zipIdx do
    let leaves : List Tree := (lex.getCats t).map (.leaf t ·)
    let raised : List Tree := leaves.flatMap (raiseTree ·) -- 型繰り上げ適用
    chart := chart.insert (span, i) (leaves ++ raised)  -- chart の更新(cell の追加)
  -- ボトムアップに導出木を結合 + 型繰り上げ適用 (span ≥ 2)
  for span in 2...(len + 1) do
    for i in 0...(len - span + 1) do
      let mut trees : List Tree := []
      for k in 1...span do
        let lts := chart.getTrees (k, i)
        let rts := chart.getTrees (span - k, i + k)
        trees := trees ++
          lts.flatMap fun lt ↦ rts.flatMap fun rt ↦ combineTree lt rt
      let raised : List Tree := trees.flatMap (raiseTree ·) -- 型繰り上げ適用
      chart := chart.insert (span, i) (trees ++ raised)  -- chart の更新
  return chart

以下の点に着目してコードを読むとよいでしょう。

  • Id.run do :
    do ブロックの結果を値として返す (ここでは chart : Chart を返します)
  • let mut chart := {} .. chart := chart.insert.. :
    do ブロック内で、可変 (mutable) な変数を宣言・初期化し、その値を更新できる。(裏では状態モナド変換子 StateT でよい感じに処理)
  • for span in 2...(len+1) do, for i in 0...(len-span+1) do:
    2重ループで、チャートのセルを下と左から走査
  • lts.flatMap fun lt ↦ rts.flatMap fun rt ↦ combineTree lt rt :
    左のセルと右のセルの全組合せ (探索) をきれいに書ける

6.3 parse 関数

CCG パーサ parseCCG は、 fillChart でチャートを作りその頂点を返すことで、トークン列の導出木のリストを返します。

def parseCCG  (lex : Lexicon) (toks : List Token) : List Tree :=
  let chart := fillChart lex toks
  let len := toks.length
  chart.getTrees (len, 0) -- chart の頂点

def parse  (lex : Lexicon) (sentence : String): List Tree :=
  let toks : List Token := sentence.toTokens
  parseCCG lex toks

parse は(範疇辞書と)文字列を渡すと、勝手にトークンに分割して、パースしてくれます。

7. Example : 実行例 #eval で評価

例 1) Keats eats apples

パーサ(parse)を実装できたので、実際に動作を試してみます。
まず、範疇辞書を次のようにべた書きで定義しておきます。

def lexicon1 : Lexicon := {
  ("Keats",   [.NP]),
  ("eats",    [.S \> .NP /> .NP]),
  ("cooks",   [.S \> .NP /> .NP]),
  ("an",      [.NP /> .N]),
  ("apple",   [.N]),
  ("apples",  [.NP])}

parse へ範疇辞書と文(文字列)を渡すと導出木の一覧が得られます。#eval で評価してみましょう。(Lean Playground へのリンクを再掲しておきます)

#eval parse lexicon1 "Keats eats apples"

以下のような 4 種類の導出木が得られます (infoview に表示されます)。

"Keats eats apples" の導出結果
[
S [<]
├NP "Keats"
├S\NP [>]
│├S\NP/NP "eats"
│├NP "apples", 
S [>]
├S/(S\NP) [>T]
│├NP "Keats"
├S\NP [>]
│├S\NP/NP "eats"
│├NP "apples", 
S [>]
├S/NP [>B]
│├S/(S\NP) [>T]
││├NP "Keats"
│├S\NP/NP "eats"
├NP "apples", 
S [<]
├S/NP [>B]
│├S/(S\NP) [>T]
││├NP "Keats"
│├S\NP/NP "eats"
├S\(S/NP) [<T]
│├NP "apples"]

CCG の解説で示した導出木の表記とは異なっていますが、木構造の対応関係は見て取れるかと思います。

#eval parse lexicon2 "Keats cooks an apple"

なども試してみるとよいでしょう。

例 2) I think that that that that that boy wrote is wrong

有名なこの文も、"that" の多義性をその範疇に反映させることで、導出を行うことができます。(ただし導出木の候補は膨れ上がります。)

def lexicon2 : Lexicon := {
  ("I",       [.S /> (.S \> .NP)]),
  ("think",   [.S \> .NP /> .S,]),
  ("that",    [.S /> .S, .NP /> .N, .N, .N \> .N /> (.S /> .NP)]),
  ("boy",     [.N]),
  ("wrote",   [.S \> .NP /> .NP]),
  ("is",      [.S \> .NP /> (.S \> .NP)]),
  ("wrong",   [.S \> .NP])}

#eval parse lexicon2 "I think that that that that that boy wrote is wrong"

発展 : CCG での意味合成

ここまでは、CCG の範疇を組み合わせて合成していくパーサの実装について取り組んできました。実は、CCG の一番面白いところは、範疇に加えて「意味」の合成も行っていくというところです。

例を見ていきます。"Keats eats apples" の各単語に対して以下のように、範疇とその意味を表すラムダ式を対応させます。(型理論の文脈だと、ラムダ式は範疇(型もしくは命題)に対する項もしくは証明とみることができます。)

  • "Keats" \vdash NP : keats
  • "eats" \vdash S\backslash NP/NP : \lambda y. \lambda x. eat(x, y)
  • "apples" \vdash NP : apples

組合せ規則も範疇の合成に加えて意味の合成も行います。例えば関数適用規則は次のように定められます。

  • 順関数適用 [>] X/Y : f\ \ \ Y : a \Rightarrow X : f a
  • 逆関数適用 [<] Y : a\ \ \ X\backslash Y : f \Rightarrow X : f a

組合せ規則により範疇の導出を行うことで、図のように意味の合成も自動的に行われ、最終的に文全体の意味を表すラムダ式(論理式) eat(keats, apples) を得ることができます(適宜 β 簡約しています)。
CCG での "Keats eats apples" の意味合成

関数型プログラミング言語である Lean にとってラムダ式はお手の物ですので、CCG の意味合成も行うようにパーサを拡張することも、素直にできるかと思います(簡単とは言っていない)。

おわりに

本記事では、CCG の簡易パーサの実装を題材にして、Lean で

  • inductive / infix で DSL を作り
  • Option / List で探索を組み
  • HashMap で辞書とチャートを実装し
  • Id.run do / for / let mut で DP を書き
  • #eval で実験する

という一連のプログラミングの体験を説明しました。
Lean は関数型プログラミング言語としてのスタイルと、do 記法や for を使った手続き型スタイルとを組み合わせて書きやすく、パーサを作るにはやりやすい言語だと思います。
またこの先には、今度は Lean を証明支援系として使って、実装したパーサが正しいかどうかを証明するといったことも可能になります。

ぜひ、Lean でのプログラミングに取り組んでみてください。

おすすめの参考図書

Discussion