Rubyのしくみ -Ruby Under a Microscope- 序文、はじめに

お久しぶりです。
次は「型システム入門」を読む、と言いつつ半年近く間があいてしまいました。生活リズムの変化により朝の読書というのが難しくなったので、朝にこだわらずに読むようにして復活させようと思います。
さて、このたびオーム社様のご厚意により「Rubyのしくみ」を贈って頂けたので、この本で再開させたいと思います。ありがとうございます。

Rubyのしくみ -Ruby Under a Microscope-

Rubyのしくみ -Ruby Under a Microscope-

いつものように最初から順に読んでいきます。

  • 序文
    • 日本語版序文に matz、序文に tenderlove ことアーロン・パターソンさんと豪華ですね。付録に笹田さんの YARV 解説もあるみたいですし
  • はじめに
    • 対象読者は必ずしも C の知識を前提としない。図解を多用して説明するとのこと。ほう。
    • 検証にはRubyスクリプトを書いて実験してみる。これはいいアプローチですね。コード読む上でも仮説を立てて、動かしてみて、予想に合っていたかどうか確認する、というサイクルをまわすのは理解を深めるのに良い方法だと思います。
    • 対象の処理系は MRI。 JRuby と Rubinius については 第10、11、12章で触れる
  • 主なトピック

ざっくりみたところ、IO や スレッドの管理あたりのシステム(OS)に近いあたりのトピックよりは、Ruby の主に処理系の実装の大観とよく使われる構成要素についての解説をしているという感じみたいですね。

白と黒のとびら 解説

これがそれぞれ以下の形式言語のクラス/文法に対応する

ううむ、こういう言語の分類があるのですね。

各章のテーマについて

  • 古代ルル語系は正則言語
  • 第3章は非決定性オートマトンと決定性オートマトンとその変換について
  • 第4章は自動販売機の設計に潜むオートマトンがテーマだったらしい。どうりでちょっと浮いてると思った!
  • 古代クフ語は文脈自由言語
    • 筒がスタック
    • ε-遷移あり
  • 正則言語と文脈自由言語に対する反復補題
  • 文脈自由言語の統語解析
  • 第一古代セティ語は文脈依存言語。塔は線形拘束オートマトン
  • 万能チューリングマシン
    • 「塔」の動作を指定するのに偽クフ語を利用した点については補足されていました。やっぱりね
    • 状態、テープ記号、ヘッドの移動方向に整数を割りあてる

これで「白と黒のとびら」の読書は終了です。ストーリーもゃんと読めて、おもしろい本でした。

次からは「型システム入門」に進みます。大作ですね。何ヶ月かかることか…。

白と黒のとびら 第16章 返答

ガレット君はついに塔の問いかけに答えます

  • 「〇と●からなる全ての文字列を含む集合から、『塔の動作を記述した文字列のうち、それ自体が、自身が表す動作によって表現される言語の"文"であるような文字列』を取り除いた文字列」
    • 塔の動作を表す文字列ではないもの(つまり文法エラーに相当する)も含まれるわけですね
  • 証明は背理法による
    • この言語(Lとする。またここでいう言語は〇と●からなる文字列の集合を意味する)が塔によって表現できるとする
      • この言語を表現するように塔の動作を記述する文字列が存在するはず。これを S とする
      • S が L の文である(S が L に含まれる)と仮定する
        • L の定義より、S は「Sが表現する言語の文ではない」とことなるが、これは S が L の文であることと矛盾する
      • S が L の文でないと仮定する
        • L の定義より S は L の文であることになり、矛盾する
    • よって L が塔によって表現可能という前提が誤り

さて、物語はクライマックスを迎えますが、それは読んでのお楽しみとします。
エピローグは主にストーリー展開なので飛ばして、次回は「解説」の章を読んで本書を終えようと思います。
次は、ついに TAPL の邦訳「型システム入門」を読もうと思います。これは長くかかりそうです。

白と黒のとびら 第15章 詩集

クージュとレザンの兄弟が作った「万能機械」でも決っして表現できない〇と●からなる言語の特徴を述べよ、という問いかけに答えないといけなくなったガレットは苦労しながらも、答をみつけるようです

  • 「〇と●からなる言語」とは「〇と●の文字列の集合」であり「ある〇と●の文字列がその言語の文であるか否かを判別するルール」と言える
  • ガレットは塔の動作を指定する偽クフ語による詩集を再読して、レザンの書き込みを発見する
    • ある詩が、それが表現する言語そのものの文になっているものには「除外する」という書きこみがある

塔の動作を指定する詩も〇と●からなる文字列で入力されており、その詩を塔への判定すべき文字列として入力するとどうなるか……というところに着目したガレットは答えをみつけたようです。
つまり「ある文字列を塔の動作として入力すると、その文字列自身も正しい文として認識する言語を表現するような詩」以外の文字列、ということでしょうか。けど偽クフ語には文法があるので、そもそも塔に正しく解釈されない文字列もあるので、そのへんちょっと美しくないですね…。

白と黒のとびら 第14章 問いかけ

14章は、ひとつの装置で全ての古代ルル語、古代クフ語を表現できる「万能機械」についての話と、師匠の師匠のところに赴くストーリ上の展開で終わりました。

  • 万能機械
    • 全ての古代ルル語、古代クフ語を表現できるただ一つの装置
    • ヴェインさんは第一古代セティ語を表現した塔の、部屋の「状態」を1つの部屋として表現することで作れないかと思案中
    • 装置に「動作を指示する文字列」と「評価する文字列」の2つの入力を持つ
  • 師匠の師匠からの試練
    • 「〇と●の文字からなる言語のうち、上下に無限に続く『塔』をもってしても、けっして表すことのできない言語を探せ。それはいかなるものか、そしてそれはなぜ『塔』によって表すことができないのか」

〇と●からなる言語でチューリングマシンで表現できない言語を探せということですね。
ということはこれはきっと停止性問題に関するなにかだ(山勘)。

ところで長らく読んできた「白と黒のとびら」もそろそろ終わります。次はついに念願のあのぶ厚い本に取りかかろうかなと思います。

白と黒のとびら 第13章 塔 その2

ガレットが実際に塔に入り「〇〇●●〇〇」を入力してみます

  • 塔の部屋は詩に書かれているとおりに扉の色を変化させて上下する
  • 「1月」とか「2月」は部屋の位置ではなくて、部屋の「状態」を表している
  • 塔の扉はその階に部屋があるときだけ詩に記述されているとおりに色が変化する
  • 詩に記述されていない扉の色の階に止まるとそこで部屋が止まって塔に拒絶されてしまうらしい
  • 屋上に到達したら受理されたことになる

各階には扉の色という状態があり、上下に動く部屋があり、部屋には状態がある。部屋は今いる階の扉の色を変更する……これはチューリングマシンのことですね!
というところでファカタの校長からの手紙で急いで戻ることになりました。

白と黒のとびら 第13章 塔 その1

ガレットとユフィンが向かった先には「塔」を守る巨人の子孫とヴィエンが。巨人の言語を表す「塔」の遺跡についての説明がメインの章です。この遺跡はこれまでに出てきたものとはずいぶん様子が違うようです。

  • 塔の部屋は昇降機のようになっていて、部屋のボタンを押して文字列を「入力」する
    • 入力した文字列のぶん塔が「伸びる」
    • 入力した文字に対応して部屋を上下し、その時に丸い扉の色が様々に変化する
    • 屋上に到達したら文字列が「受理された」ことになる
    • 例として「〇●〇」と入力すると、1階(扉の色は白→黄色と変化)→2階(扉の色は黒→紫と変化)→3階(白→緑と変化)→1階(扉の色はまた白→黄色と変化)と移動してから屋上に到達する
    • 間違えて「〇●〇」と入力すると、1階→2階→3階と移動してそこで塔から落とされてしまう(この文字列は受理されない)

この言語をユフィンとヴィエンは「第一古代セティ語」と命名します。

塔の動作は DFA な正規表現みたいですね。各階が状態を表していて、変化する扉の色は何を表現しているのでしょうか。