古典線形論理型プログラミング言語の静的解析の一手法について  [in Japanese] A Static Analysis Method for a Classical Linear Logic Programming Language  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

本稿では古典線形論理に基づいた論理型プログラミング言語の静的解析方法を提案する.線形論理に基づく論理型プログラミング言語としてはLolli, LinLog, LO, Lygon, Forumなどが提案されている.特に, Forumは古典線形論理に対し完全である論理型プログラミング言語である.しかし, Forumのプログラムの証明探索は非決定性が非常に大きいため, 静的解析することでプログラムの実行前に証明不可能なシーケントを取り除くことは重要である.Andreoliらは古典線形論理に基づく論理型プログラミング言語LOの静的解析方法を提案している.しかし, その方法は「リソースを意識した」線形論理型プログラミング言語で最も有用な演算子である乗法的論理積の解析には適用できないのである.そこで, 我々は乗法的論理和, 含意に加えて乗法的論理積を解析できる静的解析方法を考案した.我々の方法ではまず, プログラムと証明すべきゴールが与えられたら, そのシーケントのあり得る全ての証明を1つのAND-ORグラフに表現する.そして, データフロー解析のための前方伝搬と後方伝搬を繰り返すことによって証明不可能な節点をグラフから取り除いていく.本稿の静的解析方法に基づくプロトタイプ解析機を開発し, 実際にForumで書かれたソーティングプログラムを解析した結果, 6要素のソーティングに対し, 解析していない時の実行速度に比べ1000倍以上速くなった.

We propose a new static analysis method applicable to a classical linear logic programming language. Andreoli et al. proposed a static analysis method for a classical linear logic programming language LO, but their method cannot handle multiplicative connectives, which can be seen as the most important connective for a resource-sensitive feature of linear logic. Our method, in contrast, covers multiplicative conjunctions in addition to multiplicative disjunctions and linear implications. Abstract proof graph, which is an AND-OR graph representing all possible sequent proofs, is constructed from a given program and goal sequent. The graph can be repeatedly refined by propagating information to remove unprovable nodes from the graph. We applied the result of our prototype analyzer to a sorting program written in Forum. The sorting program was improved more than 1000 times faster for sorting 6 elements.

Journal

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

    情報処理学会論文誌. プログラミング 41(SIG_4(PRO_7)), 42-55, 2000-06-15

    Information Processing Society of Japan (IPSJ)

References:  15

Cited by:  2

Codes

  • NII Article ID (NAID)
    110002725388
  • NII NACSIS-CAT ID (NCID)
    AA11464814
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    03875806
  • NDL Article ID
    5731818
  • NDL Call No.
    Z74-C192
  • Data Source
    CJP  CJPref  NDL  NII-ELS  IPSJ 
Page Top