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

Access this Article

Search this Article

Author(s)

Abstract

フランスの論理学者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.

Journal

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

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

    Information Processing Society of Japan (IPSJ)

References:  16

Cited by:  5

Codes

  • NII Article ID (NAID)
    110002725190
  • NII NACSIS-CAT ID (NCID)
    AA11464814
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    1882-7802
  • NDL Article ID
    5699372
  • NDL Call No.
    Z74-C192
  • Data Source
    CJP  CJPref  NDL  IPSJ 
Page Top