『Rustで作るプログラミング言語』を読む

2章のruststack
https://github.com/msakuta/rustack/tree/master

https://veykril.github.io/tlborm/introduction.html

3章以降のruscal
https://github.com/msakuta/ruscal/tree/master

文脈自由文法の説明とかなくいきなり実装する感じ、いいな
写経しやすいし楽しい

2.8 複数行のソースコードへの対応

parse_batchの引数をimpl BufReadで定義してるおかげで、BufReaderやCursorを引数とすることができる
impl Trait記法というらしい

blocksは、{を見つけたらとりあえず積んでおく場所で、blocksが空じゃない場合は、評価せずに詰む
また、{}の数が合わない場合はパニックになる

複数行にブロックがまたがる場合、再起呼び出しじゃなくてblocksで対応する実装に変更した
これは再帰下降パーサとは違うアプローチらしい

再帰下降パーサは、構文解析の状態を関数呼び出しスタック（つまり再帰？）で管理し、読み出しの進捗はバッファで管理するというもの
→ここの文章いまいちピンとこなかった

refってなんだっけと思ったら、所有権が移動しないように、参照だよということを示すキーワードらしい

すでに脳内シミュレーションができなくなってしまった（？）

2.9 関数呼び出し

まずこれがわからん

• 単一のフィールドを持つタプル構造体
• このフィールドは関数ポインタ型fn(&mut Vm)を保持する
• 戻り値は持たない
• 関数をラップした新しい型、みたいなイメージらしい

struct NativeOp(fn(&mut Vm));

これをrustではnewtypeパターンと呼ぶらしい

この理由が深淵らしい（？）

• Rustでは関数ポインタに対するDebug, PartialEq, Eqトレイトをderive属性で自動定義dけいない
• Rustでは外部クレーとや標準ライブラリの型にトレイトを実装できない
• Orphan ruleと呼ばれる制約らしい

この制約をはずせる代わりにvalue.0といった構文で中身にアクセスする必要がある

これは関数のポインタ同士の比較

impl PartialEq for NativeOp {
    fn eq(&self, other: &NativeOp) -> bool {
        self.0 as *const fn() == other.0 as *const fn()
    }
}

下記の場合の流れを改めて追ってみる

/double { 2 * } def
/square { dup * } def

10 double puts
10 square puts

コンソールたくさん仕込んだ
block -> stackに移動するあたりがわかったら意味がわかった

コンソール仕込んでみた

word: "/double" ,stack: [], vars: 12, blocks: []
  eval else, pushing to stack: Sym("double")

word: "{" ,stack: [Sym("double")], vars: 12, blocks: []

word: "2" ,stack: [Sym("double")], vars: 12, blocks: [[]]
  pushing to block: Num(2)

word: "*" ,stack: [Sym("double")], vars: 12, blocks: [[Num(2)]]
  pushing to block: Op("*")

word: "}" ,stack: [Sym("double")], vars: 12, blocks: [[Num(2), Op("*")]]
pop block
  eval else, pushing to stack: Block([Num(2), Op("*")])

word: "def" ,stack: [Sym("double"), Block([Num(2), Op("*")])], vars: 12, blocks: []
  eval op: "def",
  eval native: <NativeOp>
  eval else, pushing to stack: Block([Num(2), Op("*")])

word: "/square" ,stack: [], vars: 13, blocks: []
  eval else, pushing to stack: Sym("square")

word: "{" ,stack: [Sym("square")], vars: 13, blocks: []

word: "dup" ,stack: [Sym("square")], vars: 13, blocks: [[]]
  pushing to block: Op("dup")

word: "*" ,stack: [Sym("square")], vars: 13, blocks: [[Op("dup")]]
  pushing to block: Op("*")

word: "}" ,stack: [Sym("square")], vars: 13, blocks: [[Op("dup"), Op("*")]]
pop block
  eval else, pushing to stack: Block([Op("dup"), Op("*")])

word: "def" ,stack: [Sym("square"), Block([Op("dup"), Op("*")])], vars: 13, blocks: []
  eval op: "def",
  eval native: <NativeOp>
  eval else, pushing to stack: Block([Op("dup"), Op("*")])

word: "" ,stack: [], vars: 14, blocks: []
word: "10" ,stack: [], vars: 14, blocks: []
  eval else, pushing to stack: Num(10)

word: "double" ,stack: [Num(10)], vars: 14, blocks: []
  eval op: "double",
  eval stack: [Num(10)],  eval block: [Num(2), Op("*")]
  eval else, pushing to stack: Num(2)
  eval op: "*",
  eval native: <NativeOp>

word: "puts" ,stack: [Num(20)], vars: 14, blocks: []
  eval op: "puts",
  eval native: <NativeOp>
20

word: "10" ,stack: [], vars: 14, blocks: []
  eval else, pushing to stack: Num(10)

word: "square" ,stack: [Num(10)], vars: 14, blocks: []
  eval op: "square",
  eval stack: [Num(10)],  eval block: [Op("dup"), Op("*")]
  eval op: "dup",
  eval native: <NativeOp>
  eval op: "*",
  eval native: <NativeOp>

word: "puts" ,stack: [Num(100)], vars: 14, blocks: []
  eval op: "puts",
  eval native: <NativeOp>
100

関数呼び出しの実態はこれか

            Value::Native(op) => {
                op.0(vm)
            }

なんかわかった気がする
https://github.com/tsuka-ryu/ruststack/commit/0b67a0956d5401dfa627cbf6c8ee3358f2abc369

2.10 関数の再帰呼び出し

関数呼び出しが行われるたびにvarsに新たなHashMapをプッシュし、関数から抜ける時にポップする
変数テーブルのスタックの最上位から順番に探していき、最初に見つけた変数を返す挙動になる
これがshadowingという動作

めっちゃ簡単に実装できてすごい

2.11 WebAssemblyへのコンパイルとブラウザでの実行

https://msakuta.github.io/rustack/
試せる

3.2 構文へのマッチ

参照とライフタイム

Rustでは全ての参照にはライフタイムがつくけど、省略できる（elided）

fn recognizer<'src>(input: &'src str) -> &'src str;
fn recognizer(input: &str) -> &str; // 同じ意味

UTF-8文字列からの文字の取り出し

Rustの文字列はUTF-8符号化された文字列なので、可変長文字コード
1文字のサイズが1-4バイトまで変化する、のでnext()で取得する

3.5 木構造の構築

source関数を再帰的に呼び出して、括弧の中身はサイドsourceで構文解析する

地味にIdentの型やidentの返り値の型が変わってる

Ident
Ident(&'src str),

fn ident(mut input: &str) -> (&str, Option<Token>) {
fn ident(mut input: &str) -> Option<(&str, Token)> { // Optionだけ返す型になってる

LParenで再帰的にsourceを呼ぶ

                Token::LParen => {
                    let (next_input, tt) = source(next_input);
                    tokens.push(tt);
                    next_input
                }

RParenまで達したら、TokenTreeに突っ込む

                Token::RParen => {
                    return (next_input, TokenTree::Tree(tokens));
                }
                _ => {
                    tokens.push(TokenTree::Token(token));
                    next_input
                }

最終的にはTokenTreeに全部包む

Rustの興味深い言語使用の一つ、Rustの手続き型マクロにおいて、入力と出力のTokenTreeという型をとり、トークン列を自在に処理できるという仕様がある
ユーザ独自の言語をRustの文法の一部にできることを意味する（？）

3.6 式の構文技

add()関数を構文解析したいけど、無限再帰が発生する
正しい解決策は、再起呼び出しの代わりにループで左結合演算子を表現すること

実行順序で混乱したけど、expre()自体もaddやparenの中で呼び出されてるから再帰構造になってる

3.7 パーサコンビネータ nom

• いくつか順番に試して最初に成功したものを返すalternative
• 順番に出現することを認識し、ひとつでも失敗すれば全体が失敗となる順番パターン
  • この2つをnomというクレートで簡略化できる

nom、コンビネータは「パーサを引数にとり、新たなパーサを返す関数」
パーサコンビネータは再帰下降パーサ簡潔にかけるようにしただけのもの

急にnomとかいうのが出てきてびっくり

https://docs.rs/nom/latest/nom/

https://github.com/rust-bakery/nom/blob/main/doc/choosing_a_combinator.md

3.8 Parsing Expression Grammerによる構文解析

pestはPEGで記述された文法を解析するパーサを生成するライブラリ
YaccやBisonなどに似ているが、Rustの手続きマクロを使ってコンパイラがパーサを生成することと、文法のみを記述する専用のファイル形式を持つ

BNFは曖昧な文法が記述できてしまうが、PEGは曖昧でない
BNFは A | Bといった記法が曖昧な部分、どちらを選んでも適合できる
PEGでは、「Aが適合するか試して、失敗したらBを試す」という意味になる
曖昧性はなくなるが、直感に反する場合がある

短絡評価的？な挙動が玄人向けらしい（？）

紹介だけだった

3.10 関数呼び出しの構文と評価

ラムダ式とクロージャ

クロージャを含む式は生存期間の問題でスコープの外に渡せない的な感じ（？）

Rustのラムダ式がデフォルトで参照でキャプチャするためです

Fn、FnMut、FnOnce

FnOnceは一度だけ使用（消費）できる関数

moveを使えば解決もできる
変数ごとにキャプチャのされ方を変える方法もあるよ

let to_move = 1;
let to_clone = 2;
let as_res = 3;
let f = {
  let cloned = to_clone.clone();
  let as_ref = &as_ref;
  move |arg| to_move + cloned + *as_ref

流し読みしたのでスキップ
わからなくなったら戻って読む

4.9 関数定義

関数定義構文の設計思想

二大派閥

• トップレベルでの定義のみを許す
  • C
• 文として許すか
  • Python, JavaScriptなど
    • クロージャを実装するために重要
  • Rust, C++
    • クロージャは専用構文
  • Rustでは単純にネストした関数は外部変数を参照できないので、クロージャオブジェクトをラムダ式で作る必要がある

クロージャはASTインタプリタではいいけど、バイトコードへ変換するときに難しくなる
ここではクロージャではなく、単純な関数とする

StackFrameに関数と変数の状態を保存する

StackFrame構造体を考える

• コンストラクタ的な関連関数newを実装するか、
• deriveマクロに#[derive(Default)]
  • これは、型の自明なデフォルト値がある場合にdefaultメソッドで構築できるようにするDefaultというトレイトを、自動的に実装するマクロです。

1つのHashMapコンテナにすべての関数定義を入れるため、impl Trait記法は使えません（？）
動的ポリモーフィズムを使ってBox<dyn Trait>として返す必要があります（？）

よくわからん

「1つの HashMap コンテナにすべての関数定義を入れる」
→ HashMap<String, ???> のような形で、複数の異なる関数を1つの HashMap に格納したい。

「impl Trait 記法は使えません（？）」
→ impl Trait は静的ディスパッチ（コンパイル時に具体的な型が決まる）なので、HashMap に異なる型の関数を統一的に入れることができない。

なーるほど

GPTに聞いた

impl Trait で格納できない例

use std::collections::HashMap;

fn foo<T: Into<i32>>() -> impl Fn(T) -> i32 {
    |x: T| x.into() + 1
}

fn bar<T: Into<i32>>() -> impl Fn(T) -> i32 {
    |x: T| x.into() * 2
}

fn main() {
    let mut map: HashMap<String, impl Fn(i32) -> i32> = HashMap::new(); // ❌ エラー！
    map.insert("foo".to_string(), foo()); // `foo` の戻り値の型は異なるためエラー
    map.insert("bar".to_string(), bar()); // `bar` も異なる型を返すためエラー
}

この場合、foo と bar はそれぞれ別の 匿名の型 (impl Fn(T) -> i32) を持ってしまうため、コンパイル時に HashMap に統一できません。
Box<dyn Fn(i32) -> i32> を使うと、異なる型でも dyn Fn にキャストして統一できます。

そうか、TSと違ってimpl Fn(T) -> i32みたいなのは個別の匿名の型と認識されるのか

関数の引数渡し意味論

• 値渡し
• 参照渡し
• 名前渡し

C言語型やRustでは参照やポインタで参照渡しできるけど
Ruscalでは値渡しのみ