A technique for dynamic term size computation via program transformation

Knowing the size of the terms to which program variables are bound at run-time in logic programs is required in a class of applications related to program optimization such as, for example, granularity analysis and selection among different algorithms or control rules whose performance may be dependent on such size. Such size is difficult to even approximate at compile time and is thus generally computed at run-time by using (possibly predefined) predicates which traverse the terms involved. We propose a technique based on program transformation which has the potential of performing this computation much more efficiently. The technique is based on finding program procedures which are called before those in which knowledge regarding term sizes is needed and which traverse the terms whose size is to be determined, and transforming such procedures so that they compute term sizes "on the fly". We present a systematic way of determining whether a given program can be transformed in order to compute a given term size at a given program point without additional term traversal. Also, if several such transformations are possible our approach allows finding minimal transformations under certain criteria. We also discuss the advantages and applications of our technique and present some performance results.

Deriving a fixpoint computation algorithm for top-down abstract interpretation of logic programs

Bruynooghe described a framework for the top-down abstract interpretation of logic programs. In this framework, abstract interpretation is carried out by constructing an abstract and-or tree in a top-down fashion for a given query and program. Such an abstract interpreter requires fixpoint computation for programs which contain recursive predicates. This paper presents in detail a fixpoint algorithm that has been developed for this purpose and the motivation behind it. We start off by describing a simple-minded algorithm. After pointing out its shortcomings, we present a series of refinements to this algorithm, until we reach the final version. The aim is to give an intuitive grasp and provide justification for the relative complexity of the final algorithm. We also present an informal proof of correctness of the algorithm and some results obtained from an implementation.

Towards an abstract domain for resource analysis of logic programs using sized types

We present a novel general resource analysis for logic programs based on sized types.Sized types are representations that incorporate structural (shape) information and allow expressing both lower and upper bounds on the size of a set of terms and their subterms at any position and depth. They also allow relating the sizes of terms and subterms occurring at different argument positions in logic predicates. Using these sized types, the resource analysis can infer both lower and upper bounds on the resources used by all the procedures in a program as functions on input term (and subterm) sizes, overcoming limitations of existing analyses and enhancing their precision. Our new resource analysis has been developed within the abstract interpretation framework, as an extension of the sized types abstract domain, and has been integrated into the Ciao preprocessor, CiaoPP. The abstract domain operations are integrated with the setting up and solving of recurrence equations for both, inferring size and resource usage functions. We show that the analysis is an improvement over the previous resource analysis present in CiaoPP and compares well in power to state of the art systems.

Resource usage analysis of logic programs via abstract interpretation using sized types

We present a novel general resource analysis for logic programs based on sized types. Sized types are representations that incorporate structural (shape) information and allow expressing both lower and upper bounds on the size of a set of terms and their subterms at any position and depth. They also allow relating the sizes of terms and subterms occurring at different argument positions in logic predicates. Using these sized types, the resource analysis can infer both lower and upper bounds on the resources used by all the procedures in a program as functions on input term (and subterm) sizes, overcoming limitations of existing resource analyses and enhancing their precision. Our new resource analysis has been developed within the abstract interpretation framework, as an extension of the sized types abstract domain, and has been integrated into the Ciao preprocessor, CiaoPP. The abstract domain operations are integrated with the setting up and solving of recurrence equations for inferring both size and resource usage functions. We show that the analysis is an improvement over the previous resource analysis present in CiaoPP and compares well in power to state of the art systems.

Compendium logicæ secundum principia D. Renati Descarte catechisticè propositum : [1693]

Small leather hardcover volume containing a manuscript copy of William Brattle’s abstract of René Descartes’ "Compendium Logicae" copied in Latin, likely by Thomas Phipps in 1693. A crossed out inscription on the inside back cover appears to read “Thomas Phips 1693” likely referring to Thomas Phipps, a member of the Harvard Class of 1695.

Program manual : NOR network transduction based on connectable and disconnectable conditions (reference manual of NOR network transduction programs NETTRA-G1 and NETTRA-G2) /

"UIUCDCS-R-75-698"

TESLA : a control language for logic simulations of digital circuits /

"August 8, 1969."

Program manual for the programs ILLOD-MINSUM-CBS, ILLOD-MINSUM-CBSA, ILLOD-MINSUM-CBG, and ILLOD-MINSUM-CBGM, to derive minimal sums or irredundant disjunctive forms for switching functions /

"UILU-ENG 78 1719."

A manual of SIMPL, a logic network simulator for PLATO /

"UILU-ENG 79 1728."

Program manual for the NETTRA system /

"UILU-ENG 77 1743."

Program manual, NOR network transduction by generalized gate merging and substitution : (reference manual of NOR network transduction programs NETTRA-G3 and NETTRA-G4) /

Includes bibliographical references.

Design of Irredundant MOS Networks : a program manual for the design algorithm DIMN /

Thesis (M. S.)--University of Illinois at Urbana-Champaign.

Program manual : NOR network transduction based on error-compensation : (Reference manual of NOR network transduction programs NETTRA-EL, NETTRA-E2, and NETTRA-E3) /

"Work supported in part by the National Science Foundation under Grant no. GJ-40221."

Program manual of programs for minimal covering problems : ILLOD-MINIC-B, ILLOD-MINIC-BP, ILLOD-MINIC-BS, ILLOD-MINIC-BA, ILLOD-MINIC-BG /

Includes bibliography references.

Results of the synthesis of optimal networks of AND and OR gates for four-variable switching functions by a branch-and-bound computer program /

Bibliography: p. 39 (2d group)