Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Binding-time analysis for Mercury
Vanhoof W., Bruynooghe M.  Logic programming (Proceedings of the 1999 International Conference on Logic Programming, Las Cruces, New Mexico, United States,500-514.1999.Type:Proceedings
Date Reviewed: Oct 14 2004

Partial evaluation (or program specialization) is a technique that transforms a program into another program, by pre-computing some of its operations. This kind of program transformation typically has been approached from two points of view. The first approach is offline partial evaluation. In offline partial evaluation, a process called binding-time analysis (BTA) is applied to the original program. This process determines, for every statement in the program, which input values will be known during specialization. The second approach is online partial evaluation. Using this approach, specialization is done without any previous analysis.

In this work, a BTA is developed for the logic programming language Mercury (http://www.cs.mu.oz.au/research/mercury/). This BTA is polyvariant (each of the original procedures may occur in several versions of the annotated program), and is based on the type information available in Mercury programs.

The proposed BTA works in two phases. In the first phase, binding times and the relations between them are represented in a symbolic way (without using a particular call pattern); this allows the BTA to perform a large part of the data-flow analysis independent of a particular call pattern. In the second phase, the annotations and the actual binding times are computed, by combining particular call patterns and the result of the first phase.

Thanks to the available mode information, the analysis is driven by a number of constraints between binding time variables. These constraints conveniently represent the dependencies between the values of the control variables associated to a goal and the goal’s input variables.

The approach is well formalized, and covers all the features of the language, including higher-order ones. One important question readers could think about is if this proposal would be applicable to a more established language, such as Prolog. In order to solve this question, the authors provide a complete example, to discuss to what extent the proposed analysis is also applicable in the context of Prolog, and how it could be applied.

Reviewer:  Josep Silva Review #: CR130278 (0506-0713)
Bookmark and Share
  Reviewer Selected
 
 
Logic Programming (I.2.3 ... )
 
 
Logic And Constraint Programming (F.4.1 ... )
 
 
Language Classifications (D.3.2 )
 
 
Programming Languages And Software (I.2.5 )
 
Would you recommend this review?
yes
no
Other reviews under "Logic Programming": Date
An efficient strategy for non-Horn deductive databases
Demolombe R. Theoretical Computer Science 78(1): 245-259, 1991. Type: Article
Jan 1 1992
Three-valued nonmonotonic formalisms and semantics of logic programs
Przymusinski T. Artificial Intelligence 49(1-3): 309-343, 1991. Type: Article
Dec 1 1992
A proof theory for general unification
Snyder W., Birkhäuser Boston Inc., Cambridge, MA, 1991. Type: Book (9780817635930)
Mar 1 1993
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy