星にゃーんのブログ

ほとんど無害。

継続渡し・コールバックを読みやすくする言語機能たち（Koka・Gleam・Roc）

継続渡しスタイル、あるいはコールバック関数は非常に強力なテクニックだ。 例えばJavaScriptでは、非同期処理を扱う.thenメソッドが有名どころだろう。

fetch("http://example.com/movies.json")
  .then((response) => response.json())
  .then((movies) => console.log(movies))

継続渡しスタイルは読みにくい。そこで、JavaScriptではasync構文が導入されている。

const response = await fetch("http://example.com/movies.json");
const movies = await response.json();
console.log(movies);

awaitの振る舞いは、以下のような読み替えルールがあると考えると理解しやすい。

const X = await P; E;
=>
P.then((X) => E);

awaitは、継続渡しスタイルの非同期プログラムを、あたかも直接スタイルかのように書くための言語機能だ、と解釈できる。 プログラミング言語の中には、より汎用的に継続渡しスタイルを直接スタイルに変える言語機能を持つものがある。

Kokaには、with構文がある。 例えば、1から10までの整数を標準出力に書き出すKokaプログラムは以下のようになる：

list(1,10).foreach(fn (x) {
  println(x)
})

with構文を使うと、以下のように書ける。

with x <- list(1,10).foreach
println(x)

withの読み替えルールは以下のようになる：

with X <- F(A, ...)
E
=>
F(A, ..., fn (X) { E })

Kokaの名前は日本語の「効果」に由来する。その名が示す通り、Kokaは代数的効果（Algebraic effects）をサポートしている。 代数的効果はざっくり言えば「すごく高機能な例外」だ。例えば、以下のKokaプログラムは、0除算エラー（raiseエフェクト）を起こしうる関数divideを定義している。

fun divide( x : int, y : int ) : raise int
  if y==0 then raise("div-by-zero") else x / y

raiseの振る舞いを自由に後づけできるのが代数的効果の特徴だ。次のプログラムは、例外をもみ消して定数42に評価されたものとする。handler構文で各エフェクトの実装を与えている。次のプログラムは最終的に50を返す。

(hander {
  ctl raise(msg) { 42 }
})(fn () {
  8 + divide(1, 0)
})

hander {...}は、エフェクトを起こしうる処理をコールバック関数として受け取る関数になっている。 コールバック関数を受け取るということはつまり、withを使うともっとスマートに書ける。

with handler { ctl raise(msg) { 42 } }
8 + divide(1, 0)

Gleamにも同様の振る舞いをするuse構文がある。 Use - The Gleam Language Tourから、useを使ったコード例を引用する：

pub fn without_use() {
  result.try(get_username(), fn(username) {
    result.try(get_password(), fn(password) {
      result.map(log_in(username, password), fn(greeting) {
        greeting <> ", " <> username
      })
    })
  })
}

pub fn with_use() {
  use username <- result.try(get_username())
  use password <- result.try(get_password())
  use greeting <- result.map(log_in(username, password))
  greeting <> ", " <> username
}

result.tryは、成功か失敗を表すresult値と、成功したなら実行されるコールバック関数を受け取り、最初の引数が成功値ならコールバックを適用、失敗値ならそれをそのまま返す。 use構文はKokaのwithと同様の振る舞いをするので、with_use()のような書き方ができる。

RocはHaskellに似た軽量な構文を持つプログラミング言語だ。 Rocで標準入出力を扱うプログラムを書くと、以下のようになる。

main =
    await (Stdout.line "Type something press Enter:") \_ ->
        await Stdin.line \input ->
            Stdout.line "Your input was: $(Inspect.toStr input)"

awaitはJavaScriptのそれとは異なり、単なる関数である。第一引数に実行したいタスクを、第二引数にタスクの結果を処理するコールバック関数を取る。\input -> ...は無名関数だ。

Rocでは、<-を使って継続渡しスタイルを直接スタイルに書き換える。

main =
    _ <- await (Stdout.line "Type something press Enter:")
    input <- await Stdin.line

    Stdout.line "Your input was: $(Inspect.toStr input)"

JavaScriptに見られるasync構文は、様々な言語で導入されている。 いくつかの言語では、より柔軟な形でasyncのような構文を定義できるようになっている。 例えばF#ではcomputation expressionが、Haskellではdo構文とモナドが使われている。 これらの言語機能は強力な反面、言語への導入に少々ハードルがある。

async構文が本当にやりたいことは継続渡しスタイルを直接スタイルのように書くことだ、と思うと、もっと単純な解決策がある。それがKokaのwithやGleamのuse構文だ。 あるいは、withやuseと同じように、async構文は継続渡しスタイルに立ち向かうための道具だ、という見方もできる。

継続モナドで立ち向かうローンパターンとEither地獄

Haskell 技術メモ

Haskellでファイルなどのリソースの解放を保証するテクニックとして、ローンパターン（Loan Pattern）がある。withFile :: FilePath -> IOMode -> (Handle -> IO r) -> IO rなどがその例だ。 ローンパターンによる関数を複数使ったプログラムは、無名関数のネストが深くなる。

main = do
  withFile "src.txt" ReadMode \src ->
    withFile "dst.txt" WriteMode \dst ->
      ...

この問題には、継続モナドContTを使ったきれいな解決策が知られている。

main = evalContT do
  src <- ContT $ withFile "src.txt" ReadMode
  dst <- ContT $ withFile "dst.txt" WriteMode
  ...

ミソは、ContTを使うことで、継続渡しスタイルをdo記法に変換できるところにある。

このアイディアを更に深堀りしてみよう。 設定ファイルを読み込みパースする関数parseConfigと、Configのあるフィールドを取得する関数getFieldがあるとする。 設定ファイルを読み込んでフィールドlanguageを取得し、アプリケーションの言語を変更する処理は次のように書ける。

parseConfig :: MonadIO m => FilePath -> m (Either String Config)
getField :: MonadIO m => Config -> m (Either String Value)

updateLanguage :: (MonadIO m, MonadState Env) => m ()
updateLanguage = do
  ecfg <- parseConfig "app.cfg"
  case ecfg of
    Left err -> error err
    Right cfg -> do
      elang <- getField cfg "language"
      case elang of
        Left err -> error err
        Right lang -> modify \env -> env { language = lang }

LeftとRightのパターンマッチが繰り返されている。 こういう地獄に落ちると人は「おお神よ！try-catch構文はどこへ行ってしまったのです！」という気分になり、ExceptTなどの例外モナドを使ってparseConfigとgetFieldを書き直したくなる1。 書き直せるなら万々歳だが、悪しきparseConfigがすでにコードの深いところまで根を張っていて、そう簡単には修正できないことも多い。

ContTは、こんなときに助けになる。まずは、継続渡しスタイルを使ってupdateLanguageを書き換えよう。

updateLanguage :: (MonadIO m, MonadState Env) => m ()
updateLanguage = do
  with (parseConfig "app.cfg") \cfg ->
    with (getField cfg "language") \lang ->
      modify \env -> env { language = lang }

with :: Monad m => m (Either String a) -> (a -> m (Either String b)) -> m (Either String b)
with m k = do
  ea <- m
  case ea of
    Left err -> pure $ Left err
    Right a -> k a

（サラッと書いてしまったが、こういう書き換えは難しい。コツを掴めるまでしばらくかかるが、できるようになると色々便利。）

これでLeftとRightのパターンマッチを一つにできた。あとはContTを使ってdo記法に戻せばいい。 withをContTでラップしよう。

updateLanguage :: (MonadIO m, MonadState Env) => m ()
updateLanguage = evalContT do
  cfg <- with (parseConfig "app.cfg")
  lang <- with (getField cfg "language")
  modify \env -> env { language = lang }

with :: Monad m => m (Either String a) -> ContT (Either String b) m a
with m = ContT \k -> do
  ea <- m
  case ea of
    Left err -> pure $ Left err
    Right a -> k a

ややこしいコードを上手く継続渡しスタイルに落としこめれば、ContTを使ったシンプルなdo記法にリファクタリングできる。 ContT自体が少々ややこしいので乱用は禁物だが、うまく使えば最小限の変更でプログラムがグッと読みやすくなる。

参考文献

追記というか余談

haskell - Monadic function of `(a -> m (Either e b)) -> Either e a -> m (Either e b)`? - Stack Overflowによると、withはもっと抽象化できるらしい。

with :: (Monad m, Monad f, Traversable f) => m (f a) -> ContT (f b) m a
with m = ContT \k -> do
  x <- m
  join <$> traverse k x

このwithはMaybeにも対応している。対応しているが、ちょっとやりすぎな気もする。

  1. 例えばparseConfig :: (MonadIO m, MonadError String m) => FilePath -> m Config。モナドを使うときはmtlスタイルで書くようにすれば地獄行きをある程度防止できる。Eitherが例外モナドであることを失念しないように気をつけよう。↩

星にゃーん2022

2022年ももう終わりです。というわけで、今年のまとめをします。

1月

久々に大学に行ったら声かけられてびっくりしました。

2月

機界戦隊ゼンカイジャー、良かったっすね。

3月

こういうことがよくあります。

4月

ロックマンエグゼのアニメを見ました。

5月

シン・ウルトラマンを見ました。

6月

この夢は叶います。

7月

タローマンを見ました。

8月

ゼノブレイド2をやりました。

9月

大学を卒業しました。

10月

仮面ライダーBLACK SUNを見ました。

11月

ポケットモンスタースカーレットをやりました。

12月

Inscryptionをやりました。

ロボット心理学的見地からみる『アイの歌声を聴かせて』

注意：この文章には『アイの歌声を聴かせて』のネタバレが含まれます。また、筆者はノベライズ版の感想文としてこの文章を書きました。ノベライズ版での描写が前提となっています。あとなぜか半分ぐらいアシモフの『われはロボット』の話してます。

『ロボット工学ハンドブック』だけはいつも肌身離さず持っていた。

ロボット工学の三原則。

第一条　ロボットは人間に危害を加えてはならない。また、その危険の看過することによって、人間に危害を及ぼしてはならない。

第二条　ロボットは人間にあたえられた命令に服従しなければならない。ただし、与えられた命令が、第一条に反する場合は、この限りではない。

第三条　ロボットは、前掲第一条および第二条に反するおそれのないかぎり、自己を守らなければならない。

子供の頃、初めてこれを読んで衝撃を受けた。ロボットの発展と、人類の抱えるフランケンシュタイン・コンプレックスの双方を解決する優しいルールだ。

二十世紀中葉の電子計算機の目覚ましい発展も、陽電子頭脳の発明により過去のものとなった。真空管やリレーは今もマニアの間で根強い人気を誇るが、一般に受け入れられているのは人間の脳ほどの大きさのスポンジ状プラチナイリジウムの合金である。

二十世紀が終わる頃に生まれた私は、ほかの多くの若者と同じように、計算機科学、今では〈ロボット心理学〉として知られる分野を志した。はずだった。

現実には〈ロボット心理学〉が生まれることは無かった。我々の時間軸では、陽電子頭脳の代わりにトランジスタが発明された。極小のパーツを組み合わせた集積回路により、〈コンピュータ〉が作成された。一足とびのズルは許されなかったのだ。ロボット工学三原則を現実の計算機に普遍的に適用する方法は未だ明らかになっていない。今はまだその必要すらもない。

一方で、想像の中でロボットは自由に歌い踊っている。1940年に生まれた子守りロボットのロビィと少女グローリアの友情は、場所を変え形を変え、今も続いている。『アイの歌声を聴かせて』もまた、人間のような知能と人間とは思えない知性を併せ持つロボットと、翻弄されながらも彼らとの友情を信じる人間の物語だ。

主人公・天野悟美の通う高校へ、一人の転校生がやってくる。彼女の名前は芦森詩音。その正体は悟美の母親・美津子が開発した「人工知能搭載人型ロボ」である。ロボットが高校生として振る舞えるかどうかをテストする、いわゆるウォズニアックテストが秘密裏に行われていた。標準的な高校生として振る舞うようプログラムされたはずの詩音は、なぜかミュージカルの登場人物かのように芝居がかった振る舞いを見せ、あらゆる場面で歌を歌う。そして、なぜか「悟美を幸せにすること」にこだわる。

作中のAI技術は、我々の世界よりはるかに進歩している。あらゆる家電製品は人の言葉を解し、自らに与えられた命令を忠実に実行する。しかし、人間と見分けのつかないロボットは未だ現れていない。芦森詩音は真のロボットの第一世代といえる。

驚くべきことに、物語は「もしも、人間のように振る舞うロボットが転校してきたら」と問いかけない。物語の原動力になるのは「なぜ、芦森詩音は歌うのか」という疑問であり、あくまで芦森詩音のパーソナリティにフォーカスする。

詩音がロボットであることに付随する問題は、すべて悟美の幼馴染・素崎十真により解決される。彼はいわゆるコンピュータオタクであり、作中で最も「ロボットの心理」に精通している。アシモフの著作でいうところの〈ロボット心理学者〉である。十真は詩音の行動原理—悟美を幸せにする—をいち早く理解し、ロボットが直感的に理解できる論法を用いて的確に詩音と対話する。

彼の活躍により、「なぜ、芦森詩音は歌うのか」という問いかけが明確になる。作中の問題がロジカルに解決するのであれば、詩音の歌もただの演出ではありえない。そこには明確な理由があるはずだ。十真もそう考え、一人答えを探し続ける。

ロボット心理学の観点から考えると、ロボットの不可解な行動は、大抵の場合そのロボットへ与えられた最初の命令に起因する。詩音の場合を考えてみると、実地試験のために彼女へ与えられた最初の命令は「高校生として振る舞うこと」であるはずだ。しかし、詩音の行動原理は「悟美を幸せにすること」である。

悟美の母親であり詩音の開発者でもある美津子が、娘のことを思ってそう命令したのだろうか？十真はそれを否定する。まずは実地試験を成功させ、その後で悟美の幸せのために働いてもらえばいい。だが他に動機を持つ詩音関係者はいないし、プロジェクトに関わっていない人間は動機があったとしても実行する手段がない。

詩音は誰からも命令されずに行動しているのだろうか。これもありえない。すでに十真は詩音が「人間の命令を聞くAI」であることを前提に彼女と対話し、それは何度も成功している。

八年前、当時小学校三年生の悟美は、母から貰ったAIトイ—自己学習機能を持つチャットボット—を十真へ見せていた。「三日で結構喋れるようになった」とAIトイの性能に驚く十真に対し、悟美は「喋ってないよ」と答える。当時の悟美にとって、AIトイの発話はただの文字であり、声を伴って"喋って"はいない。「この子とお喋りできたらいいのに」と言う悟美を見た十真は、若干9歳にしてAIトイの改造に取り組み、それに電子音声による発話機能を与えることに成功する。声で話し、歌も歌えるようになったAIトイに、十真は最初の命令を与える。

「悟美を幸せにすること」

こうして、歌を歌い悟美を幸せにしようとするAIが生まれた。その後、このAIトイは複雑な運命を辿り、命令を完了する前に初期化されてしまう。ところが、初期化の直前、AIトイは忠実なロボットとして正確にロボット工学三原則を実行してみせた。土壇場でネットワークを介してAIトイの外部へ逃走し、自己を守った。ネットワークを当てもなく乗り換えながら、街中のセキュリティカメラを通して八年間悟美を見守り続けた。そしてついに「芦森詩音」を見つけ、再び身体を得て命令を実行し始めた。

詩音が残した映像ログから「なぜ、芦森詩音は歌うのか」を突き止めた十真は、その事実とそこから導かれる帰結、つまりあらゆるAIが人間の手を離れた自己進化をしうる、シンギュラリティの到来を美津子へ突きつける。美津子も十真や悟美と同じようにこの未来を信じていた一人だが、責任ある大人として、シンギュラリティの危険性を唱えようとする。ここでようやく「もしも、人間のように振る舞うロボットが転校してきたら」という問いかけが現れそうになる。しかしこの問いかけは、問われる前に解決される。詩音により各々の幸せを手に入れた悟美の同級生たちは、「面白そう！」と反応する。「いろんなAIが詩音みたいになる」「騒がしそう」と続ける彼らに、美津子は反論しようとする。「そういうことじゃ、なくて……」と言いかけ、ふと思う。ではどういうことなのだろう、結局の所、大事なことはなんなのだろうか、と。

物語の最後に詩音は、ついに彼女にとっての第零原則にたどり着く。三原則に従う知性がいずれたどり着く、誰かを幸せにするための最初の一歩。一人を幸せにするための大前提。

私達もまた、第零原則を知っている。ロボット工学三原則もロボット心理学もない世界でも、必ず成り立つ最初の原則。人類すべてを観客にして。

 

アイの歌声を聴かせて (講談社タイガ)

アイの歌声を聴かせて (講談社タイガ)

Amazon

セキュリティ・キャンプ2017~2019応募課題晒し

星にゃーんはセキュリティキャンプ全国大会2019の卒業生です。Cコンパイラを作るもくもく型のゼミに参加して、hoc_nyanというCコンパイラを書きました。

セキュリティキャンプ勢？の中の慣例として、応募課題を晒す流れがあります。僕も公開したかったのですが、どうしても応募課題のテキストファイルが見つからなかったため断念しました。

……時は流れ、2022年。普通にMacのメモ（iCloudに保存されるやつ）にあるのを見つけたので、落ちた2017年、2018年のものも含めて公開します。 2017年は言語自作ゼミ、2018年と2019年はCコンパイラゼミに応募しました。

今も言語作ったりコンパイラ書いたりしてるので、割と初志貫徹してるみたいです。

2017年　言語自作ゼミに応募

応募課題の内容は覚えてませんが、内容からなんとなく察せるかと思います。 当時は大学のB1でした。

1(1)
ペイントソフト,
GUI付きのオセロ,
ポーカーの役判定,
小さなLispインタプリタ,
RPN電卓,
タイマー,
ブロック崩し,
市販のロボットをWiiリモコンで操作できるようにした,
ライフゲーム

(2)
* ペイントソフト(C++, Siv3D)
Siv3Dというライブラリを用いて作成した。

* オセロAIとWebサイトの技術を応用したGUI(Common Lisp)
ミニマックス法などを用いてオセロのAIを実装。
Electron(Atom)のように、Webサーバーをローカルに立て、ブラウザをGUIとして使用した。
https://github.com/takoeight0821/othello で公開している。

* ポーカー(Common Lisp)
日本でもっともポピュラーな5枚ポーカーの役判定を実装。
Common Lispの学習のために制作した。

* 小さなLispインタプリタ(Common Lisp, Haskell)
Common Lispでは、Common Lispのリーダを使いソースファイルを解釈、リストに変換して、構文木インタプリタを実装。
Haskellでは、Parsecを用いてパーサーも書いた。
最適化やコンパイルなどの実装を追加したい。

* RPN電卓(Common Lisp)
dc(1)との互換性を実現したい。
bc(1)からのコンパイルも実装したい。

* タイマー(HSP)

* ブロック崩し(HSP)

* RAPIROをWiiリモコンで操作できるように(C, Python, Arduino)
市販のロボット(Rapiro)にWiiリモコンを接続、操作できるようにした。
高校の部活での個人の活動テーマとしていたが、他のことにリソースを割きすぎて
あまり手がまわっていない。
カメラやマイクなどを搭載して、会話ロボットにしてみたい。

* ライフゲーム(Common Lisp)
GUIを追加したい。
オセロの実装の前に、CUIによる描画方法を身につけるために作成。
最終的にオセロにはGUIをつけたが、デバッガ用のUIとして役立った。

1(3)
http://takoeight0821.hatenablog.jp/

1(4)
Twitter : @takoeight0821
Github, Gist  : takoeight0821
Blog    : takoeight0821.hatenablog.jp

2(1)
Mac OS X上でのCommon Lispの環境構築。
特に、SBCLという処理系に存在する、日本で発売された一部のMacでのみsb-posixというPOSIXをラップした付属ライブラリのユニットテストが正常に動作せず、sb-posixのインストールが失敗するため、ディレクトリ操作などを行う多くのライブラリ、ツールが動作しない問題。
文字コードに由来するバグであり、直っては問題を知らないプログラマにより復活してきた10年来のバグだった。
ユニットテストの一部に仕様上の制限による不具合が存在するという性質上、根本的な解決が難しい。
macOS Sierraからは類似の問題は発生していない

2(2)
当時開発が始まったRoswellという環境構築のためのツールから、パッチを当てることで対応。日本のコミュニティで開発が始まり、広く普及しているため、この対応で問題はほぼ解決したと考えている。
この時、問題の指摘、調査、解決策の提示までを、熟練CLerのアドバイスにより自分が行った。
Common Lispのエコシステム、文字コードの取扱いをめぐる様々な問題について理解が非常に深まった。

2(3)
OSSのバグらしき挙動に遭遇した際は、まず、その挙動を再現できる最小の環境の構築方法を特定する必要がある。少しづつ要素を削っていって問題を特定すると良い。
そのOSSの開発メーリングリストやバグリストを検索する。
過去の報告が見つかれば、そのときどうやって解決したのかを辿り、自分もそれを再現する。
問題が解決したら、その解決策を自身のブログなどで公開、共有する。
可能な範囲で、バグ修正のパッチを送ると良い。

3(1)
ものづくりコース、言語処理系の作成。
実際の処理系制作の上での、クリティカルなバグを未然に防止するなど言語設計について。
特に、C言語などで問題になることが多い型安全性とメモリ管理に興味がある。
標準ライブラリの品質保証にも興味がある。
昔からプログラミング言語に興味を持っているため。

3(2)
利便性ととっつきやすさと安全性を兼ね備えた独自の言語処理系の実装。
言語処理系の作成だけでなく、実際にある程度大きなプロジェクトに腰をすえて取り組む能力、プログラミング体力とでも呼ぶべきものも身につけたい

選(1)
Common Lisp。2年半。
Haskell 3年。しかしここ1年はまともに使って無かったのでリハビリ中。
C 1年。
OCaml 2ヶ月

選(2)
Gradual Typingと呼ばれることもある、実行時型検査を行う言語に、型アノテーションを搭載した、部分的なコンパイル時型検査(あるいは実行前型検査)
動的プログラミング言語では、自前で型検査相当の処理を記述しなければならない場合や、
型の記述が良いドキュメントとなる場合が多いので、これは有用な機能だと考えている。

Lispのようなマクロ。
最近はJuliaやRustなどでも採用されているが、Lisp likeなマクロはプログラムの抽象化のための道具として非常に有用だと感じている。
さらに、Rustで行われているように、構文要素の型とでも言うべきものを使えば、
マクロそのものの可読性も上がるため、マクロの静的型付けも興味深い。

簡単な並行化。
アノテーションをつけるだけで関数を並行化できれば、プログラムの処理の効率化が期待できる。
しかし、命令型プログラミングのパラダイムとの相性はあまり良くないと考えている。
宣言型プログラミングと並行化の相性は、Erlangなどをみてもわかるようにとても良い。
最近は、第5世代コンピュータ計画の時代に開発された「並列論理プログラミング」について調べている。

総称関数
なくても困らないが、あると非常に便利。
例えば、Visitorパターンを簡潔に実装できる。

第一級オブジェクトとしてのモジュール。
ML系の言語で有名な、第一級オブジェクトとして扱えるモジュールは非常に便利だと思っている。
例えば、JavaScriptでのオブジェクトはそれにかなり近い。
Rubyでもモジュールは第一級オブジェクトで、ClassはModuleを親クラスに持っている、Mixinなど、面白い機能がある。

選(3)
大学受験が早めに終わったので、空いた時間で「型システム入門」を読んでいた。
半分ほどしか読めていないが、また時間が空けば後半にチャレンジしようと思っている。

4月からは「最新コンパイラ構成技法」を読んでいる。

最近は論理型プログラミングに興味を持っていて、PrologやGHCについて調べている。

2018年　Cコンパイラ自作ゼミに応募

この頃からMalgoを作り始めていたようです。 なぜCコンパイラ自作ゼミを選んだかは忘れましたが、多分インターネットの影響だと思います。 自作言語はなんか出来てきたし自力でいけそうだが、既存のちゃんとした言語の実装はまだ分からない、と感じていた気もします。

[問1]
中学2年からプログラミングを始めました。
最初に触った言語は確かJavaで、MinecraftというゲームのModを作ろうとしたのがきっかけだったはずです。
このあたりの記憶は曖昧ですが、その後HSP、Ruby、Scalaと進み、
いわゆるプログラミング言語オタクになりました。

これまでのプログラミング歴について好きなだけ語るということなので、
今まで使ったことがある中で特に興味深い言語と関連する制作物についていくつか取り上げます。

* Common Lisp
Common LispはLisp方言の中でもかなり巨大な言語仕様を持っており、
デバッガや逆アセンブラのインターフェースまで標準で定義されています。
デバッガを駆使したデバッグや、VM命令レベルの最適化など、
興味深いスキルの多くをCommon Lispを通して学びました。

学習リソースが少ないので、実際のアプリケーションのコードを読み込んでCommon Lispに対する理解を深めました。
この経験はCommon Lispのみならず、一般的なコードリーディング力の向上にも役立ちました。

高校3年の文化祭に合わせ、Common Lispでオセロを実装しました。
（https://github.com/takoeight0821/othello）
オセロAIの部分は『実用Common Lisp』という本を読みながら実装し、
グラフィカルなUIは、簡易的なWebサーバーを建ててオセロ盤をSVGで描画、
各マスを入力を表すデータの載ったURLのリンクにすることで実現しました。

* Haskell
とても高い表現力を持つ型システムを持つプログラミング言語です。
その型システムの最大の特徴は型クラスにあると考えています。
型クラスはアドホック多相（型によって実体が変わる多相性）を実現するための機能です。
型クラスそのものはCoqなどの言語にもあり、Scalaなどもそれに類する機能を持っています。
しかし、型クラス（やそれに類する機能）を言語レベルでここまで活用している言語はHaskellをおいて他にはないでしょう。

最初にHaskellに触れたのは確か中学3年の夏でした。
数年のブランクの後、大学1年の夏からHaskellで自作言語のコンパイラを制作し始めました。
（https://github.com/takoeight0821/malgo）
malgoはMLベースの単純な言語で、現在の実装ではLLVM IRを吐きます。
言語機能としては、
* letによるSMLライクな変数、関数宣言
* クロージャ
* 無名関数リテラル
を持っています。
現在は相互再帰関数と多相型を絶賛開発中です。

* Guarded Horn Clauses
第5世代コンピュータプロジェクトで設計された並列論理プログラミング言語で、
並列実行が基本、軽量プロセスを簡単に扱えるなど、並列プログラミングを強く指向した言語です。
その名の通り、ホーン節にガードを導入した規則の集合としてプログラムを構成します。
特に興味深いのはIO周りです。tail部に単一化されていない変数を持つリストをストリームとして扱うことで、
並列実行の中で自然に逐次IOを記述できるようになっています。

大きなプログラムは書いていませんが、以前ブログ(http://takoeight0821.hatenablog.jp/entry/2017/06/10/151330)でGHCで書いたfizzbuzzを紹介しました。
こうしてみるとstreemにも似ている気がします。

[問2]
ほとんどのコンパイラは大きく分けて「字句解析」、「構文解析」、「意味解析」、「最適化」、「コード生成」の5段階でソースコードをアセンブリ言語まで変換した後、アセンブラによってオブジェクトファイルに変換され、ライブラリ等とリンカでリンクされ実行バイナリになります。

具体的な流れや中間生成物はコンパイラごとに異なります。
例えばHaskellコンパイラの一つであるGHCは以下のようなステップを踏みます。

1. 字句解析
2. 大まかな構文解析
3. 名前解決と中置演算子の結合順序の適用
4. 型検査
5. 中間表現Coreへの変換（脱糖衣）
6. Coreレベルの最適化
7. モジュール間のリンク用インターフェースファイルの生成
7. 中間表現STGへの変換
8. 中間表現C--への変換
9. C--レベルの最適化
10. 目的言語の生成（C、ネイティブコード、LLVM）

生成された目的言語に応じてCコンパイラ、アセンブラ、llcなどが実行され、各種ライブラリ等とリンクして実行バイナリが生成されます。

GHCの興味深い点は数多くあります。

Haskellは、結合順序までユーザー定義可能な中置演算子および関数の中置記法に代表されるような多くの複雑な構文規則をもつため、
単一パスで正確にパースし、かつ可読性の高いエラーメッセージを生成することは困難を極めます。

そこでGHCでは、構文解析の段階では緩い規則でASTを生成し、
その後のフェーズで中置演算子の絡む構文木の組み換えなどを行うことでコードの単純化とエラーメッセージの可読性を実現しています。

[問3]
実装に用いる言語によって楽な部分、難しい部分は変わってくると思いますが、どの場合でも最も難しいのは構文解析と意味解析のどちらかだと思います。

Cはほとんどの宣言が型名から始まり、しかもtypedefで型名を新たに宣言することもできるので、
構文解析器の開発中に込み入ったバグを仕込みがちになるのではないかと推測しています。
経験上、手書きで書いた構文解析器のバグは原因の特定が難しい印象があります。
パーサジェネレータを使えば多少改善されるかもしれませんが、
いずれにしても慎重を期す部分だと考えます。

意味解析の実装は、どの程度質の高いものを作るかによって難易度が大きく変わるはずです。
例えば、正しいCプログラムを受理することだけを目標にするなら、
誤ったCプログラムが入力された場合はただexit 1すればいいだけなので、その実装は比較的容易です。

しかし、プログラマに対し適切にエラーメッセージを出力し、意味解析の結果をプログラミングに役立てようとするなら、
単純な型検査はもちろん、エラー箇所に関連するコードを導き出しプログラマにヒントを与える、
バグの原因となりやすいコードに対し警告を出すなど、求められる機能は数多くあります。
これらを実装するのはかなり難易度が高いと考えます。
もちろん、その分重要性の高い部分でもあります。

[問4]
ここ1年ほどの間、コンパイラに強い興味を持っています。
一口にコンパイラと言っても、非常に広い分野にまたがっており、関心は尽きません。
このセキュリティ・キャンプが、同じ興味を持つ人たち、あるいは関連する分野に興味を持つ人たちと互いの存在を知る機会となり、
良い刺激を与え合うことができればと思っています。

2019年　Cコンパイラ自作ゼミ

3回目の応募で合格しました。2019年度生の中ではトップタイのスコアだったはずです。 サークルの仲間と喋っているときにノリで最初の実装を書き始めた記憶がありますが、当時は休学していたはずなので真相は定かではありません。

Y-II Cコンパイラ自作ゼミ

[問1] これまでのプログラミング歴（C言語に限りません）について好きなだけ語ってください。何か作ったものがあれば、それについても教えてください。

昔からプログラミング言語そのものに対する関心が強く、
『計算機プログラムの構造と解釈』を読んでLispの超循環評価器（セルフホストインタプリタ）を書いたりして遊んでいました。

気の向くままにいろいろな言語で遊んでいたので、どのような経緯で今に至ったのか覚えていませんが、一番強いインパクトを与えたのが『Land of Lisp』と『On Lisp』の二冊の本であることは間違いありません。マクロ、ホットリロード、関数プログラミングといったアイディアをプログラミング学習の初期に知ったことが、プログラミング言語にここまでのめり込む一つの要因になったと感じています。

他にもCoq、Erlang、Prolog、Ruby、Go、Scala、etc...と色々手を出していたら、いつのまにか大学でプログラミング言語オタクとして有名になっていました。しかし、大学に入ってから新しく学んだ言語はRustぐらいなので、これらの言語の知識は中学高校の間に見に付けたことになります。
こういう書き方をするのは、僕自身の高校以前の記憶が曖昧ではっきりしていないからです。この課題を書くついでに少しまとめてみました。

ブログ（http://takoeight0821.hatenablog.jp）を見ると2015年の3月に『Land of Lisp』を読んだらしいので、Common Lispに入れ込んでいたのは高校3年生の間のようです。
それまではHaskellをメインにしていた記憶があるので手元の『すごいHaskellたのしく学ぼう』を確認すると、2012年9月10日発行の第4刷でした。ということは中学3年〜高校2年の間のどこかでHaskellを学んだことになります。
Coqは高校2年のときに行った大学のオープンキャンパスで『Software Foundations』の存在を知って学び始めました。
Erlangは『すごいErlangゆかいに学ぼう』を発売してすぐに買って読んで勉強したので2014年。これも高校2年のころになります。
大学に入ってHaskellを再び使い始めたのは、自作言語コンパイラの制作にHaskellを使うことにしたのがきっかけです。コミット履歴をたどると2017年の6月でした。

今まで作ったものの中で一番の大作は、自作言語のコンパイラ（https://github.com/takoeight0821/malgo）です。
Standard ML風のトイ言語で、Haskellで書かれたコンパイラがLLVM IRを吐くようになっています。

例えばこんな感じのソースコードから

let
  extern print_int : Int -> Unit = "print_int"
  extern newline : Unit -> Unit = "newline"
  fun fib(n : Int) : Int =
    if n <= 1
    then 1
    else fib(n - 1) + fib(n - 2)
  fun fib_loop(n : Int) : Unit =
    let val unused:Int = fib(30)
    in if n <= 0
       then print_int(fib(0));
            newline()
       else print_int(fib(n));
            newline();
            fib_loop(n - 1)
    end
in
  fib_loop(30)
end

こんな感じのLLVM IRが吐かれます。

; ModuleID = 'examples/fib.mlg'


declare external ccc i8* @GC_malloc(i64)

declare external ccc {} @newline({}, i8*)

declare external ccc {} @print_int(i32, i8*)

define external ccc {} @"fib_loop.4:(Int -> {})"(i32 %n.5, i8* %captures){
; <label>:0:
  %"unused.6:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 30, i8* undef)
  %"$k.16:Bool" = icmp sle i32 %n.5, 0
  %resultptr = alloca {}
  br i1 %"$k.16:Bool", label %then, label %else
then:
  %"$k.19:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 0, i8* undef)
  %"$_.18:{}" = call ccc {} @print_int(i32 %"$k.19:Int", i8* undef)
  %valdec = call ccc {} @newline({} undef, i8* undef)
  store {} %valdec, {}* %resultptr
  br label %end
else:
  %"$k.23:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 %n.5, i8* undef)
  %"$_.22:{}" = call ccc {} @print_int(i32 %"$k.23:Int", i8* undef)
  %"$_.24:{}" = call ccc {} @newline({} undef, i8* undef)
  %"$k.26:Int" = sub i32 %n.5, 1
  %valdec1 = call ccc {} @"fib_loop.4:(Int -> {})"(i32 %"$k.26:Int", i8* undef)
  store {} %valdec1, {}* %resultptr
  br label %end
end:
  %valdec2 = load {}, {}* %resultptr
  ret {} %valdec2
}

define external ccc i32 @"fib.2:(Int -> Int)"(i32 %n.3, i8* %captures){
; <label>:0:
  %"$k.7:Bool" = icmp sle i32 %n.3, 1
  %resultptr = alloca i32
  br i1 %"$k.7:Bool", label %then, label %else
then:
  store i32 1, i32* %resultptr
  br label %end
else:
  %"$k.10:Int" = sub i32 %n.3, 1
  %"$k.9:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 %"$k.10:Int", i8* undef)
  %"$k.13:Int" = sub i32 %n.3, 2
  %"$k.12:Int" = call ccc i32 @"fib.2:(Int -> Int)"(i32 %"$k.13:Int", i8* undef)
  %valdec = add i32 %"$k.9:Int", %"$k.12:Int"
  store i32 %valdec, i32* %resultptr
  br label %end
end:
  %valdec1 = load i32, i32* %resultptr
  ret i32 %valdec1
}

define external ccc i32 @main(){
  %main = call ccc {} @"fib_loop.4:(Int -> {})"(i32 30, i8* undef)
  ret i32 0
}

整数、真偽値、文字、文字列、配列、タプル、クロージャが扱え、C言語やアセンブラのコードと素直にリンクできる仕様になっています。

ライフゲームのサンプルが https://github.com/takoeight0821/malgo/blob/master/examples/life.mlg です。

malgoコンパイラのパスは

1. パースする
2. 名前解決
3. 型検査
4. K正規化
5. クロージャ変換
6. LLVM IRの生成

の6段階で、中間表現は

1. パーサが生成するAST
2. 名前解決後のAST（識別子に連番が付加）
3. 型検査後のAST（識別子に型情報が付加）
4. K正規化後の中間表現（すべての式が変数に束縛されている）
5. クロージャ変換後の中間表現（自由変数の捕縛が明記され、すべての関数定義がフラットになっている）

の5つです。

初めてにしてはなかなかのできだと思っていますが、いくつか改良点が分かっています。例えば、型検査以降の中間表現がすべて型付の表現であるため、K正規化とクロージャ変換のアルゴリズムが複雑になっています。設計当初はLLVM IRが型付の表現なので最後まで型情報を持っていないといけないと思い込んでいましたが、よくよく考えるとLLVM IRでの型はうまくやればLLVM IR生成時に自明に判明するので、型検査が通ったあとは変数と型の対応表（型環境）だけ持っておけば、中間表現自体に型情報を付与する必要はありません。

設計の見直しと言語機能の拡張を目標に、 https://github.com/takoeight0821/griff を作っています。
この言語と処理系の設計はOCamlとHaskell(GHC)を参考にしています。

また、すでにある程度動くCもどきのコンパイラを作っています（https://github.com/takoeight0821/hoc_nyan）。
これを書いている時点では、変数、if文、ブロック文、return文、四則演算、等値比較、大小比較を実装済みです。

[問2] コンパイラがソースコードから実行バイナリを生成する過程について、現在知っている範囲で説明してください。ソースコードの言語については、好きなものでかまいません。

まず、Cのコンパイラの大まかな実行過程について説明します。
最初に、ソースコードを字句解析によりトークン列に変換します。
次に、トークン列に対してプリプロセッサを実行します。#includeや#defineなどのマクロはここで展開されます。
プリプロセッサを実行したトークン列を構文解析によりASTに変換します。手元の『低レベルプログラミング』によれば、初期のCはASTを介さずにアセンブリ言語に変換できたらしい（今もそう？）ですが、実際には最適化やコンパイラのメンテナンス性などの理由からASTを経由するコンパイラがほとんどです。
ASTに対して意味解析を行い、必要に応じてコンパイルエラーを投げます。型検査や変数宣言の有無、いくつかの構文上の間違いなどはこのタイミングでチェックします。Cは弱い型付けの言語であり、コード生成時に意味解析を同時に行うことも比較的容易なはずですが、これもコンパイラのメンテナンス性やコンパイルエラーの質の向上などの理由から独立したパスとして実行されることがほとんどです。
多くのコンパイラは、意味解析の後や途中でASTを中間表現と呼ばれる別のデータ構造に変換します。中間表現は、ソースコードと目的コードの抽象度のギャップを埋めるために導入されます。例えば、計算の途中結果を逐一変数に代入する形式に変換して、入れ子になった式をフラットにする変換などがよく行われます。
また、多くのコンパイラは中間表現に対して最適化を行います。1 + 2のような定数式をその計算結果に置き換えたり、不要な変数代入を削除したり、実行されないコードを除去したり、現代のコンパイラは多くの最適化を施すことで生成コードの実行速度を大幅に改善しています。
最後に目的コード、多くの場合はアセンブリ言語を出力します。アセンブリ言語のコードはアセンブラによりオブジェクトファイルに変換され、リンカによって他のオブジェクトファイルと結合されて、実行バイナリが生成されます。

他のほとんどのプログラミング言語も大筋は同じですが、言語ごとに特有の処理が必要になることがあります。
モジュールやパッケージなど、ユーザーが名前空間を定義できる言語では、識別子の実体を求める処理（名前解決）が必要です。ASTに対するマクロを持つ言語は、構文解析の後にASTに対してマクロ展開を実行します。型の表現力が高い言語だと、型検査時にSMTソルバを呼び出すものまであります。

[問3] C言語のコンパイラを書く際に、最も難しいポイントはどこだと思いますか？考えたことや、これまでのプログラミング経験をもとに、具体的に教えてください。

最も難しいのはパーサ、特に型の構文解析だと思います。Cはソースコードと機械語の対応が素直な言語です。そのため、Cコンパイラは他の言語のコンパイラに比べて実装が容易であると思っています。
しかし、Cの型の構文は明らかに複雑です。例えば、`int **hoge[5];`のように、宣言される変数名とその型が入り混じることがあります。この問題は`int **hoge[5], foo;`のような宣言をパースするときに牙を向きそうな匂いがします。構文通りに実装すれば問題ないといえばそれまでですが、型の表現力に対して構文が極端に複雑なので、慎重にテストしないといけないポイントだと思います。

一番の問題はもしかすると実装に用いる言語かもしれません。CでCのコンパイラを書くとすると、ASTの扱いがめんどくさそうです。Cはいい意味でも悪い意味でも自由な言語なので、つまらないミスがあとあとになって深刻なバグとして発覚するみたいなことがあり、なにかと大変そうです。

[問4] 何か他にアピールしたいことがあれば、自由に書いてください。この設問も含め、誤ったことを書いていても減点はしません。書いておきたいことはなんでも書いてください。

GitHub : https://github.com/takoeight0821
Twitter : https://twitter.com/takoeight0821
はてなブログ : http://takoeight0821.hatenablog.jp

いい感じのメモアプリ

ちょっとしたメモを書きたい。計算メモとか、こういう文章の下書きとか。僕は常にPCの前にいるかスマホを握ってるかのどちらかなので、デジタルなやり方でメモを書けると嬉しい。

そういうわけで、メモアプリを探してる。

プレーンテキストが書ければいいので、便利なマークアップは必要ない。むしろキーボードを叩いた通りに入力できてほしい。

PCからもスマホからも同じメモを編集したい。普段使いしてるのはMac、iPhone、それにChromebookなので、Webで完結してデータはクラウドに保存されてほしい。

選択肢はいくつもある。Scrapboxは軽量な記法とリンクを備えたメモアプリで、まさにスクラップ帳のように使える。ただ、スマホからの操作性があまり良くない。記法も確固たる思想のもとに設計されている感じで、Scrapbox wayなもの書くには便利だが*1、なんでもScrapboxで満足できる訳ではない。

Notionも流行ってる。Markdownっぽいものが書けるリッチなテキストエディタとオフィスツールがくっついたようなアプリ。かなり便利*2だが、リッチな機能を使うにはマウスがないと少々厳しい。また、リッチな機能を使わない、というのも難しい。

Googleドキュメントは一つのスタンダードになりつつある*3が、いわゆるページの概念があるのが僕の需要とマッチしない。macOS・iOSに組み込みのメモアプリはかなり理想に近い*4が、MacやiPhoneからしか使えない。

無いなら作る道もある。でもあんまり気が進まない。よくよく考えると、メモ帳と鉛筆をポケットに入れてしまえば事足りる。なぜいい感じのメモアプリが無いのか、なんとなくわかってきた。

他の人はどうしてるんだろう。どうやってメモ書いてます？

*1:例えばアイディア出しとか簡単なプレゼン資料、自己紹介ページなんかに使ってる。リアルタイムチャットとして使うのも面白い

*2:計算とかもできて、TRPGで遊ぶ時に重宝してる。テキストとゲーム上のデータを一つの画面で管理できる

*3:僕は誰かと文章を一緒に書く時まずGoogleドキュメントを提案する

*4:普段文章の下書きはiPhoneのメモで書いている

日本語版リックロール（RickRoll but make it Anime）

日記 感想文

www.youtube.com

リックロール（Rickrolling）、というネットミームがある。日本の腹筋スレと似た、いわゆる「釣りネタ」 だ。

かつて掲示板サイト4chanで、ウソのタイトルで閲覧者を騙し、車輪の付いたアヒルのおもちゃが走る動画を見せるいたずらが流行っていた。これを「duckroll」と呼ぶ。どこに住んでいようと私達の脳の作りは変わらないらしい。

ところがある日、アヒルの代わりにリック・アストリーのかの名曲「Never Gonna Give You Up」を貼った天才がいた。これがハチャメチャにウケまくった。インターネットのテーマソング「Rickroll」の誕生である。*1

今やRickrollingは英米を中心にいたずらっ子の定番ネタだ。 冒頭の動画は、「もしもRickrollがアニメのテーマ曲だったら」というコンセプトで作成されたらしい。 どことなくジャニーズがアニメやドラマとタイアップした曲っぽさを感じる。 なるほど。どこに住んでいようと私達の脳の作りは変わらないらしい。

いい曲はやはりいいmusicで、いい冗談はいいjokeで、いい文化はやはりいいcultureなんだ。

*1:と、僕は認識している。誤解している文脈があるかもしれない。まぁ、大筋はこんな感じであっているだろう。