著者

坪井 良介 各務 裕太 山口 大輔 倉光 君郎

雑誌

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

巻号頁・発行日

vol.11, no.2, pp.22, 2018-06-26

---

型推論は,構文パターンから型を推論する方法で,型アノテーションなしで静的型付けを実現する.ただし,構文パターンからの型推論はアルゴリズムが複雑になりがちですべての言語に採用しにくい問題がある.本発表は,よりお手軽に型推論を実現するため,名前からの型推論を提案する.まず,実際のソース・コードを解析し,型と名前の法則性を調べる.それに基づき,名前からの型を推論するシステムと言語設計を定義した.我々は,これらのアイディアを関数型スクリプト言語konoha 5λに実装し,その使いやすさを検証し報告する.

著者

松本 宗太郎 南出 靖彦

出版者

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

雑誌

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

巻号頁・発行日

vol.49, no.3, pp.39-54, 2008-03-15

参考文献数

9

---

本研究では,多相レコード型に基づいてRubyプログラムの型推論ツールを設計,実装した.型推論ツールは,組み込みライブラリの型を記述したシグネチャとRubyプログラムを入力とし,プログラムの型を推論し,誤りを検出する.しかし,Rubyの柔軟性を表現できる,実用的で健全な型体系を設計しようとすると,体系は非常に複雑になる.それを避けるため,多相レコード型によって拡張されたMLの型推論アルゴリズムを,直接,Rubyに適用した.型体系は,非常に制限されたRubyプログラムに対しては,健全になるように設計した.Rubyにおいては,組み込みクラスなどの既存のクラスを拡張することが許されており,実際に多くのプログラムで既存のクラスが拡張されている.このようなプログラムを処理するために,シグネチャとプログラムを分離して型推論するのではなく,プログラムの一部としてシグネチャが含まれるよう型体系を設計した.実際のRubyプログラムを型付けする場合には,多相レコード型の表現力やMLの型推論アルゴリズムにおける再帰的な定義の型推論に関する多相性の制限から,いくつかの問題が生じることが分かった.これらの制限は,特に組み込みライブラリの型付けにおいて問題になることから,クラス定義を複製し展開することによって型推論を行った.We design and implement a type inference tool for Ruby programs. The type system is based on polymorphic record types of Garrigue. The tool takes two inputs, a type signature of the built-in classes and a Ruby program, and then infers the type of the Ruby program and detect type errors. The type system is a direct adaptation of that of ML with polymorphic records, and designed to be sound only for a restricted tiny subset of Ruby. Ruby allows programmers to modify existing classes and many programs actually modify existing (built-in) classes. Thus we design our type system so that type signatures and method implementation coexist in a class definition. We encounter difficulties when typing common Ruby programs, since polymorphic methods are not expressible in our type system and the ML type inference does not infer polymorphic types in recursive definitions. We alleviate these difficulties by introducing transformations that duplicate class definitions.

著者

木山 真人

出版者

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

雑誌

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

巻号頁・発行日

vol.42, no.3, pp.40-48, 2001-03-15

被引用文献数

1

---

迅速なソフトウェア開発の要求が高まるにつれて,オブジェクト指向スクリプト言語は,より多くの場面で使用されている.これまでのスクリプト言語は,主に小規模なプログラムに使用されていたが,オブジェクト指向スクリプト言語はその保守性の高さから大規模なプログラムにも使用されている.一般に,オブジェクト指向言語ではプログラマの負担を軽くするため,メモリ管理を処理系側で行う実装となっている.そのため,処理系はメモリを有効に利用するために,不要になったメモリを回収し再利用可能にするためのごみ集め処理(GC)が必要になる.多くのオブジェクト指向スクリプト言語はGCを有しているが,実装の容易さから,マークスイープ法,リファレンスカウント法が用いられている.しかし,これらの方法ではプログラムの規模が大きくなるにつれて,GC処理時間の全実行時間に占める割合が大きくなる.そこで,プログラムの実行時間を短縮するため, GCの高速化に着目し,世代別GCの導入を検討する.本論文では,オブジェクト指向スクリプト言語Rubyに世代別GCを実装する場合の方法および結果を示す.世代別GCにすることで,従来のGCにくらべGC処理時間が最大92%,プログラムの実行時間が最大50エ%短縮することが分かった.Object-oriented scripting languages are becoming more and more important as a tool for software development, as it provides great flexibility for rapid application development.Scripting languages have been used for developing small-scale programs, object-oriented scripting languages are also used for developing large-scale programs. n general, memory management is implemented in object-oriented language in order to reduce programmers burden. Garbage Collection is necessary to collect and reuse the unnecessary memory to utilize the memory effectively. Mark-sweep and reference counting are general use among most object-oriented scripting languages. But these method, the ratio of whole execution time to GC execution time will increase as program size increase. In order to reduce program execution time, we introduce generational garbage collection in Ruby. In this paper, we show the method of implementation of generational garbage collection in Ruby, and how efficient that. It can reduce 50エ% of total execution time and 92エ of the cost of garbage collecting for our benchmark.

著者

上里 友弥

雑誌

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

巻号頁・発行日

vol.5, no.2, pp.1-15, 2012-03-30

---

本論文では,必ず停止するパーザのみを構成できるようなパーザコンビネータライブラリ(total parser combinator library)の実装手法について述べる.構成されるパーザが必ず停止することの保証は,定理証明支援系のCoqによって行う.Coqは,停止する関数だけを許すプログラミング言語としても使うことができるので,Coq上で定義することができればよい.パーザおよびパーザコンビネータはmonadicに実装したい.しかし一般に,monadicな実装においては証明の段階で逐一定義を展開していかなければならず,無駄が多いという問題がある.一方,この問題に対しては,Swierstraの提案したHoare state monadが有効である.そこで,我々はパーザをmonadicに実装する手段として,Hoare state monadを一般化したHoare state monad transformerを新たに提案する.このHoare state monad transformerを用いたことで,従来のmonadicな実装をもとにしながらも,停止性を比較的容易に証明することができた.

著者

山本 晃成 湯淺 太一

出版者

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

雑誌

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

巻号頁・発行日

vol.42, no.11, pp.37-51, 2001-11-15

---

プログラミング言語の中には末尾再帰の最適化と一級継続を必須としているものがある.たとえばScheme ,Standard ML や他の関数型言語のほとんどがその機能を必要としている.これらの言語は,末尾再帰の効率によるところが大きく,また,継続が操作可能であることが言語の重要な特色でもある.しかし,Java 仮想マシン(JVM )上で末尾再帰の最適化と一級継続を実現することは困難である.これはJVM の仕様がそれらを実現するための機構を十分に提供していないことが要因である.実際に,JVM のバイトコードを出力する様々なコンパイラが実装されているにもかかわらず,JVM の制限のために,言語が要求する完全な機能を実現できていないものが少なからず存在する.そこで,JVM で末尾再帰の最適化と一級継続を実現するために,いくつかのバイトコード命令とその実行を補うためのクラスを拡張することを検討する.様々な拡張方法や実現方法が考えられるが,JVM の基本設計は可能な限り尊重し,最低限の拡張でかつ効果的にこれらの機能を実現可能にすることを目標とする.There are several programming languages that require tail recursion optimization and first-class continuations.Scheme,Standard ML,and several other mostly functional languages require these features.These languages rely heavily on the efficiency of tail recursion,and the ability of controlling continuationsisone of the important features.However, it is difficult to implement tail recursion optimization and first-class continuations on the Java Virtual Machine (JVM),because the JVM specification does not provide features to realize them. Although variouscompilersare implemented that produce JVM byte code,some of them cannot realize full language features because of the restriction of the JVM specification.In this research, we propose byte code extensions and classes to support their execution to realize tail recursion optimization and first-class continuations on the JVM.Although there are various ways to extend it and implement them,we aim at having respect for the basic design of the JVM as far as possible and realizing them efficiently with minimum extensions.

著者

神戸 隆行

出版者

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

雑誌

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

巻号頁・発行日

vol.46, no.1, pp.78-96, 2005-01-15

参考文献数

17

---

現在,数多くの様々な最適化技術が研究されているが,そのすべての最適化技術,特に問題依存度の高い最適化を組み込むことは処理系の肥大化を招く.そこでこのような問題依存度の高い最適化は問題の解法とともに処理系ではなくプログラム部品としてライブラリ化することが考えられる.その手段の1 つとしてメタ・プログラミングがある.そしてこのように最適化をライブラリに組み込むにあたっては実行環境の違いをどう反映するかという問題がある.これについては最適化に適当なパラメータを導入し,実行環境で試行・計測してパラメータを求める実行時プロファイリングという方法がある.本発表ではFFT を例にとり,メモリ階層を意識した最適化をC++テンプレートの機能を用いたメタ・プログラミングで行うとともに,実行時プロファイリングに基づいて適応的な最適化を行ったので報告する.これは3 つの段階からなる.1) 核となる小さなサイズのデータに対するFFTコードをサイズごとに複数生成(ループの展開,三角関数値の静的計算).2) 前段で生成したサイズごとの核コードの実行時間計測.3) 計測結果に基づく核コードの選択・合成による最終的なFFT コードの生成.特にこのうち1) と3) でC++テンプレート・メタ・プログラミング技法を利用した.以上の実装と評価について報告を行う.Although much various optimization technologies are studied now, including all these optimization technologies, especially highly problem dependent optimizations bloats code size of compiler too much. One approach is the following: the optimizations build into a part of component library the solution instead of build into compiler itsself, which is able to realize with meta-programming technique. But including the optimizations in a library in this way, there is a problem how to reflect the difference in execution environment. This problem is dealt with introducing parameters for optimization, profiling trial execution in an execution environment, and looking for a suitable parameter value. In this presentation, FFT is taken for the example, and we describe memory hierarchy conscious optimization for FFT, which is implemented in meta-programming technique, and adaptive optimization based on execution time profiling. Our method consists of three steps. Step1: They are some FFT code generation (ex. unrolling of a loop, static evaluation of a trigonometric-functions value) for each small constant size data used as a kernel. Step2: Execution time measurement of the kernel for every size generated in the preceding step. Step3: Generation of the final FFT code by selection and composition of the kernel based on the measurement results. C++ template meta-programming technique was used in Step 1 and Step3. The above method and its evaluation are reported.

著者

前田 敦司 曽和 将容

出版者

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

雑誌

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

巻号頁・発行日

vol.41, no.4, pp.1-10, 2000-06-15

参考文献数

20

---

末尾再帰的な関数呼び出しをジャンプに変換する処理は,コンパイラの最適化として広く行なわれている.特に,Lispの一方言であるScheme言語においては末尾再帰呼び出しを空間計算量ο()で実行することが言語仕様で要求されている.このように,空間計算量ο()で実行することができる末尾再帰呼び出しを真の末尾再帰呼び出し(roper tail recursio)と呼ぶ.動的スコープを持つ変数が存在する場合,通常の実装では,スコープを規定する構文の実行が終るまで変数束縛を保持しておく必要があるため,構文の末尾で再帰的な関数呼び出しがあってもそれを真の末尾再帰呼び出しとすることができない.しかしながら,リスト構造を用いて変数束縛を保持する,いわゆる深い束縛を用いるLispインタプリタについては,事実上定数空間計算量で末尾再帰呼び出しを処理することができる手法が知られている.本論文では,動的スコープ変数の実装として現一般的な,浅い束縛を用いた場合について,真の末尾再帰呼び出しを実現するための手法について述べる.Conversion of tail recursive function call into simple jump is a technique widely used as optimization in compilers. Especially, Scheme, a dialect of Lisp, requires as part of language specification that tail recursion be performed in ο(1) space complexity. Tail recursion implemented in ο(1) space complexity is called "proper tail recursion". With existance of dynamically-scoped variables, ordinary implementation keeps variable bindings until binding construct exits. Thus, syntactic tail call cannot be implemented in a properly tail recursive fashion. For Lisp interpreters which keeps variable bindings in list structures (i.e. deep binding), there is a known way to achieve almost-proper tail recursion with dynamic scoping. In this paper, we argue about an implementation method of proper tail recursion with shallow binding, which is a common way of implementing dynamically-scoped variables in current Lisp implementations.

著者

松本 宗太郎 南出 靖彦

雑誌

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

巻号頁・発行日

vol.49, no.SIG3(PRO36), pp.39-54, 2008-03-15

---

本研究では,多相レコード型に基づいてRubyプログラムの型推論ツールを設計,実装した.型推論ツールは,組み込みライブラリの型を記述したシグネチャとRubyプログラムを入力とし,プログラムの型を推論し,誤りを検出する.しかし,Rubyの柔軟性を表現できる,実用的で健全な型体系を設計しようとすると,体系は非常に複雑になる.それを避けるため,多相レコード型によって拡張されたMLの型推論アルゴリズムを,直接,Rubyに適用した.型体系は,非常に制限されたRubyプログラムに対しては,健全になるように設計した.Rubyにおいては,組み込みクラスなどの既存のクラスを拡張することが許されており,実際に多くのプログラムで既存のクラスが拡張されている.このようなプログラムを処理するために,シグネチャとプログラムを分離して型推論するのではなく,プログラムの一部としてシグネチャが含まれるよう型体系を設計した.実際のRubyプログラムを型付けする場合には,多相レコード型の表現力やMLの型推論アルゴリズムにおける再帰的な定義の型推論に関する多相性の制限から,いくつかの問題が生じることが分かった.これらの制限は,特に組み込みライブラリの型付けにおいて問題になることから,クラス定義を複製し展開することによって型推論を行った.

著者

諏訪 将大 八杉 昌宏 平石 拓 馬谷 誠二

雑誌

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

巻号頁・発行日

vol.9, no.1, pp.15-15, 2016-02-26

---

我々は分散進捗管理のためのシステムとしてメッセージ媒介システム(MMS)を開発している.本発表ではMMS中の不必要なメッセージの削除方法について述べる.MMSは並列アプリケーションや並列言語処理系の開発に有用であり,MMSを介して与えられた計算の部分的計算結果をメッセージとして多数のワーカが交換できる.一部ワーカが障害により停止してもよいような並列分散手法により,MMSは与えられた計算の進捗を管理する.開発の初期段階においては,アプリケーション独自の樹状再帰的計算の一部を表すための可変長アドレスを各ワーカが使ってよいものとしてMMSを設計した.このアプローチで計算速度の向上と耐障害性が達成されたが,書き込まれたメッセージが単調に増え,メモリ使用状況へ大きな影響があった.本研究では不必要なメッセージを削除できるようMMSの設計と実装を変更し,その効果を評価する.

著者

中川 博貴 笹田 耕一

雑誌

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

巻号頁・発行日

vol.4, no.4, pp.44-44, 2011-09-22

---

本発表では Ruby 処理系の正規表現などの文字列処理を手軽に高速化する手法について述べる.高速化を目指すにあたり,文字列処理のアルゴリズムに手を加えず,互換性を損なわない範囲で行うことができる 2 つの手軽な手法を適用した.1 つ目に,正規表現エンジン鬼車用の AOT コンパイラを実装した.Ruby の正規表現処理を行う正規表現エンジン鬼車は,仮想マシン型の評価器を持ち,実行時に正規表現をオペコードに変換して評価する.我々は正規表現処理の高速化を目指し,このオペコード列をC言語の関数に変換し,仮想マシンの代わりに動作させる AOT コンパイラを開発した.2 つ目に,主要な文字コードについて,文字コードに関する処理を文字列処理へインライン化した.鬼車は多言語文字列に対応した正規表現エンジンである.多言語文字列に対応するために,文字のバイト数を調べるといった各文字コード固有の処理を関数ポインタによって呼び分けている.また,この仕組みを利用して,Ruby 処理系の文字列も多言語化が行われている.しかし,各文字コード固有の処理を関数ポインタ経由で呼び出すため,関数呼び出しにコストがかかり,また C コンパイラによる関数をまたいだ最適化が効きにくくなるという問題があった.そこで,我々は主要な文字コードについて,文字コードに関する処理を文字列操作にインライン化することで高速化を実現した.本発表では,鬼車用 AOT コンパイラの仕組みと文字コードに関する処理のインライン化の手法について述べる.そして評価を行い,これらの高速化の結果について述べる.In this presentation, we describe the lightweight methods to speed up string processing for Ruby. To speed up, we adapt two lightweight methods which do not change string processing algorithms and do not break compatibility. First, we implemented the AOT compiler for regular expression engine Oniguruma which is used for regular expression processing in Ruby. Oniguruma is implemented as a virtual machine. The regular expression parser of Oniguruma compiles the regular expressions into a sequence of opecodes, and then the virtual machine executes it. We implemented the AOT compiler which compiles an opecode sequence into a C function, and then executes the C function instead of the execution of virtual machine. Second, we inlined processes of major character encodings into string functions. Oniguruma supports multilingual strings. To support multilingual strings, Oniguruma calls each character encoding functions, for example a function to calculate a byte length of a character, via a function pointer. Similarly, Ruby string is multilingualized in the same way as Oniguruma. However this approach increases the cost of function calls, and prevents a C compiler interprocedural optimization. For speed up, we inlined processes of major character encodings into string functions. In this presentation, we describe the design and the implementation of the AOT compiler for Oniguruma and the method to inline processes of character encodings. Moreover, we show the results of performance evaluation for these implementations.

著者

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

雑誌

情報処理学会論文誌プログラミング(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構文マクロシステムを実現できた.

著者

前田 敦司 山口 喜教

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.13, pp.47-57, 2003-10-15

参考文献数

15

被引用文献数

1

---

スタックアーキテクチャの仮想マシン命令を解釈実行するSchemeインタプリタの効率的な実装法について述べる.単純な命令セット定義から出発し,ベンチマークプログラムにおける命令列の実行頻度に応じて命令セットを最適化することで解釈実行のオーバへッドを最小化する体系的な手法を示す.本手法を用いて構成したインタプリタの性能評価を行い,インタプリタの移植性,対話性,デバッグの容易さを損なうことなく,ネイティブコードの20?40%程度の,比較的高い性能が得られていることを示す.An effcient implementation methodology for Scheme interpreters that interpretes stackoriented virtual machine instructions is presented. Starting from simple instruction set definition, we show how our systematic optimization techniques reduces the interpretation overhead based on dynamic frequency of instruction sequence. Evaluation shows that our interpreter can achieve 20 to 40 percent of the performance of native code, without losing portability, interactivity, and ease of debugging.

著者

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

出版者

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

雑誌

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

巻号頁・発行日

vol.42, no.11, pp.25-36, 2001-11-15

参考文献数

12

---

「ぶぶ」は,Java 言語とのシームレスなインタフェースを備えたオブジェクト指向型のScheme 処理系である.Java の機能を最大限に利用しつつScheme を使って対話的にプログラミングができることを目標としており,Scheme の継続機能,Java の例外処理機能の両方に対応していることが望まれる.ぶぶではScheme とJava で記述したメソッドを相互に呼び出し合うことができる.Scheme部分の実行には専用に確保した制御スタックを使っているが,Java 部分の実行にはJava VM の制御スタックを使っている.したがって,完全なファーストクラスの継続を実現するためには,Java の継続も得なければならない.しかし,Java 言語はこのような手段を提供していない.そこで,継続オブジェクトを生成するときは実行中のScheme 部分だけの継続をヒープに保存しておき,Java 部分の継続はJava VM の制御スタック上に残しておくことにした.継続を呼び出すときにJava 部分の継続が制御スタック上に残っているかどうかを調べ,残っていれば完全な継続呼び出しとして動作する.残っていないときはScheme 部分だけの部分継続として呼び出す.また,Java の例外処理機能をScheme で記述したプログラムでも直接利用できるようにした.この例外処理機能は継続機能と同時に使うことができる."Bubu" is an object-oriented Scheme system with seamless interface to Java. Because the goal of Bubu is to provide an interactive environment of Scheme and draw out maximum functionality of Java, we expect it to support both first-class continuations of Scheme and the exception system of Java. In Bubu, methods written in Java and Scheme can call each other. The control stack for methods in Scheme is implemented by using an array object of Java. On the other hand, methods in Java uses the control stack of Java VM. Therefore, when a first-class continuation is captured, a continuation of Java must be also saved to heap. However, Java does not support this facility. In our proposal, when a continuation is captured, only a continuation of Scheme part is saved to heap and the continuation of Java part is left on the control stack of Java VM. When the continuation is called, whether the continuation of Java part is left on the stack of Java VM or not is checked, and if left, this call works as a traditional continuation call. If not, this works as a partial continuation call which has only the Scheme part. In addition, we developed a seamless interface to the Java exception system which can cooperate with the continuation facility.

著者

笹田 耕一 松本 行弘 前田 敦司 並木 美太郎

雑誌

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

巻号頁・発行日

vol.48, no.SIG10(PRO33), pp.1-16, 2007-06-15

---

本論文ではスクリプト言語Ruby 用仮想マシンYARV: Yet Another RubyVM における並列実行スレッド処理機構の実装について述べる.Ruby はその使いやすさから世界中で広く利用されているプログラム言語である.Ruby の特徴の1 つにマルチスレッドプログラミングに対応しているという点があるが,現在広く利用されているRuby 処理系は移植性を高めるため,すべてユーザレベルでスレッド制御を行っている.しかし,このスレッド実現手法では,実行がブロックしてしまう処理がC 言語レベルで記述できない,並列計算機において複数スレッドの並列実行による性能向上ができないなどの問題がある.そこで,現在筆者らが開発中のRuby 処理系YARV において,OS やライブラリなどによって提供されるネイティブスレッドを利用するスレッド処理機構を実装し,複数スレッドの並列実行を実現した.並列化にあたっては,適切な同期の追加が必要であるが,特に並列実行を考慮しないC 言語で記述したRuby 用拡張ライブラリを安全に実行するための仕組みが必要であった.また,同期の回数を減らす工夫についても検討した.本論文では,これらの仕組みと実装についての詳細を述べ,スレッドの並列実行によって得られた性能向上について評価した結果を述べる.

著者

塚田 武志 小林 直樹

雑誌

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

巻号頁・発行日

vol.4, no.2, pp.31-47, 2011-03-25

---

言語の包含判定問題とは,与えられた言語 L1 と L2 について L1 ⊆ L2 が成立するか否かを判定する問題であり,理論的な興味の対象であるだけでなく,プログラム検証などへの広い応用を持つ重要な問題である.この問題に関する既知の最も強い結果の 1 つが文脈自由言語と超決定性言語の包含判定の決定可能性である.このオリジナルの証明は,Greibach と Friedman によって与えられている.我々はこの問題に対して,小林らによって提案されている型に基づく言語の包含判定の手法を適用し,決定可能性に対する別証明を与えた.この手法は以下のような利点を持つ.(1) 部分型関係やポンプの補題などのよく知られた概念で理論が展開できる.(2) 型推論を効率的に行う方法は多数提案されており,それらを利用することができる.また,提案する証明は小林らのアイデアを正規言語よりも広いクラスに適用したはじめての例であり,その他の非正規言語クラスへの応用も期待される.

著者

上里 友弥

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.5, no.2, pp.1-15, 2012-03-30

---

本論文では,必ず停止するパーザのみを構成できるようなパーザコンビネータライブラリ(total parser combinator library)の実装手法について述べる.構成されるパーザが必ず停止することの保証は,定理証明支援系のCoqによって行う.Coqは,停止する関数だけを許すプログラミング言語としても使うことができるので,Coq上で定義することができればよい.パーザおよびパーザコンビネータはmonadicに実装したい.しかし一般に,monadicな実装においては証明の段階で逐一定義を展開していかなければならず,無駄が多いという問題がある.一方,この問題に対しては,Swierstraの提案したHoare state monadが有効である.そこで,我々はパーザをmonadicに実装する手段として,Hoare state monadを一般化したHoare state monad transformerを新たに提案する.このHoare state monad transformerを用いたことで,従来のmonadicな実装をもとにしながらも,停止性を比較的容易に証明することができた.We have implemented a total parser combinator library that can constitute only a parser that terminates for all inputs. The termination is guaranteed by using the Coq proof assistant as a programming language that allows only terminating functions. If a parser is implemented with the library on the Coq, then termination of it is really guaranteed. It is desirable to implement parsers and parser combinators in the monadic style. However, when a program is implemented in the monadic style, it is usually necessary to unfold the definition of monads in the process of proving, and the unfolding makes the proofs rather cumbersome. To overcome this problem, we generalize Hoare state monads of Swierstra to Hoare state monad transformers. By using Hoare state monad transformers, we maintain the monadic style implementation, and also it is relatively easy to prove the termination of constructed parsers.

著者

三宅 立記 今城 哲二 佐藤 忍 井藤 敏之 横塚 大典 辻畑 好秀 植村 俊亮

出版者

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

雑誌

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

巻号頁・発行日

vol.41, no.2, pp.89-101, 2000-03-15

---

既存の企業情報システムを安価に再構築するインフラとして Web を利用するイントラネットの導入が急速に進行している.しかし,企業情報システムのイントラネット化には,システム開発の面で次のような問題がある.()システム開発を行うための技術としてHTML,Java等をシステム開発者が新たに習得する必要がある.()COBOL,PL/I等の正確な精度を保証する10進演算機構が利用できないため,金額処理を伴ったシステム開発が困難.()従来のクライアントサーバシステムや端末に比べてレスポンスが悪い.COBOLスクリプトは,これらの問題を解決するために日立製作所と日立ソフトウェアエンジニアリングが共同開発したスクリプト言語であり,次のような特長を有する.()企業内の情報システム部門で最もよく利用されているCOBOL85をベースにWebに必要な機能に絞り込んだ言語仕様.()メインフレーム系のCOBOLと同一精度の10進演算機能をサポート.()既存のCOBOL処理系の長所,短所の分析に基づいた効率のよい実装.これにより次の成果を得た.()金額計算など誤差の許されない分野の業務を Web上で心配なく稼動可能とした.()テストデバッガやカバレージのサポートにより大規模な開発プロジェクトでの利用を可能にした.()プログラムの保守性を向上する日本語プログラミング機能をサポートした.()優れた実行性能を実現できた.The introduction of intranet which allows to access Web technology is rapidly growing as the infrastructure to restructure existing business information systems within a reasonable cost. However, in terms of system development, use of intranet on the business systems poses the following problems. (1)The system developers must learn new technology such as HTML and Java as the technology for system development. (2)As the decimal arithmetic functions, which guarantee the precision such as in COBOL and PL/I, are not available, it is difficult to develop systems that involves accounting processing. (3)The response time might exceed those of the existing Client and Server systems or terminals. COBOL Script, which is a script language developed jointly by Hitachi Ltd. and Hitachi Software Engineering Co., Ltd. to solve these problems, has the following features. (1)The language specification, which consists of required functions for Web computing, is a subset of COBOL85, which is the most frequently used programming language in business information analysis of the pros and the cons of the COBOL processing system. We obtain the following results; (1)Applications requiring high precision such as accounting processing can be operated on Web. (2)The test debugger and the coverage functions make it possible to use in a large development project. (3)The Japanese programming facility provides good maintainability. (4)Good performance is achieved.

著者

牧 大介 岩崎 英哉

出版者

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

雑誌

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

巻号頁・発行日

vol.48, no.12, pp.1-18, 2007-08-15

参考文献数

15

---

Ajax は Web 開発の世界で普及したが、一方で Ajax 開発が従来の Web 開発に比べて非常に困難であることがよく知られている。その理由として、Ajax 開発においては複雑な非同期処理を 1 つのスレッドの上にすべて記述しなければならない点、JavaScript では非同期通信をイベント駆動型でしか記述できないため、制御フローの記述が困難である点があげられる。上の問題を解決するため、本論文では JavaScript のマルチスレッドライブラリを提案する。提供するライブラリの特徴としては、(1) 代表的な複数の Web ブラウザで可搬性があること、(2) プリエンプティブなスレッド切替えが可能であること、(3) オブジェクト指向で API を提供すること、がある。提案機構では、マルチスレッド・スタイルで記述された JavaScript プログラムを継続ベースの並行処理を応用して既存の処理系で実行可能な JavaScript プログラムへと変換し、この変換済みプログラムを実行時ライブラリであるスレッド・スケジューラの上で並行実行する。そして実際に Ajax アプリケーションを記述することで、提案機構の有効性を確かめた。提案機構にはオーバヘッドがあるが、Ajax アプリケーションにおける通信遅延に比べると十分に小さいため、実用上は大きな問題にはならないと考えられる。Although Ajax is widely used in the development of Web applications, it is well known that Ajax development is much more difficult than traditional Web development. There are two reasons: (1) Ajax developers have to write complex asynchronous program on a single thread; (2) asynchronous communication on JavaScript can be programmed only in event driven style, which causes control-flow difficulty. To resolve this problem, we provide multithread library to JavaScript programmers. The proposed library has the following features: (1) it is portable among popular Web browsers; (2) it provides preemptive scheduling; (3) it provides object-oriented API. The proposed system converts JavaScript programs written in multithreaded-style into those in continuation-based style that are executable on existing systems, and then executes them concurrently on a runtime-library called thread-scheduler. To see the effectiveness of the library, we implemented an Ajax application using the library. The overhead of the converted programs is not a serious problem in practice because the overhead is smaller enough than communication delay of Ajax applications.

著者

今城哲司 鈴木 弘 大野 治 植村 俊亮

出版者

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

雑誌

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

巻号頁・発行日

vol.41, no.4, pp.90-90, 2000-06-15

---

約20年前からコンピュータでの漢字利用が普及し,標準プログラム言語で日本語データ処理が可能となった.日本語処理は,国際規格化されていて,いくつかの言語では,識別名にも漢字などマルチオクラット文字が使用できる.予約語まで日本語にした本格的な日本語プログラム言語も,分かち書きのレベルで,実用化されている.本論文では,分かち書きをしない,より日本語に近い日本語プログラム言語"まほろば"の設計思想と文法について述べ,実装実験による評価について報告する.Twenty years ago, programming languages have acquired an ability to handle Japanese. Generalizing it to internationalization (i18n), many of i18n facilities of each programing language were accepted as ISO standards. Some programming languages allow users to use user-defined words in such multi-octet characters as kanji. Some new Japanesebased programming languages have also been developed and used. In all those languages, keywords and grammar are based on Japanese, but words have to be separated by spaces. This paper discusses a non-separated (No wakachigaki) version ofJapanese-based programming langage"Mahoroba"."Mahoroba" is a word of ancient Japan, and means a nice country. The paper describes its design philosophy, syntax and evaluation by experimental implementation.

著者

稲津 和磨 岩崎 英哉

雑誌

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

巻号頁・発行日

vol.3, no.4, pp.1-15, 2010-09-22

---

近年Google Mapsなどに代表される,Ajaxと呼ばれる手法を用いたWebアプリケーションが増加している.Ajaxを用いたWebアプリケーションはサーバ側とクライアント側で動作する2つのプログラムにより構成され,それらが協調して動作する.そのため,煩雑な通信処理を記述する必要があり,さらには,それぞれの実装言語が多くの場合は異なっているため,プログラミングが非常に煩雑になる.そこで本論文では,開発効率の向上を目的として,JavaScriptに基づくプログラム言語でWebアプリケーションを1つのプログラムとして記述し,処理の柔軟な分割を可能とするフレームワークを提案する.また,そのプログラム言語で記述されたプログラムを読み込み,サーバ側で動作するソースコードとクライアント側で動作するソースコードを出力するような機構を設計し,実装した.提案機構は,与えられたプログラムを解析し各構文要素がサーバとクライアントのどちらで実行するべきかを決定する.その際,分割方針を指定することで,同じソースコードから異なる分割を得ることができる.同じ動作をするWebアプリケーションを,提案機構と既存の手法のそれぞれを用いて記述し,プログラムを比較して記述性が向上していることを確認した.また,提案機構によるオーバヘッドは,Webアプリケーションで行われる一般的な処理については問題ない程度の小さなものであることを確認した.