Hatena::ブログ(Diary)

すにぺっと

2011-04-14

clojureプログラミング入門-22 関数型プログラミングと再帰

22:48 | clojureプログラミング入門-22 関数型プログラミングと再帰を含むブックマーク

怠け者になろう

関数型プログラミング再帰定義を多用し、

・基底:シーケンスのいくつかの要素を明示的に列挙した部分

帰納:シーケンスの残りの要素をすでに判明している要素を組み合わせて

    創りだすルール

の部分からなる。

再帰実装がヘタだと、スタックオーバーフローになったり

メモリを食いつぶしたりなど、バグの原因になる。

clojureでは遅延評価が最良の方法であることが多いという。


ここでは単純な再帰を用いてフィボナッチ数列を求めてみる。

user=> (defn stack-com-fib [n]
  (cond
     (= n 0) 0
     (= n 1) 1
	 :else (+ (stack-com-fib (- n 1))
           (stack-com-fib (- n 2)))))
#'user/stack-com-fib

user=> (stack-com-fib 10)
55
user=> (stack-com-fib 100000000000000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

小さい数ならうまくいくが、大きい数だとスタックオーバーフロー

こういった再帰は避けるべき。


末尾再帰

末尾再帰を使えばスタックオーバーフロー問題を解決できる。

再帰呼び出しがコードの最後(関数の返り値を計算する式)

に制限されていればOK.

そうすれば末尾最適化TCO)により

スタックを消費しないように変換する。

関数を末尾再帰にするには、

帰納を進めるのに必要な情報をすべて引数で渡せるように

すればOK.こんなふうにする。

user=> (defn tail-fib [n]
  (letfn [(fib
		   [current next n]
		   (if (zero? n)
			   current
			   (fib next (+ current next) (dec n))))]
		 (fib 0 1 n)))
#'user/tail-fib
user=> (tail-fib 9)
34
user=> (tail-fib 1000000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

letfnはローカル関数を定義するためのマクロ

ローカル関数fibは3つの引数をとる。

引数は、現在のフィボナッチ数current,次のフィボナッチ数next,

次のステップ数n。

しかし、末尾再帰で書いても大きな値でスタックオーバーフロー

原因はJVMらしい。

JVM関数型言語向けに設計されていないため、簡単にTCOを実施してくれないとのこと。

Haskellはしてくれるそうです)

ではどうするかというと、clojureはいくつかの代替手法を用意している。

1.recurをつかった自己再帰

2.遅延シーケンスの使用

3.トランポリンを使った明示的な相互再帰


次回はこれらの手法でフィボナッチ数列

求める関数を書いていく。


プログラミングClojure
プログラミングClojure
posted with amazlet at 11.04.14
Stuart Halloway
オーム社
売り上げランキング: 90335

node.jsのrailsっぽいやつ、Express on railwayを動かしてみた

| 14:00 | node.jsのrailsっぽいやつ、Express on railwayを動かしてみたを含むブックマーク

なにげなくexpress on railwayについてツイートしたら

@koichik氏からレポートお待ちしております、といわれてしまったので、

とりあえずなんとか動かした。


node.jsとnpmはインストールしておくべし。

なんかexpress on railwayはデフォルトmongodbに接続するように

なってるっぽいので、まずはmongodbインストール

$ brew install mongodb

mongodbを起動しておく。

$ mongod run --config /usr/local/Cellar/mongodb/1.8.1-x86_64/mongod.conf
Thu Apr 14 13:39:18 [initandlisten] MongoDB starting : pid=25051 port=27017 
dbpath=/usr/local/var/mongodb 64-bit 
Thu Apr 14 13:39:18 [initandlisten] db version v1.8.1, pdfile version 4.5
Thu Apr 14 13:39:18 [initandlisten] git version: a429cd4f535b2499cc4130b06ff7c26f41c00f04
Thu Apr 14 13:39:18 [initandlisten] build sys info: Darwin erh2.10gen.cc 9.6.0 Darwin Kernel Version 9.6.0: Mon Nov 24 17:37:00 PST 2008; root:xnu-1228.9.59~1/RELEASE_I386 i386 BOOST_LIB_VERSION=1_40
Thu Apr 14 13:39:18 [initandlisten] journal dir=/usr/local/var/mongodb/journal
Thu Apr 14 13:39:18 [initandlisten] recover : no journal files present, no recovery needed
Thu Apr 14 13:39:18 [initandlisten] waiting for connections on port 27017
Thu Apr 14 13:39:18 [websvr] web admin interface listening on port 28017

configファイルの場所は人によって違うかもしれないので、

/usr/local/Cellar/mongodb以下の適切な場所を指定。


次に

expressとmongo系パッケージをインストール

$ npm install express
$ npm install mongo-connect
$ npm install mongodb(いらないかも?)

次はexpress on railwayをインストール

https://github.com/1602/express-on-railway

にあるように、

下記手順でrailwayをインストール

$ git clone git://github.com/1602/express-on-railway.git
$ cd express-on-railway
$ npm install
$ cd -
$ rm -rf express-on-railway

次はサンプルプロジェクトで試してみる。

適当なディレクトリを作成して、railway初期化

$ mkdir mysample
$ cd mysample
$ railway init
create  app/
create  app/models/
create  app/controllers/
create  app/helpers/
create  app/views/
create  app/views/layouts/
create  config/
create  config/initializers/
create  db/
create  public/
create  public/stylesheets/
create  public/javascripts/
create  config/routes.js
create  config/requirements.json
create  server.js
create  config/database.json
create  Jakefile
create  app/views/layouts/application_layout.ejs
create  public/stylesheets/reset.css
create  public/javascripts/rails.js
create  db/schema.js

このままではいまのexpressだと動かないので、

server.jsを一部書きかえる

〜
app.configure(function(){
    app.use(express.static(__dirname + '/public'));  //staticPovider→static
    app.set('views', __dirname + '/app/views');
    app.set('view engine', 'ejs');
    app.use(express.bodyParser()); //bodyDecoder→bodyParser
    app.use(express.cookieParser()); //cookieDecoder→cookieParser
    app.use(express.session({secret:"mysample",store: mongoSessionStore}));
    //secret属性を追加
    app.use(express.methodOverride());
    app.use(app.router);
});
〜

あとは適当な画面をつくって、

とりあえずうごくようにする。

まずはコントローラーを作成。

$ railway generate controller mysamples home
exists  app/
exists  app/controllers/
create  app/controllers/mysamples_controller.js
exists  app/helpers/
create  app/helpers/mysamples_helper.js
exists  app/views/
create  app/views/mysamples/
create  app/views/mysamples/home.ejs

コントローラーを編集。

app/controllers/mysamples_controller.js

action("home", function () {
		   render({title:"Express on railway!"});
});

ejsを編集。

app/views/mysamples/home.ejs

<h1><%= title %></h1>
<p>Hello, <%= title %></p>

routeファイルを編集。

config/routes.js

exports.routes = function (map) {
map.get('/', 'mysamples#home');
};

起動してlocalhost:3000にアクセス。

$ node serer.js
Express server listening on port 3000

アクセスすると、画面に

Hello,Express on railway!の文字が出るはず。

あとこんなログがコンソールに出る。

Thu Apr 14 2011 13:55:18 GMT+0900 (JST)
GET / controller: mysamples action: home
Rendering mysamples/home using layout application_layout

いきおいで書いたので

間違いとかありまくるかも。

とりあえずうごいたどー



clojureプログラミング入門-21 関数型プログラミングの概念

| 08:46 | clojureプログラミング入門-21  関数型プログラミングの概念を含むブックマーク

関数型プログラミングによるコードは書きやすく、

読みやすく、テストがしやすいという。

その理由とは…


純粋な関数

プログラムは純粋な関数を組み合わせて作られる。

これは副作用を持たない関数のこと。

副作用とは、引数以外のものに依存せず、関数の外界に影響を持たないこと。

つまり、数学における関数と意味合いが同じ。

数学関数とは違い、プログラムの出力は純粋ではない。

printlnを使用すると出力ストリームにデータを流して外の世界を変化させるし、

printlnは外の世界の影響を受ける。


純粋な関数は、変更不可なデータと相性がよい。

(defn mystery [input]
       (if input data-1 ata-2))

mysteryが純粋な関数であるには、data-1とdata-2は

変更不可であること。

1つのデータが変更可能であるだけで、一連の関数呼び出しすべてが

純粋でなくなる。


関数型プログラミングをするには、

なにはなくとも不変データを使用することを考えること。


永続的なデータ構造

clojureの並行プリミティブはスレッドセーフな操作を実装するため、

データが変更不可であることを必要とする。

ただ、変更不可を意識すると性能が犠牲になる。

すべてのデータが変更不可なら、

データ更新とは「元データから変更をしたデータのコピーを作成する」

ということになるため、必要以上にメモリを使用してしまう。

実際にclojureは元データすべてをコピーするようなことはしないが、

下記のようなコードがあった場合、

user=> (def a '(1 2))
#'user/a
user=> (def b (cons 0 a))
#'user/b

リストa(1,2)に要素0のリンクを貼り、それをリストbとして

扱うらしい。(書籍の図を参照)

clojureではできるかぎり共有をするようになっているとのこと。


遅延評価再帰

関数型プログラミングでは、遅延評価再帰を多用する。

clojureでは関数と式は遅延評価されないが、

シーケンスは遅延評価の対象となる。

遅延評価関数が純粋であることを前提としているので、注意すること。


参照透過性

遅延評価は、関数呼び出しをいつでも

その結果の値と置き換えられるという性質に依存している。

これを参照透過性というらしい。

これは、

・結果をキャッシュするメモ化

関数評価を別プロセッサやマシンへ移動する自動並列化

と相性がよい。

純粋な関数は定義上参照等価になるという。


FPの利点

関数型コードはテストにおいて、

引数を揃える以外に整える必要がある環境がないので、

テストがしやすくなる。

また、再利用もしやすい。

コードを再利用するために、

・再利用したいコードを見つけて理解し

・再利用したいコードを他のコードと組み合わせる

とうステップが必要。

純粋な関数であれば、コードの可読性もよく、

さらにカプセル化を破壊せずに外界に影響を与えないことが

保証されるので、安心して組み込むことができる。


6つのルール

関数型プログラミングに馴染みの薄い人は、下記に示す

6つのルールに従うことで、関数型プログラミングマスターへの

最初の一歩をクリアできるという。

1.直接の再帰を避ける。

  最適化できないのでスタックオーバーフローになる。

2.要素数がそれほど多くないことがわかっている場合、

  recureを使用する。clojureはrecureを最適化可能。

3.巨大、または要素数が不明なシーケンスは、

  recureを使わず遅延評価を使う。

4.遅延シーケンスを必要以上に評価しない

5.シーケンスライブラリをよく知る。

6.問題を分割する。

  より小さな部分に分解していくと、シーケンスライブラリを使った

  再利用可能な解放が見つかるかもしれない。


ルール5と6が特に重要らしい。

ちなみに書籍には、

関数型プログラミングにはじめてふれる人は、

 どうしようも無い壁に当たるまで、本書の第4章にあるテクニックを使うこと」

とある。

上記ルールはマクロのときのように、あくまでもガイドラインなので

適切に判断しよう。

まあ自分はまだまともに判断できないが。。。


では次回から関数型コードを書いていく。


プログラミングClojure
プログラミングClojure
posted with amazlet at 11.04.14
Stuart Halloway
オーム社
売り上げランキング: 28975