著者

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

出版者

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

雑誌

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

巻号頁・発行日

vol.41, no.9, pp.87-99, 2000-11-15

被引用文献数

8

---

Lispなどの大多数のリスト処理システムでは,不用セルを回収するためにごみ集め(GC)が行われる.一般的に採用されているGCは,ごみ集めの間プログラムの実行が中断されるので実時間処理には適さない.この問題を解決するために,ごみ集めの一連の処理を小さな部分処理に細分化し,プログラムの実行と並行してごみ集め処理を少しずつ進行させる実時間方式のGCが提案されている.代表的な実時間GCであるスナップショットGCは,スタックなどのルート領域から直接指されているセルをGC開始時にすべてマークしておかなければならない.この間の実行停止時間は,ルート領域の大きさによっては,無視できなくなる.そこで,関数からのリターン時にマーク漏れがないようにチェックすることで,スタックから直接指されているセルを関数フレーム単位でマークする方法を提案する.スタック上のルート領域をフレーム単位でマークしていき,ある関数からリターンする際に次の関数フレームがマークされているかどうかをチェックし,マークされていなければその関数フレームをマークしてからリターンする.これをリターン・バリアと呼ぶことにする.ルート領域のマークが終了したら,従来のスナップショットGCと同様に残りのセルをマークする.本論文では,Common Lisp処理系KCL(Kyoto Common Lisp)上でリターン・バリアを実装し,GCによる実行停止時間について,従来のスナップショットGCと比較評価および検討を行った.Garbage collection (GC) is the most popular method in list processing systems such as Lisp to reclaim discarded cells. GC periodically suspends the execution of the main list processing program. In order to avoid this problem, realtime GC which runs in parallel with the main program so that the time for each list processing primitive is bounded by some small constant has been proposed. The snapshot GC, which is one of the most popular realtime GC methods, has to mark all cells directly pointed to from the root area at the beginning of a GC process. The suspension of the main program by this root marking cannot be ignored when the root area is large. This paper proposes ``return barrier'' in order to divide the process of root marking into small chunks and to reduce the suspension time of the main program. The root area on the stack is marked frame by frame each time a new cell is requierd. When a function returns, the garbage collector checks if cells pointed to from the frame of the caller function have been already marked, and marks them if not. After marking all cells directly pointed to from the root area, other cells are marked as in the original snapshot GC .In this paper, we implemented the snapshot GC equipped with the return barrier in KCL (Kyoto Common Lisp). We compare and discuss the suspension times of this GC and the original snapshot GC.

著者

小藤 哲彦 河野 健二 竹内 郁雄

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.13, pp.84-99, 2003-10-15

被引用文献数

3

---

具象構文と抽象構文は対応関係が強く,これらを別々に記述するのは無駄が多い.この無駄を省くために,具象構文と抽象構文を一体として記述する手法がいくつか提案されている.本論文では,具象構文と抽象構文を一体として記述し,抽象構文木を出力するパーザを生成するコンパイラ・コンパイラ?<>< ∪∪(notavaCC )の設計と実装について述べる. ?<>< ∪∪は,継承,ラベル付け,エイリアスの構文記法を用い,オブジェクト指向に基づいた抽象構文を記述することができる. ?<>< ∪∪は,算術式のような従来の研究では表現できない抽象構文を記述することができ,表現力が高い.本論文では?<>< ∪∪が実用的な性能を持っていることも示す.Because of the similarity between abstract syntax and concrete syntax, it is wasteful to write these syntax descriptions individually. The paper describes the design and implementation of a compiler compiler named ¬<>< ∪∪(notavaCC), which has an integrated notation that can represent both of abstract syntax and concrete syntax, and generates a parser that builds an object-oriented abstract syntax tree. Using the notation for inheritance, labeling and aliases, ¬<>< ∪∪enables us to generate an object-oriented syntax tree of an arithmetic expression, which existent compiler compilers cannot generate. The paper also describes the practicability of ¬<>< ∪∪.

著者

松田 一孝 大川 徳之 野村 芳明 森田 直幸 筧 一彦 胡振江 武市 正人

出版者

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

雑誌

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

巻号頁・発行日

vol.47, no.2, pp.84-98, 2006-02-15

---

ファイルの操作において,ショートカットまたはシンボリックリンクといった別名の存在は,しばしばユーザを混乱させる.初心者にとってファイル実体と別名との区別は難しい,たとえば通常のファイルマネージャでは,ファイル実体を削除してもそれを指し示している別名は消えずに残り,逆に別名を削除しただけではファイル実体は削除されない.そこで,我々はファイルへの参照すべてを対称かつ統一的に抽象化して扱うファイルマネージャを,木上の双方向変換の技術を用いて実現する.我々のファイルマネージャの上では,1 つのファイルへの複数の参照は互いに同期されており,1 つを変更すると必ず同期された別の部分に伝播される.たとえば,1 つをディレクトリ木から削除すると残りも削除される.さらに,双方向変換を利用することにより,ディレクトリ木からの情報を抽出し操作して表示するなどのディレクトリ木の"見せ方" を抽象化および拡張でき,またその"見せ方"自体も変更することができる.このような"見せ方" の操作やファイル木に対する編集操作は,GUIを通して対話的に実行することができる.本論文では,この木上の双方向変換を利用したファイルマネージャの設計とその実装とを示す.File management is sometimes confusing due to the difference between files and their shortcuts (or symbolic links). While deleting shortcuts to a file can leave the file entity as it is, deleting a file entity may lead to dangling shortcuts. To resolve this problem, we apply the technique of bidirectional tree transformations to design and implement a new file manager which can treat file references in a symmetric and uniform way. This file manager is unique in its synchronization mechanism which eliminates the confusing difference of file references. Plural file references are synchronized, and changes applied on one reference will propagate to the others. For example, if one of the synchronized file references is deleted, the rest are also deleted automatically. This synchronization mechanism can be efficiently implemented based on bidirectional tree transformations. In this paper, we show the design and the implementation of our file manager. The interactive graphical user interface of our file manager enables us to manipulate file references easily, in which bidirectional tree transformations can produce complicated dependency.

著者

竹辺 靖昭 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.43, no.8, pp.98-109, 2002-09-15

被引用文献数

1

---

現在の多くのWeb サイトでは,Web サーバ上で動作するプログラムで,データベースへのクエリを行い,動的にWeb ページを生成する処理が行われている.我々は,部分評価の手法を応用し,こうした動的Web ページの生成を高速化するシステムを開発している.このシステムは,Web サイトの開発において広く使用されているPHP という言語を対象とした部分評価器と,部分評価によって生成されたプログラムをWeb サーバに配置するシステムからなる.この部分評価器は,更新の頻度が低いデータを静的と見なすことにより,これらのデータへのクエリを部分評価時に行うことができる.部分評価および生成されたプログラムの配置は,これらのデータが更新されるタイミングなどで行われる.Web ページを生成する時点では,変換結果に残された動的な部分のみが実行される.これにより,リアルタイムに更新される情報を含むページやパーソナライズ機能を持つページなど,さまざまなタイプの動的Web ページを生成する負荷を低減することができる.本論文では,このシステムで使用している部分評価の手法および実装方法を紹介するとともに,パーソナライズ機能を持つWeb ページなどに対して実際にこの手法を適用した結果を報告する.On many Web sites today, Web pages are generated dynamically by programs, which are deployed on Web servers and execute queries to databases. We are developing a system to reduce the cost of dynamic Web page generation on those Web sites. This system consists of a partial evaluator for PHP, a widely used programming language for Web site development, and of a deployment system which installs residual programs to Web servers. This partial evaluator regards those data that are not updated frequently as static and executes queries on them during partial evaluation. This system performs partial evaluation and program de-ployment when such data are updated. On Web servers, only residual programs are executed to generate Web pages. By this method, we can reduce the cost to generate many sorts of Web pages, including personalized Web pages and Web pages that contain real-time infor-mation. In this paper, we describe the partial evaluation technique used in this system and implementation of this system. We also report the result of experiment in which we apply this system to a Web site with personalized pages.

著者

田沼 英樹 出口 弘 清水 哲男

出版者

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

雑誌

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

巻号頁・発行日

vol.46, no.6, pp.63-63, 2005-04-15

被引用文献数

3

---

私たちはエージェントベースシミュレーションのための新たなプラットフォームとしてSOARS(Spot Oriented Agent Role Simulator)という言語を開発した.SOARS は当初,病院内でのSARS院内感染シミュレーションを行うための記述言語として開発された.病院内では医師,看護師,患者など様々な役割を持つ人々がそれぞれのルールに応じて複雑な社会的行動を行い,相互に影響を与えあう.これらの人々を自律的なエージェントと見なし,そこに協調,対立,あるいは無自覚の感染などの相互作用を入れることにより,一種の複雑系が構成される.そこで,このようなルール行動を抽象化したモデルを定義し,スクリプト言語として表現することにより,シンプルかつ柔軟にシミュレーションを記述することができる.SOARS 言語処理系の実装にはJava 言語を利用し,リフレクションを用いることにより柔軟な言語の拡張を可能にしている.そして,スクリプトのみで表現することが困難な処理については,Java のクラスを直接利用することができる.現在,SOARS の処理系は各エージェントについての処理を逐次的に行うが,言語モデル自体は処理の逐次性を仮定していない.将来的には別の処理系で並列分散処理が行える可能性があり,あるいは新たな並列処理アーキテクチャのパラダイムとして発展する可能性を秘めている.本発表ではSOARS モデル概念,スクリプト文法,処理系の実装,およびシミュレーション結果の実例について説明を行う.We developed a new language for agent-based simulation platform named SOARS (Spot Oriented Agent Role Simulator). At first, SOARS is developed for a simulation of SARS infection in a hospital. In hospital, there are various persons who play each role such as doctor, nurse and patient. They act complex social behavior as their own rules and interact with each other. We regard the persons as autonomous agents with interaction like cooperation, opposition, or unaware infection. And they construct a kind of complex system. We abstract the model of agents' rule actions and represent them as script language, and then we can describe simulations simple and flexible. We implement SOARS in Java language and enable functional expansion by Java reflection feature. Also, processes which are difficult to describe only by script language can be implemented in reinforcement by external Java classes. At present, SOARS implementation processes agents one by one, but the language model does not assume consecutiveness of the processes. In the future, other implementation can be parallel and distributed, and may provide a new paradigm of parallel processing architecture. In this presentation, we explain SOARS modeling concept, grammar of script language, detail of implementation, and example of simulation.

著者

中島 一 亀山 幸義

出版者

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

雑誌

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

巻号頁・発行日

vol.45, no.12, pp.11-24, 2004-11-15

被引用文献数

2

---

本研究の目的は,抽象化・精密化の手法を用いて,実時間モデル検査の状態数爆発問題を解決することにある.実時間モデル検査は,実時間システムの検証に用いられる手法で,そのシステムを時間オートマトンで記述する.実時間モデル検査における状態数爆発問題は,探索する状態空間が,実数値をとるクロック変数の数に対し指数的に大きくなり,実用的な時間内で検査が終了しないというものである.抽象化・精密化に基づくモデル検査法では,抽象化によりクロック変数をすべて省いた,初期抽象システムを構築し検査する.しかし,このような抽象化では検証結果として,間違った結果すなわち偽物の反例を得てしまうことがある.その場合,初期抽象システムから抽象化のレベルを低くしたシステムに作り替え,検証をやり直す.これを,正しい結果が得られるまで繰り返す.この手法の最大の課題は,得られた反例を基に,抽象化のレベルが高くかつ検証可能なシステムをどのように作るかということである.提案手法では,取り除いた変数のうち必要なものを復元する精密化を行う.また状態数を抑えるため,システム全体に変数を復元するのではなく,部分的に復元する.さらにクロック変数を復元せず不必要な遷移を除去する,もう1 つの精密化を併用することで状態数の増加を抑える.本稿では,提案手法の適用例として時間オートマトンの到達可能性解析を試み,実験でその有効性の検証を行った.We address the state explosion problem in real-time model checking. Real-time model checking automatically verifies real-time systems described as timed automata. This method suffers from the state explosion problem: the size of the state space grows exponentially with the number of real-valued clock variables. We use abstraction-refinement for reducing the state space. Using this method, an initial abstract system, which is an over-approximation to behaviors of the timed automaton, is constructed by removing all clock variables, and then the abstract system is verified. This kind of conservative abstraction may lead to a false result, that is a spurious counterexample. In this case, the abstract system is refined on the basis of the counterexample and the refined system is verified. The process is repeated until a correct result is obtained. The difficulty in this method is how the system is refined. In our approach, we extract clock variables needed in the refinement. Additionally, we do not refine the whole system but a part of the system. Besides this refinement, we introduce another refinement removing transitions which are proved to never fire in the timed automaton. Our approach avoids the state explosion problem by combining these refinements. In this work, we apply our techniques to reachability analysis of timed automata.

著者

今井 健男 山本 泰宇 遠藤 敏夫 田浦 健次朗 米澤 明憲

出版者

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

雑誌

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

巻号頁・発行日

vol.40, no.1, pp.42-56, 1999-02-15

---

我々は C++に分散オブジェクトと分散ごみ集め(分散GC)機構を導入した 分散記憶型並列計算機向け拡張言語DisCを開発する. 我々はまず 分散オブジェクトをC/C++上で扱うためのライブラリ(GCライブラリ)を開発する. これは オブジェクトがどのプロセッサ上にあるのかの判定 あるいは遠隔参照の明示的な作成等 分散オブジェクトの基礎的な機能を実現する. そしてこのライブラリに対し 動的にゴミとなった分散オブジェクトを回収する分散ごみ集めの機能を導入する. このごみ集め機構は特定の通信ライブラリに依らないため 広範な環境での動作が可能である. 次に 上記のGCライブラリを暗黙的に呼び出してリモートメソッド呼び出し等の抽象度の高い機能を 構文仕様の変更なしに実現するフロントエンドを構築する. ここでは自己反映言語OpenC++を用いる事により実装を簡便にし 保守性と移植性を確保している. そして このフロントエンドとGCライブラリを既存のC++処理系に組み合わせる事で 既存の処理系に手を加えない形でのC++の拡張を行なう. プログラマは 通常のC++プログラムでのオブジェクトの操作と同様の記述を用いて 分散オブジェクトの機能を暗黙的に使用できる. DisCは 分散GC機構を備えている他に 1)構文仕様の変更が一切なく 通常のC++と同様の記述で分散オブジェクト・プログラミングができ また 2)様々な計算機環境への高い移植性を持つ という特長がある. これにより 分散記憶型計算機上で動くプログラムの開発と保守 及び異なる分散記憶計算機間でのソフトウエア資産の共有が容易になる. 本稿では 上記ライブラリ及び言語処理系の設計及び実装手法について述べ さらに応用プログラムを作成し 実際に分散記憶型計算機上で動かして拡張言語の性能を評価する.We develop DisC, an extension of C++ that supports distributed objects and distributed garbage collection on distributed memory parallel computers. We first develop a library for C/C++, which includes basic functions to manage distributed objects. This library includes a function that tells whether an object is local or remote, functions that explicitly make remote references. It also provides a distributed garbage collection facility that reclaims objects that are no longer used. The facility is portable because of its independency from communication libraries. We also develop an front-end processor that implicitly invokes functions or the library described above, and brings higher abstractions such as remote method invocation, with no changes to the syntax of C++. We use a reflective language Open C++ to implement the processor, we achieve simple implementation and acquire its portability and maintainability. Programmers can invoke methods of distributed objects in our language as if they were normal C++ objects. Besides the distributed garbage collection facility, there are two major advantages in our language: 1)its extension involves no syntactic changes and the users can write programs with distributed objects as if they write programs in original C++, and 2) it is highly portable to various distributed parallel computers or environments, which have diverse interfaces for inter-processor communication. These advantages makes it easier to develop or maintain parallel software that are portable across various distributed-memory parallel environments. We also evaluate our extended C++ with some experiments using several parallel applications.

著者

多賀 奈由太 関口 龍郎 米澤 明憲

出版者

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

雑誌

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

巻号頁・発行日

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

被引用文献数

1

---

我々は,C++言語を拡張してC++の例外機構を利用した,通常の実行効率をほとんど損わないマイグレーション機能を実現した.通常の実行効率とは,スレッドマイグレーションの処理以外の部分の実行効率のことである.従来の多くのモーバイル言語システムでは,通常の実行効率を犠牲にしてスレッドマイグレーション機能を実装している.我々の方式はソースコード変換に基づいており多くのコンパイラとプラットフォームに適用することができる.対象となる言語は,マーシャリングができるようにポインタやunionの取り扱いなどが制限されている,我々のマイグレーション方式は透明である.つまり,場所に依存する操作以外の部分のプログラムの意味はスレッドマイグレーションの前後で変化しない.我々は複数のアプリケーションについてベンチマークを実行し,オーバヘッドを分析し,実行効率がほとんど損われないことを確かめた.We present a mobile C++ language system in which normal execution efficiency is hardly degraded, where normal execution efficiency means the execution efficiency of non-migration efficiency. In existing mobile programming languages, the normal execution efficiency is usually degraded due to the implementation of thread migration. Our implementation is based on source-code-level transformation, exploiting the C++ exception handling mechanism. Thus our thread migration mechanism can be applied to many platforms and it can be combined with many compilers. Compared to the standard C++, use of pointers and unions is restricted in our language so that data on the heap can be migrated to a remote host. Our migration scheme is transparent, namely the semantics of a single thread except location-dependent operations does not change with thread migration. We measured execution performance for several application programs, analyzed their overheads, and verified that the normal execution efficiency was hardly degraded.

著者

森住 大樹 小宮 常康 八杉 昌宏 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.45, no.12, pp.94-94, 2004-11-15

---

実時間処理を妨げる要因の1 つとしてごみ集めがあげられる.ごみ集めが一括して行われる場合には,その間プログラムの実行は一時的に停止することとなり,実時間処理の妨げとなる.この問題に対処するため,実時間処理に対応したごみ集めも考慮されているが,Real-Time Specification forJava(RTSJ)では,ごみ集めの方式自体には制限を加えることなく,実時間処理を可能としている.Lisp もごみ集めの機能を持つプログラミング言語の1 つである.本発表では,RTSJ の方法を取り入れることによって実時間処理にも利用できるように設計,実装したLisp を紹介する.具体的には,従来のヒープとは別にスコープメモリと呼ばれる実時間処理用のメモリ領域を導入する.スコープメモリはごみ集めにより使用済みのメモリ領域を回収するのではなく,ある程度の大きさでまとめて確保し,必要がなくなったら一度に破棄する.細かいメモリ管理の手間が必要なく,使用中のデータの破棄やメモリリークの恐れもない設計となっており,ごみ集めの利便性を損なうこともない.実装にあたっては,Java により記述されたScheme 処理系であるJAKLD とRTSJ を満たすJava 処理系を組み合わせることにより,効率良く実装を行うことを可能とした.Lisp に新たに追加する機能はRTSJ のJava 処理系にも含まれるものであり,実装ではJAKLD を改良しJava の機能を有効利用した.また,JAKLD を基に作成されたL 処理系に対しても,設計と実装を行った.実装されたLisp 処理系は,それ自身十分に動作するものであり,また,より高性能の本格的な処理系を作成する際に参考となりうるものでもある.Design and Implementation of Lisp System with Memory Management suitable for Real-Time Processing. Garbage collection (GC) is one of the factors obstruct real-time processing. In case that GC is executed at a time, it stops temporarily execution of program and obstructs real-time processing. For the purpose of dealing with this problem, GC corresponding to realtime processing are devised, but Real-Time Specification for Java (RTSJ) realizes real-time processing without adding restrictions to a method of GC itself. Lisp is one of programming languages with GC. At this presentation, we introduce Lisp which is designed and implemented for real-time processing by taking in the method of RTSJ. Specifically, the memory area called scope memory for real-time processing is introduced apart from the conventional heap. At a scope memory area, GC does not collects used memory, but a certain size memory is secured at a time and deleted at a time if it is not necessary. Because it is designed not to need complicated work for memory management and not to concern about deletion of necessary data and memory leak, the convenience of GC is not spoiled. It made the implementation efficient to combine JAKLD which is a Scheme system described by Java and a Java system of RTSJ. The function newly added to Lisp is included also in a Java system of RTSJ, and the function of Java was available at the implementation by improving JAKLD. We also designed and implemented to L system created from JAKLD. The implemented Lisp system works enough in it self, and it may also be referred when a more highly efficient system is created.

著者

川谷 宗之 岡本 英彰 松田 一人 北川 哲 大西秀志 番原 睦則 田村 直之

出版者

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

雑誌

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

巻号頁・発行日

vol.46, no.6, pp.61-61, 2005-04-15

---

制約プログラミングとは,「ユーザは解決したい問題を制約の形で宣言的に記述するだけで,あとは制約解消系がその制約を満たす解を求めてくれる」という問題解決手法であり,近年注目を集めている.1990 年代には商用の制約解消系が登場し,これまで制約プログラミング手法に基づく生産スケジューリング,資源割当てなどの,実用的なシステムが開発されている.しかしながら,大規模な問題に対しては,制約解消系の処理に大きな計算量が必要とされるという問題がある.一方,近年の急速なネットワークインフラの高速化,普及を受けて新しい分散処理形態であるGrid が注目を集めている.我々の研究チームでは,Grid 計算環境に制約解消系を実装することでそのパフォーマンスを向上させることを目的とし,Grid に適した制約解消系の設計および実装を進めている.本発表では,その一環として実装を行ったGrid 計算環境上の2 つの制約解消系について述べる.まずSunGrid Engine(S.G.E.)上の制約解消系の実装,次にGlobus Toolkit を用いた制約解消系の実装について説明し,最後に,これらの制約解消系と単体計算機上の制約解消系を用いてパフォーマンス比較を行った結果を示す.ベンチマークにはよく知られているJob Shop Scheduling 問題などを用いた.得られた結果のうち,多くの場合において,今回の2 つの制約解消系が単体の計算機上の制約解消系より良い結果を示しており,制約解消系をGrid 計算環境上に実装することによる有効性は十分にあると結論付ける.In constraint programming, all you have to do is to define problems as sets of constraint declaratively, and then, constraint solvers search solutions. Commercial constraint solvers appeared in 1990s and have been used for production scheduling, resource allocation, and others. Constraint solving systems are useful but there are some issues. One of them is that they need much computational power to solve large scaled problems. Meanwhile, the Grid computing is a hot topic on the recent spread of the network infrastructure. In this presentation, we show some experimental results of two constraint solving systems on the Grid. We have developed these two systems on Sun Grid Engine and Globus Toolkit respectively. In each system, constraint solvers are implemented using Cream developed by our group. Cream is a Java class library for constraint programming and provides various optimization algorithms such as Simulated Annealing, Taboo Search, etc. We use Job Shop Scheduling Problem as benchmarks. In performance, our systems on the Grid gave nice speedup compared with Cream on a single machine.

著者

長尾 雄行 土屋 陽介 森本 祥一 中鉢欣秀

出版者

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

雑誌

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

巻号頁・発行日

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

---

従来型のWeb アプリケーション開発で利用されるMVC 2.0 アーキテクチャではモデルからビューへのリアルタイムの更新が困難である.この問題に対する解決策として,Web ブラウザからの非同期通信技術であるAjax とLong-lived HTTP を利用することでWeb サーバからWeb ブラウザへ更新情報をプッシュできることに着目した.本発表ではMVC アーキテクチャの構成要素であるモデル・ビュー・コントローラを複数のWeb ブラウザと単一のWeb サーバに分散させてインターネット経由で協調動作させる「Web 分散MVC(WD-MVC)」アーキテクチャを提案する.WD-MVCアーキテクチャを利用することで,リアルタイムで情報共有が可能な分散Web アプリケーションを実装できる.Web ブラウザ側が満たすべき要件の洗い出しやサーバ負荷に関する評価やチューニング方法ついても考察する.One of the most difficult and challenging problems in the application of the MVC 2.0 architecture is how to realize the "real- time" web application by using that. Especially, there are few approach to update a view on demand in the MVC models. In this presentation, we focus on this difficulty and try to find a solution of this problem by proposing the new architecture, so called "Web Distributed MVC (WD-MVC)", in which models, views, or controllers are distributed over the internet and can cooperate with each other to constitute a single web application. In creating interactive web application, the Ajax (Asynchronous JavaScript and XML) was proposed by J. J. Garrett (2005) and it enables a web server to push messages to web browsers asynchronously. It turns out that by using this WD-MVC, we can implement a real time communication utility such that multiple users can share information simultaneously over the internet. Also, we discuss on the requirements that a user's web browser must satisfy and examine how to tune and customize the web servers to realize such web applications.

著者

山崎 憲一 吉田 雅治 天海良治 竹内 郁雄

出版者

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

雑誌

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

巻号頁・発行日

vol.42, no.7, pp.70-83, 2001-07-15

---

Lispに論理型言語の機能を融合する場合には,論理型言語特有の内部データ構造である未定義値(UNDEF)と,参照(REF)をどのように表現するかということが問題となる.本論文では,我々がTAO86およびTAOという2つの言語で採ったアプローチについて述べる.UNDEFには,必然的に構造データ中の「番地」という概念がともなうが,これをLispからどのように隠蔽するかがポイントとなる.TAO86では,UNDEFを即値とし,REFを処理系が自動的にたどる方法によって実装を行った.これにより言語が単純なものとなるが,いくつかのケースにおいては特有の問題を生じる.たとえば,REFやUNDEFを含む構造データの同一性を判定するために,アドホックな関数を必要とする.TAOでは同様の方法を採りつつも,論理変数を述語の値として返す関数型の機能,パターンマッチによる同一性の判定の機能などを用いて,これらの問題を解決する.また,本論文ではTAOのタグ割当てなど,実装の詳細についても述べる.Lisp can have much expressive power by incorporating logic-programming facilities. In this paper, we discuss implementation issues of this incorporation, especially for internal data representation such as undefined value (`UNDEF') and reference (`REF'). We designed two Lisp-based multi-paradigm programming languages, TAO86 and TAO, to solve these issues. In TAO86, UNDEF is a first-class immediate value, and REF is dereferenced by the system automatically. This solution is quite simple but did not have enough power to handle the whole set of data so that TAO86 provides some adhoc builtin functions. TAO, a thoroughly redesigned successor of TAO86, has new features such as functional predicates and pattern-matching mechanism that give an elegant solution of TAO86 issues. This paper also describes the implementation of internal data representation and data handling mechanisms in detail.

著者

任福継 財満康通

出版者

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

雑誌

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

巻号頁・発行日

vol.40, no.7, pp.93-93, 1999-08-15

---

ソフトウェア開発において ユーザーの要求を正確にプログラムに反映するためには ユーザ自身がプログラミングできることが最も望ましい.しかし 一般に ユーザはプログラムの開発者ではないので ユーザがプログラミング言語を学習しプログラムを開発するには大きな困難がともなう.ユーザにより自然言語記述で書かれた要求文をプログラムに変換するのを支援するシステムがあれば ユーザはプログラムを簡単に得ることができる.一方 コンピュータによる自然言語理解は困難であり しかも自然言語記述には要求が過不足なく反映されるとは限らない.人間にとっては十分な表現であってもコンピュータではその意図を把握することは難しい面もある.本研究ではこのような問題を解決するため 予め用意した知識により自然言語文の曖昧性の解消手法 要求細分類化によりプログラムベースの検索方法 さらに 人間の部分介入によるプログラムの生成方法を提案する.我々はこの方法に基づくプロトタイプシステムAIDPGを構築し 算数の文章問題に関するプログラム生成実験を行った.AIDPGは自然言語入力モデル(NLI-Model) 自然言語解析モデル(NLA-Model) プログラム生成モデル(PGG-Model) インタフェース制御モデル(HMC-Model)から構成される.さらに プログラム生成モデルは プログラム構造管理モデル データ構造及びデータタイプ管理モデル プログラム(関数)ベース操作と管理モデルからなる.ここで プログラムベースは予めシステムに用意されており 問題固有のプログラム(関数)の集合である.現在 AIDPGはまだ初歩的段階であるが 算数の文章問題のプログラムを生成する実験では 本研究で提案した方法は大変効果的であると考える.In this paper we describe AIDPG, an interactive prototype system, which derives computer programs from their natural language descriptions. AIDPG shows how to analyze natural language, solves ambiguities using knowledges, and generates programs. AIDPG consists of a natural language input model (NLI-Model), a natural language analysis model (NLA-Model), a program generation model (PGG-Model) and a human machine interface control Model (HMC-Model). The PGG model has three sub-models, a program structrul manage submodel, a data structurl and type manage sub-model, and a program base manage sub-model. We used arithmetic problems which descripted in Japanese to pass AIDPG and got their run-possible C programs. Although AIDPG is basic corrently we got a significant result.

著者

米田 匡史 鵜川 始陽 花井 亮 八杉 昌宏 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.47, no.11, pp.38-49, 2006-07-15

---

リージョン推論と呼ばれる静的にオブジェクトの寿命を見積もる手法に基づくメモリ管理が,Tofteらによって提案されている.リージョン推論に基づくメモリ管理では,オブジェクトはリージョンと呼ばれるメモリブロックのいずれかに生成される.リージョンは特定のスコープを抜けると解放され,そのリージョン内に生成されたオブジェクトも同時に解放される.そのため,再帰呼び出しのように,関数呼び出しが連続する場合にはリージョンの解放ができない.Tofteらの処理系では,今後の計算においてアクセスされる可能性のあるオブジェクトが入っていないリージョンにオブジェクトを生成する際に,そのリージョンに入っているオブジェクトに上書きして生成しようとしている.しかし,関数がリージョンをリージョン変数に受け取ることができるため,リージョン変数のエイリアスが生じ,静的にオブジェクトを上書きしてもよいと判定できる箇所が限られる.本論文では,問題となるエイリアスが存在するかどうかを,実行時にオブジェクトを生成する際に調べる手法を提案する.これにより,Tofteらの手法では上書きしてよいか分からなかったオブジェクト生成の箇所で,より厳密に判定できるようになる.その結果,メモリ効率が向上し,これまで妥当なメモリ使用量で動かなかったプログラムが動くようになると期待される.A technique for memory management based on region inference, which statically estimates the life-time of objects, was proposed by Tofte, et al. With this technique, objects are created in one of the memory blocks, called regions. Each region is deallocated when the control flow exits its corresponding scope and all objects in the region are deallocated at that time. This means that systems cannot deallocate regions while function calls are repeated without returning. This often happens in the case of recursive function calls. Tofte implemented a system which creates a new object by overwriting existing objects in a region if the region has no object that might be accessed in the rest of the computation. However, there are not a few points of object creation at which his static analysis cannot find it possible to overwrite. This is because functions may receive regions as region variables and there may be aliases of region variables. In this paper, we propose a technique to improve memory usage by checking the existence of problematic aliases at runtime. Our technique can determine exactly whether it is possible to overwrite in many points of object creation where Tofte's analysis fails. As a result, we expect more programs to run with a relatively small amount of memory in region-based systems.

著者

近藤 秀樹 小出 洋 三宅 芳雄

出版者

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

雑誌

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

巻号頁・発行日

vol.48, no.12, pp.19-27, 2007-08-15

被引用文献数

1

---

我々は PC 上でのユーザの活動履歴を包括的に記録し活用する NecoLogger というシステムを開発した。履歴の中から必要に応じて有用な一連の活動の様子を取り出して、当面の問題解決に役立てるためのシステムである。本論文では、開発したシステムの設計と実装方式、複数ユーザの利用から得られた運用実績について報告する。膨大な活動履歴から必要に応じて過去の活動から有益な情報を得るため、人が思い出せる断片的なキーワードでも活動を取り出せるよう、できるだけ多くの検索可能なテキスト情報を記録しておく必要がある。本システムでは打鍵履歴のような PC の操作内容だけでなく、画面に表示されている文字列も検索可能にするために、OS レベルの API をフックし、画面上のテキスト情報をアプリケーションにとらわれずに記録する手法を実現した。人の活動は画面全体に広がっているため、画面の様子から活動内容を読み取れるよう、画面イメージを記録することも重要である。しかし動画で記録し続けると情報量が膨大になり、現実的ではなくなる。そこで人の活動がまとまりを持つことを利用し、画像を断続的に記録することで情報量を削減し、実用的に活動履歴を記録するよう工夫した。また、規模の大きなシステムは漸次的に開発できるほうが良いが、一方で、履歴を扱うシステムは開発初期から一貫して履歴を蓄積し続けなければならないため、開発中にデータ構造を変更するのが困難である。そこで、十分に拡張性のある中間フォーマットを設計し、柔軟なシステム開発を可能にした。これらの工夫によって、2年以上にわたって、活動履歴を実際に蓄積・活用しつつ、同時に、ユーザの利用実態に適合した有用なシステムを漸次的に開発することが可能になった。We have developed NecoLogger, a recording-retrieving system that records the entire activity of personal computer use. Using NecoLogger, users can retrieve useful information and utilize it for their current problem solving. In this paper we report the overall design of the system and the details of its implementation. We also report the operational findings to show the usefulness of this system. In order to retrieve user activities efficently, we record the textual information on the screen regardless of the applications software by utilizing API hooks in OS. We also record screen images intermittently to restore the entire activity of a user. Logging the user's entire activity requires large amount of data area and it is necessary to reduce the amount to a practical level. We reduce the amount by taking screen shots at the optimal interval. Since our system should be developed extensively in the course of the development, we had to modify data structures quite often to store logging data. We adopted the XML format to meet the requirement. By adopting these methods mentioned above, we have been able to accumulate logging data continuously and have developed the system progressively to meet the newly found requirements based on the actual uses of the system.

著者

西崎 真也 小田 崇史

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.13, pp.116-116, 2003-10-15

---

AbadiとCardelliにより提唱されたオブジェクト計算は,大変簡潔な構文と意味論により定義されるにもかかわらず,セルフパラメータの遅延束縛などオブジェクト指向言語の主要な計算機構をモデル化することに成功している.継続とは,計算のある時点における計算の残りの部分を表現する概念であり,実行系の内部状態の1つである.ファーストクラス継続は,ある時点の継続をデータとして保存したり,データとして保存した継続をしたりすることを可能とするものである.ファーストクラス継続は,プログラミング言語Schemeで実現され,コルーチンやバックトラックなどを表現できることが知られている.本研究では,オブジェクト計算にファーストクラス継続の概念を導入した継続オブジェクト計算を提唱する,この体系において,意味論は評価文脈を用いて定義される弱簡約関係により与えられる.ファーストクラス継続は,評価文脈をフィールドに保存する継続オブジェクトとして形式化される.最初に型なし継続オブジェクト計算を紹介する.次に,継続オブジェクト計算の1階型体系を与え,主部簡約定理を示す.さらに,部分型体系を与え,主部簡約定理のほか,基本的性質を示す.With the advance of information society, releasing the software at an early stage that satisfies users has been required, and therefore it has been more important to quickly develop the software that the user can check and feed back. In software development, based on users' concept, developers make the specifications of a program cooperating with the users, and then design, make, test and debug the program. Through this procedure, programs are completed. If we can use the image that users have to design a program, and if the program is completed when the design finishes, we can easily develop software and reduce the time required to develop it. This presentation presents an approach to a brain-image oriented programming method and describes the BioPro system that implements this method for Web applications. The brain-image oriented programming has the features that users can develop programs based on their image, (2) easily verify the completeness of components that make up the program and the consistency between them, and (3) easily confirm what they have developed so far in the middle of the development.

著者

内山 雄司 緒方 大介 脇田 建

出版者

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

雑誌

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

巻号頁・発行日

vol.46, no.6, pp.1-17, 2005-04-15

被引用文献数

1

---

著者らが開発したバイトコードインタプリタ生成系であるVirtualMachineBuilder(VMB)について発表する.VMBは,仮想機械の仕様記述を入力として,仮想機械の中核をなすインタプリタの実装を生成するシステムである.VMBに与える仕様記述は,仮想機械を構成するレジスタやスタックの定義と,仮想機械で実行される各バイトコード命令の意味の定義からなる.バイトコード命令の意味は,仮想機械の状態遷移の形で表現される.以前のVMBには,データ型の宣言やオブジェクト間の参照の表現力に不十分な点があり,バイトコード命令の意味を記述する際に特別な工夫を必要とする場合があった.本研究では,仕様記述言語を再設計して,より自然な形で仮想機械の仕様を記述できるように工夫した.VMBを適用した処理系開発の事例として,簡単な手続き型言語に対するバイトコード言語を設計し,その処理系を実装した.さらに,VMBを利用してObjectiveCamlのインタプリタを実装し,仕様記述言語の表現力と生成されるインタプリタの性能という2つの観点からVMBの評価を行った.表現力については,146命令のうち133命令を自然な形で記述できた.インタプリタの性能については,ベンチマークテストの結果,手書きのインタプリタで実行した場合の93%の性能が得られた.The article proposes Virtual Machine Builder (VMB) which is a bytecode interpreter generator developed by authors group. VMB takes a specification of a virtual machine and generates implementation of the interpreter which compose a main part of the virtual machine. A specification of a virtual machine comprises a definition of a virtual hardware composed from registers and stacks, and a definition of the behavior of each virtual machine instruction. The behavior of an instruction is specified in terms of a machine state transition system. In the previous version of VMB, there were cases that we needed some tricks to specify the behavior of an instruction since the specification language lacked the way to declare data types of objects and to express references between objects. We redesigned the language so one could specify instructions more naturally. The article also shows an experience in developing tiny imperative language system using VMB. Also the expressiveness of the specification language and the perormance of the generated interpreter are evaluated by the use of a virtual machine of Objective Caml 3.08 generated by VMB. On the former point, 133 of 146 bytecode instructions can be defined naturally. On the latter point, a benchmark test shows that the efficiency of the generated virtual machine is 93% of a carefully implemented human-crafted one.

著者

永山 友和 佐藤 雅彦 亀山 幸義

出版者

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

雑誌

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

巻号頁・発行日

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

---

仕様からプログラムを開発する際,抽象的な仕様を具体的なプログラムへ変換することが行われている.抽象的な仕様には,用いるプログラミング言語では与えられていないデータ構造が含まれている可能性があり,具体的なプログラムとは,それらのデータ構造が実現されたプログラムである.このような変換のことを"詳細化"と呼ぶ.Honsellは,Pre Logical Relationを用いる,詳細化の正しさの証明技法を提案した.本研究では,定理証明システムCoqを用いて彼らの技法を形式化した.このことより,計算機上でプログラムの詳細化の正しさを厳密に証明することができる.In developing programs form specifications, we transform abstract programs (specifications) into concrete programs. Abstract programs may have data, which are not available in our programming languages. In concrete programs, these data are represented by data which are provided. We call these transformation data refinement. Honsell suggest proof method of data refinement which use pre-logical relation. In this paper, we formalize their method with Coq. As a result, we can strictly prove the correctness of data refinement on computer.

著者

吉川 隆英 田浦 健次朗 近山 隆

出版者

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

雑誌

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

巻号頁・発行日

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

---

世代GC 方式において,新たに生成されたデータは,何回かのGC を経た後,旧世代領域に移される.これを「殿堂入り」という.殿堂入り時期が遅すぎると,長寿命データと新世代ゴミが長期間新世代メモリ領域に混在するため,ユーザプログラム中や新世代GC 中でのキャッシュヒット率が低下する.逆に,殿堂入り時期が早すぎると,短寿命データが新世代領域で回収できず,新世代GC の回収効率が悪化し,旧世代GC が発生しやすくなる.殿堂入りの適切な時期は,プログラムによって,また1 つのプログラムの中でもその実行フェーズによって異なる.これまで,プログラム実行時に動的に殿堂入り時期を調節する手法はいろいろ提案されてきたが,主に新世代GC の回収効率を改善することに主眼がおかれており,キャッシュの効果が,動的な殿堂入り時期調節の基準に,実験データに裏打ちされる形で明快に反映されていなかった.そこで本研究では,まず,様々なプログラムにおいて,実際のデータ寿命分布,殿堂入り時期の違いによるキャッシュミス数と実行時間の測定を行い,メモリ領域中のデータの振舞いに対するモデルを作成した.そして,このモデルに基づく殿堂入り時期調節手法の提案を行った.また,この殿堂入り時期調節手法を,ヒープサイズを自動調節する世代GC を行う並行並列論理型言語処理系KLIC 上に実装し,動的に殿堂入り時期調節を行わない世代GC との性能比較を行った.In generational GC schemes, objects are allocated to the young generation area and are advanced to the old generation area after surviving a small number of collections. This advancement is called tenuring. Tenuring too late makes some short-lived objects that some of them have already become garbage and long-lived objectsreside together in the young generation, making memory reference locality worse. On the other hand, tenuring too early makes it impossible to collect short-lived objects in the young generation; its mark/cons ratio becomes worse and, as short-lived objects are moved to the older generation, more older generation GCs will be required. For the best performance, we should adjust tenuring timings dynamically according to programs and their execution phases. Many adaptive tenuring policies have been proposed.However, most of them aim at improving mark/cons ratio of the younger generation and improvementsin cache performance are not proven with experimental evidences. In this work, we (1) measure object lifetime distributions on several programs, and how cache misses and execution times vary with different tenuring timings, (2) make a simple analytical model to estimate an appropriate young generation size, (3) propose a cache-conscious adaptive tenuring policy, and (4) implement dynamic young generation size adjustment mechanism with this policy into KLIC and compare its execution time to one with conventional generational GC on several programs.