Linearity analysis of concurrent logic programs

Kazunori Ueda*

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review


Automatic memory management and the hiding of the notion of pointers are the prominent features of symbolic processing languages. They make programming easy and guarantee the safety of memory references. For the memory management of linked data structures, copying garbage collection is most widely used because of its simplicity and desirable properties. However, if certain properties about runtime storage allocation and the behavior of pointers can be obtaind by static analysis, a compiler may be able to generate object code closer to that of procedural programs. In the fields of parallel, distributed and real-time computation, it is highly desirable to be able to identify data structures in a program that can be managed without using garbage collection. To this end, this paper proposes a framework of linearity analysis for a concurrent logic language Moded Flat GHC, and proves its basic property. The purpose of linearity analysis is to distinguish between fragments of data structures that may be referenced by two or more pointers and those that cannot be referenced by two or more pointers. Data structures with only one reader are amenable to compile-time garbage collection or local reuse. The proposed framework of linearity analysis is constraint-based and involves both equality and implicational constraints. It has been implemented as part of klint v2, a static analyzer for KL1 programs.

Original languageEnglish
Pages (from-to)188
Number of pages1
JournalElectronic Notes in Theoretical Computer Science
Issue number2
Publication statusPublished - 2000
EventWOID'99, Workshop on Optimization and Implementation of Declarative Programs (in Connetion with ICLP'99, International Conference on Logic) - Las Cruces, NM, United States
Duration: 1999 Dec 21999 Dec 3

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Linearity analysis of concurrent logic programs'. Together they form a unique fingerprint.

Cite this