著者

梅村 晃広

出版者

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

雑誌

情報処理学会研究報告. [プログラミング-言語基礎実践-]

巻号頁・発行日

vol.93, no.97, pp.1-8, 1993-10-29

---

本稿では,代数仕様についてのモナド解釈という新しい意味論を定義し,これに基づく仕様書換え方法を示す.Moggiは,値から値への関数と値から計算への関数との関係がモナドによって与えられることを示した.本稿では,これを代数仕様に応用し,通常解釈の拡張としてのモナド解釈を定義する.そして,この意味論に基づいた,仕様書き換えのためのモディファイアの定義方法を提案する.本稿の方法はエラー処理の追加に限らず,さまざまな書換えに対応し得るものである.

著者

鈴木 大介

出版者

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

雑誌

情報処理学会研究報告. [プログラミング-言語基礎実践-]

巻号頁・発行日

vol.93, no.97, pp.37-46, 1993-10-29

---

ポリモルフィズム(多相)はプログラミングの柔軟性と再利用性を向上させるのに必要な道具の一つである.Stracheyは多相をparametricなものとad-hocなものに区分した.これらはプログラム言語において広く用いられているが,実際には両方の多相を備えた言語はほとんど存在しないので,プログラムの再生産性には制限が生じる.我々はparametric多相とad-hoc多相を備えたオブジェクト指向言語のための新しい枠組であるF^<&le;>-Fにsubtyping, bounded qantification, coercion, mergeの機能を追加したもの-を提案する.そして,この計算系が,簡約による合流性,型保存性,強正規性などの性質を満たすことを示す.最後に,この計算系の実際のオブジェクト指向言語へのいくつかの応用例を与える.

著者

今井 克暢 森田 憲一

出版者

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

雑誌

情報処理学会研究報告. [プログラミング-言語基礎実践-]

巻号頁・発行日

vol.94, no.21, pp.121-128, 1994-03-09

---

一斉射撃問題を可逆(すなわち,逆向きにも決定的な)セル・オートマトン(RCA)で実現できるか考察した.まず従来の単一の射撃状態からなる一斉射撃解は構成できないことを証明した.そこで,RCAにおける一斉射撃解を複数の射撃状態を許したものとして定義し,この条件の下でMinskyの3n時間解を540状態のRCAに埋め込めることを示した.その際,分割セル・オートマン(PCA)を用いた.これはCAのサブクラスとみなすことができ,RCAの設計を容易にする.さらに3n時間解に基づく99状態の解を可逆PCAによって構成した.

著者

小川 瑞史

出版者

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

雑誌

情報処理学会研究報告. [プログラミング-言語基礎実践-]

巻号頁・発行日

vol.93, no.46, pp.75-85, 1993-05-28

---

近年Robertson-Seymourにより証明されたグラフマイナー定理(Wagnberの予想)により有限グラフ上のminor-closedな性質の検出は多項式時間アルゴリズムが存在することが知られている.しかし,その証明は非構成的であり一般に実際のアルゴリズムを構成するのは難しかった.本稿ではグラフマイナー定理の簡単な場合であるHigmanの補題の構成的証明を用い,未解決問題であった時間概念を含むデータベース上の選言的単項質問処理の線形時間アルゴリズムを自動生成により与えた.

著者

前田 宗則 小中 裕喜 石川 裕 友清 孝志 堀 敦史

出版者

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

雑誌

情報処理学会研究報告. [プログラミング-言語基礎実践-]

巻号頁・発行日

vol.93, no.73, pp.113-120, 1993-08-19

---

参照カウント方式ゴミ集めは,アプリケーションが生成する参照に循環構造が存在しないことを前提とする既に広く知られたゴミ集め技法である.これまでに,循環参照を取り扱えるよう拡張された循環参照カウント方式が提案されているが,アルゴリズム上その方式の適用可能な計算モデルがコンビネータマシンに限定される問題がある.本稿では,オブジェクト指向言語を含めて,参照の循環を任意の時点で引き起こすようなポインタ操作を許す言語に対する循環参照カウント方式ゴミ集めを提案する.さらに本方式は,ゴミ集めの並列処理と重み付き参照による参照複製に関して考察し,並列/分散環境のための基礎を与える.

著者

茅野 剛史 多田 好克

出版者

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

雑誌

情報処理学会研究報告. [プログラミング-言語基礎実践-]

巻号頁・発行日

vol.94, no.65, pp.145-152, 1994-07-21

---

協調言語であるLindaは,現在UNIXワークステーション上で実現されたものが多い.また,現行のLindaシステムではデータ通信の手段であるタプル空間がひとつのワークステーション上にしかないものが多く,そのためにさまざまな問題が発生している.本研究では,タプル空間がひとつしかないことによって起こる問題を解決するために,タプル空間が複数の計算機上に分散して存在するLindaシステムを提案する.また,効率をあげるためにアプリケーションのデータの扱いによって,分散のさせ方を変更するアプリケーション指向のアルゴリズムを考案する.今回の実現では,既存のシステムを改良し,Lindaのセマンティクスを用いて分散システムを記述した.