Rustの並列処理を学ぼうぜ☆(^~^)?<その6>

rust 並列処理 ラムダ式 SKIコンビネーター 公開下書き

前回の記事

Combinators

ラムダ計算
ベータ簡約
Confluence (abstract rewriting)

KIFUWARABE_80x100x8_01_Futu.gif
「 コンビネーターって何だぜ☆?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 数学で カリー化 と一緒に出てくるやつだぜ☆ 美味そうだろ☆ ラムダも焼けば美味しそうだよな☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 非同期処理がしたいだけなのに、なんで カレーとか ラクダが出てくるの?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 型無しラムダ計算 には チャーチ・ロッサー性 があり、
これは 部分の計算を同時にやっても 部分の計算をどんな順番でやっても、
全部終わってしまえば 結果は 合流(confluence; カンプレンス) する、という性質だぜ☆
これが非同期処理に効く☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 フーン」

Confluence - 合流

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 Confluence を簡単に おさらい してみようぜ☆」

Step1   Step2   Step3    Step4
-----   -----   ------   ------
(1+4) × (2+8) × (4+16) × (8+32)

KIFUWARABE_80x100x8_01_Futu.gif
「 おもんない計算だ……☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 同時にやるって どういうことだぜ☆? 並列にやるってことなんだが、並列にやってみろだぜ☆」

                Step1        Step2     Step3
core1: +---+--- (1+ 4) ---+--- × ---+--- × ---+
           |              |         |
core2:     +--- (2+ 8) ---+         |
           |                        |
core3:     +--- (4+16) ---+--- × ---+
           |              |
core4:     +--- (8+32) ---+

KIFUWARABE_80x100x8_01_Futu.gif
「 こんな感じだろう☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 なんだ この図は……☆? 足し算をどのコアに振り分けても、足し算の順序を入れ替えても、いけるよな☆
この性質は 並列化にとって グッド……☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 Step数 1 しか減ってないんだけど!」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 細かく分けても オーバーヘッド が増えるだけなんで、 ある程度 粒(つぶ) を大きくして どさっと任せろだぜ☆」

Step1   Step2   Step3    Step4    Step5     Step6      Step7      Step8
-----   -----   ------   ------   -------   --------   --------   ---------
(1+4) × (2+8) × (4+16) × (8+32) × (16+64) × (32+128) × (64+256) × (128+512)

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑これぐらい 数が多くなってくれば 分担のやりがいも出てくるぜ☆」

                Step1   Step3 Step2           Step4     Step5
core1: +---+--- (1+ 4)    ×   ( 16+ 64) ---+--- × ---+--- × ---+
           |                               |         |
core2:     +--- (2+ 8)    ×   ( 32+128) ---+         |
           |                                         |
core3:     +--- (4+16)    ×   ( 64+256) ---+--- × ---+
           |                               |
core4:     +--- (8+32)    ×   (128+512) ---+

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 8分の5 ステップなら まずまず なのかしら?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 4コアあるんなら 4分の1 に漸近していって欲しいよな☆
12コア 使って 作業量が2分の1に減りました、とか言われたら わたしは ジャパセントリック!(Japacentric) とか
フォールスエコノミー!(false economy) って叫ぶからな☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 それって 作業量が6倍に増えた、の間違いじゃないのか☆ 物は言いよう だよな☆
空いている時間はあるから 2で割っても良いかもしれないが、会社では 空き時間も拘束時間だろ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 せっかく 4コア に分ける努力をしたのに……☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 日本には 着手マン が多いわりに 検証マン を付けてないから そうなる☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 基本的に☆、」

(128+512)

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑こんな風に かたまりになってくれてるやつは 他から独立しているので 並列化の対象になる☆
逆に、並列化しにくいのは……☆」

(128+x)

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑x みたいな変数があるときで、この変数が決まる前、決まった後という 順番 ができてしまう☆
ラムダ計算 は だから 変数 の取り扱いについて ルールが うるさい☆
カリー化 は その変数の取り扱いのテクニックだぜ☆
まあ細かいことは 今はいいだろう☆」

x = y+1

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 しかも ↑x を計算するには 先に y を計算しとかないといけない、とか出てくるんで、これは並列化には 美味くない☆
変数の答えが 次の変数になっている、という レイヤー階層みたいになっているのを
極力 減らして フラットにするテクニック などが出てくる☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 じゃあ 変数をいっぱい使った プログラミング って 並列化 から見れば うんこ なの?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 人類は そこは気にしなくていい☆
ボトルネックは人類なんで、 人類に読みやすいプログラムを書けだぜ☆
プログラミングの基礎もできてないのに 並列処理に手を付けて 成果が伸びると思うなよ☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 Rust を学ぶより、数学を学んだ方が 効果が出るよな……☆」

Function

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ラムダを説明する前に、 数学の function の おさらいを しようぜ☆」

20190929comp48a1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 数学の function というと ↓こういうやつだった☆」

20191001comp3a1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 プログラム言語の呼び方を使うと、fという関数名、xという引数、2xという返り値というか、式があるよな☆」

20191004comp11a1.png

KIFUWARABE_80x100x8_01_Futu.gif
「 例えば x に 3 を入れてみると 6☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 じゃあ次だぜ☆」

20190929comp48a2.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 引数を1個 追加してみよう☆」

20191004comp12a1.png

KIFUWARABE_80x100x8_01_Futu.gif
「 例えば x に 4、 b に 3 を入れてみると 11☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 こうやって説明されてみると 足りないものは感じないが、 Function にはできないこと があるんだぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 へぇ」

First order function

20191006comp21a2.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 例えば、返り値として 式そのもの が出てくるということは できない☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 そうなのかなあ☆?」

20191006comp21a1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 また、引数として 式そのもの を入れるということは できない☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 そうなのかなあ☆?」

20191004comp12a5.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ナンバー(Number; 数)を出すことはできる☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 フーム☆」

20191004comp12a6.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ナンバー(Number; 数)を入れることはできる☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 フーム☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 Function と Number って何が違うの?」

20191004comp12a7.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 計算機科学の用語で揃えると、
Function というのは、 入り口と 出口があって 何か中で変換している工場のような箱のようなものがあるとき、
その  のことだぜ☆
関数 のことを Returns a value のことだと言っている人もいるが 数学というのは いつ誰に教わったか で用語が異なる☆
時間をかけて定着していくものだから 諦めて 脳内変換しろだぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 Function には 数が入って、数が出ていくのかだぜ☆?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 そんな決まりは 一切ない☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 ついさっきの説明と 言っていることが違う……☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 数学というのは あとから出てきた考え方で もともとの意味を上書き修正される ことがある☆
まず 数を説明する☆」

Number

20191001comp2a1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 Number は色々あるが、そのうちの例として 山の木の数 とか、 バケツに入っている水の量 などがある☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 で、要点としては 山の木の数とか 数えてられないし、 水はそもそも 1滴、2滴 と数えれていられない☆」

20191001comp2a1b1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 そこで 昔の人々は 木に縄を縛り付けたり、 バケツの水を小さな枡に 移し替えたりした☆」

20191001comp2a1b2.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 そのあと、 木に縛った縄だけ持ち帰ったり、 水を捨てて 枡だけ持ち帰って みんなで数えれば、
山の木の数とか、バケツの水の量とか 数えられるな☆ これが 数(すう; Number) だぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 どれが 数 だぜ☆?」

20191001comp2a1b3.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 1つ前より 1が増えている……、それが何回起こっていたのかを表したのが 数 だぜ☆
数はいろいろあるが、これは特に Nature(ネイチャー; 自然数) と呼ばれる数の説明だぜ☆」

Higher order function

Higher-order function
高階関数

20191006comp21a3.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 数の代わりに 関数が返ってきたり、関数を入れることができたりするのが、
Higher order function(ハイアー・オーダー・ファンクション; 高階関数) だぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 関数から関数が出てきてどうすんの? 関数の中に関数を入れてどうすんの?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ここで注目していただきたいのは……☆」

20191004comp12a9.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 関数を利用しようとしている人から見れば
↑ ファースト・オーダー・ファンクション(First order function; 一階関数) に見えることだぜ☆」

20191006comp21a4.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 だから Higher order function は First order function の中に入っている☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 その図解から決まってしまうことがあるわよ」

20191006comp21a5.png

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 最もXに近い側 の高階関数は ナンバーを受け取って、
最もYに近い側 の高階関数は ナンバーを返すのよ」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 図を見て0秒で真理に到達するやつがいるのか……☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 最もXに近い側とか、最もYに近い側って どこだぜ☆?」

一階関数を受け取ってナンバーを返す高階関数(ナンバーを受け取る関数)
{
    return ナンバーを受け取る関数 # 最もYから遠い側
}

一階関数(ナンバー)
{
    return ナンバー
}

できた関数 = 一階関数を受け取ってナンバーを返す高階関数(一階関数)
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 最もYに近い側

できた関数(3)

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑こういうやつとか……☆」

一階関数を受け取ってナンバーを返す高階関数(ナンバーを受け取る関数)
{
    内側の高階関数(一番外側のナンバーにあたる引数)
    {
        return ナンバーを受け取る関数(一番外側のナンバーにあたる引数) # 最もYから遠い側
    }

    return 内側の高階関数
}

一階関数(ナンバー)
{
    return ナンバー
}

できた関数 = 一階関数を受け取ってナンバーを返す高階関数(一階関数)
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 最もYに近い側

できた関数(3)

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑こういうやつだぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 何がなんだか 分からんな……☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 しかたのないやつだな……☆(/_\)」

20191006comp21a6.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 関数をそのまま入れると……☆」

20191004comp12a13.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 計算をするわけではなく、高階関数を作ってるんだぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 じゃあ ナンバー を入れるまで計算は始まらないのかだぜ☆?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 良い視点だぜ☆」

20191006comp21a7.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ナンバーを入れるまでの間に どんどん 関数をそのまま入れようぜ☆」

20191006comp21a8.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 入り口に さらに加わったな☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 入り口の方に加わるのか☆?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 入り口の方に加わる☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 一番内側にいるやつが 一番外に ケツ開けてんの? 空間がおかしくない?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 まず最初に 一番内側まで駆け下りて、そのあと じっくり外側に上がってくるんだぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 分けわからん形してるな……☆」

20191004comp12a16.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 じゃあ ケツの穴に ナンバーを突き刺していこうぜ☆?」

20191004comp12a17.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 まず一番内側の 一階関数 のケツの穴に刺さる☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 それが直観に反するのよね」

20191004comp12a18.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 次に、残っているなかで 一番内側の 一階関数 のケツの穴に刺さる☆」

20191004comp12a19.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 次もずっと、残っているなかで 一番内側の 一階関数 のケツの穴に刺さる☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 でも なんで そんなことをする必要があるわけ?」

20191004comp12a20.png

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 シーケンスにすると何がダメなの?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 それは プロシージャ言語から 関数型言語にやってきた人が 最初に抱く問いだぜ☆
ぶっちゃけて言えば その図は シーケンスじゃないんだぜ☆」

20191004comp12a21.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ループなんだぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 むぅ」

20191004comp12a22.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 シーケンスとは 繰り返していない1本道のことを言う☆」

20191004comp12a23.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 で、これから先のプログラミング……、というか アラフォーにもなると 先もないプログラミングだが、
プログラムは 繰り返していない一本道だが 音楽の ※繰り返し みたいに その各部分はループしてる構造とか
キリッと 全体をループで括れないケースが しょっちゅう出てくる☆」

20191006comp21a9.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 高階関数というのは その繰り返し制御の構造を まるっと担当し、
for文のような単なるループにとどまらない 入り組んだループの表現を行う☆
高階関数に渡される関数というのは、その各部にあたる☆
パターンとか、タイルを 高階関数に渡す感じになる☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 じゃあ 関数を関数に渡すのは 豊かな表現のループ の方を部品にしたというのがメリットなの?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 そうだぜ☆ 豊かな表現のループ と 豊かな表現のループ を部品として扱い、組み合わされたときに描き出す図形もまた
豊かな表現のループなのは どこかで見てこいだぜ☆」

Currying - カリー化

食べられないほうのカリー化入門
関数適用、関数から評価するか?引数から評価するか?

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 カリー化 をプログラミングしても うま味はなく、
カリー化が プログラム言語の実装で 使えるようになってたら うま味がある、ということだな☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 さらに カリー化 をすると 関数呼び出し が増えるので、実行速度は遅くなる☆
f(x)(y) より、 f(x,y) の方が実行速度が速い☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 なんでカリー化したいんだぜ☆?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 カリー化できるなら コンパイラーがCPUに対して最適化しやすく、カリー化できないなら そうではないということだろう☆
人類から見れば、カリー化は 最適化の検証 に使えるだけ☆」

add( x, y )
{
    x + y
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 疑似コードで ↑こんな2つの引数を取る関数があるとき☆、」

add( x )
{
    add( y )
    {
        x + y
    }
}

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 引数を1個取る関数を返す関数にすれば☆、」

# add(2) は、2+y のアブストラクションを持った f を返す。
# f(3) は 2+3 なので答えは 5。
add(2)(3)

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 と書けるな☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 それが 何やってるか 分けわかんないのよね。
何でこんなこと やらされているのかも分かんない」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 カリー化 で1記事書いた方がいいのかもしれないな☆」

Lambda

Lambda calculus
ラムダ計算入門
ラムダ計算入門
SKIコンビネータ計算
SKIコンビネータ覚書
SKI (combinatory logic) interpreter
SKIコンビネーター入門以前(ついでに、PythonでSKIコンビネーター学習用ライブラリを書いた)
SKI コンビネータ?
コンピュータ・サイエンス入門ラムダ計算第1回目資料

20191006comp21a10.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 関数に 式本体を入れたり、 式本体 を返したりできる関数を 高階関数 と呼ぶのは 前に説明した☆
ラムダ計算では 高階関数 を使う☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 どんなときに 使いたくなるのかしら?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 2×4 を 2×(3+1) と書き直したり、
2×(3+1) を (4×(6+2))÷4 と書き直したりのような、
簡単な形をキープしたまま より複雑な書き方に挑戦しようとするときだな☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 高階関数を減らしていく方が やりたいが……☆ なんで しっちゃかめっちゃかな方に行こうとするんだぜ☆?」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 なんで 複雑な書き方に挑戦しようとするの?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 プログラミングに落とし込みたい対称の現実が 複雑だからだぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 そんなもんかなあ?」

Variable

20191006comp21a11b1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ラムダ計算では、 高階関数のケツの穴のことを Variable(バリアブル; 変数) と呼ぶ☆
計算機科学では Parameter(パラメーター; 仮引数)と呼んでるやつだぜ☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ラムダ計算がいうところの Variable は、あとで出てくる Lambda term(ラムダ ターム; ラムダ項) だぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 フーン」

Abstraction

20191006comp21a11b2.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 高階関数の中身には、せっかく入れた Variable を使った 何か式でもあるだろう☆
ラムダ計算では Abstraction (アブストラクション; ラムダ抽象)と呼ぶ☆
計算機科学では何が近いかというと、 Eval関数に入れる文字列だな☆ Expression(エクスプレッション; 式)と呼んでるやつだぜ☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ラムダ計算がいうところの Abstraction は、あとで出てくる Lambda term(ラムダ ターム; ラムダ項) だぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 フーン」

Application

20191006comp21a11b3.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 高階関数に ナンバー、一階関数、高階関数のいずれかを入れるとき、
または、 一階関数に ナンバーを入れるときのことを、
ラムダ計算では Application (アプリケーション; ラムダ適用)と呼ぶ☆
計算機科学では何が近いかというと、 匿名関数を高階関数の引数に渡すとき だな☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ラムダ計算がいうところの Application のうち、
高階関数の引数に渡す匿名関数と、高階関数の中の式 の2つは、あとで出てくる Lambda term(ラムダ ターム; ラムダ項) だぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 フーン」

ラムダ式の書き方

まず匿名関数を書けだぜ☆(^~^)

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ラムダ式の書き方は 匿名関数(Anonymous function; アノニマス ファンクション) から覚えた方が早い☆
Function と比較しながら Anonymous function を見ていこうぜ☆?」

20191004comp14a1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 数学の序盤では Function は ↑こう書くが……☆、
というか そもそも 数学の序盤に 匿名関数はない☆ いきなり ラムダ計算に飛ぶ☆」

20191004comp14a2.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 匿名関数は ラムダ計算 で初めて出てくる☆
イコールの左右に分かれていた Parameter と Expression を、 ドットの左右に くっつける形にすることで、
イコールの片方に まとめることが できるようにしているぜ☆

丸かっこは付けなくていいが、 ここに丸かっこが付く書き方はよく使うんで、
最初の覚えようとしている最中のうちは 付けておいた方が 見やすいだろう☆」

20191004comp14a4.png

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 こいつは何もんなの?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ギリシア文字の11番目、ラムダだぜ☆ ラムダ計算やってます、というのが分かるように そこにいる☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 関数の名前は 消えちゃったの?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 有ると邪魔だから消した☆」

20191004comp14a3.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 Java script 言語や、 Rust 言語でも 匿名関数は 書ける☆
匿名関数(anonymous function; アノニマス ファンクション)で検索すれば出てくる☆」

20191002comp9a1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 アーギュメント(Argument; 実引数)は丸かっこの右に置く☆ 左結合だぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 丸かっこの外に 実引数を置くのねぇ」

20191004comp14a5.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 仮引数(Parameter; パラメーター)を追加したいときは、ドットで区切って 外側に増やしていけだぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 変なの」

20191004comp14a6.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 実引数(Argument; アーギュメン)を示したいときは、丸かっこの右隣に スペース区切りで添えろだぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 関数のカンマ区切りの引数リストが スペース区切りに変わって 丸かっこの右外に飛び出ただけかだぜ☆?」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 書き方が変わっただけじゃないの? ふつーの Function と比べて 使い勝手は何が変わったの?」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 入れ子の構造を 筆算できるところだな☆」

I Combinator - Identity combinator

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ラムダ計算に入る前に、次に コンビネーターの説明をしていくぜ☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 一番簡単なコンビネーターは I Combinator(アイ・コンビネーター)だぜ☆」

20191006comp21a12.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 絵にすると ↑こんな感じだぜ☆
第一引数が そのまま 返り値 として出てくる Function が Iコンビネーターだぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 ふーむ。
いても いなくても いいやつな気がするけどなあ。
ひょっとして プレース・ホルダー(場所取り) に使うの?」

20191006comp21a13.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 じゃあ、 x に 3 を入れたら どうなるだろうか☆?」

= (λx.x) 3
  (λ .x) 3
    ^

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 仮引数の x を消して……」

= (λx.x) 3
  (λ .x) 3
  (λ .3) _
      ^  ^

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 アブストラクションのxを 3に置き換えて……」

= (λx.x) 3
  (λ .x) 3
  (λ .3) _
  __ _3_ 
  ^^ ^ ^

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 実引数の無くなったラムダ式の囲いを消して 答えは 3 よ」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 そうだぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 実引数が x で、返り値が x なんだから、 3 を入れたら 答えは 3 よね。
なんで こんなこと やらされてるのか 分からないけど」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 よく使うから だろうけどな☆」

Constant

20191006comp21a14.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 実引数に何を入れても、決まった値が出てくる Function は、Constant (コンスタント; 定数)と言ってしまっていい☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 アップデートできなくなった人類みたいだな☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 入力を捨てちゃうなんて 不思議ねぇ」

K Combinator - Constant combinator

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 定数のことらしいんで Constant なんだが、ドイツ語由来なんで Konstant なんで
K コンビネーターと呼ぶらしい☆ 見ていこう☆」

20191006comp21a15.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 絵にすると、1つ目の実引数 red を取る 青い親Function があって、
これは 子の水色Function に red を詰め込む☆ そしてその 水色Functionを返す。
2つ目の実引数 green は 水色Function に渡されるが、何にも使われない☆ 水色Functionの中の red を取り出して返すぜ☆
これは結局、2つ目の引数は無視されて 1つ目の引数だけが返ってくるということだぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 yの配線が切れてて xだけ通ってる電源タップにしか見えない☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 定数のコンビネーターって xを指して 定数って言ってるの? こんなこと やらされている 意味が分かんないのよね。
y を引数に入れたの 無駄じゃん、って……」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 このとき、親の青Functionから見ると xは 束縛変数、 yは 自由変数 という☆
子の水色Functionから見ると xは 自由変数、 yは 束縛変数 という☆
プログラム言語の用語で言うと、自由変数はグローバル変数、束縛変数はローカル変数みたいな感じだぜ☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↓数式を ちゃんと見ていこう☆
まぎらわしいことなく、ちゃんと Kコンビネーター を記述できている記法だぜ☆」

20190929comp51a1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑まず 1行目でリクツを示し、 2行目で 丸かっこを省き、 3行目が よく使われる 省略した書き方だぜ☆」

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 あの yの配線が ぶち切れたみたいな 記述に ちゃんとなってるわね」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↓ちゃんと 計算できることも 確かめておこう☆」

20191006comp21a16.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑実引数に 5 と 7 を置いて 適用してみてくれだぜ☆」

= (λxy.x) 5 7
= (λ_y.5) _ 7
    ^  ^  ^

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 xに 5 を置いたら、もう 定数 の形になったわよ」

= (λxy.x) 5 7
= (λ_y.5) _ 7
= (λ _.5)   _
     ^      ^
= __  _5_
  ^^  ^ ^

OKAZAKI_Yumemi_80x80x8_02_Syaberu.gif
「 一応最後までやるけど、 5 よ」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 そうだぜ☆ 引数が2回にわたって渡されたら、1つ目を採用し、2つ目を無視するぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 なんで こんなこと 覚えさせられているのか 分からん☆」

S combinator - Sharing combinator

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 最後に S コンビネーターを解説する☆ これで S、K、I コンビネーター3つを覚えればカンペキだぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 3つでいいのか☆ じゃあ覚えてしまおう☆」

20191005comp19a4b5.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 絵で描くと 多分 ↑こう だぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 やっぱ 覚えられね☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↓ちゃんと 計算できることも 確かめておこう☆」

20190929comp52a1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 Sコンビネーターは、 ↑こういう形をしている☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 くわしく☆」

二分木

20191005comp20a1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑二分木になっているらしいんだぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 分かんね☆」

β-redex (ベータ簡約)

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 アブストラクション(ラムダ抽象)の変数を減らして フラット にしていく作業だぜ☆
チャーチ・ロッサー性 というのは、このベータ簡約を 同時にやったり、お好きな順序でやっていい ということを言っている☆」

書きかけ

beta-redex

α-conversion (アルファ変換)

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ベータ簡約の操作を間違えないように、アブストラクション(ラムダ抽象)を先に掃除するテクニックに アルファ変換 がある☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 このように ごっそり 束縛変数x を入れ替えることを α変換 (アルファー変換)と呼ぶ☆
束縛変数というのは、 λ の記号の横に書いてある 仮引数 と、
アブストラクション の中の両方に出てくる 変数 のことだぜ☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 名前が似ているが、実引数を消していく、 アルファ消去 という操作も別にある☆」

alpha-conversion

η-conversion (イータ変換)

ラムダ計算をちょっと勉強してみたので、忘れないうちに書いておく
イータ変換までやるかな、それと、大きなラムダの基本概念とか

書きかけ

eta-conversion

application

20191006comp26a6b2.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 現代では プログラミング用語に合わせて ↑こんな風に呼んだ方が伝わりやすいと思うんで これも使うが……☆」

20191006comp26a6b1.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 ↑ラムダ計算での歴史的な名称も知っておくと 過去のドキュメントに 当たりやすいぜ☆
M(エム)や N(エヌ)は 変数名ではなく、容れ物の名前と思ってくれだぜ☆ 集合で分かる人は集合で☆」

20191006comp26a4.png

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 で、アプリケーションというのは ↑こういう計算だぜ☆」

KIFUWARABE_80x100x8_01_Futu.gif
「 何だぜ この トンチキ な校正みたいな約物は☆?」

= (λx.x+1)(y*2)3
  (λ_.x+1)(y*2)3
    ^

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 パラメーターを消して……☆」

= (λx.    x+1)(y*2)3
  (λ_.    x+1)(y*2)3
  (λ_.(y*2)+1)_____3
    ^ ^^^^^   ^^^^^

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 第1実引数を 返り値 に埋め込んで……☆」

= (λx.    x+1)(y*2)3
  (λ_.    x+1)(y*2)3
  (λ_.(y*2)+1)_____3
= (λy.(y*2)+1)     3
    ^

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 自由になってる変数 y を束縛☆
丸かっことか 要らなければ外しておけだぜ☆」

KITASHIRAKAWA_Chiyuri_80x100x8_01_Futu.gif
「 これが Application(アプリケーション; 適用)だぜ☆」

次の記事へ

何度でもクリック!→

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位

光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位 の最近の記事