WIP【備忘録】DBの論文を読む : バックグラウンド

そろそろデータベースに関するちゃんとした基礎知識をつけたいという思いがあるので、Readings in Database Systems, 5th Edition を読んでいこうと思う。
URL: http://www.redbook.io/index.html

この本は、DB に関する古典的な論文から、近年の特に重要な論文まで、章ごとに短い解説とともに紹介されている。

今回は Ch1 バックグラウンド を読む。

紹介された論文

  1. What Goes Around Comes Around. [因果応報] (2005).

    • 約 35 年間の間に提案されてきたデータモデルとそこから得られる教訓について解説されている。
  2. Architecture of a Database System. [データベースのアーキテクチャ] (2007).

    • DB の構成要素と全体像について解説を行っている。

解説を読んだ

かつて XML をリレーショナルエンジンに追加するのが流行りかけていた(?)らしいが、以下の理由でだめだったらしい。

  • XML そのものも、そのためのエンジンの拡張も複雑過ぎた
  • ユースケースが狭かった

その次は JSON が台頭した。
JSONデータ形式が階層的であったり、Schema on read と相性が良かったりでスパースなデータに非常に適していた。
JSON については本文では以下のように書かれている。

私は、RDBMSJSON を単なるデータ型(数あるデータ型の中の 1 つ)としてシステムに組み込むことを期待しています。

Readings in Database Systems, 5th Edition

postgre とかは JSON 型があった気がする。
ここらへんの非構造なデータモデルの話は NoSQL, GraphQL とかと関わりがあるのだろうか。

他に言及があるデータモデルは Map-Reduce, BigTable など。
この辺りに関わる HDFS, Spark, Hadoop やデータレイクは Ch5 で詳しく話してくれるっぽい。

論文2は殆どのレガシー DBMSOracleDB2 など)がどのような仕組みで動いているのかを解説している。 また、現在の DBMS の構造はこの論文の説明とは詳細部分は大きく異なるものの、全体的なアーキテクチャは変わらないとしている。
(例えば、昔は行ストアが主流だったが今は列ストアが取って代わっている)
とはいえ、今の日本社会で動いている DB の中には所謂レガシーなものが沢山あるだろうし、学んでおいたほうが良さそうだと私も思う。

参考文献

論文1について

この論文ってデータモデル提案の歴史について書かれたものなんだけど、 そもそもデータモデルの定義をうまく言えなかったので、wiki で調べることか

データモデルは、アプリケーションである設計のための計画として使うソフトウェア工学の抽象モデルの 1 つである。班・要員間の意思疎通のための事業データの文書化、組織化、そして特にデータの格納方法や利用方法のために利用される。

データモデルは、データまたは構造化データの構造を明示的に決める。データモデルの代表的な応用は、データベース・モデル、情報システムの設計、およびデータの交換を可能にすることを含む。通常データモデルは、データモデリング言語によって規定する[3]。 出典 データモデル

ユーザーは実世界のデータを扱うが、そのデータが DB にどの様に格納されるかという低レベルの話は考えたくない。
データモデルを使用することで、(実世界の)高レベルの構成要素を使用してデータを定義することが出来る。
DB の文脈では、私達の世界の情報を DB 上でどの様に表すかという情報だと思って良さそう。

で、この論文は 1960 年~2005 年までにされたデータモデルの提案を以下の年代に分けて夫々解説した後、歴史から得られる教訓をまとめている。

  1. Hierarchical (IMS): late 1960’s and 1970’s
  2. Directed graph (CODASYL): 1970’s
  3. Relational: 1970’s and early 1980’s
  4. Entity-Relationship: 1970’s
  5. Extended Relational: 1980’s
  6. Semantic: late 1970’s and 1980’s
  7. Object-oriented: late 1980’s and early 1990’s
  8. Object-relational: late 1980’s and early 1990’s
  9. Semi-structured (XML): late 1990’s to the present

What Goes Around Comes Around.

こんなに沢山のデータモデルが提案されているとは思わなかった...。 特に耳慣れない Object-relational(OR)という提案は SQL エンジンにユーザ定義の{データ型, 演算子, 関数, アクセスメソッド}を追加した事が特徴的だったらしい。(Postgre が代表的)

個人的には、関係モデルより先に階層型データモデルが提案されたことが意外だった。関係モデルの方が最初に思いつきそうなものだけど...それは私が関係モデルに慣れてるからなだけなのかな。

ER モデルが元々 DB のデータモデルとして提案されたことも初めて知った。 今までクラス図とかスキーマ表現で使われているのは見たことがあったけど、関係モデルとの関係がよりクリアになった気がする。

TODO: XML の感想

ここ最近の NoSQL 等の話題もいつか触れていきたい。

各データモデルに対して説明が程々にあり、読みやすい論文だったと思う。

最後に、論文で載せられている教訓を記載する。

  1. 物理・論理データ独立性はとても望ましい
  2. 木構造データモデルは非常に制限的
  3. 木構造データを論理的に再構成するのが課題になっている
  4. レコード毎(record-at-a-time)の UI ではプログラマは手動でクエリ最適化を行う必要があるが、これは困難であることが多い
  5. 有向グラフは階層モデルよりも柔軟であるが複雑
  6. 有向グラフのロードとリカバリーは階層モデルよりも複雑
  7. データモデルがなんであれ、セット毎の(Set-a-time)言語は良い。物理データ独立性が格段に改善するからだ
  8. 複雑なデータモデルよりも単純なデータモデルのほうが論理データ独立性は高めやすい
  9. 技術的な議論は、たいてい市場の巨象によって解決される。技術とはあまり関係のない理由で決まることが多い
  10. クエリオプティマイザが勝てないのは、最高の record-at-a-time DBMS プログラマだけ
  11. 機能依存性は人間が理解するには難しすぎる。KISS(Keep it Simple Stupid)
  12. 性能や機能面で大きなメリットがない限り、新しい構造は成功しない
  13. パッケージは、ユーザーが "大きな痛み"を感じていないと売れない。
  14. 永続的プログラミング言語は、プログラミング言語コミュニティのサポートがなければ成功しない
  15. OR(Object-Relation)の主な利点は2つ。
    • コードはデータベースの中に入れられること(それによりコードとデータの区別が無くなる)
    • 汎用的な拡張機能により、市場の要求に素早く答えられる
  16. 新技術が広く浸透するには、標準規格(と・または)強く推す推す巨象が必要だ
  17. Shema-later はおそらくニッチな市場
  18. XQuery は構文が違うだけの OR SQL に近い
  19. XML では、企業の内外を問わず、意味論的不均一性を解決できない

What Goes Around Comes Around. 投稿主による翻訳

論文2について

論文2はかなり長いので別記事に移した。

zypressen.hatenadiary.com

【メモ】インタプリタつくった感想とメモ (Crafting Interpreters ch1~13)

crafting interpreters というサイトでloxというインタプリタを作ったので、そこで学んだことだったり感想をメモしておく。

loxの作成はこのサイトのch1~ch13の内容にあたる。
loxは動的型付けの言語で、「式、代入や制御構文、クラスと継承」等の基本的な機能を持つ。

私はこのサイトで勉強を始めるまでコンパイラインタプリタに関する知識はほぼ無かったが、苦戦するところはありつつもなんとか終わらせられるぐらいの難易度だった。
(コンパイラインタプリタもプログラムを実行するものだけど、インタプリタのほうが手軽に実行できるぐらい認識だった)

やりきるまで数ヶ月ぐらい掛かったが、取り組んで良かった点としては、例えば

  • インタプリタや言語を作る過程を辿ることで、多少なりともインタプリタの動きが理解できた
  • visitor パターンのようなプログラミング技法が学べた
    • 普段はデータ分析のためのコードしか書かないので、こういったソフトウェア開発のコードを書くのは新鮮だった...
  • 一部の章末にあるデザインノートが面白かった

等がある。特に1点目については、パーツを段階的に作成するような章構成になっていた点がよかった。

このコンテンツの良くなかった点はあまり思いつかないが、あえて上げるなら

  • 英語を頑張って読む必要がある
  • 理論的な側面はあまり記載がない

ぐらいな気がする。ただ、前者はgoogle翻訳使えばいいし、後者は他の本を参照しましょうって感じだ。

というわけで、CSを学校で習っていない人やインタプリタや言語の動きに興味がある人は是非チャレンジしてみてほしい。

作ったインタプリタの動作例を最後に載せておく。

public class BasicExample {
    public static void main(String[] args) {
    String str = """
            // 変数代入とprint文
            var message = "hello, lox!";
            print message; // hello, lox!
                            
                            
            // 制御構文
            for (var b = 0; b < 5; b = 1 + b) {
                print b;
            }
                            
            // クラス
            class Game {
                init(review_rate) {
                    this.review_rate = review_rate;
                }
                
                print_rate() {
                    print "this book's rate: " + this.review_rate;
                }
            }
                            
            // castは未実装
            Game("4").print_rate(); // this book's rate: 4

                            
            // 継承
            class MysteryGame < Game {
                init(review_rate, offender) {
                    super.init(review_rate);
                    this.offender = offender;
                }
                
                print_rate() {
                    print "this game's offender: " + this.offender;
                    super.print_rate();
                }
            }
            
            // キーワード引数は未実装
            MysteryGame("23", "A clerk at a tofu shop in the neighborhood").print_rate();
            // this game's offender: A clerk at a tofu shop in the neighborhood 
            // this book's rate: 23

            """;
    Lox.run(str);
    }
}

各章のメモ

それぞれの章で書いていたメモ書きを雑に載せる。
これからlox作りに取り組むかどうか悩んでる人は参考になるかもしれない?

ch1 序文

この章には以下のことが書かれている。

  • これを学ぶ理由
    • ニーズに合った既存のライブラリがない場合でも、パーサーやその他のツールを作成する必要がある可能性は十分にある
    • 言語の実装はいい運動になる
    • 興味
  • この本では2つのインタプリタを作る。
    • 1つ目は java で、2 つ目は c で実装する

ch2 地図

プログラムが実行するまでのステップを書いている。

文章(プログラム)

--フロントエンド--
1 . Scanning ... 字句解析。 文章を単語に分ける。
2 . Parsing ... 構文解析。 単語列を AST(抽象構文木)に変換する。
3 . Static analysis ... 静的解析。コードを実行せずに識別子等の解析を行う。

--ミドルエンド--
4 . Intermediate Representations (IR) ... 中間表現。 コードは、ソースフォームまたは宛先フォームのいずれにも緊密に関連付けられていない(セマンティクスがより明確な)中間表現で格納される場合がある。

--バックエンド--
5 . Optimization ... 最適化。 同じセマンティクスのより効率的な実装を探す
6 . Code Generation ... マシンが実行できる機械語バイトコードに変換する。
- 基本的に、アーキテクチャ固有の作業はパイプラインの下流に押した方がアーキテクチャ間で共有できる部分が多くなる。

7 . Virtual Machine ... 仮想マシン。 実行時に仮想アーキテクチャをサポートする架空のチップをエミュレートするプログラムのこと。
8 . Runtime ... 実行。

出力

ショートカットと代替ルート

ちょくちょく話題の(?)JuliaもJITコンパイルができたはず。。

コンパイラ」 ... ソース言語を他の(通常は低レベルの)形式に変換することを含む実装手法 「言語実装がコンパイラ」... ソースコードを他の形式に変換するが、それを実行しない。ユーザは自分で実行する必要あり。 「言語実装がインタプリタ」... ソースコードを受け取り、すぐに実行する。つまり、ソースコードから直接、プログラムを実行する。

コンパイラインタプリタは果物と野菜みたいなもの。
GCCコンパイラ
PHP3はインタプリタ
CPYTHONはコンパイラでありインタプリタ

ch3 Lox 言語

これから作る Lox 言語について説明がある。
デザインノートが面白かった。

ch4 字句解析

字句解析を行うScannerクラスの実装がメイン。

全体的に素直な実装だと思った。
基本的に While ループで回してマッチさせていく構造。

語彙素 ... トークンのパターンに一致するソースプログラム内の文字のシーケンス。
字句文法 ... 特定の言語が文字を語彙素にグループ化する方法を決定する規則

完成したもの

public class ScannerExample {
    static void scan_and_print(String source) {
        Scanner scan = new Scanner(source);
        System.out.println(scan.scanTokensのような);
    }
    public static void main(String[] args) {
        String ex1 = "12.5";
        Scanner scan = new Scanner(ex1);
        System.out.println(scan.scanTokens());
        // [NUMBER 12.5 12.5, EOF  null]

        String ex2 = "// this is a comment\n" +
                "(( )){} // grouping stuff\n" +
                "!*+-/=<> <= == // operators";
        scan_and_print(ex2);
        // コメントがしっかり無視されている
        // [LEFT_PAREN ( null, LEFT_PAREN ( null, RIGHT_PAREN ) null, RIGHT_PAREN ) null, LEFT_BRACE { null, RIGHT_BRACE } null, BANG ! null, STAR * null, PLUS + null, MINUS - null, SLASH / null, EQUAL = null, LESS < null, GREATER > null, LESS_EQUAL <= null, EQUAL_EQUAL == null, EOF  null]


        String ex3 = "\"neptunia\"";
        scan_and_print(ex3);
        // [STRING "neptunia" neptunia, EOF  null]

        String ex4 = "false and true";
        scan_and_print(ex4);
        // [FALSE false null, AND and null, TRUE true null, EOF  null]

        // must error
        String ex5 = "\"neptunia";
        scan_and_print(ex5);
        // [line 1] Error: Unterminated string.
    }
}

デザインノート
Pythonの文法は、文が式の中に決して現れないようになっている。
そのため、lambdaは単一の式本体のみが許される。
なるほど。

ch5 コードを表現する

この章は以下のことを行う。 - コードの表現を決める - ASTを使用することになる - Loxの文法を一部定義する - 文脈自由文法で定義する - ASTの実装 - ASTを文字列で表現するためのクラスを実装 - これは、後々作成するパーサーのデバッグなどに用いることができる

構文解析器(Parser)を作るために、そもそもコードをどう表現するかを決めないとだめだもんね。
コードの表現は、以下の2点を満たすことが望ましい。

  • パーサーはその表現を作るのが簡単
  • インタプリタはその表現を消費するのが簡単

それを満たすものの一つが抽象構文木(AST)。

Lox の文法は、文脈自由文法(CFG)で定義した。
CFGの詳しい定義はwikipediaにある。 https://ja.wikipedia.org/wiki/%E6%96%87%E8%84%88%E8%87%AA%E7%94%B1%E6%96%87%E6%B3%95

構文木の実装にあたって、javaのコードを生成するjavaのプログラムを作った。
この方式でコードを作るのは初めてだったので新鮮だった。かしこい。

また、構文木で作業する処理を書く際に、「構文木のノードの種類」に対する拡張と「処理の種類」に対する拡張の両方がやりやすいようにしたいというモチベーションから、visitor patternを使った実装を行った。 5.3.1 節のオブジェクト指向と関数型指向のプロコンをオブジェクトと関数の表での説明はかなり分かりやすかったと思う。(同様の話はクリーンコードとかに書いてたはず)

Visitor パターンそれ自体の説明はわかったようなわからなかったような・・・
別の本を見たりしてまとめ直したい。
ただ、Visitor パターンの目的が、「関数型スタイルを近似する(真似る)」ことであるのは覚えておこう。

TODO: visitor pattern

public class AstPrinterExample {
    public static void main(String[] args) {
        Expr expression = new Expr.Binary(
                new Expr.Unary(
                        new Token(TokenType.MINUS, "-", null, 1),
                        new Expr.Literal(123)),
                new Token(TokenType.STAR, "*", null, 1),
                new Expr.Grouping(
                        new Expr.Literal(45.34)));

        System.out.println(new AstPrinter().print(expression));
        // (* (- 123) (group 45.34))
    }
}

参考

ch6 式の解析

この章では、パーサーの実装を行う。
ただ、ここで全てを実装するのではなく、式をパースする部分だけを作ることになる。

パーサーは以下の2つの役割を担うことになる。 1. 有効なトークン(単語)列が与えられた場合、それに対応するASTを生成する 2. 無効なトークン列が与えられた場合、エラー検出を行う

パーサーは再帰下降構文解析という方式で実装した。

public class ParserExample {

    static void scan_and_parse_and_print(String source) {
        Lox.hadError = false;

        System.out.println("=========start============");
        Scanner scan = new Scanner(source);
        System.out.println(source);

        List<Token> tokens = scan.scanTokens();
        System.out.println(tokens);

        Parser parser = new Parser(tokens);
        Expr expression = parser.parse();

        // stop if there was a syntax error
        if (Lox.hadError) return;

        System.out.println(new AstPrinter().print(expression));
        System.out.println("\n\n");


    }
    public static void main(String[] args) {
        String ex1 = "12.5";
        scan_and_parse_and_print(ex1);

        String ex2 = "// this is a comment\n" +
                "(13.4 + 23) + (5 * 4) * 5\n";
        scan_and_parse_and_print(ex2);

        String ex22 = "// this is a comment\n" +
                "(13.4 + 23) + (5 * 4)\n";
        scan_and_parse_and_print(ex22);

        String ex222 = "// this is a comment\n" +
                "(13.4 + 23) + (5 * 4 * 5)\n";
        scan_and_parse_and_print(ex222);

        String ex3 = "\"stone\" + \" is good.\"";
        scan_and_parse_and_print(ex3);

        String ex4 = "false and true";
        scan_and_parse_and_print(ex4);

        // must error
        String ex5 = "\"neptunia";
        scan_and_parse_and_print(ex5);
    }
}

ch7 式の評価

ch7 ではパーサーの結果を評価するインタプリタを作成する。
現在のパーサーは式しかサポートしていないため、ここで作成するインタプリタも式のみをサポートする。

作成にあたり、2つのことを考える必要がある。
- どの様な値(≒オブジェクト, データ型?)を生成するか
- Lox の型と Java の型の対応付け - コードのチャンクをどのように整理するか
- Lox の構文木Java演算子を使用し評価する

動的型付け感がバリバリの実装だった。

public class InterepreterExample {
    public static void main(String[] args) {
        String valid_source = "//result is 48.5 \n (12 + 4)*3 + (2 / 4)";
        Lox.run(valid_source);
        // 48.5


        // 計算順序は考慮されない
        String valid_source2 = "//result is not 48.5 \n (12 + 4)*3 + 2 / 4";
        Lox.run(valid_source2);
        // 50

        String valid_source3 = "//result is 48.5 \n \"nep\" + \"nep\"";
        Lox.run(valid_source3);

        //String invalid_source = "12 + 4)"; // 実行されてしまう...
        String invalid_source = "(12 + 4";
        Lox.run(invalid_source);
        // [line 1] Error at end: Expect ')' after expression.
    }
}

https://github.com/kamiteku557/create_interpreters/tree/feature/ch7_evaluating_expressions

ch8 文と状態

この章では文に対応するための実装を行う。
具体的には、変数代入文と print 文を作る。

ところで、代入文や print 文を含む「文(ステートメント)」は何か値を評価するのではなく、副作用という形で役割を果たす。
また、変数代入文をサポートするには、インタプリタの内部状態を実装する必要がある。

(ゼロ幅スペースというものを初めて知った)

↓printに対応した

public class InterpreterExample {
    public static void main(String[] args) {
        String valid_source = "//result is 4\nprint 3+1;";
        Lox.run(valid_source);

        String valid_source2 = "//result is \"3+1\"\nprint \"3+1\";";
        Lox.run(valid_source2);

        String valid_source3 = "print 1;\nprint 2;";
        Lox.run(valid_source3);

        String valid_source4 = "print <200b>\"one\";\nprint true;\nprint 2 + 1;";
        Lox.run(valid_source4);
        // \u200B(ゼロ幅スペースでinvalid charactorがでる

        String valid_source5 = "//result is 48.5 \n print (12 + 4)*3 + (2 / 4);";
        Lox.run(valid_source5);
        // 48.5


        String invalid_source = "12 + 4);"; // ちゃんとエラーが出るようになった
        Lox.run(invalid_source);
        // [line 1] Error at end: Expect ')' after expression.
    }

}

代入=C言語では式なのか...びっくり(Pythonでは文だったはず) loxでも代入をthe lowest precedence expression formとするらしい。 正直、print a=2;2を返すのは違和感がある。 理由を理解できていないんだろうか。

↓代入に対応した。

public class VariableExample {
    public static void main(String[] args) {
        String valid_source = "var a; print a;";
        Lox.run(valid_source); // nil

        String valid_source2 = "var b= 4 + 2; print b;";
        Lox.run(valid_source2); // 6


        String valid_source3 = "var b=2; var c=b; print c;";
        Lox.run(valid_source3); // 2

        String valid_source4 = "var d=2; print d = 3;";
        Lox.run(valid_source4); // 3

        try {
            String invalid_source = "print e;";
            Lox.run(invalid_source);
        } catch (Exception e) {
            System.out.println(e);
            // Undefined variable 'a'.
            // [line 1]

        }


    }
}

次は(変数の)スコープを作る。 具体的には以下のことをする。 - 環境を連鎖させる実装の追加 - block構文の追加

思ったより簡単に出来てびっくり。

public class ScopeExample {
    public static void main(String[] args) {
        String valid_source = "var a = 1; {var a = 2; print a;}";
        Lox.run(valid_source); // 2

        String valid_source2 = "var b = 1; {var a = 2; print b;}";
        Lox.run(valid_source2); // 1

        String valid_source3 = "var a = 1; {var a = a +2; print a;}";
        Lox.run(valid_source3); // 3
    }
}

個人的には例3は未定義エラーのほうが直感的。

デザインノートでは暗黙の変数宣言(存在しない変数に割り当てると、自動的にその変数が作成されること)のプロコンについて話している。

In Python, assignment always creates a variable in the current function’s scope, even if there is a variable with the same name declared outside of the function. ...
Python added a global statement to let you explicitly assign to a global variable from within a function. Later, as functional programming and nested functions became more popular, they added a similar nonlocal statement to assign to variables in enclosing functions. ...
Given those, I think the simplicity argument is mostly lost.
...
As programmers have gotten more comfortable with deep nesting, functional programming, and closures, it’s become much more common to want access to variables in outer scopes. That makes it more likely that users will run into the tricky cases where it’s not clear whether they intend their assignment to create a new variable or reuse a surrounding one.

Ch9 制御フロー

ようやく、ついにifとかforみたいな制御フローを実装できるらしい。 やっとプログラミング言語らしくなってくるのかな?

まずはチューリングマシンに軽く触れていたが、正直よくわからんかった。 ここら辺の本が良さげか。
https://www.amazon.co.jp/%E8%A8%88%E7%AE%97%E3%81%A7%E3%81%8D%E3%82%8B%E3%82%82%E3%81%AE%E3%80%81%E8%A8%88%E7%AE%97%E3%81%A7%E3%81%8D%E3%81%AA%E3%81%84%E3%82%82%E3%81%AE-%E2%80%95%E5%AE%9F%E8%B7%B5%E7%9A%84%E3%82%A2%E3%83%97%E3%83%AD%E3%83%BC%E3%83%81%E3%81%AB%E3%82%88%E3%82%8B%E8%A8%88%E7%AE%97%E7%90%86%E8%AB%96%E5%85%A5%E9%96%80-John-MacCormick/dp/4873119332

dangling elseの問題に触れている。 もし入力が if (first) if (second) whenTrue(); else whenFalse();

だった時、下の2択からルールを選ぶ必要がある。

// whenFalseは not(first and second)の場合実行される
if(first)
    if(second)
        whenTrue();
else
    whenFalse();
// whenFalseは first and (not second)の場合実行される
if(first)
    if(second)
        whenTrue();
    else
        whenFalse();

loxはif節を見つけた時に貪欲にelse節を探すため、前者を表すことになる。

if文はelsethenを評価しない可能性があるという点で、他の制御フローと毛色が違う。 これはandor演算子でも同じ話があって、短絡評価なんて呼ばれていたりする。 http://ichitcltk.hustle.ne.jp/gudon2/index.php?pageType=file&id=word_short_circuit.md

構文は、彼らが短絡することを気にしない。それは意味論的な懸念だ。

andorの実装は少し面食らった。 andorassignmentに関する文法から派生させる。 元々はこうだったのが

expression     → assignment ;
assignment     → IDENTIFIER "=" assignment | equality ;

(equalirytermだけである場合もあることを思いだす)

こうなる。

expression     → assignment ;
assignment     → IDENTIFIER "=" assignment | logic_or ;
logic_or       → logic_and ( "or" logic_and )* ;
logic_and      → equality ( "and" equality )* ;

equalirylogic_orになった。 論理式は(A and B) or (C and D) or ...みたいな形であると想定しているということか。

and, orは短絡評価であるため、他のBinaryExprとは分ける必要がある。 また、bool値を返すわけではない。

print "hi" or 2; // "hi".
print nil or "yes"; // "yes".

次はwhile文を実装したんだけど、これはloxとjavaを橋渡しするだけで簡単だった。 for文はwhile文の糖衣構文なので、for文はwhileを使って実装される。

フィボナッチ数を計算するところまでできた。

    public static void main(String[] args) {
        String fibs =
                "var a = 0;" +
                "var temp;" +
                "for (var <200b>b = 1; a < 10000; b = temp + b) {"+
                "     <200b>print a;" +
                "     <200b>temp = a;" +
                "     <200b>a = b;" +
                "}";

        Lox.run(fibs);
        //0
        //1
        //1
        //2
        //3
        //5
        //8
        //13
        //21
        //34
        //55
        //89
        //144
        //233
        //377
        //610
        //987
        //1597
        //2584
        //4181
        //6765
    }

ch10 関数

この章では関数を作る。

まず、関数のsyntaxは以下のように定義する。

unary          → ( "!" | "-" ) unary | call ;
// 0回以上の関数呼び出し
call           → primary ( "(" arguments? ")" )* ;
arguments      → expression ( "," expression )* ;

関数は単項演算子より優先したいということ? 引数は0 以上のコンマ区切りでいいじゃんと思うが、どうやらその実装は非常に面倒らしい。なんでだろう。

ちなみに、元々はこうだった。

unary          → ( "!" | "-" ) unary | primary ;

今までunaryから直接primaryに行っていたのが、callを通すようになったということか。

引数の数を何処まで許すかという考えはなかった。 pythonだとどうなんだろう。

>>> def a(*args):
...     return 0

>>> a(0, 0)
0
>>> a(0 for i in range(0, 10000000))
0

>>> a(0 for i in range(0, 100000000000000))
python(3954,0x116e0f5c0) malloc: can't allocate region
*** mach_vm_map(size=800000000000000) failed (error code=3)
python(3954,0x116e0f5c0) malloc: *** set a breakpoint in malloc_error_break to debug
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError

ここの回答も詳しい。
https://stackoverflow.com/questions/714475/what-is-a-maximum-number-of-arguments-in-a-python-function

引数式を評価する順番によって、副作用次第では結果が変わる。 loxはキーワード引数には対応していない。

用語を整理しておく。
アリティ ... 関数または操作が期待する引数の数。
ネイティブ関数... 言語で予め実装されている関数。ーザーのプログラムの実行中に呼び出すことができるため、実装のランタイムの一部を形成する。

多くの言語では、ユーザーが独自のネイティブ関数を提供することもできる。 そのためのメカニズムは、外部関数インターフェース( FFI )、 ネイティブ拡張、ネイティブ・インターフェースとか呼ばれるらしい。

関数を実装した。

    public static void main(String[] args) {
        String valid_source = "fun add(a, b) {\n" +
                              "  print a + b;\n" +
                              "}\n" +
                              "\n" +
                              "print add;print add(1, 3.5);";
                              // <fn add>; 4.5
        Lox.run(valid_source);

        String valid_source2 = "var b = 3; fun addb(a) {print a+b;} addb(3);";
        // 6
        Lox.run(valid_source2);

        String valid_source3 =
                        "var a = 1;" +
                        "var b = 1;" +
                        "for (var b = 0; b < 3; b = b+1) {"+
                                "fun addab() {" +
                                "  print a + b;" +
                                "}" +
                                "addab();" +
                        "}";
                        // 2;2;2
        Lox.run(valid_source3);

    }

returnは例外みたいにscopeを飛び越えるし、実装は結構大変そうと思っていたら実際にそうらしい。 事実、loxではReturnクラスをExceptionのサブクラスとして実装している。 例外のコールスタックを抜ける性質を利用している。

組み込み関数も、以下のように実装できるようになった。 Pythonprint関数とかもこんな風に実装されているんだろうか?

  Interpreter() {
    globals.define("clock", new LoxCallable() {
      @Override
      public int arity() { return 0; }

      @Override
      public Object call(Interpreter interpreter,
                         List<Object> arguments) {
        return (double)System.currentTimeMillis() / 1000.0;
      }

      @Override
      public String toString() { return "<native fn>"; }
    });
  }

最後に、クロージャを実装したあとはこうなった。

String valid_source3 =
                "var a = 1;" +
                "var b = 1;" +
                "for (var b = 0; b < 3; b = b+1) {"+
                        "fun addab() {" +
                        "  print a + b;" +
                        "}" +
                        "addab();" +
                "}";
                // closure実装前: 2;2;2
                // closure実装後: 1;2;3
Lox.run(valid_source3);

ch11 解決とバインド

この章では、以下のことを行う。
- 動的スコープから静的スコープへの変更
- 静的解析の実装

現在の実装では、関数が宣言時のスコープ、つまり字句的(静的)スコープではなく、実行時の環境を見てしまうので、動的スコープになっている。

String str = """
        var a = "global";
        {
          fun showA() {
            print a;
          }
                        
          showA();
          // global
          var a = "block";
          showA();
          // block
        }
        """;
Lox.run(str);

これは、現在の実装では関数が「呼び出し時の環境」を参照していることが関係している。
そのため、関数の宣言時に環境をキャプチャし、呼び出し時はそちらを参照するように変更する。

意味分析 というか、loxでは変数の解決(参照先を追跡すること)を毎回行っているけど、それは不要だよねという話から始まった。
例えばforループの中にある変数xは参照先が毎ループで同じなのに、毎回解決が行われる。
確かに、静的スコープなら変数は宣言時に参照先は確定するはずなので、これは非効率。

しかも、これはソースコードを実行せずに検査することができるので静的解析のプロセスとして実施できる。
このように変数がどの宣言を参照しているかを把握するプロセスは意味解析の一例とされている。

というわけで、変数解決を調べるResolverクラスの実装を行った。

動的スコープの実装もできた。

String str = """
        var a = "global";
        {
          fun showA() {
            print a;
          }
                        
          showA();
          // global
          var a = "block";
          showA();
          // global
        }
        """;
Lox.run(str);

ch12, 13 classes, inheritance

クラスと継承の話が始まった。
クラスをそこまで使ったことがないので、まずはクラスとはなんぞやというところを以下の記事で復習した。

https://qiita.com/kaitolucifer/items/926ed9bc08426ad8e835

とはいえ、ここら辺はあんまり感想がなかった。
サイトにもあるように、興味がなかったらやらなくて良さそう。

プロパティとフィールドの違い(知らなかったのでメモ)
- フィールドは、インスタンスに直接格納される名前付きの状態ビットのこと。 - プロパティは、get式が返す可能性のある名前付きのもの。全てのフィールドはプロパティだが、すべてのプロパティがフィールドであるとは限らない。

public class ClassInstantiationExample {
    public static void main(String[] args) {
    String str = """
                class Empty{}
                var empty = Empty();
                print Empty; // Empty
                print empty; // Empty instance
                
                class Foo {
                    init() {
                    print "constructor";
                    this.bar = 12;}
                }
                var foo =  Foo();
                print foo.bar;
                """;
    Lox.run(str);
}
}
public class ClassInheritanceExample {
    public static void main(String[] args) {
    String str = """
    class Doughnut {
    cook() {
        print "Fry until golden brown.";
    }
    }

    class BostonCream < Doughnut {}

    BostonCream().cook();

    class A {
    method() {
        print "A method";
    }
    }

    class B < A {
    method() {
    print "B method";
    }

    test() {
    super.method();
    }
    }

    class C < B {}

    C().test();
                    """;
        Lox.run(str);
    }
}

【読書メモ】 Murphy Probabilistic Machine Learning: An Introduction ドラフトを読んだメモ

Probabiistic Machine Learning: An Introduction (Murphy) のドラフト(2021 Mar 8)をちろちろ読んだ感想を書き溜めてく。

1章 Introduction - 確率的アプローチを取る理由 1. 不確実性の元での決定にたいする効率的なアプローチ - 意思決定するのは人間である前提? (機械がするなら確率じゃない、Energy based modelのほうが良さそう) 2. 確率的モデリングは色んな分野で使われた統一的なフレームワーク - 帰納バイアス

Foundation

2章 Probability: univariate models 随分色々詰め込んでいた...
ヤコビアンとかの話は後半にいきそう

  • 不確実性のタイプはその理由で2つに分けられる
    1. epistemic uncertainty (model uncertainty)... データの取得方法や背後に隠された原因や構造に起因するもの
    2. aleatoric uncertainty... 内在的な変動性に起因するもの。これはデータをより多く集めても改善することはできない
      • ex) 公平なコインを投げた時、表が出る確率はp=0.5
    3. この区分けはactive learning等の応用で特に重要
      • ex) H(p(y| x, data))が大きい時、model uncertaintyであるH(p(theta| data))が大きいのか、aleatoric uncertaintyである H(p(y|x, x, theta))が大きいのか。
  • softplus 関数というものがあるらしい。
  • 積分は「和」で、畳込みは「flip and drag operation」と捉えられる

3章 Probability multivariate models

  • マハラノビス距離は「線形変換を通した、より低次元でのユークリッド距離」として考えられる

線形変換L s.t. Σ-1 = L'L, L: RD -> Rd (d ≦ D)
(y - μ)Σ-1(y - μ) = (Lδ)'(Lδ) = ||L(y - μ)||^2

4章 Statistics
相変わらずめちゃくちゃいろんな話題を詰め込んでいる。

  • モーメント法は単純だけど、理論的にはすべてのデータをより効率よく使えるMLEのほうが好ましい。
    • MLEは漸近的に最小分散であることとかが関係してるのかな
    • モーメント法は計算が楽だから、MLEの初期値をモーメント法で算出するのは賢い
  • EWMAなつかしい
    • 式(4.86)がわからん
    • 初期値を補正する式(4.87)知らなかった
  • 正規分布の分散行列のMAP推定とMLEを比較したの、わかりやすかった
    • 高次元になると分散行列の推定は特異になりがち
      • 解決策としてのMAP推定
    • 縮小推定
      • Rigde推定は対角成分にλ'で影響を与える
      • 事前分布にウィシャート(母数S = N*diag(Σ_mle))を使用した場合のMAP推定は対角成分以外を0に近づける
        • 図がわかりやすい。MAP推定の行列のスペクトルはMLEのものより真の分散行列のスペクトルに近い。固有ベクトルは影響を受けない。
  • 経験ベイズ
    • 事後推論はモデルによっては計算が大変なので、何らかの近似を用いる手法が色々ある
    • 経験ベイズはハイパーパラメタを周辺尤度を最適化するように選んだ後、そのハイパラを用いて事後分布の推定を行う。
      • これは、データがありそうなところに事前分布を寄せることになる
      • MLEよりは過学習しにくい。
    • 複数の手法を表にすると以下のようになる。 下にいくほど、よりベイズっぽくなる。
Method Definition
最尤推定 argmax_{θ} p(D|θ)
MAP推定 argmax_{θ} P(D|θ)p(θ|φ)
ML-Ⅱ 経験ベイズ argmax_{φ} ∫ p(D|θ)p(θ|φ) dθ
MAP−Ⅱ argmax_{φ} ∫ p(D|θ)p(θ|φ)p(φ) dθ
Full-ベイズ p(θ, φ| D) ∝ ∫ p(D|θ)p(θ|φ)p(φ) dθ
  • フィッシャー情報量はピーク時での曲率がどの程度きわだっているかを示す
  • バイアスバリアンストレードオフは分類問題ではあまり役に立たないと書いている。。。
    • 理由: バイアスとバリアンスが積の関係で組み合わさっているから
    • うーむ、よくわからん