ウクレレのコードを見つけるプログラム [OCaml]
ウクレレやギターのようなコードを弾く弦楽器では同じコードを弾くのにも何通りもの押さえ方が存在します。
ウクレレで C のコード（C, E, G の3音）を鳴らす場合を例にとりましょう。ウクレレには4本の弦があり、何も押さえない状態では1弦から4弦まで順に A, E, C, G の4つの音を出します。A の音はCコードの構成音ではないので1弦の3フレットを押さえます。これにより1弦から出る音は A から3つ (A->Bb->B->C) シャープした C の音になって C, E, C, G の音が出るわけです。
一方で1弦7フレットを押さえても C のコードと見なせます。A から7つ分シャープすると A->Bb->B->C->C#->D->Eb->E となり、鳴る音は E, E, C, G となります。これも C, E, G で構成されるのでCのコードと言えるのです。
このような何通りもの押さえかたは一番高い音を何にしたいかといった理由などで使い分けますが、市販の教則本等のコード一覧に押さえ方としても載っているのはそのうちの代表的な1つか、コードブック的なもので各々3つくらいです。タブ譜などを見ながら押さえ方の難しいコードが出てきて「もうちょっと楽な押さえ方はないのか？」というときに自分で編み出すのはなかなか大変ですので自動で計算するプログラムを OCaml で書いてみました。
まずは型定義です。音名をヴァリアント型で定義します。
type tone = C | Db | D | Eb | E | F | Gb | G | Ab | A | Bb | B
これは整数で表現したほうが演算（シャープするとかフラットするとか）ができていいという考え方もあるかもしれませんが、今回のプログラムでは特に不要だったのでヴァリアント型にしました。異名同音（C#とDbとか）はすべてフラットのほうの書き方にしていますが、これはヴァリアント型のコンストラクタに記号が使えないためです。
次にいくつかタイプエイリアスを定義します。
type chord = tone list type position = tone * int type string_ = position list type form = position list type state = form * string_ list
実を言うと実際に後で型注釈とかをして使うわけではないのですが、一応気分の問題で定義しておきました。コード chord は音名を集めたものです。ポジション position は何フレット目を押さえると何の音が出るかを示しています。弦 string_ はポジションを1列に並べたものです。フォーム form は各弦のどのポジションを押さえてコードを鳴らすかを表現します（要素数4つのリストです）。state がよくわからないと思いますが、これは後で説明します。以下、型を説明するときはこれらを使います。
次にウクレレの4つの弦を表現するデータを定義します。
let rec iota m n = if m = n then [n] else m :: iota (m + 1) n let a_string = List.combine [A; Bb; B; C; Db; D; Eb; E; F; Gb; G; Ab] (iota 0 11) let e_string = List.combine [E; F; Gb; G; Ab; A; Bb; B; C; Db; D; Eb] (iota 0 11) let c_string = List.combine [C; Db; D; Eb; E; F; Gb; G; Ab; A; Bb; B] (iota 0 11) let g_string = List.combine [G; Ab; A; Bb; B; C; Db; D; Eb; E; F; Gb] (iota 0 11) let strings = [a_string; e_string; c_string; g_string]
これは以下のような構造を作っています。(note * int) list list は気分としては string_ list です。
# strings;; - : (note * int) list list = [[(A, 0); (Bb, 1); (B, 2); (C, 3); (Db, 4); (D, 5); (Eb, 6); (E, 7); (F, 8); (Gb, 9); (G, 10); (Ab, 11)]; [(E, 0); (F, 1); (Gb, 2); (G, 3); (Ab, 4); (A, 5); (Bb, 6); (B, 7); (C, 8); (Db, 9); (D, 10); (Eb, 11)]; [(C, 0); (Db, 1); (D, 2); (Eb, 3); (E, 4); (F, 5); (Gb, 6); (G, 7); (Ab, 8); (A, 9); (Bb, 10); (B, 11)]; [(G, 0); (Ab, 1); (A, 2); (Bb, 3); (B, 4); (C, 5); (Db, 6); (D, 7); (Eb, 8); (E, 9); (F, 10); (Gb, 11)]]
ここでは11フレットまでしか用意しませんでしたが、もちろんもっと用意してもかまいません。
ユーティリティ関数として (A, 0) などのポジションと [C; E; G] というコードが与えられたときに A がコード [C; E; G] の構成音かどうかを判定する関数を用意しておきます。position -> chord -> bool です。
let is_chord_tone (tone, _) chord = List.mem tone chord
今回のコード探索プログラムは「クロージャを作成して、そのクロージャを呼び出すたびにコードフォームの候補を次々返してくれる」というものにします。そのクロージャは unit -> form で、呼び出す度に [(G, 0); (C, 0); (E, 0); (C, 3)] とか [(G, 0); (C, 0); (E, 0); (E, 7)] を返してくれるイメージです。
クロージャを作り出すための関数を次のように定義しました。
let create_form_finder strings chord_to_find filters = let agenda = Queue.create () in let rec find () = let state = Queue.take agenda in match state with | (form, []) -> if List.for_all (fun p -> p form) filters then form else find () | (form, (position :: string) :: strings) -> if (is_chord_tone position chord_to_find) then (Queue.push (position :: form, strings) agenda; Queue.push (form, string :: strings) agenda; find ()) else (Queue.push (form, string :: strings) agenda; find ()) | (_, [] :: _) -> find () in Queue.push ([], strings) agenda; find
まず引数です。
let create_form_finder strings chord_to_find filters =
strings : string_ list には先ほど定義した strings を与えます。変則チューニングにも対応できるように引数にしました。chord_to_find : chord は見つけたいコードです。filters : (form -> bool) list は検索するコードフォームをフィルタリングする条件を与えます。複数指定できるようにリストにしました。
let agenda = Queue.create () in
agenda : state Queue.t には探索中の状態が入ります。state は type state = form * string_ list と定義しましたが「これまでに押さえたポジション * まだ押さえていない弦」という意味になります。
let rec find () =
let state = Queue.take agenda in
match state with
コード探索クロージャの中ではまず agenda から状態をひとつとって、その状態の内容で進み方を決めます。
まず「すでに全ての弦を押さえていて、コードフォームになっている」という場合です。
| (form, []) -> if List.for_all (fun p -> p form) filters then form else find ()
この場合、フィルタリング条件を適用して OK だったらコードフォームを返します。だめだったら探索を続けます。
次のケースはまだ全ての弦を押さえていない途中のケースです。
| (form, (position :: string) :: strings) ->
このケースは「残りの最初の弦の一番低いポジション」がコードの構成音かどうかで場合分けします。
if (is_chord_tone position chord_to_find) then
(Queue.push (position :: form, strings) agenda;
Queue.push (form, string :: strings) agenda;
find ())
構成音だった場合「そのポジションを押さえる」か「そのポジションは押さえずにもっと高いポジションを押さえるか」という2通りの行き先があります。これは先の C コードの例で言うと1弦3フレットが構成音だけど3フレットを押さえるか、もっと先（7フレット）を押さえるかというようなことです。1つ目の push は押さえるほうの分岐で、フォームにポジションを追加して残りの弦を減らします。2つ目の push は押さえない判断で、フォームはそのままで弦の最低ポジションを捨てます（次のフレットが次回 agenda から取られるときの最低ポジションになります）。
else
(Queue.push (form, string :: strings) agenda;
find ())
構成音ではなかった場合はフォームはそのままで弦の最低ポジションを捨てます。
| (_, [] :: _) -> find ()
今回の定義では各弦について11フレット目までしかポジションを定義していないので、最低ポジションを捨て続けて11フレットまでを使い切ったら「詰み」になります。
in Queue.push ([], strings) agenda; find
初期状態として「まだどこも押さえていなくて4弦すべて残っている状態」をキューに入れ、クロージャを返しています。
とりあえずこの状態で使ってみましょう。
# let find = create_form_finder strings [C; E; G] [];; val find : unit -> (note * int) list = <fun> # find ();; - : (note * int) list = [(G, 0); (C, 0); (E, 0); (C, 3)] # find ();; - : (note * int) list = [(G, 0); (C, 0); (G, 3); (C, 3)] # find ();; - : (note * int) list = [(G, 0); (E, 4); (E, 0); (C, 3)] # find ();; - : (note * int) list = [(G, 0); (C, 0); (E, 0); (E, 7)]
1弦3フレットを押さえる C や 1弦7フレットを押さえる C を見つけてくれています。一方で2つ目の結果のように C と G だけで E が入っていないフォームも結果に含まれています。「完全なコード」だけを検出するように追加条件を指定したいと思います。
let is_complete_chord chord form = let tone_included tone = List.exists (fun (t, _) -> t = tone) form in List.for_all tone_included chord
これを指定すると次のような結果になります。
# let find = create_form_finder strings [C; E; G] [is_complete_chord [C; E; G]];; val find : unit -> (note * int) list = <fun> # find ();; - : (note * int) list = [(G, 0); (C, 0); (E, 0); (C, 3)] # find ();; - : (note * int) list = [(G, 0); (E, 4); (E, 0); (C, 3)] # find ();; - : (note * int) list = [(G, 0); (C, 0); (E, 0); (E, 7)]
不完全なコードを除外してくれるようになりました。なお「最初から不完全なコードを除外するように create_chord_finder を書けばいいのでは？」と思うかもしれませんが、ウクレレでは不完全なコードを使うことも結構あるため（例えば D7=D+F#+A+C のコードに対して A+F#+C+A で押さえることも多い）、追加条件で指定する仕様にしました。
ところで、コード検出を続行すると次のようなフォームを検出します。
# find ();; - : (note * int) list = [(G, 0); (G, 7); (E, 0); (C, 3)] # find ();; - : (note * int) list = [(G, 0); (E, 4); (G, 3); (C, 3)] # find ();; - : (note * int) list = [(G, 0); (C, 0); (G, 3); (E, 7)] # find ();; - : (note * int) list = [(G, 0); (C, 0); (E, 0); (G, 10)] # find ();; - : (note * int) list = [(C, 5); (G, 7); (E, 0); (C, 3)] # find ();; - : (note * int) list = [(E, 9); (C, 0); (G, 3); (C, 3)]
3フレット目と9フレット目を同時に押さえるというのは無理ですね。3と7もすこし遠いかもしれません。押弦している最低フレットと最高フレットの差を3フレットまでに限定してみます。
let is_possible_form form = let non_open = List.filter (fun (_, fret) -> fret <> 0) form in match non_open with | [] -> true | _ :: [] -> true | (_, fret) :: ps -> let (min_, max_) = List.fold_left (fun (min_, max_) (_, fret) -> (min min_ fret, max max_ fret)) (fret, fret) ps in (max_ - min_) < 4
この条件を追加すると11フレット目までの全ての C コードは以下のとおりとなります。
# let find = create_form_finder strings [C; E; G] [is_complete_chord [C; E; G]; is_possible_form];; val find : unit -> (note * int) list = <fun> # find ();; - : (note * int) list = [(G, 0); (C, 0); (E, 0); (C, 3)] # find ();; - : (note * int) list = [(G, 0); (E, 4); (E, 0); (C, 3)] # find ();; - : (note * int) list = [(G, 0); (C, 0); (E, 0); (E, 7)] # find ();; - : (note * int) list = [(G, 0); (E, 4); (G, 3); (C, 3)] # find ();; - : (note * int) list = [(G, 0); (C, 0); (E, 0); (G, 10)] # find ();; - : (note * int) list = [(C, 5); (E, 4); (G, 3); (C, 3)] # find ();; - : (note * int) list = [(G, 0); (C, 0); (C, 8); (E, 7)] # find ();; - : (note * int) list = [(C, 5); (G, 7); (E, 0); (E, 7)] # find ();; - : (note * int) list = [(E, 9); (C, 0); (E, 0); (G, 10)] # find ();; - : (note * int) list = [(G, 0); (G, 7); (C, 8); (E, 7)] # find ();; - : (note * int) list = [(C, 5); (G, 7); (C, 8); (E, 7)] # find ();; - : (note * int) list = [(E, 9); (C, 0); (C, 8); (G, 10)] # find ();; - : (note * int) list = [(E, 9); (G, 7); (C, 8); (E, 7)] # find ();; - : (note * int) list = [(E, 9); (G, 7); (C, 8); (G, 10)] # find ();; Exception: Queue.Empty.
「はい/いいえ」、「○/×」、「真/偽」 [自然言語]
ある会社の経理担当と「中小企業の会計に関する指針」の適用に関するチェックリストのことで大喧嘩である。
「営業上の債権のうち破産債権等で１年以内に弁済を受けることができないものがある場合、これを投資その他の資産の部に表示したか。」という確認事項があって、○か×かでチェックを入れなければならない。
その会社には「営業上の債権のうち破産債権等で１年以内に弁済を受けることができないもの」が無かった。
（中略）
だからここは「○」にするのが正しいと私はその会社の経理担当に言った。
http://d.hatena.ne.jp/yaneurao/20090927#p1
自然言語のシンタクスを論理学の意味論を使って（構文要素を対応させて）解釈すると自然言語の話し手が意図し（また聞き手が解釈し）ている意味とずれが生じていることがある（だがそのずれには何らかの法則があるはずだからそれを解明しよう）―というのが言語学的語用論の出発点だ。そういう例はたくさんある。例えば自然言語の "or" や「または」は論理和と解釈される場合と排他的論理和と解釈される場合がある、とか。
上記もそうした例の一つといえる。面白い例なので私も少し考えてみたところ、問題は自然言語（日本語）の「はい/いいえ」が論理学の「真/偽」とは異なっていること、そして「○/×」が状況によっては「はい/いいえ」とほぼ同義なものとして使われていること（だがそう感じない人もいるようであること）にあるのではないかと思った。（ちなみにこのトラブルで誰に非があるかという裁定には興味はない）
例文を少しわかりやすいものに変えたい。あなたは家を出るときに忘れ物をすることが多いので、これを防止するために外出時のチェックシートを作って運用することに決めた、ということにしよう。チェックシートにはチェック欄があり、チェック欄すべてを「レ」で埋めたら玄関を出ることができる。
家を出る前に以下をチェックせよ
・携帯電話を持った （ ）
・財布を持った （ ）
・雨が降っている場合、傘を持った （ ）
携帯を持ち、財布をもち、雨が降っておらず、傘を持っていない場合、すべての空欄に「レ」を付けることに殆どの人は躊躇しないだろう。何しろ全てチェックしないと出かけられないわけだし。携帯を持ち、財布をもち、雨が降っておらず、しかし傘を持っている場合も「レ」をつけるだろう。雨が降っていて傘を持った場合も。しかし雨が降っていて傘を持っていなければ傘を手にするまで「レ」を付けないに違いない。つまり我々はここで「論理学的」に考えている。「雨が降っている場合、傘を持ったか」は「P→Q」の解釈と同じで、「レ」は「真」を意味する。
続けて次の例を考えよう。あなたは家を出るときに忘れ物をすることが多いので、外出時に同居人に確認の質問を毎回してもらうように頼むことにした。あなたは携帯を持っており、財布を持っており、雨は降っておらず、傘を持っていないとしよう。同居人は布団の中から声をかけており、外で雨が降っているかどうか知らない。
同居人「携帯電話は持った？」 あなた「はい」
同居人「財布は持った？」 あなた「はい」
同居人「雨だったら傘は持った？」
多分最後の質問に対する答えは「いや（傘は持っていない）。でも雨はふっていないから」とか、「いや、雨は降っていない（だから傘を持つ必要はない）」になるだろう。おそらく殆どの日本語話者の言語的直観はこの状況で単に「はい」と答えることを自然と感じないはずだ。もし答えるとしたら、それは忙しい朝のやり取りを短く終わらせるために無害な嘘をついてみた（「はいはい」）といったところだろう。
では先のチェックシートが以下のような形をしており、「レ」ではなく｢○/×」を記入する運用だった場合はどうか。
・携帯電話を持ったか （○・×）
・財布を持ったか （○・×）
・雨が降っている場合、傘を持ったか（○・×）
雨が降っていなくて傘を持っていないときに「○」を付けることに、さっきより違和感を感じるのではないだろうか。このことは「○/×」が「真/偽」よりは「はい/いいえ」に近いという認識からくるものだと思う(*1)。「持ったか」という疑問文にしたことでその解釈への志向も強まっている。
最後に元の例に戻ろう。この例は自作の忘れ物防止チェックシートとは異なり、他人に対して回答するものである（と思う。たぶん）。この状況は先ほどの同居人の例にさらに近づく。そして「○」により強い違和感を覚えるのがたいていの人の反応だろうと思う。「○/×」でなく「はい/いいえ」で回答する方式だったらさらに違和感は増すのではないだろうか。
以上のまとめ。対話的状況での「はい」は条件節を含む疑問文の後件を肯定する強い傾向がある。次のスケールで左に行くほど成立状況が限定される。
はい ＜ ○ ＜ レ
対話 ＜ 非対話
*1 「はい/いいえ」よりも解釈に個人差があるとしたら、「はい/いいえ」は通常の日本語の語彙として自然に習得するのに対して「○/×」はもっと「後天的」に習得しているからかもしれない。
Semantics with Applications を読んで denotational semantics について知る (1)
これからの一連のエントリは私が "Semantics with Applications" (Nielson & Nielson) の第5章 "Denotational Semantics" を読みながら記録を残していくものです。注意点としては別に翻訳ではないし、理解に間違いを含むかもしれません。この本の第1版はウェブで読めるので怪しいぞと思ったらそちらを参照されるとよいでしょう。
http://www.daimi.au.dk/~bra8130/Wiley_book/wiley.html
Scala から Gainer mini を使う [Scala]
このところマイコンを使った電子工作に興味を持ち始めました。電子工作をやっているといっても理科の知識は中学生未満だし半田付けもできるだけ避けたいという軟派な感じのものですが。
マイコンとしては主にPICという電子工作によく使われている廉価なものを使っていて、アセンブラかCで書いたプログラムをマイコンのフラッシュメモリに書き込むのですが、ちょっとした実験のために使い捨てプログラムが必要になることがあります。しかしそうしたプログラムをいちいちアセンブラやCで書いてライターで書き込むのは面倒くさい。多少の制約（時間的な精度とか）は受け入れても超高級言語が使いたい、と思うことがあります。
そこで Gainer mini [http://gainer-mini.jp/] というデバイスを買いました。これはPCとUSBケーブルで接続され、電子回路上の電圧の制御や読み取りがPC上のプログラミング言語から行えるようにパッケージ化されたものです。フィジカルコンピューティングデバイスというカテゴリに含まれるものですが、その言葉の意味はともかくとして、これを使うと電子回路の頭脳の部分を回路上のマイコンから外に出してPC上に移すことが出来ます。
プログラミング言語として公式には Flash+ActionScript、Processing、Max/MSP が使え、私はまず Processing を使ってみたのですが、いろいろと言語やライブラリに対する不満が出てきたため、Scala から使うためのライブラリを作ってみました。
まずは単純な使用例です。Gainer mini に LED を2つ（dout 0,1）、押しボタンスイッチを1つ（din 0）、ツマミ（可変抵抗）を1つ（ain 0）取り付けます。
この回路を使って、「周期的に LED を点滅させる。点滅周期の長さはツマミで制御し、スイッチが押されていないときは dout 0 につながった LED を、押されたときは dout 1 につながった LED を点滅させる。Gainer のオンボードスイッチが押されたら終了」ということをするプログラムを Scala で書きます。
val gainer = Gainer("COM3")
try {
gainer.open()
while (!gainer.button) {
val led = if (gainer.din(0)) 0 else 1
val interval = gainer.ain(0)
gainer.dout(led) = true
Thread.sleep(interval)
gainer.dout(led) = false
Thread.sleep(interval)
}
} finally {
gainer.close()
}実行結果です。（動画です）
以下がライブラリのソースコードです。Gainer mini のライブラリが使っているのと同じ RXTX というシリアル通信用の Java ライブラリを使っています。RXTXcomm.jar を Scala の lib ディレクトリに、rxtxSerial.dll（Windows 前提で話していますが）をパスの通った場所においてください。
チェック例外の特徴を整理する [Java]
Java を勉強していてエキゾチックだと感じるのはやはりチェック例外だ。このチェック例外という仕組みは、便利か邪魔か、ということはひとまず置くとしてやはり非常に興味深いものだと思う。そんな Java のチェック例外を自分なりに理解しやすいように整理・言い換えをしてみた。（これも前回と同様にかなり雑な内容だと思いますがとりあえずあきらめて記事にしてしまいます）
まずメソッドの throws 節に書かれる例外クラスを戻り値の型と比べてみよう。戻り値の型は実際に return される型と不整合があるとコンパイルエラーになる。同様に throws 節の例外クラスと実際にメソッドから投げられうる例外との間に不整合があるとコンパイルエラーになる。
いずれもメソッドのクライアントに対する契約の一部をなしているから、宣言された型より小さい型を実際に返す/投げる分には構わないが逆は不可である。例えば Object m() throws Exception {} は String を返したり IOException を投げたりできるが、String m() throws IOException は Object を返したり Exception を投げたりできない。（なお、この記事では継承関係にあってサブクラスに向かうほど小さい、逆を大きいと呼ぶ。≦と≧に対応する不等号として <: と >: を使う）
また、メソッドがサブクラスでオーバーライドされるとき、オーバーライドするメソッドの throws 節にはオーバーライドされたメソッドの throws 節と同じか、それよりも小さい型を指定しなければならない。例えば throws Exception を throws IOException でオーバーライドできるが、逆は不可である。これは Java1.5 からは戻り値についても同じである (covariant overriding)。逆に言うと例外には昔から covariant overriding があったともいえる。
戻り値とチェック例外の類似点は一応ここまでである。チェック例外は戻り値とは異なり互いに継承関係にない複数の型を指定することができる。
throws IOException, ClassNotFoundExceptionという宣言は IOException か ClassNotFoundException を投げるかもしれないが、例えば（同様に Exception の直接のサブクラスである）InterruptedException は投げないという約束になる。一方で戻り値の型は1つだけだ。
ちなみに「互いに継承関係にない」と断り書きをつけたのはもし継承関係にあればその大きいほうのクラスに包摂できるからで throws Exception, IOException というのは throws Exception というのと同じことである。
「一応ここまで」と書いたのは、次のように捉えなおすことで例外と戻り値の型とのアナロジーを引き続き維持しようという企みからである。
戻り値の型とは別に、そして例外クラス（とその階層）とも別物として、メソッドの「チェック例外に関する型」（およびその階層）を考える。これを仮に「throws の型」と呼ぶことにする。「throws の型」は単に継承関係にない例外クラスの集合として表現される型である。{IOException, ClassNotFoundException} のように表記することにする。
throws の型は次のような規則で階層をなす。
(1) 2つの throws の型が包含関係にあるとき、部分集合のほうの型のほうが小さい。したがって throws IOException, ClassNotFoundException を throws IOException でオーバーライドできる。
(2) また、throws の型の要素の一部を例外クラス階層においてより小さいものに置き換えるとより小さい型になる。したがって throws IOException, ClassNotFoundException を throws FileNotFoundException, ClassNotFoundException でオーバーライドできる。
例外クラスの階層と throws の型の階層の間の関係をいくつか例をあげて示す。
チェック例外のクラスが A, B, C の3つしかなく、以下の継承関係にあるとき、
throws の型の階層は以下のようになる。
こうなる。
例外のクラスが A, B, C, D の4つで以下の継承関係にあるとき、
throws の型の階層は以下のようになる。(*)
例外の階層が以下だったら、
こうなる。
これらは全部プログラムで出力しているのできちんと変換方法を定義できるが、大雑把にいうとまず例外クラスをメンバとする全ての集合の包含関係で階層を作り、それを例外クラスの階層に基づいて正規化すると throws の型階層ができる。（TODO: throws の型階層が必ず lattice であることを示したい）
あらゆる throws の型に対して下にくる (bottom) のが空集合からなる型である。つまりどんなメソッドでも throws を書かないメソッドでオーバーライドできる（勿論 final でなければ）。あらゆる throws の型に対して上に来る型 (top) は例外クラスのルート一つだけからなる集合として構成できる（上の例ではすべて {A}）。これは例外クラスがツリー階層をなす（top を持つ）ということからくる効用である。
このように throws の型を定義するとオーバーライドについて先ほどと同じ言い方を維持できる。オーバーライドするメソッドの throws 節にはオーバーライドされたメソッドの throws 節と同じか、それよりも小さい型を指定しなければならない。
話はここで終わりではない。インターフェイスが関与する場合は複数のメソッドをオーバーライドするということがありうるので、それら全ての throws の型に対して下に来るような型でなければならない。さっきの (*) を付けた図でいうと throws C と throws B, D をオーバーライドするメソッドは throws D か例外を投げないメソッドでなければならない。
throws の型の階層では2つの要素から下に辿ったときに最初に出会う地点が1つだけ決まる (meet) ので「この型と同じか、それより小さい型」という風に単一の型を使って表現できる。今の例だと「{D} か、それより小さい型」だ。
次に、throws 節に指定する型はメソッド本体の定義からも制約を受ける。メソッド本体はその実装から「こういう例外を投げうる」ということを求めることができる。Java の仕様書では "possible result" とか "can throw ..." （...は例外クラス）とかいう言葉で表現されているが、やや見通しの悪い書き方になっているので throws の型の観点から再構成してみよう。
メソッドがどんな例外を投げうるかを定式化することを考える。関数型言語などでは式の型は（日本語で書くと）以下のような規則（ML 風文法を想定）を定義して型を推論したり検査したりする。
・式 a が型αで式 b が 型βのとき、式 a; b の型はβ
・式 f が型α→βで式 a が型αのとき、式 (f a) の型はβ
・式 c が型 bool で式 t と式 f がともに型αのとき、式 if c then t else f の型はα
このやり方を throws の型に適用すると以下のようになるだろう。なお、以下でα∨βは「αとβから上に辿っていって最初に出会うところ」(join) を意味するものとする（throws の型については「和集合をとって正規化」にだいたい対応）。
・文 a が型αで文 b が型βのとき、ブロック {a; b} の型はα∨β
・式 a が型αでメソッド b が型βで式 C が型γのとき、式 a.b(c) の型はα∨β∨γ
・式 a が型αでブロック b が型βでブロック C が型γのとき、文 if (a) {b} else {c} の型はα∨β∨γ
などなど。
以上から throws の型の特徴として次のようなことが観察できる。先ほどの ML 風文法のための規則は式の組み合わせ方について型の制約を追加で課していた。これに対して throws の型は統語的な組み合わせにはまったく影響を与えない。
たったいま述べた観察に対する唯一の例外は try/catch である。（finally と catch 節複数の場合は省略）
・ブロック a が型αでブロック b が型βのとき、文 try {a} catch (E id) {b} の型は γ∨β。ただしγは{E}>:αのとき{}、それ以外のときγ∨{E}={E}∨αとなるような最小の型で、γ=αとなるときエラー
「ただし」以降は結構考えた末にこうなったけどまだ考慮漏れがあるかもしれない。「γ=αとなるときエラー」が「投げられるはずがない例外をキャッチしてはいけない」に対応している。[2008-10-28追記]もうちょっと良く考えてみると{E}>:αのとき「γ∨{E}={E}∨αとなるような最小のγ」は「γ∨{E}={E}となる最小のγ」で {} だ。だから場合わけは不要だった。こうなってみるとこの定義は Java の仕様書よりもずっといい感じだ。
こうした規則に基づいてメソッド本体の throws の型（「こういう例外を投げうる」）が求まる。メソッドの throws 節にはこうして求まった型と同じかそれより大きい型を書かなければならない。
というわけで「throws の型」という概念を導入したことによりメソッドの throws 節に書くことが許される型 T について、
「T は U 以下で L 以上のものである（ただし U はオーバーライドされる型全ての meet で、L はメソッド本体の型）」
という言い方で述べることができるようになった。
さて、throws 節に書いていい型の範囲はわかった。ところで実際にメソッドのオーバーライドをして、そのメソッド本体の throws の型がオーバーライドされるメソッドの型より小さいとき、どちらを選択する（まあ中間という選択肢はないだろうから）のが慣習として好ましいのだろう。
例えば void m() throws Exception というメソッドをオーバーライドして、メソッド本体は実際には FileNotFoundException しか投げえない場合、オーバーライドする側のメソッドには throws FileNotFoundException と書くべきだろうか、それとも throws Exception と書くべきだろうか。
サブクラスを利用するクライアントに対してより informative なのは前者のほうである。しかしこのクラスをさらに継承する側の実装者に対してより高い自由度を与えるのは後者である。こういうケースには定説があるのだろうか（例えば Effective Java みたいな本に書いてあるとか）。
covariant なコレクションと構造的型付けの話
前回の記事で言及した「structural な型付けしか存在しないオブジェクト指向言語」についてまだ少し考えていました。この記事はあまり裏をとっていない話が混じっているので注意して読んでください（誤りだと思ったら指摘してほしいです）。
最初に Scala の話を一つ。
Scala で immutable で covariant なコレクション、例えば List を使うと、空の状態では要素の型は Nothing になっていて、異なる型の要素を追加するにつれて Any に近づいていく。
scala> class A defined class A scala> class B extends A defined class B scala> class C extends B defined class C scala> class D extends B defined class D scala> class E extends D defined class E scala> class F extends E defined class F scala> val list1 = List() list1: List[Nothing] = List() scala> val list2 = new F :: list1 list2: List[F] = List(F@158aeed) scala> val list3 = new E :: list2 list3: List[E] = List(E@e964fe, F@158aeed) scala> val list4 = new C :: list3 list4: List[B] = List(C@9403a3, E@e964fe, F@158aeed) scala> val list5 = 123 :: list4 list5: List[Any] = List(123, C@9403a3, E@e964fe, F@158aeed)
ここで List[E] に C を追加すると List[B] と型推論される。この B は E と C という2つのクラスから上に辿っていって初めて出会う地点 (join) だ。クラス階層はツリーだからそういう地点は必ず1つ存在し、1つしかない。ここで E と C の共通の祖先 (upper bounds) としては B の他にも A や A から Any までの間のクラスがあるのだが、いきなり上にいくと不便だからそのうちの一番下のものが選ばれる (least upper bound)。
trait を含む型の階層はツリーではないから話は少し複雑になる。
scala> trait T defined trait T scala> trait U defined trait U scala> trait V defined trait V scala> class X extends B with T with U with V defined class X scala> trait W defined trait W scala> class Y extends D with T with U with W defined class Y scala> val list6 = new X :: list1 list6: List[X] = List(X@13e86ec) scala> val list7 = new Y :: list6 list7: List[B with T with U] = List(Y@30380, X@13e86ec)
trait を含む型の階層構造において、型は継承関係によって順序づけられるが、任意の2つの型を取り上げたとき、それらは継承関係にあるかもしれないしないかもしれないという、それ以上の性質は期待できない (partially ordered set) 。
この例では X と Y の共通の祖先には A, B, T, U （および A から Any までのクラス）があるが、結果の要素型として推論される型は祖先の集合の「底」に来る要素すべて (minimal elements) を足したものになる。すなわち B, T, U になる。 クラスだけを考えたときは「任意の2つの型を取り上げて上に辿ると、どこか1地点で出会う」という性質を期待できた (join semilattice) から、この中にクラスは1つしか存在しない。そのクラスを with の左に持ってきて残りの trait を右に持ってくれば B with T with U となる。
ちなみに何も継承していない trait を関与させると共通の祖先のない例が作れそうに思えるが、Scala の型推論ではそういう場合は実は ScalaObject with SomeTrait と見なされるようだ（エラーにはならない）。
scala> List[U]() ::: List[T]() res6: List[ScalaObject] = List()
と、ここまでが前置き。空想上の「structural な型付けしか存在しないオブジェクト指向言語」ではクラスは単にメソッドのシグニチャの集合であって、名前があるとしたら単にエイリアスでしかないものとする。この言語のクラス階層では「任意の2つの型を取り上げて上に辿ると、どこか1地点で出会う」が成立し、さらに逆方向（下向き）でも成立する (lattice)。これは集合の包含関係がそうであるというのと全く同型である。
この言語にも Scala のように covariant な型付けをするコレクションがあると考える。メソッドとして a と b と c しか定義されていないとしよう。そうすると例えば {a, b, c} list という型のリストに {a, b} 型の要素を追加したら {a, b} list に、{a, b} list に {b, c} を追加したら {b} list になるはずだ。{a, b} list に {c} を追加したら {} list になるのだろう。
さて空のリストの型は何から始めたらいいのだろうか。上に上っていくわけだから、最初はクラス階層の一番下 (bottom element) でなければならない。クラスはメソッドのシグニチャの集合でしかないという定義から、メソッドとして a, b, c があれば {a, b, c} list で a, b, c, d だったら {a, b, c, d} list ということになる。だけどプログラム内すべてを見渡して定義されたメソッドの情報がすべて分からないと空リストの型が決まらないというのはどうもおかしい。
というわけで「プログラムでクラスがどう定義されようがすべてのクラスに対して一番下に来るクラス」を導入する必要性が出てくる。Scala の Nothing 型も存在するすべてのクラスを持ち上げる (lifting) ようなクラスだった。
ところでこのクラスは「メソッドのシグニチャの集合」には還元できない。だからこの型だけは名前によって直接名指されなければならない。
さて structural な型付けのオブジェクト指向といえば OCaml だけど、この辺どうなっているのだろうか。
# let list1 = [];; val list1 : 'a list = [] # let list2 = object method a () = () method b () = () end :: list1;; val list2 : < a : unit -> unit; b : unit -> unit > list = [<obj>] # let list3 = object method a () = () method c () = () end :: list2;; This expression has type < a : unit -> unit; b : unit -> unit > list but is here used with type < a : unit -> unit; c : unit -> unit > list Only the first object type has a method b
あれ－。
じゃあリスト自作で、と思ってクラス定義について調べると Scala 同様に variance の指定はできるようなんだけど Nothing 相当についてはどうしたらいいのか？
2008-10-13追記:図を作成して挿入したJava における直列化と型 [Java]
このところめっきりプログラミングをしていないのだけど、最近は SJC-P の教科書を買って Java を勉強していて、直列化周りの言語仕様に興味と疑問が湧いた。
Java ではクラスが Serializable インターフェイスを implements すると ObjectOutputStream とかを使ってシリアライズできるようになる。この Serializable インターフェイスは実装すべきメソッドというものがない空のインターフェイスであって、これはマーカーインターフェイスと呼ばれる。
まずこのマーカーインターフェイスというのがちょっと興味深い。これは単にこの名前のインターフェイスを implements しているということだけに意味があるものだ。例えば nominal な型付けというものが全くなくて structural な型付けしか存在しないような静的なオブジェクト指向言語を考えてみると、そういう言語ではマーカーインターフェイスの居場所が無い。だからマーカーインターフェイスの用途すべてが他の仕組みに還元できるわけではないということが示せれば nominal な型付けを完全放棄してはいけない根拠の一つになるかもしれない。
次に疑問点として、何故 ObjectOutputStream#writeObject の引数は Serializable obj ではなくて Object obj なのだろうか、ということを思った。
writeObject は Serializable でないオブジェクトを受け取ると実行時エラーになる、つまりマーカーインターフェイスのマーカーは実行時に利用されているわけだけど、引数を Serializable にすると現在手に入るコンパイラの仕組みでこれをコンパイルエラーにすることができる。もっというと Serializable を implements したクラスのすべてのフィールドが直列化可能な型であるということも、やろうと思えばコンパイル時チェックできるのではないだろうか。
後半はともかく前半に対する反論を考えてみると、たまたま Object 型（や Serializable を implements していないクラス）の変数に入っているオブジェクトが実際には直列化可能だとわかっている場合（サブクラスで Serializable を implements していて、そのクラスのインスタンスである）を救えないことになってしまう。
…と思ったのだけど、そう状況ではしょうがないのでキャストすればいいのではないだろうか。一般に Serializable にキャストできないのかとも思ったけどそうでもないようだ（変換元が final でなければ可能）。その場合 NotSerializableException が ClassCastException になるだけの違いで、「キャストを使わない限りはコンパイル時に検出可能」という線までは前進できる。
それともそこまで前進しても現実的な使用では意味がないのだろうか。ひょっとしたら何か根本的な思い違いをしているような気もするけど釈然としない。
Java の本当の発明について [Java]
それはいいとして、本当に Java の発明になるものがないかといえば実はあって、「チェック例外」というものがそうだ、と思ったのだけどこれは間違ってるでしょうか。
もうひとつ、Java 以降に現れた言語で Java のチェック例外を真似した言語はない、という気もするのだけど、これは本当でしょうか。（C# には？）
