無駄と文化

実用的ブログ

Rust はコストのかかるコードを書くのが苦痛になるようにデザインされている(?)

Rust は「コストのかかるコードは書くのが苦痛であるべき」という思想のもとデザインされている気がする。
というのも Rust を書いていると「意図的にショートカットが用意されていない」と思える場面があるからだ。

いくつか例を挙げてみようと思う。

 

文字列の連結

String 型の変数 s を所有しているときに、s の 後ろに 文字列リテラルを連結するのは簡単だ。+ 演算子で文字列の連結ができる。

let mut s = String::from("hello");
s = s + ", world";
println!("{}", s);  // => hello, world

一方で s の 前に 連結するには一手間必要になる。

let mut s = String::from("world");
s = "hello, ".to_string() + &s;
println!("{}", s);  // => hello, world

+ 演算子の左オペランドは String でなければいけないので "hello, " をそのまま置くことはできない。.to_string() メソッドで String 型に変換している。1
右オペランドは &str 型でなければいけないので &s として &str に変換している。

 

文字列の連結がなぜこんなにも左右非対称なのか、実装を追ってみよう。

+ 演算子の挙動は Add trait を実装することで定義される。

doc.rust-jp.rs

Rust では Add<&str> for String が定義済みなので + 演算子を使って String 型と &str 型が連結できる。
他方で Add for &str は未定義なので、&str 型と String 型の連結はできない。2

これによって String 型の変数 s を後ろに伸ばしていくのは簡単で、前に伸ばしていくためには冗長な記述が必要という非対称性が生まれている。

 

このような状況はおそらく意図的で。&str + String がシンプルに書けないのは &str + String を実行するのにコストが大きいからだ。

Rust の String 型は内部的に Vec として実装されている。Vec は「8ビット非負整数の可変長配列」だ。

Vec はデータを前から詰めて保持するために、後ろに伸ばすのは容易で前に伸ばすのにはコストがかかる。String 内部的には Vec なので同じ制約下にあるはずだ。

ちなみにここで言う「前に伸ばすのにはコストがかかる」というのは、連結後の文字列が収まるメモリを別の場所に確保してから連結後の文字列を配置し直す必要があるということだ。
String + &str はあらかじめ確保していたメモリに連結後の文字列が収まらなかったときだけ再配置すればいい一方で、&str + String は 毎回かならず メモリの再配置が必要になる。

そういう都合で String + &str は簡単に書けて、&str + String には意図的にショートカットが用意されていないんじゃないだろうか。

 

ユーザー定義型は (可能であっても) 自動的には Copy にならない

2つめの例は値の複製について。

Rust には言わずと知れた所有権システムがある。*1
Rust の基本戦略は値を所有している変数を一つだけに制限して、できるだけ借用 (参照) で間に合わせるというものだ。

そのため Rust の代入は基本的に所有権を移動 (ムーブ) させる。

let x = vec![1, 2, 3];
let y = x;  // ここでムーブが発生し x は所有権を失う
println!("{:?}", x);
//               ^ エラー: ムーブ済みの値を借用しようとしている

この制限を回避する方法はいくつかある。

  1. 変数を .clone() する
  2. 型を Copy にしておく
  3. Rc などの型で包む

いちばんよく使われるのは 1. だろう。
Rust の多くの型は .clone() メソッドを実装していて、値を複製して別の変数に渡すことができる。

let x = vec![1, 2, 3];
let y = x.clone();  // x を複製して値の所有権を y に渡す
println!("{:?}", x);  // => [1, 2, 3] 
//              ^ OK: x の所有権は失われていない

.clone() はお手軽だが、所有権がムーブする箇所で一々 .clone() をタイプするのは面倒でもある。もし型が Copy trait を実装していれば .clone() を省略できる。
Copy trait を実装した型は所有権がムーブするタイミングで自動的に値が複製される。元の変数が所有権を失うことはない。

let x = 42;  // 42: u8 は Copy trait を実装している
let y = x;   // .clone() を書かなくても自動的に複製される
println!("{:?}", x);  => 42
//              ^ OK: x の所有権は失われていない

char, bool, u8 などが Copy になっている。
さらに Copy な型を組み合わせたタプルもまた Copy になる。例えば (char, bool, u8) は Copy だ。

let x = ('🦀', true, 42);  // (char, bool, u8) は Copy になる
let y = x;                 // .clone() を書かなくても自動的に複製される
println!("{:?}", x); // => ('🦀', true, 42)
//              ^ OK: x の所有権は失われていない

 

Copy な型はいわば .clone() を免除されているわけだ。
これは「Copy な型が占有するメモリ」が「それの参照が占有するメモリ」に比べて充分に小さいからだ。

Rust において char は4バイト, bool は1バイト, u8 は1バイトだ。一方それらの参照である Box, Box, Bool のサイズはどれも1バイトだ。
u8 な値を二つの変数に持たせるのに、値そのものを持たせるのも片方に参照を持たせるのもメモリサイズは変わらない。
参照を持たせることで節約にはならないし、暗黙に .clone() したとしても無駄遣いにはならない。

というわけで Copy な型は手動で .clone() する必要がなく、代入時に値が自動的に複製される。

 

さて「Copy のタプルも Copy になる」ということを踏まえてユーザー定義型について見てみよう。
Copy な型だけを含む struct や enum は Copy に なれる#[derive(Clone, Copy)] で修飾すればいい。

#[derive(Clone, Copy)]
struct Foo { val: u8 }

let foo = Foo { val: 42 };
let bar = foo;
println!("{}", foo.val); // => 42

なんとも簡単だが 自動的に Copy になる訳ではない。

ユーザー定義型が (可能であっても) 自動的に Copy にならない理由は「将来的に拡張されて Copy でない型を含むようになったときに困るから」と説明されている。
Copy でない型を含む型はどうがんばっても Copy になれない。将来的にも Copy な型しか持たせないことを心に決めたうえで、実装者が責任を持って #[derive(Clone, Copy)] をタイプする必要がある。

 

というわけで実はユーザー定義型を安易に Copy にするべきではないのだ。現実的なユースケースではムーブを回避したいときには一々 .clone() することになる。

そういう意味で Rust は 一々 .clone() をタイプさせるように デザインされていると言える。

プログラマが .clone() をタイプするときデータが複製されている様を意識せずにはいられない。複製元の値と同じだけメモリが消費されてる様を意識するというストレスがかかるわけだ。
そういう少しのストレスによって Rust はプログラマに極力 .clone() せずに済むコードを書くように仕向ける。

一々 .clone() をタイプするのは苦痛で。ストレスが無いのは一つの値を一つの変数だけが所有しているコードだ。
苦痛から逃れるコードを書こうとすると、自然に「値の複製」も「ガベージコレクション」も必要のないコードになっていく。

所有権システムの制約も Copy な型の制約も、理想的なコードを書かせるための意図したデザインと思えてくる。

 

Vec が map() メソッドを持たない

Rust の Vec は便利だ。色々なメソッドがあり、ほとんどが安全だ。
が、とある不思議なことに気づく。Vec には .map() メソッドが無い。

.map() メソッドは Iterator に定義されている。
Vec の中の値を変換しようとしたら、

  1. まず Vec を Iterator に変換し
  2. .map() して
  3. 結果の Iterator を再び Vec に変換する

という手順を踏む必要がある。

とはいえこれらの手順はどれも簡単だ。
Vec から Iterator を作るには .into_iter() メソッドを呼び出すだけでいい。
Iterator から Vec の変換は .collect() メソッドがやってくれる。

let vec = vec![1, 2, 3];

let iter = vec.into_iter();
let iter = iter.map(|n| n * n);
let vec: Vec<u8> = iter.collect();

println!("{:?}", vec);  // => [1, 4, 9]

簡単ではあるが、いかにも冗長だ。

いちいち変数に格納せずともメソッドチェーンで書くこともできる。そうするといくらかスッキリする。

let vec = vec![1, 2, 3];

let vec: Vec<u8> = vec.into_iter().map(|n| n * n).collect();

println!("{:?}", vec);  // => [1, 4, 9]

が、やはり冗長じゃないか?

Vec が .map() を持たない背景には遅延評価的な思想がある気がしている。
ここでいったん脇道に逸れて Iterator の .map() メソッドについて見てみよう。

 

Iterator の .map() は Iterator が持つ値を変換するメソッド ではない

.map() は std::iter::Map を返すように実装されている。std::iter::Map は別の Iterator と「値を変換する関数 f」を内包した構造体だ。
こんな感じの実装になっている。

pub struct Map<I, F> {
    pub(crate) iter: I,
    f: F,
}

impl<B, I: Iterator, F> Iterator for Map<I, F>
where
    F: FnMut(I::Item) -> B,
{
    type Item = B;
    fn next(&mut self) -> Option<B> {
        match self.iter.next() {
            Some(v) => Some(self.f(v)),
            None => None,
        }
    }
}

std::iter::Map は値を変換可能な状態を保持しているだけで、値が必要になるまで変換は行わないのだ。
「値が必要になったとき」とは iter.next() が呼ばれたときだ。

 

std::iter::Map の存在を知れば .map() の見方も変わってくる。Iterator の .map() は変換可能な状態を作っているだけ。

必要になるまで変換を行わないのは、全ての値に対して変換を行わなくてもいい場合があるからだ。
例えば .skip() でいくつかの要素を読み飛ばしたり .find() で特定の要素だけをピックアップしたときには、捨てられる要素に対しての変換は省略できる。

Rust はコレクションの中に使われない値があるかもと想定しているので「必要になったときに初めて値を用意する」という処理を抽象化して用意している。それこそが Iterator だ。

 

というわけで Vec を .map() するときに Iterator を経由するのは使われない値があるときに備えてのことだと言える。
Vec に .map() を直接実装してしまうと、そのような効率化のための意図は消し飛んでしまう。タイプ数が減る代わりに非効率さが覆い隠される。

プログラマが vec.into_iter().map().collect() をタイプするときに思うことは、どうにかして .collect() を省けないか?ということだ。
.collect() を呼んだ時点で内部的に .next() が呼ばれて、遅延されていた std::iter::Map の処理は即座に実行されていまう。もし必要ない要素があるなら、Vec に変換することなく処理を進めるのが効率がいい。

Vec を .map() するための冗長さは裏側で起こっていることをプログラマに思い出させるためにある。

 

Rust はコストのかかる箇所にマークをつける

Rust を学んでいて面白いと思ったのは、Rust のデータ型はコストのかかる処理を覆い隠したりしないことだ。
むしろコストのかかる箇所が見えるように個別の型やトレイトが用意されている。

この記事では、

  • 後ろ側に連結が容易な String 型
  • 自動的な複製を許す Copy トレイト
  • Lazy な Iterator トレイトと正格な Vec 型

を例に挙げた。

これらの型やトレイトはプログラマが見て裏側の処理の性質を知るのにも役立つし。もっと直接的に、とあるトレイトの有無を条件に制約を課すガードとしても使われている。*2

 

コストのかかる処理をマークするための型があることで、マークするためにわずかにタイプ数が増える。そうやってわずかにストレスを感じさせて、コストのかかる処理を避けるよう誘導しているんじゃないだろうか。

もちろんコストのかかる処理をカジュアルに書ける記法を用意することも技術的に可能だ。でも Rust はそのようにデザインされていないと感じる。むしろコストのかかる箇所が明確に見えるように、コストのかかる処理を書いていて苦痛に感じるようにデザインされている気がする。

 

まとめ

ここで紹介した冗長さはどれも意図的だと私は思っている。
Rust を書いていて苦痛なときは「もっと効率のいい書き方がある」というメッセージを受信しているときだ。

Rust は苦痛を型で表現しているのが面白い。
文字列連結の例では String と &str が、値の複製の例では Copy が、.map() の例では Iterator や std::iter::Map が。これらの型はコストを覆い隠すのではなく、そこにコストがあることを表明している。

この記事を読んで「いや Rust でもコストが覆い隠されているデザインはあるぞ」とか「他の言語ではこういう工夫がされているよ」とかの意見や知見があればぜひ教えてほしい。
私もこの意見に確信があるわけではなく、まだまだ考え始めたところだ。

 

 

私からは以上です。

 

おまけ

X でアンケートを取ってみたら見事に真っ二つに割れた図


  1. Rust では文字列リテラル "some string" は &str 型に解決される
  2. 連結不可能というわけではなく、左オペランドを String 型に右オペランドを &str 型に変換しておく必要があるということ

*1:そしてガベージコレクションが無い

*2:いわゆる「トレイト境界」

二重数を使って2階微分を計算する方法 と 超二重数への発展

二重数という数があります。「その数自体は0でないのに2乗すると0になる数」のことを二重数と呼びます。


x \ne 0\ \land\ x^2 = 0

実数の範囲で  x^2 = 0 を満たす  x x = 0 のみなので、 x \ne 0 でかつ  x^2 = 0 となるような数があるならばそれは 実数ではない ということになります。
そのような実数ではない数  \varepsilon の存在を認めて、実数と  \varepsilon の線型結合  a + b \varepsilon の形で書いた数が二重数と定義されます。

二重数にはいろいろとおもしろい性質があるのですが、それについては色々な人が記事を書いているのでそちらを参照してみてください。私のおすすめはこれ↓↓↓です。

www.ajimatics.com

kamino.hatenablog.com

この記事では二重数の応用の一つである関数の自動微分について取り上げます。

 

関数に二重数を与えると微分係数が求まる

突然ですが関数  f(x) = x^4 + x^2 の微分について考えてみましょう。ひとまず  x = 1 における微分係数を求めるところから始めます。

高校数学の知識で関数  f(x) = x^4 + x^2 x = 1 における微分係数は、  f(x) を微分して導関数  f'(x) を求めてから  x = 1 を代入すればいいとわかります。

 \begin{align}
f(x)&=x^4 + x^2 \\\
f'(x)&=4x^3 + 2x \\\
f'(1)&=4+2 \\\
&=6
\end{align}

というわけで求める微分係数は  6 なんですが。二重数を使えば導関数を求めずにこれを計算できるという面白い性質があります。

具体的には  f(x) x = 1 + \varepsilon を代入して、

 \begin{align}
f(1 + \varepsilon) &= (1 + \varepsilon)^4 + (1 + \varepsilon)^2 \\\
&= (1 + 4\varepsilon + 6\varepsilon ^2 + 4\varepsilon ^3 + \varepsilon ^4) + (1 + 2\varepsilon + \varepsilon ^2)
\end{align}

ここで  \varepsilon は2乗すると  0 になるような数だったことを思い出すと上記の式を大幅に整理できます。なんせ2以上の累乗の項は消えてしまうからです。

 \begin{align}
f(1 + \varepsilon) &= (1 + \varepsilon)^4 + (1 + \varepsilon)^2 \\\
&= (1 + 4\varepsilon + 6\varepsilon ^2 + 4\varepsilon ^3 + \varepsilon ^4) + (1 + 2\varepsilon + \varepsilon ^2) \\\
&= (1 + 4\varepsilon) + (1 + 2\varepsilon) \\\
&= 2 + 6\varepsilon
\end{align}

さてこれにて  x = 1 における微分係数がもとまりました。上記の式で  6\varepsilon の項に注目してください。 \varepsilon の係数になっている  6 x = 1 における  f(x) の微分係数です。

...何もかも唐突ですね。
これは

 \begin{align}
f(x_0 + \varepsilon) = f(x_0) + f'(x_0)\varepsilon
\end{align}

という二重数の性質を応用して  f(x) の微分係数を求めたのです。上記の式では  f(x) x = x_0 + \varepsilon を代入して整理した後、 \varepsilon のついた項の係数が  f'(x_0) に等しいと云っています。

 

なんとも不思議ですが、ともかく  f(x) x = x_0 + \varepsilon を代入して式を整理するだけで微分係数  f'(x_0) が機械的に計算できてしまうのです。

 

微分係数と云わず導関数を求めた方が納得感があるかもしれない

さきほどの例で、二重数を使って関数  f(x) = x^4 + x^2 x = 1 における微分係数を求めてみました。たったの1例ということもあって、初見ではなかなか納得しづらいんじゃないかと思います。同じ方法で導関数を導出してみると納得感があるんじゃないでしょうか。

さきほどは  f(x) x = 1 + \varepsilon を代入しましたが、今度は  x = t + \varepsilon を代入してみます。

 \begin{align}
f(t + \varepsilon) &= (t + \varepsilon)^4 + (t + \varepsilon)^2 \\\
&= (t^4 + 4t^3\varepsilon + 6t^2\varepsilon ^2 + 4t\varepsilon ^3 + \varepsilon ^4) + (t^2 + 2t\varepsilon + \varepsilon ^2) \\\
&= (t^4 + 4t^3\varepsilon) + (t^2 + 2t\varepsilon) \\\
&= (t^4 + t^2) + (4t^3 + 2t)\varepsilon
\end{align}

ここで右辺に着目し  \varepsilon を含んでいない項を  g_0(t) \varepsilon を含む項の係数部分を  g_1(t) として抽出してみましょう。

 \begin{align}
f(t + \varepsilon) &= g_0(t) + g_1(t) \varepsilon \\\
\\\
g_0(t) &= t^4 + t^2 \\\
g_1(t) &= 4t^3 + 2t
\end{align}

ここで  g_0(x),  g_1(x) t についての関数とみなしましょう。変数を置き換えても関数自体は変わらないので変数  t を変数  x に置き換えてみます。

 \begin{align}
g_0(x) &= x^4 + x^2 \\\
g_1(x) &= 4x^3 + 2x
\end{align}

はい、鋭いかたはお気付きでしょう。上記の  g_0(x),  g_1(x) はそれぞれ  f(x),  f'(x) に等しくなっていますね。

 \begin{align}
g_0(x) &= x^4 + x^2 = f(x)\\\
g_1(x) &= 4x^3 + 2x = f'(x)
\end{align}

このことから、

 \begin{align}
f(x + \varepsilon) = f(x) + f'(x)\varepsilon
\end{align}

という性質に納得感が出てきたんではないでしょうか。

 

2階微分を求めたい

さて二重数をつかって微分係数や導関数が求まることがわかりました。
が、先ほどまで見た例は 1階の 微分係数や 1階の 導関数でしたね。もし2階微分を求めたくなったら、二重数をつかって計算をすることは可能でしょうか?

答えは 条件付きの Yes です。

二重数というアイデアはそのままつかえますが 2階の二重数 を持ち出す必要があります。

2階の二重数とは先ほどまでの  \varepsilon とは別の基底  \varepsilon\,_1,  \varepsilon\,_2 を用いて、

 \begin{align}
a + b\varepsilon\,_1 + c\varepsilon\,_2
\end{align}

の形で書ける数です。

具体的な計算を見せる前に二重数の基底になる  1,  \varepsilon\,_1,  \varepsilon\,_2 の積について見ていきます。

 1  \varepsilon\,_1  \varepsilon\,_2
 1  1  \varepsilon\,_1  \varepsilon\,_2
 \varepsilon\,_1  \varepsilon\,_1  2\varepsilon\,_2  0
 \varepsilon\,_2  \varepsilon\,_2  0  0

縦軸と横軸の重なる部分が積算の結果になっています。例えば  \varepsilon\,_1 \cdot \varepsilon\,_1 = 2\varepsilon\,_2,  \varepsilon\,_1 \cdot \varepsilon\,_2 = 0 です。

 

2階の二重数を導入したので、先ほどと同じ要領で関数  f(x) = x^4 + x^2 の2階微分を求めていきましょう。
さきほどは  x = t + \varepsilon を代入して整理してから  t = x と変数変換しましたが、まぁ正直煩わしいので最初から  f(x + \varepsilon) を展開整理して計算を進めていきます。ちなみに、ここで云う  \varepsilon \varepsilon\,_1 のことです。

 \begin{align}
f(x + \varepsilon\,_1) &= (x + \varepsilon\,_1)^4 + (x + \varepsilon\,_1)^2 \\\
&= (x^4 + 4x^3\varepsilon\,_1 + 6x^2\varepsilon\,_1 ^2 + 4x\varepsilon\,_1 ^3 + \varepsilon\,_1 ^4) + (x^2 + 2x\varepsilon\,_1 + \varepsilon\,_1 ^2)
\end{align}

先ほど示した演算表を見ながら 2乗, 3乗, 4乗の項を整理していきましょう。

 \begin{align}
f(x + \varepsilon\,_1) &= (x + \varepsilon\,_1)^4 + (x + \varepsilon\,_1)^2 \\\
&= (x^4 + 4x^3\varepsilon\,_1 + 6x^2\varepsilon\,_1 ^2 + 4x\varepsilon\,_1 ^3 + \varepsilon\,_1 ^4) + (x^2 + 2x\varepsilon\,_1 + \varepsilon\,_1 ^2) \\\
&= (x^4 + 4x^3\varepsilon\,_1 + 6x^2 \cdot 2\varepsilon\,_2) + (x^2 + 2x\varepsilon\,_1 + 2\varepsilon\,_2) \\\
&= (x^4 + x^2)  + (4x^3 + 2x)\varepsilon\,_1 + (12x^2 + 2)\varepsilon\,_2
\end{align}

最終行に注目してください。それぞれの項の係数が、

 \begin{align}
f(x) &= x^4 + x^2 \\\
f'(x) &= 4x^3 + 2x \\\
f''(x) &= 12x^2 + 2
\end{align}

となっていますね。

というわけで2階の二重数を使って2階微分を求められました。

 

では3階微分は?

さてここで歩みを止めずに3階微分へと進みましょう。2階の二重数を使って3階微分は求まるでしょうか?
先ほどの同じアイデアで可能ですが、(お察しの通り) 3階の二重数を持ち出す必要があります。

2階の二重数とは基底  \varepsilon\,_1,  \varepsilon\,_2,  \varepsilon\,_3 を用いて、

 \begin{align}
a + b\varepsilon\,_1 + c\varepsilon\,_2 + d\varepsilon\,_3
\end{align}

の形で書ける数です。

再び積の演算表をお見せします。

 1  \varepsilon\,_1  \varepsilon\,_2  \varepsilon\,_3
 1  1  \varepsilon\,_1  \varepsilon\,_2  \varepsilon\,_3
 \varepsilon\,_1  \varepsilon\,_1  2\varepsilon\,_2  3\varepsilon\,_3  0
 \varepsilon\,_2  \varepsilon\,_2  3\varepsilon\,_3  0  0
 \varepsilon\,_3  \varepsilon\,_3  0  0  0

さて、3階の二重数の導入が済んだら先ほどと同じように  f(x + \varepsilon\,_1) を展開整理します。

 \begin{align}
f(x + \varepsilon\,_1) &= (x + \varepsilon\,_1)^4 + (x + \varepsilon\,_1)^2 \\\
&= (x^4 + 4x^3\varepsilon\,_1 + 6x^2\varepsilon\,_1 ^2 + 4x\varepsilon\,_1 ^3 + \varepsilon\,_1 ^4) + (x^2 + 2x\varepsilon\,_1 + \varepsilon\,_1 ^2) \\\
&= (x^4 + 4x^3\varepsilon\,_1 + 6x^2 \cdot 2\varepsilon\,_2 4x \cdot 6\varepsilon\,_3) + (x^2 + 2x\varepsilon\,_1 + 2\varepsilon\,_2) \\\
&= (x^4 + x^2)  + (4x^3 + 2x)\varepsilon\,_1 + (12x^2 + 2)\varepsilon\,_2 + 24x\varepsilon\,_3
\end{align}

そして各基底の係数を並べて眺めます。

 \begin{align}
f(x) &= x^4 + x^2 \\\
f'(x) &= 4x^3 + 2x \\\
f''(x) &= 12x^2 + 2 \\\
f'''(x) &= 24x
\end{align}

簡単ですね?

 

n階の二重数

ここまでの話を見ていて「さっさとn階の二重数を導入したほうが早いな」と思った読者も多いでしょう。
実際、4階の二重数, 5階の二重数, ... と拡張していくことは簡単です。積の演算表だけさっと示しましょう。

4階の二重数の積の演算表

 1  \varepsilon\,_1  \varepsilon\,_2  \varepsilon\,_3  \varepsilon\,_4
 1  1  \varepsilon\,_1  \varepsilon\,_2  \varepsilon\,_3  \varepsilon\,_4
 \varepsilon\,_1  \varepsilon\,_1  2\varepsilon\,_2  3\varepsilon\,_3  4\varepsilon\,_4  0
 \varepsilon\,_2  \varepsilon\,_2  3\varepsilon\,_3  6\varepsilon\,_4  0  0
 \varepsilon\,_3  \varepsilon\,_3  4\varepsilon\,_4  0  0  0
 \varepsilon\,_4  \varepsilon\,_4  0  0  0  0

 

5階の二重数の積の演算表

 1  \varepsilon\,_1  \varepsilon\,_2  \varepsilon\,_3  \varepsilon\,_4  \varepsilon\,_5
 1  1  \varepsilon\,_1  \varepsilon\,_2  \varepsilon\,_3  \varepsilon\,_4  \varepsilon\,_5
 \varepsilon\,_1  \varepsilon\,_1  2\varepsilon\,_2  3\varepsilon\,_3  4\varepsilon\,_4  5\varepsilon\,_5  0
 \varepsilon\,_2  \varepsilon\,_2  3\varepsilon\,_3  6\varepsilon\,_4  10\varepsilon\,_5  0  0
 \varepsilon\,_3  \varepsilon\,_3  4\varepsilon\,_4  10\varepsilon\,_5  0  0  0
 \varepsilon\,_4  \varepsilon\,_4  5\varepsilon\,_5  0  0  0  0
 \varepsilon\,_5  \varepsilon\,_5  0  0  0  0  0

 

そして4階の二重数を使えば4階までの微分が求まる、5階の二重数を使えば5階までの微分が求まるというところも予想を裏切りません。
なんだか逆に退屈ですね。というわけで 超二重数 に話を進めましょう。

 

超二重数

超二重数は無限個の基底  1,  \varepsilon\,_1,  \varepsilon\,_2,  \varepsilon\,_3, ... の線形結合よって表現される無限次元線型空間です。

積の演算表を示します。

 1  \varepsilon\,_1  \varepsilon\,_2  \varepsilon\,_3  \varepsilon\,_4  \varepsilon\,_5
 1  1  \varepsilon\,_1  \varepsilon\,_2  \varepsilon\,_3  \varepsilon\,_4  \varepsilon\,_5
 \varepsilon\,_1  \varepsilon\,_1  2\varepsilon\,_2  3\varepsilon\,_3  4\varepsilon\,_4  5\varepsilon\,_5  6\varepsilon\,_6
 \varepsilon\,_2  \varepsilon\,_2  3\varepsilon\,_3  6\varepsilon\,_4  10\varepsilon\,_5  15\varepsilon\,_6  21\varepsilon\,_7
 \varepsilon\,_3  \varepsilon\,_3  4\varepsilon\,_4  10\varepsilon\,_5  20\varepsilon\,_6  35\varepsilon\,_7  56\varepsilon\,_8
 \varepsilon\,_4  \varepsilon\,_4  5\varepsilon\,_5  15\varepsilon\,_6  35\varepsilon\,_7  70\varepsilon\,_8  126\varepsilon\,_9
 \varepsilon\,_5  \varepsilon\,_5  6\varepsilon\,_6  21\varepsilon\,_7  56\varepsilon\,_8  126\varepsilon\,_9  252\varepsilon\,_10

無限個の基底があるので全てを示すことはできませんが、簡単な規則性があります。
二項係数  \binom{n}{k} = {}_n C_{k} = \frac{n!}{(n-k)!k!} を使って  \varepsilon\,_m,  \varepsilon\,_n の積を

 \begin{align}
\varepsilon\,_m \cdot \varepsilon\,_n = \binom{m + n - 1}{m - 1} \varepsilon\,_{m+n}
\end{align}

と表せます。

特に  \varepsilon\,_1 の累乗については

 \begin{align}
\varepsilon\,_1 ^1 &= \varepsilon\,_1 \\\
\varepsilon\,_1 ^2 &= 2\varepsilon\,_2 \\\
\varepsilon\,_1 ^3 &= 6\varepsilon\,_3 \\\
\cdots \\\
\varepsilon\,_1 ^n &= n! \cdot \varepsilon\,_n \\\
\end{align}

という規則があります。

 

そしてこの超二重数を使うと、任意の多項式関数について  f(x + \varepsilon\,_1) を展開整理するだけで任意の階数の微分が求まるというわけですね。簡単便利。

 

この超二重数は "二重数" なのか?

最初に二重数を導入したときのことを思い出しましょう。「2乗すると0になる数  \varepsilon」を認めるところから二重数を考え始めたのでした。

ところで超二重数の積の法則を見てください。

 \begin{align}
\varepsilon\,_m \cdot \varepsilon\,_n = \binom{m + n - 1}{m - 1} \varepsilon\,_{m+n}
\end{align}

ここから

 \begin{align}
\varepsilon\,_n^2 = \binom{2n-1}{n-1} \varepsilon\,_{2n}
\end{align}

となります。

あれ、どの  \varepsilon\,_n も「2乗すると0になる数」ではない...。

いったい2乗すると0になる性質はどこに消えてしまったのでしょうか?不思議ですね。

 

そもそも1階の二重数は2階の二重数のサブセットではない

もう一つサラッと流したけど違和感のある理論展開がありました。
2階の二重数とは基底  \varepsilon\,_1,  \varepsilon\,_2 を用いて  a + b\varepsilon\,_1 + c\varepsilon\,_2 と書ける数と定義しました。このとき1階の二重数は2階の二重数の特別な場合 ( c = 0 の場合) と明言しませんでした。

それもそのはず1階の二重数における  \varepsilon と2階の二重数における  \varepsilon\,_1 は演算規則が異なるからです。 1階の二重数において  \varepsilon ^2 = 0 です。一方で  \varepsilon\,_1 ^2 = 2\varepsilon\,_2 \ne 0 です。

n階の二重数や超二重数は、二重数の自然な拡張なのでしょうか?

 

超二重数にプランク距離を定めるとn階の二重数が (そして実数が) 出る

ここから先の話はポエムでありオカルトです。超二重数からn階の二重数を導出してみます。

そもそも二重数の基底  \varepsilon は実数に比べて非常に小さい数というイメージがあります。例えば実数の  0.1 を2乗すると  0.01 になってより小さくなってしまうように、非常に小さい数を2乗すると 0と区別できないくらい 小さくなってしまうのです。

この点においては2階以上の二重数でも同じイメージで語れます。2階の二重数における  \varepsilon\,_1,  \varepsilon\,_2 はどちらも非常に小さい数で。くわえて  \varepsilon\,_1 に比べて  \varepsilon\,_2 はさらに小さいとイメージできます。 \varepsilon\,_1^2 = 2\varepsilon\,_2 より、仮に  \varepsilon\,_1 = 0.1 くらいとすると  \varepsilon\,_2 = 0.005 くらい?

さて、二重数の基底に小ささのレベルが存在すると思うと。 1階の二重数と2階の二重数を統一的風に解釈できます。
1階の二重数の演算表にも  \varepsilon\,_2 が現れているのですが、小さすぎて  0 と区別できないために  \varepsilon\,_1^2 = 0 と捉えるしかないのです。

(なんかポエムを連ねるのがしんどくなったのでこの記事はここで終わります)

 

まとめ

いかがでしたか?みなさまも実数を適当に拡張して遊んでみてはいかがでしょうか?
実際、n階の二重数は微分計算ために便利なのでそのうち Rust で実装して遊んでみようと思います。

 

 

私からは以上です。

 

おまけ

Rust のデータ型としてn階の二重数を実装している例はすでに在って。たとえばこれ↓↓↓です。

zenn.dev

ラムダ式に含まれる全ての部分式に一意かつ列挙可能なタグを付与する方法

ラムダ式に含まれる全ての部分式に一意かつ列挙可能なタグを付与する方法について考察する。

導入

例として次のラムダ式について考える。

````ABC``DEF`GH

この式を二分木で書くと以下のようになる。

graph TB;
a1((app))---a2((app))
a2((app))---a3((app))
a3((app))---a4((app))
a4((app))---A
a4((app))---B
a3((app))---C
a2((app))---a5((app))
a5((app))---a6((app))
a6((app))---D
a6((app))---E
a5((app))---F
a1((app))---a7((app))
a7((app))---G
a7((app))---H

このラムダ式には全部で15個の部分式が含まれる。

  1. A
  2. `AB
  3. B
  4. ``ABC
  5. C
  6. ```ABC``DEF
  7. D
  8. `DE
  9. E
  10. ``DEF
  11. F
  12. ````ABC``DEF`GH
  13. G
  14. `GH
  15. H

ラムダ式を簡約することを考えるとき、式の中のいずれかのβ基に着目することになる。
β基とはβ簡約可能な部分式のことなので、簡約の過程ではたえず部分式に着目していることになる。 これらの部分式 (元の式も含まれる) を一意に指し示すタグ付けのルールがあると便利だ。

先ほど列挙した部分式は下記のようにタグ付けされる。

部分式 タグ
0 A 0
1 `AB 1
2 B 1,0
3 ``ABC 2
4 C 2,0
5 ```ABC``DEF 3
6 D 3,0
7 `DE 3,1
8 E 3,1,0
9 ``DEF 3,2
10 F 3,2,0
11 ````ABC``DEF`GH 4
12 G 4,0
13 `GH 4,1
14 H 4,1,0

はじめに部分式を列挙したときの並び順は、実はタグを辞書順に並べたものだった。

 

用語の定義

ラムダ式

この記事では一般的な型無しラムダ計算における 変数関数適用 のみからなる式を「ラムダ式」と呼ぶ。
この記事ではラムダ抽象を含む式については取り扱わない。

  • 変数はラムダ式である
    • A, B, C, ... などの記号で変数を表す
  • ラムダ式をラムダ式に適用したものもまたラムダ式である
    • バッククォート ` で適用を表す
    • AB に適用したラムダ式を `AB と書く

同じことを バッカス・ナウア記法 で書くと、

<expression> := <variable> | "`" <expression> <expression>
<variable> := "A" | "B" | "C" | ...

となる。

部分式

とある式 expr が別の式 expr0, expr1 を用いて ` expr0 expr1 と書けるとき、expr0 と expr1 を「expr の部分式」と呼ぶ。

さらに別の式 expr2 が expr0 ないしは expr1 の部分式であるとき、expr2 もまた expr の部分式とみなす。
また便宜上 expr 自身も expr の部分式であるとみなす。

``ABC に対して `AC は部分式ではないことに注意。

ラムダ式の列形式

最初に紹介した、

````ABC``DEF`GH

のような形式を「ラムダ式の列形式」と呼ぶ。

列形式はラムダ式を素朴に文字列で書いた形式とみなすことができる。
が、ここでは少し拡張して列形式はラムダ式を トークン の列で書いた形式とみなす。

「トークン」とは列形式の中の最小単位で。上記の例でいうと A, B, ` などがトークンにあたる。
例えば A0 のような複数文字からなる変数を扱う場合、これを「長さ2の文字列」とみなすのではなく、「1つのトークン」とみなす。

また、さきほどこの記事ではラムダ抽象を含む式については取り扱わないと書いたが、ラムダ抽象全体を一つのトークンとみなせば、ラムダ抽象を含む式もこの記事の枠組みで捉えることができる。

ラムダ式の木形式

ラムダ式を二分木で書いた形式を「ラムダ式の木形式」と呼ぶ。

例として `AB を木形式で書くと、

graph TB;
a1((app))---A
a1((app))---B

のようになる。

末端 (葉, Leaf) が変数に対応し、節 (ノード, Node) が関数適用に対応している。
このとき適用する変数を左側に、適用される変数を右側に書くことにする。

列形式と木形式で表現力に差はないが、木形式のほうが部分式の範囲がビジュアルで分かりやすいという利点がある。
木形式において、部分式はそのまま部分木として表現される。

最左項

とあるラムダ式 (またはその部分式) を木形式で書いたとき、最も左に位置する項を「最左項」と呼ぶ。

graph TB;
a1((app))---a2((app))
a2((app))---A
a2((app))---B
a1((app))---C

上記の例では A が最左項にあたる。

木形式おいて最左項を見つけるのは簡単で。ルートから左の枝を辿っていき最後に行き着いた項が最左項になる。

右部分式 (右部分木)

とあるラムダ式 (またはその部分式) を木形式で書いたとき、最左項ではない部分式 (部分木) を「右部分式 (右部分木)」と呼ぶ。

graph TB;
a1((app))---a2((app))
a2((app))---A
a2((app))---B
a1((app))---C

上記の例では B, C はどちらも右部分式である。

右部分式は単一の変数からなる式とは限らない。

graph TB;
a1((app))---a2((app))
a2((app))---A
a2((app))---a3((app))
a3((app))---B0
a3((app))---B1
a1((app))---C

この例では右部分式は `B0 B1C となる。

さらに部分式 `B0 B1 に着目しているときには、 B0 が最左項で B1 が右部分式ということになる。

変数のタグ付け

部分式にタグ付けすることを考える前に、ラムダ式の中の変数にタグ付けするルールを考える。

右部分木に番号付けする

右部分木に番号付けするルールを与える。
右部分木に左から 1, 2, ... と連番で付番する。

例えば ``ABC という式に対しては、

graph TB;
a1((app))---a2((app))
a2((app))---A
a2((app))---B[B:index=1]
a1((app))---C[C:index=2]

のように付番される。

右部分木が複数の変数からなる式の場合、式全体に付番されることに注意しよう。

graph TB;
a1((app))---a2((app))
a2((app))---A
a2((app))---a3((app:index=1))
a3((app:index=1))---B0
a3((app:index=1))---B1
a1((app))---C[C:index=2]

この番号付けは再帰的に適用できる。
さきほどの例で `B0 B1 は、 B0 が最左項, B1 が1番目の右部分木となっているので、

graph TB;
a1((app))---a2((app))
a2((app))---A
a2((app))---a3((app:index=1))
a3((app:index=1))---B0
a3((app:index=1))---B1[B1:index=1]
a1((app))---C[C:index=2]

と付番できる。

最左項に番号付けする

右部分木だけでなく最左項にも付番したい。最左項には 0 で付番する。

graph TB;
a1((app))---a2((app))
a2((app))---A[A:index=0]
a2((app))---a3((app:index=1))
a3((app:index=1))---B0[B0:index=0]
a3((app:index=1))---B1[B1:index=1]
a1((app))---C[C:index=2]

一見してこれで全ての変数に付番できたように見えるが、実はまだ付番が完全でない変数がある。

C:index=2 に着目してみよう。index=2 と付番されているため C が2番目の右部分木であることが分かる。
ここで C は単項の部分木だが、部分木である以上 最左項と右部分木に分解できるはずだ。C の最左項は C で、右部分木を持たない。C は最左項でもあるので 0 で付番されるべきだ。

同様に B1 も単項の右部分木であると同時にそれ自体が部分木の最左項でもあるので 0 で付番する。

するとこのようになる。

graph TB;
a1((app))---a2((app))
a2((app))---A[A:index=0]
a2((app))---a3((app:index=1))
a3((app:index=1))---B0[B0:index=0]
a3((app:index=1))---B1[B1:index=1:index=0]
a1((app))---C[C:index=2:index=0]

ルートから変数に至る経路によって変数にタグ付けする

さて全ての最左項と右部分木に付番したので、ようやく各変数にタグ付けできる。
変数へのタグ付けの基本的なアイデアは、ルートから変数に至る経路の番号を全て並べてタグとすることだ。

graph TB;
a1((app))---a2((app))
a2((app))---A[A:index=0]
a2((app))---a3((app:index=1))
a3((app:index=1))---B0[B0:index=0]
a3((app:index=1))---B1[B1:index=1:index=0]
a1((app))---C[C:index=2:index=0]

上記の例で B0 に至るには、まずルートから1番目の右部分木 app:index=1 へと進み、続いて最左項 B0:index=0 へと進めばよい。B0 に至る経路の番号を順に並べて、B01,0 でタグ付けする。

各変数とタグの関係を表にまとめる。

変数 タグ
`
`
A 0
`
B0 1,0
B1 1,1,0
C 2,0

タグが「ルートから変数に至る経路」を表現していることを知っていれば、逆にタグから変数への経路を辿ることも容易だ。

関数適用のタグ付け

もう一歩踏み込んで変数だけでなく関数適用にもタグ付けすると便利だ。 木形式において関数適用は節 (ノード, Node) に対応している。右部分木に付番したときと同様に、関数適用にも左から 1, 2, ... と連番で付番する。

graph TB;
a1((app))---a2((app:index=1))
a2((app:index=1))---A
a2((app:index=1))---B
a1((app:index=2))---C

右部分木に現れる関数適用にも同様に付番していく。
さきほど変数にタグ付けする際に右部分木に付番したことと、関数適用に付番することは別の概念として区別する。

graph TB;
a1((app:index=2))---a2((app:index=1))
a2((app:index=1))---A
a2((app:index=1))---a3((app:index=1))
a3((app:index=1))---B0
a3((app:index=1))---B1
a1((app:index=2))---C

関数適用にタグ付けするときの考え方は変数に対するタグ付けの考え方と同様だ。その関数適用に至るまでの経路の番号を並べてタグにする

関数適用 タグ
` 2
` 1
A
` 1,1
B0
B1
C

変数と関数適用のタグ付けまとめ

各変数に対するタグ付けと各関数適用に対するタグ付けをあわせて表にまとめると以下のようになる

変数・関数適用 タグ
` 2
` 1
A 0
` 1,1
B0 1,0
B1 1,1,0
C 2,0

変数に対するタグは末尾が 0 になっているのが見て取れる。
それ以外には変数に対するタグと関数に対するタグは形がとても似ている。

タグの性質

ここまででラムダ式のなかの全ての変数と全ての関数適用にタグ付けするルールを定めた。
先ほどよりも複雑な式を例に付番とタグ付けの様子を見てみよう。

````ABC``DEF`GH

最初にも挙げたラムダ式を例とする。

この式の木形式は以下のようになる。

graph TB;
a1((app))---a2((app))
a2((app))---a3((app))
a3((app))---a4((app))
a4((app))---A
a4((app))---B
a3((app))---C
a2((app))---a5((app))
a5((app))---a6((app))
a6((app))---D
a6((app))---E
a5((app))---F
a1((app))---a7((app))
a7((app))---G
a7((app))---H

各変数・各関数適用にタグ付けしたものを列挙すると下記のようになる。

変数・関数適用 タグ
` 4
` 3
` 2
` 1
A 0
B 1,0
C 2,0
` 3,2
` 3,1
D 3,0
E 3,1,0
F 3,2,0
` 4,1
G 4,0
H 4,1,0

さてこのタグ付けにはいくつかの有用な性質がある。

一意性

ラムダ式の変数・関数適用にタグ付けしたとき各タグは一意になる。この性質のために、このタグによって特定の変数ないしは関数適用を指し示すことができる。

タグが一意になることの証明は省略するが。直感的には木形式で表現したときの各経路が一意であることから自然に理解できるだろう。

トークンに対する網羅性

これまで "変数・関数適用に対して" タグ付けするルールを定めてきたが。実は列形式で表現したときの "全てのトークンに対して" もタグ付けできている。

列形式の各トークンは変数かバッククォート ` のいずれかであり、バッククォートが関数適用に対応しているため、列形式の各トークンと木形式の変数・関数適用が1対1で対応する。木形式の変数・関数適用に対してタグ付けすることは、同時に列形式の各トークンにタグ付けすることにもなっていた。

部分式 (部分木) に対する網羅性

実は全ての部分式 (部分木) に対してもタグ付けできている。
部分式は単項の変数か関数適用からなっていて、これまでに全ての変数と全ての関数適用にタグ付けしてきたためだ。

先ほど示した変数・関数適用とタグの対応表に、部分式の列を追記してみよう。

変数・関数適用 関数適用に対応する部分式 タグ
0 ` ````ABC``DEF`GH 4
1 ` ```ABC``DEF 3
2 ` ``ABC 2
3 ` `AB 1
4 A A 0
5 B B 1,0
6 C C 2,0
7 ` ``DEF 3,2
8 ` `DE 3,1
9 D D 3,0
10 E E 3,1,0
11 F F 3,2,0
12 ` `GH 4,1
13 G G 4,0
14 H H 4,1,0

列形式に対して指定したタグが示す部分木の範囲を容易に判別可能

さきほどまでで「トークン」「部分式」「タグ」が1対1対1で対応していることを述べた。
与えられたラムダ式に含まれる全ての部分式を列挙するには、列形式 (トークン列) のどこからどこまでが部分式を表現しているか判別する必要がある。全てのタグの列を保持していれば、部分式の範囲を特定することは容易だ。

例としてタグ 3,2 に対応する部分式の範囲について考える。
列挙したタグの一覧から 3,2 で始まるものを探すと。7行目の 3,2 と11行目の 3,2,0 が該当する。そのためタグ 3,2 に対応する部分式の範囲はトークン列の7文字目から11文字目であると分かる。
(ここではトークンを0文字目から数えていることに注意)

````ABC``DEF`GH
       ^^^^^
       タグ 3,2 に対応する部分式の範囲

これによってタグ 3,2 が部分式 ``DEF に対応していることが分かった。

このようにしてタグを指定することで、そのタグに対応する部分木が列形式 (トークン列) の中でどの範囲に対応するのかを知ることができる。

まとめ

この記事で以下のトピックを取り上げてきた

  • ラムダ式の列形式と木形式
  • 木形式の経路を辿ることによる変数・関数適用へのタグ付け
  • タグが一意であり、これによって全ての部分式が網羅的に列挙できること
  • 列形式の中のトークン - タグ - 木形式の中の部分木 が1対1対1で対応していること
  • タグによって部分木を一意に指し示すことができ、列形式のなかの対応する範囲も分かる

列形式は紙面上でコンパクトである点において優れている一方、部分式の範囲が分かりづらいという欠点もある。列形式のなかの各トークンにタグ付けすることによって、構文解析して木形式に変換することなく即座に部分式の範囲を特定できる。
またタグによって部分式を網羅的に列挙可能なことも、ラムダ式の簡約過程を考える際に有用であると考える。

 

 

私からは以上です。

おまけ

この記事におけるタグ付けのルールをプログラムに落とし込んだ参考実装を用意しました。

github.com

TypeScript で実装されていて実際に動作します。

TypeScript をコンパイルすることなく Deno でそのまま動かすのが簡単です。
(JavaScript にコンパイルしたのちに Node.js や Web ブラウザで動かすこともできると思います)

実行イメージ

このあたりが主なロジックの実装です。