Edited at

プログラミングにおける変数について


変数の気持ち

配列 $a$ の和を求めるプログラムは


a_nの和その1.js

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$ を用いて書くことができる. このとき下から3行目

  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}$ の和を求めるプログラムは以下となる.


a_nの和その2.js

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]


このプログラムでは下から3行目の等号 $=$ の左辺と右辺は等しい.

式(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}$ の和を求めるプログラムを


a_nの和その3.js

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_nの和.hs

a = [0..10]

s = 0 : zipWith (+) s (tail a)
print s


実行結果

[0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]


これ↑は例のフィボナッチ数列のやつ↓


フィボナッチ.hs

fib  = 0 : 1 : zipWith (+) fib (tail fib)

print $ take 12 fib


実行結果

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]


からインスパイアされていて, つまり JavaScript でも

フィボナッチ数列のやつ書けるのではと思ったのがこれ↓


フィボナッチ.js

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]


無限リスト化は諦めたけれど雰囲気は出てる. 気がする.