線形論理型言語のJava言語による処理系の設計と実装 Java Implementation of a Linear Logic Programming Language

この論文にアクセスする

この論文をさがす

著者

抄録

フランスの論理学者J -YAG.Girardによって線形論理(Linear Logic)が発表されて以来 プログラミング言語への応用が盛んに研究されている.線形論理に基づく論理型言語については すでにいくつかが提案されている:Lolli Lygon LO LinLog Forum HACL.しかし Java上の処理系が実現されたものはまだ存在していない.これらの言語では 動的に生成 消費される「リソース」を論理式のレベルで表現できる.そのため効率のよりリソース処理は実装上最も重要な問題の1つである.Lolli Lygon Forumについては インタプリタ処理系が開発されている.(LolliはSML及びλProlog上 LygonはProlog上 ForumはSML Prolog及びλProlog上).これらの処理系では リソースは木構造として表現されているため リソースを消費した場合に木構造の再構築が必要となり 効率低下の原因となっている.本稿では 線形論理型言語LLPの概要と LLPからJavaへのトランスレート方式について述べる.LLP言語はPrologのスーパーセットで Lolliのサブセットになっている.リソースはコンパイルコードと自由変数の束縛情報から構成されるクロージャ(closure)にコンパイルされ ただ1つのリソース表により管理される.リソースの呼び出しは通常のプログラム呼び出しに統合される.Nクイーン配置問題を解くLLOプログラムの実行速度は 標準的なPrologベンチマークに含まれるNクイーンプログラムをMINERVAでコンパイルしたものより N=12で約1.5倍速い.また Prologベンチマークの実行速度は 既存のトランスレータjPrologと比較して 平均で3倍強の高速化を実現している.There have been several proposals of logic programming languages based on linear logic; Lolli, Lygon, LO, LinLog, Forum, HACL. In these languages, it is possible to create and consume resources dynamically as logical formulas. The efficient handling of resource formulas is therefore an important issue in the implementation of these languages. Lolli, Lygon, and Forum are implemented as interpreter systems; Lolli is on SML and λProlog, Lygon is on Prolog, Forum is on SML, λProlog and Prolog. But, none of them have not been implemented in Java. In this paper, we describe a method for translating a linear logic programming language called LLP into Java. LLP is a superset of Prolog and a subset of Lolli. In our design, resource formulas are compiled into closures which consist of a reference to compiled code and a set of bindings for free variables. Calling resources are integrated with the ordinary predicate invocation. LLP program for N-Queen (N=12) is about 1.5 times faster than an N-Queen program in classical Prolog benchmarks which is compiled by MINERVA. On average, the execution speed of generated code for classical Prolog benchmarks is about 3 times faster than existing Prolog-to-Java translator called jProlog.

There have been several proposals of logic programming languages based on linear logic: Lolli, Lygon, LO, LinLog, Forum, HACL. In these languages, it is possible to create and consume resources dynamically as logical formulas. The efficient handing of resource formulas is therefore an important issue in the implementation of these languages. Lolli, Lygon and Forum are implemented as interpreter systems; Lolli is on SML and λProlog, Lygon is on Prolong, Forum is on SML, λProlong and Prolog. But, none of them have not been implemented in Java. In this paper, we describe a method for translating a linear logic programming language called LLP into Java. LLP is a superset of Prolong and a subset of Lolli. In our design, resource formulas are compiled into closures which consist of a reference to compiled code and a set of bindings for free variables. Calling resources are integrated with the ordinary predicate invocation. LLP program for N-Queen (N=12) is about 1.5 times faster than an N-Queen program in classical Prolog benchmarks which is compiled by MINERVA. On average, the execution speed of generated code for classical Prolog benchmarks is about 3 times faster than existing Prolog-to-Java translator called jProlog.

収録刊行物

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

    情報処理学会論文誌プログラミング(PRO) 40(SIG10(PRO5)), 1-16, 1999-12-15

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

参考文献:  16件中 1-16件 を表示

被引用文献:  5件中 1-5件 を表示

各種コード

  • NII論文ID(NAID)
    110002725190
  • NII書誌ID(NCID)
    AA11464814
  • 本文言語コード
    JPN
  • 資料種別
    Article
  • ISSN
    1882-7802
  • NDL 記事登録ID
    5699372
  • NDL 請求記号
    Z74-C192
  • データ提供元
    CJP書誌  CJP引用  NDL  NII-ELS  IPSJ 
ページトップへ