Pixel Pedals of Tomakomai

北海道苫小牧市出身の初老の日常

函数プログラミングで集いに来ました

函数プログラミングの集い 2011 in Tokyo に来てます。途中退出しますが、居る間内容を適当にメモります。会場はIIJさんです。毎度のことながらすばらしい会場。

この会は、神田でICFPという大きな国際的な学会が日本で行われるのにちなんでいるそうです。普段は「この言語は糞だ」みたいなことを言っている方も今日は休戦でお願いしますとのこと。

ハッシュタグ#fpm2011 です。ustreamこちら

関数プログラミングの道しるべ / @kazu_yamamoto さん

  • 今日は時間が短いので、今日の内容を理解してもらえるとは微塵も思ってない
    • 入り口で引き返さずに、山へ登ってみて欲しいという思い
  • Twitter での市場調査 → 関数 = 数学 = 怖い。関数 = アカデミック = 役に立たない
    • Functional の訳を「実用的」とすべき。Functional Programing = 実用的プログラミング
  • 「関数型」の定義はあいまい。みんなが色んな要素のサブセットを勝手に関数型と呼んでいる
    • 議論の前には擦り合わせをしないと喧嘩になるよ
  • プログラミングHaskell での定義
    • 関数を適用することを主眼とする
    • 関数型の手法を提供するだけでなく「奨励」
  • パラダイムの違い
    • 関数適用、状態はない、破壊的代入をしない
    • 永続データを使ったプログラミング
  • 例: [10, 20, 30, 40, 50] のリストをn番目はn倍して加える
    • 命令型のパラダイムでは、for を使う
    • 関数型だとMapReduce → zip, map, foldl。データを変形して行く。データーフローモデルと呼ばれる
  • 昔for を愛していた。for で1時間は語れる → 「非対称範囲(n <= x < m)を使え」など
  • 関数プログラミングではバグの入り込まないような小さな部品を使う
  • リストの三種の神器
    • car, cdr, cons (Haskell では head, tail, :)
    • LISPの本では、これらの重要な意味が語られていないため、つまらないのではないか
    • 配列は永続データではない。リストは永続データとして使える
    • リストの先頭にデータを追加しても、データを永続させつつ再利用できる
    • パターンマッチがあるHaskellでは、[] と x:xs を使うことが多い
  • リストを連結(++)すると、左側はコピーされる(永続化のため)
    • ++ はなるべく使わない
    • ++ を使うなら右結合で使う (右結合だとO(N)、左結合だとO(N^2))
  • 関数プログラミングはリストプログラミング。ここはつまらないけど乗り越えて
  • 再帰 → 基底部で終了、再帰部で仕事をさせる
    • 「1つ前ができていたら、次はどうする?」を考えれば書ける
  • なぜ再帰がいいのか → 再帰は式なので、型検査の恩恵を受けられる
  • リストの生成 : 末尾でない再帰で書く
    • 遅延評価と相性がよい。正格評価の言語はdelayとforceを使う
  • 数値の生成 : 末尾再帰で書く
    • sum (x:xs) = (+) x (sum xs) は末尾再帰でない(右辺の一番最後の関数は(+) )
    • sum' r (y:ys) = sum' (y+r) ys は末尾再帰 (rは蓄積変数)
    • 末尾再帰はgotoになるのでスタックは溢れない
  • Q. for ループだとなんで型チェックの恩恵を受けられない?
  • A. スタートHaskell の議論を参照!
  • Q. Haskell の sum のデフォルトの実装が末尾再帰してないのはなぜ?
  • A. 知らない。foldl'を使うといいんだけど、なぜか使ってない
  • foldr と foldl
    • foldr は末尾再気にならない。リストを生成する関数と相性がよい
    • foldl は末尾再帰。数値を生成する関数と相性がよい
  • map、filter は再帰でも foldr でも書ける
  • 自由度 : 再帰>畳み込み>単純な高階関数
    • なるべく自由度の弱い物を使う
    • 例: sumEven は再帰より map + filter を使った方がわかりやすい
    • 「(再帰で)考えるな! (MapReduceを)感じろ!」
  • Q. 効率を考えても自由度が弱い物がよいの?
  • A. YES
  • 文字列 → 文字のリスト
    • メールヘッダのパーサ → Haskellのbreak, dropWhile, foldr を使うと書ける
    • 最長重複文字列を探す → suffixリスト
  • suffix リストは全要素で文字列を共有するため、効率がよく非常に相性がよい
  • 複雑な文字列操作にはパーサを書く。正規表現は忘れよう
  • 二分木 → なんでもリストで解決しようとしない
    • 永続化により、効率的に共有できる
    • 10000ノードの気に要素を追加する場合、約13ノードの追加で済む
    • 走査も再帰と(++)で簡単に書ける → (++) 使わずにも書ける
    • 用途 → 探索木(八種テーブルの代わり)、集合、キュー、巨大な文字列走査(O(log n)でできる)
  • 永続データプログラミングの弱点
    • 配列と相性が悪く、O(1)の連想配列がない
    • 簡約λカ娘参照
  • コンビネータとは、「すてきな内部DSL
    1. まずデータ型を定義
    2. データを返す小さな関数を作る
    3. 上項を組み合わせる関数を書く (これをコンビネータと呼ぶ)
  • コンビネータ : パサー、プリティプリンタ、ハードウェア記述、金融商品記述
  • さらに勉強するための書籍・記事の紹介
  • 質疑応答
    • Q. Lazyな言語にCLEANもあります
    • Q. ループを再帰にする方針はありますか?
    • A. ループで書けるならループでいいんじゃない? 何も考えずには無理では? 自転車に乗るのと一緒で、少し修行が必要。パターンは少ないのですぐ覚えられる
    • Q. ループは末尾再帰に単純にできるのでは?
    • A. はい。

モナドについて / @tanakh さん

  • モナドとは何か?
    • 非常に難しい質問。数多くの人が答えているが、全然違う主張をしている
    • 例 : Monads are Elephants
    • 例 : モナドはメタファーではない
    • 例 : プログラマブル・コンテナ
    • 例 : モナドのすべて 「コンベアのアナロジー」
    • ゼノブレイドをやると理解できる
  • モナドへの疑問
    • なに? 役に立つ? なぜモナド(他じゃ駄目?)?
  • モナドパラダイム
    • 手続き型の中の「モナディック」という1パラダイムではないか
    • Programmable semicolon
    • 構造化定理 : 順次、反復、分岐によって全てのプログラムが書ける → モナドマッピングされる
  • 何が嬉しい? → 順次、反復、分岐 のセマンティクスの書き換え
    • ; に意味を持たせたのが >>
    • continuation の一般化とも考えられる
    • 普通のプログラムが、「非決定計算」「エラーハンドリング」「暗黙の状態を含む処理」に変わる → コンテキストが変わる
  • それぞれのコンテキストにあうプログラムを書けばいいんじゃない?
    • 抽象化したい。コード偏の共通化
  • 例: N-クイーン問題
    • Int を受け取り、「解」を返す
    • 解を表すモナドを m で書くことで、解の実装を抽象化できる
  • なぜモナドなのか? → 構造化定理に必要な要素を自然に記述できる。簡潔。
  • Haskell でのモナド (>>=) と return
  • モナド則 → 単位元結合則。ただし、プログラマが保証しないと処理系は何もしてくれない
    • (a >> b) >> c と a >> (b >> c) が同じになるために必要
  • do記法 → 糖衣構文。あたかも手続き型のように見える
  • 組み込みのモナド → リスト、Maybe、Eigher、IO
  • リストモナド → 非決定計算のコンテクスト
  • Maybeモナド → 失敗するかもしれない計算
  • IOモナドモナドはIOのためにあるのではない。コンテキストの一種。
  • モナド変換子
    • 例: 失敗するかもしれないIO計算
    • 例: エラーハンドリングできるパーザー
  • MTL → Monad Transformer Library。モナド変換子を含む
    • Monad.Cont, Reader, Writer, State, List, Error
    • 例: StateT s IO a → IOモナドの走査とStateモナドの操作が両方できる
    • liftIO をしてIO 操作をする
  • moge = liftIO $ print "HOGE=" にたいして、どんな型をつけると一般的に使えるの?
    • MonadIOクラスを使う。liftIOを抽象化したもの
    • そして、StateT s IO を MonadIO のインスタンスにすればよい
    • 一般の持ち上げにはMonadTrans で、liftを定義できる。内側のモナドから外側への持ち上げ
  • monad-control : liftの逆をする物が欲しい
    • IOモナドだけでなく、MonadIOにたいしても例外ハンドルしたい。catch はIO専用
    • MonadControllIO : liftControlIO が定義されている。
    • IOしかとらないインタフェースの関数に、任意のliftしたものが渡せる
  • 様々なモナディックライブラリ
    • MonadPar : 並列計算。par、seq の代わりに pval と get
    • いろいろなパーザー
    • WebApp : WAI, Yesod, Snap, CGI
    • Interpreter : hint, BASIC
  • モナドを作るときには慎重に設計する
    • 使いにくくなる。使いにくいライブラリも多い
  • 検討すべきこと
    • 既存のモナドが利用できない? mtl にあるモナドの張り合わせで実現すべき
    • モナド変換子版を必ず用意する : XxxxT という名前
    • モナド変換子版は、Identity モナドを適用したものにする
    • MonadIO のインスタンスにする → 全ての場所でIOができるようになる
    • MonadControlIOのインスタンスにする → bracket による正しい後処理
    • MonadTrans のインスタンスにする → 他のモナドから多段持ち上げのため
    • Functor, Applicative のインスタンスにする → Monadと親子関係になってないのは、歴史的理由ではないか
    • エラーハンドリングするならMonadError、失敗への代替はAlternative
  • IOモナドHaskell において外すことのできないモナド
    • まともなプログラムを書くとほとんどの関数の方がIOになる → 「IOモナドは感染する」
    • MonadIO によって解決できる。IOが必要なコンテキストだけMonadoIOを要求すればよい(PureなコードとIOのコードのオーバーロード)
  • Alternative クラス → <|>なる演算子。失敗すると次の結果を使う
    • Parsec から来ている。many, some, optional
  • -XGenericNewtypeDeriving → newtypeモナドは、deriving で済ませられる
  • 質疑応答
    • Q. MonadPlus は使わないの?
    • A. Alternative と被っている。guard を使いたいときはMonadPlus が必要なので、インスタンスにする方がいいだろう
    • Q. コンテキスト変数をhaskellはうまく実装している
    • A. そう思う。Haskellの型クラスがうまくいく理由では
    • Q. モナドクロージャーの連鎖になるのでは。実装が大変では
    • A. オーバヘッドは大きそう。ghcではインライン化を頑張っているが、モナド変換子が重なるとインライン化しきれなくなる。最近Yesod のパフォーマンスが出なかったのもそれが原因
    • Q. モナドはセミコロンの抽象化ってことは、手続き型言語でもできるのでは。いいことは?
    • A. 手続き型言語でも同等なことができるだろう。同じコードで違うコンテキストが与えられるのはいいことでは
    • A. Haskell に限って言えば、do 構文。また、モナド変換子によって組み込まれて価値が出る

ITプランニングにおける関数プログラミング / @yoshihiro503 さん

  • 静的型付関数型言語でのお仕事
  • 案件1: FXチャート
    • サーバサイドがOCaml
    • ロウソク生成 : グラフ内の長方形のこと。1分足、5分足、・・・月足、がある
    • ニューヨーク時間を使う。サマータイムの考慮等が必要
  • OCamlのよいところ
    • 実行時エラーがおきにくい(nullがない、型が強力)
    • 型チェックによる拡張
    • 副作用がなく見通しがよい
    • パフォーマンスがよい (少ないサーバで安定かどう)
  • OCamlの悪いところ
    • SQL ServerOracleとの連携のライブラリ不足 → 自作した
    • Oracle は現在はあるっぽい
  • 遅延リストにより、メモリを大量消費せず多くのデータを順次処理できる
  • 派生案件 → Javaアプレットiアプリ、ocamljsのスマフォアプリ、iPhone+Androidアプリ
  • 案件2: 名古屋大ネットワーク管理システム
    • Ruby になりそうなところを、静的型付関数型言語がいいですよ!とScala にした
    • 他社との協業
  • Scalaのよいところ
    • 型チェックにより、複数人での開発につよい
    • パーサーのコードの見通しがよい
  • Scalaの悪いとこ
    • (特に他社の)学習コスト。ドキュメント不足。
    • JavaができるならScalaできるだろ」
  • 案件3 iZE Smart Desktop
    • バイル端末にUSBを挿して端末化
    • サーバサイドとクライアント再度
    • GAEを使いたいという要求 → 自動的に COBOL
  • サーバサイドはScala
    • モナドにより、失敗するかもしれない処理を簡潔に書く (Optional??)
    • Scala では ?~ によるアノテーション(?)でエラー情報をつけられる
  • クライアントサイドは haXe + OCaml + Coq
    • haXeActionScript に似ているけど、関数型。パターンマッチとかある
  • 静的型付関数型言語の環境はたくさんある
    • 中古車相場分析 → haXe + OCaml
    • 金属工場の生産受注管理 → F#
    • Androidアプリ → Scala
    • Coqの改造 → OCaml
  • 静的型付関数型言語 でよかったこと
  • 静的型付関数型言語 での苦労
    • ドキュメント不足 (エラーメッセージが不明)
    • (枯れた)ライブラリが少ない
    • 開発環境・・・は今のとこ困ってないEmacsでいいのでは?
  • 関数型言語を使うには
    1. お客さんの信頼を得る
    2. 開発言語・環境の提案
    3. 関数型言語を使う
    4. いいものができる (最初に戻る)
  • 具体的にどうアクションをするか
    • まずは社内の小さなプロジェクトから使う
    • 同僚を巻き込む
    • 社内社外勉強会で裾野を広げる
    • 「ボクと契約して関数プログラマになってよ!」と言う
  • 質疑応答
    • Q. エラー文字列をつけるのはMaybe では無理では? 文字列以外をつけるには
    • A. Optional 型。拡張すれば可能でしょう
    • Q. JavaアプレットOCaml?
    • A. サーバサイド
    • Q. OCaml で例外をキャッチせずに終了する問題はどう対応する?
    • A. Exception は使わない。Option型等を使う。
    • Q. 関数型が狙えるような分野ってありますか?
    • A. 仕事でプログラムを書くのに、実行時エラーがあって許されるわけがない。どんな分野でも使うべき。
    • Q. 静的型付関数型言語 を使いたいから、って理由で断ったことは?
    • A. ある。PHPを使ってやって欲しい、という仕事で他の仕事が多かったため断ったことがある。(ただし、仕事がなければなんでもやるという主義だそう)

COBOL meets HaskellHaskellを用いたCOBOLリバースエンジニアリングツールの開発事例 / @georgenano さん

  • このタイトルを見て疑問が浮かぶだろう
  • お客さんのIT化できる部分で残っている部分は限られている
    • 機能追加等がメインの仕事
    • コストの削減が求められる
    • しかし、更改は難易度が高い → 予算が少ない。現行仕様のドキュメントはメンテされてない。
  • 仕様が必要 → コストが高い
    • ソースを人が読む : 人手によるミス
    • ヒアリングし直す : 品質が低い
    • リバースエンジニアが必要
  • 求められるリバースエンジニアリング
    • 他言語の解析 : メインフレーム + COBOL + ADABAS のシステムは多い
    • 多様な設計書を作成 : 内部設計、CRUD図、ジョブネット図、クラス図
    • 実用的な時間で解析 : ファイル数1万、ステップ数5M とかは普通
  • Haskell を選択した理由
    • パターンマッチが強力
    • Strafunski という構文解析ツール
    • 単機能のフィルタを組み合わせやすい
    • 副作用がないので、機能の入れ替えがしやすい
    • 副作用がないので、並列処理がしやすい
  • 2年間で15人で300ファイル、36k行のツールが開発された → 実案件でも利用
    • チームは役割ごとに分けられている
  • 処理の流れ
    • 前処理 : コメントの削除など。COBOLのコメントは構文解析しにくい文法(xx~yy列がコメント、など)
    • sglr : 構文解析。解析する言語ごとのSDFファイルを作る。ここではATermと呼ばれるデータ
    • Strafunski : Haskell で扱えるようなデータにする。ただし、ここではまだ言語依存
    • 抽象構文木変換 : 言語非依存の木にする
    • 解析変換 : 成果物の形にする
  • 解析変換では構文木をルールで変換
    • 変数名を日本語台帳で日本語にする。
    • 記述順から処理順に変換する
    • 論理式や算術式を簡約にする
  • 日本語となったデータを、「Excel」で出力。お客様はExcel以外は許さない
    • VBAで字下げ等を反映させる
  • Strafunski にて探索を行う
    • 探索方法 : トップダウンなど
    • マッチしたデータ型に対する処理を記述
    • 簡単に記述できる
  • 企業でHaskell を使ったときの問題
    • Haskell の技術者が少ない
    • 教育コストが高い → インドにはHaskell が書ける人がたくさんいるらしい
    • 教育用問題集の作成
    • Eclipse のようなコード補完、GUIがない
    • vim が使える人は少ない
    • 他言語の開発手法、比較値が使えない (ホワイトボックステストや生産性の指標、工数見積もり値などの統計を持ってない)
  • Haskellリバースエンジニアリングする方募集だそうです!
  • 質疑応答
    • Q. 15人のうち何人がインド人? さっきカレーを食べたので気になりました
    • A. 2人。これから人数を増やす予定
    • Q. Haskell を使わないと教育コストは高いが、Javaなどを使うとその分生産性が下がってマイナスになるのでは?
    • A. その通りだと思う。Haskell の生産性の高さは、教育コストの高さより見返りが大きい。Java などで作ると、保守性が低かったりカスタマイズしにくかったりする。

言語アップデート

Scala編 / @kmizu さん
  • Scala が何かはググって
  • 2.9 の新機能について
  • 並列コレクション
    • map とか勝手に並列化。 .par を呼ぶと変換してくれる
    • コア振り分けを自動でする
    • コア数に比例はしない : オーバヘッドや同期のため
    • 4コアで1.5倍くらい早くなる。記述は楽なのでこんなもん
    • 不変コレクションで副作用がないものが前提。そうじゃないものは注意
    • foldLeft など。前の要素の処理結果を使っての処理するので並列化できない
  • プロセスの呼び出しライブラリ (I/O周りの改善)
    • scala.sys.process "ls" run とか "ls" #> とか "ls #| っとか
    • !!や lines など
  • Scala dynamic
    • Ruby のmethod_missing → 型システムを部分的に破壊できてしまう
    • -Xexperimental をつけたときのみ有効
    • ある種のDSLには有効。
    • Dynamic で化粧したもののみ型システムが破壊される。乱用はしないこと
  • Typesafe社
    • Scala の商用サポート
    • Scala IDE for Eclipse
    • オールインワンパッケージを作りたい (現状は Scala + Akka + α)
  • 8/29 2.9.1 final
    • REPLの立ち上げの高速化 7秒→1秒
    • コンパイルの高速化 1.5倍
    • 2.9.0 との倍なり互換
  • 9/13 Scala for Eclipse 2.0.0 beta 10
    • ビルドマネージャがsbtベースになった
    • セミコロン推論を表示(省略したセミコロンを表示してくれる)
    • 昔は要らないツールだったが、今は普通に使えるので試してもいいのでは(2.0.0 の最新)
  • IntelliJ IDEA のScala プラグインの方が凄い
  • RESTful HTTPサービスライブラリの流行 (WAFではなく)
  • PartialFunction の活用
    • Unfiltered, BlueEyes
    • NOT MVC。View がない
  • 型クラスの流行
    • 昔は活用されていなかった。2.8で入った型
    • Scalaz 型クラスライブラリ。Category 周り。IOモナドとかも。sjson。
  • More Functional
    • 昔よりも手続き型ではなく関数型的に書くことが多い
    • 副作用の排除、関数合成、永続データ構造
    • sbt 0.10系, Specs2 Scalaz, Unfiltered, BlueEyes
  • 宣伝
    • Scala スケーラブルプログラミング の第2版が出る
      • Scala 2.8 対応。おまけの2.9記事
    • Scala 実践プログラミング / Cakeパターン、CONCEPTパターン、限定継続
  • 質疑応答
    • Q. Partial function ってなに?
    • A. 定義域を調べる isDefinedAt が使える。
    • Q. Nothing と Just を返すアプローチと比べると?
    • A. 実行しなければわからない。isDefinedAt は本体は実行しない。
Clojureの今 / @tnoborio さん
  • ノマドClojureアジャイル開発する会社」
  • Clojure 1.3
    • 9/13 にRC0 がリリース
    • 直接ダウンロードするか、Leiningen (別リポジトリの指定)を使うか
    • プリミティブ型のパフォーマンスの改善。竹内関数で4倍差
    • defrecord の改良 → mapで利用できる。シリアライズできる。キーを返せる
    • docとdinf-doc は clojure.repl に入った
  • Leiningen の進化
    • lein retest : 失敗したテストのみ実行
    • lein daemon : デーモン化
    • lein ring : ring サーバの起動
  • ClojureScript
    • JavaScript へ書き出されるClojure (CoffeeScript と同じアプローチ)
    • Google Closure と連携する
    • JS => ブラウザ、Titanium/PhoneGap、Node(連携する機能がClojureScriptにある)
  • Clojure on Heroku
  • コミュニティ
  • 質疑応答
    • Q. Clojure の関数型らしさの方向性は?
    • A. 破壊的代入はできない。シーケンシャルに、流れるように書く。
Erlang update / @kuenishi さん
  • Clojure以下、CommonLisp 以上のメジャーな言語
  • Erlang/OTP はプログラミング言語
    • Javaはすごくないけど、Eclipse はすごい → 言語には売りとなる何かがついてるはず
    • 高可用サーバープログラミングフレームワークと思った方がよい
    • ATM, RADIUS, DNSなど
  • Erlangの得意分野
    • 計量プロセス/ネイティブスレッドとリクエストの対応
    • タイムアウト処理
    • 複数イベントの待ち合わせ
    • 高速なGC
    • ホットコードアップグレード → 末尾再帰をうまく利用して切り替えている
    • LET IT DIE - Error処理をきれいに書く
  • 開発環境
    • Emacserlang-mode + distel
    • rebar : 同梱できるビルドツール (Python の waf)
    • git
    • eunit or ct : テストツール
    • cover
  • DISられる問題の解決策
  • Erjang → JVMに倍とコンパイルする
  • LFE → LISPっぽいErlang
  • R15が12/14にでる 新機能
    • スタックとレースに行番号が出るようになる
    • make -j がようやく通るようになる
最近のHaskellマップ @ma0e さん
  • GHC 7.0.x
    • Haskell 2010 対応
    • 新しいI/Oマネージャ (epollベース)
  • GHC7.2.x(先月)
  • 未来のGHC
    • 型レベル GHC Kind level
      • データコンストラクタを型レベル、型コンストラクタを種レベルに
  • Hugsは亡くなった。使わないで。
  • コミュニティ「Hackage」 - 3386パッケージ、929 開発者
  • Iteratee-based I/O
    • 遅延 I/O の問題を解決 → enumerator が現在の主流のパッケージ。
  • attoparsec
    • Parsec は遅い(モナド変換子、エラーメッセージ)
    • CPS変換で8倍速い
  • blaze-builder → データをシリアライズ。差分リスト
  • text → 高速なUnicode テキスト処理。
  • Web界隈 : Yesod vs. Snap
  • 並行、並列 → Parallel GHC Project
  • Haskell For Kids プロジェクト → ソースを書くとアニメーションが出るサービス
  • 日本の勉強会 → スタートHaskell 180人。
    • 今年中に終わる。大量のHaskellerを排出
  • Haskellの課題
    • GUIライブラリ不足、遅延評価難しい
  • 言語もコミュニティも成長過程。これから参加しても遅くない。
  • 質疑応答


ここまでで退出しました。大変面白かったです。