著者

安本 太一 湯淺 太一

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.39, no.9, pp.2659-2670, 1998-09-15

参考文献数

18

---

複数の名前空間を持つLispのためのモジュール機能を提案する.提案するモジュール機能の特徴は,モジュールによって最上位環境(top?level environment)とともに記号空間を分割し,モジュール間で(記号ではなく)束縛の可視性制御を行うことにある.既存のLisp言語を自然でかつ容易な方法で拡張してモジュール機能を追加できるうえ,Lispにおけるプログラム開発効率の高さも損なわない.さらに,マクロの束縛捕捉問題を,単純ではあるが効果的に解決できる.A module system is proposed for Lisp dialects with multiple name-spaces.A module in this module system is characterized by its own top-level environment and its own symbol space.By partitioning a single symbol-space,as well as a single top-level environment,into modules,the module system allows to extend existing Lisp languages in a natural and easy way,while preserving the efficiency of program development in Lisp.It also provides simple but effective solutions to the binding-capturing problems of macros.

著者

東田 学 下條 真司 湯淺 太一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. CNR, クラウドネットワークロボット (ISSN:09135685)

巻号頁・発行日

vol.111, no.178, pp.71-76, 2011-08-17

---

XSは、LEGO Mindstorms用の対話型プログラミング環境として開発された非常に小さなLisp処理系であり、LEGOブロックで組み上げたロボットにブロック型のモーターやセンサーを組み込んで高度に制御することができる。今回、ZigBee短距離無線通信センサブロック用のドライバを開発し、LEGOロボット間の協調的制御を可能にした。さらに、ZigBeeインターネットゲートウェイを開発しており、自律的に動作するLEGOロボット群をクラウドから介入的に制御する方法を模索している。

著者

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

雑誌

情報処理学会論文誌プログラミング(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.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.

著者

湯淺 太一

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.45, no.12, pp.1279-1283, 2004-12-15

---

ACM/ICPCの日本国内予選が去る7月2日に開催された。世界大会やアジア地区予選と異なり、日本国内予選はインターネットを使って行われる。インターネットを使って問題をダウンロードし、解答プログラムを送付し、判定結果を受け取る。この点を除けば、世界大会やアジア地区予選と基本的に同じルールで競技を行う。今年度は44校199チームが参加し、うち26チームが国内予選を通過し、12月に愛媛大学で開催されるアジア地区予選への出場権を獲得した。

著者

竹辺 靖昭 湯淺 太一

出版者

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

雑誌

情報処理学会論文誌プログラミング(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.

著者

近山 隆 湯淺 太一 上田 和紀 田浦 健次朗 遠藤 敏夫 横山 大作 田浦 健次朗 遠藤 敏夫 横山 大作 馬谷 誠二

出版者

東京大学

雑誌

特定領域研究

巻号頁・発行日

2006

---

爆発的に増加する大量の情報を効率的に扱うソフトウェアの構成には、広域に分散配置した高度な並列性を持つ情報システムを柔軟に記述できるソフトウェアの枠組が基本技術として必要となる。このためのプログラミング言語やミドルウェアのシステムと、複雑なソフトウェアの正当性を検証するためのシステムを対象に研究を進め、具体的なシステムを提案、設計、実装し、その性能を検証した。代表的成果ソフトウェアは公開している。

著者

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

出版者

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

雑誌

情報処理学会論文誌プログラミング(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.

著者

小宮 常康 湯淺 太一

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.35, no.11, pp.2382-2391, 1994-11-15

被引用文献数

2

---

継続とはある時点以降の残りの計算を表したものである。Lispの一方言であるSchemeでは、継続を生成する関数が用意されており、継続をデータとして扱うことができる。これによって、非局所的脱出やコルーチンなどの様々な制御構造を実現することができる。一方、Scheme言語を並列化するためによく使用されるfuture構文は、プロセスの生成とそれらの間の同期を取るメカニズムを提供する。しかし、future構文に墓づく従来の並列Schemeの継続機能では、並列プログラムを記述するのに不十分であった。そこで本論文では、future構文に基づく並列環境に適合するように、Schemeの継続機能を拡張することを提案する。

著者

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

出版者

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

雑誌

情報処理学会論文誌プログラミング(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.