代数プログラミング入門 Ch1 イントロダクション
(執筆準備中)
代数の基礎と,代数による仕様記述,Haskellの基礎に関して書いていく予定です. 現在執筆中のため, 構成及び内容が今後変わります.
1 はじめに
本資料は,正規の大学の科目ではなく, 学内での学生,教員の勉強会において使用する予定のものとなります. したがって,講義形式で作成しますが,通常の講義よりはかなり緩めの記述,内容が含まれます.
本講義では,関数型プログラミング言語Haskellの基礎,使用法,及び設計に関して扱います. 想定する履修者はPythonやJavaScriptなどの手続き型言語の使用経験はあるが,関数型言語を利用したことがない大学学部生です. 関数型言語の特徴を説明する際に手続き型言語の例としてPythonでの記述が出てきますが,Pythonの文法等に関しては既知のものとして扱います.(こちらはもとも官庁用の報告書として執筆したものを(大幅に)改変したものですので,もともとの資料ではVBAやJavaを事例として用いていました.)
また,本講義では代数学を利用したプログラミングの設計に関する方法論も扱います.集合論や代数学に関する知識は前提とせず,初歩から扱いますので,数学に関する前提知識は特に必要ありません. なお,本講義は集合論や代数学の習得を目的としているわけではないので,これらに関してはかなり簡略化した説明になります.専門的に数学を学びたい方向けの講義ではないことを理解したうえで受講してください.
一方で,CLIの操作やディレクトリの概念,ソフトウェアのインストール,テキストエディタの設定などの基本的なPC操作に関しては,扱いません. それらが分からない方は,それらを自分で学習するか,それらを扱っている講義を履修してから受講することをおすすめします.
1.1 本資料の読み方
(執筆中)
1.2 Haskellとは
Haskellは,1987年に生まれた静的型付けの純粋関数型言語です. Haskellには,様々な特徴がありますが,本講義では,特に代数的データ型による,代数的なプログラミングに焦点をあてて,代数的な仕様記述とHaskellの関連を中心に議論します.
Haskellがどんな言語で,どのようなメリットがあるのか,という話は今後本講義でも扱いますが,ここでは深入りしません. 取り敢えず,どのような言語かを細かく説明する前に,関数型言語の雰囲気を掴んでもらおうと思います.
1.3 関数型言語の雰囲気
HaskellはLispやOCamlなどと同じ関数型言語です.関数型言語は関数によってプログラムを構築していく点にありますが,近年ではこのスタイルは関数型言語の専売特許というわけではなくなりつつあり,関数で書くことの特別さは,薄れつつあります. なので,ここでは,関数型言語の細かい機能について見る前に,関数型言語の考え方について,手続き型言語との違いという観点で見ていきましょう.
関数型言語でプログラミングををするとは,｢それが何か｣を分解して書いていくことです. 関数型プログラミングが宣言的であると言われる所以はそこにあります.手続き型言語が,｢何をどうするのか｣という手続きを書くのにたいして,｢欲しいものはなにか｣を宣言します.
こちらの(Haskell界隈では)有名なブログでは,関数型言語の考え方について以下のように説明しています.
Functional programmers have a peculiar way of approaching problems. They start by asking very Zen-like questions. For instance, when designing an interactive program, they would ask: What is interaction? When implementing Conway’s Game of Life, they would probably ponder about the meaning of life.
- 翻訳(DeepL大先生)
関数型プログラマーは問題への取り組み方が独特だ. 禅問答のような質問から始めるのだ.例えば,インタラクティブなプログラムを設計するとき,彼らは「インタラクションとは何か?コンウェイの「人生ゲーム」を実装するとき,彼らはおそらく人生の意味について熟考するだろう.
手続き型プログラミングと関数型プログラミングの違いは色々とありますが,取り敢えずここでは,この文章に習って
- 関数型プログラミング: ｢それが何か｣を問い,｢それが何か｣をプログラムする.
という観点に注目します. 例として以下の｢ウサギの問題｣について考えてみましょう.
ウサギの問題
1つがいのウサギは,生まれてから2ヶ月後から毎月1つがいずつのウサギを産む
ウサギが死ぬことはない
この条件の下で,生まれたばかりの1つがいのウサギは1年の間に何つがいのウサギになるか
これについて,取り敢えず12ヶ月までのつがいの数をプログラムを用いて計算してみましょう.
まずは手続き型の考え方で数を数えてみます. 手続き型言語的には,｢ウサギのつがいの数｣を｢どのように求めるのかという手続き｣をプログラムに記述します.
note
学生にプログラミングを教えているとこれくらいのプログラムは,for文,if文,代入などの概念をちらっと読んだだけで簡単にできる人もいれば,数時間教えてもできない人もいます.これが何によって異なるのかというのは,長年の謎で,教育の難しいところです.
しかも,プログラムを教える人間は大抵前者なので,教師も学生も何が分からないのか分からないという事態によくなってしまいますね.
しかし,大抵の場合後者の人に話を聞いていくと,そもそもこの手続きを日本語であっても書けないという人が多いようです. なので,本当に苦労するタイプの人は,パワーポイントでウサギの絵を並べてルールにのっとってウサギが増えていく様子を小学生に教える日本語資料を作ってというような作業を一緒にすることになります.
これを書きながらこういった学生が実は関数型なら簡単だったりしないだろうか,と考えていますが,楽観的に過ぎるだろうなという予感がしています.いろいろな方法がありますが(何が起きて,次に何が起きて,というふうに手続きを考える)｢手続き型言語っぽい数え方｣を一つ考えると,例えば
つがいは,新生ウサギ(0ヶ月)→子供ウサギ(1ヶ月)→大人うさぎ(2ヶ月)の順で変化する
大人うさぎのつがいは毎月1つの新生うさぎのつがいを産む
0ヶ月の新生うさぎの(こどもが産めない),子供ウサギ,大人うさぎの数を記録する
- 新生 1
- 子供 0
- 大人 0
1月たつと
- 大人と同じ数だけ新生が生まれる
- 子供が大人になる
- 新生が子供になる
これを12ヶ月繰り返す
というように｢何がどうなる｣という｢手順｣を書いた説明になるかと思います. 授業では大抵,これをフローチャートに書き直させて,フローチャートをプログラムに直すという作業をさせますが,そこは省略します.
これをPythonのプログラムにすると以下のようになり,結果は233となります.
# 初期化
months = 12 # シミュレートする月数
#1ヶ月目の状態
new_born_pairs = 0 #新生のつがいの数
young_pairs = 1 # 子供のつがいの数
mature_pairs = 0 # 大人のつがいの数
# 各月におけるうさぎのつがいの数をシミュレート
for month in range(1, months + 1):
# 大人と同じ数だけ新生が生まれる
new_born_pairs = mature_pairs
# 子供が大人になる
mature_pairs += young_pairs
# 新生が子供になる
young_pairs = new_born_pairs
# 成熟したつがいと若いつがいの合計
total_pairs = mature_pairs + young_pairs
print(total_pairs)こういった考え方が,いわゆる手続き型的な考え方とプログラミングの方法になります.
では,関数型の考え方とはどのようなものでしょうか. 先ほど引用したように,関数型では,それが何かを考えます.つまり,ここで問われている｢つがいの数｣を抽象化して,その特徴を記述するわけですね.
特定の数がなにかのルールに基づいて段々と増えていくというときに,それを並べてみて,法則性を探るということが一般的に行われます.これは,高校数学で扱う漸化式の考え方ですね.
月ごとのつがいの数を,並べてみると以下のようになります. そして,その増え方を計算してみると一定のルールに基づいていることが分かります.
| 月 | つがいの数 | 計算 |
|---|---|---|
| 0 | 1 | |
| 1 | 1 | |
| 2 | 2 | 1 + 1 |
| 3 | 3 | 1 + 2 |
| 4 | 5 | 2 + 3 |
| 5 | 8 | 3 + 5 |
| 6 | 13 | 5 + 8 |
| 7 | 21 | 8 + 13 |
| 8 | 34 | 13 + 21 |
| 9 | 55 | 21 + 34 |
| 10 | 89 | 34 + 55 |
| 11 | 144 | 55 + 89 |
| 12 | 233 | 89 + 144 |
実はこのウサギのつがいの合計どの月でもは,1,1,2,3,5,8という風に前々月と前月のつがいの合計になることが知られています. このような,前の数字と前の前の数字の和によって次の数字を作る数をフィボナッチ数といいます.
※ 普通フィボナッチ数というと,0から始まりますが,ここではウサギの例で考えたいので1から始まることにします.
フィボナッチ数を漸化式として捉えると,第n月のフィボナッチ数の正体は以下のように得られます.
F_0 = 1 \\ F_1 = 1 \\ F_n = F_{n-1} + F_{n-2} (n >= 2)
したがって,上の条件での12ヶ月後のウサギの数はなにかという問題は,フィボナッチ数の第12番めの項F_{12}がなにかという問題であり,フィボナッチ数とはなにかといえば上の漸化式である,という風に考えることができます.
実際に計算手順を,一つひとつ追っていくのではなく,このように求めたい対象がなにかということを考えて,抽象化し記述するというのが,関数型言語の基本的な考え方になります.
ちなみに,これをHaskellで書くと以下のようになり,上の漸化式の書き方とかなり近い対応関係があることが分かります.
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)※メモ化とかそういったことは,取り敢えずここでは置いておきます (この辺の数学的定義そのままだと,実用には向かない問題は,後ほど扱います.)
これを実行してみると確かに正しい数が求められています.
ghci> :{
ghci| fib :: Int -> Int
ghci| fib 0 = 1
ghci| fib 1 = 1
ghci| fib n = fib (n-1) + fib (n-2)
ghci| :}
ghci> fib 12
233当然フィボナッチ数の漸化式は広く知られていますし, むしろ最初から漸化式として学習することが多いでしょう. したがって, Pythonでの実装もフィボナッチ数が漸化式であるという前提で,以下のように書くほうが一般的です.
def Fib(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return Fib(n-1) + Fib(n-2)また,最近では,PythonやJavaScriptなどの手続き型の言語にも,関数型の考え方が導入され,内包表記,再帰,ラムダ式などの関数型のシンタックスも一般的に使われるようになっています(これらの詳細についてはこのあとやっていきます).逆にHaskell等の関数型言語においても,手続き型のほうが便利な場合には手続き型の記法を利用します.
したがって,現在では関数型的な考え方と,手続き型の考え方というのは,それほど明確に分かれるものではありません.
ここでは,手続き型の考え方と関数型の考え方の違いを説明するために,Pythonの事例をあえてあまり用いられない方法で書きましたが,大げさに書けば手続き型と関数型の考え方の違いとはこのような考え方,問題へのアプローチの仕方にあります.
1.4 関数型だと何が嬉しいのか
前節では,関数型の考え方に関して簡単な事例をしましました. 関数型の考え方がしっくり来る人は,それが関数型を使う理由になるでしょうが,しっくり来るという抽象的な話ではなく,具体的な関数型言語のメリット/デメリットをこの節では紹介します. なお,関数型言語と一言でいっても,様々な言語がありますし,前述のように手続き型と関数型が明確に分かれる時代でもありません.
関数型言語の設計仕様は,関数型です. 手続き型言語の仕様定義にもいろいろな種類があります.
(執筆中) 例の論文のまとめ
厳密な仕様記述を書くとプログラムと1体1対応になる.そもそもHaskellで書けばプログラムと仕様が対応関係を持つようになりますし,数式への変換も容易です.
そういった意図もあり,私が内閣府で統計作成を市ていた時代には, 数式による定義,とプログラムのペアを対応付けたOSSとして基幹統計を開発することを提唱していましたが,それは色々な制約でまだ実現していません.
1.5 設計も関数型で
(執筆中)
1.5.1 雑談:なんでHaskell?
(執筆中)