式指向構文が言語処理系にもたらす複雑性

式指向の構文 (式の途中に文を書けるような構文) は便利な反面、言語設計の面でちょっとした課題があるという話

式指向の構文

この記事ではいわゆる式指向の構文の一例として Rust風の構文 を考えます

ブロック式 は次のように複数の文と1個の式からなる式です

    { 文の並び…; 式 }

文と違って、式は 評価 (計算) すると値が得られるものです。 ブロック式を評価する場合、文を順番に実行してから、末尾にある式を評価します。その末尾の式の値がブロック式の値となります

式の評価の途中で一時的に使う値をローカル変数に束縛 (代入) したりできます

let y = {
    let x = f();
    g(x, x) // 末尾の式
};

(上記は let y = 式; というローカル変数の宣言で、初期化式の部分にブロック式が置かれているかたち)

また、条件分岐を表す if や match も式です。if式では分岐の結果として評価された側のブロックの値が、そのif式の値となります

let x = if p() { f() } else { g() };

let x = match try_f() {
    Some(x) => x,
    None => return,
};

以降、サンプルコードはRust風の構文で書きます。ただし型システムや処理系はRustと同じとはかぎらず、あくまで 疑似コード のスケッチと思ってください

ジャンプとスタックマシン

式指向の構文では、式の評価の途中で ジャンプ し、その式の評価が最後まで完了しないことがあります

スタックマシンで計算を行おうとすると、式の途中でのジャンプには問題があります。 スタックマシンは部分式の値をスタックに積みながら式の評価を進めるので、その途中でジャンプをしてしまうと、スタックに部分式の値が残ってしまう ことになります

例:

fn f() {
    1 + { return 2; 3 }
}

この関数をスタックマシンのコードにそのままコンパイルすると、次のような不正な振る舞いになります

• 1 をスタックに積む
• 2 をスタックに積み、return する。スタックから返り値 2 をpopして、関数から抜ける
• 3 をスタックに積む。スタックから2つの値をpopし、和をスタックに積む (← ジャンプしたので、これは実行されない)

1 をスタックに置いたまま関数を抜けてしまっているため、関数の実行の前後でスタックの状態が維持されていません

解決策

解決策はいくつかあります:

• 式の途中でジャンプする際に、不要になる値をスタックから取り除くコードも生成する
• 式の外側にジャンプするようなコードを禁止してしまう
• スタックマシン以外の方法を使う (レジスタマシンとか)

正準化 (canonicalization)

追記: 正準化(canonicalize)などの手順により、式の評価の途中でジャンプが起きないように変形しておく方法もあります (近況 2019-04-30 にも似たような話を書きました)

上記のサンプルコードでいえば、次のような変形を行います

• a + b → { let x = a; let y = b; x + y } と変形 (一時変数の導入)
• let x = { 文…; 式 }; → 文…; let x = 式; と変形 (letの平坦化)

fn f() {
    // 元: 1 + { return 2; 3 }

    let x = 1;  // 1 + …
    return 2;   // { return 2; … }
    let y = 3;  // { …; 3 }
    x + y       // _ + _
}

関数全体を文の並びに変形し、式の途中でジャンプしないようにできます (導入した一時変数がレジスタのような役割をしている)

ジャンプする式の型

静的型システムを備える言語を考えます

break, return のようなジャンプ命令も構文的に式であると決めたとします (実際にRustはそう)。ジャンプ式を評価すると、ジャンプが起こって評価が中断するため、評価して得られる値というものは存在しません。このような式にどう型をつければよいでしょうか

例えば次の match 式です:

    let x: T = match parse(input()) {
        Ok(value) => value,  // x ← value
        Err(_) => return,  // x ← ???
    };
    // …

parse(…) の結果が Ok(value) なら、match の値は value に評価され、変数 x = value として後続の処理に続きます。しかし parse の結果が Err(_) なら関数から return します

Rustの場合、 return 式には ! (never) という型がつきます。! はあらゆる型の 部分型 とされています。そのため value の型 T がなんであれ、match 式の型を T としてよいです

もうひとつの方法として、ジャンプする式の出現ごとに メタ型 を割り当てる方法があります。メタ型は、型推論において未知の型を表すものです。α をメタ型として、return 式の型は α であるということにして、残りの型推論によって α の型を決定する、ということにします。上記の例では、Err 側にある return 式の型を α とします。match 式の型は「T または α」であり、α = T と代入すれば問題なく型がつきます

どちらの場合も結果は同じですが、ポイントは それを解決する何らかの仕組み が必要ということです。部分型 (!) を使う場合は部分型を導入する必要があり、メタ型を使う場合はメタ型を含む型推論の仕組みが必要です

ほかの案として、ジャンプ式に決め打ちで特定の型をつけることもできます (この方法を使う言語があるかは知りません)。その場合、上記のような match 式は型検査が通らないことになります。return を外に動かすような書き換えが必要となり、「式指向らしさ」が減ってしまいます

(追記: C++ にパターンマッチ機能であるinspect式を追加する提案があります。制御を返さないブランチに構文的に印をつけることで、そのブランチの評価値の型を型検査時に無視する、という方法が述べられているようです。 参考: Pattern Matching - p1371r3.pdf)

if式の後ろのセミコロン

C言語のような「セミコロン必須」の構文を考えます。if文の構文を単純に「文」から「式」に移動すると、従来のif文の記述が式文になることで、 一見余計なセミコロンが必要になる という問題があります

もともと、式文やif文の定義を次のようにしたとします (elseは省略):

    # 式文
    ExpressionStatement = Expression ";"

    # if文
    IfStatement = "if" "(" Expression ")" Block

    # 文
    Statement = ExpressionStatement | IfStatement | …

    # 式
    Expression = …

これらを式に統合したとします (ただし式文は文に残す):

    # 式文
    ExpressionStatement = Expression ";"

    # 文
    Statement = ExpressionStatement

    # if式
    IfStatement = "if" "(" Expression ")" Block

    # 式
    Expression = IfExpression | …

この構文で「普通のif文」は1個の式であることになります

    if (cond) {…}

文が必要な場所にこれを書こうとすると、式文は末尾に ; が必要なので、一見余計なセミコロンを書くことになります

let x = {
    if (cond) {…}; // ← 式文
//               ^ このセミコロンが必要
    f()
};

(ちなみに、構文から「文」自体をなくして、式を順番に評価するための 式; 式 という式を導入しても、セミコロンが必須なら状況は同じです)

解決策

ひとつの解決策は if キーワードで始まる文を特別扱いすることです。つまり、if で始まる式文だけ末尾のセミコロンをなくすという、部分的なセミコロンの省略ルールを作ります

ただし、if式から始まる式文のパースがうまくいかない問題があります。例えば次の文は、. の左辺にif 式がある構造になっています:

    if flip() { you } else { opponent }.win();
//  -----------------------------------^

JavaScriptにすでに似たような問題があります。function f() {} という記述は関数を定義する「文」でもあり、いわゆる関数オブジェクトを表す式でもあります。構文上、前者が優先されるため、function キーワードで始まる式文を書くことはできません。回避策として (function(){})() のように式の先頭が function にならないようにする方法があります。この回避策はおそらくコミュニティにも受け入れられており、「文優先」の構文でも問題ないと思います

また、Rustは 打ち切り規則 と呼ばれる構文上の規則を用意しています。打ち切り規則は、おおまかにいうと「文頭にif式がある場合、それが明らかに他の式の一部でなければ、末尾のセミコロンの省略を許す」というものです。例えば次のコードは、2つの文にパースされます:

    if cond {…}  // 末尾にセミコロンなし
    f();

一方、次のコードにおいてif式は . の左辺となっています。このケースではセミコロンが省略されているとはみなされません

    if cond {…}.f();
    //         ^ . は左辺に式が必要なので文のパースを続ける

(特別扱いされているのは . と ? だけで、二項演算子は打ち切られるらしい: if cond { 42 } / 2 など)

参考: Rustの文でセミコロンを省略してよい条件 - 簡潔なQ

(追記(2024-10-10): 文章を全体的に調整しました)

関連記事

• コンパイラでのエラーの扱い
• 判別共用体が共通フィールドを持てたら嬉しい
• プログラミング言語の構文とセミコロン
• nullはポインタだがリファレンスではない
• 円周率チャレンジにアルゴリズムでチャレンジ