宿題：関数型言語 #

Homework 約30分 答え

ラムダ計算において真偽値は次のように定義される．

true  = λxy. x
false = λxy. y

また条件分岐の関数は次のように定義される．if <c> <x> else <y>の意味である（C言語の構文と同じである）．

if = λcxy. c x y

if false A Bという式に対する簡約の流れを示せ．AとBは任意のラムダ式（関数）だと解釈せよ．これらは展開は不要である．関数適用は左結合である点に注意せよ．

以下の書式をコピーして回答せよ．

if false A B
→ (λcxy. c x y) false A B  ; ifをラムダ式に展開
→ ???

回答フォーム

Answer

様々な簡約順序があるが，展開(1)を後回しにすると楽に記述できる．

名前付き関数をラムダ式へ書き換える操作のこと．\(\alpha\)変換でも\(\beta\)変換でもない単なる定義の書き換えである．

if false A B
→  (λcxy. c x y) false A B  ; ifをラムダ式に展開
→b false A B                ; false A Bを適用（β変換）
→  (λxy. y) A B             ; falseをラムダ式に展開
→b B                        ; A Bを適用（β変換）

以下は先に展開するパターンである．

if false A B
→  (λcxy. c x y) false A B     ; ifをラムダ式に展開
→  (λcxy. c x y) (λxy. y) A B  ; falseをラムダ式に展開
→b (λxy. (λxy. y) x y) A B     ; 1つ目のλcに2つ目λを適用（β変換）
→b (λxy. y) A B                ; 1つ目のλxyにA Bを適用（β変換）
→b B

最終的にBが得られる．条件文の期待通りの振る舞いである．if true falseの全てが関数である点にも着目せよ．これが関数型言語の背後にある論理，ラムダ計算である．

Q&A#

：口頭での解説はスキップ

ラムダ式の計算の順序が難しい#

まず基本操作は2つのだと考えると良い．展開と\(\beta\)変換である．

展開：定義済みの名前あり関数をラムダ式に書き換える（例：if → λcxy. c x y）
\(\beta\)変換（関数適用）：関数に値を与えて計算する（例：(λxy. x) A B → A）

\(\beta\)変換は左結合である点に注意すること（例：A B CはAにBを適用すること）．

それ以外はどのような順序で計算しても良いです．展開も\(\beta\)変換も等価な関係なので適用順序によらず結果は一つに定まります．

できるだけ展開を後回しにすることを推奨します．λcxy. c x yと書くよりifと書いたほうが短いので楽です．

ラムダ式の計算の順序で混乱した#

宿題の場合，展開の順序によっては次のような表現が現れる．

→ ...
→ (λxy. (λxy. y) x y) A B

この際，AとBをどのxとyに関数適用するかで混乱してしまう．

次のように考えると良い

→ ...
→ (λxy. (λxy. y) x y) A B
     ;  ~~~~~~~~
     ;   この部分は独立した関数なので名前付きの関数Fだと見なしてみる
→ (λxy. F x y) A B

関数適用すべきxとyが一つに定まる．その後でFをまた再展開すると良い．展開は左辺と右辺の等価を意味する関係なので，交換則が成り立ちます．

あるいは\(\alpha\)変換するのも良い．

→  ...
→  (λxy. (λxy. y) x y) A B
      ;  ~~~~~~~~
      ;   この部分は独立した関数なのでa変換してもOK（束縛変数の名前を変える）
→a (λxy. (λst. t) x y) A B

自然数の定義あれこれ#

チャーチ数が自然数の定義に似ているように感じました．
0=∅
1={∅}
2={∅,{∅}}

ラムダ計算の自然数のの定義は1回生の「基礎解析学」で紹介していた内容に似ていた．
・1をαとすると
・2はαα、3はααα...

ラムダ式による自然数の定義が集合による自然数の定義に似ているような気がしました．

チャーチ数はつまり，数学において自然数を集合で定義しているやつの，集合を関数に置き換えているような感じだと認識した．

ラムダ計算の自然数の定義がノイマンの自然数の定義に似てると感じた

良い質問 👍👍👍

このような性質をペアノの公理と呼びます．自然数の持つ性質を体系づけた公理系です．チャーチ数もノイマンの自然数もペアノ公理を満たすので，似た表現になります．

関数型言語はどの程度使われているのか？どの分野で使われているか？#

Webからバックエンドまで様々な分野で使われています．参照透過（変数の再代入を許さない）という性質から並列処理にも向いています．競合が発生しにくいためです．また金融等でも使われます．参照透過が満たされるとプログラムの正しさを数学的に証明しやすいためです．

カリー化は自動車工場のシステムに似ていると感じた#

大量の部品で構成される自動車を最小の部品まで分ける
部品工場で最小の部品を作り、それを組み上げる
最小の部品を組み合わせてもう少し大きな部品を作る
上記の繰り返し

良い解釈 👍👍👍

ラムダ式の使い所は？#

使い回さない関数はラムダ式で書くことが多いです．

Pythonでのリストのフィルタ

words = ["apple", "banana", "orange"]
filtered = filter(lambda w: w.startswith("a"), words)
print(list(filtered))  # ['apple']

この場合，filter()に渡すフィルタ関数は使い回さないので，通常の関数定義ではなくラムダ式を使うとベターです．以下は通常の関数を使った場合です．

Pythonでのリストのフィルタ

def my_filter(w):
    return w.startswith("a")

words = ["apple", "banana", "orange"]
filtered = filter(my_filter, words)
print(list(filtered))  # ['apple']

関数名はあった方が分かりやすいのでは？#

基本は名前があった方が良いが「必須ではない」点が重要です．開発者が取れる選択肢が増えます．上記filter()のような再利用しない関数は名前が不要なケースが多いです．

あとはコールバック関数の引数にもよく使われます．Web周りの仕組みはコールバックだらけで無名関数だらけです．

おすすめの関数型言語はあるか？#

単に試すだけなら講義で扱ったSchemeが良いです．大真面目に関数型言語を学ぶならHaskellです．Pythonの中で徹底的に関数型プログラミングを実践するのも良いです．

変数は代入ではなく定義だと考えるとRAマシンのload/storeが不要になる．つまり計算モデルが違うと解釈した#

👍👍👍

ラムダ計算を基にしたコンピュータアーキテクチャを作るとしたらどのようなものになるか？#

おもしろい観点だと思う．まつ本はわからん．

第2引数に部分適応する方法はあるか？#

おそらくありません．

カリー化できないラムダ式は存在するか？#

ありません．強いて言うなら引数が1個以下はカリー化できません．

関数型言語はメモリ操作が少なそうなので実行速度が速い？#

観点は間違っていない．参照透過なのでキャッシュ効率が良く並列化にも適しています．ただ現実的にはコンパイラの性能に強く左右されます．

ラムダ計算で小数はどう表現するのか？#

有理数ならa/bとして表現できます．ただラムダ計算自体は理論的な枠組みであり，実数の表現や解析には適していません．

ポーランド記法なら構文の曖昧さがなくなるのか？#

Yes．結合性と優先度が一意に定まります．

現在アプリを開発して公開している．貢献者を増やすためには今後どうすべきだろう？#

リポジトリ見ました．かなり実践的な取り組み方をしていると思います．

まつ本個人は"Just for fun"の精神で開発するので，あまり良い意見が出せません．OSSの参加やモチベーションに関する研究はたくさんあるので，そちらを見るのが良いかもしれません．

宿題：関数型言語#