謎
夏休みに関数型言語でも勉強してみようかと思い、よく分からないので国産 ML の SML# というのを選んでみました。
座学
- 総合的感想:特殊な規則や場合分けが多い問題に適している気がしました。
倒叙的て明晰でない説明がなされる末尾再帰ですが、要するに JMP Label0001 もしくは goto 1 のようなジャンプ型の構造で、しかも唯一の構造なのだと思いました。
末尾再帰のようなジャンプ構造で DO LOOP を実現しようとすると、ループ変数等の本来隠蔽されるべき変数を関数の引数としてあらわに外部に晒す必要が出てきます。それを包む外側の関数を書いて本来の引数のみにするのですから、ローカル変数宣言を内側の関数の引数で代用している形になっています。(終端値を兼用する形をとることが多いようですが)
また型と演算のファンクターを言うなら、初めに整数型や文字型などを出す前に、単なるビット列の集合を出して、同一のビット列を複数の解釈でみて(多価写像として整数や実数や文字列として解釈して)同一の演算子で演算した結果がそれぞれ異なるビット列に移されるという話にした方が、型がビット列の解釈と演算を規定するという意味がはっきりして分かりやすい気がしました。
一番よく分からないのが、はじめの方で全順序集合としてのリスト構造が、暗黙裡に導入されて前面に出てくるところです。一般論としては、まず順序のない集合を出して、それに色々な位相構造を導入して見せるという形で話が進んだ方が分かりやすい気がしました。その位相構造の一つが一次元リストの全順序集合で、次が二進木などの半順序束構造という感じに・・・
ところが、いきなり全順序リスト構造が断りもなしに出てきますし、整数と同型な構造であることもいつの間にか持ち出してくるので、とりあえずわかりやすい例としてリスト構造を出しているのか、それともリスト構造がコンピュータ用言語として固有の重要性を持つものなので、初めから出してきているのかが判断しづらく、謎としか言いようがなく感じました。
たとえば数学的帰納法が必須というならば、全順序集合が必須ということになってくる気もしますが、読んでる私としてはコンピュータのメモリ番地が一次元的になっていることをモデル化して全順序一次元リスト構造を出しているのかと思って読み進んでいました。結局どうなのかは未だにわかりません。
また全順序集合を基本にループ構造を再帰による漸化式構造にしたため、配列の代入のように本来順序によらない並行動作までもが順序に依存した形になることもよくないと思いました。Fortran では20年前からこれらを区別して別々の表現で書くような方向へ進んでいて、別々の直観的イメージを持てるようになっています。
無論漸化式の形でも場合によっては並行動作に直せるので、その説明がグダグダとなされますが、それは80年代ベクトル計算機用の Fortran コンパイラでも使われていた回帰(再帰)演算の定式化に過ぎないのに、関数型言語の説明と渾然一体に入り混じって出てきて本質が見分けにくくなっているように思いました。
Foldr は、Fortran の世界では多項式計算のところで必ず出てくる Honer 法そのものですが、群論で出てくる半直積とも同じ形だなと思いました。
実践
とりあえずガウスの掃き出し法でも書いてみるかと思いましたが、配列の取り方が分からず挫折。次に Fortran で書いたシダ植物でも移植しようかと思いましたが、今度はバイナリファイルの I/O がよく分からなくてまたもや挫折。一応備忘代わりに、以下に断片をメモしておきます。
バイナリファイル読み込み
# val f = openIn("shida.bmp");
val f = _ : TextIO.instream
# inputN(f, 2);
val it = "BM" : string
# inputN(f, 4);
val it = "�q\v\^@" : string
# String.explode(w);
val it = [#"\230",#"q",#"\v",#"\^@"] : char list
# val e = it;
val e = [#"\230",#"q",#"\v",#"\^@"] : char list
# val (x1::x2::x3::x4) = e;
(interactive):83.5-83.23 Warning: binding not exhaustive
:: (x1, :: (x2, :: (x3, x4))) => ...
val x1 = #"\230" : char
val x2 = #"q" : char
val x3 = #"\v" : char
val x4 = [#"\^@"] : char list
# val y1 = ord x1;
val y1 = 230 : int
# val y2 = x2;
val y2 = #"q" : char
# val y3 = ord x3;
val y3 = 11 : int
# hd x4;
val it = #"\^@" : char
# val x4 = it;
val x4 = #"\^@" : char
# val y4 = ord x4;
val y4 = 0 : int
# y1 + 256 * (y2 + 256 * y3);
val it = 750054 : int
# y1::y2::y3::y4::nil;
val it = [230,113,11,0] : int list
# val p = y1::y2::y3::y4::nil;
val p = [230,113,11,0] : int list
# val int4 = foldr (fn (x, y) => x + 256 * y) 0;
val int4 = fn : int list -> int
# int4 p;
val it = 750054 : int
なんとかバイナリファイルを少しだけ読みこんで、リトルエンディアン整数にすることに成功したところで時間切れ終了。あとは BMP データを書き込む配列を学べば何とかなる?
n個の1バイト符号なし整数のリストを引数として、nバイト符号なしリトルエンディアン整数を返す関数。
sml
val to_int = foldr (fn (x, y) => x + 256 * y) 0