著者

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

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.44, no.13, pp.58-71, 2003-10-15

参考文献数

21

被引用文献数

25

---

近年,教育課程の改訂により,小学校から高等学校までの初中等教育において情報教育の導入が進められている.筆者らは,「情報教育の中でプログラミングを体験することは計算機の動作原理を学ぶうえで効果的である」という考えから,初中等教育で活用可能なプログラミング言語である「ドリトル」を開発し,それを用いたプログラミング教育について研究を行ってきた.本稿では,中学校においてドリトルを用いて実施したプログラミング教育とその評価について報告する.行った授業では,プログラミング経験のない生徒を対象に,タートルグラフィックスとGUI部品を用いたプログラミングを扱った.また,アンケートと2回の定期試験の結果に基づき,オブジェクト指向を含むプログラミングの概念が生徒にどのように理解されるかを分析した.Recently, IT education curriculum at K12 (kindergarten and 12-year-education) schools are being started in Japan. Programming experiences will be useful for students to learn essence and principle of computers. However, we insist that the use of "modern" languages is indispensable to achieve the goal. In this paper we describe our experiences of using "Dolittle" object-oriented programming language in junior high school classes. Turtle graphics, figure objects, and GUI objects were taught in the class, and paper tests and enquiries were conducted for evaluation. As the result, majority of the students understood basic concepts of programming and object-orientation, and enjoyed the classes.

著者

笹田 耕一 松本 行弘 前田 敦司 並木 美太郎

出版者

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

雑誌

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

巻号頁・発行日

vol.48, no.10, pp.1-16, 2007-06-15

被引用文献数

2

---

本論文ではスクリプト言語Ruby 用仮想マシンYARV: Yet Another RubyVM における並列実行スレッド処理機構の実装について述べる.Ruby はその使いやすさから世界中で広く利用されているプログラム言語である.Ruby の特徴の1 つにマルチスレッドプログラミングに対応しているという点があるが,現在広く利用されているRuby 処理系は移植性を高めるため,すべてユーザレベルでスレッド制御を行っている.しかし,このスレッド実現手法では,実行がブロックしてしまう処理がC 言語レベルで記述できない,並列計算機において複数スレッドの並列実行による性能向上ができないなどの問題がある.そこで,現在筆者らが開発中のRuby 処理系YARV において,OS やライブラリなどによって提供されるネイティブスレッドを利用するスレッド処理機構を実装し,複数スレッドの並列実行を実現した.並列化にあたっては,適切な同期の追加が必要であるが,特に並列実行を考慮しないC 言語で記述したRuby 用拡張ライブラリを安全に実行するための仕組みが必要であった.また,同期の回数を減らす工夫についても検討した.本論文では,これらの仕組みと実装についての詳細を述べ,スレッドの並列実行によって得られた性能向上について評価した結果を述べる.In this paper, we describe an implementation of parallel threads for YARV: Yet Another RubyVM. The Ruby language is used worldwide because of its ease of use. Ruby also supports multi-threaded programming. The current Ruby interpreter controls all threads only in user-level to achieve high portability. However, this user-level implementation can not support blocking task and can not improve performance on parallel computers. To solve these problems, we implement parallel threads using native threads provided by systems software on YARV: Yet Another RubyVM what we are developing as another Ruby interpreter. To achieve parallel execution, correct synchronizations are needed. Especially, C extension libraries for Ruby which are implemented without consideration about parallel execution need a particular scheme for running in parallel. And we also try to reduce a number of times of synchronization. In this paper, we show implementations of these schemes and results of performance improvement on parallel threads execution.

著者

小池 龍信 岩井 輝男 中西 正和

出版者

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

雑誌

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

巻号頁・発行日

vol.40, no.7, pp.1-8, 1999-08-15

参考文献数

8

被引用文献数

1

---

ごみ集め処理(GC)を必要とする言語がいくつか存在し Lisp言語などのような関数型言語処理系にはGCが不可欠である.これらの処理系は 実時間性に向いてないとされてきた.理由としては GCを行っている時に処理が一時中断することがあげられる.この中断時間をできるだけ減らすための研究がなされている.このようなGCを実時間GCと呼び その中の一つにTreadmill GCがある.Treadmill GCは複写式GCを改良したものである.このGCでは全てのオブジェクトを双方向環状リストで連結し GCは複写によるオブジェクトの移動ではなく 双方向ポインタのつけかえ(relink)で実現する.これにより複写式GCの利点を保持し さらにオブジェクトの移動を行わないため複写式GCで問題となるreadバリアが解消されている.Treadmill GCの時間的コストは生きているオブジェクトの数に比例する.よって生きているオブジェクトが多い場合には実時間性が乏しい.この問題点の解決方法として世代別GCの考えを取り入れた.世代別GCの考え方は ある程度生き続けたオブジェクトは半永久に生き残り また生成して間もないオブジェクトの殆どは寿命が短いというものである.本稿では 世代別GCの考えを取り入れたTreadmill GC(Opportunistic Treadmill GC)の提案及びその実現方法 さらにいくつかのベンチマークアプリケーションを実行し その実験結果から1回のGC時間 総実行時間を削減したことについて報告を行う.Real-time Garbage Collection is a study that makes pause time of GC as short as possible. Treadmill GC, one of the real-time GC algorithms, is improved Copying GC. In this scheme all objects are linked by cyclic doubly-linked lists (treadmill). Objects are not removed by copying, and objects' pointer of treadmill are relinked. This means that advantages of Copying GC are preserved, solving read barrier problem at the same time. We propose the "Opportunistic Treadmill GC", which is a Garbage Collection technique that the collector traces only short-life objects, setting long-life objects out of collector's view. There is a strong evidence that the overwhelming majority of objects die very young, although a small proportion may live for a long time. In Treadmill GC, pause time of GC is mostly the time for relinking alive objects. Especially in the original Treadmill GC, collector has to relink all alive object. However in Opportunistic Treadmill GC, collector only has to relink short-life objects of all alive objects. Hence we can make a pause time of GC shorter and improve effective real-time GC. Then we implemented the original Treadmill GC and Opportunistic Treadmill GC on an incremental garbage collector of the Lisp1.5 based system, and showed how efficient it is by a few experiments, in comparison with the original Treadmill GC, we could decrease average time of one GC execution as well as total execution time. We refined incremental GC so that the real-time systems with our Opportunistic Treadmill GC will be more useful.

著者

伊藤陽 小濱 真樹 佐々 政孝

雑誌

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

巻号頁・発行日

vol.46, no.SIG14(PRO27), pp.30-42, 2005-10-15

---

SSA 形式(静的単一代入形式)は,φ 関数という仮想的な関数を用いることで,変数の定義を字面上1 カ所だけになるように表した中間表現である.しかし,SSA 形式を用いたプログラム中に現れるφ 関数が仮想的であることから,SSA 形式から直接目的コードを出すことはできない.そこで,目的コードを出す前段階として,φ 関数を消去して通常形式に戻すことが必要である.これをSSA 逆変換と呼ぶ.SSA 逆変換には主なアルゴリズムが2 つある.以前から用いられているBriggs らのアルゴリズム,およびこれとは異なるアプローチによるSreedhar らのアルゴリズムである.SSA 逆変換アルゴリズムはそれぞれ異なった特徴を持つが,これらを実際に比較した研究はほとんどなされていない.このため,SSA 形式を最適化コンパイラに採用するにあたって,どのSSA 逆変換を用いるかの選択の指標となるものがなかった.そこで本研究では,Briggs らとSreedhar らのアルゴリズムの長所と短所を明確にした.また,Briggs らのアルゴリズムに対する改良案を提案した.さらに,Briggsらのアルゴリズムとその改良案,Sreedhar らのアルゴリズムの3 つを実装し,同一のコンパイラ上で,SPEC ベンチマークを用いて種々の条件を変えながら比較した.本研究により,Briggs らの方法ではコアレッシングすることのできないコピー文が数多く挿入されること,実証的にはSreedharらの方法が最も優れていること,が判明した.

著者

立堀 道昭 鈴村 豊太郎 小野寺 民也

雑誌

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

巻号頁・発行日

vol.2, no.4, pp.1-12, 2009-08-28

---

ウェブ・アプリケーション開発では,通常 HTML テンプレートを用いてウェブページの表現部を背後にあるビジネスロジックやオブジェクトから分離するのが事実上の標準プログラミングモデルとなりつつある.本稿では,このテンプレートに基づくプログラミングにおける典型的な慣習に着目し,従来の実装形態とは大きく異なる実装を施したサーバ側テンプレート・エンジンである FlyingTemplate について述べる.FlyingTemplate では,既存のウェブ・アプリケーションのテンプレート・エンジンを置き換えることにより,ウェブサーバの負荷を,自動的に,かつ従来の自動分散機構より安全にクライアントに分担させることができる.FlyingTemplate では,HTML 文書をまるまる生成する代わりに,テンプレートのパラメータ値とクライアント側で動作するブートストラップのコードのみを含む骨子文書を生成する.ブートストラップコードはクライアント側用のテンプレート・エンジンとウェブページのテンプレートをそれぞれサーバから取り寄せることにより,ウェブブラウザのキャッシュを有効利用できる.実験として,SPECweb2005 の Banking アプリケーションをそのまま,テンプレート・エンジンのみ FlyingTemplate で置き換えたところ,キャッシュがよく当たるケースでは,1.6 倍から 2 倍のスループット向上がみられた.

著者

笹田 耕一 卜部 昌平 松本 行弘 平木 敬

雑誌

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

巻号頁・発行日

vol.5, no.2, pp.25-42, 2012-03-30

---

我々は,高性能なRuby処理系の開発を行っている.Ruby処理系は仮想マシン(VM)を用いて実現されているが,現在のVMでは,同時にたかだか1つのRubyスレッドのみ実行するという制約があり,並列実行をサポートしていない.また,複数のRubyプロセスを用いて並列実行すると,計算に必要となるオブジェクトの転送がプロセス間転送となり,オーバヘッドが大きいという問題がある.そこで,我々は1つのプロセスに複数のVMを並列に実行できるマルチ仮想マシン(MVM)の開発を行っている.各VMはオブジェクト空間を独立に管理するが,各VMが同一プロセス内にあることを活かしたVM間の高速なオブジェクト転送を行うことができる.また,これらの機能をRubyから利用するためのプログラミングインタフェース(API)を設計した.さらに,Rubyの遠隔メソッド呼び出し機構であるdRubyをMVM上で利用できるように拡張し,MVMの利用を容易に行うことができるようにした.MVMの実装は,現在の処理系との互換性を維持するため,既存の処理系のプロセス全体で共有されるデータ,たとえばC言語のグローバル変数やI/O資源などを,VMごとに保持するようデータ構造を変更することで行った.本論文では,開発しているMVMの設計と実装について述べ,MVMを用いるためのAPIを説明する.そして,MVMを用いた並列処理の現在の実装での性能評価について述べる.

著者

皆川 宜久 鵜川 始陽 八杉 昌宏 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.46, no.11, pp.71-71, 2005-08-15

---

継続とは,計算のある時点の残りの計算である.Scheme では,これをファーストクラスのオブジェクトとして扱え,コルーチンやマルチスレッドなどの機能を実現するのに有用である.ML 言語において一級継続の機能を搭載した処理系としては,Standard ML of New Jersey がある.この処理系はスタックを用いず関数フレームをすべてヒープ領域に割り付けているため,定数オーダの時間で継続の生成を実現している.しかし,一般に関数フレーム生成時にスタックを用いた方が,高速であり,メモリ効率も良い.本研究では,スタックを用いているML 処理系に対し,一級継続の実装を行った.この場合,継続の生成時にスタックの内容をヒープにコピーするスタック法が一般的である.実際,スタックを用いたScheme 処理系で多く採用されている.この方法は動作が単純で実装しやすいなどの利点がある.一方,継続生成のたびにスタックのコピーが行われるので,生成時間,メモリ効率の点などで効率が悪いことがある.そこで本研究では,その効率化手法である遅延スタックコピー法を採用した.この手法は,継続を使用したプログラムの効率を高める一方,オブジェクトの生成時や代入時にオーバヘッドが存在するという欠点がある.そこで,コンパイル時にML の型情報を利用して,そのオーバヘッドを軽減する手法を提案し,実装,評価を行った.A continuation is the remaining task at a point in a computation. In Scheme, a continuation can be captured as a first-class object. This is useful for implementing coroutines and multi-threading. Standard ML of New Jersey is an implemenation of ML with first-class continuations. This system allocates all activation records into the heap, and this feature allows capturing continuations in constant order time. In general, however, a stack is more efficent in terms of execution time and memory space to allocate activation records. We implemented first-class continuations in a stack-based ML system. In order to implement first-class continuations, we adapted the stack strategy which is used in many stack-based implementations of Scheme. With this strategy, the entire stack contents are copied into the heap whenever a continuation is captured. This strategy is simple and easy to implement, but capturing continuations requires a lot of time and memory space. Thus, we employed the lazy stack copying strategy, which is based on the stack strategy but more efficent. While this strategy is useful when creating continuations, there is an overhead when creating and modifying objects. We propose a technique to reduce this overhead by using the type information of ML at compile time, and we applied this techinique to the ML system and evaluated it.

著者

岡本 秀輔 鎌田賢 中尾 隆司

雑誌

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

巻号頁・発行日

vol.46, no.SIG1(PRO24), pp.19-27, 2005-01-15

---

アニメーションは,Web ページの例で代表されるように,情報伝達手段の重要な選択肢の1 つである.特に,キーやマウスなどのユーザ入力によって,表示内容が変化するような対話型のアニメーションは,ユーザの興味を引きつける.しかし,ひとたびこのような対話型アニメーションを作ろうとすると,芸術的な素養のほかに,プログラミング技術やグラフィックスの知識が必要となり,素人には敷居が高すぎる.そこで,我々は小学生の利用も視野にいれた,対話型アニメーション作成ツールの設計と実装を行っている.ユーザは,GUI エディタで状態遷移図と表示画像を指定することにより,オブジェクト指向モデルに沿った形で,アニメーションに登場するキャラクタの動きを決めていく.そして,インタプリタにより動作を確認し,トランスレータによりJava やJavaScript といった対象コードへの変換を行う.変換の際には,Java の内部クラスやJavaScript の関数ポインタを用いることで,状態遷移図と対象コードの対応関係を保たせている.副産物として,このツールは楽しみながら情報処理を学ぶための教材となる可能性がある.状態遷移図を作成して,その動きをイメージすることは,情報処理教育の導入に適している.また,アニメーションに対応する中間言語表現や,対象形式への変換例を見ることは,プログラミングを含めた次のステップの教育に役立つ.

著者

中川 博貴 笹田 耕一

雑誌

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

巻号頁・発行日

vol.5, no.4, pp.1-16, 2012-09-04

---

我々はオブジェクト指向スクリプト言語Rubyにおいて,マルチコアプロセッサによる並列プログラミングを効率的,かつユーザが扱いやすい形で実現することを目指し,Rubyオブジェクトのプロセス間転送・共有を行うTeleporterライブラリを開発した.既存のプロセス間通信機構でオブジェクトを転送するには,オブジェクトをバイナリ列に変換してから送信し,受信側でそれをオブジェクトに復元する必要があり,そのオーバヘッドが問題となっていた.そこでTeleporterでは通信路にプロセス間共有メモリを利用することで,オブジェクトを従来の機構よりも軽量なシリアライズ,もしくはシリアライズを行わずに転送するようにし,オーバヘッドの少ない通信を実現した.さらにプロセス間でRubyオブジェクトを安全に共有する仕組みについて設計し,実装を行った.Teleporterはユーザが手軽に利用できることを目指すため,Ruby処理系の改修を行わずにRubyの拡張ライブラリとして実装した.本稿では,開発したTeleporterの設計と実装,そしてAPIについて詳細に述べる.また,Teleporterを用いた評価結果を示し,その考察を示す.

著者

小菅 圭介 佐藤 規男

雑誌

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

巻号頁・発行日

vol.2, no.3, pp.60-60, 2009-07-10

---

Python あるいは Ruby のようなスクリプト言語のデバッガは,コールバック関数指定時に,インタープリタが line,call,return などのトレースイベントを通知するために起こすコールバックを解析することにより,ブレークやステップなどのデバッグイベントを検出する.しかし,トレースイベントごとのコールバックは,デバッギの仮想マシンコードの実行速度を 2 桁あるいは 3 桁オーダで著しく低下させてしまうという欠点がある.これは,大規模プログラムの効率良いデバッグの妨げとなる.そこで,インタープリタが提供すべき新しいデバッガサポートを提案する.このサポートでは,基本的にコールバックの生成は何らかのデバッグイベントをインタープリタ内部で検出したときのみに限定する.このサポートを利用すると,デバッギコードをほぼフル速度で実行したまま,デバッグイベントを検出することができる.我々はこのサポートとデバッガを CPython インタープリタと我々がオープンソースとして提供している非同期型デバッガ Dionea に実装した.TurboGears の Depot システムで実験した結果,デバッギのほぼフルスピードの走行とデバッガ反応速度の飛躍的向上を確認した.Debuggers for scripting languages such as Python or Ruby detect the debug events such as break or step hit by analyzing the callbacks that are raised by the interpreter to report the trace events such as a new line, call and return. A drawback of the callback for each trace event is to slow down the execution speed of the debuggee virtual machine code seriously by two or three orders of magnitude. This prevents efficient debugging for large programs. We therefore propose a new debugger support that the interpreter should provide, with which the callback is raised basically when and only when some debug event is detected inside of the interpreter. Using this support, the debugger can detect the debug events while the debugged code is running almost at full speed. We have implemented the proposed support in the CPython interpreter and applied it to the asynchronous debugger Dionea which we deliver as an open source project. A measurement using test programs and a TurboGears Depot system shows almost full speed execution of the debugee and remarkable response time improvement of the debugger.

著者

川又 晃 羅翔 寺島 元章

出版者

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

雑誌

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

巻号頁・発行日

vol.41, no.2, pp.105-105, 2000-03-15

---

当研究室で開発した便宜的ガーベッジコレクション(ccasional G)の並行化とその実装について述べる.便宜的GCとは,リスト処理などの純計算側が消費したヒープ中の最新の使用域のみを対象として使用中オブジェクトの圧縮(liding compactio)処理を行うものである.その効果として,GC処理時間の短縮化と,ヒープ使用の節約に伴うワーキングセットの縮小で純計算時間の短縮も図れることが停止回収型の実装から示されている.この便宜的GCの並行化は,毎回行われるGC処理の実時間(ealtim)化と定期的に行われるGCの並列(oncurren)化とからなる.前者は通常の掃除をこまめに行うことを,後者は時間のかかる大掃除を別個に行うことを意味する.GCの圧縮処理の実時間化に必要な,write?barrierと輪切り複写の機能は,そのまま並列化にも適用できる.並列化ではこれらに,排他制御が付加されるだけである.輪切り複写とは,一度に圧縮するオブジェクトを移動先にその複製が作られる範囲に限定することであり,GCの圧縮処理中での中断を可能にする.また,write?barrierはオブジェクト参照に伴う純計算側の負荷を減らす.純計算側はLispの一方旨であるPHLを用い,GC側はスレッドライブラリを利用したコルーティンという汎用的な環境下で実装を行った.数種のLispプログラムの実行結果から得られた本GCの実時間特性についても述べる.The design and implementation ofincremental occasional garbage collection are presented. The occasional garbage collectionis a new type of garbage collection(GC)based on a "mark-and-compact" or sliding compaction scheme.The GC focuses its task of scavenging on most recently generated data object to gain time, and its good performance is shown by a prototype of "stop-and‐collect" version. The incremental occasional garbage collection is made up of two features:"realtime"and"concurrency''. The former is performed usually, while the latter is periodically to gain more spaces.They need common schemes of a write barrier and a coherent copy.The write barrier is less costly in time for coordination than a read barrier, and the coherent copy makes each data object consistent upon its relocation. The concurrency needs exclusive control in addition to them, so that these two features are implemented effectively in the GC.The incrementaI GC is implemented on a multi‐processor machine with shared memory by using(POSI・ス)thread library that makes it portable. The analys of the GC on its performance is done by using our experimental data obtained from the execution of typical Lisp programs.

著者

長慎也 筧 捷彦

出版者

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

雑誌

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

巻号頁・発行日

vol.43, no.8, pp.121-121, 2002-09-15

---

アクションゲームを作成する際に必要となる技術として,複数のオブジェクトの並行動作や,ゲーム画面の視覚的設計,といったことがあげられる.これらの技術をユーザから簡単に利用可能にする言語および開発環境Tonyu System(以下Tonyu)を作成した.まず,Tonyuは各オブジェクトの動きを独立に記述し,それらを並行動作させることが可能である.並行動作を行うには通常マルチスレッドを用いるが,アクションゲームはオブジェクトが多数出現するため,OSで用意されているスレッドでは負荷が大きすぎる.Tonyuは仮想機械による実行系を持ち,仮想的なスレッドを同時に複数実行できるが,OS上ではシングルスレッドで実行される.このため,同等の処理をOSのスレッドを利用して行う場合に比べて負荷が抑えられている.また,Tonyuはゲーム画面の設計を視覚的に行う仕組みを持つ.GUIアプリケーションの外観を設計するビジュアルツールは多く普及しているが,Tonyuはこのビジュアルツールの技術をゲーム画面のレイアウト設計に応用したものである.さらに,Tonyuはプログラムの実行中においても,設計時同様,ゲーム画面のクリックによるオブジェクトの選択,選択されたオブジェクトの値の閲覧,編集といったデバッグ操作をリアルタイムに行うことができる.この機能を利用して,他ユーザのプログラムを容易に解析,改変することができる.これらの特徴を活かし,Tonyuをプログラムの共同開発やプログラミング教育のためのツールとして利用していく予定である.To making action games, we need following techniques: parallel processing of multiple objects and visual design of game fields. We developed "Tonyu System" to support these techniques for users. At first, Tonyu allows users write behavior of each object independently and then put them into a field and run them automatically in parallel. In action games, there may be many threads at a same time. That will charge very high load when using native threads (threads provided by OS). Tonyu can execute virtual multi-threads on the virtual machine. But consumes just one native thread. It charges less load than using native thread. Second, Tonyu enables users to design layouts of game fields visually. To design layouts of GUI-based applications, visual development tools are widely available. Tonyu is also a visual development tool, but for designing layouts of action games. Moreover, Tonyu has some useful debugging features: selecting each object by clicking the game screen and inspecting and editing values of the object. These features can be used not only at design time, but also at runtime. They support users to analyze and modify other user's programs. Using these features, we are using Tonyu for co-operating development, or programming education.

著者

涌井 智寛 沼崎 隼一 三塚 恵嗣 畠山 正行

雑誌

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

巻号頁・発行日

vol.4, no.2, pp.134-134, 2011-03-25

---

最近いわゆるインターネット技術の発達と成熟にともなって,Web アプリケーションの開発と利用の機会は増し,社会的需要も増大しつつある.しかし,それらを支えるアプリケーションの開発をより簡単にする技術や,ユーザの利用をより快適にする技術はまだまだ発展途上にあると考えられる.開発を簡単にするという点では,jQuery,Ruby on Rails 等の多くの技術が存在するが,我々は利用の応答性を高めるという点に着目し,Web アプリケーションを提供するサーバのスループットや,クライアントのインタラクティブな応答性の問題における 1 つの解決を目指す.Web アプリケーションで扱うデータ量が増加すると,その応答はユーザの利用応答性を現実に損なう.そこで我々は,(i) ブラウザで多数の要素を生成,表示する場面では,(i-1) 軽量な要素と単一の textarea を使用する,(i-2) display プロパティによる選択的表示を行う,(i-3) class 属性値によってデータを保持する工夫をし,(ii) 多数の要素の中からいくつかの所定の要素へアクセスする場面では (ii-4) 特別な ID 名をセレクタとする,など合わせて 4 つの工夫により,応答性の問題に対する 1 つの解決案を見いだした.これらの工夫を実装することで数万要素程度を扱う Web アプリケーションでは,多くの状況で応答時間を 0.1 秒に抑えられ,ユーザが瞬時の応答を得られるという点で良好な結果を得た.また,これらの工夫は Web アプリケーションの開発者にとっては基本技術と見なしうる技術範囲で実装可能となるように考案した.このような基本技術に限定したことで,数個の工夫を付加的に実装する形で応答性改善が期待できる.本論文では上記の基礎的な技術のみに基づき,Web アプリケーションの応答性を高める実装方法について報告する.The importance and the use of the Web applications will increase due to the development of the Internet technique. In the present paper, we have focused our attentions to the response time of the user operation of the Web applications on the browser. As are well known, the response time increases along with the increase of the data amount using in the Web applications. To improve the response time of the Web application, we have thought out the following four technique as follows; (i) In the scene of generating and rendering a lot of elements on the browser; (i-1) use an element properly by the scene, (i-2) select the target to view or to edit by the display property, (i-3) store the data in the form of the class attribute value instead of the element's content, (ii) In the scene accessing to some elements among a lot of elements; (ii-4) use ID as the selector as if it was a class attribute value. As the results, we have got the rather good solutions for the user's response time less than 0.1 seconds. We have also developed a simple technical skill set to realize the solutions the above described simple technique.

著者

今井 敬吾 結縁祥治 阿草 清滋

出版者

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

雑誌

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

巻号頁・発行日

vol.47, no.16, pp.10-28, 2006-10-15

参考文献数

17

---

我々はプログラミング言語Haskellへ,型付き非同期局所化pi計算(typed Asynchronous Localized $\pi$-calculus; ALpi)を,ネットワークプログラミングのためのフレームワークとして埋め込む手法を提案する.本フレームワークは埋め込み言語として実装されることで以下の利点を持つ:(1) Haskellで構築されているため処理系が頑健である,(2) Haskellのリテラル,型や関数といった言語要素をフレームワークに組み込むことができる.さらに,ALpiのmobilityに対する制限はフレームワークの実装を簡単にする.本フレームワークでは,ALpiのプロセスはPiMonadと呼ばれるHaskellのモナドとして実装する.結果として,通信により引き起こされる副作用は型のPiMonadタグで区別される.ALpiのサブタイプ関係はHaskellの多引数型クラスで実現する.サブタイプ関係にある型の対は通信の方向を反映した3つの2引数型クラスに属する.本フレームワークを用いた例としてTCP/IPネットワーク上のインスタント・メッセンジャアプリケーションの構築例を示し,有用性と利点を述べる.We propose an embedding of the typed Asynchronous Localized pi-calculus (ALpi) into the programming language Haskell as a framework for network programming. The framework has following advantages due to the embedded language nature: (1) the framework is robust due to being built upon the Haskell framework, and (2) the framework can incorporate various Haskell language elements, such as literals, types, and functions, in the framework. Moreover, the limitation of mobility in ALpi simplifies the implementation of the framework. ALpi processes are implemented by means of a Haskell monad called PiMonad. As the result, side-effects caused by communications are distinguished by the tags of PiMonad in typing. The subtyping relations is realized by multi-parameter type classes in Haskell, where a pair of subtype-related types belongs to three binary type classes reflecting the directions of communication. We illustrate the usefulness and benefits of our framework with an example of an implementation of instance messenger application over TCP/IP network.

著者

八杉 昌宏 小島 啓史 小宮 常康 平石 拓 馬谷 誠二 湯淺 太一

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.3, no.5, pp.1-17, 2010-12-10

---

Scheme処理系は真に末尾再帰的であることが要求されており,アクティブな末尾呼び出しの数に制限がない場合もサポートしなくてはならない.Clingerは真の末尾再帰の形式的定義の1つを空間効率の点から与えており,その定義に従えば,末尾呼び出しの最適化(末尾呼び出しをトランポリンなどによりジャンプに置き換えて実装する方法)だけでなく,BakerのCPS(継続渡しスタイル)変換を用いたC言語におけるSchemeの実装手法も,真に末尾再帰的と分類できる.Bakerの実装手法は,CPS変換された末尾呼び出しにおいて新たな継続を生成せず,C言語の実行スタックに対してもごみ集めを行うため,空間効率が良い.本論文では拡張C言語による真に末尾再帰的なSchemeインタプリタの実装手法を提案する.本手法はCPS変換を用いず,Cの実行スタックがあふれそうになれば,残りの計算に必要な"Frame"オブジェクトのみを含むリストとして表現された空間効率の良い一級継続を生成し,すぐさまその継続を呼び出すというアイディアに基づく.ごみ集めや継続のキャプチャにおいては,実行スタックに合法的にアクセスできる,つまりデータ構造や変数の値としてアクセスできるL-closureという言語機構を用いている.ベースとなるSchemeインタプリタは,Javaアプリケーション組み込み用LispドライバであるJAKLDをもとにC言語で再実装されたものとした.Implementations of Scheme are required to be properly tail-recursive and to support an unbounded number of active tail calls. Clinger proposed a formal definition of proper tail recursion based on space efficiency. The definition covers systematic tail call optimization, where every tail call is converted to a jump (with an optional trampoline), as well as Baker's implementation of Scheme in the C language with CPS (continuation-passing style) conversion. Baker's implementation is space-efficient, since no new continuation is created on a CPS-converted tail call and garbage is collected even on C's execution stack. We propose techniques to implement a properly tail-recursive Scheme interpreter in an extended C language. Our approach does not convert a program into CPS. The key idea is to avoid stack overflow by creating a space-efficient first-class continuation represented as a list containing only the "Frame" objects necessary for the rest of computation and immediately invoking the continuation. We use a language mechanism called "L-closures" to access the contents of the execution stack as values of legal data structures and variables for implementing garbage collection and capturing continuations. This research is based on a Scheme interpreter which is developed in the C language by referring to an existing Lisp driver called JAKLD that is intended to be embedded in Java applications.

著者

平石 拓 李 暁? 八杉 昌宏 馬谷 誠二 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.46, no.1, pp.40-56, 2005-01-15

被引用文献数

2

---

現在,実用的システムの開発にC 言語は欠かせないが,細粒度マルチスレッド機能などを追加するためにC 言語を拡張するのはそれほど容易ではない.言語拡張の実現方式としては,C コンパイラに手を加えるもの以外に,拡張C プログラムを変換し,C コードを生成する方式もある.後者の方式では,最初にプログラムを抽象構文木(AST)に変換し,拡張に必要な解析や変形などを行った後,C コード生成を行うことが多い.AST のデータ構造には従来,構造体,オブジェクト指向言語のオブジェクト,直和型のデータなどが用いられているが,本研究では,AST をS 式で表現し,それをそのままプログラムとして用いることを提案する.このため,S 式ベースの構文を持つC 言語,SC 言語を設計した.SC 言語では新しいコンストラクトの追加が容易であり,また,S 式は,変換時に便利な動的変数も備えたCommon Lisp 言語を使って簡単に入出力や解析や変形ができるため,言語拡張のrapid prototyping が可能となる.ただし,Common Lisp 言語ではパターンマッチングを直接書くことができないので,本研究では,backquote マクロの記法をパターン部にも用いた変形規則の表記も提案する.このようなSC 言語は他の高水準言語の中間言語として用いることも可能である.本論文では,実際にSC 言語に細粒度マルチスレッド機能を追加した例も示す.The C language is often indispensable for developing practical systems, but it is not so easy to extend the C language by adding a new feature such as fine-grained multithreading. We can implement language extension by modifying a C compiler, but sometimes we can do it by translating an extended C program into C code. In the latter method, we usually convert the source program to an Abstract Syntax Tree (AST), apply analysis or transformation necessary for the extension, and then generate C code. Structures, objects (in object-oriented languages), or variants are traditionally used as the data structure for an AST. In this research, we propose a new scheme where an AST is represented by an S-expression and such an S-expression is also used as (a part of) a program. For this purpose we have designed the SC language, the C language with S-expression-based syntax. This scheme allows rapid prototyping of language extension because (1) adding new constructs to the SC language is easy, (2) S-expressions can easily be read/printed, analyzed, and transformed in the Common Lisp language, which features dynamic variables useful for translation. Since pattern matching cannot be described directly in Common Lisp, we also propose denoting transformation rules with patterns using the backquote-macro notation. Such an SC language can also be used as an intermediate language for other high-level programming languages. This paper also shows a practical example where fine-grained multithreading features are added to the SC language.

著者

IKUO TAKEUCHI YOSHIJI AMAGAI MASAHARU YOSHIDA KENICH YAMAZAKI

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.16, pp.41-55, 2003-12-15

---

In this presentation we report on the microprogramming implementation and its evaluation of a concurrent real-time garbage collector (GC)for the rea-time symbolic processing system TAO/SILENT. Our real-time GC is implemented as a set of GC processes which run concurrently with other Lisp processes. It is based upon a sort of well-known incremental update algorithm and it brings in only a little overhead to Lisp primitives. We embedded a scheduling mechanism that is speci fic to GC process scheduling since it is indispensable to devise a good cooperation scheme between the operating system kernel and concurrent GC. We also developed a good deal of tiny techniques to make the GC processes as swift as possible. As a result our concurrent GC achieves a very small response delay for external events that is when an interrupt event takes place the corresponding urgent Lisp process can wake up in less than 131 microseconds for the worst case where more than ten thousand memory-consuming Lisp processes are concurrently running and surely in less than 50 microseconds if those Lisp processes are made with real-time consciousness. These figures are more than a hundred times as good as most of those appeared in the literature. Our GC can be said "transparent"in the sense that real-time processes would not be aware of the GC whether it runs or not at least with respect to response delay.In this presentation,we report on the microprogramming implementation and its evaluation of a concurrent real-time garbage collector (GC)for the rea-time symbolic processing system TAO/SILENT. Our real-time GC is implemented as a set of GC processes which run concurrently with other Lisp processes. It is based upon a sort of well-known incremental update algorithm, and it brings in only a little overhead to Lisp primitives. We embedded a scheduling mechanism that is speci fic to GC process scheduling, since it is indispensable to devise a good cooperation scheme between the operating system kernel and concurrent GC. We also developed a good deal of tiny techniques to make the GC processes as swift as possible. As a result, our concurrent GC achieves a very small response delay for external events, that is, when an interrupt event takes place, the corresponding urgent Lisp process can wake up in less than 131 microseconds for the worst case where more than ten thousand memory-consuming Lisp processes are concurrently running, and surely in less than 50 microseconds if those Lisp processes are made with real-time consciousness. These figures are more than a hundred times as good as most of those appeared in the literature. Our GC can be said "transparent"in the sense that real-time processes would not be aware of the GC whether it runs or not, at least with respect to response delay.

著者

舞田 純一 中井 央

出版者

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

雑誌

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

巻号頁・発行日

vol.46, no.14, pp.67-67, 2005-10-15

---

近年,様々な用途に合わせて様々なプログラミング言語が出現している.このため,自身の用途のためにプログラミング言語の処理系であるコンパイラをできるだけ容易に作成できることが望まれる.コンパイラ作成のためのツールとしてはLex やYacc が代表的である.Yacc が登場してからかなり長い年月が過ぎたが,その間には時代の要求に合わせて,たとえばベースとなる言語がJava であるようなツールも出現してきている.これらのツールを用いたコンパイラ開発の場合,意味解析処理は構文解析時の動作(アクション)としてC 言語などのプログラム断片を記述することが一般的である.また,記号表などはコンパイラ作成者がゼロから実装することも通常である.この際,算術式の構文や識別子の出現といった構文においては,型の検査や記号の登録といった作業のためのプログラム断片を記述することとなるが,一般にはあるプログラミング言語の文法にはその中に同様の構文的な構成が複数箇所あり,同様の意味解析処理のプログラム断片もそれに合わせて複数箇所記述しなければならない.これまで意味解析処理の内容について個別に研究は行われてきていても,それを視野に入れた生成系については論じられることがほとんどなかった.本発表では,型についての処理,記号表についての処理に焦点を当てた意味解析器の自動生成を含むコンパイラフロントエンドの自動生成について述べる.In these days, for many purpose, various programming languages has appeared. So rapid and easy construction of compilers is required. Yacc and Lex is very famous tool for compiler construction. Recently, there are some tools based on Java. In general, in order to implement the semantic analyzing process, the action of Yacc written as a fragment of C program is used. In many cases, the symbol table is also implemented from scratch. When we want to implement a compiler with these tools, we have to write a fragment that expresses type checking and/or adding symbols to the symbol table. But, there are many resemble production rules and its semantic actions in a grammar. There are very few researches for semantic analyser generator from the view point of the above although up to now, there are many individual research of each topic of semantic analysis. In this presentation, we mention about automatic generation of compiler front end that includes automatic generation of semantic analyser from the view point of type check and symbol table processing.

著者

外崎 由里子 大野 和彦 中島 浩

出版者

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

雑誌

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

巻号頁・発行日

vol.43, no.3, pp.82-82, 2002-03-15

---

PCクラスタやデュアルCPUマシンなどの普及により近い将来,研究者だけでなく一般のエンドユーザが並列環境を利用できるのが当たり前になると予想される.逐次計算機上では,Cなどの高性能なコンパイラ型言語処理系とともに,Perlなどの手軽なスクリプト言語処理系が使用されてきた.並列計算機上では前者に対してHPC++などが開発されているが,後者に相当するものの研究は進んでいない.そこで我々は,エンドユーザが容易に並列計算機資源を有効利用できる環境を実現するため,並列性を簡易に記述できるようにPerlを拡張した,並列スクリプト言語(Perl)+の設計・開発を行っている.(Perl)+では指定した計算機を並列環境に追加し,RPCにより任意のサブルーチンを実行することができる.その返り値は遅延評価されるため,ユーザは複数のサブルーチン呼び出しを容易に並列タスクとして実行できる.また,並列タスク間では通信用に擬似的なファイルストリームを開くことができ,Perlの入出力関数を使ってデータを送受信できる.これらの機能はCで実装し,PerlとCを組み合わせるためのツールであるXSを使ってPerlモジュールPerlplus.pmを構築している.このため,ユーザは本モジュールを取り込むだけで(Perl)+の機能を利用できる.本モジュールは起動時に各ホスト上にPerlプロセスを生成し,PVMによりRPCや通信を実現している.また,各プロセス上で実行スレッド/受信スレッドを生成することで,RPCの実行と並行して受信処理を行えるようにしている.The spread of PC clusters and multi-CPU machines makes multiprocessors environment available not only for the reseachers but also for the end users.On the uniprocessor machines,we can use both effcient languages such as C and simple script languages such as Perl.On the multiprocessors,the languages of the former type such as HPC++have been developed.However,the latter type is not researched enough.Thus,we designed and implemented a parallel script language named (Perl)+as an extension of Perl.(Perl)+supports parallel task generation using RPC.Since the return value of a subroutine is lazily evaluated,the subroutine is executed in parallel to its caller.In addition to the communication through input arguments and return value,a user may open quasi file streams for the communication between parallel subroutines.Through this stream,any type of Perl data may be transferred using input/output functions of Perl.We implemented these functions in C.The user-interface is built as a Perl module Perlplus.pm,using XS for the linkage of C and Perl. This module adds speci fied hosts to the PVM virtual machines and creates Perl processes.We also introduced multi-threads for concurrent execution of user 's Perl code and PVM message receiving.

著者

笹田 耕一 松本 行弘 前田 敦司 並木 美太郎

出版者

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

雑誌

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

巻号頁・発行日

vol.47, no.2, pp.57-73, 2006-02-15

被引用文献数

5

---

本稿ではオブジェクト指向スクリプト言語Ruby を高速に実行するための処理系であるYARV: Yet Another RubyVM の実装と,これを評価した結果について述べる.Ruby はその利用のしやすさから世界的に広く利用されている.しかし,現在のRuby 処理系の実装は単純な構文木をたどるインタプリタであるため,その実行速度は遅い.これを解決するためにいくつかの命令実行型仮想マシンが提案・開発されているが,Ruby のサブセットしか実行できない,実行速度が十分ではないなどの問題があった.この問題を解決するため,筆者はRuby プログラムを高速に実行するための処理系であるYARV を開発している.YARV はスタックマシンとして実装し,効率良く実行させるための各種最適化手法を適用する.実装を効率的に行うため,比較的簡単なVM 生成系を作成した.本稿ではRuby の,処理系実装者から見た特徴を述べ,これを実装するための各種工夫,自動生成による実装方法について述べる.また,これらの高速化のための工夫がそれぞれどの程度性能向上に寄与したかについて評価する.In this paper, we describe the implementation and evaluation results of YARV, next generation Ruby implementation. The Ruby language is used worldwide because of its ease of use. However, current interpreter is slow due to its evaluation method. To solve this problem, several virtual machine designs were proposed, but none of them exhibited adequate performance/functionality combination. Our implementation, called YARV (Yet Another Ruby VM), is based on a stack machine architecture. YARV incorporates a number of optimization techniques for high speed execution of ruby programs. In this paper, we describe the characteristics of Ruby from implementor's point of view, and present concrete solutions for these issues as well as implementation of optimization techniques. We also show how each of these optimizations contributed to the speed-up.