232 名前：仕様書無しさん[] 投稿日：2006/04/23(日) 07:34:43 仕様変更に柔軟に対応するには文字列の方が良かったり・・・ いままで数字だった課番号に突然「東日本課」なんかが追加されたりして・・・ ここから始まる一連のレスがお寒い現実を暴露している…

そう言えばこないだJavaのジェネリクスの話に関連して，某所で「List<T> や HashMap<K, Integer> ではなく List<Integer> や HashMap<String, Integer>」を意図して深く考えずに「concreteな型」と書いてしまったのだけど， higher order polymorphism の言葉を使って "monotype" と言（えばよか｜うべ</string,></integer></k,></t>…

そう言えば，なんか昨日は数百メートル近くにGuy Steele Jr. 来てたんだっけな． とてもそれどころでは...*1 *1:いや別に強制されたという訳ではなく，それどころか私の直接の所属であるレーザー班の仕事でもなかったんだけどね．でも実験系の設計とかはまだ…

http://citeseer.ist.psu.edu/diehl00abstract.html Diehl, Hartel and Sestoft, Abstract Machines for Programming Language Implementations 色々あるんですねぇ...

「このノードは赤／黒」というのは1bitのフラグで判断できるが，現在のCPUでは1bitのフラグにも32bit整数を使うことが多く，1bitであることはあまり得ではない．じゃあ32bitの「フラグ」を使ったらどうなるかと言えば，それは結局はB気になってしまう木がす…

IEEE 754 double準拠のFPUの正しさを検証できる論理学的な手法って存在する／し得るのかな？ ある特定のビットパターンの入力ではand/or素子の列を伝播する誤差が最後の1桁に消えずに残る，みたいなことを防ぎたい．別の言い方をすれば「このときはこうなる…

なんか今になって気付いたんだが（ぉぃ），Hopcroft-Tarjanのアルゴリズムは「辺が直線であること」なぞ微塵も考慮していないんで，Planarity.netの攻略には全く使えない．まぁ攻略法として見つけたアルゴリズムじゃないから別にいいんだが．

上に挙げたばかりだけど，これね： http://www.paddle.mb.ca/G&G/articles/Planarity.pdf The Hopcroft-Tarjan Planarity Algorithm 大体は理解した．実際に平面グラフを構成して判定するアルゴリズムなので，おかげでPlanarity.netの必勝法も分かったことに…

Planarity.net のゲームは自動でランダムにグラフを生成しているようだが，「たまに解けない問題を出してしまうバグが残っています．御容赦ください」とあった．Wikipediaによれば，あるグラフが平面グラフになる必要十分条件は「そのグラフの部分グラフのう…

涼風とこれらの本は，私には区別なくエンターテインメントに思える．片方に飽きたらもう片方... と交互に読んで違和感がない． Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman (ASIN:071671045…

これがSugarSunさん3の卒論ネタらしい． http://citeseer.ist.psu.edu/550205.html Alias Types for Recursive Data Structures 線形型の発展版．「ポインタ」とか「メモリ」を明示的に考えるような低水準言語を念頭に置き，特にこの論文では単方向リスト，…

Google:"superword level parallelism" ↑これは聞いたことのない言葉だ．Instruction Level Parallelismの上に来るらしい？

きちんとした教科書に当たってない訳だが... 型理論というのは，データやソース片に付加し得る属性と言うか，今流行りの言葉で言えばアノテーション（？）を，ソースの静的分析によってどこまで詳しく自動付加できるか追求してるみたい．そしてそこで使われ…

id:sumii先生からは大堀先生のSML#についてお勧めいただいた．しかしSML#は色々新しい着想に基づいてるようで，MinCamlを追うのもいっぱいいっぱいな私にはそれすらまだ早いかな． ただまぁ一応SML/NJについてのメモ．SML/NJが「すさまじい」というのは goog…

id:flappphys:20041115#p1 で触れたGCの実装についてのチュートリアルがいつの間にか更新されていたようなので，改めて読んでみた． http://www.logos.t.u-tokyo.ac.jp/~endo/gc/gc.pdf 一般教養としてのGarbage Collection ときが経ってから再び読むとやは…

何かと思えば直和型を作る構文のミニマルなもののようだ．Ocamlで言えば (* トップレベルのインタラクティブセッションに打ち込むソース *) type figure = Circle of int | Rectangle of int * int;; let foo = Circle 10;; let bar = Rectangle (5, 15);; l…

今はまだ理解できないことについても，時間の余裕ができたとき，なんとなくそっち系の気分になったときや，気合を入れて体系的に学ぶ必要に迫られたときのために，メモを残しておく心がけは大事だと思う． そういう意味では「世界に」公開された日記を使うの…

現在の「勝ち組」はどれなんだ？ 操作的？ 表示的？ 公理的？ いっぺん「MLの意味論完全解説ブック」を手に取って見たい．そして多分全く理解できないことに慄きたい．そう，R5RS末尾の意味論セクションを初めて見たあの日のように．まぁどちらも教材として…

さすがにモデルとか意味論は未ださっぱりなのですが... プログラミング言語の意味論をきっちり考える上で確かな基礎となってくれそうなのが再帰関数と帰納法（自然数）．その再帰関数を作ってくれるYコンビネータはとても重要だが，しかしちょっと考えると妙…

id:sumii先生に，昨年の日記 id:flappphys:20041027:p1 にトラックバックをいただいた．丁寧にありがとうございます． それこそ私が↑で始めて存在型に出合った Cardelli, On Understanding Types, Data Abstraction, and Polymorphism (PDF) でもよいのだけ…

ついでだからSchemeにおいて*1再帰を使ってしまった似非Y combinatorを導くところも示そう（昨日の話の前段階に当たる）． *1:というか動的型，静的スコープ，正格評価の関数型言語において．

http://plapla.tk/%7Eplaster/d/ 11/12 > 不動点関数 本物のY combinatorにはあと一歩，自明な書き換えを行うだけである．整理すると現状は次の通り((私の好みに従って少々名前を変えた．fixよりYが好き．))：

MSDNライブラリより引用． 正規表現の由来は、人の神経系がどのように機能しているかを研究していたころにさかのぼります。神経心理学者である Warren McCulloch と Walter Pitts が、神経回路網を数学的に説明するため方法を開発しました。 1956 年、数学者…

現実逃避のためにオートマトンに関する基本的な演習問題をちょこちょこ解いていた orz 「アルファベットΣ={a}と固定したとき，任意のNFA Aについてそれが受理する言語L(A)がどんなものか説明せよ」という問には悩まされた． もちろん完全な答えが書ける類の…

徳田および村井，はじめて出会うコンピュータ科学 1--8，岩波 を全国の小学生に普及させよーぜ．これは小学生の頃に夢中になって読んだっけな（図書室に入れてくれた図書係の先生に感謝）． http://tokuda-www.cs.titech.ac.jp/~tokuda/abstract.html はじめ…

λ項における優先度や結合性を覚えられる人はよほどの天才に違いない．そういう人こそがきっと歴史に名を残すのだろう．

最近増えてる絶版本の無償ダウンロード（PostScript）．ちょっと難しそう． http://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ Thompson, Type Theory and Functional Programming, Addison-Wesley 売り物では青っぽい表紙の変型判の本が評判いいようだが...…

「オラクル」があるときには難しい問題（ とか）が1ステップで解けるようになる（というか，解けるように問題ごとにオラクルが与えられたものと想定する）．そうするととても難しい問題が中くらいの難しさになる．そうして問題の相対的な階層化ができるよう…

SSAとはStatic Single Assignment formのこと．大量の中間変数とパス依存性を表現する関数φを導入することで，ある変数への代入が2回行われることがないようにする，プログラム変換の一種．データフロー解析等の形式化にとても役立つので中間言語として最近…

CSカテゴリを新設． なんでみんなmost general unifierをmguと書くんだろう．略語が小文字なんて珍しくない？ ... MGUもあるか．