Static Analysis of Linear Logic Programming
Jean-Marc Andreoli, Tiziana Castagnetti, Remo Pareschi
Linear Logic is gaining momentum in computer science because it offers a unified framework and a common
vocabulary for studying and analyzing different aspects of programming and computation. We focus here on
models where computation is identified with proof search in the sequent system of Linear Logic. A proof
normalization procedure, called "focusing", has been proposed to make the problem of proof search tractable.
Correspondingly, there is a normalization procedure mapping formulae of Linear Logic into a syntactic fragment
of that logic, called LinLog, where the focusing normalization for proofs can be most conveniently expressed.
In this paper, we propose to push this compilation/normalization process further, by applying abstract
interpretation and partial evaluation techniques to (focused) proofs in LinLog. These techniques provide
information concerning the evolution of the computational resources (formulae) during the execution (proof
construction). The practical outcome that we expect from this theoretical effort is the definition of a general tool
for statically analyzing and reasoning about the runtime behavior of programs in frameworks where computations
can be accounted for in terms of proof search in Linear Logic.
New Generation Computing (NGC), 15(4), 1997
dist.pdf.gz (185.84 kB)
dist.ps.gz (104.69 kB)