著者

高島 尚希 亀山 幸義

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.5, no.1, pp.27-27, 2012-03-28

---

本発表は,コントロールオペレータの表現力を解明すること,特に,捕捉される限定継続の範囲が入れ子になることを許すコントロールオペレータnested shift/resetを,入れ子を許さないコントロールオペレータcontrol/promptを用いて表現できることを厳密に示すことを目的とする.コントロールオペレータnested shift/resetは,よく知られているコントロールオペレータshift/resetに,タグを付加して拡張したものである.本研究の出発点は,独立に提案され研究されているnested shift/resetとcontrol/promptが,抽象機械のレベルでは非常に類似した構造を持つ,という観測である.この観測に基づき,抽象機械のレベルで前者を後者でシミュレートできることを証明する.この手法を拡張して,nested control/promptをcontrol/promptでシミュレートできることも示す.最後に,抽象機械をソースコードレベルに戻す変換を適用することにより,nested shift/resetやnested control/promptを,control/promptでマクロ定義可能であることを示す.本手法によるマクロ定義は,簡潔なデータ型を用いて実現され,多くの関数型言語でそのまま利用可能である.

著者

大島 芳樹 脇田 建 佐々 政孝

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.41, no.SIG09(PRO8), pp.62-77, 2000-11-15

---

高機能なSmalltalk処理系であるSqueakを携帯情報端末Zaurusに移植し,Zaurusの持つ独自のハードウェアにあわせて拡張を施したので,システムの実現方法,性能,可用性の評価について報告する.我々の行った実装作業は大きく2つに分類される.まず,基本的な機能の性能を向上させるために,Zaurus上でのイベント処理方式やビットマップ変換方式の性能について定量的評価を行い,それに基づいて最適化を行った.さらに,Zaurus独自の拡張を施すことによって,ペン入力,音声機能,デジタルカメラ,TCP/IPネットワーク,シリアル・IrDAポート,電力消費制御,およびフラッシュメモリファイルシステムのようなPDA独自のハードウェアをSqueakから操作可能とした.この移植および拡張はZaurus依存の部分を記述した4000行程度のC記述および600行ほどのSqueak記述によって達成された.我々は大小各種のベンチマークによる性能評価およびいくつかのアプリケーションによる可用性評価を行った.Zaurusシリーズの最上位機種であるMI-EX1上のSqueakは,400MHz G3 Macに対して最高1/8程度の性能を示した.このベンチマークの数字および実際の使用テストから,このシステムは十分実用に耐える性能を持つことが分かった.我々の実装によって,さまざまな周辺機器を操作できる実用的なプログラミング環境を手のひらサイズの機器上で運用できることが示された.

著者

根岸 純一 岩崎 英哉

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.2, no.3, pp.48-56, 2009-07-10

---

遅延評価型関数型言語 Haskell で書かれたプログラムのデバッグは,処理系 GHC に組み込まれている GHCi デバッガを用いて,実行時の変数の情報を確認する等して行うことが一般的である.GHCi デバッガは,対話的な環境におけるコマンド入力により,ブレイクポイントの設定,ステップ実行,状況に応じた変数の評価や追跡機能等の機能を提供する.しかし,GHCi デバッガは,グラフィカルなユーザインタフェースによる,ステップ実行の可視化が必要であることが,開発者らにより指摘されている.そこで,本論文では GHCi デバッガに対して,デバッグ実行時の表示を追加し,操作を簡易化するための機構を,ウェブブラウザを利用したフロントエンドとして実装する.本フロントエンドは,GUI を用いてソースコードと評価順序を確認しつつ履歴を簡単に戻りながら遅延オブジェクトの内容を評価できるデバッグ支援環境を提供する.実装には,Python および jQuery ライブラリを用いた.本フロントエンドは,GHCi デバッガの出力を JavaScript を用いた動的 HTML として整形する機構とウェブブラウザの操作を GHCi デバッガのコマンドに対応付ける HTTP サーバの 2 つで構成されている.GHC とウェブブラウザが使用できる環境であれば,環境を選ばず簡単に導入が行えることが特長となっている.

著者

坂口 和彦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.7, no.5, pp.10-10, 2014-12-05

---

本発表では,スタック指向プログラミング言語PS0と定理証明支援系Coq上に実装したPS0の対話的プログラミング環境を紹介する.この対話的プログラミング環境では,ユーザはまず目的のプログラムがスタックの状態をどう変化させるかを表す形でプログラムの仕様を与え,次にプログラムの断片や証明を順番に与えていくことでプログラムを完成させる.このとき,記述するべき残りのプログラムの仕様は今までに入力したプログラムでどのような状態のスタックに遷移するかを表しているため,一般化されたスタックの状態を見ながらプログラムを記述できる.また,PS0のプログラムをPostScriptのプログラムに変換し,GhostScript等のPostScriptインタプリタの上で実行できることを確認した.We introduce a stack-oriented programming language PS0 and its interactive programming environment implemented in the Coq proof assistant. In this programming environment, first, a user writes the specification of a program as to how the program mutates the stack. Next, the user interactively fills unspecified part of the program. Finally, the user obtains the complete program that proved satisfying the specification. At each step, the environment shows the specification of the program that we should fill. The specification describes the property of the initial and final state of the stacks. Therefore, we can write the program with the generalized state of the stack given. We also implemented a translator from PS0 programs to PostScript programs. It was confirmed that PostScript programs generated by the translator can be executed on PostScript interpreters (e.g., Ghostscript) properly.

著者

田代 克也 中野 圭介 岩崎 英哉

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.6, no.3, pp.51-51, 2013-12-20

---

Webアプリケーションの開発を支援するための枠組みとして,テストツールと呼ばれる機能が多くの開発フレームワークにおいて提供されている.この機能では,テストに必要な入力値などの組であるテストケースを開発者が設定することで,自動的なテストの実行が可能である.しかしながら,正確なテストを行うには,入力値などを詳細に記述しなければならないため,テストケースの作成自体が開発者側への大きな負担となっている.本発表では,Webアプリケーション開発フレームワークにおける,テストケースの自動生成機能を提案し,実装を行った.対象とする開発フレームワークは,現在主流になっているRuby on Railsとし,Railsのテストツール機能の1つである機能テストにおいて実装した.本システムでは,開発者は全体の入力値の一部を与えることで,不足している入力値を補完しつつテストケースが生成される.また,オープンソースのRailsのWebアプリケーションに対して本システムを適用し,多くのテストケースが自動生成されることを確認した.Many Web application frameworks provide testing tools for supporting development of Web applications. The testing tools automatically test a Web application with a set of test cases given by a developer. However, the developer should carefully designate the set of test cases to achieve precise tests. We propose and implement an automatic test case generation system for a Web application framework. Our system works for the Web application developed with Ruby on Rails which is widely used. It provides a set of test cases for functional tests on Rails from only a part of input values designated by a developer. Furthermore, we demonstrate that our system can automatically generate many test cases for open-sourced Web applications developed with Rails.

著者

田中 哲

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.7, no.3, pp.51-51, 2014-07-14

---

本発表ではプログラムを逆方向にも実行可能なプログラミング言語Conservationを提案し,例としてX.509証明書のエンコーダとデコーダを記述する.また応用として,エンコーダを修正して間違った証明書を生成し,既存の暗号ライブラリに対してファジングを行う.通信プロトコルやデータフォーマットなど,データをプロセスの外部で表現するためにはデータをバイト列にエンコードし,また,逆にバイト列をデータにデコードすることが欠かせない.エンコードとデコードは対になる処理であるが,通常は別々に開発するため,正しく対応がとれた実装になるとは限らない.本発表ではプログラムを逆方向にも実行可能なプログラミング言語によりエンコードとデコードをひとつのプログラムとして記述可能とする.それにより常に正しく対応のとれたエンコーダとデコーダが開発できる.また,開発における利点だけでなく,ファジングにも利用できることを示す.This presentation proposes a reversible programming language: Conservation. We implemented encoder and decoder for X.509 certificates as an example program. Also, we modify the encoder to generate wrong certificates and fuzz existing cryptographic library. Implementation for communication protocols and data formats needs encoder (converter from a data structure to a sequence of bytes) and decoder (converter from a sequence of bytes to a data structure). Usually they are implemented individually and not guaranteed to be inverse functions of each other. This presentation explains the language can be used to implement a pair of encoder and decoder with single program. The program can run forward to work as an encoder and run backward as a decoder. The behaviors are guaranteed to be inverse functions. This means correct program can be implemented with less effort. The program can also be used for fuzzing by modifying the encoder.

著者

塚田 武志 小林 直樹

出版者

情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.4, no.2, pp.31-47, 2011-03-25

---

言語の包含判定問題とは,与えられた言語 L1 と L2 について L1 ⊆ L2 が成立するか否かを判定する問題であり,理論的な興味の対象であるだけでなく,プログラム検証などへの広い応用を持つ重要な問題である.この問題に関する既知の最も強い結果の 1 つが文脈自由言語と超決定性言語の包含判定の決定可能性である.このオリジナルの証明は,Greibach と Friedman によって与えられている.我々はこの問題に対して,小林らによって提案されている型に基づく言語の包含判定の手法を適用し,決定可能性に対する別証明を与えた.この手法は以下のような利点を持つ.(1) 部分型関係やポンプの補題などのよく知られた概念で理論が展開できる.(2) 型推論を効率的に行う方法は多数提案されており,それらを利用することができる.また,提案する証明は小林らのアイデアを正規言語よりも広いクラスに適用したはじめての例であり,その他の非正規言語クラスへの応用も期待される.The language containment problem, which asks whether L1 ⊆ L2 for given languages L1 and L2, is an important problem in the field of formal language theory and has a variety of applications including program verification. One of the strongest result about this problem is the decidability for the case where L1 and L2 are context free and superdeterministic languages respectively, originally proved by Greibach and Friedman. In this paper, we give a new proof of the decidability, inspired by Kobayashi's type-based approach to language containment problems. The new proof has the following advantages. (1) The key notions and lemmas in the proof are well-known ones, such as subtyping and Pumping Lemma. (2) We can apply well-studied techniques for efficient typability checking. Furthermore, our proof is the first application of the type-based approach to the inclusion between non-regular languages and it seems applicable to other cases.

著者

上里 友弥 南出 靖彦

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.7, no.4, pp.8-20, 2014-08-29

---

本論では,言語が決定性文脈自由言語(DCFL)ではないことを証明するための,決定性プッシュダウンオートマトン(DPDA)に基づく手法を提案する.提案する手法は,計算中でのスタックの高さを特徴付けるもので,以下のようなスタックの変化に対する直感を形式的に扱うことができる:言語{anbncn | n ≧ 1}が何らかのDPDAで受理できたとすると,aの個数とbの個数を比較した結果として,anbnの部分を読み終わった段階のスタックはほとんど空になっているはずである.このとき,続く文字列cnを検査することができない.したがって,この言語はDCFLではない.具体的には,十分に長い繰返し文字列を消費した結果のスタックの内容には繰返し構造があることを示し,繰返し文字列を消費した結果のスタックが一般化順序機械と呼ばれる機械で定義可能であることを示した.この結果を用いて,上の例のようにaの個数とbの個数を比較するためには,スタックがほとんど空にならなければならないことを形式化して示した.

著者

田村 知博 高野 保真 岩崎 英哉

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.1, no.2, pp.28-41, 2008-09-26

---

実行効率の良い探索プログラムを書くためには,結果に寄与しない計算を除去する枝刈りが有効であるが,一般に,簡潔なプログラム構造を保ったまま枝刈りの記述をすることは難しい.この問題点を解決するために,Improving Sequence(IS)というデータ構造を用いる手法が提案され,有効性が確認されている.ISとは,ある全的に定義された推移的な二項関係に従い,要求駆動によって単調に最終結果へ近づいていく近似値の列のことである.ISを用いたプログラムでは,枝刈りをするか否かの判断に近似値を用いることができる.従来の純関数型言語上のISの実装はライブラリによるものだったので,近似値の数に比例したヒープ領域を必要とし,効率があまり良くないという問題点があった.この問題点を解決するため,本論文では,ISの近似値が持つ単調性に着目し,また,近似値が枝刈りの判断にのみ用いられ,中間データとしての役割しか持たないことを前提として,純関数型言語において,定数領域しかヒープを消費しないISの実装を提案する.提案手法の効果を確認するため,Glasgow Haskell Compilerに実装を施し,ナップサック問題など,いくつかのプログラムで実験を行った.その結果,問題によってばらつきはあるものの,メモリ消費量において3%~75%程度の減少が見られ,安定的に改善できることが確認できた.また,メモリ消費量を削減することで,多くの場合に実行時間を改善できることも確認できた.

著者

東 達軌 武田 正之

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.3, no.5, pp.30-30, 2010-12-10

---

近年では,計算の対象としてあげられる問題は多様化しており,様々な問題領域の構文や意味論を任意に設定可能であるようなプログラミング環境が望まれている.本研究では,そのような汎用のメタプログラミング環境の構築を目的としている.本発表ではそのような環境で用いる計算モデルの1つとして,リフレクティブなグラフ書換え言語REGRELを提案する.REGRELは頂点と接続の両方にラベルを持つ有向グラフを書換え対象とするグラフ書換え系である.プログラムの構造やその値をグラフで表現し,計算の意味を書換え規則で表現する.書換え規則自体もまたグラフで表現されているため,高階書換えを行うことが可能である.そして,高階書換えによってリフレクションを表現することができる.REGRELの動作は並行動作,非決定性動作を基本としている.逐次動作,決定性動作はその特別な場合として扱う.また,分類と呼ばれる機構を持ち,書換え規則の適用範囲を制限することができる.本発表ではREGRELの定義を示し,その応用としてアクターモデルなどいくつかの計算モデルの表現方法を示す.また,評価戦略の決定や計算順序の制御など基本的な言語機能の表現を,REGRELの基本機能によって表現できることを示す.最後に,他のグラフ書換え系との比較について論じる.Domains for computational application become diverse and programming environment that can use various syntax and semantics for such domains is required. We propose reflective graph rewriting language REGREL to implement such multipurpose meta programming environment. REGREL is graph rewriting system, which rewrite digraphs that have labeled nodes and arcs. Program structures and values are represented by graph, and semantics is represented by rewriting rules. Rewriting rules are also expressed by graphs. Thus, higher-order rewriting rules are able to realize reflection. The REGREL's behaviors are based on concurrent and nondeterministic operations, and sequential/deterministic behaviors are special cases for them. And, REGREL has a classification mechanism, which limit the scope of rules. In this presentation, we show definitions of REGREL at first, and describe to express other computational models such as the actor model by REGREL. It is shown that REGREL can controll computational sequences and customize the evaluation strategies using basic functions. At last, we discuss comparisons between REGREL and other graph rewriting systems.

著者

遠藤 仁 前田 敦司 山口 喜教

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.4, no.4, pp.38-38, 2011-09-22

---

CPU の性能向上手法がクロックの高周波化からマルチコア化へとシフトした現在,CPU の性能を活用するために処理の並列化を図ることはますます重要性を増している.広く用いられているプログラミング言語の構文解析手法の多くは,有限の (多くの場合 1 つの) トークンを先読みすることによって逐次的に処理を進めるものであり,並列化は困難である.筆者らは,バックトラックによる再帰下降構文解析とメモ化を組み合わせた構文解析アルゴリズムである packrat parsing において,下位の非終端記号の解析結果を記録するメモ化表を,別のスレッドを用いてあらかじめ埋めておくことによって,上位の構文解析スレッドの動作を高速化できるのではないかと考えた.本研究では,Medeiros らの PEG 仮想マシンにメモ化機能を加えて packrat parsing 仮想マシンとし,さらに上記のアイディアを用いて並列化を行った.PEG で表記した文法を与えると,構文木を作成する並列 packrat parser を生成するパーザジェネレータを試作し,生成されたパーザに対して実際のプログラムを入力として評価実験を行い,並列処理の有効性を確認した.Parallelization of programs is getting more importance because recent performance improvement is driven mainly by increasing number of cores, rather than increase in clock frequency. Many of parsing algorithms used in programming language implementations rely on directing their actions by lookahead of finite (in many cases, only one) tokens, thus severly limiting the possibility of parallel processing. Packrat parsing is a variant of backtracking recursive descent parsing combined with memoization. In packrat parsing, memoization table for low-level nonterminals can be filled by distinct prefetch thread to accelerate processing of higher-level nonterminals. Following the idea, we have parallelized packrat parsing abstract machine, which is based on PEG machine by Medeiros. We built a parser generator that generates parallel packrat parser from grammar description written in PEG. We evaluated performance of the generated parser using real program as input, confirming the effectiveness of our approach.

著者

伊藤陽 小濱 真樹 佐々 政孝

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.46, no.14, pp.30-42, 2005-10-15

被引用文献数

3

---

SSA 形式(静的単一代入形式)は,φ 関数という仮想的な関数を用いることで,変数の定義を字面上1 カ所だけになるように表した中間表現である.しかし,SSA 形式を用いたプログラム中に現れるφ 関数が仮想的であることから,SSA 形式から直接目的コードを出すことはできない.そこで,目的コードを出す前段階として,φ 関数を消去して通常形式に戻すことが必要である.これをSSA 逆変換と呼ぶ.SSA 逆変換には主なアルゴリズムが2 つある.以前から用いられているBriggs らのアルゴリズム,およびこれとは異なるアプローチによるSreedhar らのアルゴリズムである.SSA 逆変換アルゴリズムはそれぞれ異なった特徴を持つが,これらを実際に比較した研究はほとんどなされていない.このため,SSA 形式を最適化コンパイラに採用するにあたって,どのSSA 逆変換を用いるかの選択の指標となるものがなかった.そこで本研究では,Briggs らとSreedhar らのアルゴリズムの長所と短所を明確にした.また,Briggs らのアルゴリズムに対する改良案を提案した.さらに,Briggsらのアルゴリズムとその改良案,Sreedhar らのアルゴリズムの3 つを実装し,同一のコンパイラ上で,SPEC ベンチマークを用いて種々の条件を変えながら比較した.本研究により,Briggs らの方法ではコアレッシングすることのできないコピー文が数多く挿入されること,実証的にはSreedharらの方法が最も優れていること,が判明した.The SSA form (static single assignment form) is an intermediate representation where the definition of each variable appears only once in the program by using a hypothetical function called φ-function. However, since the φ-functions appearing in the program using the SSA form are non-executable, the target code cannot be directly generated from the SSA form. Therefore, it is necessary to delete the φ-function and put the SSA form back to the normal form before generating the target code. This conversion is called SSA reverse translation'. There are two major SSA reverse translation algorithms. One is the method by Briggs et al., which is used from relatively early times. The other is the method by Sreedhar et al., which is based on a completely different approach. So far, there has been almost no research that actually compares these SSA reverse translation algorithms, although each algorithm has different characteristic features. Therefore, there have been no criteria as to which SSA reverse translation algorithm should be selected when the SSA form is used in an optimizing compiler. In this paper, we clarify merits and weak points of algorithms by Briggs and Sreedhar. We also propose an improvement of the algorithm by Briggs. Then, we implement algorithms by Briggs and its improvement and the algorithm by Sreedhar on the same compiler, and compare the three by changing the various environments using the SPEC benchmarks. The experiment has shown that the method by Briggs inserts a lot of copy statements that cannot be coalesced. Empirically, the method by Sreedhar is the most efficient.

著者

湯淺 太一 中川 雄一郎 小宮 常康 八杉 昌宏

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.41, no.SIG09(PRO8), pp.87-99, 2000-11-15

---

Lispなどの大多数のリスト処理システムでは,不用セルを回収するためにごみ集め(GC)が行われる.一般的に採用されているGCは,ごみ集めの間プログラムの実行が中断されるので実時間処理には適さない.この問題を解決するために,ごみ集めの一連の処理を小さな部分処理に細分化し,プログラムの実行と並行してごみ集め処理を少しずつ進行させる実時間方式のGCが提案されている.代表的な実時間GCであるスナップショットGCは,スタックなどのルート領域から直接指されているセルをGC開始時にすべてマークしておかなければならない.この間の実行停止時間は,ルート領域の大きさによっては,無視できなくなる.そこで,関数からのリターン時にマーク漏れがないようにチェックすることで,スタックから直接指されているセルを関数フレーム単位でマークする方法を提案する.スタック上のルート領域をフレーム単位でマークしていき,ある関数からリターンする際に次の関数フレームがマークされているかどうかをチェックし,マークされていなければその関数フレームをマークしてからリターンする.これをリターン・バリアと呼ぶことにする.ルート領域のマークが終了したら,従来のスナップショットGCと同様に残りのセルをマークする.本論文では,Common Lisp処理系KCL(Kyoto Common Lisp)上でリターン・バリアを実装し,GCによる実行停止時間について,従来のスナップショットGCと比較評価および検討を行った.

著者

山田 英史 中居 祐輝 山根 智

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.6, no.3, pp.1-19, 2013-12-20

---

近年の組込み機器の多機能化を受け,消費電力の抑制や小型化のために動的再構成可能プロセッサ(DRP)が注目されている.本稿では,CPUとDRPから構成される動的再構成可能システムを対象とした仕様記述言語を提案する.提案する仕様記述言語では,線形階層ハイブリッドオートマトンとオブジェクト指向を組み合わせることで,システム構成の動的変化を表現している.また,提案言語を対象とした検証器を開発し,その有効性を実証する.Recently, embedded systems begin to have various functions, Dynamically Reconfigurable Processor (DRP) draws attention to solution for the miniaturization and saving energy. In this paper, we propose the specification language for Dynamically Reconfigurable System, which is composed of CPU and DRP. The proposed language describes dynamically changing the system using Hierarchical Linear Hybrid Automaton and Object Orientation. Then, we develop the verifier for the proposed specification language, and verify the system.

著者

西崎 真也 樋口 貴志

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.41, no.9, pp.103-103, 2000-11-15

---

本論文では,ファーストクラス環境の機構を用いて単一化機構を関数型言語へ組み込む方法を提唱する.単一化子は変数上の代入として表現されるが,これを変数の束縛する環境とを同一視することにより,単一化の機構を関数型言語へ自然に組み込むことが可能となる.In this paper, we propose a way of embedding of the unification mechanism into function languages through facility of first-class environments, where unificands are introduced as expressions and their evaluation is defined as the first-order unification.

著者

吉川 隆英 近山 隆

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.41, no.SIG09(PRO8), pp.78-86, 2000-11-15

---

世代GC方式は,データ割付領域を生成後間もないデータを配置する新世代領域と長寿命データを配置する旧世代領域とに分割することにより,長寿命データが何度もGCを経験するのを防ぐとともに,データ局所性の向上を図るメモリ管理方式である.世代GC方式においては,新世代領域から旧世代領域への移動(殿堂入り)時期の適切な選択が性能を大きく左右する.通常,殿堂入り時期はデータのGC経験回数によって決定される.そして,GCは新世代領域を使いきった時点で発生する.したがって,新世代領域サイズを動的に変更すれば,殿堂入り時期は動的に変更できる.本稿では,GC時に回収されるゴミの比率のモデルに基づきデータの平均余命を推定,その結果に沿って新世代領域サイズを動的に変更することによって,殿堂入り時期を適切に調節する世代GC方式を提案する.また,この方式を並行並列論理型言語処理系KLICに実装し評価を行った結果も述べる.

著者

志田 駿介 井出 真広 倉光 君郎

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.6, no.4, pp.1-9, 2013-12-25

---

本研究の目的は静的型付けを特徴とするスクリプト言語Konohaの処理系をLego社が開発したプログラム可能なロボットシステムであるMindstorms NXT上に移植し,Konohaのスクリプトを動作させることである.Mindstorms NXTはARM7 CPUと64kB RAMを搭載したロボットであり,Konoha処理系とリアルタイムOS TOPPERSの使用するメモリの合計を64kBに抑える必要があった.我々はMindstorms NXT上で動作するKonoha処理系をTinyKonohaと名付け,パーサや各ランタイムのコンパクト化を行った.最終的にTinyKonohaの使用したメモリ量はコード領域,スタック領域,ヒープ領域合わせて32kB程度となり,VM命令セットやオブジェクト構造の再設計を行った言語ランタイムを開発した.その結果,組み込みシステム技術協会が主催するETロボコンの公式コースを走行可能な規模のスクリプトを実行することが可能であった.本論文ではTinyKonohaの設計,省メモリ化の工夫を詳細に報告し,メモリ使用量の評価とともに省メモリ環境のスクリプト処理系開発の知見をまとめる.We present a small-size scripting language interpreter named TinyKonoha, which is originally developed as statically typed scripting language Konoha, that can be executed on Mindstorms NXT. Mindstons NXT is a robot developed by Lego Inc. and has ARM7 CPU and 64kB RAM. We set a goal to execute the script that can controls Mindstorns NXT and can read a value from sensors. Our language processor is based on static typing script language Konoha and we called it TinyKonoha. The memory usage of TinyKonoha gets to less than 32kB including code segment, stack segment and heap segment and we developed a new language runtime. In the result, writing a script, which can run the course of ET Robot Contest hosted by JASA, becomes possible. In this paper, we present the design and the implementation of TinyKonoha, the method of simplifying the language processor and the actual memory usage of TinyKonoha.

著者

鈴木 貢 寺島 元章 渡邊 坦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.42, no.11, pp.102-102, 2001-11-15

---

マークアンドスイープ法に基づく固定長セルを対象とした並列ごみ集め(GC)を提案する.従来のGCは印付けと回収が直列的に実施されるのに対し,本GCではそれらが並列に実施される.これによってGCの処理能力が増し,セルを消費する複数のプロセスに対応できる.その特徴は,印付けを行いながら回収を行う「尺取り虫印付け法」と,複数プロセスの効率の良いセルの確保を可能にする「フリーセルのクラスタ化」である.印付けは,スタックを使ったリスト辿り法を用いているので,それに要する時間は使用中セルの個数に比例する.また,本GCでは,従来の印付け回収法では必須であった回収時の印の取り外しを行わない.そして,印付けプロセスと回収プロセスが印をめぐって際どい部分に入ることがほとんどなく,両者は本質的に非同期に稼働しうる.A parallel garbage collector (GC) based on mark-and-sweep method for fixed size cells is presented. It enables parallel running of both marking process and collection process, while previous parallel GCs do not permit such parallel running. With this method, we can get enough high performance GC to support multiple processes which consume cells. The distinguished technical points of this paper are "Inchworm marking" which enables parallel running of marking and collection, and "Clustered free cells" which improves allocation time overhead for multiple mutators. We adopts list traversal method with stack for marking, and the marking process can be completed in a time proportional to the amount of in-use cells. Our GC does not reset the marks of the cells, while others does. The marking process and the collection process rarely enter into critical region for marks, and they essentially can run asynchronously.

著者

神谷 知行 坂本 一憲 鷲崎 弘宜 深澤 良彰

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.6, no.3, pp.33-45, 2013-12-20

---

リファクタリングはコード体質改善の手法として広く知られているが,手動での実行はコストが高く欠陥を埋め込みやすいため,リファクタリングツールが多数提案されている.しかし,これらのツールは単体の単純なリファクタリングの実行を支援するものであり,リファクタリングによるデザインパターンの導入など,複雑なリファクタリングを行うのは難しい.すなわち,単体のリファクタリングを複数種類組み合わせて逐次実行したり,複数箇所に対してあるいは複数回数繰り返してリファクタリングを実行したりすることは困難である.そこで我々は,Javaソースコードを表現可能なモデルを用いて,リファクタリング内容やその適用箇所の指定を記述できるスクリプトおよびその処理系を提案する.複雑なリファクタリングを簡潔に記述でき,少ないコストで複雑なリファクタリングを実行できること,またプロジェクト横断的に再利用できることを評価実験で確認し,本手法の有用性を示した.

著者

坂本 諒 千葉 雄司 久保田 光一 土居 範久

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.4, no.2, pp.48-66, 2011-03-25

---

本論文では SH4A 向けコンパイラにおいて浮動小数点演算の演算精度を指定する命令を選択し,挿入先を定める手段として,0-1 整数計画法を利用する手法を提案し,その実用性を評価した結果を示す.SH4A は浮動小数点演算命令の実行時にどの精度で演算を行うか指定するための命令を 2 種類提供するが,それぞれ挿入可能な箇所と実行コストが異なる.このため SH4A 向けコンパイラでは,どこでどの命令を使って精度の指定を行うべきか判断する必要があるが,提案技法ではこの判断に 0-1 整数計画法を利用する.また,0-1 整数計画法がコンパイル時間に与える悪影響を軽減するために,挿入箇所を求める問題を分割,簡約化する技法も提案する.分割や簡約化を適用しても最適解の探索に膨大な時間がかかる場合はあるが,そのような場合には最適解を求めることを諦め,探索を中断してヒューリスティックにより解を求める.組み込み機器向けベンチマーク EEMBC benchmark suite および組み込みプロセッサ向けベンチマーク CoreMark を使って評価したところ,提案技法でコードサイズを最適化すると,コードサイズを 1.2% 小さくできることが分かり,このときコンパイル時間の増加率は相乗平均で 13.5% になり,最適解を求ることができた問題の比率は 99.9% 以上になることが分かった.また,CoreMark を使って評価したところ,提案技法で実行サイクル数を最適化すると,最適化しない場合と比べ,精度指定にかかる実行サイクル数と,アプリケーション全体の実行サイクル数をそれぞれ 64.1% と 3.1% 削減できることが分かった.