研究

ちょっと研究上の都合から、小さな小さなインタプリタを書く必要性が生じました。作ったプログラミング言語の拡張 BNF はこんな感じ。

program ::= (command  *
command ::=
    | <変数> = e
    | <変数> := e
    | if e then { (command  * } [ else { (command  * } ]
    | while e { (command  * }
    | print e
    | dump
e ::= <整数> | <変数> | unary e | e binary e
unary ::= -
binary ::= + | - | * | / | % | = | == | <> | < | > | <= | >=

全部でぴったり 300 行です。バイト数が 8,837 というのはつまらなかった。コメントでも書いて 8,888 バイトにすればよかった。Objective Caml を使いました。ビルドには OMake を使っています。

よかったらzip を公開してますので拾って行って下さい。ダウンロードされた方はコメントしてね。LALR 文法の shift/reduce 衝突が 13 個も出るので文法記述のお手本にはなりませんね。S 先生@東工大かN 先生@筑波大にお願いして直してもらおうか。。。

PPL 2010 のプログラムが発表されたようです。うちの研究室からは初日の晩のポスターセッションで三つの発表をします。

• 非S式言語における構文マクロの実現に向けて ー 荒井 浩，脇田 建
• JavaScriptアプリケーションのLive Edit開発環境 ー 吉永 卓矢, 脇田 建
  デモやります！
• 関数型言語におけるべイズデバッグ ー 津田 均, 脇田 建

ちょっと詳しい内容については以前にこのブログで紹介しました。

3月3日から3月5日に香川県で開催される第12回プログラミングおよびプログラミング言語ワークショップ (PPL 2010) に参加してきます。研究室からは以下の発表があります。萌芽段階なためにポスター発表ばかりですけれども、いずれも興味深い話題を提供します。是非、ご期待下さい。

荒井浩：非S式言語における構文マクロの実現に向けて †

荒井くんの研究は、プログラミング言語にマクロ機能を追加する試みです。マクロと言ってもC言語のCPPやM4のようなちゃちなものではございません。Hygeinic macro systemと言って、従来から指摘されていたマクロがひこ起こす名前の衝突を解決し、パターンマッチを用いて複雑な構文を定義することができる高級マクロ機構に関する研究です。

実は、この高級マクロは20年ほど前にSchemeのために提案されてから、他のプログラミング言語に応用されたことがありません。それというのも、Lisp の一種である Scheme ではあまり問題にならなかった構文の拡張をプログラミング言語のコンパイル中に施すという技術的な問題が解決できていなかったからです。

もうひとつの問題は、Scheme で現在、標準的に用いられている高級マクロの実装において、高級マクロが用いられていることがあります。つまり、高級マクロシステムを他のプログラミング言語に移植するためには、その言語自身が予め高級マクロシステムを備えていないと移植が困難だということになります。

この発表では、荒井くんがこの問題にどのような指針を与え、実装の状況がどのように進展してくれるかを話してくれると思います。

参考文献 †

• Eugene Kohlbecker, Daniel P. Friedman, Matthias Felleisen, Bruce Duba, "Hygienic macro expansion," in Proceedings of the 1986 ACM conference on LISP and functional programming, pp. 151-161, 1986.

津田均：関数型言語のためのベイズデバッグ*1 †

津田くんの研究は、Liu、Lian、Hanが2006年に提唱したプログラミング言語のデバッグ手法に注目したものです。このデバッグ手法は、プログラムの実行における統計的な振舞いの違いから、バグの所在を言い当てるというものです。簡単に説明すると、プログラムのなかのそこここにif文がありますね。そのif文は条件式を評価した結果を受けて二者択一の動きをします。Liuらのアイデアは各if文で条件式が真の値となる確率を調べることでプログラム実行の特徴づけをできるのではないかという点です。

このBayesian Debugと名付けられたデバッグ手法では、同じプログラムに対して、正当な結果を出力する正答入力と間違った結果を出力する誤答入力を与え、それぞれについて各条件式ごとの真偽値の確率を収集します。そして、両者を比較し真偽値のずれがひどい箇所の近くにバグがあるだろうという発想です。

Bayesian DebugはC言語について提案されたのですが、津田くんはこれをSchemeにおいて試しました。Schemeのような関数的言語はCと異なり、プログラムが式から構成され、関数閉包が一級オブジェクト*2として扱える点が拡張されています。このために津田くんは、原論文の統計理論の枠組みを拡張し、条件式のような二値データだけではなく、一般の多値データを扱えるような工夫をしました。

津田くんは、Cと比べてSchemeのような関数的言語を扱うときにどのような問題が生じるのか、そしてその解決のためにどのようなことを考えればよいのかを語ってくれるでしょう。

参考文献 †

• Chao Liu, Zeng Lian, Jiawei Han, "How Bayesians Debug," icdm, pp.382-393, Sixth IEEE International Conference on Data Mining (ICDM’06), 2006.

吉永卓矢：JavaScriptアプリケーションのLive Edit開発環境 †

吉永くんの研究対象はウェブブラウザを使った開発環境に関するものです。彼が目指しているのは、エディタや統合開発環境のようなものは一切使わずに、ウェブブラウザだけでウェブアプリケーションを開発できるような基盤ソフトウェアです。

ただ単に、アプリケーションが作れるだけでなく、ウェブブラウザの上で動いているウェブアプリケーションをアプリケーションを動かしつつ、データやコードを置き換えることで、動作状況を確認しつつシステムの開発ができるようにすることです。

このような仕組みは少くとも、parc の Smalltalk プロジェクトから発したプログラミング言語 Self には取り入れられており、Live Edit環境と呼ばれています。

吉永くんは、JavaScript を元に Dan Ingalls らが作った Lively Kernel という Live Edit 環境に触れるなかで、その問題点を見つけ、それを修正する形で独自の Live Edit 環境を提案しています。文章で書いても分りにくいのですが、当日はデモをしつつ分りやすく発表してくれると思います。

参考文献 †

• Dan Ingalls, Krzysztof Palacz, Stephen Uhler, Antero Taivalsaari, Tommi Mikkonen. The Lively Kernel — A Self-Supporting System on a Web Page. In Proceedings of the Workshop on Self-Sustaining Systems (S3) 2008, Springer LNCS 5146, pages 31-50, Potsdam, Germany, May 15-16, 2008, Springer.
• Lively Kernel