Gauche > Archives > 2010/09/14

2010/09/14 01:39:09 UTCshiro
#
高いスペックの求人: http://www.kt.rim.or.jp/~kbk/zakkicho/10/zakkicho1009b.html#D20100913-3 ビザ絡みかも。
2010/09/14 01:44:47 UTCshiro
#
職業ビザ/グリーンカードは、「このポジションに必要なスキルを持つ人を探したけどこの外国人以外見つからなかった」って客観的証明が必要。めちゃくちゃ特定的な求人広告を一定期間出して採用できなかったことを以って証明としたりします。
2010/09/14 02:31:36 UTCeyasuyuki@twitter
#
#appengine #oauth #android 2.2 #C2DM 経験者とかを募集したらくるかな?
2010/09/14 02:49:54 UTCeyasuyuki@twitter
#
XSD AXI CXF WSはなんだかわからないしSpringは経験ないけどその他はいちおう経験あるorできそう。どのレベルでやれるかは別として。>高いスペックの求人
2010/09/14 03:25:52 UTC(び)
#
雑魚どもお断り、と短く入れるかわり、かな(笑)
#
レベルの低い求職者の面接に疲れてキレたとか
2010/09/14 05:29:02 UTChigepon
#
OO における Mock とか Stub は関数型言語では、どういうインターフェースで使えると良いか考えていたんですが、こんなの見つけた。
#
http://s-expressions.com/2010/01/24/conjure-simple-mocking-and-stubbing-for-clojure-unit-tests/
#
JMock のようにもう少し色々できるとうれしいかもなあ。
2010/09/14 06:21:09 UTCshiro
#
動的束縛のうまい応用例ですね。R6RSだとよそのモジュールの束縛を勝手に置き換えられないのでちょっと相性が悪いかも?
2010/09/14 06:29:49 UTChigepon
#
そうですね。トリッキーな方法が必要そうです。
#
Emacs Lisp とかなら advise とかでうまくやれそう。
#
Lisp 界隈でこのあたりまじめに追求している人たちいないのかな。テスト時に indirect input/output をどうにかしたいみたいな要求はたとえ関数型言語でもある気がするのだけど。
2010/09/14 06:46:29 UTCshiro
#
AOPの応用例としてテストってのはよく取り上げられてるとは思いますが、汎用のLisp処理系で実用規模で追求してるのは知りませんね。もっとも動的環境になってさえいればいくらでも差し替え可能なので (Schemeのcurrent-*-portとか)、アドホックに対応できてしまうことが多いから誰も追求しないのかも。
2010/09/14 06:51:19 UTChigepon
#
ありがとうございます。アドホックにやるのと、モノが用意されているってのは、使う側からすると見える世界が違うと思うので、がんばって用意したいところですが、まずは小さくはじめてみようかな。
#
xUnit test patterns が出版されたのが 2007 年だから、まだ波が到達していないだけかもしれませんが。
2010/09/14 07:08:15 UTCshiro
#
テストってことで言えば、最近なんとかしたいなと思ってるのがグローバルな状態を変更するような操作のテスト。setupで初期状態にして、テスト走らせて、その後でチェックする、っていうのでいいんだけど、状態数が増えてくるとsetupでちゃんと設定したり、異常時にちゃんと元に戻したりするのが面倒くさくなってくる。
#
OMetaのAlexがWorldっていう概念を考えてて、それはグローバルな世界のコピーがいつでも作れるって感じなんだけど、そういうのがあると状態変更のテストが綺麗に書けるかも、と考えてます。
#
これ http://lambda-the-ultimate.org/node/3040
2010/09/14 07:35:06 UTCshiro
#
動的環境っていうのは世界(環境)への変更がスタックになるんだけど、
#
Worldは変更したやつを元のWorldにマージしたりできるんで、環境の操作モデルがグラフになる。
#
継続の導入によって制御構造がスタックから木になるのと似てるかな。制御構造は合流っていう概念が無いか。むしろ平行計算と相性が良いかも。
2010/09/14 08:29:25 UTChigepon
#
ふむむ。面白いです。unit test の場合は基本的に global な環境をいじるようなコード側に問題があると考えて、break dependency してしまう場合が多いかと思います。この場合 global な環境ってのは global 変数的なものなのかもしれませんが、RDBMS とうまく結びつけてテスト後に rollback してしまうというのも良くある手ですね。
#
あとは global 環境の変化は許容して、初期状態と終了状態の差分でテストするとかもありますね。
2010/09/14 08:35:04 UTCshiro
#
Worldは言語のグローバル環境にトランザクションを持ち込むみたいなものなので、テスト後rollbackというのと発想は一緒ですね。
2010/09/14 08:46:00 UTCkazu
#
こんにちは、IIJ の山本です。
#
MIT Scheme のことで恐縮ですが、質問させて下さい。
2010/09/14 08:47:03 UTCshiro
#
ようこそ。どうぞどうぞ。
2010/09/14 08:47:07 UTCkazu
#
質問は、「MIT Scheme に wttee というライブラリがありますが、これはどれくらいつかわれていますか?」です。
#
長いですが、背景を書いていきます。
#
Haskell には、Data.Map という finite map の実装があります。
#
内部では、weight binary search tree というバランス木が使われています。
#
the art of computre programming 3 では、AVL の代替品として半ページぐらい紹介されている木です。
#
最近、Data.Map にバグが発見されました。
#
挿入はいいのですが、要素を削除すると、バランスが壊れることがあるのです。
#
これをきっかけに、weight binary search tree を研究してみて、面白いことが分かったので、現在論文を書いているところです。
#
同じアルゴリズムが、MIT Scheme の wttree にも使われています。
#
wttree の亜種を考えた Stephen Adams さんが、MIT Scheme のメンテナーだったみたいなので、入っていても不思議ではありません。
#
Data.Map の実装も、Adams さんのテクニカルレポートに基づいています。
#
というわけで、MIT Scheme の wttree にもバグがあります。
#
実際、実験してみたところ、やはり削除で簡単にバランスを崩すことができます。
2010/09/14 08:53:43 UTCshiro
#
実装のバグではなくアルゴリズム上のバグだったってことですか?
2010/09/14 08:54:33 UTCkazu
#
大枠のアルゴリズムはいいのですが、パラメーターの選び方がダメです。
#
Adams さんの wttree のパラメーターは (5,1) なんですが、これは削除のことをまったく考えていません。
#
(x,y) の x は、バランスが取れてないか判断して回転させるかを決めるもの、y は回転させるときに一回転か、二回転かを決めるものです。
#
Adams さんの方式に対しては、数学的に証明を与えられていませんが、我々のテストでは (4,2) と (3,2) のときしかバランスが成り立ちません。
2010/09/14 08:57:56 UTChigepon
#
http://www.google.co.jp/codesearch?as_q=wttree&btnG=Search+Code&hl=&as_package=&as_lang=&as_filename=&as_class=&as_function=&as_license=&as_case=
#
slib に含まれているようですね。
2010/09/14 08:58:14 UTCkazu
#
Adams さんが元にしていて、TAOCP でも紹介されているオリジナルの論文の方式に対しては、我々は Coq で証明を与えられそうなところまで来ています。オリジナルの論文の方式に対する整数解は面白いことに (3,2) しかありません。
#
興味があれば、我々の英語のスライドをお送りします。
#
slib って、Scheme コミュニティでは重要なものですか? 素人質問ですいません。
#
念のため、例を示しますね。
#
(alist->wt-tree
 number-wt-type
 '((-3 . -3)(-6 . -6)(3 . 3)(1 . 1)(7 . 7)(-2 . -2)(5 . 5)))
2010/09/14 09:01:40 UTCshiro
#
おもしろい。slibはポータブルなSchemeライブラリとして歴史が長く、R5RSならほとんどのシリアスな実装上で走るものなので、「slibのユーザ」なら「MIT-Schemeのユーザ」より多いかも。slib中のwttreeを使ってる人ってのは限られるだろうけど。
2010/09/14 09:02:11 UTCkazu
#
こうやって作った木はバランスしているんですが、この木に対して wt-tree/delete-min すると、バランスが崩れます。
#
さっきのを x だとすると:
#
(balanced x) -> #t
#
(balanced (wt-tree/delete-min x)) -> #f
#
となります。
#
balanced の実装は、こう書きます。
#
(define (balanced n)
  (balanced- (tree/root n)))

(define (balanced- n)
  (or (empty? n)
      (let ((l (node/l n))
	    (r (node/r n)))
	(and (isBalanced l r) (isBalanced r l) (balanced- l) (balanced- r)))))

(define (isBalanced a b)
  (let ((x (node/size a))
	(y (node/size b)))
    (or (fix:<= (fix:+ x y) 1)
	(fix:>= (fix:* wt-tree-ratio x) y))))
#
MIT Scheme の define-structure の仕様がよく分からないので、僕はこの定義を外に持ち出すことができず、wttree.scm に直接書きしました。
#
あ、MIT Scheme の問題というより、slib の問題という方が、インパクトが強いんですね。
2010/09/14 09:06:30 UTCshiro
#
関係ないけど「balanced-」は本当は「balanced'」と書きたかった?
2010/09/14 09:07:03 UTCkazu
#
Scheme の習慣はあまり知りません。名前は適当です。ごめんなさい。
#
Adams さんのテクニカルペーパーは、ここにあります。
#
http://groups.csail.mit.edu/mac/users/adams/BB/
2010/09/14 09:07:49 UTCshiro
#
slibがMIT Schemeの実装に基づいているなら、上流が直ればslibも追従すると思いますが、MIT Schemeの方の反応が遅ければslibのAubrey Jafferさんに直接言えばすぐに対応してくれると思います。
2010/09/14 09:09:06 UTCkazu
#
そうですか。論文の草稿ができたら、それを見せて直してもらうことにします。
2010/09/14 09:10:13 UTCshiro
#
日本でのMIT Schemeのユーザというのはどのくらいいるんでしょうね。blogで何回かみかけたことはありますが…
2010/09/14 09:11:38 UTCkazu
#
それで、論文では Haskell の Data.Map に使われているよ、で十分インパクトはあるんですけど、Scheme コミュニティにも重要なことなら、wttree にも触れようかなぁ、どうしようかなぁという感じで迷っています。
2010/09/14 09:14:17 UTCshiro
#
MIT Schemeにあってslibにも取り込まれているなら、Scheme界でのニュースとしてのインパクトは十分にあると思います。
2010/09/14 09:15:19 UTCkazu
#
分かりました。ありがとうございます。MIT Scheme と slib の名前を論文で出す方向で考えます。
#
我々のスライドを見たい方がいましたら、kazu iij ad jp までメールを下さい。
2010/09/14 09:28:23 UTCshiro
#
まさかとは思いますが、その広告は、あなたの想像上の存在にすぎないのでは(ry RT: @rui314: この広告と本文とのマッチは奇跡の一枚。 http://i.imgur.com/IOBPq.jpg
#
ありゃ、RT中に埋め込まれた短縮urlもインライン表示しちゃうんだな。
2010/09/14 09:56:22 UTCshiro
#
ゲームの「セーブポイント」でいいんじゃないでしょうか。サブルーチンコールも「ゲームをセーブして別のに入れ替える」みたいなイメージ RT: @tana_ash: Schemeの継続をどうやって説明したらいいか。ただし相手は小学校高学年から中学生を想定する。
2010/09/14 22:46:32 UTCshiro
#
お、ありがとうございます RT: @yoshikiohshima: Worldsに関する論文はちょっとだけ機能が充実したりしたものに関する改訂版が http://www.vpri.org/pdf/tr2010001_worlds.pdf にあります。
#
@yoshikiohshima あと、twitterからchaton_gaucheへの投稿は、chaton_gaucheをフォローしてないと反映されないようになってます。(でも何でこの仕様にしたんだったかな?)
2010/09/14 23:05:36 UTCshiro
#
ところで、もしハワイでScheme Workshopが開催されたら、日本から参加したいって方はどのくらいいますか。Scheme Workshopについては http://www.schemeworkshop.org/
#
例年、週末の一日を使ってやります。一応"Scheme and Functional Programming"なのでScheme限定ではないです。
#
日本から参加の場合、例えば土曜にやることにすると、最短で日本の土曜夜出発→ハワイの土曜朝着、ワークショップ参加で一泊、ハワイの日曜朝出発→日本の月曜午後着、ということで最低一日は仕事を休む必要がありますが。
#
金曜夜出発→ハワイの金曜朝到着、でも休みは変わらないか。
2010/09/14 23:13:18 UTCeyasuyuki@twitter
#
参加希望>Scheme Workshop。最近美しくない括弧{}ばかり書いているので。
2010/09/14 23:15:49 UTCshiro
#
あ、今秋からホノルル-羽田便が出来るんだっけ。夕方出発で翌日深夜に羽田着という便ができるので、どうしても休めなかったら土曜のワークショップを夕方ぎりぎりまでいて羽田便に飛び乗って日曜深夜に日本帰着、という手もあり得る? ちょっと厳しいか。
2010/09/14 23:21:18 UTCeyasuyuki@twitter
#
ハワイに行くLCCを調べたんだけどドル箱路線なのか存在しなさそうでした。ハワイローカル線としてはgo!っていうLCCがあるらしい。
2010/09/14 23:30:20 UTCnobsun@twitter
#
(^o^)ノ 〉shiro: ところで、もしハワイでScheme Workshopが開催されたら、日本から参加したいって方はどのくらいいますか。