<< 2月 2009 | ホーム | 4月 2009 >>

Packrat Parsing のメモリ効率の改善手法

Packrat Parsing という構文解析手法の入力になる parsing expression grammer (PEG) に新しい演算子を追加して解析時のメモリ効率を良くしてみました、という論文。Packrat Parsing は、バックトラックにメモ化を組み合わせることで時間効率を良くしているが、メモ化のためにメモリ効率は良くない。そこで、バックトラックしなくてもよくなるポイントを PEG 上に示すためにカット演算子というの導入して、メモ化のための記憶領域を節約する。どうやって意味を変えないように効果的にカット演算子を挿入できるかが課題。

author="水島 宏太 and 前田 敦司 and 山口 喜教",
title="{Packrat Parsing のメモリ効率の改善手法}",
journal="情報処理学会論文誌 プログラミング",
volumn="49",
number="SIG 1",
pages="117--126",
year="2008"

タグ : ,

A Framework for Implementing Pluggable Type Systems

Java に新しい型システムを実装するためのフレームワークの提案。型付け規則の実装は基本的には AST に対してごにょごにょすればよいのでそのための記述言語を Java のアノテーションとも連携しながら定義。その言語で規則を書いてコンパイル時に適用する。いくつかの応用が述べられているけど、提案されている言語が型付け規則を記述するのに十分かどうかは不明だし、型付け規則から素直に出てくるかどうかも微妙な印象。だけど似たようなことは少し考えていたので参考になるかも。

author="Chris Andreae and James Noble and Shane Markstrum and Todd Millstein",
title="{A Framework for Implementing Pluggable Type Systems}",
booktitle="OOPSLA 2006",
publisher="ACM",
pages="57--74",
year="2006"

http://doi.acm.org/10.1145/1167515.1167479

タグ : ,

ホーキング 虚時間の宇宙、竹内薫 著、講談社ブルーバックス

読了。

タグ :

Soft Typing

静的型付けできないところは実行時に検査すればいいよね、という立場の型付け手法。論文には、静的型付けと動的型付けのいいとこ取りって書いてある。型の決定も実行時検査コードの挿入も自動的に行うみたいだけど、途中で議論についていけなくなったのでもう一度読むかも。

author="Robert Cartwright and Mike Fagan",
title="{Soft Typing}",
booktitle="SIGPLAN 1991",
publisher="ACM",
year="1991"

http://doi.acm.org/10.1145/113445.113469

タグ : ,

昭和の軍閥、高橋正衛 著、講談社学術文庫

読了。

タグ :

宇宙論入門、佐藤勝彦 著、岩波新書

読了。

タグ :

振替休日

先週の金土曜が卒業式だったせいだと思うけど今日は振替休日でした、ということに大学に出てきて駐車場の車が少ないのを見て初めて気付きました。もともと今日は特に予定もなかったので普段と何も変わらないわけですが。

タグ :

名古屋

A草研の後輩が結婚して二次会にお呼ばれしたので名古屋行ったのが昨日。昨日のうちに帰ってくるつもりだったけど、A草研のメンバーで飲みに行って名古屋に泊まる羽目になって、少し前にようやく帰宅。末永く幸せでいてほしいなーと思いました。

タグ :

Amazon

Amazon で予約していた本が届きました。今月末か来月初めに出版のはずだったから予想外に早い。ちなみに、届いたのは Milner の新しい本です。読む時間とれるかな。

タグ :

文明の衝突、Samuel P. Huntington 著、鈴木主税 訳、集英社

読了。もっと早いうちに読むつもりだったけどようやく。手をつけてからも半年くらいかかってようやく。

タグ :

昭和天皇の履歴書、文春新書編集部 編、文藝春秋

読了。

タグ :

宇宙は"地球"であふれている、井田茂、佐藤文衛、田村元秀、須藤靖 著、技術評論社

読了。

タグ :

アップルの法則、林信行著、青春出版社

読了。

タグ :

悪夢の医療史、William R.LaFleur, Gernot Böhme, 島薗進編著、中村圭志、秋山淑子訳、勁草書房

読了。

タグ :

宇宙環境と生命、佐藤温重著、裳華房

読了。

タグ :

型エラースライシングによるデッドロックの原因特定

小林先生のデッドロック解析のための型システムに対して、型付けできなかった時の原因、つまりデッドロックの原因を特定するための型エラースライシングを導入したという論文。型推論はつまるところ制約充足なので、充足不能な場合に極小な充足不能集合を求めて、それを元のプログラムに戻せばスライスになってるよね、というのが型エラースライシング。制約と元のプログラムの対応付けをどうするかがこの論文のコア部分。型エラースライシングは面白いので最近実装している情報流解析のための型システムに応用してみたけど、元のプログラムに戻すところがやっぱり面倒。

author="飯村 枝里 and 小林 直樹 and 末永 幸平",
title="{型エラースライシングによるデッドロックの原因特定}",
journal="情報処理学会論文誌 プログラミング",
volumn="1",
number="2",
pages="71--84",
year="2008"

タグ : ,

Recency Types for Dynamically-Typed, Object-Based Languages

JavaScript のような動的型付けでオブジェクトな言語の型システムの提案。うまいようにも見えるし微妙な感じにも見えるのは読み方が甘いのかなんなのか。同じロケーションに割り付けられたオブジェクトは基本的には最新のものしか見えなくて、古いのはそこにあったことだけわかるような仕掛けになっている。preservation と progression が示されているけど、やっぱりどことなく納得いかない感じ。

author="Philip Heidegger and Peter Thiemann",
title="{Recency Types for Dynamically-Typed, Object-Based Languages}",
booktitle="FOOL'09",
publisher="ACM",
year="2009"

タグ : ,

心はプログラムできるか、有田隆也著、ソフトバンククリエイティブ

読了。人工生命とか。学生の頃この筆者の講義を受けたことがあります。

タグ :

へんな数式美術館、竹内薫、技術評論社

読了。

タグ :

PR-Miner: Automatically Extracting Implicit Programming Rules and Detecting Violations in Large Software Code

初めにこの関数を呼んで次にこれを呼んで最後にあれを呼ぶ、といった暗黙知となっているようなルールを抽出するとともに、関数の呼び忘れみたいなルールに反すると思われるコードを検出する手法の論文。単純な方法では場合の数が爆発するので、frequent itemset mining を応用する。手法としては、パターンの抽出、ルールの生成、違反の検出の順で、前の 2 つに対して frequent itemset mining 特に FPclose を利用。基本的には関数内で呼び出す関数や利用する変数の名前に着目して関数ごとに解析するが、関数をまたがったルールに対応するために関数間解析も行う。

author="Zhenmin Li and Yuanyuan Zhou",
title="{PR-Miner: Automatically Extracting Implicit Programming Rules and Detecting Violations in Large Software Code}",
booktitle="FSE'05",
publisher="ACM",
pages="306--315",
year="2005"

タグ : ,

11万

車の総走行距離が 110,000km を超えました。超えたのは昨日のドライブのときですが。引っ越してから月間の走行距離が 3 分の 1 くらいになったのでようやくといった感じ。そろそろクラッチを交換しないといけない感じだし、来年車検だし、この車気に入ってるけどいつまで乗ろうかな。

タグ :