Lean4 で CCG パーサを実装する
Lean 4 で組合せ範疇文法 (CCG : Combinatory Categorial Grammar) の簡易パーサを実装します。CKY ライクなチャートパースで導出木を列挙し、#eval でその場で動かして眺めます。
この記事は Lean で「証明する」話ではなく、Lean を「プログラミング言語として使う」話です。ただし、CCG の導出にはある種の証明のような雰囲気もあり、Lean との親和性が高い話題かと思います。
対象読者:
- Lean や Haskell などの関数型言語に興味があり、なんとなく読み書きできる人
- 自然言語処理や形式文法、パーサの構築に興味がある人
- 「Lean = 証明支援」というイメージはあるが、プログラミング用途も覗いてみたい人
この記事でやること
CCG の簡易的パーサを Lean 4 で実装します。CKY ライクなアルゴリズムでチャートパースをして、導出木を列挙します。
Lean でのプログラミング上のポイントは以下の通りです。
-
inductiveやinfixで DSL 的な表記や AST (抽象文法木) を自然に作れる -
Option/List/HashMapとdo構文 /for/let mutで、探索 + DP を素直に書ける
CCG の概要
CCG は、単語に「範疇 (Category)」を割り当てて、「組合せ規則」により文を構成する単語や語句の範疇の合成を繰り返し、最終的に範疇
範疇
範疇は語句の統語的な役割を示すラベルです。証明支援系になじみがある人には、ある種の型もしくは命題だと思うとよいです(Lambek 計算)。
範疇は、基底範疇と関数型範疇からなります。
- 基底範疇 :
,N ,NP など (直感的にはそれぞれ、名詞、名詞句、文に相当)S - 関数型範疇 : 二つの範疇を演算子
,/ で結合したもの\backslash
例 : ,NP/N ,S\backslash NP などS\backslash NP/NP
関数型範疇については直感的には次のようにとらえるとよいです。
-
を持つ語句は、右にNP/N が来ると合成されてN になる (例 : 冠詞)NP -
を持つ語句は、左にS\backslash NP が来ると合成されてNP になる (例 : 自動詞)S
なお、演算子
組合せ規則
隣接して並ぶ複数(もしくは単一)の範疇を組み合わせて、新たな範疇を作る規則です。
代表的なものを以下に示します。
- 順関数適用 [>]
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
これらの範疇を組合せ規則で組み合わせて、文の範疇を導出していきます。導出木を自然演繹での証明図の記法を用いて次のように表せます。

CCG での "Keats eats apples" の範疇の導出
まず、"eats" の範疇
なお、"Keats eats apples" には次のような別導出も存在します。

CCG での "Keats eats apples" の範疇の別導出
こちらでは、"Keats" の範疇
このように、同じ文(語・語句)に複数の導出があり得る(曖昧性)のが、CCG の特徴のひとつです。
CCG パーサの実装
CCG パーサを実装していきます。
全体のコードは下記リンクの Lean Playground で動かせます。Playground の下のほうで、
#eval parse lexicon1 "Keats eats apples"
のように打つと、"Keats eats apples" をパースした導出木の一覧が infoview に表示されます。
全体構成
プログラムの全体的な構成は以下の通りです。コード中 section でブロック分けしています。
- Utility : トークン分割や文字列補助
- Category : 範疇 Cat の定義
- Rules : Binary/Unary 規則 (関数適用、合成、型繰り上げ)
- Tree : 導出木 Tree の定義
- Applying : 木に規則を適用して新しい木を生成
- Parsing : CKYライクなアルゴリズムでチャートを埋める
- Example : 実行例
0. Lean でプログラムを書くための Tips
Lean でプログラミングするときに知っておくとよい Tips を挙げておきます。
-
#evalはその場で実行評価できる-
#eval <term>で評価結果を表示できる - 型を
ToStringのクラスインスタンスとしておくと表示をカスタマイズできる
-
-
inductive/structure/abbrevでデータ定義する-
inductive: 列挙型・再帰データ (AST など) -
structure: レコード -
abbrev: 型エイリアス
-
-
OptionとListで探索を書くとよい- 失敗は
noneにする - 複数候補は
Listを使う -
map/flatMap/filterMapと組み合わせて「列挙+失敗除去」を自然に書ける
- 失敗は
-
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 で定義する
まず、関数型範疇を構成するときの演算子 Dir を inductive を使って定義します。
/-- 関数適用の向き -/
inductive Dir : Type
| Fwd -- /
| Bwd -- \
deriving BEq
deriving BEq により == が使えるようになります。組合せ規則適用で「範疇が一致するか」を見るのに必要になります。
範疇を表す型を Cat として定義します。inductive によって、基底範疇(
/-- 範疇 Cat -/
inductive Cat : Type
| S
| NP
| N
| Fun : Dir → Cat → Cat → Cat -- 関数型範疇 x/y or x\y
deriving BEq
例えば Cat.Fun .Bwd .S .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 関数合成規則
今回は
順(一般化)関数合成規則[>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 \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"] を考えます (トークン長

"Keats eats an apple" のチャート
チャートは「開始位置
各セルの導出木は、そのセルを頂点とするピラミッドの下の部分の導出木を使うことによって構築することができます。例えば、セル
したがって、一番下層
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 は、
/-- 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 風のアルゴリズムでチャートを埋めていきます。大まかにやることは次の通りです。
-
:span = 1 - 各トークン
tについて、範疇辞書lexから leaf を作る - leaf に unary 規則を適用した木を追加
- 各トークン
-
: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
組合せ規則により範疇の導出を行うことで、図のように意味の合成も自動的に行われ、最終的に文全体の意味を表すラムダ式(論理式)
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 でのプログラミングに取り組んでみてください。
おすすめの参考図書
- 戸次大介,「日本語文法の形式理論 ー活用体系・統語構造・意味合成ー」, くろしお出版 (2010)
日本語 の CCG を意味論も含めて構成しています。難しいところも多々ありますが、日本語を CCG で徹底的に解析できるようにしてやろうという気概が感じられて大変面白いです。 - 鶴岡慶雅 (著), 宮尾祐介 (著), 奥村学 (監修) 「構文解析 (自然言語処理シリーズ)」, コロナ社 (2017)
タイトルの通り構文解析の教科書です。CKY 法も含めて様々なアルゴリズムが説明されています。CCG についての記述もあります。
Discussion
#eval について
どちらかというとevalに使われるのはReprです。ToString とは用途が異なります。