Crafting Interpreters

Crafting Interpreters こた

第7回 言語処理系 勉強会 Lox本編 3章 The Lox Language

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - 動的型付け GC 基本的なデータ型 - - 算術演算子 - - 以下, 以上, 未満, 超過 論理演算子 - - 加減乗除, 単項マイナス 比較演算子 - - Boolean, Number, String, Nil 否定, 論理和(or), 論理積(and) かっこによる演算の優先度やスコープ 変数

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - 動的型付け GC 基本的なデータ型 - - 算術演算子 - - 以下, 以上, 未満, 超過 論理演算子 - - 加減乗除, 単項マイナス 比較演算子 - - Boolean, Number, String, Nil 否定, 論理和(or), 論理積(and) かっこによる演算の優先度やスコープ 変数 Why was the C syntax for arrays, pointers, and functions designed this way? - Software Engineering Stack Exchange

• https://softwareengineering.stackexchange.com/questions/117024/why-was-the-c-syntax-for-arrays-pointers-and-functions-designed-this-way

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - 動的型付け GC 基本的なデータ型 - - 算術演算子 - - 以下, 以上, 未満, 超過 論理演算子 - - 加減乗除, 単項マイナス 比較演算子 - - Boolean, Number, String, Nil 否定, 論理和(or), 論理積(and) かっこによる演算の優先度やスコープ 変数 Bacon04Unified.dvi (washington.edu)

• https://courses.cs.washington.edu/courses/cse590p/05au/p50-bacon.pdf

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - 動的型付け GC 基本的なデータ型 - - 算術演算子 - - 以下, 以上, 未満, 超過 論理演算子 - - 加減乗除, 単項マイナス 比較演算子 - - Boolean, Number, String, Nil 否定, 論理和(or), 論理積(and) かっこによる演算の優先度やスコープ 変数

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - 動的型付け GC 基本的なデータ型 - - 算術演算子 - - 以下, 以上, 未満, 超過 論理演算子 - - 加減乗除, 単項マイナス 比較演算子 - - Boolean, Number, String, Nil 否定, 論理和(or), 論理積(and) かっこによる演算の優先度やスコープ 変数

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - 動的型付け GC 基本的なデータ型 - - 算術演算子 - - 以下, 以上, 未満, 超過 論理演算子 - - 加減乗除, 単項マイナス 比較演算子 - - Boolean, Number, String, Nil 否定, 論理和(or), 論理積(and) かっこによる演算の優先度やスコープ 変数

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - 動的型付け GC 基本的なデータ型 - - 算術演算子 - - 以下, 以上, 未満, 超過 論理演算子 - - 加減乗除, 単項マイナス 比較演算子 - - Boolean, Number, String, Nil 否定, 論理和(or), 論理積(and) かっこによる演算の優先度やスコープ 変数

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - 動的型付け GC 基本的なデータ型 - - 算術演算子 - - 以下, 以上, 未満, 超過 論理演算子 - - 加減乗除, 単項マイナス 比較演算子 - - Boolean, Number, String, Nil 否定, 論理和(or), 論理積(and) かっこによる演算の優先度やスコープ 変数

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - 動的型付け GC 基本的なデータ型 - - 算術演算子 - - 以下, 以上, 未満, 超過 論理演算子 - - 加減乗除, 単項マイナス 比較演算子 - - Boolean, Number, String, Nil 否定, 論理和(or), 論理積(and) かっこによる演算の優先度やスコープ 変数

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - if, for, while 関数 クロージャ クラス 継承

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - if, for, while 関数 クロージャ クラス 継承

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - if, for, while 関数 クロージャ クラス 継承 そもそもクロージャとは？ 関数が状態を 持てる仕組み 1. カプセル化 2. 関数の動的生成 JavaScriptを学ぶ上でつまずきやすいポイントを理解 するための連載【第 2回】2つの利用シーンから理解する「クロージャ」活用法

• https://www.r-staffing.co.jp/engineer/entry/20221021_1

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - if, for, while 関数 クロージャ クラス 継承

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - if, for, while 関数 クロージャ クラス 継承

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - if, for, while 関数 クロージャ クラス 継承

Loxの構文 文法はCライクで機能はJavaを組み合わせたような構文 - if, for, while 関数 クロージャ クラス 継承

第9回 言語処理系 勉強会 Lox本編 13章 Inheritance

スーパークラスとサブクラス 新しい予約語を追加したくないので、Rubyに習って < を使う

スーパークラスとサブクラス Javaだと全てのクラスにはスーパークラスが存在するが、 Loxでのスーパークラスはオプション スーパークラス名をトークンでは なく、 Expr.Variable として保存 変数としてラップすることで、パーサー がクラスを解決できるようになる

スーパークラスとサブクラス このままでは自分自身を継承できるような構文も書けてしまうので排除する

スーパークラスとサブクラス また、クラスでないものをスーパークラスに書けてしまうのでこれも排除する

メソッドの継承 こ れ だ け (ちょっと感動した)

スーパークラスメソッドの呼び出し

スーパークラスメソッドの呼び出し Q. 右の図のコードを実行すると結果は？

スーパークラスメソッドの呼び出し Javaで同じように書いてみたら

スーパークラスメソッドの呼び出し

スーパークラスメソッドの呼び出し スーパークラスのmethodを呼 び出したらいいじゃん って思うけど、簡単にはいかない

スーパークラスメソッドの呼び出し Cから呼び出された test は直接どのクラスに属しているか分からない super.method()を正しく解決するには... 1. このsuper式はクラスBで定義された ↑この情報が必要 2. よって、Bのスーパークラス（A）の methodを呼ぶべき なので、 LoxFunction に LoxClass への参照を保存する

スーパークラスメソッドの呼び出し

スーパークラスメソッドの呼び出し クラス宣言時にスーパークラスが 指定されている場合は、 スーパークラスの全ての メソッドを含む新しいスコープを 作成して、 super という名前 を定義する クラスのメソッドの解決が 完了したら そのスコープを破棄

第10回 言語処理系 勉強会 Lox本編 18章 Types of Values

Tagged Unions Loxは動的型付け言語であり、1つの変数の値がbool, number, string等になる また、C言語ではデータ構造を生のビット列から自由に構築する必要があり、 0と1の無機質な羅列からデータ構造を見出し、任意の型に適応させる必要がある そして、値を扱うためには２つの問題に対処する必要がある 1. 2. 値の型をどのようにして表現するのか 1 * true のような式を実行時にエラーにするために、型を知る必要がある 値自体をどうやって保存するのか 3 という数が 4 という数と違うということを認識する必要がある また、これらの問題に「効率的」に対処する必要がある

Tagged Unions

Tagged Unions 構造体ではメモリの無駄が多く、できる限り少ないビット数で型を表現したいので、 共用体を使用する 共用体は同じメモリ領域を複数の型が共有する構造

Tagged Unions 共用体から意味のある値を取り出すためには 中身のデータそのものに加えて 「今、何の型のデータが入っているか」という 情報（タグという）が必要となる タグを付加情報として持ち、常に正しい型で データを得られるように設計された共用体を 特にタグ付き共用体という

Tagged Unions

Lox Values and C Values タグ付き共用体で指定した型に合わせてデータ型を適切に変換する

Dynamically Typed Numbers print -false のような構文に対処するためにランタイムエラー処理を作る

Two New Types 準備が整ったので、 nil, true, false を追加する

Two New Types せっかく true と false を導入したので、論理演算子も追加する !, ==, <, > の４つを追加する !=, <=, >= の3つは4つを組み合わせて表現する a != b は !(a == b), a <= b は !(a > b) になる

Two New Types 比較は値を取り出して比較する memcmp() でやればいいと思うかもしれないが、 パディングに不定な値が入るため比較できない

第11回 言語処理系 勉強会 Lox本編 23章 Jumping Back and Forth

If Statements if文を追加する jloxではJavaのif文を使って制御構文を実装していたが、 cloxではネイティブなCPUと同じように制御構文を実装する といってもCPUを実装したことがあるなら 容易に想像がつくと思う

If Statements ただし、どれだけジャンプすればいいかが分からないので、バックパッチ法で対処する 値が決定できないものについては、とりあえずその値が必要とされる場所を覚えてお き、値が決定した段階で覚えておいた場所に値を埋め込む手法

If Statements いったん、 0xff を充てて、後から実際の オフセットを計算してパッチを充てる

If Statements elseも実装する 単純に then の下に実装したら良い気がするが、これではthenの後にelseも実行し てしまう

If Statements なので、thenが終わった後にも JUMP 命令を置く必要がある

If Statements また、if文の条件を抜けた後にはスタックにプッシュ したアドレスをポップする必要があるので、 右図のようなフローになる

Logical Operators and と or は短絡評価を行うので、elseをもつifのような働きを行う and or

While Statements 基本はifと同じで、()内の条件を読み取り、真であれば中身を実行する 唯一異なるのは、 emitLoop という関数があること

While Statements

For Statements for文は 1. 2. 3. 初期化子に式または変数宣言が入る while と同じく、条件式がある ループ本体実行後にインクリメントが実施される この３つの要素があり、かつこれらはオプション 今回は while をベースに前後にfor用の処理を行うことでforを実装する

For Statements 初期化子が存在する場合 (セミコロンがある場合) は、値を評価する この際、値か式か不明なので両方評価する必要がある また、ここで宣言されたもののスコープも設定する

For Statements これも省略されていればセミコロンがあるので、ない場合は条件式があるということ 条件式がある場合は、評価する

For Statements インクリメントもオプションなため、右括弧があるかないかで判定する また、インクリメント用の変数の宣言はループ開始前にされるが、 インクリメント自体はループ終了後に実行されるという性質を持つため、ちょっと面倒 今回はJumpで対処する

For Statements

第12回 言語処理系 勉強会 Lox本編 28章 Methods and Initializers

Method Declarations メソッドとメソッドコール、イニシャライザを実装する jloxでも実装したが、それに比べて7倍高速化 メソッドを表現するにはjloxと同じように、クラスにメソッドのハッシュ表を持たせる Key: メソッド名 Value: メソッド本体のOnjCloｓure markTable関数が、表エントリーのKeyとValueをトレースする jloxではクラス宣言とそれに含まれるすべてのメソッドをASTノードとしてアクセス可 cloxではバイトコードとして管理しなくてはいけない

Method Declarations 新しいメソッドを定義するとき、VMに必要なのは 1. メソッド名 2. メソッド本文のためのクロージャ 3. メソッドを束縛するクラス

Method Declarations

Method References メソッドの参照方法は２つあるのでコードも別々に用意 あとから呼び出される可能性もあるので アクセス元のインスタンスを覚えておく そのためにランタイムに新しい型が必要になる

Method References

This Thisも追加する

Instance Initializers 1. 2. 3. ランタイムは、クラスのインスタンスが生成されるたびに自動的に イニシャライザーを呼び出す。 インスタンスを構築する呼び出し元は、イニシャライザ関数自体が何を返すかに 関係なく、イニシャライザ終了後に常にインスタンスを取得する。 イニシャライザーは、これを明示的に返す必要はない。 イニシャライザが値を返すことは禁止されている。（参照されないから）

Instance Initializers

Instance Initializers

Optimized Invocations まだメソッドコールが遅いので最適化する といってもその都度メモリアロケーションしている部分をやめるだけ