Chapter 07

💡 逐次、選択、反復の3要素でチューリング完全

Ken Okabe

2023.11.27に更新

このチャプターの目次

チューリング完全と構造化定理
逐次、選択、反復の3要素は関数型コードの式で表現可能
逐次処理のための式
選択のための式
反復のための式

関数型コードにおける逐次、選択、反復の3要素を紹介する

チューリング完全と構造化定理

関数型プログラミング とは、このように数式というブロックをつなぎ合わせて組みあげるだけでぜんぶやってしまう手法

プログラミング言語で「なんでもできるようになる」ことを チューリング完全 と言う

チューリング完全になるためには逐次、選択、反復の ３要素さえできれば良い という 構造化定理 がある

逐次、選択、反復の3要素は関数型コードの式で表現可能

逐次、選択、反復の3要素は素朴にみて命令型のフローの概念

関数型コードは、数学の式なので、 逐次、選択、反復の3要素も素朴なフローの制御構造ではなく、式で表現される

逐次処理のための式

数学の式は、演算優先順位だけでいくらでも演算の順番がコントロールできる ので、 関数型コード、というより代数構造 には逐次の機能が、プログラミング言語を設計する人間があれこれと考える必要すらなく、あらかじめ備わっている

Haskellのような純粋関数型言語では、逐次処理を、優先順位がある数式の演算で処理する、というスタイルで徹底している

関数型プログラミングとは数学そのもの という原則原則に可能な限り忠実で純粋であろうと追求しているのが、Haskellのような純粋関数型言語で、このように、逐次処理も式の演算、代数構造で表現している

Haskellのコードの二項演算子とIO Monad

今のところ、初見ではHaskellのコードはわかりにくいだろう

ここで、 do を展開したときに現れた

>> や >>= が、この順次処理のための演算で使われている二項演算子

このような順次処理のための式、演算をHaskellでは、 IO Monad と呼んでいるが、後で詳しく紹介する

ただし、逐次処理をIO Monad の式で表現するコードを書く、というのは人間にとってはなかなか直感的ではなく大変なので、Haskellでは最初に示されたとおり do キーワードを使ったSyntaxSugarが使われる

その他多くの純粋ではない関数型言語では、ここは適度に緩めており、式が裏側にある do をプログラマに書かせることはせず、巷の命令型言語と同じように、単にコードの上から下に列挙させることを許可している

純粋関数型言語Haskellと他の純粋ではない関数型言語の最も大きな違いは、逐次処理の表現にIO Monadという演算式を使わなければいけないのか、そうではないかだ

IO Monadは、すべてを演算で行うという原理原則を追求しているHaskellのような純粋関数型言語にとっては、逐次処理を実現するために必須だが、純粋でない関数型言語では、命令型スタイルでコードの上下の順序で式を並べるだけで逐次処理が実現できるのでわざわざ使う必要がない

ここでは純粋関数型言語Haskellではなく、 F#とTypeScriptを関数型言語として利用するので、IO Monadを使った演算式のスタイルで逐次処理のコードを書くことはない

ただし、Monadの基礎ができてからはIO Monadを各関数型言語に実装して挙動をエミュレーションすることは難しくないので、それは後で挑戦してみよう

選択のための式

選択は単に 条件式 をつかう、関数型コードの式はフローではないので分岐ではなく数学でいうところの 「場合分け」の選択 だ

条件式は、式なので、 必ず値を持っている（値を返す） 、 命令形フローの構文のときのように else を省略することはできない

Haskellでは、命令型の条件分岐のように見える if then elseキーワードでも、すべて式になっている

Rustのような関数型スタイルを取り入れたモダンな言語も条件式になっている

Verseも条件式

F#も条件式

F#やHaskellそれからRustなどもifとelseのキーワードをそのまま踏襲しているが、C系のIF-ELSE構文でなく、 C 言語の 三項演算子による演算とまったく同じであり（条件）式 になっている

JavaScriptを含む C言語系のプログラミング言語では三項演算子 が用意されていることが多い、これは 条件式 だ

三項演算子

condition ? exprIfTrue : exprIfFalse

let x = true;
let result =
     x == true
     ? "x is true!"
     : "x is false!";
// "x is true!"

JavaScriptではより複雑な条件分岐の際に、switch-case構文が使われるが、ガチ 関数型言語では強力なパターンマッチ という仕組みがあり、F#では match 式を使う 、JavaScriptでは言語にパターンマッチは含まれていないので、サードパーティのNPMライブラリなどを使うしかない

条件式

if condition then exprIfTrue else exprIfFalse

let x = true
let result =
    if x = true
        then "x is true!"
        else "x is false!"
// "x is true!"

パターンマッチ

let x = 2
let result =
    match x with
    | 1 -> "one"
    | 2 -> "two"
    | _ -> "other"
// "two"

その他のほとんどのJavaScriptを含むC言語系のプログラミング言語では、命令型の if else 構文であり、式にはなっていない、つまり値を持たない

反復のための式

命令型コードと関数型コードを比較

関数型コードの 反復のための式 を紹介する以前に、まず命令型でどういうコードを書いているか確認しておくと、それはもちろん for というフローの制御構文を使ったループ

関数型コードでは上記のような簡潔なコードとなる

命令型コードでは、「計算結果」となる値 sum が最初 0 に設定されていて、さらに i というカウンター変数もあり、この2つの値がループ毎にコロコロ値が変化していく、という実は非常に複雑な処理をやっている

関数型コードでは、そのようなループのようなフローは存在しないし、ただ二項演算をして一発で「計算結果」 sum が求まっている

なぜそんなことが可能なのか？と言うと、.reduce という関数、二項演算として見れば演算子なのだが、これが配列のFold（畳み込み）処理をすることができるから

つまり、命令型コードでは、制御構文をもってコードブロック最初から最後まで全体で複雑なことをするスタイルに対して、関数型コードでは、1つの演算子にそういう反復処理を詰め込んでしまっている

その結果、コードは簡潔な二項演算になり、見通しもよく、バグの発生確率は激減するだろう

ループ毎に値が変わる変数をWatchしてフローの中身をいろいろ検討する代わりに、「ここの二項演算の式は妥当か？」という問題になるので、デバッグが簡潔になる

そのようなことを以下説明していく

チューリング完全になるための最後の要素である反復だが、だいたいの関数型プログラミングの教科書的な解説では再帰を利用するとされる、再帰というのは 自己参照 つまり自分で自分自身のことを言及したりすることだ

たとえば「 $0$ から $5$ までの自然数をぜんぶ足す 」とき、再帰を利用したコードはsum自身を参照するsum関数をつかって書く、recキーワードでsumが自己参照をする再帰関数であることをコンパイラに明示している

let rec sum =
    fun n ->
        if n = 0 then 0
        else n + sum (n - 1)

let result = sum 5
// 15

再帰は、 自己参照する関数 である 不動点コンビネータ（Yコンビネータが有名）がラムダ式だけで書ける 、つまり ラムダ式だけでチューリング完全になる ので、関数型プログラミングの理論でよく言及される

理論的には重要 で、たとえばファイルシステムのディレクトリなど再帰構造になっている対象をプログラミングする際には必須だが、それ以外では不必要に複雑なコードになるし、計算量が爆発しやすくパフォーマンスの問題があるので、自己参照する関数を定義する再帰プログラミングは避けたほうが良い、代わりにこれまでやったとおり代数構造のコードを書く

2つの式（ブロック）を $+$ という演算子でつなぎ合わせることを何度も繰り返してみよう、これは反復だ

$+$ + 演算子は、左結合（左から右方向へ演算が進んでいく）されるルールなので、 $0 + 1 + 2$ は、暗黙に、 $((0 + 1) + 2))$ と同じになる

\begin{gather*} ((((0 +1) + 2) + 3) + 4) + 5 \\ (((1 + 2) + 3) + 4) + 5 \\ ((3 + 3) + 4) + 5 \\ (6 + 4) + 5 \\ 10 + 5 \\ 15 \end{gather*}

二項演算の繰り返しは、 折り畳み 構造になっていることがわかる

結合性

折り畳みは、必ずしも 左から右 （ 左結合 ）とは限らない、明示的に、カッコをつけることで、 右から左 （ 右結合 ）へ結合順序を変えることもできる

\begin{gather*} 0 + (1 + (2 + (3 + (4 + 5)))) \\ 0 + (1 + (2 + (3 + 9))) \\ 0 + (1 + (2 + 12)) \\ 0 + (1 + 14) \\ 0 + 15 \\ 15 \end{gather*}

$+$ + 演算で、左結合、右結合、両者の結果が同じなのは、 「つなげる順番によって結果が変わるようなことはない」「つなげる順番はどうでも良い」という性質 ＝ 結合性 があるから、これはとても重要な性質なので後で詳しく調べよう

指数演算子 ** のように、デフォルトで 右結合 の演算子もある、この演算子は左から先に演算すると結果は異なるので、 結合性 がない

\begin{gather*} 2 ~ ** ~ 3 ** ~ 2 \\ 2 ~ ** ~ (3 ~ ** ~ 2) \\ 2 ~ ** ~ 9 \\ 512 \end{gather*}

関数型言語ならば、この繰り返し（折り畳み）処理をするための Fold 関数が提供されている

JavaScriptでは左結合の折り畳みは、 .reduce 、右結合の折り畳みは、 .reduceRight という名前の Array （配列）オブジェクトに紐づいている関数（メソッド）になっている

let plus = (a,b) => a + b;
let sum = [0,1,2,3,4,5].reduce(plus);
console.log(sum); // 15

[0,1,2,3,4,5]という式（ブロック） と plus関数という式（ブロック） をつなぎ合わせるのが.reduce関数

JavaScriptという言語の仕様上オブジェクト指向のメソッド表記になっているが、根本的には、左にデータ、右に関数、その２つをつなぎ合わせる 二項演算子としての.reduce と捉えることができる

[0,1,2,3,4,5] ~~ \textup{.reduce} ~~ plus = 15

もちろん、つなぎ合わせる式（ブロック）を足し算でなく掛け算の関数にすることもできる

[0,1,2,3,4,5] ~~ \textup{.reduce} ~~ times =120

また、前の二項演算子はパイプライン演算子だったが、今回はFold系の( .reduce )演算子に取り替えられている

2つのブロック接続（二項演算）さえできれば、自由に3つ以上接続していけるので、

(([0,1,2,3,4,5] ~~ \textup{.reduce} ~~ plus) + 1) \times 2

= (15 + 1) \times 2

= 16 \times 2

= 32

plus関数は、F#では直接(+)関数として取り出せるし、[0;1;2;3;4;5]という式（ブロック） と (+)関数という式（ブロック） をつなぎ合わせるのがList.fold関数や、 List.reduce 関数

F#のパイプライン演算子 |>

以下の説明は、説明の都合上、 UNIT2 BASIC の内容を先取りしてしまっている

後で詳しく説明しなおすので、今のところは、そういうものがあるのだ程度に読み流してもらって構わない

いちばん外枠の要点としては、

関数型コードでは、繰り返し処理も演算（式）で書ける 、ということ

F#のパイプライン演算子 |> と組み合わせて $\rhd\textup{reduce}$ |> List.reduce とすることで(+)とつなげる二項演算子になれる

[0;1;2;3;4;5] |> List.reduce (+)
// 15

[0;1;2;3;4;5] ~~~ \rhd\textup{reduce} ~~~~ (+) ~= ~15

２つの式（ブロック）をつなぐ演算子+は(+)とすることで、関数という式となり、つなぎ合わされる側のブロックとなる

9~~ + ~~(~[0;1;2;3;4;5] ~~~ \rhd\textup{reduce} ~~~ (+)~)

畳み込み操作をするために用意されているList.reduce 関数は、パイプライン演算子 |>とつなぎ合わされた |> List.reduce と「ひとまとまり」と見なすことで、畳み込み対象となるリスト[1;2;3;4;5]と(+)という2つの式（ブロック）をつなぐ演算子となる

このように 演算子が関数となり、関数が演算子となり、相互入れ替わりながら、二項演算式を構築していく