!kiyoka.blog.2010_06 RSSPLAIN

Related pages: !kiyoka.blog.list
25525554444444434444443444444444444444344444444444444444444443434444444444444444444444444444444444444444344444444444444444444444444444444444444444444444444444444444444444444434444444444444444444444444344444344344044455555555555555555555555555505555555555555551551555555555555555055555555555555555555555555555555555055555555555550555555555555555555555555555555555555555555055555555555555505
2

kiyoka日記。NendoSekkaの開発や、最近思うことなど

5

最新10件!kiyoka.blog   過去記事一覧!kiyoka.blog.list

5

kiyoka.blog_header 

2

このブログを書いている人: 西山 清香(kiyoka) - twitter: @kiyokaEXT

5

5

 

5

 

4

kiyoka.2010_06_30[Nendo] 末尾再帰最適化、実装完了

4

私がRubyで書いているLisp方言、 Nendoについて。

4

 

4

先日「kiyoka.2010_05_28[Nendo] 末尾再帰最適化をどう実装するか」で悩んでいた末尾再帰最適化が解決した。

4

結局Chaton上のGaucheのチャットルームで質問したら、shiroさんにcallccのないプラットフォーム上で末尾再帰最適化する方法を教えて頂いた。

4

仕組みは簡単だけど、なぜそれで実現できるのかの説明が難しい。(自分的に)

4

今回はその説明を試みてみる。「継続」などの専門用語を使わずに説明してみたい。

4

 

3

末尾再帰最適化とは

4

Lisp(特にScheme)や関数型言語では再帰呼び出しを多様したプログラミングスタイルが推奨される。

4

理由は、そのほうが手続き的スタイルでコーディングするよりも問題をより自然に表現できるから。(宣言的に書ける)

4

問題は、言語処理系がなんの工夫もしていない場合、再帰呼び出しがスタックを消費するため、いずれスタックオーバーフローを起こすということ。

4

そうならないため、Schemeなどの処理系は末尾再帰最適化を施して、再帰的記述を積極的に使えるようにしている。

4

次の例で、再帰を使ったプログラムの例を挙げる。

4

 

3

mainループ:  自分自身を呼び出す無限ループの例

4

一番シンプルな例では、関数の最後で自分自身を呼び出し無限ループを作る。

4

Schemeなどではごく普通に使われる書き方で、SchemeのサブセットであるNendoもこのスタイルを推奨している。

4
(define (main argv)
4
  ;; イベントキューから新しいイベントを取り出して処理する等
4
  (main argv)
4

このようなコーディングは、デーモンプロセスのようにメモリに常駐し半永久的に動き続けるようなプログラムで使われる。

4

 

4

説明のために Rubyで再帰を使わずに記述すると、以下のようになる。

4
def main
4
  while true
4
  # イベントキューから新しいイベントを取り出して処理する等
4
  end
4
end
4

Rubyでは処理系が末尾再帰最適化をサポートしていないため、このように書かないといけない。(実際にRubyは1.9.2になっても末尾再帰最適化はサポートしていない)

4

 

3

my-member?関数: リスト中に特定の値が含まれているか調べる関数

4

上記のmainループの例では、宣言的に書けるというメリットが感じられなかった。どちらかというと、whileを使ったほうが自然なほどだ。

4

しかし、プログラムによっては、再帰定義で記述するとプログラムを宣言的にすっきり記述できる。

4
(define (my-member? val lst)
4
  (if (null? lst)
4
      #f
4
      (if (eq? val (car lst))
4
          #t
4
          (my-member? val (cdr lst)))))
4

この例では、my-member?自身を呼び出して、リストの先頭以外の調査を自分自身に丸投げしている。

4

 

4

[実行結果]

4
(my-member?
4
 2
4
 '(1 2 3 4 5))
4
 => #t  ;; リスト中に含まれていた
4

 

4
(my-member?
4
 6
4
 '(1 2 3 4 5))
4
 => #f  ;; リスト中に含まれていなかった
4

 

4

 

3

Nendoでの末尾再帰最適化の実現方法

4

 

3

末尾再帰最適化を施していない場合のイメージ

4

NendoはNendoのソースコード(S式)をいったんRubyのプログラムに変換する。今回の対策をする前は以下のようなコードを出力していたため、10000回の再帰が完了するまでに、Stackオーバーフローで停止していた。

4

Rubyでsimple_loop関数を再帰呼び出しするコードになっているので、当然だ。

4

 

4

[生成後のRubyソースコードイメージ(説明用に簡略化されている)]

4
#!/usr/local/bin/ruby
4
#
4
# non tail recursion optimization code.
4
#   => tail_recursion_normal.rb:X: stack level too deep (SystemStackError)
4
#
4
4
def printCounter( count )
4
  m = count % 1000
4
  if 0 == m 
4
    printf( "count = %6d\n", count )
4
  end
4
  count
4
end  
4
4
def main
4
  count = 0
4
  @_simple_loop = lambda {|dummy1|
4
    printCounter( count )
4
    count += 1
4
    if count < 10000
4
      @_simple_loop.call(nil)
4
    end
4
  }
4
  @_simple_loop.call(nil)
4
end
4
4
main
4

 

4

[実行結果]

4
$ ./tail_recursion_normal.rb
4
count =      0
4
count =   1000
4
count =   2000
4
count =   3000
4
./tail_recursion_normal.rb:8: stack level too deep (SystemStackError)
4

 

3

末尾再帰最適化を施した場合のイメージ

4

遅延呼び出しリクエストパケット(DelayedCallPacketクラス)を使って末尾再帰最適化を実現した。

4

以下のようなコードが生成される。

4

実行しても、生成前のNendoのスクリプトは再帰呼び出しでプログラミングしているにもかかわらず、スタックオーバーフローすることはない。

4

※ 本当のNendoの内部では、可変長引数が扱えるため、下記のコードよりも複雑になっている。

4

 

4

[生成後のRubyソースコードイメージ(説明用に簡略化されている)]

4
#!/usr/local/bin/ruby
4
#
4
# tail recursion optimization with trampline and DelayedCallPacket
4
#
4
4
class DelayedCallPacket
4
  def initialize( _proc, _arg1 )
4
    @proc = _proc
4
    @arg1 = _arg1
4
  end
4
4
  def call
4
    @proc.call( @arg1 )
4
  end
4
end
4
4
def trCall( result )
4
  while result.is_a? DelayedCallPacket
4
    result = result.call()
4
  end
4
  result
4
end
4
4
def printCounter( count )
4
  m = count % 10000
4
  if 0 == m 
4
    printf( "count = %6d\n", count )
4
  end
4
  count
4
end  
4
4
4
def main
4
  count = 0
4
  @_simple_loop = lambda {|dummy1|
4
    trCall( printCounter( count ))
4
    count += 1
4
    if count < 100000
4
      DelayedCallPacket.new( @_simple_loop, nil )
4
    end
4
  }
4
  trCall( @_simple_loop.call(nil) ) 
4
end
4
4
main
4

 

4

 

4

[実行結果]

4
$ ./tail_recursion_optimized_with_tramp.rb
4
count =      0
4
count =  10000
4
count =  20000
4
count =  30000
4
count =  40000
4
count =  50000
4
count =  60000
4
count =  70000
4
count =  80000
4
count =  90000
4
 .
4
 .
4
 .
4

 

3

解説

4
末尾再帰呼び出しと判断される箇所には関数呼び出しコードを出力せず、かわりに遅延呼び出しパケットを生成して返すコードを埋め込む。
4

(DelayedCallPacketクラスのインスタンスを返す)

4
それ以外の関数呼び出しについては、いつ遅延呼び出しパケットが戻ってきても良いように、trCall()関数で括る。
4
trCall()関数は、遅延呼び出しパケットが戻って来なくなるまで繰り返し遅延された呼び出しを実行しつづける。(パケット以外の値はスルー)
4

 

4

末尾再帰最適化をしていない場合の呼び出しツリーはこのようになり、いつか呼び出しスタックが溢れる。

4
main
4
  simple_loop
4
    simple_loop
4
      simple_loop
4
        simple_loop
4
         .
4

 

4

それに比べて、末尾再帰最適化を行った場合には次のようになる。

4
main
4
  trCall
4
    simple_loop
4
    simple_loop
4
    simple_loop
4
    simple_loop
4
    .
4

 

4

一度trCall()関数に入れば 本来再帰呼び出しとなるところが、trCall()関数内のwhileループ内部からの連続呼び出しに変換される。

4

なぜ、これで解決するかというと、遅延された再帰呼び出しを、トランポリン関数trCall()が、スタックを消費しない単純なループに変換して処理しているからだ。

4

 

3

これは継続か?

4

遅延呼び出しパケットは継続を格納したパケットといえなくもない。参考:Scheme:CPSEXT

4

パケットはその時点での未来の実行継続ポイントでもある。

4

Schemeの本物の継続(call/ccで取得できるもの)との大きな違いは、その実行継続ポイントとして関数の入り口しか扱えないという違いがある。

4

(他にもいろいろ違いがあると思う。詳しい人、コメントください)

4

 

3

まとめ

4

末尾再帰呼び出しの実行を、呼び出し元に遅延させ、呼び出し元でループとして処理すればスタック消費をリダクションできる。(リソース消費の最適化)

4

 

3

参考リンク

4

末尾再帰 - WikipediaEXT

4

 

0

comment (disabled)

4

4

 

4

 

5

kiyoka.2010_06_29[Mac][セットアップ] MacBook Pro上のsubversionとファイルシステムの準備

5

MacBook Proが手に入ってさっそく開発できるようにセットアップを行っている。

5

この記事は未来の自分の為のメモ。

5

この時作業したOSのバージョンは Snow Leopard (10.6.4)

5

 

5

 

5

UTF-8-MAC問題の回避方法

5

X Code 3.2に入っているsubversionクライアントはファイル名の濁点をUTF-8-MACとして処理する。

5
 参考リンク:
5
 selflearn @ ウィキ - MacでのUTF-8-MAC問題を解決するEXT
5

 

5

解決方法は、MacPortsのsubversionをインストール時に +unicode_path オプションを指定すると濁点の処理が、Linux等と同様のアルゴリズムになるパッチが当たる。

5
$ sudo port -v install subversion +unicode_path
5

(MacPorts 1.9.1で確認済)

5

 

5

 

5

大文字小文字問題の回避方法

5

過去記事 (kiyoka.2008_02_02[MacOSX]MacOS XのSubversionでCodeReposがチェックアウトできない) と同じ問題。

5

(要するにmakefileとMakefileという二つのファイルを同一のディレクトリ内に共存できない)

5

そういうファイルは、時々オープンソースのソースコードパッケージ内に存在するので、オープンソースの作業をする場合は対処しておいた方が後々便利。

5

 

5

作業はMacOS Xの『ディスクユーティリティ』というツールを使う。

5

kiyoka_2010_06_29

5

新しいパーティション作りを大文字小文字を区別できるファイルシステムでフォーマットする。上の例では "CaseSensitive"というパーティション名にしている。

5

この新しいパーティションでなら、makefile と Makefileという二つのファイルを同一ディレクトリ内に保存できるようになる。

5

Macを買ってきてまだパーティションが汚れていないうちに、パーティション分割すればデフラグの様な作業も不要。

5

 

0

comment (disabled)

5

5

 

5

 

5

kiyoka.2010_06_22[創作心理] 2010年現在、これから個人で始めるプロジェクトについて思ったこと

5

2010年にもなると個人で作るべきWebアプリケーションはあまり無い。

5

2008年位までは、時間さえ許せば個人がプライベートで、アイデア一発モノのWebアプリケーションを作れた。というよりも、まだ試されていなくて簡単に実装できるアイデアが沢山あった。

5

例えば、新しいWikiエンジンとかblogエンジンとかCMSとかの汎用ツールやWebフレームワークが沢山生み出された。どれも発展途上で試行錯誤のしがいがあった。

5

2010年現在の状況を見てみると、なかなか普通に思いつくアイデアはほとんど試されているんじゃないかなー。世の中にはWebサイトが溢れ返っている。Webフレームワークもある程度定番に収束しつつある。

5

おまけにGoogle App Engineなどのように無料で使えるクラウドサービスがあるので、サイトをオープンするための費用面での敷居も下がり続けている。

5

TechCrunch Japanなんかを時々チェックしていると、ますますそういう思いが強くなっていく。毎日似たようなサービスが雨後の竹の子のように生まれ続けている。

5

 

5

そうすると何が起きるかというと、「個人がプライベートで習作するWebアプリケーション」というのは既存の無料サービスのサブセットの作り直し作業に成り下がる。これは残念。まるでピアノの練習曲を弾いているみたいな感じがする。そんなんでいいのか?

5

この作業はモチベーション的になかなか厳しいものがある。既にあるのに、しかも無料なのに、なぜ今更作る必要があるのかと。ノウハウが得られる以外のメリットは無い。

5

いま、単なるWebアプリケーション開発は飽和している。

5

 

1

また、ベンチャーが立ち上げるWebアプリケーションもWikiシステムやブログシステムのような汎用情報プラットフォームを裸で提供するだけでなく、特定業者向けに最適化されたWebサイト(クラウド)に移ってきているように思う。

5

そういうものは、その業界に精通したものだけが作れる類いのものだ。(本当にそういうものが有用なんだけど)

5

現在では、Ruby On Railsのようなフレームワークを使えば簡単にWebアプリケーションが量産できる時代になってしまったので、そうなるのは当然でむしろ望ましい方向だろう。

1

でも考えてみれば、アプリケーションの存在意義は本来そこだ。

5

注力すべきレイヤーが汎用フレームワークから1段上のアプリケーションに上がっている。生産性が上がった結果、その生産性が正しい方向に使われている。うんうん、世の中は確実に良くなっている。

5

 

5

さてさて、個人でやれることに戻ると、何が残っているのか。

5

人によっていろいろな意見はあるだろうけど、私は自然言語処理やプログラミング言語などの新しいアイデアを試すとか、スマートフォン上のアプリケーションとWebサイト(クラウド)との組み合わせで、さらに進歩したものを作る方向かなーと思う。(スマートフォン関連は既に飽和気味の感も否めないが...)

5

結論めいたことは書けないけど、個人がやるべき領域はどんどん狭く、専門的になってきている気がするなぁ。

5
 kiyoka_2010_06_22
5

 

5

何かまとまりがない記事だけど、一応公開しときます。

5

 

5

※ 進歩って何?という議論はあるだろうけど。新規性? 独自性? 生産性? 利便性?

5

※ 自分がチェックしているブログやニュースサイトによる偏った見方かもしれないので注意。

5

※ 私が最近開発しているNendoというLisp処理系もScheme言語の習作の域を出ていないというご指摘もあるだろうけど、これはこれで、これからいろいろ試したいアイデアが残っているので...

5

 

5

COMMENTyoriyuki

自然言語処理や機械学習も5年くらい前は論文一つ読んだだけの門外漢でも何かできそうな気がしましたが、今となってはとてもとても。Googleみたいな大企業が専門家を揃えて参入してくるのだから太刀打ち出来ません。

自分が何で優位なのかを見極めないといけないですね。月並みですが。

5

COMMENTkiyoka

まとまりの無い記事だったのに、コメント頂けて幸いです。

自然言語処理や機械学習の件は、私もそう思います。趣味でちょっとかじった程度の人間にはもうインパクトのあるものは作れそうにない気がします。

よほど、奇を衒ったもの(要は役に立たないネタ的なもの)くらいしか作れないでしょうね。

>自分が何で優位なのかを見極めないといけないですね。月並みですが。

本当にそう思います。

これまでの自分を振り返って、手を出したジャンルがバラバラで一貫していないので余計に自分の優位な部分って何なのかがよくわからなくなってきています。

平均的に優秀なエンジニアではこの先やっていけいないことは目に見えているので、冷静に自己分析も必要ですね。

誰もが抱える悩みではあると思いますが、自分も引き続き悩み続けることでしょう。

0

comment (disabled)

5

5

 

5

 

5

kiyoka.2010_06_20[Life][Computer] MacBook Proを買ったらできるようになること

5

AppleStoreに入金すると発注完了する所まで来た。もうすぐ手に入るぞ。

5
 product-front-13Mac Book Pro "13
5

今持っているPowerBook G4はPowerPCなので、色々できないことがあった。

5

新しいマシン(Intel)では色々できることが増えて楽しみ。

5

 

5
プログラミング関係
5
MongoDBが動く
5
Sumibiがローカルで動く(メモリが4GByteになるため)
5
MacRubyが動く
5
Rubiniusが動く
5
iPhoneアプリの開発ができる。
5

 

5
アプリ関係
5
Google日本語入力が動く
5
Google Chrome Browserが動く
5

 

5
エンターテイメント関係
5
音楽が聞ける!
5

現在自分のiTunesに入っている音楽ファイルは17GByte分有るのだが、古いPowerBook G4では音楽よりもソフトウェア開発を優先し、HDDをMacPortsに明け渡すため、音楽データを全てUSB HDDに退避した。よって普段iTunesはカラッポだった。

5

新しいマシンではHDD容量が大きいのでやっとiTunesに音楽が戻ってくる。

5

 

5
その他
5
バッテリーが長持ちする
5

古いPowerBook G4では3時間しかバッテリーが持たなかったので、いつも予備バッテリーを持ち歩いていた。

5

その必要が無くなりそう。

5
軽くなる。
5

サイズが"15から"13になるので500グラムほど軽くなる。予備バッテリーも考えると1Kグラムほど軽くなる。

5

 

5

体感速度も上がりそうで楽しみ。

5

EmacsでRubyスクリプトをruby-modeで編集するとき、1行のインデントが2秒くらいかかっていたが、それもストレスも無位に高速化されるのではないかな。

5

 

0

comment (disabled)

5

5

 

5

 

5

kiyoka.2010_06_14[Life] ケチケチ生活は新しいもの好きにはツラい

5

iPhone 4、iPod、数々のAndroidケータイ。

5

HTML5に、次から次に発表されるクラウドサービス。

5

最近の新製品発表のペースはおそろしいほど早い。

5

 

5

昔から新しいものはそれなりに飛びついて、どんなものかいち早く体験するほうだったのだが、いまは休職中でケチケチ生活を強いられているため、それができない。

5

本当は、スマートフォンを一台買ってアプリを作ってみたいのだけど、毎月の基本料金がかかるのは避けたい。(それよりも電動アシストのママチャリを買わねば)

5

こういう時期は、脇目も振らずLisp処理系とか作ってコンピュータサイエンスの基礎に立ち返るストイックな精神が必要かも。

5

いつか、Androidケータイ上でNendoのreplが走るのを夢見ながら今は地道にいこうかなー。

5

 

0

comment (disabled)

5

5

 

5

 

5

kiyoka.2010_06_12[Nendo][Ruby] 今さらRubyでCGIもないだろうと思って調べたら、Rackにたどりついた。

5

CGI程度の簡単アプリであっても、Rackに乗せるべきだと思った。

5
 rack-logo
5

 

5
 Route 477 - 5分でわかるRack , シュレーディンガーの猫たちEXT から一部引用
5

(略)

5
 というわけで、これからRuby用のWebアプリ用フレームワークやWebサーバを書
5
 こうとするなら Rackは間違いなくチェックすべきライブラリだ。そうでなくて、
5
 単にWebアプリを作りたいだけの場合でも、「超シンプルなWebアプリ用フレー
5
 ムワーク」としてRackを使うという選択肢もあるだろう。
5

(略)

5
 Rackの思想
5
 「Webアプリって要するにリクエストをレスポンスに変換するだけの関数だよねー」
5
  ってのがRackの基本っぽい。
5
 なので、
5
  * env(環境変数のハッシュ)を受け取って
5
  * ステータスコードとHTTPヘッダとHTTPボディを返す
5
 ような関数を書けばWebアプリになります。
5

 

5

一度、サンプルを作って体験してみよう。

5

デカ文字作成サイトがちょうど良いかな。

5
 4637389571_74838ed7e3
5

 

5

ついでに、Rack::ReloaderをNendoでWebアプリ開発する時にうまく使えないかにも興味がある。

5

 

5
 Greenbear Laboratory - Rack日本語リファレンスEXT
5
 Rack::Reloader
5
   リクエスト時に、Rubyスクリプトが更新されていたらリロードする。 (ただ
5
   し、重くなるのを避けるため、一度リロードしたら10秒間はリロードしない。
5
   この秒数は設定可能。)
5

 

5

Nendoの話に移ると、EmacsでNendoアプリを編集する場合、スクリプト全体を毎回実行するのではなく、関数単位でevalし、テストを繰返すスタイルを取る。

5

Lispでは多分、標準的な開発スタイルだと思われる。

5

ちなみに、Gauche用のWebフレームワークKahuaはもっと進んでいて、サーバーに直接replで接続し、サーバー上にデプロイ済みのアプリに対して関数単位で動的に更新しながら開発できる。

5

これに慣れると、ファイル単位のReloadとかDeployの繰返しには戻りたく無くなる。

5

 

5

NendoとRackで、これに似たスタイルを作れそうな気がするので、その辺もいろいろ実験してみようと思う。

5

(単に、replでS式を一つ評価する度に完成したRubyソースを吐きだすような特殊なreplを作れば良いだけだと思っている。考えが甘いかな?)

5

 

0

comment (disabled)

5

5

 

5

 

5

kiyoka.2010_06_09[Ruby][Nendo] Rubyの呼び出しスタックの深さ制限値を広げることはできるか

5

Rubyで、再帰呼び出しの回数が深すぎると、スタックオーバーフローになる。

5

再帰を多様する関数型プログラミングスタイルでコーディングなんかすると頻繁にスタックオーバーフローを目にすることになる。

5
 [例]
5
tail_recursion_normal.rb:7: stack level too deep (SystemStackError)
5

Nendoの末尾再帰最適化をやろうとして、ふと思った。「Ruby側のstackの深さ制限を緩和すれば、そこそこ深い再帰呼び出しをしても実用レベルでは問題にならないんじゃないだろうか」

5

 

5

結論。その考えは甘かった。

5

CRuby 1.9.2 preview3 のソースを見たのだが、CRubyが採用しているGCの制約でMARKが届く範囲までしかstackの拡張を許していないようだ。

5

ということは、現状の設定が理論値上の最大値に設定してあるということなのだろう。

5

そんな楽な道はあきらめて、ちゃんと末尾再帰最適化にチャレンジしよう。安心して再帰が書けるようにしよう。

5

 

0

comment (disabled)

5