著者

甫水 佳奈子 脇田 建 佐々木 晃

雑誌

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

巻号頁・発行日

vol.6, no.2, pp.85-101, 2013-08-29

---

本稿は,JavaScriptの構文拡張を可能にするHygienic構文マクロシステムの実装技法を提案する.Hygienic構文マクロシステムは,マクロ展開の前後で変数の束縛や参照関係を破壊しない安全な構文マクロシステムである.このHygienic構文マクロシステムを利用することによって,プログラミング言語の構文の自由な拡張が可能になる.しかし,Hygienic構文マクロシステムは,S式という一貫した構文構造を持つSchemeには標準で組み込まれているものの,その他の一般的なプログラミング言語に実装された例はほとんどない.本稿では,まず,汎用的なプログラミング言語におけるHygienic構文マクロシステムの実装の難しさを示し,次に,本研究が提案するJavaScript向けHygienic構文マクロシステムの実装技法について述べる.提案する実装技法では,マクロ構文の追加によって拡張されるJavaScript構文を解析するための拡張可能なパーザの実現に解析表現文法を用い,マクロ展開は既存のSchemeマクロ展開器に委ねる.マクロ展開においては,マクロを含むJavaScriptコードをそれと等価なS式へと変換し,Schemeマクロ展開器で展開を行った後に,JavaScriptコードに逆変換するという言語間相互変換を行う.これらの工夫によりわずか2,000行弱のコンパクトな実装によってJavaScriptに対する記述力が高いHygienic構文マクロシステムを実現できた.

著者

佐藤 一道 脇田 建

出版者

FIT(電子情報通信学会・情報処理学会)運営委員会

雑誌

情報科学技術フォーラム一般講演論文集

巻号頁・発行日

vol.6, no.4, pp.457-460, 2007-08-22

著者

増田 萌 脇田 建

出版者

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

雑誌

情報処理学会研究報告ヒューマンコンピュータインタラクション(HCI) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.41, pp.27-34, 2007-05-11

---

本研究は彩色を施された文書が生ずる色覚障害の問題に取り組む。本手法は、筆者が意図した色彩効果を目的関数として定式化し、それを最大化することにより、文書の筆者が意図した色彩効果が色覚障害者にとって最も認知し易い文書になるように再配色を与える。一般に非線形多変量となる目的関数は、マルコフ連鎖モンテカルロ法のレプリカ交換法を用いて最適化した。また、計算時間を高速化するために、探索空間の近似を行った。本手法の評価のために、文書に意図的に色覚障害者が文字を読み取れない彩色を施したものを本手法を用いて再配色し、十分な可読性が得られることを確認した。Color-blindness is caused because color effects intended by the author are sometimes difficult for the color-blind to observe. SmartColor takes author's expectation about color effects found in the document in terms of mathematical formula (energy function). Minimization of the energy function gives the best repainting for the color-blind. Replica exchange method (a variant of MCMC) for minimization nonlinear multivariate target functions energy function. SmartColor incorporates some approximation technique to reduce computational cost. Effectiveness of the system is tested by using specially arranged diagrams and color-blind simulation.

著者

大島 芳樹 脇田 建 佐々 政孝

出版者

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

雑誌

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

巻号頁・発行日

vol.41, no.9, pp.62-77, 2000-11-15

参考文献数

16

---

高機能なSmalltalk処理系であるSqueakを携帯情報端末Zaurusに移植し,Zaurusの持つ独自のハードウェアにあわせて拡張を施したので,システムの実現方法,性能,可用性の評価について報告する.我々の行った実装作業は大きく2つに分類される.まず,基本的な機能の性能を向上させるために,Zaurus上でのイベント処理方式やビットマップ変換方式の性能について定量的評価を行い,それに基づいて最適化を行った.さらに,Zaurus独自の拡張を施すことによって,ペン入力,音声機能,デジタルカメラ,TCP/IPネットワーク,シリアル・IrDAポート,電力消費制御,およびフラッシュメモリファイルシステムのようなPDA独自のハードウェアをSqueakから操作可能とした.この移植および拡張はZaurus依存の部分を記述した4000行程度のC記述および600行ほどのSqueak記述によって達成された.我々は大小各種のベンチマークによる性能評価およびいくつかのアプリケーションによる可用性評価を行った.Zaurusシリーズの最上位機種であるMI-EX1上のSqueakは,400MHz G3 Macに対して最高1/8程度の性能を示した.このベンチマークの数字および実際の使用テストから,このシステムは十分実用に耐える性能を持つことが分かった.我々の実装によって,さまざまな周辺機器を操作できる実用的なプログラミング環境を手のひらサイズの機器上で運用できることが示された.This paper reports our effort to implement Squeak Smalltalk on a family of personal digital assistant ({エit PDAエ/}) devices called Zaurus. The Squeak on Zaurus ({エit Squeak/Zaurusエ/}) offers programmable interfaces to various Zaurus specific devices. The system is evaluated in terms of its usability and performance. Two important issues in implementation of Squeak/Zaurus are as follows. Firstly, we measured performance of several implementation strategies for event-handling and bitmap conversion, which are dominant performance issues, and adopted the best ones in Squeak/Zaurus. Secondly, we have extended Squeak to support PDA specific hardware such as pen input, audio, digital camera, TCP/IP network, serial and IrDA communication, power consumption control, and file I/O on flash memory. These PDA specific devices are made directly accessible to the programmer. Those Zaurus specific functions are written in 4,000 lines of C code and 600 lines of Squeak code. The performance of Squeak/Zaurus has been evaluated by various micro- and macro-benchmarks and its usability has been tested by applications. MI-EX1, the highest model of Zaurus family, marked 1/8 of the performance of Squeak running on 400エ,MHz G3 Mac at best. This result and the usability tests indicate that it performs sufficiently well for practical use. The Squeak/Zaurus implementation demonstrates feasibility of practical programming environment on palm size devices that can operate PDA specific hardware.

著者

高野 陸 脇田 建

雑誌

研究報告ヒューマンコンピュータインタラクション(HCI) (ISSN:21888760)

巻号頁・発行日

vol.2018-HCI-180, no.8, pp.1-8, 2018-11-27

---

複雑ネットワークの構造を理解するための手段として,グラフクラスタリングが挙げられる.グラフクラスタリングはネットワークの構造を要約する手法として有用であるが,必ずしも意味的に正しいクラスタ構造を構成できないという問題があり,しばしば人間の判断を必要とする.このような人間と機械の健全な協力関係の必要性を満たす手法として,しばしば対話的な可視化が用いられる.しかしグラフクラスタリングの対話的な可視化に関する既存研究では,人間と機械が協力して意味的に正しいクラスタ構造を探索するシステムは存在しない.本研究では対話的なネットワーク可視化分析ツールである Social Viewpoint Finder を拡張し,人間と機械が協力的にクラスタ構造を探索的に分析するシステムを提案した.システムの中では機械的なグラフクラスタリングへ人間が介入するために,クラスタ構造をパラメトリックに表現したクラスタ雲を新しく提案し,それを用いた対話的なクラスタ分析の UI を提供した.他にも,人間のクラスタ構造への理解を深めるための包括的なクラスタ分析を支援する機能も提案した.また,本研究で提案した対話機能が探索的なクラスタ分析において有用であるかを,二つの実データセットを用いた分析例によって議論した.

著者

中野 雄基 美添 一樹 脇田 建

雑誌

ゲームプログラミングワークショップ2013論文集

巻号頁・発行日

pp.81-88, 2013-11-01

著者

鶴見 敏行 脇田 建

出版者

FIT(電子情報通信学会・情報処理学会)運営委員会

雑誌

情報科学技術フォーラム一般講演論文集

巻号頁・発行日

vol.6, no.2, pp.97-100, 2007-08-22

---

Clauset, Newman, Mooreはネットワークをボトムアップかつ貪欲に解析する手法(CNMアルゴリズム)を提案し、50万ノード程度までの社会ネットワーク解析を可能としたが、それ以上の規模については実用的な時間内での解析は困難であった。そこでCNMアルゴリズムの合併の過程を観察した。その結果合併するクラスタサイズの不均衡が計算コストに大きく影響していることが明らかとなった。この観測から、合併するクラスタサイズの均衡がアルゴリズムの速度向上につながると考えた。本稿では、合併時のクラスタのサイズを考慮することにより合併比率を向上させる3種類の手法を提案する。提案手法の実験データセットとして、国内最大級のソーシャルネットワーキングサービスより2006年10月に取得した550万ユーザーの友人関係のネットワークを使用した。提案した3つの手法を用いたところ、CNMアルゴリズムに比べ劇的なスケーラビリティの向上がみられた。もっとも速度向上がみられた手法では、100万ノードに対して5分、400万ノードに対しては35分程度で解析する事に成功した。また別の手法では、50万ノードに対して50分(CNMアルゴリズムより7倍早い)で解析でき、モジュール性の向上にも成功した。

著者

大島 芳樹 脇田 建 佐々 政孝

雑誌

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

巻号頁・発行日

vol.41, no.SIG09(PRO8), pp.62-77, 2000-11-15

---

高機能なSmalltalk処理系であるSqueakを携帯情報端末Zaurusに移植し,Zaurusの持つ独自のハードウェアにあわせて拡張を施したので,システムの実現方法,性能,可用性の評価について報告する.我々の行った実装作業は大きく2つに分類される.まず,基本的な機能の性能を向上させるために,Zaurus上でのイベント処理方式やビットマップ変換方式の性能について定量的評価を行い,それに基づいて最適化を行った.さらに,Zaurus独自の拡張を施すことによって,ペン入力,音声機能,デジタルカメラ,TCP/IPネットワーク,シリアル・IrDAポート,電力消費制御,およびフラッシュメモリファイルシステムのようなPDA独自のハードウェアをSqueakから操作可能とした.この移植および拡張はZaurus依存の部分を記述した4000行程度のC記述および600行ほどのSqueak記述によって達成された.我々は大小各種のベンチマークによる性能評価およびいくつかのアプリケーションによる可用性評価を行った.Zaurusシリーズの最上位機種であるMI-EX1上のSqueakは,400MHz G3 Macに対して最高1/8程度の性能を示した.このベンチマークの数字および実際の使用テストから,このシステムは十分実用に耐える性能を持つことが分かった.我々の実装によって,さまざまな周辺機器を操作できる実用的なプログラミング環境を手のひらサイズの機器上で運用できることが示された.

著者

太田 行紀 田淵 聡 脇田 建 佐々 政孝

雑誌

全国大会講演論文集

巻号頁・発行日

vol.46, pp.81-82, 1993-03-01

---

プログラム開発環境においてはデバッガの存在が欠かせない。しかし,それを始めから作成するためには多大な時間と労力を要する。本稿は,インタプリタの内部情報を利用することにより,インタプリタ型のデバッガ作成に要する労力を劇的に減少することができることを報告する。われわれは言語処理系を記述する統一的な枠組として属性文法を使ってきた。これまでに,さまざまなクラスの属性文法を用いることでコンパイラの構文解析,意味解析,最適化,コード生成の各フェイスが記述できることを確認したほか,インタプリタやグラフィカルユーザインタフェイスの生成にも利用できることが分かった。このインタプリタに対して,文を実行する前にフックをかけ,コルーチン的に協調動作するデバッガフロントエンドを呼び出すように変更することで,文字端末用のデバッガが実現できた。今回作成したPL/0言語のデバッガの記述に要するコードは従来のデバッガに比べ行数比でわずかに1/65にすぎない。さらに,すでにわれわれが開発した属性文法に基づくグラフィカルユーザインタフェイス(GUI)生成系を利用し,デバッガのGUIも作成した。これにより,xdbxとほぼ同等の機能を持ったものが実現できた。

著者

佐々 政孝 山下 義行 徳田 雄洋 脇田 建

出版者

東京工業大学

雑誌

試験研究(B)

巻号頁・発行日

1994

---

本研究は、属性文法に基づくコンパイラ生成系をフリーソフトウェアとして公開するものである。1.Rieは,1パス型属性文法に基づく生成系である.これは,GNU Bisonをベースに,C言語で実装してある.Rieについては,平成5年度に1.0.3版と1.0.4版,平成6年度に1.0.5版を公開したが,平成7年度は寄せられたコメントやバグ情報へ対応などを行い,GNU規約に基づいたフリーソフトウェアとして1.0.6版を公開した.これらは,fjのニュースグループおよび世界的なネットワークであるusenetのニュースグループcomp.compilersでアナウンスし,具体的にはfip.is.titech.ac.jp:/pub/Rieよりanonymous ftpで入手できるようにした.これに対し,海外からはGNU規約をゆるめられないか等の問合せがあったり,国内ではfjのニュースグループで取り上げられたりしている。また,Rieを用いたコンパイラ記述に関する解説を図書に掲載した.2.Junは,木の上の属性文法に基づく,コンパイラのバックエンド用の生成系である.これはCommon Lispで実装してある.Junは,属性の依存関係にサイクルがある場合も扱えることが特徴で,これにより最適化器の定式化が可能になった.Junについては,初期版に対し,入力記述の仕様を改訂し,継承属性と合成属性とを対称的に扱うよう生成される属性評価器の形を変更し,全面的な書き直しを行った.これをfj.lang.misc,fj.sources.dなどでアナウンスし,具体的にはftp.is.titech.ac.jp:/pub/Junよりanonymous ftpで入手できるようにした.3.RieとJun双方を用いた実用規模言語に対するコンパイラ作成を行った.具体的には言語Cのサブセットについて,フロントエンドをRieにより,最適化器,レジスタ割付け,コード生成器をJunにより記述することで,コンパイラ作成を行った.

著者

脇田 建 佐々木 晃

出版者

東京工業大学

雑誌

基盤研究(C)

巻号頁・発行日

2011

---

マクロシステムはさまざまなプログラミング言語で使用されているが,多くの問題の原因となることも指摘されている.この点を改善するHygienic構文マクロシステムはLISPについて研究されてきたが,一般のプログラミング言語への応用は限定的であるため,われわれはこの系統的な実装方式にうちて研究し,その技術を応用してJavaScriput,およびScalaのためのHygienic構文マクロシステムを完成させた.研究成果として拡張可能な構文解析器の実装,および,汎用マクロ展開器の実装という二つの主要な困難を解決した.研究成果としてWebで実装を公開している.

著者

内山 雄司 脇田 建

出版者

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

雑誌

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

著者

太田 行紀 脇田 建 佐々 政孝

出版者

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

雑誌

情報処理学会研究報告ソフトウェア工学(SE) (ISSN:09196072)

巻号頁・発行日

vol.1995, no.25, pp.185-192, 1995-03-09

---

コンパイラをテストする際、コンパイラのすべての機能をもれなくテストするようなソースプログラムを人手によって作成することは非常な労力を要する。このテストは,構文的にも意味的にも正しいプログラムが正しく処理されることを調べる正常系試験と、その一方または両方が誤っているプログラムに対して適切なエラーメッセージが出力されることを調べる異常系試験の2つに分けられる。本論文では、そのそれぞれに対して、属性文法によるコンパイラの形式的定義より自動的にソースプログラムを生成する方法を試みた.その際,属性文法の文脈条件を意図的に真または偽にすることによって,意味的に正しいまたは誤ったプログラムを生成できたことがオリジナルな点である.In testing a compiler, it is very hard to manually generate test programs that cover all functions of the compiler. The test consist of the normality test and the abnormality test. The former checks whether the compiler works for syntactically and semantically correct programs. The latter checks whether the compiler detects errors and gives proper error messages for programs including syntax or semantic errors. In this paper, we try to automatically generate test programs for each of the above cases from formal definition by attribute grammars. The originality of this research resides in that we can generate semantically correct/incorrect programs by making context condition true/false intentionally.

著者

内山 雄司 緒方 大介 脇田 建

出版者

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

雑誌

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