感想文・エッセイの草稿置き場をNotionに作りました。
星にゃーんの掌編集の没案とかも置くかも。
星にゃーんの掌編集はこちら。
Notionは、使い勝手が良く、便利です。今まではiOSのメモとScrapboxを使ってたんですが、文書を構造化できない（メモ）、スマホからの操作感が良くない（Scrapbox）など不満がありました。Notionは今のところ、これらの不満を解消できていそう。
夢と勇気と変身ベルト
一番古い記憶は、変身ベルトのCMだ。
物心ついたときから憧れだった。仮面ライダーそのものより、変身ベルトが好きだった。 ファイズギアとブレイバックルを買ってもらった。四六時中巻いていた。 夢中で仕組みを調べていた。カードのバーコードを目で読もうとしていた。 でも、もう捨ててしまった。
夢が無かった。なりたいものも、叶えたいことも無かった。 それで良かった。無くて構わないと知っていた。 夢が無くとも、誰かの夢の妨げにはならない。 どこかの誰かが代わりに夢を抱くなら、それだけで十分だった。
勇気が無かった。これはちょっとまずかった。 しかし良かった。悪いことをするよりは、何も為さないほうがずっとマシだ。 勇気が無くても、誰かの勇気を咎めることはしない。 これを読んでいるあなたが勇気を振り絞るなら、それで報われるはずだった。
変身ベルトは捨ててしまった。もう必要のないものだから。 これで良かった。幻想の時間は終わり、確かな地面が僕の礎となった。 ベルトがあっても、誰かを殺すのが関の山だ。 あれは夢と勇気を抱く幼子の、思いを叫んで輝くのだろう。
いつか思い出すと分かっていた。 亡くしたものが蘇るとき、僕の命は始まるのだろう。 ずっと先だと思っていた。すべてが止まった、その後だと。
ところがどうだろう。辺りを照らすのは夢の灯りだ。 身体を動かす勇気の炎が、再び燃える音がした。
一度止まった心臓が、過去の記憶に目を覚ます。
夢と勇気と変身ベルト。
Haskellのsomeを正格評価したら無限ループする話
パーサコンビネータなんかでよく使う、 some と many という関数があります。それぞれ引数を１回以上/０回以上実行して結果のリストを返す関数で、これの単純な定義は
some v = (:) <$> v <*> many v many v = some v <|> pure []
となります。 some は v : (many v) 、 many は some v または [] を返すイメージです。
パーサコンビネータでは、例えば英数字１文字以上の文字列をパースしたいとき some alphaNum と書いたりします。
面白いのは、一見とても自明に思えるこの定義は、遅延評価がないと無限ループしてしまう点です。 本当は v が失敗したら some v 自体が失敗してほしいところが、v が失敗するか否かに関わらず many v が実行されてしまいます。正格評価の気持ちで考えるとあたりまえですが、Haskellに慣れてるとびっくりするかもしれません。僕はびっくりしました。
Haskell風の正格評価な言語であるPureScriptでは、 some の定義がちょっと違います。
some v = (:) <$> v <*> defer (\_ -> many v)
many v の実行が v が成功するか失敗するかわかるまで遅延されています。こうすれば正格評価な言語でも無限ループすることはありません。
他にもHaskellには「遅延評価だからこの書き方できるけど、正格評価だと動かないな〜」となるケースが多く、Haskellプログラムを自作言語に移植するときにハマりまくってます（マイナーな悩みだ…）
今回のsomeとmanyのケースも、自作言語Malgo(https://github.com/malgo-lang/malgo)に移植した際に気づきました。
many : Parser a -> Parser (List a);
many = { v -> some v <|> pure Nil };
some : Parser a -> Parser (List a);
-- many v が必ず実行されてしまい、無限ループになる
some = { v -> Cons <$> v <*> many v };
-- PureScriptの例と同様に、many vの実行を明示的に遅延させる
some = { v -> Cons <$> v <*> defer { many v } };
ヘビ兄ちゃん
我が家では時々、「怪人たる資格」の話が始まる。
仮面ライダーの登場人物には、怪人かどうか判断が難しいキャラクターがいる。仮面ライダー1号は、ショッカーによって生み出された改造人間だ。
もっと直接的に、怪人への変身能力を持つ者もいる。例えばオーズの火野英司のように。この話はいつも、同じところに着地する。「ヘビ兄ちゃんは怪人なのか、仮面ライダーなのか」
ヘビ兄ちゃんとは、仮面ライダーファイズに登場するキャラクター、海堂直也のことだ。我が家では彼をそう呼ぶ。ヘビ兄ちゃんは露悪的な性格で、大仰な身振りと陽気な態度の、単純だが底の見えない男だ。そして、蛇の力を持つ怪人スネークオルフェノクへの変身能力を持つ。つまり、彼は怪人だ。
オルフェノクは人間ではない。死から甦り、人間を超える種として生まれ変わった生命だ。繁殖のための本能を抱えている。人間を殺せという心の叫びを。
この意味で、ヘビ兄ちゃんは特殊だった。人を殺そうという気をおくびにも出さなかった。
ヘビ兄ちゃんはギターを弾いて、いた。しかし、今の彼には指先の感覚がない。昔のように音楽を奏でることはできない。音楽の夢は彼の中で呪いとなった。奏でられることのない音楽が彼の心を掻き乱している。
この呪いと化した夢の残骸が、「殺せ」と叫ぶ声を掻き消している。ヘビ兄ちゃんは夢を絶たれ、呪いを背負い、生きている。彼は怪人なんだろうか。
夢に生きる人に、怪人たる資格はあるんだろうか。
初出はこのツイートです。
蛇兄ちゃん #星にゃーんの掌編集 pic.twitter.com/s364TtGy66
— 星にゃーん (@takoeight0821) 2021年8月3日
2進数も16進数も10進数
コンピュータに詳しい人は、しばしば1024とか65536みたいなへんてこな偶数を指して「キリが良い」という。
なぜかと言えば簡単なことで、1024は2進数で書くと0b10000000000で、16進数だと0x400になるからだ。 「0b」と「0x」はそれぞれ、続く数字が2進数（Binary）、16進数（heXadecimal）であることを表す。
コンピュータの中では2進数や16進数をよく使うから、こういう数字は「キリが良い」。 ゲームでレベルが255でカンストしたり、どんなにがんばってもダメージが65535を越えなかったりするのも、数値の最大の桁数を2進数や16進数で考えて決めてるからだ。
困ったことに、桁数の扱いを間違えると1 - 2 = 255みたいな不思議な計算が行われる。 これはオーバーフローと呼ばれる典型的なバグの一種で、温厚な性格のAIが突然ブチギレて周囲に喧嘩を売りまくるみたいなことが起きる。 「シヴィライゼーション」の有名なバグ「核ガンジー」がまさにこれだ。
2進数が3進数や42進数を差し置いてここまでみんなに愛されているのは、コンピュータが2進数をベースに作られているからだろう。 0と1をスイッチのONとOFFに割り当てれば、大量のスイッチを高速でパチパチする機械を作れば計算ができる。 このスイッチの化け物が、友だちと話したり本を読んだりして暇を潰すのに最適な道具だとわかったのは、 間違いなくここ数十年の人類文明で最大の発見だ。
ところで、この2進数というのは機械が扱うには便利なのだが、人間が読み書きするとなるとかなり不便だ。 例えば、日本の人口はだいたい120,000,000人らしいが、これを2進数で書くと0b111_0010_0111_0000_1110_0000_0000となる。 4桁ごとに_を挟んで読みやすくしてはみたが、桁数が大きすぎて紙に書くのも大変そうだ。
そこで登場するのが16進数である。 16進数は、2進数との相互変換がとても簡単だ。 2進数を4桁ごとに区切って、4桁ごとに16進数の1桁へ変換すればいい。逆もすぐにできる。慣れれば暗算できるほどだ。 そして、人間にとっても読み書きしやすい。ちょっと慣れは必要だが。 そういうわけで、16進数は2進数を人間が扱うときに役立つ。
さっきの人口の例だと、こんな感じになる。
- 10進数 120000000
- 2進数 0b111001001110000111000000000
- 16進数 0x7270E00
2進数や16進数は便利だが、10進数に慣れきった私たちは彼らのことを誤解しやすい。 特に、コンピュータと絡むとひどいことになる。
よくあるのは、例えばこんなCのプログラムの一行があるときに
int max_level = 0xFF;
「max_levelを16進数から10進数に変換したいんだけど、そんな関数ググってもでてこないんだよね。 10進数で書いた文字列に変換する関数は山ほど見つかったんだけど。」
彼がどんな誤解をしているか、わかるだろうか。
そりゃそうなのである。16進数だろうが10進数だろうが、数値は変わらない。変わるのは数字だけである。 16進数か10進数かが問題になるのは、人間が読み書きするときだけで、コンピュータは数値を扱っているだけだから、 「16進数を10進数に変換する」なんて処理はナンセンスだ。 （もちろん例外はある。気になる方は「二進化十進数」でググってみよう。）
こういう誤解が起こるのは、「2進数」という言葉の使い方に問題があるかもしれない。
〜数と名のつくものを考えてみよう。 自然数、整数、有理数、実数、複素数など、数の体系を表す言葉がたくさんある。
では、2進数も数の体系なのだろうか？いかにもそう思える。（これは同意を得られないかもしれない） しかし、そうではない。 「2進数」は、「2進記数法で書かれた数」であり、本質は「記数法」つまり書き方の話なのだ。
ここまで、知っている人にとってはあたりまえのことを書いてきた。 私自身、あたりまえだと思っている。
そして、同じくあたりまえでよくネタにされることについて書いて本稿を終える。
あなたはヒューマノイドタイプの宇宙人だ。アルファ・ケンタウリあたりに住んでおり、 板状の計算機械を用いて、惑星を覆う通信網を通してブログを読んだり動画を見たりしている。 そして、あなたは右手に8本の指を、左手にも8本の指を持っている。あなたにとってはあたりまえのことである。
さて、あなたは計算機科学の講義で計算に困ったことがない。 なぜならあなたは10進数を使っており、計算機も10進数を使うからだ。 正確には2進数らしいが、4桁ごとに区切って考えればいいだけだから問題はない。
ところが、少し困ったことがある。 太陽あたりに留学することになったのだが、その星では日常生活でA進数を使うらしいのだ。 なんてめんどくさいんだ。彼らはなぜ罰ゲームみたいな生活をしているのだろうか。 あっちにも計算機はあるんだから、10進数を使えば楽なのに。
Malgo開発記録：型シノニムとimport
はじめに
この記事は『第39回 #hiro_it』と『プログラミング言語処理系が好きな人の集まり 第３回定期ミートアップ』での発表資料を清書したものです。
『プログラミング言語処理系が好きな人の集まり』は、
です。
prog-lang-sys-ja-slack.github.io
『#hiro_it』は、
#hiro_itは広島で開催する学生向けのITコミュニティです．
です。
型シノニム
Malgoには、型の別名（型シノニム）を定義する機能があります。
type MyInt = Int32 type MyTuple a = (a, a)
このように型シノニムを定義すると、MyIntとInt32が同じ型として扱われます。
MyTuple MyIntは(MyInt, MyInt)であり(Int32, Int32)です。
型シノニムの実装にバグがあったというのが今回の最初の話題なのですが、その前にすこしMalgoの型検査について説明します。
Malgoの型推論のしくみ（簡単に）
Malgoは型推論を持ちます。例えば、
let x = (1, 2)
と書くと、xの型は(Int32, Int32)と推論されます。
addOne = { x -> x + 1 };
と書くと、addOneの型はInt32 -> Int32と推論されます。
addOneを例に、型推論の動作をざっくり述べると、
addOneの型を仮にαと置くxの型を仮にβと置くaddOne = { x -> ... }から、α ~ β -> γ（αとβ -> γは同じ型）だとわかるx + 1から、β ~ Int32とγ ~ Int32がわかるα ~ β -> γ,β ~ Int32,γ ~ Int32を解いてaddOne :: Int32 -> Int32,x :: Int32がわかる
Malgoの型シノニムのしくみ（バグってた）
型シノニムの（バグってた）実装では、α ~ β -> γなど型制約に加えて、MyInt ~ Int32を含めて解くことで実現していました。
この実装の問題点を明らかにするために、xの例を考えます。
let x = (1, 2)から、x :: (Int32, Int32)だとわかります。
そして、x :: MyTuple Int32やx :: MyTuple MyIntでもあってほしいわけです。
つまり、MyTuple α ~ (α, α)を含めて解かなければいけません。
(α, α)は、内部的にはTuple2 α αのような型として表されています。
MyTuple α ~ (α, α)はMyTuple α ~ Tuple2 α αという制約になります。
この制約は、~の左辺と右辺で項数が異なるため、簡単には解けそうにありません。
どうやら型シノニムを型制約として表すのは無理があるようです。（もしかしたらいいやり方があるかもしれませんが、見つけられませんでした）
結局、型制約を解く前に、型シノニムをすべて展開するように変更して解決しました。
(Int32, Int32) ~ MyTuple MyIntを(Int32, Int32) ~ (Int32, Int32)に展開すれば、この型制約の解は自明です。
「型シノニムは事前に展開する」というのは考えてみれば自然で簡単なんですが、 あんまり型シノニムを扱った型検査器の実装の話が見つからなくて苦労しました。 （結局GHCとかのコードを読んだ）
モジュール
Malgoはプログラムを分割するための機能としてモジュールを提供しています。 雰囲気としてはJavaのpackageと同じです。
今までのMalgoでは、例えばモジュールMainからPreludeをインポートしたいときには
module Main = {
import Prelude;
...
}
と書いていました。
今までのMalgoでは、import Prelude;と書くと、Preludeで定義されているすべての型・関数がMainの中に展開されたかのように振る舞います。これは明らかに不便です。例えば、同じ名前の関数を定義しているモジュールを複数インポートすると名前衝突を起こしてしまいます。
新しいimport文
importたるもの、「どの型・関数をインポートするか」ぐらいは指定できるようになっていて欲しいものです。 そこで、import周りの構文を大規模に改修して、こんな構文を定義しました。
module { putStrLn, appendString } = import Prelude;
こう書くと、putStrLnとappendStringのみがインポートされます。
また、
module {..} = import Prelude;
と書くと、今まで通りPrelude内のすべての型・関数がインポートされます。
（..を選んだのは、「省略している」雰囲気を重視したものです。Haskellのレコード展開の構文に影響を受けた気もします）
module P = import Prelude;
と書くと、P.putStrLnのように、モジュール名.名前とモジュール名のプレフィックスをつけることで参照できるようになります。
イメージはJavaScriptのrequireです。
名前解決のテーブルの設計
実装にあたって問題になったのは、名前解決のテーブルの設計でした。 今までは、
{ main -> [Main.main],
putStrLn -> [Prelude.putStrLn],
appendString -> [Prelude.appendString]
}
のような連想配列を使って、mainが出てきたらMain.mainに置き換え、putStrLnが出てきたらPrelude.putStrLnに置き換え……という実装でした。
Mainモジュール内でappendStringが定義されたら、
{ appendString -> [Main.appendString, Prelude.String] }
のようにエントリの先頭に新たな識別子を追加し、リストの先頭にあるものへ優先して置き換えることで、シャドウイングを実現していました。
しかし、新たなimportでは、P.putStrLnをPrelude.putStrLnに置き換えるような処理が必要になります。
そこで、
module { appendString } = import Prelude;
module P = import Prelude;
のとき、
{ main -> [implicit Main.main],
putStrLn -> [explicit as P Prelude.putStrLn],
appendString -> [implicit Prelude.appendString]
}
のように、「プレフィックスなしで参照できるか(implicit/explicit)」、「どんなプレフィックスで参照するか(as P)」をエントリに加えて、この情報をもとに名前解決するようにしました。
……と、ここまで書いて気づいたんですが、単に
{ main -> Main.main,
P.putStrLn -> Prelude.putStrLn,
appendString -> Prelude.appendString
}
としたほうが単純ですね。
まとめ
- 型シノニムの実装のバグを直しました
- import文をより便利にしました
地味なバグと誰かの囁き声
最近（ここ数年？）malgoというプログラミング言語を作ってる。
今日、地味なバグを見つけた。厳密にはバグじゃない気もするんだけど、ユーザーの直感に反するような挙動をする。
例えば、Eitherを定義するとする。
data Either a b = Left a | Right b;
すると、これを読んだコンパイラは、内部的に以下のような定義を型の辞書に追加する。
data Either b a = Left b | Right a;
aとbが逆転してる。いかにも単純で地味なバグだ。
なぜこんなことが起こるのかというと、（ここからややこしい解説が始まるので適当に読み飛ばせばよい）malgoコンパイラが内部的に管理している型辞書の型変数名は、元のソースコードとは独立に決まるから。コンパイラは単に名付けるべき型変数の集合を求めて、適当な方法でリストに変換して、そのリストの先頭から順にa,b,c,...と名付けていく。「適当な方法」が集合{t1, t2}をリスト[t2,t1]にしたために、直感的にはaと名付けられるべきだったt1がbになり、bになるはずのt2がaになる。
とりあえず、「適当な方法」のところでソートをかけることで見た目だけは直した。 だが、これはまったく解決にはなっていない。本当に実装すべきなのは、「名付けるべき型変数の集合Sと、Sのそれぞれの要素tとその元となったソースコード上の型変数aの連想配列Eが与えられた時、Sの要素すべてにEに基づく名前をつけたもののリストLを返すアルゴリズムF:(S,E)->L」。 （ややこしい解説ここまで）
つまり、これは簡単に解決する地味なバグではなく、コンパイルエラーのUXに関わるかなり重大なバグだった。単に集合をリストにしたものをソートするだけではダメだった。
ということについさっき、23時ごろ気づいた。ソートでとりあえず直した風なコミットをしたのが15時。そういえば、List.sortと書いたとき、脳裏に「ソートする意味は？本当にソートしたいの？」と囁く声が聞こえた気がする。
コードを書いていると、こういう囁き声が聞こえることがある。多分囁いているのは僕のプログラマとしての直感そのものなんだろう。今までの経験から、長期的（1時間ぐらい）にはこの囁きに従った方が良く、短期的（10分ぐらい）にはこの囁きを無視した方がいいことが分かってる。
短期的目標が片付く前に囁きに惑わされると、差分がどんどんぐちゃぐちゃになっていって、コード自体もぐちゃぐちゃになる。後片付けのリファクタリングはかなり大変だ。
一方で、長期的には、今回のように鋭い指摘であることが多い。しかし、1時間も経てば、たった一度の囁きなんてすぐに忘れてしまう。これはまずい。都度コメントにメモを取るのが良さそうだ。 -- TODO: ソートする意味は？ちゃんと考える みたいに。でもこういうTODOって大抵放置されて、バグが発覚した時に、その爆心地で見つかるんだよな〜。
