著者

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

出版者

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

雑誌

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

巻号頁・発行日

vol.45, no.5, pp.81-81, 2004-05-15

---

近年,教育課程の改定により,小学校から高等学校までの初中等教育において,プログラミングを含む情報教育の導入が進められている.筆者らは,初中等教育で活用可能な教育用オブジェクト指向言語「ドリトル」を開発し,提案を行ってきた.本稿では,プログラムの中からオブジェクトをネットワーク間で複製・共有して扱うドリトルの拡張について報告する.この機能により,ある生徒がドリトルの任意のオブジェクトに名前を付けて公開したときに,他の生徒はそのオブジェクトを自分のプログラムに取り込んで再利用したり,共有して使ったりすることが可能になった.授業の中では,生徒が個人ごとに独立したプログラミングを行うだけでなく,複数の生徒が共同で作業する形のプログラミングを行うことが可能である.共有機能の実装は,Java2 で記述されたドリトルの処理系に,RMI(Remote Method Invocation)を用いた通信機能を組み込むことで拡張を行った.The Japanese government has been promoting IT education at elementary and secondary schools since 2002. In this presentation, we describe design and implementation of object sharing for "Dolittle" programming language. Students can release their objects into network in the classroom. Then other students can copy or share objects in their programs. By using object sharing, students not only can make program by oneself, but also can make program with collaboration. We implemented object sharing using Java RMI (Remote Method Invocation).

著者

内山 雄司 脇田 建

出版者

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

雑誌

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

巻号頁・発行日

vol.43, no.1, pp.10-24, 2002-01-15

参考文献数

19

被引用文献数

1

---

メモリ管理機能のモジュラーかつ効率的な実装手法を提案する.言語処理系の実装においてメモリ管理機能をモジュラーな設計とすることは,既存の処理系に新たなメモリ管理アルゴリズムを実装することを容易にする点で有用である.まず,メモリ管理機能のモジュラーな実装を可能とするために,本研究では,実行時システムとメモリ管理機能との間に抽象的なインタフェースを定義する.このインタフェースはプログラム実行時のメモリ操作を抽象化し,広範なメモリ管理アルゴリズムを抽象的に記述する手段を提供する.また,メモリ管理機能をモジュラーな実装とした処理系の高速化のために,本研究では,実行時システムの特化手法を提案する.一般に,インタフェースの導入による抽象化には,実装上のさまざまな工夫による高速化を妨げるという問題がある.提案する手法は,メモリ管理機能の仕様に基づいて実行時システムの実装を自動的に特殊化することで,モジュラーな実装にともなうオーバヘッドを解消する.本研究では,提案した手法に従って既存の処理系のメモリ管理機能を再実装し,ベンチマークテストを用いて,それぞれの実装での実行性能を比較した.その結果,本研究が提案した特化手法がモジュラーな実装にともなう10%程度のオーバヘッドを解消し,既存の処理系と同等の性能を達成することを示した.The article describes a novel design and implementation scheme of memory management systems for programming languages. The scheme is modular in that it allows the memory management system to be replaced without modifying the rest of the programming language implementation. It is efficient in that the scheme incorporates optimization of the memory management interface to eliminates possible overhead incurred from using this interface. The paper defines an abstract interface between the runtime system and the memory management substratum. Though the interface is simple it is flexible enough to describe variety of memory management algorithms. Execution efficiency is achieved by a specialization technique that specializes the programming language implementation with respect to the implementation of the memory management system. Modular design typically incurs execution overhead due to use of generic interface definitions. This inefficiency is resolved by adding efficient bytecode instructions which are specialized for a given memory management system and also applying a bytecode transformation technology that make use of the added instructions. This memory management interface and the specialization technique has been implemented used for description of various memory management algorithms and tested effectiveness of the approach with a number of small- to medium-scale benchmark programs. The results show that for most cased the specialization technique removes 10\% overhead which is otherwise incurred from using our abstract interface."

著者

向井 国昭 井出 陽子

雑誌

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

巻号頁・発行日

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

---

高階述語の引数としてソート付きのラムダ式を許す評価器 (eval),および,適用可能な部分がなくなるまで書き換え規則を適用する項書き換え器 (reduce),この 2 つの述語を SWI-Prolog の上に実装した.関数を表す通常のラムダ項のほかに関係を表すラムダ項を新たに導入した.この導入により,Prolog の特長であるデータの流れの双方向性を活かす,いわば関係型のラムダ計算を実現した.Eval は代数構造における準同型規則を解釈する述語であり,reduce は等号論理のパラモジュレーション規則を解釈する述語であると見なす.つまりいずれも簡潔明快な根拠を持つ計算モデルに基づいて設計した.適用例として Emacs-lisp・Ajax・Unix シェルをとりあげ,それらと Prolog の間のインタフェースの実現方法を示す.Emacs-lisp へは S 式を送信し,それを実行させることにより制御する.こうして Emacs バッファの複雑な編集・制御に,宣言的な Prolog の限定節を用いることができる.Ajax とのインタフェースは,Ajax が関数式を Prolog CGI に送信し,Prolog はそれを eval 述語で評価し,結果の値を HTML として Ajax のフィルタに返信する,という流れである.Unix シェルの呼び出しは,Bash コマンドをまず Prolog の項として表現・生成・操作し,最後にそれを eval 述語でコマンドラインテキストに変換して Unix シェルに送信する.Two interpreters have been written on Top of SWI-Prolog; the one interprets sorted expressions including lambda calculus as arguments of higher order predicates calls, ant the other interprets term rewriting rules. Not only the functional lambda terms but also relational lambda term are now availabe adapted to bi-directional data flow feature of Prolog. In other words, a class of relational lambda caculus is now in Prolog. The implementation obeys fairly general two views that evaluation is homomorphism between algebras of a same kind, and that that on the other hand term rewriting rules are paramodulation of logics with equality. Thus our implementation is based on theoretical clear justifications. As applictions, some interface codes to Emacs-lisp, Ajax, and Unix-shell are illustrated; the extended prolog controls in a declarative way emacs-lisp using S-expressions and Prolog terms depending on the direction, talks with Ajax in Prolog terms, and communicates Bash shell using abstract unix command syntax in Prolog terms. These heterogeneous communications are described in an elegant and unified way based on the two new interpeters.

著者

向井 国昭 井出 陽子

雑誌

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

巻号頁・発行日

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

---

高階述語の引数としてソート付きのラムダ式を許す評価器 (eval),および,適用可能な部分がなくなるまで書き換え規則を適用する項書き換え器 (reduce),この 2 つの述語を SWI-Prolog の上に実装した.関数を表す通常のラムダ項のほかに関係を表すラムダ項を新たに導入した.この導入により,Prolog の特長であるデータの流れの双方向性を活かす,いわば関係型のラムダ計算を実現した.Eval は代数構造における準同型規則を解釈する述語であり,reduce は等号論理のパラモジュレーション規則を解釈する述語であると見なす.つまりいずれも簡潔明快な根拠を持つ計算モデルに基づいて設計した.適用例として Emacs-lisp・Ajax・Unix シェルをとりあげ,それらと Prolog の間のインタフェースの実現方法を示す.Emacs-lisp へは S 式を送信し,それを実行させることにより制御する.こうして Emacs バッファの複雑な編集・制御に,宣言的な Prolog の限定節を用いることができる.Ajax とのインタフェースは,Ajax が関数式を Prolog CGI に送信し,Prolog はそれを eval 述語で評価し,結果の値を HTML として Ajax のフィルタに返信する,という流れである.Unix シェルの呼び出しは,Bash コマンドをまず Prolog の項として表現・生成・操作し,最後にそれを eval 述語でコマンドラインテキストに変換して Unix シェルに送信する.

著者

田中 陽 亀山 幸義

雑誌

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

巻号頁・発行日

vol.48, no.SIG12(PRO34), pp.67-67, 2007-08-15

---

本研究は、関数型言語 Scheme における動的環境と限定継続の共存について検討し、形式的意味論を定義し、それに基づく実装を与えたものである。動的環境はプログラム実行時に動的に決定される環境で、Scheme では、プログラム中の手続きが一定の動的環境を持つことを保証するための機構として、dynamic-wind が用意されている。限定継続は、「計算の残りの一部」のことである。Scheme の標準手続き call/cc が、「計算の残り」全体を操作するのに対して、本研究で扱う shift/reset はこの限定継続を操作し、種々の探索問題などがより簡潔に記述できるようになる。すでに知られているように、dynamic-wind と call/cc の共存は容易ではない。Scheme の仕様書 R5RS の形式的意味論はこれらの共存に対応しておらず、後の研究で修正された。我々は、shift/reset を Scheme に追加し、記述力を向上させる研究を行っている。本研究はその一環として、dynamic-wind と shift/reset の共存について取り組んだものである。まず、R5RS の表示的意味論を拡張して、shift/reset に対応した意味論を与える。次に、プログラムの実行が dynamic-wind の性質を保証することを示すために、その意味論に対応する抽象機械を導く。またあわせて、この意味論に基づいた Scheme インタプリタを作成し、shift/reset と dynamic-wind を含むプログラムが正しく動くことを確かめた。

著者

森口 草介 渡部 卓雄

雑誌

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

巻号頁・発行日

vol.2, no.5, pp.43-43, 2009-11-20

---

アスペクト指向が提案されて十余年たち,ソフトウェア工学の広い分野で用いられている.しかしながら,アスペクトとは何であるかを議論することはほとんどなく,ただAspectJに代表されるジョインポイントモデルにおけるモジュールをアスペクトとすることが多い.このように本質を定義しないままの議論は実際の言語に強く依存したものとなり,またツールにおけるアルゴリズムとその実装もアドホックになる.アスペクト指向はモジュール化を主眼としたものであり,その特徴はアスペクトモジュールの結合方法にあるといえる.本研究では,この結合方法を抽象化および定式化し,アスペクト指向の理解や議論の基礎とすることを目標としている.本研究の特徴はアスペクト指向言語のとらえ方にある.現存するアスペクト指向言語は,既存の言語に対して拡張を施すことによって作成されている.一方,既存研究ではアスペクト指向言語を1) ラムダ計算のような既存の計算体系にアスペクト指向を加えたもの,または2) 言語全体を記述する体系で定式化している.それに対し,本研究では2) と同様に既存の計算体系に依存せずにアスペクト指向としての操作の定式化のみを行い,他の体系との組合せによって1のように言語を表現する.本発表では,アスペクト指向における操作の定式化と,ラムダ計算との組合せによる言語の定式化,および他研究における議論の表現について述べる.Aspect-orientation has gained in software development in the last decade. However, formal and/or general definitions of aspects and related concepts are not thoroughly discussed so far. The important concepts such as aspect, join point, pointcut, advice, etc. are defined on top of specific aspect-oriented languages such as AspectJ. Our goal is to formalize some'aspectual'operations commonly used in aspect-oriented languages. We designed a simple calculus that models the operations independently from other computational activities such as function application or message passing. We can easily construct a model of a specific aspect-oriented language by mixing our calculus with another model that represents the base computation. In this presentation, we give a formalization of the aspectual operations in our calculus and then discuss the formalization by comparing to other works.

著者

森本真一

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.2, pp.41-41, 2003-02-15

---

本発表では,文脈自由文法に対するボトムアップ型構文解析アルゴリズムのカテゴリ理論に基づく導出を行う.カテゴリ理論は,問題の本質的な部分を自然に記述できるため,高水準の使用記述や仕様変換に適している.このためカテゴリを用いた仕様記述も行われているが,それらはデータ構造の記述が中心であり,データを扱う制御構造に対する記述はあまり行われていない.そこで本発表では制御構造に対する仕様記述の例として,文脈自由文法に対するボトムアップ型構文解析アルゴリズムをカテゴリ理論に基づいて導出する.文脈自由文法に対する構文解析は実際的な問題であり,これまで多くのアルゴリズムが提案されてきたが,仕様記述という点からは論理式(集合論)に基づく検討以外はあまり行われていなかった.本発表では,構文解析アルゴリズムをカテゴリ理論によって導出することにより,論理式による導出との比較を行う.本発表では,文脈自由文法の構文記号や構文規則などを対象とし,それらの間の射から,最左導出の逆としてボトムアップ型構文解析アルゴリズムを導出する.さらに,対象となる文法をLR 文法に限定した場合に,このアルゴリズムがどのように簡略化されるか(LR 構文解析アルゴリズムに帰着されるか)を述べる.In this presentation, I derive bottom up parsing algorithms for context free grammars by categorical approach. For a context free grammar G, I consider a category whose objects are symbols and rules of G. From this category, I derive bottom up parsing algorithms for G by categorical operations. I also show how this algorithms are reduced to the LR parsing algorithm if G is an LR grammar. Finally I compare this categorical approach for derivation of parsing algorithms with a set theoretic (logical) approach.

著者

中田 秀基 井上 辰彦 工藤 智宏

雑誌

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

巻号頁・発行日

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

---

Sawzallは,Google が 2006 年に発表した大容量データの並列バッチ処理に適した言語である.Sawzall の計算モデルは MapReduce 型の分散演算であるが,リダクション操作を組み込みの Aggregator に限定することで,エンドユーザによる容易な記述を可能にしている.我々は現在開発中の並列データ処理機構上の言語処理系を開発するための 1 ステップとして,Scala 言語による Sawzall 言語のサブセット処理系を実装した.文法やセマンティクスに関しては明確な定義がなかったため,2006 年の論文をベースに推測した.その結果,最近公開された Sawzall 処理系とは機能的に若干の相違がある.構文解析にScala言語の Parser Combinator を用いることで,処理系の記述量が削減できた.現在の実行対象処理系は Hadoop である. Hadoop の Mapper 上で言語インタプリタを動作させ,Reducer 上では我々の提供する Aggregater を動作させる.Scala は Java VM 上で動作することから,Java で記述される Hadoop 上での実行は容易である.本発表では,本処理系の実装について詳しく述べる.さらに,Hadoop で直接記述した場合と,プログラム量および実行速度の点で比較を行う.比較の結果,プログラム量は大幅に小さくなる一方,実行速度の面でも一定のオーバヘッドがあることが確認された.Sawzall is a script language designed for batch processing of large amount of data, which is introduced by Google in 2006. The processing model of Sawzall is the MapReduce. Sawzall allows programmers only to program 'mappers' to ease the burden. Sawzall provides a set of 'built-in aggregaters', from which programmer choose mapping function. We are developing distributed data processing system for large scaled data. As a part of the project, we have iplemented an interpreter for Sawzall subset in Scala language. We employed paser combinator for lexical parsing. Currently, the system is running on Hadoop. In the paper, we provide detailed implementation of the system. We also evaluated the system with naked Hadoop in terms of program size and execution speed. We confirmed that, with Sawzall, program size is much smaller, while there are certain overhead in terms of execution speed.

著者

森川 和哉 鵜川 始陽 岩崎 英哉

雑誌

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

巻号頁・発行日

vol.6, no.1, pp.27-27, 2013-01-24

---

Jikes RVM上で,ビットマップマーキングを利用したマークコンパクトごみ集めを実装し評価した.マークコンパクトごみ集めで広く使われているLisp 2アルゴリズムでは,オブジェクトの移動処理のために,生きているオブジェクトをアドレス順に2回探索する.本手法は,オブジェクトの生存情報をビットマップを使って保持し,そのビットマップをスキャンすることによって,生きているオブジェクトを探索する.生きているオブジェクトが少ない場合,ビットマップ上ではゼロビットが連続しているため,この探索を高速化することができる.提案するごみ集めの性能をDaCapoベンチマークを用いて評価したところ,プログラムによっては,ヒープの使用率が低い場合に,Jikes RVMに標準で搭載されているマークコンパクトごみ集めよりも優れた結果を示した.

著者

岩間 太 五十嵐 淳 小林 直樹

出版者

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

雑誌

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

巻号頁・発行日

vol.48, no.4, pp.48-61, 2007-03-15

---

ファイルやメモリなどの計算資源がプログラム中でどのように使用されるかを型を用いて推論するための手法が五十嵐,小林らにより提案されている.彼らの手法では,各計算資源に対して起こりうるアクセス列の集合を使用法表現と呼ばれる式として推論する.しかしながら,推論された使用法表現が表すアクセス列の集合が,仕様として許されるアクセス列からなる言語に包含されているかどうかを判定するアルゴリズムが考案されておらず, 計算資源使用法検証の完全な自動化は達成できていなかった.本論文では,ある特定の言語クラスに属する仕様に対し,そのような包含判定を行うための健全かつ完全なアルゴリズムを提案する.仕様として任意の正則言語を許す場合には,包含判定問題は決定不能なので,我々のアルゴリズムが扱う仕様のクラスは,1つの入力記号について,遷移元および遷移先の状態がたかだか1つしか存在しない有限オートマトンが受理する言語のクラスとして与えられ,正則言語のクラスより小さい.しかしながら,ファイルなど現実の計算資源の仕様の多くは,我々のアルゴリズムで扱える言語のクラスに属する.したがって,本論文のアルゴリズムを五十嵐と小林らによる従来の研究と組み合わせることにより,ファイルなど多くの計算資源の使用法検証を自動化できる.In our previous work, we have developed a type-based method for inferring how resources such as files and memory are accessed in a program. Due to the lack of an algorithm for deciding whether the inferred resource usage conforms to the specification, however, it was not possible to verify automatically that resources are accessed according to the specification. In this paper, we propose a sound and complete algorithm for deciding the conformance of the inferred resource usage to the specification. Since the language denoted by the inferred resource usage belongs to a class larger than the class of the context-free languages, the class of specifications that our algorithm can deal with is smaller than the class of regular languages. Fortunately, however, that language class contains many of the typical resource usage specifications used in practice. Thus, by combining our algorithm with our previous method for resource usage inference, we can automatically check whether each resource is accessed according to the specification in many cases.

著者

服部 健太

雑誌

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

巻号頁・発行日

vol.5, no.2, pp.99, 2012-03-30

---

Hindley/Milner多相型システムは様々なプログラミング言語の型システムの基盤として広く用いられてきた.現実的なプログラミング言語においては,Hindley/Milner多祖型システムの表現力を高める必要があり,多相レコードやオーバロード,型クラスといった数多くの拡張が提案されてきた.これらの拡張は,型変数に述語やカインドといったある種の制約を付け加えることで実現している.我々はHindley/Milner多相型システムを拡張するための新しいアプローチを提示する.我々のアプローチの鍵は,(1)暗黙的に型づけられたプログラムをそれと同等な明示的に型づけられたプログラムに変換し,(2)型レベルでそのプログラムを評価しながら型判定を行う,というものである.我々のアプローチは,制約付きの型のように型システムを複雑化することなく,簡単に拡張することができる.本発表では,例としてオーバロードと多相レコードを扱うシステムについて検討する.

著者

佐々木 晃 須賀 康行

雑誌

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

巻号頁・発行日

vol.1, no.2, pp.124-124, 2008-09-26

---

本発表では,プログラミングを支援する言語指向エディタの自動生成手法を提案する.本研究で対象とする言語は,汎用プログラミング言語ではなく,特定の分野で使われることに目的を特化した言語,ドメイン特化型言語である.このような言語の利用者は必ずしもプログラミングの知識を持つわけではない.そこで,プログラミング支援をする専用の言語指向エディタが不可欠となる.たとえばGUIによるウィザード形式でテンプレートに埋めながらプログラムを完成させるようなエディタが考えられるが,そのような単純なものでも,開発では,言語仕様を満たすための緻密性が要求される.したがって,自動生成による開発コスト削減,保守性の向上が望まれる.汎用言語に対する言語指向エディタの自動生成は,インクリメンタル構文解析,属性評価など関連する研究が古くからなされている.一方で,今回想定しているエディタでは,プログラマが編集するものはプログラムのテキストではない.そこで本研究では,テキストの構文などを抽象化した抽象構文木を編集させるという視点を持ち,木の文法(tree grammar)に基づいた仕様記述に基づいてエディタを生成する方法をとる.この方式では汎用言語における構文エラーは発生しない.一方で,言語要素の型や静的意味チェックが必要となるが,これは属性文法に基づく手法を用いる.本発表では,以上で述べた仕様記述やエディタ生成のアルゴリズムの詳細,本研究の評価について実例を交えて示す.We propose a method for generating language-oriented editors. Target languages in this study are domain specific languages that are specialized to supporting tasks in specific domains. Primary users of such languages do not have programming skills. This means we should also offer a programming development tool with the language processor. These tools are expected to be generated from specifications, since the development and maintenance cost of such tools tends to be high. There are several studies on syntax-oriented editors for general purpose programming languages, such as incremental parsing and attribute evaluation techniques. On the other hand, in this study, it is not a program text that a programmer is to edit. Therefore, our approach to generating such tools is based on abstract syntax trees (ASTs) in which text structure is abstracted out. The method for checking of static semantics is based on the attribute grammar formulation. In this presentation, we will show the details of specification, generating algorithms, and evaluation with experiments.

著者

松崎 公紀 江本 健斗 劉 雨

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.4, no.4, pp.1-11, 2011-09-22

---

正規表現は広く用いられており,文章が正規表現にマッチするかどうかの問合せ (クエリ) を効率的に実行することは重要である.これまで,正規表現マッチングを高速に行う逐次的な手法について多くの研究がある.正規表現マッチングを並列に行う方法についても研究があるが,その多くは,複数の文章に対するクエリの並列実行や,複数のクエリの並列実行というような自明な並列実行について扱うものである.一方で,巨大な 1 つの文章に対して 1 つのクエリを行う場合には,正規表現マッチングそのものを並列化する必要が発生する.本稿では,正規表現マッチングを並列化する手法について議論を行う.また,本稿で提案する正規表現の並列マッチングの計算効率を評価するため,Hadoop を用いて実験を行いその結果を報告する.Hadoop は,大規模分散データに対して効率的に処理を行うことができる MapReduce フレームワークのオープンソース実装である.Regular expressions are now widely used and efficient implementation of regular expression matching is an important issue for efficient manipulation of data. There have been many studies for efficient implementation of regular expression matching. There have also been studies on parallel implementations of regular expression matching, but these implementations exploit parallelism only in executing a single query on multiple documents or in executing multiple queries on a single document. In this paper, we discuss a technique to parallelize a regular expression query itself. In other words, with this technique we can execute a regular expression query on a single document in parallel. We evaluate efficiency of regular expression matchings parallelized by the proposed method on the Hadoop; the Hadoop is an open-source implementation of the MapReduce framework that enables efficient processing of large-scale data.

著者

新名 庸生 佐藤 雅彦 馬谷 誠二 八杉 昌宏 湯淺 太一

雑誌

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

巻号頁・発行日

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

---

プログラミング言語Zには簡潔で厳密なセマンティックが与えられており,将来的にはZで記述したプログラムついてもその数学的,論理的性質を素直に記述,証明できる言語になることを目指している.今回はZのコア言語となるpure Zと,Javaで書かれたLisp処理系JAKLDを基にしたpure Zの実装を紹介する.JAKLDは携帯電話でも動くコンパクトさと改造しやすさからpure Zの実装に適している.今回のpure Zの実装は今後の拡張に備え,コンパクトさと改造のしやすさを引き継いだ実装になっている.The programming language Z is given a simple and strict semantics, and we expect we will be able to easily describe mathematical and logical properties of programs written in Z in the future. In this search, we introduce a core language of Z called pure Z and its implementation based on JAKLD, a Lisp system written in Java. JAKLD is suitable for the purpose because it is so compact that some versions of it runs on mobile phones and designed so that it will be easy to add, delete, and modify its functionalities. Our implementation of pure Z keeps the compactness and easiness for the next extension.

著者

鵜川 始陽 皆川 宜久 小宮 常康 八杉 昌宏 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.13, pp.72-83, 2003-10-15

---

実行にスタックを利用している処理系でファーストクラスの継続を生成する場合,スタックの内容をヒープにコピーするのが一般的である.スタックの内容をヒープにコピーする戦略には様々なものが提案されているが,実際の処理系の多くはスタック法を採用している.スタック法では継続の生成のたびに処理系のスタック全体の内容をヒープにコピーする.このように,スタック法は動作が単純なので簡単に実装でき,また他言語呼び出しをサポートした処理系でも利用できるという長所がある.しかし,継続の生成に時間がかかり,また,メモリ効率が悪いという欠点があり,利用の妨げとなる場合もある.本発表では,スタック法による継続の生成に対する効率化手法として,スタックのコピーの遅延を提案する.継続の生成によりコピーされるスタックの内容は,継続を生成した関数からリターンするまでスタック上にも残っている.したがって,スタックのコピーを継続を生成した関数からリターンするまで遅らせてもよい.もし,生成した継続が,スタックをコピーする前にごみになれば,スタックのコピーを省略できる.本発表では,さらに,スタックコピーの遅延により可能となる,継続オブジェクトの部分的共有も提案する.これらの効率化手法をScheme処理系に組み込んで性能を評価したところ,継続を使ったプログラムの実行効率が改善された.In order to capture first-class continuations, most stack-based implementations copy contents of the stack to the heap. While various implementation strategies for copying are proposed, most implementations employ the stack strategy. With this strategy, the entire stack contents are copied to the heap whenever a continuation is captured. This simple strategy is easy to implement and can be used for implementations with foreign language interface. However, continuations with this strategy spend a lot of time and memory for their creations and invocations, and this week point often discourages programmers from using first-class continuations. We propose a lazy stack copying technique. The contents of the stack to copy will be preserved on the stack until returning from the function that is capturing the continuation. So we delay stack copying for a continuation until the function returns. We can avoid stack copying if it is detected that the continuation became a garbage before the function returs. In addition, we propose another technique, partial sharing of the copied stack, which is realized by using the lazy stack copying technique. We applied these techniques to Scheme interpreters and found that the proposed techniques improve runtime and memory efficiency of programs that use continuations.

著者

八杉 昌宏 馬谷 誠二 鎌田十三郎 田畑 悠介 伊藤 智一 小宮 常康 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.42, no.11, pp.1-13, 2001-11-15

被引用文献数

4

---

MIMD 型並列計算機における効率の良い並列処理のための,メソッドの実行時置換と構造化されたスレッドによる並列処理を特徴とするオブジェクト指向並列言語OPA を開発している.本論文では,その共有メモリ型並列計算機用のコード生成手法について述べる.コンパイル時には,オブジェクトへのメモリアクセスやコンテキストスイッチ時のメモリアクセスを削減するための解析を行う.また実装方式としては,プロセッサ間通信とスレッドスケジューリングにはlock-free バッファ管理方式,スレッド内スケジューリングには関数フレーム二重表現方式と値ベースサスペンドチェック方式,同期処理には重み付きカウント方式などを用いている.値ベースのチェックにより,1 呼び出しあたり1 分岐命令追加程度のオーバヘッドで高速なコンテキストスイッチを可能とした.We are developing an object-oriented parallel language OPA for effcient parallel processing on MIMD computers,which features dynamic method replacement and structured parallel processing using multiple threads.In this paper,the code generation techniques for shared-memory parallel computers are presented.The compiler performs analyses to reduce the memory access to objects and the memory access on context switches.The implementation techniques include a lock-free buffering method for inter-processor communication and thread scheduling,a double function-frame representation method and a value-based suspension check method for intra-thread scheduling,and an weighted counting method for synchronization.The value-based check enables fast context switches with small overhead for an additional branch instruction per call.

著者

太田 昌孝

雑誌

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

巻号頁・発行日

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

---

最初のJIS漢字コードであるJIS C 6226-1978では1つのコードに複数の字体が対応し,包摂と呼ばれるが,包摂の工学的に適切な扱いのためには,包摂を入力における量子化誤差ととらえ,出力における偏り(誤差)と区別する必要がある.文字コードと文字の入出力を電圧のAD/DA変換と対比した結果,現行のJIS漢字コードであるJIS X 0208:1997には,入力における偏り(誤差)を考慮していない,出力の許容誤差が不必要に厳しい,などの各種の問題があることが分かった.この結果を反映してJIS漢字コードを改定する必要があり,既存の実装の精度を定義できる.実装内容の改定は不要である.JIS C 6226-1978, the first JIS Kanji code, maps multiple glyphs to a single code, which is called unification, proper engineering treatment of which requires recognition of unification as quantization error on input and distiction of the quantization error from offset (error) on output. By comparing character input and output to/from character code with AD/DA conversion of voltage, it is found that the current JIS Kanji code JIS X 0208:1997 have various problems such as ignorance on input offset (error) and unnecessarily strict error allowance on output. It is necessary to revise JIS Kanji code to reflect the result of this paper, which enables to specify precision of existing implementations, content of which do not need any revision.

著者

深野 佑公 山本 繁弘 大野 和彦 中島 浩

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.2, pp.47-47, 2003-02-15

---

我々は並列言語Orgel の開発を行っている.Orgel は,並行/並列の実行単位であるエージェントをストリームと呼ぶ通信路で結び,明示的なメッセージ送信を行う言語である.Orgel では,プログラマが問題をエージェントという並列実行単位に切り分けることに加え,ストリームによる通信路接続網の構造をすべて宣言的に記述するので,コンパイル時に並列モデルが明確になっており精度の高い静的解析が可能である.本発表では,このOrgel の特徴を生かして,動的なオーバヘッドを最小限にした最適化を行う手法を提案する.プログラム全体の構造および粒度,通信量が完全に把握できれば,すべて静的に最適化することも可能である.しかし,Orgel では再帰的な接続も記述できるため,実際に生成されるエージェント個数および構造は必ずしも静的には決まらない.また,通信対象は分かっても送信するメッセージの個数やエージェントの粒度は実行時にしか分からない.したがって,各プロセッサの処理量が偏らないよう静的に全体をスケジューリングすることは困難である.そこで,コンパイラは静的にエージェントの持つ量的な性質を解析し,エージェント割当てやスケジューリングをするための情報をランタイムに渡す.ランタイムは,この情報をもとにノード数やプロセッサの現在の負荷などを考慮して,負荷が均等になり通信量が多いエージェントは同一プロセッサになるように割り当てる.また,同一プロセッサ内では依存解析等に基づいてスケジューリングを行う.本手法を実装し,14 クイーンを解くプログラムで従来のOrgel ランタイムと性能比較を行った.その結果,従来版と比べ最大1.7 倍の速度向上が得られた.We are developing a parallel language called Orgel.In the execution model of Orgel,a set of agents are connected with abstract communication channels called streams.The agents run in parallel sending asynchronous messages through the streams.In an Orgel program, each unit of parallel execution is speci ?ed as an agent by the programmer.The connections among agents and streams are declaratively speci ?ed.Thus,parallel execution model is clear and the highly accurate static analysis is possible.Utilizing these features,we propose an optimization scheme that minimizing the dynamic overhead.If the complete structure of the whole program is known at compile time,static optimization will be sufficiently effective. However,in Orgel,the number of agents and structures actually generated are not always static,because recursive connection is supported.Moreover,although a communicating pairs of agents are known at compile time,the number of messages and the granularity of agents are known only at runtime.Therefore,it is difficult to balance loads on the processor by whole static scheduling.Thus,in our scheme the compiler outputs an analysis result to instruct the runtime how to allocate and/or schedule an agent when its quantitative attributes are known. Considering the number of processors and the present load of each processor,the runtime uses this information for optimization;it allocates agents balancing loads and minimizing inter-node communication.It also schedules agents on each node considering dependencies. We designed and implemented the system.As the result of evaluation using 14-Queen solver, we obtained 170%speed-up.

著者

山本 繁弘 大野 和彦 中島 浩

出版者

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

雑誌

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

巻号頁・発行日

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

---

我々は並列言語Orgelの開発を行っている.Orgelは,並行/並列の実行単位であるエージェントをストリームと呼ぶ通信路で結び,明示的なメッセージ送信を行う言語である.Orgelでは,プログラマが問題をエージェントという並列実行単位に切り分けることに加え,ストリームによる通信路接続網の構造をすべて宣言的に記述するので,コンパイル時に並列モデルが明確になっており精度の高い静的解析が可能である.本発表では,このOrgelの特徴を生かして,動的なオーバヘッドを最小限にした最適化を行う手法を提案する.プログラム全体の構造および粒度,通信量が完全に把握できれば,すべて静的に最適化することも可能である.しかし,Orgelでは再帰的な接続も記述できるため,実際に生成されるエージェント個数および構造は必ずしも静的には決まらない.また,通信対象は分かっても送信するメッセージの個数やエージェントの粒度は実行時にしか分からない.したがって,各プロセッサの処理量が偏らないよう静的に全体をスケジューリングすることは困難である.そこで,量的な性質が分かった時点でエージェントを,割当てやスケジューリングできるように,コンパイラは静的解析による結果をランタイムに渡す.ランタイムは,この情報をもとにノード数やプロセッサの現在の負荷などを考慮して,負荷が均等になり通信量が多いエージェントは同一プロセッサになるように割り当てる.また,同一プロセッサ内では依存解析などに基づいてスケジューリングを行う.We are developing a parallel language called Orgel.In the execution model of Orgel,a set of agents are connected with abstract communication channels called streams.The agents run in parallel sending asynchronous messages through the streams.In an Orgel program, each unit of parallel execution is speci fied as an agent by the programmer.The connections among agents and streams are declaratively speci fied.Thus,parallel execution model is clear and the highly accurate static analysis is possible.Utilizing these features,we propose an optimization scheme that minimizing the dynamic overhead.If the complete structure of the whole program is known at compile time,static optimization will be sufficiently effective. However,in Orgel,the number of agents and structures actually generated are not always static,because recursive connection is supported.Moreover,although a communicating pairs of agents are known at compile time,the number of messages and the granularity of agents are known only at runtime.Therefore,it is difficult to balance loads on the processor by whole static scheduling.Thus,in our scheme the compiler outputs an analysis result to instruct the runtime how to allocate and/or schedule an agent when its quantitative attributes are known. Considering the number of processors and the present load of each processor,the runtime uses this information for optimization;it allocates agents balancing loads and minimizing inter-node communication.It also schedules agents on each node considering dependencies.

著者

中村 成洋 松本 行弘

雑誌

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

巻号頁・発行日

vol.2, no.2, pp.176-176, 2009-03-23

---

Apache HTTP サーバのもとで提供される Web サービスのような,ひんぱんにサブプロセスが生成される環境下では,現在 Ruby が採用しているマークビットをオブジェクトヘッダ内に持つマークスイープ方式のゴミ集め実装は,copy-on-write によるメモリページ共有を疎外し,必要以上にメモリを消費する.本研究では,マークをオブジェクトヘッダ内から独立したビットマップに移すことによるメモリ消費量実行性能の変化を示す.効率的なビットマップマーキングのためにはオブジェクトポインタからビットマップの特定の位置の計算が必要である.一般的にはビットマップ位置をたとえば 1M バイト単位でアラインしておきアドレスをマスクすることでビットマップ位置を求めることが行われている.しかし,Ruby のように種々のプラットフォームで動作する言語処理系では,利用できるメモリ割当て API はmalloc() しかないため,効率良くアラインされたメモリを確保する方法は知られていない.本研究では Ruby のオブジェクト配置方式を利用し,移植性を維持したまま,オブジェクトポインタから定数時間でビットマップ位置を計算する手法を提案する.また,二分検索を用いたビットマップマーキングと比較したマーキング性能の改善も示す.Since mark-and-sweep garbage collection scheme, which Ruby interpreter uses modifies every living object, it suffers performance problems due not to utilize copy-on-write memory page sharing among processes, under the circumstances like web-services running under Apache HTTP servers. In this paper, we proposes adding bitmap marking for Ruby's garbage collection. We show much memory usage and performance change by bitmap marking. For efficient bitmap marking, it is needed to calculate bitmap position from an object pointer. Prior art uses aligns heap memories and pointer masking to retrieve bitmap position from object pointer. But Ruby interpreter runs on various platforms, and we do not have portable memory allocation API to obtain aligned memory region without wasting region. In this paper, we propose portable scheme to map from object pointers to corresponding bitmap table in constant time. We also show how much proposed bitmap marking improves performance, comparing bitmap marking method using binary search to obtain bitmap position from object pointers.