[Rust] 自作言語で配列への代入にはまった時、左辺値が助けてくれるかも

Rust で作るプログラミング言語シリーズです。

https://www.amazon.co.jp/dp/4297141922

今回の記事は、 Mascal プログラミング言語を作るにあたって私がはまった集成体型(Aggregate type^[1])の更新方法に関してです。

書籍で作った言語 (Ruscal) は集成体型をサポートしていないので今回の課題は当てはまりませんが、実用的な言語を目指したら配列などをサポートする際問題になる確率が高いです。

本稿は AST インタプリタ型言語とバイトコードコンパイラの両方に当てはまります。

問題

ここでいう集成体型とは、配列や構造体など、「部分」を持ち、個別に更新できる型のことです。

たとえば、配列は要素の更新ができることが期待されます。

var a = [1, 2, 3];
a[1] = 20;
print(a); // [1, 20, 3]

なお、タプルはここでいう集成体型には含みません。なぜなら、タプルは変更不可であり、部分への代入は許されていないからです^[2]。

var a = ("Hello", "world!");
a.0 = "Goodbye"; // Error!

しかしながら、これを素直に実現しようとすると非常に困難です。なぜなら、代入先がどのオブジェクトなのかを評価するためには、式をそのまま評価してしまってはいけないからです。

オブジェクトの内部定義

まず前提として、オブジェクトの値は次のような列挙型で定義されています。

pub enum Value {
    F64(f64),
    F32(f32),
    I64(i64),
    I32(i32),
    Str(String),
    Array(Rc<RefCell<ArrayInt>>),
    Tuple(Rc<RefCell<TupleInt>>),
}

そして、式の評価をする eval 関数は次のようなシグネチャを持ちます^[3]。

pub(crate) fn eval(e: &Expression, ctx: &mut EvalContext) -> EvalResult<Value>;

つまり、式の AST (Expression)を引数に取り、結果を Value 型で返すわけです。バイトコードコンパイラの場合は AST を一度バイトコードに直しますが、そのバイトコードも式の結果として Value を返すことには変わりありません。

式の評価

例えば、次のような式があったとします。

a[0]

これを評価すると a が表している配列オブジェクトの最初の要素のコピーを Value 型で返します。しかしながら、これが次のような代入文(代入式でもよいですが)の一部として現れた場合、一時的なコピーの値を置き換え、配列の中の要素は変化しません。これはプログラマの意図とは異なるでしょう。

a[0] = 42;

集成体型が登場する前は、代入文の左辺は識別子しか出現しないので、変数名をルックアップすれば更新先のオブジェクトが見つけられました。しかし、左辺に任意の式が現れるようになると困難が生じます。

以下に解決策の候補を挙げますが、上手くいく解決策は最後の「左辺値の評価✔」で、それ以外は試行錯誤の記録なので、解決策を知りたいだけの方は読み飛ばしても構いません。

配列への代入演算子を定義する方法 💀

配列要素への代入を表す []= のような演算子を定義し、通常の変数への代入とは別に構文を定義すればよいのではないかと思うかもしれません。しかしこれはスケールしません。なぜなら配列要素の参照はネストできるからです。

a[0][1] = 42;

さらに構造体も混ざって入れ子になってくる可能性があります。このような全てのケースに構文を定義するのは現実的ではありません。

people[0].children[0].first_name = "John";

全てのオブジェクトを参照型にする解決策 💀

次に思いつくのは、オブジェクトをすべて Rc<RefCell<_>> で包み、式の評価時にはその参照を返すという策です。もし代入文の左辺が参照型を返したら、その参照先を書き換えるようにします。右辺の場合は参照外しを行い値に変換します。

配列の内部表現は次のようになります。

struct ArrayInt {
    values: Vec<Rc<RefCell<Value>>>,
}

enum Value {
    // ...
    Array(Rc<RefCell<ArrayInt>>),
    Ref(Rc<RefCell<Value>>),
}

これは機能しますが、効率という観点では非常に悪い策です。例えば、三つの要素を持つ配列 a の要素への参照を取ろうとすると、下図のようになります。

var a = [1, 2, 3];
a[2]

全ての変数へのアクセスに Rc ポインタを辿ることと、 RefCell チェックが必要になります。メモリ効率も非常に悪いです。プリミティブ型の配列であれば一要素当たり4か8バイトが意味のあるデータですが、 Rc と RefCell のポインタ二つ分のオーバーヘッドが増え、8か16バイト余計にメモリが必要になります。これはサイズが10,000の配列などには明らかに向いていません。

配列の内部表現の効率化

少なくとも、多数のオブジェクトが含まれる配列に関してはもう少し効率化したいところです。そこで次に思いついたのは、下のような「配列参照型 (ArrayRef)」を値の一種として定義することです。

 struct ArrayInt {
-    values: Vec<Rc<RefCell<Value>>>,
+    values: Vec<Value>,
 }

 enum Value {
     // ...
     Array(Rc<RefCell<ArrayInt>>),
     Ref(Rc<RefCell<Value>>),
+    ArrayRef(Rc<RefCell<ArrayInt>>, usize),
 }

内部表現は次のようになります。少なくとも配列の要素は一続きのメモリになり、無駄な参照外しや RefCell のチェックは必要なくなります。

しかしながら、配列の要素アクセスが式に登場した時は必ずこの参照型を返さねばならず、代入するか否かで参照外しをするかを判断しなければなりません。

もっといい方法がないものか考えあぐねて半年ほどたったころ、次の方法を思いつきました。

左辺値の評価 ✔

C や C++ における左辺値と右辺値

左辺値 (lvalue) とは、 C や C++ コンパイラで使われる用語で、右辺値 (rvalue) と対で使われます。簡単に言うと、代入できる値が左辺値、できない値が右辺値です^[4]。

たとえば、リテラルは常に右辺値です。次の文はリテラル数値に代入しようとしているのでエラーになります。

1 = 2;

gcc の場合は次のようなエラーが表示されます。

rval.c:3:4: error: lvalue required as left operand of assignment
    3 |  1 = 2;
      |

「左辺値は名前がある変数、右辺値は名前のない変数」という覚え方もありますが、これは必ずしも正しくありません。配列の要素は名前で直接参照することはできませんが、左辺値です^[5]。

a[0] = 2;

また、ポインタの参照先は左辺値ですので、名前がついていなくても、参照外し演算の結果には代入できます^[6]。

*(int*)0x4000 = 2;

名前の由来は、代入演算子の左辺と右辺ではあるのですが、左辺値は左辺に現れるとは限らず、右辺値も右辺に現れるとは限りませんので、あまりこだわらず固有名詞として覚えた方が良いでしょう。たとえば a[0] = 1 の a[0] は左辺値ですが、 0 はリテラルなので右辺値です。

普通のプログラマはあまり知る必要のない概念ですが、 C++11 から右辺値参照 (rvalue reference) という概念が登場し、 move semantics に関わるようになったので馴染み深くなりました。

左辺値の評価

さて、ここからが本題です。今までの試行錯誤の結果わかることは、左辺値を評価する時と右辺値を評価する時ではやりたいことが異なるということです。左辺値を評価するときは代入の対象としてオブジェクトの実体への参照を持っておきたいですが、右辺値の場合は値のコピーで良いです。

これをモデル化するため、左辺値の評価を行う関数を別に定義します。シグネチャは次のようになります。

pub(super) fn eval_lvalue(
    expr: &Expression,
    ctx: &'ctx mut EvalContext,
) -> EvalResult<LValue>;

ここで、 LValue というのは左辺値を表す概念的な型で、評価時のコンテキストにしか存在しません。具体的には、インタプリタのメモリには置きません。

/// An LValue is a description of a target memory to be written to.
pub(super) enum LValue {
    /// A variable identified by a name
    Variable(String),
    /// Reference to a refcounted variable, e.g. an array element.
    ArrayRef(Rc<RefCell<ArrayInt>>, usize),
}

Variable バリアントはローカル変数を表し、 a = 1 のような単純な変数への代入に使われます。その時の変数テーブルから変数名を参照することで実際のオブジェクトを見つけることができます。

ArrayRef バリアントは配列の要素への参照です。実は先ほど「全てのオブジェクトを参照型にする解決策 💀」で出てきた Value のバリアントと全く同じです。違いは、 LValue として目的が明確に分かれていることです。 a[0] などの式の評価時に使われます。

これだけだと、ネストした配列参照 a[0][1] はどう表すのかわからないかもしれませんが、実は ArrayRef の第一メンバは「内側」の配列への参照を直接持てるので、ネストした表現を LValue に入れる必要はありません。

これを使って、代入演算子 (VarAssign) の評価時には次のように書き換えることができます。

pub(crate) fn eval<'src, 'native>(
    e: &Expression<'src>,
    ctx: &mut EvalContext<'src, 'native, '_>,
) -> EvalResult<RunResult>
where
    'native: 'src,
{
    Ok(match &e.expr {
        // ...
        ExprEnum::VarAssign(lhs, rhs) => {
            let rhs_value = unwrap_run!(eval(rhs, ctx)?);
            let lhs_result = eval_lvalue(lhs, ctx)?;
            match lhs_result {
                LValue::Variable(name) => {
                    if let Some(var) = ctx.variables.borrow_mut().get_mut(name.as_str()) {
                        *var.borrow_mut() = rhs_value.clone();
                    }
                }
                LValue::ArrayRef(arr, idx) => arr.borrow_mut().values[idx] = rhs_value.clone(),
            }
            RunResult::Yield(rhs_value)
        }
        //...
    })
}

注目は右辺の let rhs_value = unwral_run!(eval(rhs, ctx)?); で右辺値を評価する eval を使い、左辺の let lhs_result = eval_lvalue(lhs, ctx)?; で eval_lvalue を使っているところです。このように非対称な評価関数を使うことで、 a[1] = a[2] のような式も無駄なく評価できます。右辺は値のコピーを返し、左辺はその参照先を置き換えることができます。

何より嬉しい副作用は、左辺値でない値へ代入しようとしたときに適切なエラーメッセージが出せることです。 1 = 2; のような式を実行しようとすると、次のようなメッセージが出せるようになりました。

Error in run(): Cannot assign to a literal: 1

もちろん、タプルの要素への代入もエラーになります。

var tup: (i32, i32) = (1, 2);
tup.1 = 20; // Error in run(): Expression tup.1  is not an lvalue.

詳細は省きますが、バイトコードへのコンパイル時も同様の左辺値評価用の関数を分けることによって最適化できました。「全てのオブジェクトを参照型にする解決策 💀」では実引数など値セマンティクスを持たせたいところでは参照外しを行う Deref インストラクションを挟むなどの苦肉の策を弄していたのですが、この変更によってインストラクションもシンプルになり、コンパイラのコードもすっきりしました。

おわりに

これは構文(Syntax)と意味論(Semantics)が異なる典型的な例です。構文を表す AST では、 VarAssign バリアントは次のように定義されています。

pub(crate) enum ExprEnum<'a> {
    // ...
    VarAssign(Box<Expression<'a>>, Box<Expression<'a>>),
    // ...
}

つまり、左辺と右辺は同じ Expression です。

構文は同じでも、適用する意味論を変えることによって挙動をコントロールすることができます。構文としては左辺と右辺はほとんど同じなので、パーサを使いまわすことができ、そのうえで効率的なインタプリタ・コンパイラを実装することができるのです。

余談

実はこの方法を思いついたのは Wascal という別のプロジェクトでのことでした。 Wascal は WebAssembly に直接コンパイルする言語ですが、同じように構造体の要素への代入が問題になりました。 WebAssembly ランタイムには専用のヒープメモリは定義されていませんが、基本的にコンパイラがメモリ管理を行うコードを生成します。ここで Linear memory に集成体型を置くと、そのアドレスの扱いが本稿の参照と同じように問題になります。

[2024/10/07 修正]

集合型と訳していた Aggregate type を規格に合わせて集成体型に直しました。

脚注

1. Aggregate type の日本語訳は多数あり、これといった良い用語がありません。ここでは C99 相当の JIS X 3010:2003 で定義されていると思われる「集成体型」という用語を使います。他には、集約型、集合型、集合体型、合成体型、アグリゲート型(そのまんまですが)などの呼び名が使われているようです。詳しくはコメント欄をご覧ください。

2. タプルを可変にするか否かは言語ごとに設計思想が分かれます。 Python は変更できませんが、意外なことに Rust はできます。

3. 実際のコードでは break 文をサポートするため RunResult という型を返しますが、これは次のように定義されている Value のラッパー型です。本文では理解を簡単にするため Value を返すものとしています。また、ライフタイムも省略しています。

   pub enum RunResult {
       Yield(Value),
       Break,
   }
   

4. C++ ではさらに glvalue, xrvalue, prvalue などといったカテゴリが増えていますが、普通のプログラマがここまで知る必要はないでしょう。

5. C では配列のインデックスはポインタ演算 *(a + 0) のシンタックスシュガーにすぎませんので、実質的にポインタの参照先が左辺値であることと同じことを言っています。

6. この例は PC では恐らく Segfault するでしょうが、組み込み CPU では memory mapped IO などがあるので、指定したアドレスに直接書き込むことはあります。実際にはマクロで名前付き定数にすることが多いでしょう。