コンテンツにスキップ

関数型言語#

教科書2.3章 パラダイム 講義1回分

序論#

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 40, 'rankSpacing': 40, 'padding': 5}}}%%
graph TD
  classDef focus stroke-width:4px
  パラダイム --> 命令型;
  パラダイム --> 宣言型;
  命令型 -->|ほぼ同義| 手続き型;
  命令型 --> オブジェクト指向;
  宣言型 --> 関数型:::focus;
  宣言型 --> 論理型;

関数型言語（functional language）は宣言型言語の一種であり，C言語やJavaなどの命令型言語とは根本的な考えが大幅に異なる．関数を中心としてプログラムを組み立てるパラダイムである．

関数型はこれまでに慣れ親しんだ命令型言語とは，根本的な考えが大幅に異なる点に注意せよ．数学的・理論的側面が強いプログラミングパラダイムである．

Note

数学的な美しさやパズル的な面白さがあると捉えよ．

あらかじめ命令型言語と関数型言語の特徴の対比を示しておく．

命令型言語 関数型言語
計算モデル RAM（チューリングマシン） ラムダ計算
プログラムの構成 計算の手順の記述 関数の入出力の記述
変数の再代入 可能 原則禁止

関数型の考えは命令型プログラミングにおいても有効である．より良いプログラミングを身につけるためには，関数型言語の考えをよく理解しておくと良い．

代表的な関数型言語#

他のパラダイムと同様，様々な関数型パラダイムの言語が提案されている．

純粋/非純粋 名前
純粋 Haskell，Miranda，Lazy Kなど
非純粋 Lisp，Scala，OCaml，Standard MLなど

全ての関数が参照透過性（後述）を持つ関数型言語は純粋型と呼ばれる．非純粋型が存在する理由はプログラミングの利便性や効率のためである．徹底して哲学を追求した言語は，一見美しいが使い勝手や性能が犠牲となりやすい．

Note

Javaにはオブジェクトではないプリミティブ型が存在しており，純粋なOO言語とはいえない．これも利便性や効率化のためである．

本ページでは説明のためにLisp（厳密にはScheme）を採用する．Lispは最初の関数型言語であり，その後の多くのプログラミング言語に多大な影響を与えた．Lispには様々な実装が存在する．Lisp方言とも呼ばれる．

プログラミング言語の歴史

©1

Lisp方言©1 1950 1960 1970 1980 1990 2000 2010 2020
LISP x x
Scheme x x x x x x
Common Lisp x x x x x
Clojure x x x
Hy x x

本ページはLisp方言の一つであるSchemeを用いる．Schemeは言語仕様が小さく学習に適している．各種Lisp方言の基本概念は共通しているが細かな命令名の差異があるため，サンプルプログラムを実行する際には注意せよ(1)．

  1. より厳密には，Scheme実装としてはGaucheを用いている． Scheme仕様はR7RSである．
Lisp系言語（Scheme）による0～10の加算処理
(define sum (lambda (n)
  (if (= n 0) 0 (+ n (sum (- n 1))))))
(display (sum 10))  ; 55

Note

Lispは括弧()を多用する言語である．覚悟せよ．以下のようなジョークもある．

"A spy manages to steal the last 50MB of the Lisp program governing U.S. missile launches. Fortunately, it was all closing parentheses." ©2

"米国のミサイル制御用のLispプログラムの最後の50MBをスパイが盗み出すことに成功した．幸いなことにすべて閉じ括弧だった．"

2年後期の「プログラミングD」ではStandard MLを用いる．

参照透過性#

命令型言語では文（statement）の連続により，機械的操作（代入）を列挙してプログラムを表現する．他方，関数型言語では関数（function）の組み合わせによってプログラムを実現する．

ここでの関数とは命令型言語における手続きやメソッドのことではなく，数学的な意味での関数である．次の二次関数\(f(x)\)は数学的な関数の一例である．

\[ f(x) = x^2 + 3x + 2 \]

数学的な関数は同じ引数に対して常に同じ結果を返す．上記の場合，\(f(3)\)の結果は常に20である．この性質を参照透過性（referential transparency，参照の透明性）と呼ぶ．参照透過性が成り立つ場合，\(f(3) = 20\)や\(f(3) = f(1+2)\)という等式がいついかなる時も成立する．また変数\(y\)について\(y=3\)が成り立つのでであれば\(f(y) = f(3)\)も成立する．

他方，命令型プログラミングの関数やメソッドは参照透過的とは限らない．関数内でグローバル変数やフィールド変数を利用している場合，同じ引数に対して異なる結果を返すことがある．また変数\(y\)の再代入によって\(f(y) = f(y)\)が成立しないこともある．

参照透過的ではないC言語の関数
int y = 3;
printf("%d\n", f(y)); // 20
y = 5;                //    yに再代入すると
printf("%d\n", f(y)); // 42 同じf(y)でも結果が変わる＝参照透過的ではない
参照透過的ではないC言語の関数
int n = 0;
int count() {
    return ++n;              // n = n + 1; なので再代入
}
void main() {
    printf("%d\n", count()); // 1
    printf("%d\n", count()); // 2 同じcount()でも結果が変わる
}

参照透過性は関数型と論理型をはじめとする宣言型言語が満たす重要な性質である．参照透過性が満たされることで以下のような利点がある．

  • 関数の実行が文脈に非依存なため，可読性が高くテストが容易
  • プログラムの正当性を形式的・数学的に取り扱うことが容易

なお，関数\(f(x)\)の仮引数\(x\)に実引数を与えて計算する操作を関数適用（application）と呼ぶ．\(f(3)\)は関数適用の一例である．

関数型言語#

ポーランド記法#

関数型言語の説明の前に，まずは関数の記法・表現方法の定義から話を進める．

加算の式x + yは+を加算を行う関数名とみなして+(x, y)と書く(1)．これをさらに括弧とカンマを省略して単に+ x yと書くことにする．このような記法をポーランド記法（polish notation，prefix notation，前置記法）と呼ぶ．ポーランド記法を用いると通常の計算式は次のように記述される．

  1. plus(x, y)と考えると良い．馴染みのあるC言語やJavaの記法と同様である．
関数名 引数1 引数2 ...

式square(x + y) / sin(a * pi)は，ポーランド記法では以下のように記述される．

/ square + x y sin * a pi

ポーランド記法自体は関数型固有ではなく，コンピュータサイエンスで広く用いられる一般的な記法である．

Quiz

ポーランド記法で記述された次の式の結果を答えよ．

+ 1 * 2 3
Answer

7

一般的な中間記法では1 + (2 * 3)である．ポーランド記法を用いると，括弧なしに演算の適用順序を表現できる．

ラムダ記法#

関数の定義はλという文字を用いたラムダ記法（lambda notation）で表現する．例えば，引数の値を二乗する関数square(x)をラムダ記法で表すと次のようになる．

square = λx. * x x

λx.は関数squareの仮引数がxであることを示している．* x xは関数squareの本体であり，ポーランド記法で記述されている．

関数適用（関数の実行）は次のように表現される．実引数は3である．

square 3 = * 3 3 = 9

関数適用は名前付きの関数squareを用いずに，以下のように記述することもできる．

(λx. * x x) 3 = * 3 3 = 9

関数型言語でラムダ記法を用いる理由は2つである．1つ目の理由は関数定義と関数適用の明確な区別である．一般的な数学における関数定義の表記では，関数定義と関数適用を区別できない．例えば\(f(x)\)という表記は仮引数\(x\)を取る関数\(f\)の定義なのか，関数\(f\)への実引数\(x\)を渡す関数適用なのかが区別できない．ラムダ記法ではλという文字の直後は常に関数定義である．

2つ目の理由は関数名の省略である．関数型言語において関数名は関数の本質ではなく，省略可能な要素である．square = λx. * x xという定義において，squareは右辺の関数に対する別称（エイリアス）でしかない．ラムダ記法を用いることで，名前を付与せず関数の定義が可能となる．

Note

数学の関数定義には名前が必須である．

\[ f(x) = x * x \]

C言語の関数定義も名前が必須．

int square(int x) { return x * x; }

ラムダ記法を使えば名前を省略できる．

(λx. * x x)

ラムダ式#

ラムダ記法で表される式λx. * x xをラムダ式（lambda expression）と呼ぶ．関数型言語ではラムダ式を用いて関数を定義する．ラムダ式では関数名が付与されていないことから，無名関数や匿名関数と呼ばれることもある．

Note

JavaやPythonでもラムダ式が取り入れられている．命令型言語であっても部分的に関数型の優れた性質を利用することができる．

Pythonのラムダ式
f = lambda x: x * x  # ラムダ式で関数を定義
print(f(3))          # 9

ラムダ式において，引数として指定され実際に本体で利用されている変数を束縛変数（bound variable），そうでない変数を自由変数（free variable）と呼ぶ．以下のラムダ式において，xは束縛変数，yは自由変数である．

λx. + x y  ; xは束縛変数，yは自由変数

Quiz

次のラムダ式に対する関数適用の結果を答えよ．

(λxyz. + x (* y z)) 1 2 3
Answer

+ 1 * 2 3 = 7

カリー化と部分適用#

2つの引数を受け取り加算する関数addは，ラムダ式では次のように記述される．

add = λxy. + x y

addへの関数適用は次のように記述される．

add 3 5 = (λxy. + x y) 3 5 = + 3 5 = 8

addのような複数の引数を取る関数を，単一の引数を取る関数の連続した呼び出しに置き換える変換をカリー化（currying）(1)と呼ぶ．例えばaddをカリー化したaddcは次のように定義される．

  1. 関数型言語の理論を構築した論理学者Haskell Curryにちなんだ言葉である．🍛とは関係がない．
addc = λx. λy. + x y
     = λx. (λy. + x y)

addcは単一の引数xを受け取り，関数λy. + x yを返す関数である．

addcへ関数適用すると次のようになる．

addc 3 = (λx. (λy. + x y)) 3
       = λy. + 3 y

addc 3の結果は関数である．その関数へさらに関数適用すると次のようになる．

addc 3 5 = (λy. + 3 y) 5
         = + 3 5 = 8

なお関数適用は左結合則を満たす点に注意せよ(1)．

  1. num+num+numは(num+num)+numと解釈．
    addc 3 5は(addc 3) 5と解釈．

カリー化された関数に対して一部の引数を適用する操作を部分適用（partial application）と呼ぶ．addc 3は部分適用の一例である．それに対して，全部の引数を適用する操作を完全適用とも呼ぶ．addc 3 5は完全適用である．

カリー化の利点はプログラムの構成要素の共通化にある．例えば，引数に対して1を加算する関数incrementは，addcに引数1を部分適用する関数として定義できる．あるいは，1を減算する関数decrementは引数-1の部分適用である．

increment = addc 1  = λy. + 1 y
decrement = addc -1 = λy. + -1 y

incrementとdecrementの関数適用は次のとおりである．

increment 7 = (addc 1) 7  = (λy. + 1 y) 7  = 8
decrement 7 = (addc -1) 7 = (λy. + -1 y) 7 = 6

カリー化によって関数の要素を分解し部分適用を行うことで，加算という処理を一切用いずに，すなわち加算処理を再利用する形でincrementやdecrementの定義が可能である．

第一級オブジェクト#

一般的な命令型言語では整数値1 2や文字列"hi"などの値に対して，生成や代入，演算，関数への受け渡しなどの処理を適用できる．プログラミング言語一般において，このような性質を持つ要素を第一級オブジェクト（first class object）と呼ぶ．

関数型言語においては関数は第一級オブジェクトであり，値と同様に扱える．例えば，カリー化でも確認したように関数の評価結果は値だけではなく関数を取りうる．

再掲：カリー化された関数addcの結果は関数

addc 3 = λy. + 3 y

値と関数を区別しないという性質に基づくと，関数の引数として関数を渡すことも可能となる．

(λx. x 4 2) add = add 4 2 = 6
(λx. x 4 2) (λxy. + x y) = (λxy. + x y) 4 2 = 6

一般的には引数が関数の場合はfやgなどの文字が，引数が値の場合はxやyなどの文字が用いられるが，単なる可読性確保のための表現であり，ラムダ記法のルールや制約ではない点に注意せよ(1)．以降，上記の例は以下のように記述することとする．

  1. 関数型言語では値と関数を区別しないので，本来このようなルールすら不要である．
(λf. f 4 2) add = add 4 2 = 6
(λf. f 4 2) (λxy. + x y) = (λxy. + x y) 4 2 = 6

関数を引数に取る，または関数を返す関数を高階関数（higher-order function）と呼ぶ．他のプログラミング言語でも広く採用されている概念である．

高階関数とそうでない関数（疑似言語）
     int f(int)       // 普通の関数（引数：int，返り値：int）
     int f()          // 普通の関数（引数：なし，返り値：int）
     int f(function)  // 高階関数　（引数：関数，返り値：int）
function f(int)       // 高階関数　（引数：int，返り値：関数）
function f(function)  // 高階関数　（引数：関数，返り値：関数）

Quiz

次の関数適用の結果を答えよ．関数適用は左結合であることに注意せよ．

(λfg. f 1 (g 2 3)) (λxy. + x y) (λxy. * x y)
Answer

+ 1 * 2 3 = 7

次のように展開できる．

   (λfg. f 1 (g 2 3)) (λxy. + x y) (λxy. * x y) ; 1つ目λfに2つ目λを投入
-> (λg. (λxy. + x y) 1 (g 2 3)) (λxy. * x y)    ; 1つ目λgに2つ目λを投入
-> (λxy. + x y) 1 ((λxy. * x y) 2 3) ; 1つ目λxに1を投入
-> (λy. + 1 y) ((λxy. * x y) 2 3)    ; 1つ目λyに2つ目λを投入
-> + 1 ((λxy. * x y) 2 3)  ; λxyに2と3を投入
-> + 1 * 2 3
-> + 1 6
-> 7

このように考えても良い．2つ目のと3つ目のラムダ式は単なる+と*である．

(λfg. f 1 (g 2 3)) + *

高階関数によって，関数内部で用いられる値だけでなく内部の処理も引数化（パラメタ化，一般化）が可能となる．例えば配列をソートする関数sortは，ソート対象となる配列データとソートの方法（2要素の比較関数）の2つを受け取る関数だと抽象化できる．

データと操作をパラメタ化したsort関数
                比較関数（第二引数） ; (1)!
                   ↓
(sort '(5 3 1 2 4) <)  ; 1 2 3 4 5
            ↑
   ソート対象の配列データ（第一引数）

(sort '(5 3 1 2 4) >)  ; 5 4 3 2 1  コンパレータを変えれば降順ソートに
  1. ソートにおいてはコンパレータと呼ばれる．

Note

高階関数の考えは関数型以外でも広く採用されている．特に配列データの操作において強力である．map関数やreduce関数が代表例であり，この名前の関数を見かけたら高階関数だと認識して良い．

ラムダ式の同値関係#

ラムダ式が持つ3種類の同値関係を説明する．ここでは，ラムダ式における変数を小文字x y zで記述し，ラムダ式を大文字Mで記述する．この2つは本質的に同じものであるが説明のためにあえて区別して表現する．

ラムダ式は次の3つの変換が可能である．すなわち3種類の同値関係を持つ．

\(\alpha\)変換：束縛変数の名前が異なっていても2つのラムダ式が同値であることを意味している．

λx. * x x  ->a  λy. * y y

\(\beta\)変換：関数適用のことであり，関数適用の前後は同値であることを意味している．\(\beta\)簡約とも呼ばれる．

(λx. * x x) z  ->b  * z z

\(\eta\)変換：2つの式が全く同じ入出力関係を持つ場合，これらが同値であることを意味している．関数の外延的等価性に基づく変換規則であるが詳細は略す．

λx. M x  ->h  M

3つの変換を用いた式の書き換えを簡約（reduction）と呼ぶ．ラムダ式を用いた計算とは簡約の繰り返しである．

ラムダ計算#

関数型パラダイムの理論的な計算モデル，ラムダ計算（lambda calculus，ラムダ算法）について説明する．題材として自然数に対する四則演算を考える．

まず自然数は次のように定義される．チャーチ数とも呼ばれる．

0 = λfx. x
1 = λfx. f x
2 = λfx. f (f x)
3 = λfx. f (f (f x))
    ...
n = λfx. f (f ... (f x) ... )  ; fがn個

直感的にはfを適用する回数によって自然数を表している．この時点では深く考えなくて良い．このような定義であると解釈せよ．

インクリメントを表す関数succ(1)は次のように定義される．

  1. succはペアノの公理に由来する名前であり，successor（後任者）の略である． 逆はpredecessor（前任者）である．
succ = λnfx. f (n f x)

直感的には，succは与えられた自然数nに対してfを一つ追加する．succに引数2を与えたときの簡約（書き換え）の流れは以下のようになる．

succ 2                               ; succを置換
=   (λnfx. f (n f x)) 2              ; 2を置換
=   (λnfx. f (n f x)) (λfx. f (f x)) ; 1つ目λnに2つ目のλを投入
->b (λfx. f ((λfx. f (f x)) f x))    ; 2つ目λfに最後のfを投入
->b (λfx. f ((λx. f (f x)) x))       ; 2つ目λxに最後のxを投入
->b (λfx. f (f (f x)))               ; fの数は3
=   3

加算plusは次のように定義される．

plus = λmnfx. m f (n f x)

plusは2つの引数mとnを受け取り，m個のfとn個のfを生成する．簡約の過程は次のようになる．

plus 1 2                                           ; plusを置換
=   (λmnfx. m f (n f x)) 1 2                       ; 1と2を置換
=   (λmnfx. m f (n f x)) (λfx. f x) (λfx. f (f x)) ; 1つ目λmに2つ目のλ式を投入
->b (λnfx. (λfx. f x) f (n f x)) (λfx. f (f x))    ; 1つ目λnに3つ目のλ式を投入
->b (λfx. (λfx. f x) f ((λfx. f (f x)) f x)) ; 2つ目λfに途中のfを投入
->b (λfx. (λx. f x) ((λfx. f (f x)) f x))    ; 2つ目λxに3つ目λを投入
->b (λfx. f ((λfx. f (f x)) f x)) ; 2つ目λfに最後のfを投入
->b (λfx. f ((λx. f (f x)) x))    ; 2つ目λxに最後のxを投入
->b (λfx. f (f (f x))) ; fの数は3
=   3

それ以外の四則演算もラムダ式によって表現可能である．ただし自然数をfの個数として定義しているため，負の整数を表すことはできない．しかし整数を1減算するpredを定義し，それを再利用することで負数を表現できる．

mult = λmn. m (plus n) 0                      ; 乗算
exp  = λmn. m (mult n) 1                      ; 指数
pred = λnfx. n (λgh. h (g f)) (λy. x) (λy. y) ; デクリメント
sub  = λmn. n pred m                          ; 減算

ここでは各演算子の簡約の流れは省略するが，興味があれば手作業で簡約してみるとよい．基本は置換操作の繰り返しである．

整数だけでなくブール値true falseや，論理式not and or xor，ブール値を利用した分岐構造ifもラムダ式で定義可能である．また繰り返し構造は再帰呼び出しで表現する．

ラムダ計算はチューリング完全であり，計算機上でのあらゆる計算を表現することができる．関数型パラダイムはプログラミング言語として成立する．

チャーチ数を用いたラムダ計算は理論的な枠組みであり，実際の関数型言語で採用されているわけではない．あらゆる対象を関数として表現する世界において，様々な計算を表現できるかを考えるための道具である．

Lisp（Scheme）#

関数型言語Schemeについて触れる．ここでの目的はSchemeの言語機能の紹介ではなく，実際の関数型言語を体験することにある．サンプルプログラムを実行する際は，ブラウザ上で動くサービス JDoodleやTutorials Pointを利用すると良い．

まずSchemeの基本的な操作の一例を以下に示す．

3の出力
(display 3)               ; 3
(display (+ 1 2))         ; 3
(display (+ 1 (* 2 3)))   ; 7
(display "hello")         ; hello
(display #t)              ; #t       true
(display (< 2 3))         ; #t
(display (= 2 3))         ; #f       false
(display '(1 2 3))        ; (1 2 3)  リスト構造のデータ
(display (car '(1 2 3)))  ; 1        リストの先頭
(display (cdr '(1 2 3)))  ; (2 3)    リストの先頭以外

先のsquareのラムダ式と等価なSchemeプログラムを以下に示す．

square = λx. * x x  ; 関数定義
square 3 = 9        ; 関数適用
squareの定義と関数適用
(define square (lambda (x) (* x x)))
(display (square 3))  ; 9

Schemeの関数定義はラムダ式そのものであり，基本的な表記は変わらない．関数名を付与しないラムダ式も当然記述可能である．

(λx. * x x) 3 = 9
無名の関数定義と実行
(display ((lambda (x) (* x x)) 3))  ; 9

クイズのラムダ式もほぼ記法は同じである．

(λfg. f 1 (g 2 3)) (λxy. + x y) (λxy. * x y)
ラムダ式を引数として受け取るラムダ式
(display
    ((lambda (f g) (f 1 (g 2 3)))
        (lambda (x y) (+ x y))
        (lambda (x y) (* x y))))  ; 7

(display
    ((lambda (f g) (f 1 (g 2 3))) + *)) ; このようにも記述可能

条件分岐はif <条件式> <true時の関数> <false時の関数>として記述する．if自体も3つの引数を受ける関数であり，3つの引数全てが関数である．関数型言語ではあらゆる要素を関数として表現する．

条件分岐
(display (if (= 2 3) "a" "b"))  ; b 2=3は成立しないのでfalse側を取る

Schemeでは繰り返しには再帰を利用する．例えば，階乗計算は次のように記述する．

繰り返し
(define fact (lambda (n)
    (if (= n 1)
        1
        (* n (fact (- n 1))))))
(display (fact 5))  ; 120
再帰の流れ
(fact 5)
-> * 5 (fact 4)
-> * 5 (* 4 (fact 3))
-> * 5 (* 4 (* 3 (fact 2)))
-> * 5 (* 4 (* 3 (* 2 (fact 1))))
-> * 5 (* 4 (* 3 (* 2 1)))
-> 120

最後に，より実践的な例としてSchemeを用いたクイックソートのプログラム©3を示しておく．プログラムの詳細は確認する必要はない．関数型言語が命令の列挙ではなく，関数定義とその組み合わせでプログラムを表現していることを確認せよ．

クイックソート
(define (split-by l p k)
  (let loop ((low '()) (high '()) (l l))
    (cond ((null? l) (k low high))
      ((p (car l))
        (loop low (cons (car l) high) (cdr l)))
      (else
        (loop (cons (car l) low) high (cdr l))))))

(define (qsort l gt?) ; リストとコンパレータを受け取る
  (if (null? l)
    '()
    (split-by (cdr l)
      (lambda (x) (gt? x (car l)))
      (lambda (low high)
        (append (qsort low gt?)
          (list (car l))
          (qsort high gt?))))))

(display (qsort '(5 3 1 4 2) >))  ; (1 2 3 4 5)

まとめ#

関数型言語の概略，及び関数型言語の計算モデルであるラムダ計算について説明した．

  • 関数型言語の計算モデルはラムダ計算である
  • 関数型言語では関数を組み合わせてプログラムを表現する・手続きを列挙しない
  • 関数型言語では変数の参照先メモリの現在値を意識しない（参照透過性を満たす）
  • 関数型言語では値も関数である
  • Lispの構文はラムダ式に準ずる
再掲：命令型と関数型の対比
命令型言語 関数型言語
計算モデル RAM（やチューリングマシン） ラムダ計算
プログラムの構成 計算の手順の記述 関数の入出力の記述
変数の再代入 可能 原則禁止

《宿題》#

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                 ; ifをラムダ式に書き換え
-> (λcxy. c x y) false A B      ; falseをラムダ式に書き換え
-> (λcxy. c x y) (λxy. y) A B
-> ???

回答フォーム

  1. https://en.wikipedia.org/wiki/Lisp_(programming_language) ↩↩

  2. https://www.reddit.com/r/ProgrammerHumor/comments/7sk1rx/a_spy_manages_to_steal_the_last_50mb_of_the_lisp/ ↩

  3. https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Scheme ↩