著者

今城 哲二 大野 治 植村 俊亮

雑誌

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

巻号頁・発行日

vol.41, no.SIG02(PRO6), pp.106-106, 2000-03-15

---

約20年前からコンピュータでの漢字利用が普及し,標準プログラム言語で日本語データ処理が可能となった.日本語処理は,国際化と一般化されて,国際規格化された.いくつかの言語では,識別名にも漢字などマルチオクテット文字が使用できる.予約語まで日本語にした本格的な日本語プログラム言語も,分かち書きのレベルで,実用化されている.本発表では,より日本語に近い非分かち書きの日本語プログラム言語「まほろば」を提案し,その構文の設計の考え方を中心に論じる.

著者

千葉 雄司 大石 圭一 永井 佑樹 中川 満

雑誌

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

巻号頁・発行日

vol.12, no.1, pp.1-9, 2019-01-30

---

RL78マイコンのようなアキュムレータマシンでは,多くの命令において,オペランドとして使えるレジスタがアキュムレータのみとなっており,その結果,命令スケジューリングの際に,命令を単独で移動しようとしても,アキュムレータに関する依存に移動を阻まれることが多い.この問題を回避して命令をスケジュールする方法として,移動の対象を,単独の命令ではなく,命令列,具体的には,アキュムレータに値を代入する命令から,代入した値を最後に利用する命令までの命令列にする方法を提案する.提案した方法をRL78マイコン向けCコンパイラ製品CC-RLの命令スケジューラに適用し,その効果を,CoreMarkやFFT,SHA256などのベンチマークによって評価したところ,最大で2.12%実行を高速化できることが分かった.

著者

村田 康佑 江本 健斗

雑誌

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

巻号頁・発行日

vol.11, no.4, pp.1-12, 2018-12-14

---

数学定理やプログラムの性質の形式的証明では,自然数上の不等式についての証明が頻出する.しかし,定理証明支援系Coqでの不等式の形式的証明は,非形式的証明とは異なる記法で記述されるため,数学的な直観がそのまま使えないことも多い.たとえば,非形式的証明では,不等式L ≤ Rを証明するために,しばしばL = M1 ≤ M2 = M3 ≤ ・・・ ≤ Mn = Rのように項を不等号で「鎖状」につなげて示す宣言的な記法が用いられる.こうした記法は数学の教科書等でよく馴染んだ記法であり,直観的に理解・記述することが可能である.一方,Coqにはそうした宣言的な記法は標準では用意されていないため,証明の理解・記述が困難になっている.本論文では,Coq上で,自然数上の不等式変形を,非形式的証明のように「鎖状」に記述する手法を提案する.本手法の特徴は,タクティックライブラリによって「鎖状」記法が実現されることにあり,それゆえ,提案記法はライブラリをモジュールとして読み込むだけで既存記法とあわせて使うことができる.また,このタクティックライブラリを用いて,Ackermann関数の性質についての不等式の証明を試みる.その結果,標準的な数学の教科書と近い記法で形式的証明を記述できることを確認する.

著者

山根 雅司 山崎 淳 阿部 正佳

雑誌

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

巻号頁・発行日

vol.1, no.3, pp.1-10, 2008-10-27

---

本発表では,自動エラーリカバリ機構を持つパーサジェネレータ yayacc の設計と実装を述べる.yacc や bison をはじめとして,現在広く使われているパーサジェネレータでは,文法中に特殊なエラーリカバリ動作を指示するトークンを手動で挿入させることで,エラーリカバリパーサを生成している.この古典的な手法は本来の文法定義を変えてしまうことに起因する深刻な問題があり,正しいエラーリカバリを行うパーサを生成させるには,多くの勘と経験が必要とされる.一方,yayacc ではエラーリカバリのために,文法を修正するというこがいっさい不要であり,生成されるパーサは従来の error トークン手動挿入によるパーサでは理論的に不可能な優れたエラーリカバリを自動的に行う.さらに yayacc では意味動作の Undo も自動で行うことが可能である.これは先行研究における自動エラーリカバリパーサでは扱われていないが,字句解析が完全に分離できない文法,たとえば C 言語に対しても自動的なエラーリカバリを行う場合に必要となる重要な機能である.yayacc は筆者らが開発している SCK コンパイラキットのツールの 1 つとして作成されたものである.現在 ANSI C言語,および小規模な関数型言語のパーサは yayacc により自動生成されたものを使っており,きわめて優れたエラーリカバリが行われている.

著者

丸山 冬彦 小川 宏高 松岡 聡

出版者

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

雑誌

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

巻号頁・発行日

vol.40, no.10, pp.39-50, 1999-12-15

被引用文献数

1 1

---

機械語命令列から同じ意味のソースプログラムを復元するデコンパイルという技術は古くから知られており 主に リバースエンジニアリングのための手段の一つとして利用されてきた.実際に Javaとそのバイトコードに関しても いくつかの処理系が提案されているが これまで提供されてきた処理系では Java言語には無いgotoを挿入するなど Java言語の文法を逸脱した結果を出力することがある.また デコンパイルのアルゴリズムがアドホックで 応用の利かないものであるため 我々のOpenJITコンパイラが要求するような 任意のバイトコードから正しいソース構造を復元するでコンパイラフロントエンドとして用いることができない.そこで 我々はJavaバイトコードから適切なJava言語の制御構造を復元するための効果的なアルゴリズムを新しく考案した.アルゴリズムの基本となる考え方は メソッドのコントロールフローグラフに対するドミネータツリーを用いるものである.これはブロック構造が完全な入れ子になる言語の場合 制御構造を表す任意のプログラム片はドミネータツリーにおいて ただ一つのサブツリーをなすという性質に基づいている.この一般性により アルゴリズムはJava以外の言語に適用することも可能である.OpenJITでの予備的な実装による評価では 他のデコンパイラが制御構造の復元に失敗するプログラムであっても 我々のアルゴリズムは適切にそれを復元し かつ 実行速度は同程度であることを示した.The technique called decompilation that reads sequences of machine code and generates the corresponding source program has been known for some time, and utilized primarily for reverse-engineering. For Java and its bytecode, although there have been several proposals of decompilers, most generate outputs that are inappropriately extend the Java language, such as insertion of gotos not present in Java. Moreover, the decompilation algorithms are somewhat ad-hoc and difficult to extend of verify its applicability, which is a hindrance to out OpenJIT compiler which requires a decompiler frontend to recover the correct source structure from arbitrary bytecode. Instead, we have devised a new and effective algorithm for decompilation, with emphasis on properly recovering control structures. The key idea is to base the algorithm around the dominator tree of the control flow graph of a method. This is based on the observation that, for a properly-nested block-structured language, each part of program representing a control structure corresponds to just a single subtree in the dominator tree. As such, the algorithm is general enough to be applied to other languages besides Java. The evaluation of our preliminary implementation in OpenJIT shows that our algorithm properly recovers control structures where other existing decompilers fail, and with relatively equivalent execution speeds.

著者

五百蔵 重典 西尾 孝典 野木 兼六

出版者

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

雑誌

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

巻号頁・発行日

vol.48, no.10, pp.199-199, 2007-06-15

---

ヒープに確保された使用されていないオブジェクトを自動的に回収するガーベジコレクション機能(以下,GC)は,プログラマのメモリ管理の負担を軽減するための重要な機能である.GC アルゴリズムの中には,GC で生き残った古いオブジェクトは若いオブジェクトよりも長く生き残るという経験則を利用して,新しく作成されたオブジェクトのみをGC の対象とすることで,処理速度を向上させる世代別GC アルゴリズムがある.しかし世代別GC アルゴリズムは,古い領域から新しい領域へのリンクを検出する処理(以下,ライトバリア)が必要である.そして,そのライトバリアは実行時間のオーバヘッドになること,処理系を実装するために必要な箇所にライトバリアを配置することは煩雑であることから,世代別GC アルゴリズムを効率良く実装することは難しいのが現状である.そこで本発表では,先頭側の領域をold 領域,末尾側の領域をnew 領域に分断し,old 領域に属しているオブジェクトはすべて古いオブジェクトと見なす新しい世代別GC アルゴリズムを提案する.本発表のアルゴリズムでは,old 領域ではnew 領域へのポインタが存在するかを検査し,new 領域ではGC を行う.本発表のアルゴリズムの特徴として,ライトバリアが必要ない,メジャーコレクションとマイナーコレクションが一体化している,および生きているオブジェクトの移動を必要としないなどがあげられる.本発表では,提案アルゴリズムをオブジェクト指向スクリプト言語であり,マーク&スイープ型の保守的GC を備えるRuby 上に実装した結果,全体の処理時間は最高90.8%に短縮でき,1 回のGC 時間では最高70.8%に短縮することができたことを示す.Garbage collection (GC) algorithms which collect unused objects in heap memory automatically are important technology, because there free programmer from memory management. There are Generation GC algorithms which try to collect unused object in only heap area are which contain new objects (new-area), using the experience that many younger objects tend to be unused object soon after allocate, and used objects after GC tend to keep being used, therefore Generation GC algorithms improvement execution time. But, Generation GC algorithms need program code which search for link from old-area to new-area (hereafter, write-barrier code). Then write-barrier code has over-head at program execution time and needs to set many write-barriers appropriately in language processor. Therefore we are difficult to implement Generation GC algorithm. We propose new Generation GC algorithm which we assume that head-side of heap area is old-area, and tail-side of heap area is newarea. The framework of this algorithm searches pointers from old-object to new-object in old-area, and applies to GC in new-are. The character of this algorithm don't need writebarrier, a distinction of combines major collection and minor collection is a little, and don't move old-objects in old-area. We implement this algorithm in object-oriented script language Ruby which have conservative mark & sweep GC algorithm. We show that execution time is 90.8% at a maximum, and one GC time is 70.8% than original ruby.

著者

松本 行弘

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.2, no.2, pp.27-36, 2009-03-23

---

多くのスクリプト言語において多言語テキスト処理は Unicode を固定的な内部文字コードとして採用しているが,その場合,Unicode 以外の文字集合で表現されたテキストを処理するためには文字集合間の変換が必要になり,文字集合間の互換性や文字集合における歴史的な事情などによりさまざまな問題を引き起こす可能性がある.そこで筆者が開発しているスクリプト言語 Ruby に対して,固定的な内部文字集合を持たない文字集合独立方式を採用し,文字集合間の変換をできるだけ行わないテキスト処理機能を実装した.本論文で述べる Ruby の多言語テキスト処理機能は,Unicode を固定的な内部文字集合とする他スクリプト言語 (Perl および Python) と比べて,テキスト処理におけるプログラムの簡潔さおよび性能において劣らない実用的なものであることを示す.本論文で述べる多言語テキスト処理機能は Ruby バージョン 1.9 として公開されている.Many scripring languages of present days use Unicode as their universal internal character set to manipulate multilingual text processing. But due to character set compatibility and other historical issues, text conversion to/from the universal character set may cause various problems. We designed and implemented character set independent multilingual processing, which avoids character set conversion as much as possible. We show that multilingual text processing in Ruby is practical in both productivity and performance, comparing other scripting languages, e.g. Perl and Python. The work described in this paper is publicly available in Ruby version 1.9.

著者

森 翔太郎 近森 凪沙 鵜川 始陽

雑誌

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

巻号頁・発行日

vol.13, no.3, pp.15, 2020-06-17

---

組込みシステム向けにコンパクトに開発されたmRuby/cというRuby処理系がある.組込みシステムの実行環境は一般にメモリが少なく,CPUも非力であるため,時間的オーバヘッドや空間的オーバヘッドが小さい方法でにプログラムを処理する必要がある.現状のmRuby/cのガベージコレクタ(GC)には,参照カウント方式が採用されている.参照カウント方式は,再帰的なオブジェクトの解放が起こらない限り停止時間が短いという利点がある.しかし,参照カウントの操作は時間的なオーバヘッドとなる.また,各オブジェクトが持つ参照カウントを保持するフィールドも空間的なオーバヘッドとなる.さらに,循環参照を回収できないという問題もある.そこで本研究では,mRuby/cで参照カウントの妥当性を調査する.そのために,比較対象としてマークスイープGCを実装する.そのうえで,いくつかの性質の異なるベンチマークプログラムを用いて停止時間や時間的,空間的オーバヘッドの面で比較する.

著者

今泉 良紀 篠埜 功

雑誌

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

巻号頁・発行日

vol.11, no.3, pp.24, 2018-09-20

---

PEG(Parsing Expression Grammar,解析表現文法)は文法規則に曖昧さのない形式文法であり,プログラミング言語の構文記述に有用である.PEGによる文法は再帰下降構文解析器と対応しているため,パーサコンビネータによる簡易な実装によってPEGの文法から実際に動作するパーサが得られる.特にEDSL(Embedded Domain Specific Language)によるパーサコンビネータ実装は,パーサの記述のし易さを確保しつつ,意味規則の記述などの点でホスト言語との接続が簡潔であるという利点がある.また,バックトラックのある再帰下降構文解析器は素朴な実装では入力長に対して最悪指数関数時間を要するが,再帰下降構文解析にメモ化を組み合わせたパックラット構文解析という手法によって入力長に対して線形時間で解析が可能となる.本発表では,C++で記述されたPEGに基づくパーサコンビネータ実装として,Boost.Spirit.X3,cpp-peglib,PEGTL,matcha2の4つの実装の実行性能について比較した結果と,これらの中で最も実行速度の速いmatcha2の実装の詳細について報告する.

著者

竹辺 靖昭 湯淺 太一

雑誌

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

巻号頁・発行日

vol.43, no.SIG08(PRO15), pp.98-109, 2002-09-15

---

現在の多くのWeb サイトでは,Web サーバ上で動作するプログラムで,データベースへのクエリを行い,動的にWeb ページを生成する処理が行われている.我々は,部分評価の手法を応用し,こうした動的Web ページの生成を高速化するシステムを開発している.このシステムは,Web サイトの開発において広く使用されているPHP という言語を対象とした部分評価器と,部分評価によって生成されたプログラムをWeb サーバに配置するシステムからなる.この部分評価器は,更新の頻度が低いデータを静的と見なすことにより,これらのデータへのクエリを部分評価時に行うことができる.部分評価および生成されたプログラムの配置は,これらのデータが更新されるタイミングなどで行われる.Web ページを生成する時点では,変換結果に残された動的な部分のみが実行される.これにより,リアルタイムに更新される情報を含むページやパーソナライズ機能を持つページなど,さまざまなタイプの動的Web ページを生成する負荷を低減することができる.本論文では,このシステムで使用している部分評価の手法および実装方法を紹介するとともに,パーソナライズ機能を持つWeb ページなどに対して実際にこの手法を適用した結果を報告する.

著者

新妻 弘崇

出版者

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

雑誌

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

巻号頁・発行日

vol.7, no.2, pp.38-38, 2014-06-10

---

本研究ではScheme言語(R4RS)の部分集合からC++言語へ変換する手法Scm2Cpp11の提案と実装を行う.Scm2Cpp11の生成するC++プログラムには編集が容易である点と,高速なプログラムであるという2つの特徴がある.Scm2Cpp11では型推論やalpha変換といった高度な操作を行わない.単純なプログラムコードの文字列置換のみでSchemeからC++への変換を行う.たとえば(car x)はcar(x)に変換される.単純な変換であるため,生成されたC++のプログラムは変換前のSchemeプログラムとの対応が容易に分かるようになっている.生成されたC++プログラムは編集が容易なため,OpenMPを使った並列化等も容易に行うことができる.またScm2Cpp11の生成するC++プログラムは他の良く知られた多くのScheme処理系より高速であるという特徴がある.高速となる理由は,単純な変換とするために,オブジェクトがデータ本体以外の型情報や環境情報などの付加情報を省かれて変換されるからである.たとえばSchemeの整数変数はC++のint型変数に変換される.int型変数に変換されるため,他の環境情報などを変換後のオブジェクトに格納しない.もう1つの理由は,Scm2Cpp11の変換はC++のtemplateやマクロの機能を使って,C++のコンパイル時の前処理として可能な限りの処理を行おうとする点である.このために,コンパイル時に前処理された後の実行プログラムが高速となる.We propose and implement a translation method Scm2Cpp11 that translates from the subset of the Scheme language (R4RS) into C++ Language. Scm2Cpp11 has two advantages. The first advantage is that Scm2Cpp11 generates an editable C++ code. The second advantage is that Scm2Cpp11 generates a quite fast C++ program. Actually Scm2Cpp11 is just string replacement operator for programming code. Scm2Cpp11 does not include other operations like type inference alpha-conversion and so on. For example, Scm2Cpp11 translates (car x) into car(x). Thus finding correspondence between original Scheme code and translated C++ code is quite easy. Adding well-known C++ library's function, for example OpenMP parallelization feature, to the editable translated C++ is also quite easy. A C++ program Scm2Cpp11 generates is faster than many other well-known Scheme implementations. Scm2Cpp11 translates a Scheme object into a C++ object which holds only data body. The translated C++ object does not have any additional environment information. For example, Scm2Cpp11 translates a Scheme integer variable into a C++ integer variable. The additional information are processed as a preprocess when C++ code compiled. The preprocess is described using C++ template and macro techniques. That is the reason why Scm2Cpp11 can generate efficient C++ programs.

著者

兼宗 進 御手洗 理英 中谷 多哉子 福井 眞吾 久野 靖

雑誌

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

巻号頁・発行日

vol.42, no.SIG11(PRO12), pp.78-90, 2001-11-15

---

情報社会の急速な発展にともない,初中等教育の中で情報の比重が高まっている.計算機の働きを最も効果的に学ぶ手段の1 つはプログラミングを体験することであるが,教育現場ではBasic やLogoといった数世代前の言語が使われることが多く,現代のソフトウェアシステムの理解につながらないという問題が存在する.本稿では,初中等教育での利用が可能なプログラミング言語「ドリトル」およびその実行系の設計と実装について述べる.ドリトルはオブジェクト指向言語であり,あらかじめ用意された各種のオブジェクトを活用した教育を可能とする一方,Self 言語と同様のプロトタイプ方式の採用により,クラスや継承などの高度な抽象概念の理解を不要にしている.その他,変数や命令語などの識別子と記号が日本語文字で統一されている,メソッドを属性と統合的に扱えるといった特徴を持つ.処理系はJava2 で書かれたインタプリタとして実装し,教育現場のさまざまな環境で動作できるようにした.

著者

坂口 和彦 亀山 幸義

雑誌

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

巻号頁・発行日

vol.10, no.1, pp.14-28, 2017-01-06

---

本研究は,対話的定理証明器Coqの有限型と有限ドメイン関数に関する既存ライブラリを改良し,従来のライブラリを用いた証明をほとんど変更することなく,その証明から抽出されるプログラムの効率を大幅に改善したものである.CoqのSSReflect/Mathematical Componentsライブラリは,有限型と有限ドメイン関数をサポートするライブラリfintypeとfinfunを提供し,これらのデータに対する証明の手間を大幅に削減することに成功している.しかし,その証明からプログラム抽出の手法で作成したプログラムは,多くの場合において非常に効率が悪いという問題がある.本研究では,fintypeやfinfunを改善したライブラリを実装した.このライブラリを用いて作成した証明から抽出したOCamlコードは,既存ライブラリの場合と比べて非常に高速である.例として,行列積の計算では,計算時間をおよそO(n5)からO(n3)へ改善できたことを示す.また,既存のSSReflectライブラリを用いたCoqの証明は,ほとんど書き換えることなく本研究のライブラリを用いた証明となる.例として,GonthierらのFeit-Thompson定理の約17万行におよぶ形式証明が,わずか10行以下の修正で,本研究のライブラリを用いた証明にできたことを示す.

著者

福室 嶺 千葉 滋

雑誌

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

巻号頁・発行日

vol.9, no.4, pp.16-26, 2016-09-12

---

本論文では,有効範囲を既知のコールパス上に限定することで安全に利用できるクラス拡張method sealsを提案する.クラス拡張は既存のクラスを拡張するための言語機構であり,RubyやAspectJ,C#など様々な言語に取り入れられている.クラス拡張を用いることで,既存のクラスに対してソースコードを書き換えることなくメソッドの追加や再定義を行える.しかし,クラス拡張はモジュラリティの向上に寄与する一方で,誤動作を引き起こしやすい.これはクラス拡張どうしの衝突や,クラス拡張が想定外の領域で有効になることが主な要因である.こうした問題を解決するために,プログラマのコードに対する理解度に応じてその有効範囲を段階的に拡張できるように設計されたクラス拡張method sealsを提案する.本機構では,プログラマにとって未知のパッケージのコードはブラックボックス内にあると見なし,クラス拡張が無効になる.また,ブラックボックス内から発するコールパス上ではそれ以外のコードも一時的にブラックボックス内にあるものと見なす.これにより,クラス拡張がブラックボックス内のコードに対して予期せぬ影響を与え,ひいてはプログラム全体の誤動作を引き起こすことを防げる.本研究ではRuby処理系上にmethod sealsを実装し,いくつかの条件下でその実行性能を評価した.

著者

櫻田 英樹

出版者

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

雑誌

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

巻号頁・発行日

vol.41, no.9, pp.8-24, 2000-11-15

---

本研究では,プログラミング言語における文脈と環境の関係を調べる.プログラミング言語において文脈とは,穴を持つプログラムのことである.文脈はプログラミング言語の操作的意味論を定義するときなどに用いられる.橋本,大堀(1996)は文脈をファーストクラスのオブジェクトとして持つ型付き ${エlambda}$ 計算を考えた.ファーストクラスの文脈を用いて,モジュールシステムやモバイルコードを柔軟に扱うことができると期待されている.一方,プログラミング言語において環境とは,変数の名前とその値の組の集合のことである.環境は局所的束縛を扱うためにしばしば用いられる.LISPのletなどは環境を作り,その中でプログラムを評価するものである.環境をファーストクラスのオブジェクトとして持つような ${エlambda}$ 計算はいくつかあり,佐藤,Burstall,桜井(1999)による ${エlambda}{エvarepsilon}$ はその1つである.ファーストクラスの環境を用いてオブジェクト指向プログラミングなどを扱うことができると期待されている.本研究では,橋本,大堀の型付文脈計算を,佐藤,Burstall,桜井の ${エlambda}{エvarepsilon}$ を用いて解釈し,解釈の健全性を証明した.また,これにより型付文脈計算が強正規性を満たすことが分かった.We investigate the relationship between contexts and environments in programming languages. In programming languages, a context is a program with a hole. We often use contexts in defining operational semantics of programming languages. Hashimoto and Ohori (1996) have studied a typed context calculus, a typed ${エlambda}$-calculus with first-class contexts. We expect that we can build flexible module systems using first-class contexts. On the other hand, an environment in programming languages is a set of variable-value tuples. We use environments to express local bindings. For example, ``{エtt let}'' construct in LISP creates an environment and evaluates a program in it. There are several works on ${エlambda}$-calculus with first-class environments. ${エlambda}{エvarepsilon}$ by Sato, Sakurai and Burstall (1999) is one of them. We expect that first-class environments are useful for object-oriented programming. In this work, we develop an interpretation of Hashimoto-Ohori's typed context calculus in ${エlambda}{エvarepsilon}$. We prove its soundness and show that the context calculus is strongly normalizing.

著者

白畑 有加 前田 敦司 山口 喜教

雑誌

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

巻号頁・発行日

vol.4, no.3, pp.97-97, 2011-06-29

---

プログラムの処理の流れを扱う概念に,継続がある.継続とは,ある処理のある瞬間における,「次にどのような処理を行うのか」 という処理過程の未来全体を表すものである.Scheme では継続をファーストクラスの機能としてサポートしており,call/cc 関数を用いて継続を扱うことができる.しかし,そのほかほとんどのプログラミング言語は継続を明示的に扱っていない.そのような言語に継続をファーストクラスの機能とし導入する手法として CPS 変換や例外処理を用いた手法など様々な研究がなされているが,導入後の実行効率が大幅に落ちてしまうという問題点をかかえている.本発表では対象言語を JavaScript とし,Pettyjohn らの手法をもとにした新しい,継続を導入する変換手法を提案する.変換後の実行効率の向上のため,継続から処理を再開するときのコードを別途定義する.これにより継続を使用しない場合の処理は変換前後で実行速度が変わらない.また,継続による処理の再開位置を示す Resumption Point を導入することで変換後のコードの重複を削減した.さらに,本発表では継続をキャプチャするタイミングに例外処理を用いる手法と 2 返戻値法の両方を使い分ける.このハイブリッドな継続のキャプチャ手法の採用により,さらに変換後の実行効率の向上を見込むことができる.Continuation is an idea which deals with flow of control inprograms. Although Scheme has continuation as a first-class feature, most other programming languages don't support it explicitly. Various approaches have proposed to adopt the continuation as a first-class feature in such languages, e.g., CPS conversion and stack-traversal and rebuilding using exception. But these conversions have significant impact on execution efficiency and slows down the execution of programs after conversion considerably. In this presentation, we propose a new transformation algorithm based on Pettyjohn, et al.'s approach, which can introduce continuation more efficiently to programming languages that don't support them (we use JavaScript as a specific example). To improve execution efficiency after transformation, we separately generate the code run in ordinary execution and the code executed when continuation is invoked. When executed without using continuations, the execution efficiency after transformation is almost equal to the one before transformation. Since we separately generate the code for two cases, code size may increase after conversions. This code expansion is reduced by sharing code using labels called Resumption Point, which marks the point to resume when continuations are invoked. We use two techniques for stack traversal when capturing continuations: exception handling and two return values method. We combine these two techniques to get better performance in continuation capturing, and believe our approach has the advantages over existing techniques.

著者

笹田 耕一 松本 行弘

雑誌

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

巻号頁・発行日

vol.8, no.1, pp.12-12, 2015-06-02

---

世代別GC,およびインクリメンタルGCはよく知られたGCの改善手法であるが,実装するためには正確なライトバリアが必須である.一方,Ruby処理系は保守的マーク&スイープGCを用いることで,C言語などで拡張コードを書くときに余計なコードを含む必要がなかったが,ライトバリアを挿入しておらず,これを必要とするGCアルゴリズムを導入することができなかった.我々はこの問題を解決するために,ライトバリアに対応しているオブジェクトとしていないオブジェクトを区別して,世代別インクリメンタルGCを実装する新しい方法を提案する.本発表では提案する手法について説明し,Rubyへの実装について述べる.

著者

中川 岳 追川 修一

雑誌

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

巻号頁・発行日

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

---

次世代の不揮発性メモリはバイトアクセス可能であり,計算機の主記憶として 利用可能である.主記憶が不揮発になることで,主記憶と2次記憶を融合することが可能になる.これにより,CPUから永続的なデータに直接アクセスが可能になり,I/Oのオーバヘッドを削減することができる.しかしながら,現時点では単体で主記憶を構成可能なNVMは登場していない.そのため,これまで,少量のDRAMと相変化メモリ(PCM)を組み合わせて主記憶を構成する方法が検討されてきた.PCMは 書き込みに短所のある不揮発性メモリ素子である.DRAMと組み合わせ,書き込みアクセスの多いデータをDRAMに配置することで,PCMの短所を隠蔽して主記憶を構成することができる.このようなハイブリッド構成では,データに対 する書き込みの傾向に基づいて,データ配置を決定する必要がある.この方法として著者らはデータの持つセマンティクスを利用して,プログラミング言語処理系のレベルでデータ配置の決定を行う方法の提案と実装を行った.実験の結果,提案手法はハイブリッド構成の主記憶における効率的なデータ配置に効果があることが分かった.しかしながらその一方で,提案手法には配置の効率面での問題がある.本発表では,その解決のための修正と効果の検証結果について説明する.

著者

Masahiko Sakai Tatsuki Kato

雑誌

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

巻号頁・発行日

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

---

Malbolge is known as one of the most esoteric languages, in which programming is very difficult. The difficulty comes from (a) its restrictive instructions, (b) instruction-replacement after execution and (c) restriction on loadable data. In this presentation, we overview Malbolge language and our results to produce its programs.

著者

須永 高浩 笹田 耕一

雑誌

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

巻号頁・発行日

vol.4, no.3, pp.1-15, 2011-06-29

---

Ruby は高い生産性を持つプログラミング言語である.これまでもプログラムにあるそれぞれのメソッドの実行時間を計測することができるプロファイラは整備されてきた.しかし,分析対象プログラムの実行と並行してリアルタイムプロファイリングが行えるツールが存在しなかった.そこで,本研究では Ruby で書かれたソフトウェアのプロファイリングをリアルタイムに行える実行時間プロファイラを開発した.本プロファイラは,対象となる Ruby で記述されたプログラムの,メソッド単位での実行時間情報を取得することが可能である.この情報取得はネットワークで接続された別のホストからリアルタイムに行うことができる.さらに,それぞれの情報についてプログラムのエントリポイントからの完全なコールパスを関連付けてプロファイリングを行うことが可能であり,対象となるプログラムのパフォーマンスの傾向を詳細に把握することが可能である.本プロファイラは,プロファイリングモジュールとモニタプログラムに分離されており,プロファイリングモジュールで情報を収集し,モニタプログラムがその情報をユーザへリアルタイムに提供する.本稿では,本プロファイラの設計と実装について述べる.また,本プロファイラのオーバヘッドの評価を行い,その結果を述べる.実用的なプログラムによる評価では 1.15 倍程度の実行時間の増加となり,本プロファイラは実用的であるとの結論を得た.Ruby is a programming language which has high productivity. Up to now, Ruby's performance profilers that are able to measure execution time of each method have been developed. However, there is no real-time profiler that is able to show the profiling result while a Ruby program is running. We developed a profiler that is able to profile programs written in Ruby language in real time. The profiler can get execution time information of each method in the target Ruby program. It is able to get the information from a foreign host connected by network in real time. Furthermore, the profiler can profile associating each information with the entire call-path from an entry point of the program. With this call-path informathion users can know the trend in program performance in detail. The profiler consists of two parts: a profiling module and a monitor program. The profiling module collects information, and the monitor program provides information for users in real time. In this paper, we describe the design and implementation of our proposed profiler. We also describe the result of overhead evaluation for the profiler. Execution time increases 1.15 times in a practical example. We conclude that our profiler is capable for practical use.