Schemeを愛するプログラマ。
メモ：Shiro:芝居関係, Shiro:BeginningActing, Shiro:ActingForAdults, Shiro:AdvancedActing, Shiro:AuditionRecords
過去：Shiro:log:2002, Shiro:log:2003前半, Shiro:log:2003後半, Shiro:log:2004前半, Shiro:log:2004後半, Shiro:log:2005前半
記事：Shiro:UnixUser0307, Shiro:UnixUser0309, Shiro:HackersAndPainters
(2005/11/15 12:02:39 PST)
やっぱり人のコーディングスタイルとかを見るのは勉強になる。 [...] で、そこで皆さんのコードをみてみたいのである。 [...] で、あんまり複雑なのは面倒なので非常に簡単な問題。
二つのツリー（もしくはリスト）が等価であるかどうかを判定するプログラムを示せ。 (深さ優先探索したときの各葉の要素の並びが2つのツリーで等価ってこと)たとえば、(1 (2 3) (4)) と(1 (2 (3 (4))))は等価である。
この方はさらっと書かれているが、これはsamefringe problemと呼ばれる なかなかに興味深い問題である。ナイーブな解は、ツリーの全ての要素を列挙した リスト(flattenしたもの、と言ってもよい)を作ってそれらを比べるというものだが、 もしツリーが巨大なものであり、しかもそれらが異なっていた場合、 flattenの作業の大部分が無駄になってしまう。
ところが必要最低限の空間複雑度で計算しようとすると、 「同型でないデータ構造を再帰する」というちょっと厄介な問題を解かねばならない。 コルーチンで解く方法もあるが、遅延ストリームを使うと再帰の部分が ジェネレータに隠されてわりと素直に書ける。
(use util.stream)
(define (samefringe? t1 t2)
(define (make-gen tree)
(stream-delay
(cond ((null? tree) stream-null)
((pair? tree)
(stream-append (make-gen (car tree)) (make-gen (cdr tree))))
(else (stream tree)))))
(let loop ((s1 (make-gen t1))
(s2 (make-gen t2)))
(or (and (stream-null? s1) (stream-null? s2))
(and (stream-pair? s1) (stream-pair? s2)
(equal? (stream-car s1) (stream-car s2))
(loop (stream-cdr s1) (stream-cdr s2))))))
streamに隠された継続を陽に扱って継続渡し形式にしても良いが、 あまりわかりやすくはない。
(define (samefringe? t1 t2)
(define (traverse g1 g2)
(g1 (lambda (e1 end1? rest1)
(g2 (lambda (e2 end2? rest2)
(or (and end1? end2?)
(and (equal? e1 e2) (traverse rest1 rest2))))))))
(define (end c) (c #f #t #f))
(define (genfringe tree c rest)
(cond ((null? tree) (rest c))
((pair? tree)
(genfringe (car tree) c
(lambda (c) (genfringe (cdr tree) c rest))))
(else (c tree #f rest))))
(traverse (lambda (c) (genfringe t1 c end))
(lambda (c) (genfringe t2 c end))))
コルーチンによるもの、継続渡しによるもの、遅延ストリームによるものは どれも本質的に同型の解になり、木の深さDに対して最悪O(D)の空間を必要とする。
(なお、良く見るsamefringe problemではコンスセルを2分木として扱う、つまり fringe (1 (2 3) 4) => (1 2 3 () 4 ()) とみなすことが多いが、 ここでは元の問題に合わせた。)
Haskellならもともとlazyだからこれでいいのかな。
data Tree a = Leaf a | Branch [Tree a] fringe :: Tree a -> [a] fringe (Leaf x) = [x] fringe (Branch x) = foldr (\x r -> fringe x ++ r) [] x samefringe :: Eq a => Tree a -> Tree a -> Bool samefringe x y = fringe x == fringe y
参考： Henry Baker, Iterators: Signs of Weakness in Object-Oriented Languages, ACM OOPS Messenger 4, 3 (July 1993), 18-25. http://home.pipeline.com/~hbaker1/Iterator.html
(2005/11/11 23:03:26 PST)
またc.l.sネタだが。Original Posterのちょっとしたミススペリングが ジョークツリーに発展中。
http://groups.google.com/group/comp.lang.scheme/browse_frm/thread/1af2cb0cf7adc026
(2005/11/09 21:20:25 PST) Sassy
From c.l.s
Sassy is a 32-bit x86 assembler written in Scheme, based on Henry Baker's COMFY65 Compiler.
Sassy supports the full x86 instruction set (SSE and all that), and comes with an output module for targeting ELF (we got GOT) and an API to write your own output modules.
アセンブラソースはS式。埋め込みScheme式があるので、 マクロアセンブラのマクロをSchemeで書けることになる。 遊びがいのありそうなソフトだ。 Gaucheでも走るらしい。
(2005/11/01 18:16:09 PST)
昨日の続き。
Gauche的には、今回の問題だけに関してはforkの前に強制的にgcを呼ぶようにすれば 回避できるな…
(2005/11/01 05:02:11 PST)
う〜。0.8.6リリース寸前にもたついている。
どうもメモリ絡みのやばいバグが潜んでる模様。 びさんのレポートするMacOS X最新版での不具合もひょっとすると同根かも。 これまでの経過。
さすがにこの爆弾を抱えたまま出すわけにいかないので、引続き調査中。
(2005/10/05 23:50:58 PDT)
Rubyだと色々やり方があるみたい。Gaucheでは
(use srfi-14) (char-set->string #[\w])
(2005/10/04 19:23:49 PDT)
これでMayaでMELの代わりにLispが使えるようになることは…無いだろうなぁ。
(2005/10/04 04:17:11 PDT)
毎年恒例(?)、Franz社の2日間にわたるLispセミナーが今年も開催されるそうです。
「2日間みっちり！ Lispチュートリアル&Lispセミナー&Lisp事例紹介」
去年はAllegro Common Lisp 7.0の正規表現ライブラリについて 発表させてもらったんですが、今年は残念ながら行けません。 1日目のJansによる「Lispゲームプログラミング」が気になるなあ。
(2005/09/30 01:58:39 PDT)
最上の日々 9/28より:
１、関数型プログラミングは、たまたま並列性を最大に記述する方法でもある。それを利用すれば並列性の抽出は容易だ。
２、関数型のプログラムの構文木を直接実行するプロセッサがあるといい。でもそこまで行かなくとも二股同時実行コール命令を追加するだけでも効果がある。
2.について。面倒なのは呼び出しより帰って来た後の同期だから、 「二股同時コール」はそこまで含めてのことだろう。 ただ、プロセッサレベルでは非同期呼び出し命令と同期命令に分かれてた 方が使いでがあるし、そうなるんじゃないかと思う。(言語レベルでの並列 呼び出しをコンパイラが非同期呼び出し+同期命令に展開すればいい)
例えばPS2ではコードとデータを用意してDMAをキックすることでVUが (CPUと並行して)計算を進めてくれる。結果を受け取るには 確かVUから割り込みもかけられたと思うが、コンソールゲームでは 計算時間の予測がたてやすい場合も多くて、CPU側である程度他の計算を 進めてからポーリングして同期していた。
ハードウェアでマルチコアに複数のスレッドを振ってくれるような機構が 出来たなら、非同期呼び出し命令も同期命令もスレッド操作のプリミティブ として処理されることになるかな。
1.について。副作用無しの関数型プログラミングは、 それだけでは並列性の記述には不十分だ。
「AかつB」「AまたはB」というパターンには、AとBを独立して評価できる場合と Bの評価可能性がAの評価結果に依存する場合がある。 後者の例は(and (char? x) (char=? x #?a))。 逐次プログラミングでは両者の区別は不要だが、並列プログラミングでは 区別してもらわないと、前者でAとBを並列に評価する機会を失う。
これはかなり本質的な違いで、「『AまたはB』でAかBの いずれかが停止しなくても、もう一方が停止すれば答えが出る」 というセマンティクスは並行演算を前提としないと実現できない。
これらの演算は実用的には非常に重要だ。並列演算を適用したい大きな データセットを扱う問題であっても、得たい答えは入力の データセットより遥かに小さい場合が多い。 ということは多くの問題で、どこかでたくさん並列に流れてた データの流れがぐっとしぼられる点が必ず一つ以上あるということだ。 例えば「たくさんのものの中から(どれでも良いから)ひとつ条件を満たすものを選ぶ」 という操作は頻出するけれど、関数的な素直な記述：
(define (find pred set)
(cond ((pred (car set)) (car set))
(else (find pred (cdr set)))))
からは並列性は抽出できない。
並列に条件判断を走らせて、どれかひとつが帰って来た時点でそれを採用し 他は捨てる、ということになれば、走っている並列演算をキャンセルする機構も 組み込みで必要になる。
(2005/09/27 05:32:48 PDT)
こちらでの演技中に、「せりふのテンポが遅い」というダメを出されることが良くあった。 自分で丁度良いペースだと感じるテンポはネイティブにとって遅いらしい。 意識して速めてOKをもらっても、気持ち的に急いでるみたいでどうも落ち着かなかった。
多分口が遅いんだろうと思い、一人で運転している時は いつもラジオを聴きながらシャドウイングに挑戦しているが、なかなか ついてゆくのは難しい。NPRのAll Things Consideredとか音楽番組など かなり聴き取り易いものでも、音に気をつけて発音しようとするとどんどん 遅れる。ついてゆこうとすると発音がでたらめになる。 ましてや地元の放送やCMは絶望的。
ふと、フレージングの問題なんではないかと気がついた。「塊」として とらえる単位が小さすぎるんではないかと。つまり、「塊」、として、 とらえる、単位が、小さすぎる、んでは、ないかと、という、具合に、認知して、 発音、してるから、どうしても、テンポが、悪くなる。 cold readingでも、ワンセンテンス全部覚えて目を離すことがなかなか出来ず 細切れになりがちだし。
フレーズを覚える位まで繰り返す練習をするのが良いのかもしれん。
(2005/08/30 05:11:37 PDT) Gaucheの起源
某所でGaucheの名前の起源について質問という程じゃないけれど 話題になっていたので、一応記しておく。いくつかの要因がたまたま 重なってついた名前にすぎず、そんなにおおげさな起源があるわけではない。
(2005/08/29 03:15:36 PDT)
ふと思ったのだが、event driven と thread の表現能力がだいたい同じだとすれば、 全部 thread なスタイルでやる GUI ライブラリというのもあり得るのだろうか。
いかにもErlangあたりがやってそう、と思ってぐぐってみた。 http://www.erlang.se/workshop/2004/ex11.pdf とか。 各ウィジェットがプロセスになっててメッセージパッシングで処理してる ように見える。
ただスタイルとしては各プロセスをオブジェクトとみなしてもあんまり変わらん ような気も。receiveで待たずにbusy loopするとか、本格的にコンカレントに 動いてるプロセスがあると差が出てくるのかも知れないけど、 触ったことがないのでよくわからない。
(2005/08/22 04:49:02 PDT)
若い女の娘を chick というのは現代の俗語かと思っていたら、 さっき読んでたシェークスピアに同じ意味で出てきたんでちょっとびっくりした。 Longmanで引くと確かに old-fashioned slang と書いてある。oldすぎる。
(2005/07/26 14:57:57 PDT)
http://reddit.com/ : Paul Grahamらの投資プログラムの支援を受けた サイトのひとつ。リンクを投稿して読者によるランキングが出来るってことかな? Apache + mod_lisp で動かしてるようだ。
(2005/07/15 11:55:20 PDT) RとL
Rの発音の前に「ウ」をつけるという のは、Rがシラブルの頭、とくに語頭にある場合はわりと有効だと思うが、 難しいのはRがそれ以外の位置にある場合である。
今読んでるStephen Kingの "The Dark Tower VI: Song of Susannah" では、 日本人観光客が Yooo take-ah pickcha, preese? Take pickcha me and my fliend? とか Solly とか喋っている。
Acting Classで注意された発音に、語尾のrがある。year, there, far, fur, cure などの 「母音+R」だ。特に文中でストレスのない場合なんか、つい曖昧に、母音をちょっと 長く発音するくらいで済ませてしまいがちなんだけど、ここに「R」があるかないかは ネイティブにとってはかなり違って聞こえるらしい。 「毎日、"ar, er, ir, or, ur" って練習するといいよ」といわれた。
なお、ハワイのピジン英語では語尾のrが落ちることが多いようで、 わざとrを落としてピジンらしさを出すことはある。 "You and me wen dea, you rememba, ya?" とか。