  |
はてなキーワード: 関数プログラミングとは
コロナ自粛で勉強中。以前買ったHaskell本を読み直している。落ち着いて読めば結構理解できる。
https://gihyo.jp/book/2016/978-4-7741-8390-9
現場の方々に向け，関数プログラミングのエッセンスを厳選解説した入門書。
関数型言語Haskellを用い，基本から，Java 8/C/C++/Python/JavaScript/Rubyをはじめ各種命令型言語との比較，オススメの開発/設計テクニック等を平易に解説。
改訂版ではGlasgow Haskell Compiler 8ならびに新機構のStackage/stackへの全面対応，関数型言語由来の他言語の機能解説章（第8章）の新設（Swift/Go/Rust/C#等の例も紹介）をはじめ実践開発に役立つ解説を増強し，関数型言語でも命令型言語でも活かせる「使える基本」を凝縮しました。
普通に読んだら「FRPも状態渡しと同様の限界がある」と言ってる文章だし、
状態渡しで何でもできるなんて誰も言ってないのに、相変わらず凄まじい捻じ曲げだな。
http://qiita.com/nonstarter/items/2763f5d85f2b8df3b18b
＞いずれにせよ、状態機械の数学的構成では状態遷移が状態と入力から状態への関数として表現されるというだけのことではあり（状態渡し）、状態遷移が複雑になれば状態遷移を純粋な関数として表現する作業も複雑になり困難になるので（そしてそれはしばしば綺麗な関数合成では上手くいかないようなものになることが多いので）、結局のところ少なくとも現状のFRPも（イベントのシグナルから状態のシグナルを構成する際に状態遷移をそうした関数で表現する必要が出てくるので）本質的には銀の弾丸にはならないと言わなければなりません（関数プログラミングで書けるということの恩恵はもちろんあるとしても）。
いや、まだ何者でもないし、僕の名前なんて誰も知らないだろうというか個人的には一生裏方のエンジニアで十分と思っているのだけど（だから匿名）、ただ単にこのタイトルかっこいーなーと思っただけだ。あと匿名である以上、この内容を信じるも信じないも読者の自由だ。
サンフランシスコベイエリアに来て2年半。まだそれだけしか経ってないのか。ずいぶん長い時間が経っているような気がする。普段のこちらの会社は事業売却でレイオフしたり転職したりパフォーマンス不足でクビになったりしない限りは至って毎日同じような天気で同じような生活リズムで働き続けているものだが、その割にずいぶんといろんなことがあった気がする。約5年勤めた巨大SIerを退職する決意をしたのがちょうど3年ほど前。いま自分がこのエリアで働いているというのが少し驚きだ。
退職するまでは仕事は忙しいながらもそれなりに充実していた。プロジェクトが変わるごとにいろんな人と出会いながらいろんなシステムを作った。出版系、公共系、銀行系、社内システム、ユーテリティ系、プロジェクト規模も数十人から数百人まで。他の会社ではなかなか出来ない経験をしていたと思う。でも、どこか自分のやりたいことと違っていて、年次が上がるごとに焦りも増しつつあった。
研究室で研究のプロトタイプのアプリケーションを書きまくっていた時は本当に楽しかった。研究の理論を考えるよりも手を動かしてコードを書いて思い通りにアプリを動かす方が楽しかった。仕事をするならプログラムを書く仕事をしたいと漠然と思っていた。それでもSIerに新卒で入社してすぐに転職しなかったのは、いろんなステークホルダーと調整して仕様を決めていったり、クライアントから隠れた要求を引き出すような仕事も実際に始めてみると楽しかったからだった。今でも自分の仕事の進め方はSIerでの5年間がベースになっているのは間違いなく、そしてそれはシリコンバレーであっても今のところ大きな武器になっていると感じる。ちなみに、SIerに入社したのは他に内定が無かったからだ。。
当時は20台後半。プログラミングを仕事にするにしても長く続けるなら将来的にはベイエリアで働くのが良かろう。ただ、いきなり現地の会社にビザサポート付きで採用してもらうのはほぼ不可能なので、語学学校→コミュニティカレッジ→インターン→現地採用というフローが遠回りながらも最も現実的なようだ。いずれにせよ、準備だけはしておかなければなるまい、ということで週末はとにかく盲目的にプログラミングの勉強を続けた。WiMaxを契約して家の近所の図書館に閉館までこもりそこが閉まるとWiFiが使えるからふね屋に移動し、という具合にラップトップを持ち運んでうろうろしていた（自宅では集中力が続かないタイプ）。iOSを触ったり、気になったオライリーの本を読んだり、蟻本を読んだりとにかく闇雲に色んな技術に触れていたが、最もよく触れていたのはJavaScriptだった気がする。仕事では業務系Webアプリケーションが多かったので、Web関連だとJavaScriptが良かろう。また「なぜ関数プログラミングは重要か」という論文をJavaScriptで写経してみて楽しかったとかそういった理由だ。当時はまさかこれほどNode.jsが使われるようになるとは思ってもみなかったし、当時読んでいた本の著者と同じ会社で働くことになるとは夢にも思わなかった。
でも、結果的にその努力が自分の身を助けることになった。偶然、ベイエリアの会社で日本人エンジニアがH1Bサポート付きのエンジニアの募集をしていたのだった。その時点では自分なんかがいきなり飛び込める世界ではないと思っていて、最初は自分のコードに何かしらアドバイスをもらえればいいと思ってメールを送ったのを覚えている。そこからダメもとで受けてみたところ、コーディングインタビューの手応えがわりと良くてオファーをもらうことができた。
その会社ではちょうど2年働かせてもらった。自分のような特にオープンソース活動もしておらず英語も上手くない日本人にチャンスを与えて本当にたくさんの経験をさせてくれ、人生でかけがえのない時間を過ごさせてもらい本当に感謝している。今は転職してそこそこ名の知れた会社でコンシューマ向けのWebサイトをJavaScriptで開発している。
こういったケースはすごい稀でたまたまめちゃくちゃ運が良くて今の自分があるんだろうけど、でも万に一つのチャンスを逃さないように努力を続けることはたぶん大事で、おそらくそれが無ければ転職することも不可能だっただろう。週末にプログラミングの勉強をするという習慣は今も続いている（むしろ東京よりも娯楽も友達も少ないこちらでは週末は他にやることがない）。勉強したいことリストの増える速度が完全に消化速度を上回っているのだけれど、何も勉強したくなくなった時がプログラミングを仕事にするのをやめるときなんだろうなと最近は思っている。
先週、KindleでWEBDBの表紙をパクったFuzoku実践入門とかいう本が話題になっていたけど、今週も同じように表紙をパクったPCでもスマホでもnasneでどこでもテレビ！とかいう本が出て、セールス上位に入ってる。
何のことか分からない人は、下記の3つを比べてみて欲しい。
フーゾクの方は、個人出版みたいだけど、ナスネの方は、インプレスだから、ちゃんとした出版社が出した本で、これはちょっと酷いんじゃないの？
で、俺は思ったんだけど、インプレスの中の人が、フーゾクの方を試しに個人で出して実験してみたところ、技評に怒られなかったから、出版社名義でもゴーサインを出したんじゃないかと睨んでいる。
なんだか話題になってるから書く。
やっと初心者を脱して中級者になりかけてるプログラミング学習者が関数型言語に何を感じているかを書こうと思う。
Haskellが短いコードでプログラムを書けるというのは分かる。
それでやりたい処理のほぼ全てがまかなえるということも実感している。
副作用のない小さな関数を合成して大きな関数を作る利点も分かる。
再利用性も上がるし、どこからどう影響を受けているかが簡単に分かるからバグも出にくい。
ただ、Haskellの基礎になってる圏論が何の役に立つのかは、まったく分からない。
むしろ邪魔なんじゃないかと思う。
ファンクターやモナドの概念が圏論で扱われているのは分かるけど、圏論なんて名前だけ知ってればコードを書くのに不都合はないだろう。
圏論が必要なのは、Haskellを設計する人であって、使う人ではないと思う。
なのに、やれクライスリ圏だ自己関手の圏だのと、うるさいったらありゃしない。
Linux上で開発環境整えるのにカーネルのコードを読めって言うぐらい的外れだと思う。
いや、知識として持っとくのはいいだろうけど、役に立たんだろ。
Rubyが羊の皮をかぶったLispとはよく言われることだけど、関数型言語もオブジェクト指向言語とそこまで違いがあるような気がしない。
純粋な言語ではできないけど、クロージャに内部状態を保持してもらって無名オブジェクトみたいな使い方をすることはあると思う。
その無名オブジェクトにもっとあれこれデータや関数詰め込めば、いつの間にか普通にJavaやC#で使うようなクラスのできあがり。
その間はなめらかにつながっていて、不連続に切れるようなもんじゃない。
関数プログラミングと言いつつ、オブジェクト指向の考え方は利用できる。
上級者はデザインパターンをdisるのが好きかもしれないけど、逆の考え方をするべきだと思う。
デザインパターンはオブジェクト指向言語の欠点を補うための苦肉の策じゃないよ。
関数プログラミングの基礎的なパーツだと思う。
だからちょっと見た目がすっきりするだけで、結局やることはオブジェクトプログラミングと変わりはないと思う。
関数プログラミングコミュニティの人って、業務でクソコードメンテさせられて、その現実逃避に美しいコードに擦り寄っているように見える。
もちろん、美しいコードを書けるなら書いた方がいいし、現代的な言語を使えるなら使ったほうがいいと思う。
けど、適材適所というか、オブジェクト指向言語でも、やってやれないことはないわけで。
役に立たない圏論をありがたがる所とか、どうもイキがってるように見える。
せいぜい生産性が倍になる程度で、他の要素が悪ければ帳消しになるような利点でしかないに違いないのに。
第1章 有限オートマトン D.Perrin：橋口攻三郎 1. 序論 2. 有限オートマトンと認識可能集合 3. 有理表現 4. Kleeneの定理 5. 星の高さ 6. 星自由集合 7. 特殊なオートマトン 8. 数の認識可能集合 第2章 文脈自由言語 J.Berstel and L.Boasson：富田 悦次 1. 序論 2. 言語 2.1 記法と例 2.2 Hotz 群 2.3 曖昧性と超越性 3. 反復 3.1 反復補題 3.2 交換補題 3.3 退化 4. 非生成元の探求 4.1 準備 4.2 生成元 4.3 非生成元と代入 4.4 非生成元と決定性 4.5 主錐の共通部分 5. 文脈自由群 5.1 文脈自由群 5.2 Cayleyグラフ 5.3 終端 第3章 形式言語とべき級数 A.Salomaa：河原 康雄 1. 序論 2. 準備 3. 書換え系と文法 4. Post正準系 5. Markov系 6. 並列書換え系 7. 射と言語 8. 有理べき級数 9. 代数的べき級数 10. べき級数の応用 第4章 無限の対象上のオートマトン W.Thomas：山崎 秀記 序論 Ⅰ部 無限語上のオートマトン 記法 1. Buchiオートマトン 2. 合同関係と補集合演算 3. 列計算 4. 決定性とMcNaughtonの定理 5. 受理条件とBorelクラス 6. スター自由ω言語と時制論理 7. 文脈自由ω言語 Ⅱ部 無限木上のオートマトン 記法 8. 木オートマトン 9. 空問題と正則木 10. 補集合演算とゲームの決定性 11. 木の単項理論と決定問題 12. Rabin認識可能な集合の分類 12.1 制限された単項2階論理 12.2 Rabin木オートマトンにおける制限 12.3 不動点計算 第5章 グラフ書換え：代数的・論理的アプローチ B.Courcelle：會澤 邦夫 1. 序論 2. 論理言語とグラフの性質 2.1 単純有向グラフの類S 2.2 グラフの類D(A) 2.3 グラフの性質 2.4 1階のグラフの性質 2.5 単項2階のグラフの性質 2.6 2階のグラフの性質 2.7 定理 3. グラフ演算とグラフの表現 3.1 源点付きグラフ 3.2 源点付き超グラフ 3.3 超グラフ上の演算 3.4 超グラフの幅 3.5 導来演算 3.6 超辺置換 3.7 圏における書換え規則 3.8 超グラフ書換え規則 4. 超グラフの文脈自由集合 4.1 超辺置換文法 4.2 HR文法に伴う正規木文法 4.3 超グラフの等式集合 4.4 超グラフの文脈自由集合の性質 5. 超グラフの文脈自由集合の論理的性質 5.1 述語の帰納的集合 5.2 論理構造としての超グラフ 5.3 有限超グラフの可認識集合 6. 禁止小グラフで定義される有限グラフの集合 6.1 小グラフ包含 6.2 木幅と木分解 6.3 比較図 7. 計算量の問題 8. 無限超グラフ 8.1 無限超グラフ表現 8.2 無限超グラフの単項性質 8.3 超グラフにおける等式系 8.4 関手の初期不動点 8.5 超グラフにおける等式系の初期解 8.6 等式的超グラフの単項性質 第6章 書換え系 N.Dershowitz and J.-P.Jouannaud：稲垣 康善，直井 徹 1. 序論 2. 構文論 2.1 項 2.2 等式 2.3 書換え規則 2.4 決定手続き 2.5 書換え系の拡張 3. 意味論 3.1 代数 3.2 始代数 3.3 計算可能代数 4. Church-Rosser性 4.1 合流性 4.2 調和性 5. 停止性 5.1 簡約順序 5.2 単純化順序 5.3 経路順序 5.4 書換え系の組合せ 6. 充足可能性 6.1 構文論的単一化 6.2 意味論的単一化 6.3 ナローイング 7. 危険対 7.1 項書換え 7.2 直交書換え系 7.3 類書換え 7.4 順序付き書換え 7.5 既約な書換え系 8. 完備化 8.1 抽象完備化 8.2 公平性 8.3 完備化の拡張 8.4 順序付き書換え 8.5 機能的定理証明 8.6 1階述語論理の定理証明 9. 書換え概念の拡張 9.1 順序ソート書換え 9.2 条件付き書換え 9.3 優先度付き書換え 9.4 グラフ書換え 第7章 関数型プログラミングとラムダ計算 H.P.Barendregt：横内 寛文 1. 関数型計算モデル 2. ラムダ計算 2.1 変換 2.2 計算可能関数の表現 3. 意味論 3.1 操作的意味論：簡約と戦略 3.2 表示的意味論：ラムダモデル 4. 言語の拡張 4.1 デルタ規則 4.2 型 5. 組合せ子論理と実装手法 5.1 組合せ子論理 5.2 実装の問題 第8章 プログラミング言語における型理論 J.C.Mitchell：林 晋 1. 序論 1.1 概論 1.2 純粋および応用ラムダ計算 2. 関数の型をもつ型付きラムダ計算 2.1 型 2.2 項 2.3 証明系 2.4 意味論と健全性 2.5 再帰的関数論的モデル 2.6 領域理論的モデル 2.7 カルテシアン閉圏 2.8 Kripkeラムダモデル 3. 論理的関係 3.1 はじめに 3.2 作用的構造上の論理的関係 3.3 論理的部分関数と論理的同値関係 3.4 証明論的応用 3.5 表現独立性 3.6 論理的関係の変種 4. 多相型入門 4.1 引数としての型 4.2 可述的な多相的計算系 4.3 非可述的な多相型 4.4 データ抽象と存在型 4.5 型推論入門 4.6 型変数をもつλ→の型推論 4.7 多相的宣言の型推論 4.8 他の型概念 第9章 帰納的な関数型プログラム図式 B.Courcelle：深澤 良彰 1. 序論 2. 準備としての例 3. 基本的な定義 3.1 多ソート代数 3.2 帰納的な関数型プログラム図式 3.3 同値な図式 4. 離散的解釈における操作的意味論 4.1 部分関数と平板な半順序 4.2 離散的解釈 4.3 書換えによる評価 4.4 意味写像 4.5 計算規則 5. 連続的解釈における操作的意味論 5.1 連続代数としての解釈 5.2 有限の極大要素と停止した計算 6. 解釈のクラス 6.1 汎用の解釈 6.2 代表解釈 6.3 解釈の方程式的クラス 6.4 解釈の代数的クラス 7. 最小不動点意味論 7.1 最小で唯一の解を得る不動点理論 7.2 Scottの帰納原理 7.3 Kleeneの列と打切り帰納法 8. プログラム図式の変換 8.1 プログラム図式における同値性の推論 8.2 畳込み，展開，書換え 8.3 制限された畳込み展開 9. 研究の歴史，他の形式のプログラム図式，文献ガイド 9.1 流れ図 9.2 固定された条件をもつ一様な帰納的関数型プログラム図式 9.3 多様な帰納的関数型プログラム図式 9.4 代数的理論 9.5 プログラムの生成と検証に対する応用 第10章 論理プログラミング K.R.Apt：筧 捷彦 1. 序論 1.1 背景 1.2 論文の構成 2. 構文と証明論 2.1 1階言語 2.2 論理プログラム 2.3 代入 2.4 単一化子 2.5 計算過程―SLD溶融 2.6 例 2.7 SLD導出の特性 2.8 反駁手続き―SLD木 3. 意味論 3.1 1階論理の意味論 3.2 SLD溶融の安全性 3.3 Herbrand模型 3.4 直接帰結演算子 3.5 演算子とその不動点 3.6 最小Herbrand模型 3.7 SLD溶融の完全性 3.8 正解代入 3.9 SLD溶融の強安全性 3.10 手続き的解釈と宣言的解釈 4. 計算力 4.1 計算力と定義力 4.2 ULの枚挙可能性 4.3 帰納的関数 4.4 帰納的関数の計算力 4.5 TFの閉包順序数 5. 否定情報 5.1 非単調推論 5.2 閉世界仮説 5.3 失敗即否定規則 5.4 有限的失敗の特徴付け 5.5 プログラムの完備化 5.6 完備化の模型 5.7 失敗即否定規則の安全性 5.8 失敗即否定規則の完全性 5.9 等号公理と恒等 5.10 まとめ 6. 一般目標 6.1 SLDNF-溶融 6.2 SLDNF-導出の安全性 6.3 はまり 6.4 SLDNF-溶融の限定的な完全性 6.5 許容性 7. 層状プログラム 7.1 準備 7.2 層別 7.3 非単調演算子とその不動点 7.4 層状プログラムの意味論 7.5 完全模型意味論 8. 関連事項 8.1 一般プログラム 8.2 他の方法 8.3 演繹的データベース 8.4 PROLOG 8.5 論理プログラミングと関数プログラミングの統合 8.6 人工知能への応用 第11章 表示的意味論 P.D.Mosses：山田 眞市 1. 序論 2. 構文論 2.1 具象構文論 2.2 抽象構文 2.3 文脈依存構文 3. 意味論 3.1 表示的意味論 3.2 意味関数 3.3 記法の慣例 4. 領域 4.1 領域の構造 4.2 領域の記法 4.3 記法上の約束事 5. 意味の記述法 5.1 リテラル 5.2 式 5.3 定数宣言 5.4 関数の抽象 5.5 変数宣言 5.6 文 5.7 手続き抽象 5.8 プログラム 5.9 非決定性 5.10 並行性 6. 文献ノート 6.1 発展 6.2 解説 6.3 変形 第12章 意味領域 C.A.Gunter and D.S.Scott：山田 眞市 1. 序論 2. 関数の帰納的定義 2.1 cpoと不動点定理 2.2 不動点定理の応用 2.3 一様性 3. エフェクティブに表現した領域 3.1 正規部分posetと射影 3.2 エフェクティブに表現した領域 4. 作用素と関数 4.1 積 4.2 Churchのラムダ記法 4.3 破砕積 4.4 和と引上げ 4.5 同形と閉包性 5. べき領域 5.1 直観的説明 5.2 形式的定義 5.3 普遍性と閉包性 6. 双有限領域 6.1 Poltkin順序 6.2 閉包性 7. 領域の帰納的定義 7.1 閉包を使う領域方程式の解法 7.2 無型ラムダ記法のモデル 7.3 射影を使う領域方程式の解法 7.4 双有限領域上の作用素の表現 第13章 代数的仕様 M.Wirsing：稲垣 康善，坂部 俊樹 1. 序論 2. 抽象データ型 2.1 シグニチャと項 2.2 代数と計算構造 2.3 抽象データ型 2.4 抽象データ型の計算可能性 3. 代数的仕様 3.1 論理式と理論 3.2 代数的仕様とその意味論 3.3 他の意味論的理解 4. 単純仕様 4.1 束と存在定理 4.2 単純仕様の表現能力 5. 隠蔽関数と構成子をもつ仕様 5.1 構文と意味論 5.2 束と存在定理 5.3 隠蔽記号と構成子をもつ仕様の表現能力 5.4 階層的仕様 6. 構造化仕様 6.1 構造化仕様の意味論 6.2 隠蔽関数のない構造化仕様 6.3 構成演算 6.4 拡張 6.5 観測的抽象化 6.6 構造化仕様の代数 7. パラメータ化仕様 7.1 型付きラムダ計算によるアプローチ 7.2 プッシュアウトアプローチ 8. 実現 8.1 詳細化による実現 8.2 他の実現概念 8.3 パラメータ化された構成子実現と抽象化子実現 8.4 実行可能仕様 9. 仕様記述言語 9.1 CLEAR 9.2 OBJ2 9.3 ASL 9.4 Larch 9.5 その他の仕様記述言語 第14章 プログラムの論理 D.Kozen and J.Tiuryn：西村 泰一，近藤 通朗 1. 序論 1.1 状態，入出力関係，軌跡 1.2 外的論理，内的論理 1.3 歴史ノート 2. 命題動的論理 2.1 基本的定義 2.2 PDLに対する演繹体系 2.3 基本的性質 2.4 有限モデル特性 2.5 演繹的完全性 2.6 PDLの充足可能性問題の計算量 2.7 PDLの変形種 3. 1階の動的論理 3.1 構文論 3.2 意味論 3.3 計算量 3.4 演繹体系 3.5 表現力 3.6 操作的vs.公理的意味論 3.7 他のプログラミング言語 4. 他のアプローチ 4.1 超準動的論理 4.2 アルゴリズム的論理 4.3 有効的定義の論理 4.4 時制論理 第15章 プログラム証明のための手法と論理 P.Cousot：細野 千春，富田 康治 1. 序論 1.1 Hoareの萌芽的な論文の解説 1.2 C.A.R.HoareによるHoare論理のその後の研究 1.3 プログラムに関する推論を行うための手法に関するC.A.R.Hoareによるその後の研究 1.4 Hoare論理の概観 1.5 要約 1.6 この概観を読むためのヒント 2. 論理的，集合論的，順序論的記法 3. プログラミング言語の構文論と意味論 3.1 構文論 3.2 操作的意味論 3.3 関係的意味論 4. 命令の部分正当性 5. Floyd-Naurの部分正当性証明手法とその同値な変形 5.1 Floyd-Naurの手法による部分正当性の証明の例 5.2 段階的なFloyd-Naurの部分正当性証明手法 5.3 合成的なFloyd-Naurの部分正当性証明手法 5.4 Floyd-Naurの部分正当性の段階的な証明と合成的な証明の同値性 5.5 Floyd-Naurの部分正当性証明手法の変形 6. ライブネスの証明手法 6.1 実行トレース 6.2 全正当性 6.3 整礎関係，整列集合，順序数 6.4 Floydの整礎集合法による停止性の証明 6.5 ライブネス 6.6 Floydの全正当性の証明手法からライブネスへの一般化 6.7 Burstallの全正当性証明手法とその一般化 7. Hoare論理 7.1 意味論的な観点から見たHoare論理 7.2 構文論的な観点から見たHoare論理 7.3 Hoare論理の意味論 7.4 構文論と意味論の間の関係：Hoare論理の健全性と完全性の問題 8. Hoare論理の補足 8.1 データ構造 8.2 手続き 8.3 未定義 8.4 別名と副作用 8.5 ブロック構造の局所変数 8.6 goto文 8.7 （副作用のある）関数と式 8.8 コルーチン 8.9 並行プログラム 8.10 全正当性 8.11 プログラム検証の例 8.12 プログラムに対して1階論理を拡張した他の論理 第16章 様相論理と時間論理 E.A.Emerson：志村 立矢 1. 序論 2. 時間論理の分類 2.1 命題論理 対 1階述語論理 2.2 大域的と合成的 2.3 分岐的 対 線形 2.4 時点と時区間 2.5 離散 対 連続 2.6 過去時制 対 未来時制 3. 線形時間論理の技術的基礎 3.1 タイムライン 3.2 命題線形時間論理 3.3 1階の線形時間論理 4. 分岐的時間論理の技術的基礎 4.1 樹状構造 4.2 命題分岐的時間論理 4.3 1階の分岐的時間論理 5. 並行計算：その基礎 5.1 非決定性と公平性による並列性のモデル化 5.2 並列計算の抽象モデル 5.3 並列計算の具体的なモデル 5.4 並列計算の枠組みと時間論理の結び付き 6. 理論的見地からの時間論理 6.1 表現可能性 6.2 命題時間論理の決定手続き 6.3 演繹体系 6.4 モデル性の判定 6.5 無限の対象の上のオートマトン 7. 時間論理のプログラムの検証への応用 7.1 並行プログラムの正当性に関する性質 7.2 並行プログラムの検証：証明論的方法 7.3 時間論理による仕様からの並行プログラムの機械合成 7.4 有限状態並行システムの自動検証 8. 計算機科学における他の様相論理と時間論理 8.1 古典様相論理 8.2 命題動的論理 8.3 確率論理 8.4 不動点論理 8.5 知識 第17章 関係データベース理論の構成要素 P.C.Kanellakis：鈴木 晋 1. 序論 1.1 動機と歴史 1.2 内容についての案内 2. 関係データモデル 2.1 関係代数と関係従属性 2.2 なぜ関係代数か 2.3 なぜ関係従属性か 2.4 超グラフとデータベーススキーマの構文について 2.5 論理とデータベースの意味について 3. 従属性とデータベーススキーマ設計 3.1 従属性の分類 3.2 データベーススキーマ設計 4. 問合わせデータベース論理プログラム 4.1 問合わせの分類 4.2 データベース論理プログラム 4.3 問合わせ言語と複合オブジェクトデータモデル 5. 議論：関係データベース理論のその他の話題 5.1 不完全情報の問題 5.2 データベース更新の問題 6. 結論 第18章 分散計算：モデルと手法 L.Lamport and N.Lynch：山下 雅史 1. 分散計算とは何か 2. 分散システムのモデル 2.1 メッセージ伝達モデル 2.2 それ以外のモデル 2.3 基礎的概念 3. 分散アルゴリズムの理解 3.1 挙動の集合としてのシステム 3.2 安全性と活性 3.3 システムの記述 3.4 主張に基づく理解 3.5 アルゴリズムの導出 3.6 仕様記述 4. 典型的な分散アルゴリズム 4.1 共有変数アルゴリズム 4.2 分散合意 4.3 ネットワークアルゴリズム 4.4 データベースにおける並行性制御 第19章 並行プロセスの操作的および代数的意味論 R.Milner：稲垣 康善，結縁 祥治 1. 序論 2. 基本言語 2.1 構文および記法 2.2 操作的意味論 2.3 導出木と遷移グラフ 2.4 ソート 2.5 フローグラフ 2.6 拡張言語 2.7 その他の動作式の構成 3. プロセスの強合同関係 3.1 議論 3.2 強双模倣関係 3.3 等式による強合同関係の性質 3.4 強合同関係における置換え可能性 3.5 強等価関係上での不動点の唯一性 4. プロセスの観測合同関係 4.1 観測等価性 4.2 双模倣関係 4.3 観測合同関係 4.4 プロセス等価性上での不動点の唯一性 4.5 等式規則の完全性 4.6 プロセスの等価性に対するその他の概念 5. 双模倣等価関係の解析 5.1 等価性の階層構造 5.2 階層構造の論理的特性化 6. 合流性をもつプロセス 6.1 決定性 6.2 合流性 6.3 合流性を保存する構成子 7. 関連する重要な文献
いくつか考えてみた
(問1)高階関数と再帰関数を必ず使って数値を要素とするリストの要素の総和を求める関数を書け。ただし高階関数を使うという要件と再帰関数を使うという要件は同じ関数で満たしてもよい。
(問2)二つの引数をとり二つのうち大きいほうを返す関数と高階関数、再帰関数をつかって数値のリストの最大値を求める関数を書け。ただし高階関数を使うという要件と再帰関数を使うという要件は同じ関数で満たしてもよい。
というのは簡単すぎるか？簡単すぎるなら
(問3)高階関数と再帰関数を必ず使ってある数値に5を足し、10かけて2で割った数を求める関数を書け。ただし高階関数を使うという要件と再帰関数を使うという要件は同じ関数で満たしてもよい。
こっちの方がいいかな。でもトリッキーすぎる気もする。
一応問題を出したので、SchemeとPythonで自分で想定している答えを書いておいた。はてなではSchemeが人気のようなので、あまり知らなかったけど関数言語ではSchemeで書いておいた。Pythonで書くのはSchemeだけだとわかりにくいので、なにかスクリプト言語で書いておこうと思ったから。Rubyの方が人気なので、はじめはRubyで書こうと思ったけど挫折した。だれかRubyで書いてくれないかな・・・。コードオブジェクトってなによ。というか関数はオブジェクトなのに引数にできないの？なんで？（以下疑問と愚痴の嵐なので略）Perlは古株が多くてユーザー数も多そうだけど、・・・その・・・無理です・・・。あの言語仕様はやる気がしない。ぶっちゃけ理解できない。Pythonを知らないひとは多そうだけど、知らなくてもSchemeよりは感じは掴めると思うのでPythonでも書いておくことにした。
http://anond.hatelabo.jp/20071110215936
http://anond.hatelabo.jp/20071110220132
これで大部分のひとがこの問題に興味をもたなくて解答するひとがいなくても、興味を持ったひとは安心だね！
追記：
問3で次のは無しとしておきたい。
(define continuous-apply
(lambda (lst obj)
(cond
((null? lst)
obj)
(else
(continuous-apply (cdr lst) ((car lst) obj))))))
(define plus5
(lambda (num)
(+ num 5)))
(define times10
(lambda (num)
(* num 10)))
(define divide2
(lambda (num)
(/ num 2)))
(define plus5-times10-divide2
(lambda (num)
(continuous-apply (list plus5 times10 divide2) num)))
(plus5-times10-divide2 2)
def continuousApply(lst, obj): if lst: return continuousApply(lst[1:], lst[0](obj)) else: return obj def plus5(num): return num + 5 def times10(num): return num * 10 def divide2(num): return num / 2 def plus5_times10_divide2(num): return continuousApply([plus5, times10, divide2], 2) plus5_times10_divide2(2)
あくまで自分でこう答えるという話。
(問1)
(define fold-left
(lambda (func obj lst)
(cond
((null? lst)
obj)
(else
(fold-left func (func obj (car lst)) (cdr lst))))))
(define my-sum
(lambda (lst)
(fold-left + (car lst) (cdr lst))))
・例
(my-sum '(1 2 3 4 5 6 7 8 9 10))
(問2)
(define fold-left
(lambda (func obj lst)
(cond
((null? lst)
obj)
(else
(fold-left func (func obj (car lst)) (cdr lst))))))
(define large
(lambda (x y)
(cond
((>= x y)
x)
(else
y))))
(define my-max
(lambda (lst)
(fold-left large (car lst) (cdr lst))))
・例
(my-max '(58 90 1 2 4 3 100))
(問3)
(define fold-right
(lambda (func lst obj)
(cond
((null? lst)
obj)
(else
(func (car lst) (fold-right func (cdr lst) obj))))))
(define my-apply
(lambda (func obj)
(func obj)))
(define plus5
(lambda (num)
(+ num 5)))
(define times10
(lambda (num)
(* num 10)))
(define divide2
(lambda (num)
(/ num 2)))
(define plus5-times10-divide2
(lambda (num)
(let ((lst (list plus5 times10 divide2)))
(fold-right my-apply (reverse lst) num))))
・例
(plus5-times10-divide2 5)
全部畳み込み関数を使っているのは、はじめ使い道がないと思ってたのにかなり使い道があることがわかったので、それを示したかったから。あとmap関数あたりはほかの言語でもあるから、すぐに思いつくだろうし。
というか最後のやつは手続きを抽象化することでリストの形で扱えるようにしているから、関数プログラミングでは重要だと思う。関数プログラミングの肝は計算によって手続きを含めたすべて表すことができることだと思っている。その例だと思うんだけどね。例えばSchemeなら上記の答えを応用して、似たような「手続き」を生み出す関数を作ることができる。
(define make-proceduce (lambda (fst . rest) (let ((lst (cons fst rest))) (lambda (num) (fold-right my-apply (reverse lst) num)))))
これを使うと次のようにできる。
(define divide2-plus5-times10
(make-proceduce divide2 plus5 times10))
(divide2-plus5-times10 2)
(define divide2-times10-plus5
(make-proceduce divide2 times10 plus5))
(divide2-times10-plus5 2)
関数合成がつかえるならそっちのほうが楽だけど、リストという形で「手続き」をつくり出していることがわかるだろうか？手続きをリストで操作できるのだ。こういうのが関数プログラミングの肝だと勝手に思っている。
こうやってくると型推論や多相型の重要性もわかると思うんだよ。上記のようなことはPythonでもできる。でも高階関数はつかいすぎるとわかりにくい。どっかにバグが入ってくるかもしれない。それを機械的に防ぐのが型推論。型という観点から型推論でおかしいところを探し出してくれる。それならC言語でもいいのではないかという人もいるかもしれない。だがC言語は融通が利かない。例えばapply関数にしても引数の型が数値なら数値、文字なら文字と決まっている必要がある。だから数値に向けにapply関数を作っても文字には使えない。こうした型のデメリットをなくす一方、そのメリットを享受するためにあるのが多相型。これによってapply関数やmap関数を一般的に作ることができ、型のメリットを享受しながらデメリットをなくすことができる。このように関数で手続きなんかを抽象化するときに型推論や多相型があると便利なのだ。
http://anond.hatelabo.jp/20071021143442
その理由は知らないが、なければ作ればいいじゃないか。
class MyString(str): def length(self): return len(self)
というクラスを作って
string = MyString("Hello world") print string.count("o"), string.length()
とRubyライクにやれば
2 11
とでるよ。え、リストもlist.length()が使いたいって？それも簡単。
class MyList(list): def length(self): return len(self) l = MyList([1, 2, 3, 4, 5, 6]) l.length()
6
きちんと他のメソッドも使えるよ。
l[1:]
[2, 3, 4, 5, 6]
l.reverse() l
[6, 5, 4, 3, 2, 1]
ね。簡単でしょ。
Pythonは仕組みが統一されているものが多いので、いじりやすいのですよ。上の例のやつは組み込みのクラスオブジェクトとユーザー定義のクラスオブジェクトがおおむね統一されているからこそ簡単にできる。他にも関数なんかもほかのオブジェクトと同じオブジェクトなので、高階関数なんてもの簡単に作ることができて関数プログラミングぽくできる。例えば今はなきapply関数なんかは
def myApply(func, *args): return func.__call__(*args)
と定義できる。実際に
def sumUpThree(num1, num2, num3): return num1 + num2 + num3
でためしてみる。
myApply(sumUpThree, 1, 2, 3)
結果はちゃんと
6
とでる。将来廃止されそうなmap関数も簡単に定義できる。他にも複数の引数をもつ関数の部分適用のようなことを行う関数も次のように簡単に定義できる。
def partial(func, *oldArgs): def wrapper(*newArgs): return func.__call__(*(oldArgs + newArgs)) return wrapper
sum_1 = partial(sumUpThree, 1) sum_1(2, 3)
6
sum_1_5 = partial(sum_1, 5) sum_1_5(9)
15
sum_10_20 = partial(sumUpThree, 10, 20) sum_10_20(30)
60
こういう風に高階関数が簡単にできるのは関数がオブジェクトで関数の実行とはメソッドの呼び出しにすぎないからだ。以上のように組み込みオブジェクトとユーザー定義オブジェクトの差があまりないことや関数もオブジェクトであることに見られるようにPythonは仕組みが統一されていてシンプルだ。そのためひとつのことがわかれば他のこともわかることが多いし、簡単にいじることもできる。
だからなければpythonをいじればいいと思うよ。
最後にラムダ式信者のためにpartialをラムダ式を使って書いておく。
def partial(func, *oldArgs): return lambda *newArgs:func.__call__(*(oldArgs + newArgs))