pow = λm n. n m とか謎過ぎる... λm n. n (λl s. m (l s)) (λs z. s z) なら分かるんだけど．つまり times m を one に対し n 回適用するの． 分からないので pow two three を手計算*1してみた： Applicative: three two = (λs z. s (s (s z))) (λs z. s (…

けたんを誘ったのは正解だと思った．むしろけたんに色々話をしてもらう結果になってしまったかな．面白い話が聞けてうれしかったです． 無論，この話を持ちかけてくれたid:nuc氏に感謝． 以下，補足： Sunの，Forthベースのほにゃらら ... については，VMで…

10:21 08/03/05 構文解析の話をしよう"> 細かい補足 ...2. CYK法、Earley法、GLR法、などの "directional / deterministic" ではないけれど万能な手法、も知られています。ただ、遅いのでプログラミング言語に対してはあまり使われません。設計者が文法自分…

こないだ書店で ヘネパタ（定量的アプローチ，難しい方）の新版が出てたのを見たので1割引の生協書籍部で買おうと思ったんだが，置いてなくて，おかげで Leiserson, Rivest, Stein and Cormen, Introduction to Algorithms, The MIT Press を衝動買い．この…

l(s)を文字列sの長さとするとき，圧縮アルゴリズムfに対し，n文字以下全ての文字列 {s1, s2, ... s_N} に対する「平均圧縮率」 はnの関数だが，極限を持つとき，その極限はどのような値か？ 可逆圧縮アルゴリズムは全ての文字列を並べた無限列に対する順列(p…

ちなみに16進Champernowne定数では駄目だった．ZIP圧縮できてしまった．考えてみれば例えば "123" という文字列が "123", "1123", "2123", ... "10123", ... という具合に無限回出現するから，そこが圧縮できてしまうのかな． 次はとりあえず円周率10000桁と…

ワロタ 101 名前：デフォルトの名無しさん[sage] 投稿日：2007/11/24(土) 23:28:42 言語はマルチスレッドをサポートすべき? │ ├CPUシングルスレッド性能は打ち止めだからこれからはマルチスレッドスレッドだよ │├マルチスレッドをどうにかするのは言語の仕事…

なんかここでの会話は怪しい気がするが細かい訂正を書いてる暇がない． http://www.lingr.com/room/NFA/archives/2007/11/21 まず「SATは決定問題だから，その解は{x1=T, x2=F, ...}でなくYES/NOですよ」とか... それを踏まえて，Wikipediaで言うところの 概…

id:flappphys:20071111#p2 の原稿を仕上げた．例によって〆切を大幅超過しており，（今日やるらしい）駒場生の印刷作業に間に合わないかもしれない（そうしたら次号に載せてもらえばいいんだけど）． http://www.komaba.utmc.or.jp/~flatline/UTMCpress20071…

今日は停止性問題に関する小文を書いていたら終わってしまった．まだChaitin数の話を書き終えてない... 月曜からまた忙しくなりそうだが（別に週末をそんなにゆったり過ごした訳でもないが），もう階層とかに話を膨らませずに急いで終わらせちゃわないとな．…

/.-Jで「Wolframが提唱したTuring機械がuniversalだと証明された．これは最小のUTMが見つかったことを意味する」との記事を読んで，これは証明を眺めてみたいと強く思ったのだが，証明の印刷を忘れたまま帰ってきてもう一度/.-Jを見たら，なんと証明に初歩的…

RSSリーダによればLtUにて面白い投稿が相次いでいるようだが，とても追う余裕がない． http://lambda-the-ultimate.org/ Lambda the Ultimate | Programming Languages Weblog 依存型λ算法のチュートリアル，concurrency （並行性）の記事とparallelism （並…

http://pc11.2ch.net/test/read.cgi/tech/1174211797/ 関数型プログラミング言語Haskell Part7 2ch Haskellスレで「Haskell処理系が日本語文字列をまともに処理してくれねぇ！」という（よくある）不満から，CharとかString (= [Char]) みたいな組み込みの（…

sumii先生のPOPL '07実況 (id:sumii:20070117:p2) キテルーーー！！ 慌しいでしょうに様子を伝えて下さり，ありがとうございます． 楽しそうだなぁ... 自分が寂しいのは 何より，専門家でないので技術的細部を追う余裕がない サーベイ不足で「これは昔からあ…

今頃ニースではPEPMが終わった頃か？ （時差とかよく分からん） プログラム変換は誰しも一度は憧れる漢の浪漫だよなぁ． Aho先生... コンパイラが書きたいです... しかし下手に首を突っ込むとニースと言うよりニートに近づきそうなので，真面目に卒論卒論．…

Harperで思い出したが，こないだ "S.M.L" というＩＯゲー・ブランドの存在を教えてもらったのだった． http://www.sml-info.net/ S.M.L WEBSITE （←18禁； 別にこういうのが私の趣味という訳ではないので注意）

まだPOPL '06のチェックも終わってないのに*1今年のPOPLが17日にやってくる． http://www.cs.ucsd.edu/popl/07/program.html POPL 2007: Preliminary Program 知ってる名前は... 招待講演のA. Tang*2は「Haskellの先進的機能のおかげでPerl 6コンパイラPugs…

数日前に教えてもらった．SIGGRAPH '06に出たらしい． http://www.cse.cuhk.edu.hk/~ttwong/papers/manga/manga.pdf Qu, Wong, and Heng, Manga Colorization Gaborウェーブレットを使うとスクリーントーンとかハッチングの模様が続いている領域を判別できて…

げ，レポート期限，明日？ 教科書の演習問題（確かすごく簡単）を解けとあるが，教科書 (Bird-Wadler) を借りるところから始めないといけないのに... 休日もやってる総合図書館と駒場図書館の蔵書は（多分，計数3年によって）払底している罠．しょうがない電…

λ算法のモデルへの応用という観点からdomain theoryと圏論とを比較せよ．特にYコンビネータの扱いに注意すること． 教えて．

I/Oや，set! 等の変数への破壊的代入が純関数的でないのは明らかだ．しかしそれらを一つも使わなくとも継続を使ったSchemeプログラムが純関数的でないという例があったような，なかったような... 見かけたのは確か (define (foo) ... (call/cc (lambda (k) .…

最近Korte-Vygenゼミに行けてないのう... 残念である．

「他学科の学生なのでレポート提出の場所が分からず，昨日は出せませんでした」 明日はこれで行こう！！！（ぉぃ 自虐ネタはともかくとしてλ算法のモデルとしての用途が分かりやすいテキスト*1を貼っておこう： http://citeseer.ist.psu.edu/martini96catego…

グラフグラフしてて，正直 私としては微妙な内容だった（スキップして欲しかった ← 部外者の我侭だが）．どうせすぐに忘れてしまう（使うときが来たら思い出す速度が向上するという御利益があるとは言えるが...） 「ネストした集合システムの木表現」の構成…

http://labs.google.com/papers/mapreduce.html Dean and Ghemawat, MapReduce: Simplified Data Processing on Large Clusters 何しろ扱うデータセットは膨大で，走らせるマシンが超巨大クラスタ，データのやりとりに分散ファイルシステムを使うってんだか…

証明は単純だった． 4.3 Completeness of the S-K basis'> It is a perhaps astonishing fact that S and K can be composed to produce combinators that are extensionally equal to any lambda term, and therefore, by Church's thesis, to any computab…

物工院試の口述試験は本当に卒研に関するプレゼンと質疑だけだった．少しくらい個人的なことを尋ねられるかと思ってたんだが．よって 面接官「得意分野は型推論とありますが？」 学生 「はい。型推論です。」 面接官「型推論とは何のことですか？」 学生 「…

先輩からこういう発表があるのを教わった． 多相型レコードに基づくRubyオブジェクトの型推論に関する考察 松本 宗太郎（筑波大学 システム情報工学研究科） 南出 靖彦（筑波大学 システム情報工学研究科） http://www.score.cs.tsukuba.ac.jp/~soutaro/ 松…

http://www.radiumsoftware.com/ Radium Software Development ここしばらく高橋氏のブログRadium Software DevelopmentにおいてCSの基礎技術，基礎理論のレビューが多く，非常に興味深い． エラー忘却型コンピューティング (failure-oblivious computing) …

Amortized complexityというのがまだ理解できてない．代表的な結果である「動的配列のアクセスのコストは拡張のコストを含めてもO(1)であること」なんかの証明がぱっと出てこないのよね．いっぺん時間を取って落ち着いて考えてみたい． そういやO記法の使い…