初めてのLisp関数プログラミング 読書メモ

ウェブ技術 デジタルトランスフォーメーション技術 人工知能技術 機械学習 自然言語処理技術 推論技術 セマンティックウェブ技術 深層学習技術 オンライン学習 強化学習技術 チャットボットと質疑応答技術 ユーザーインターフェース技術 知識情報処理技術 推論技術 プログラミング スパースモデリング 確率的生成モデル サポートベクトルマシン LISP Prolog 本ブログのナビ

LISPについて

LISP（リスプ）は、人工知能や人工言語処理などの分野で広く使用されるプログラミング言語の一種であり、その名前は「LISt Processing」に由来する。LISPは、関数型プログラミング言語あり、かつプログラムをデータとして扱い、データをプログラムとして評価する、リフレクティブ（反射的）なプログラミング言語としても知られている。LISPの主な特徴は以下のようになる。

• リスト（リンクドリスト）が基本的なデータ構造である：LISPのデータはリストとして表現され、それ自体がLISPのプログラムとして評価される。この特徴を活用して、LISPは高度に柔軟なデータ構造を扱うことができる。
• 関数型プログラミングをサポートしている：LISPは関数型プログラミング言語であり、関数を一等の値として扱うことができる。関数を引数や戻り値として他の関数に渡したり、変数に代入したりするメタ的な「高階関数」としての使い方もできる。
• 自己言及（セルフリファレンス）をサポートしている：LISPのプログラムは自己言及をすることができ、自身の構造を参照することができる。これにより、LISPは高い柔軟性を持ち、自己変更可能なプログラムを書くことができる。
• シンプルな構文：LISPの構文は非常にシンプルであり、プログラムの記述が簡潔である。
• 多くの派生言語が存在する：LISPには多くの派生言語が存在し、それぞれに独自の特徴や用途がある。代表的な派生言語には、Common Lisp（コモンリスプ）、Scheme（スキーム）、Clojure（クロージャー）などがある。

今回は、「初めてのLisp関数プログラミング」より。読書メモを記載する。

初めてのLisp関数プログラミング 読書メモ

Lisp・関数型プログラミングのメリットとは何か――副作用のないプログラミングがまず挙げられる。これでバグが圧倒的に少なくなる。さらにはコードの再利用がしやすいこと，並列処理が得意であるということも。それだけではない。動的な型付けも特徴だし，ラムダ計算もクロージャも，さらにはオブジェクト指向までできる。数十年の時を越えて現代にも通用する普遍的なアイデアがLispにはある。本書はさまざまなLispプログラム（ハノイの塔，エイトクイーン，オンライン書店など）を解説し，さらにリファクタリングまでいっきに学ぶものとなる。本書で関数型プログラミングのエッセンスを得ることができる。

第1章　関数型プログラミングとは何か――そして，それがなぜ難しいのか？

1.1 関数型プログラミングとは

1.1.1 純粋関数と参照透過性
1.1.2 副作用
1.1.3 関数型プログラミングの概観

1.2 関数型プログラミングの歴史

1.2.1 関数型プログラミング黎明期（1930～1960年代）ラムダ計算の誕生からLispへ
1.2.2 関数型プログラミング揺籃期（1970年代）Lisp v.s. MLの戦争
1.2.3 関数型プログラミング発展期（1980年代）AIによる黄金時代
1.2.4 関数型プログラミング雌伏期（1990年代）Lispの雌伏とHaskellの誕生
1.2.5 関数型プログラミング再生期（2000年代）F#やScalaらによる新たな時代に
1.2.6 関数型プログラミング言語第2次成長期（2010年代）IoT時代の関数型へ

1.3 関数型プログラミングは何がうれしいのか

1.3.1 再利用がしやすい
1.3.2 並列処理に向いている
1.3.3 バグが少ない
1.3.4 テストが行いやすい
1.3.5 コードの最適化／形式手法の適用／コードの自動生成に向いている
1.3.6 動的プログラミングができる――抽象的なプログラミングができる
1.3.7 その他のうれしいところ

1.4 関数型プログラミングはなぜ難しいのか

1.4.1 変数が使えない→破壊的代入文を伴う変数――副作用のないプログラム
1.4.2 代入文が使えない→破壊的代入文――副作用のないプログラム
1.4.3 配列が使えない→ミュータブルなデータ構造――副作用のないプログラム
1.4.4 再帰プログラミングがしにくい――副作用のないプログラム
1.4.5 連続的な関数適用がしにくい ――副作用のないプログラム
1.4.6 高階関数が難しい――関数型プログラミングの便利で難しい機能
1.4.7 評価戦略が面倒――関数型プログラミングの便利で難しい機能
1.4.8 他の機能が難しそう――関数型プログラミングの便利な機能
1.4.9 関数型の設計方法がわからない
1.4.10 パラダイムシフトがたいへん
1.4.11 関数型プログラミングは難しくない

1.5 関数型プログラミングを使いこなすには

1.5.1 副作用のないプログラムのために
1.5.2 関数型プログラミングの便利な機能のために
1.5.3 不純関数型プログラミングのススメ
1.5.4 非関数型プログラミング言語での関数型プログラミングのススメ

1.6 まとめ

第2章　関数型プログラミングを学ぶためのLisp超入門

2.1　Lisp事始め

2.1.1 Lispを関数型プログラミングの学習用言語として勧める理由
2.1.2 Lisp処理系の紹介
2.1.3 最初のLispプログラム「階乗計算 fact」
2.1.4 前置記法
2.1.5 動的型付け
2.1.6 S式――リストとアトム
2.1.7 Lispの評価戦略

2.2 Lisp関数一巡り

2.2.1 関数とマクロ，特殊形式
2.2.2 関数定義とif関数，比較関数，四則演算
2.2.3 特殊形式quoteとfunction
2.2.4 リスト
2.2.5 シンボル
2.2.6 真理値と述語関数
2.2.7 関数型プログラミング向きの関数
2.2.8 マクロ関数
2.2.9 Lispの手続き型機能
2.2.10 オブジェクト指向機能
2.2.11 その他の機能

2.3　Lispの関数型機能の実装――クロージャ

2.3.1 クロージャとその実装
2.3.2 シンプルなクロージャの例［1］
2.3.3 共通の環境を持つ複数のクロージャの例［2］

2.4 まとめ

第3章 関数型プログラミングの基本

3.1 関数

3.1.1 関数の定義ふたたび
3.1.2 関数であるために必要なもの――参照透過性と副作用がないこと
3.1.3 関数の利点――非純粋関数も含んだ関数の一般的な利点

3.2 ラムダ計算

3.2.1 ラムダ計算の記法と規則
3.2.2 カリー化
3.2.3 チャーチ数
3.2.4 ラムダ計算の性質

3.3 副作用

3.3.1 副作用の有無による関数の比較
3.3.2 状態の繰り込み
3.3.3 副作用の功績――副作用の功罪とは？
3.3.4 副作用の原罪――副作用の功罪とは？

3.4 リストの活用――イミュータブルなデータ構造

3.4.1 配列はミュータブル
3.4.2 リストはイミュータブル
3.4.3 リストによるリッチなデータ構造の実装――グラフ，ランダムアクセスリスト

3.5 再帰プログラミング

3.5.1 副作用再考
3.5.2 最初の再帰プログラム「階乗計算 fact」
3.5.3 再帰プログラミングの一般化
3.5.4 再帰プログラミングのスタックでの実装
3.5.5 再帰プログラミングのコツ――再帰の発見
3.5.6 再帰プログラムのパターン1――リストパターン
3.5.7 再帰プログラムのパターン2――整数パターン
3.5.8 再帰プログラムのパターン3――蓄積パターン
3.5.9 末尾再帰
3.5.10 再帰プログラミングのデバッグ――トレース
3.5.11 再帰プログラミングの効率と安全性

3.6 高階関数

3.6.1 1階関数と2階関数
3.6.2 高階関数の例――全数検索
3.6.3 高階関数の例――関数合成 compose
3.6.4 高階関数の例――mapとreduce
3.6.5 高階関数の例――カリー化
3.6.6 高階関数の実行速度と了解性

3.7 評価戦略――遅延評価

3.7.1 内側優先・左側優先戦略――正格評価
3.7.2 クロージャによる評価戦略の変更――非正格評価
3.7.3 マクロによる遅延評価の実装
3.7.4 項書き換えシステム
3.7.5 内側優先評価 vs. 外側優先評価
3.7.6 非正格評価（遅延評価）を使うタイミング

3.8 関数型指向設計

3.8.1 部品の組み合わせ設計
3.8.2 モジュール分割と差分開発
3.8.3 データ設計とデータ間の関係
3.9 関数型プログラミング周辺――総称関数，型推論，モノイド，モナド，FRP
3.9.1 総称関数（包括関数）generic function
3.9.2 型推論 type inference
3.9.3 モノイド monoid
3.9.4 モナド monad
3.9.5 関数型リアクティブプログラミング Functional Reactive Programming（FRP）

3.10 まとめ

第4章 プログラミングパラダイムの比較

4.1 オブジェクト指向プログラミングとの比較

4.1.1 オブジェクト指向の本質1――クラスによるカプセル化と情報隠蔽
4.1.2 オブジェクト指向の本質2――差分プログラミング
4.1.3 オブジェクト指向の利点と欠点
4.1.4 関数型プログラミングとの比較

4.2 手続き型プログラミングとの関係

4.2.1 手続き型プログラミングの本質 副作用による状態操作――配列と変数中心
4.2.2 手続き型プログラミングの理解――目的を知らせず命令ばかり
4.2.3 手続き型プログラミングの利点と欠点
4.2.4 関数型プログラミングとの比較

4.3 関数型プログラミングの分析

4.3.1 副作用がないプログラムとその効果
4.3.2 プログラムの作りやすさ
4.3.3 プログラムのわかりやすさ
4.3.4 プログラムの実行効率
4.3.5 関数型プログラミングの将来性

4.4 Javaで関数型プログラミング（参考）

4.4.1 状態操作のときは自分自身 thisのクローンを返す
4.4.2 他人のオブジェクトを変更するとき
4.4.3 オブジェクトのコピー

4.5 まとめ

第5章 関数型プログラミングの演習

5.1 再帰プログラミング入門演習

5.1.1 クイックソート（1階関数版）
5.1.2 ハイブリッド版クイックソート（1階関数版）
5.1.3 ハノイの塔
5.1.4 4本ハノイの塔

5.2 高階関数

5.2.1 全数検索
5.2.2 クイックソート（2階関数版）
5.2.3 クイックソート（2関数引数版）

5.3 イミュータブルデータのリスト

5.3.1 エイトクイーン
5.3.2 エイトクイーン（ハイブリッド版）
5.3.3 ドキュメント構造 - ツリートラバース
5.3.4 待ち行列（キュー）

5.4 状態

5.4.1 貯金箱と銀行
5.4.2 乱数とスロットマシン

5.5 遅延評価

5.5.1 たらい回し関数――tarai関数（竹内関数）
5.5.2 無限リスト

5.6 オブジェクト指向プログラム――カプセル化と差分プログラミング

5.6.1 学生と人間――カプセル化と差分プログラミングの第一歩
5.6.2 座標とウィンドウ――多重継承

5.7 オブジェクト指向と手続き型プログラムのリファクタリング――アンチパターン

5.7.1 不要なグローバル変数
5.7.2 不要なクラス
5.7.3 グローバル変数の連れ回し
5.7.4 アンチパターンのプログラムに最初にするリファクタリング

5.8 総合演習――Lisp処理系

5.8.1 構文解析の流れ
5.8.2 Lispの構文規則
5.8.3 構文解析――リテラルと関数適用
5.8.4 構文解析――特殊形式とリスト
5.8.5 コード生成

5.9 総合演習――オンライン書店

5.9.1 ビジネスオブジェクト――書籍
5.9.2 ビジネスロジック――ISBNと出版社の入力チェック
5.9.3 ビジネスロジック――データベースアクセスと階層リスト

5.10 まとめ

第6章 関数型プログラムの評価とリファクタリング

6.1 評価基準――コードメトリクス

6.1.1 コードメトリクスとは
6.1.2 コードサイズに関するメトリクス――コード行数，ステートメント数
6.1.3 項目数のメトリクス――関数呼び出し数
6.1.4 コードの複雑さのメトリクス――サイクロマティック数
6.1.5 再帰のメトリクス――再帰の段数

6.2 評価基準――コードレビュー

6.2.1 ネーミング
6.2.2 シンプル＆スモール――1関数1機能
6.2.3 抽象化――総称関数と高階関数のバランス
6.2.4 了解性と効率のバランス

6.3 関数型プログラムのリファクタリング

6.3.1 リネーム
6.3.2 関数抽出
6.3.3 末尾再帰化
6.3.4 副作用のないプログラムの再考

6.4 まとめ

おわりに

参考文献