変数の気持ち
配列 $a$ の和を求めるプログラムは
const a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let s = 0;
for (let n = 1; n <= 10; n++) {
s = s + a[n];
}
console.log(s);
55
と変数 $s$ を用いて書くことができる. このとき下から３行目
s = s + a[n];
の等号 $=$ は, 左辺と右辺が等しいと言う意味ではなく,
左辺に右辺を代入すると言う意味なのだと教えられる.
でもやっぱり等号 $=$ は等しいと言う意味で捉えたい.
そこで, 変数 $s$ を次のように数列 $s_{n}$ と考えてみよう.
\begin{align}
\begin{aligned}
a_{n} &= n; \\
s_{0} &= 0; \\
s_{n} &= s_{n-1} + a_{n};
\end{aligned} \tag{1}
\end{align}
この数列$s_{n}$は
\begin{align}\left\{
\begin{aligned}
s_{1} &= s_{1-1} + a_{1}; \\
s_{2} &= s_{2-1} + a_{2}; \\
s_{3} &= s_{3-1} + a_{3}; \\
&\;\;\vdots\\
s_{n} &= s_{n-1} + a_{n};
\end{aligned}
\right.\end{align}
と辺々足すことで, $s_{n} = a_{1} + a_{2} + a_{3} + \cdots + a_{n}$
となり, 数列 $a_{n}$ の和をあらわしていることが分かるだろう.
変数 $s$ は数列 $s_{n}$ なのだと言う考えの下で,
数列 $a_{n}$ の和を求めるプログラムは以下となる.
const a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const s = [];
s[0] = 0;
for (let n = 1; n <= 10; n++) {
s[n] = s[n-1] + a[n];
}
console.log(s);
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
このプログラムでは下から３行目の等号 $=$ の左辺と右辺は等しい.
式(1)とプログラムが素直に対応していることが分かるだろう.
数列 $s_{n}$ の最後の値 $55$ が, 今計算したかった, 数列 $a_{n}$ の和である.
こうして見てみると, 変数 $s$ と数列 $s_{n}$ の関係が分かってくる.
変数 $s$ は代入毎に値を変え最終的な値 $55$ となるが,
数列 $s_{n}$ はその変化の履歴を律儀に保存していると言える.
等号 $=$ の左辺と右辺が等しくないのは気持ち悪いかもしれないが、
逐次的に変化する変数の気持ちも少しは分かるような気がする.
静的単一代入(Static Single-Assignment)
変数 $s$ から数列 $s_{n}$ を用いるプログラムへの書き換えは
SSA (Static Single-Assignment) 形式への変換と呼ばれる.
CPS (Continuation-Passing Style) 変換とも関係あるらしい1.
おまけ
何となく思いついて気が向いたから上記まとめてみたけど,
どこかに同じような話が書いてあるに違いない. たぶん.
(やっぱりそういう話はあるようで, SSAに関して追記.
@kazatsuyu さんにコメントでご指摘いただきました. 感謝. )
変数を数列と考えると関数型プログラミング的な何かに
近づくのではないか, と唐突に思ったのが思考の始まり.
(SSA is Functional Programming というまさにそのもの
という論文があるようで, おそらくこの予感は正しい?)
以下, 変数を数列と考えてみたときの何だかんだを雑多に記載.
数列 $s_{n}$ な感じを増して, 数列 $a_{n}$ の和を求めるプログラムを
const a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const s = [() => 0, ...a.map((_,n) => () => s[n-1]() + a[n]).slice(1)];
console.log(s.map(f => f()));
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
と書いてみると関数型プログラミングぽい気がしたけど,
Haskell のコード↓ありきで書いただけなのであんま意味なさそう.
(とも思ったが, 和を数列 $s_{n}$ と捉えることで, 数列の定義に従って
素直にループを再帰で書けると言う点においては意味ありそう.)
a = [0..10]
s = 0 : zipWith (+) s (tail a)
print s
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
これ↑は例のフィボナッチ数列のやつ↓
fib = 0 : 1 : zipWith (+) fib (tail fib)
print $ take 12 fib
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
からインスパイアされていて, つまり JavaScript でも
フィボナッチ数列のやつ書けるのではと思ったのがこれ↓
const ns = [...Array(10).keys()];
const zipWith = f => xs => ys => ns.map(n => () => f(xs()[n])(ys()[n]));
const p = x => y => x() + y();
const fib = [() => 0, () => 1, ...zipWith(p)(() => fib)(() => fib.slice(1))];
console.log(fib.map(f => f()));
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
無限リスト化は諦めたけれど雰囲気は出てる. 気がする.