BACK TO INDEX

 Publications of year 1996
 Conference articles
1. M. Ducassé and J. Noyé. Tracing Prolog without a tracer. In N. Fuchs and U. Geske, editors, Proceedings of the poster session at JICSLP'96, pages 223-232, September 1996. GMD- Forschungszentrum Informationstechnik GMBH, GMD-STUDIEN Nr.296, ISBN3-88457-296-2. Note: One page abstract also appears in Proc. of the JICSLP'96, MIT Press, ISBN 0-262-63173-3.
Abstract:
 Tracing by automatic program source instrumentation has major advantages over compiled code instrumentation: it is cheaper to develop and more portable, it benefits from most compiler optimizations, it produces traces in terms of the original program, and it can be tailored to specific debugging needs. The usual argument in favor of compiled code instrumentation is its supposed efficiency. Tolmach and Appel 1 designed and implemented a tracer for Standard ML based on automatic program source instrumentation. The resulting code runs only 3 times slower than optimized code. They conjectured that a low-level tracer would run at about the same speed. However they had no reasonable low-level tracer at hand to actually compare their results with. We have performed such a comparison in the context of Prolog, using the ECRC ECLiPSe environment. The built-in low-level tracer of ECLiPSe is, at present, one of the most interesting tracers for Prolog. We have compared it with an instrumentation based on O'Keefe's "advice" utility 2 , made compatible with the ECLiPSe tracer. We traced "standard" Prolog benchmark programs 3 with both tracing techniques and measured the resulting CPU times. On average the performances of both implementations are equivalent: tracing Prolog programs by program instrumentation is no slower than using a low-level tracer. To our knowledge, this is the first time that a quantitative comparison of both approaches is made. Another contribution is that our source instrumentation is more complete than O'Keefe's advice package. In particular, it deals with built-in predicates, and allows predicates to be skipped/unskipped. ---------------------------------------- 1 A. Tolmach and A.W. Appel. A debugger for Standard ML. Journal of Functional Programming, 5(2):155-200, April 1995. 2 The "advice" utility is part of the DEC10 Prolog library, available by anonymous ftp from the AIAI of the University of Edinburg (aiai.edinburgh.ac.uk). 3 P. Van Roy and A. M. Despain. High-performance logic programming with the Aquarius Prolog compiler. Computer, 25(1):54-68, January 1992.

@InProceedings{dn96,
author = {M. Ducassé and J. Noyé},
title = {Tracing {Prolog} without a tracer},
booktitle = {Proceedings of the poster session at JICSLP'96},
year = {1996},
editor = {N. Fuchs and U. Geske},
pages = {223-232},
publisher = {GMD- Forschungszentrum Informationstechnik GMBH, GMD-STUDIEN Nr.296, ISBN3-88457-296-2},
month = {September},
note = {One page abstract also appears in Proc. of the JICSLP'96, MIT Press, ISBN 0-262-63173-3},
abstract = {Tracing by automatic program source instrumentation has major advantages over compiled code instrumentation: it is cheaper to develop and more portable, it benefits from most compiler optimizations, it produces traces in terms of the original program, and it can be tailored to specific debugging needs. The usual argument in favor of compiled code instrumentation is its supposed efficiency. Tolmach and Appel 1 designed and implemented a tracer for Standard ML based on automatic program source instrumentation. The resulting code runs only 3 times slower than optimized code. They conjectured that a low-level tracer would run at about the same speed. However they had no reasonable low-level tracer at hand to actually compare their results with. We have performed such a comparison in the context of Prolog, using the ECRC ECLiPSe environment. The built-in low-level tracer of ECLiPSe is, at present, one of the most interesting tracers for Prolog. We have compared it with an instrumentation based on O'Keefe's "advice" utility 2 , made compatible with the ECLiPSe tracer. We traced "standard" Prolog benchmark programs 3 with both tracing techniques and measured the resulting CPU times. On average the performances of both implementations are equivalent: tracing Prolog programs by program instrumentation is no slower than using a low-level tracer. To our knowledge, this is the first time that a quantitative comparison of both approaches is made. Another contribution is that our source instrumentation is more complete than O'Keefe's advice package. In particular, it deals with built-in predicates, and allows predicates to be skipped/unskipped.

----------------------------------------

1 A. Tolmach and A.W. Appel. A debugger for Standard ML. Journal of Functional Programming, 5(2):155-200, April 1995.

2 The "advice" utility is part of the DEC10 Prolog library, available by anonymous ftp from the AIAI of the University of Edinburg (aiai.edinburgh.ac.uk).

3 P. Van Roy and A. M. Despain. High-performance logic programming with the Aquarius Prolog compiler. Computer, 25(1):54-68, January 1992. }
}


2. P. Louvet and O. Ridoux. Parametric Polymorphism for Typed Prolog and $\lambda$Prolog. In 8th Int. Symp. Programming Languages Implementation and Logic Programming, volume 1140 of LNCS, Aachen, Germany, pages 47-61, 1996. [WWW] Keyword(s): Logic programming, typing, polymorphism, second-order lambda-calculus..
Abstract:
 Typed Prolog and LambdaProlog are logic programming languages with a strict typing discipline which is based on simple types with variables. These variables are interpreted as denoting generic polymorphism. Experiments show that this discipline does not handle properly common logic programming practices used in Prolog. For instance, the usual transformation for computing the Clark completion of a Prolog program does not work well with some typed programs. We observe that the head-condition is at the heart of these problems, and conclude that it should be enforced. We propose a second-order scheme which is compatible with usual practices. In this scheme, type variables denote parametric polymorphism. It allows quantifying types and terms, passing type and term parameters to goals and terms, and to express type guards for selecting goals. We give its syntax and deduction rules, and propose a solution to keep the concrete notation of programs close to the usual one.

@InProceedings{louvet:parametric:plilp:96,
author = {P. Louvet and O. Ridoux},
title = {Parametric Polymorphism for {Typed Prolog} and $\lambda${Prolog}},
booktitle = {8th Int. Symp. Programming Languages Implementation and Logic Programming},
series = {LNCS},
volume = 1140,
pages = {47--61},
year = 1996,
address = {Aachen, Germany},
abstract = {Typed Prolog and LambdaProlog are logic programming languages with a strict typing discipline which is based on simple types with variables. These variables are interpreted as denoting generic polymorphism. Experiments show that this discipline does not handle properly common logic programming practices used in Prolog. For instance, the usual transformation for computing the Clark completion of a Prolog program does not work well with some typed programs. We observe that the head-condition is at the heart of these problems, and conclude that it should be enforced. We propose a second-order scheme which is compatible with usual practices. In this scheme, type variables denote parametric polymorphism. It allows quantifying types and terms, passing type and term parameters to goals and terms, and to express type guards for selecting goals. We give its syntax and deduction rules, and propose a solution to keep the concrete notation of programs close to the usual one.},
keywords = {Logic programming, typing, polymorphism, second-order lambda-calculus.},
url = {ftp://ftp.irisa.fr/local/lande/plor-plilp96.ps.gz}
}


3. O. Ridoux. Engineering Transformations of Attributed Grammars in $\lambda$Prolog. In M. Maher, editor, Joint Int. Conf. and Symp. Logic Programming, pages 244-258, 1996. MIT Press. [WWW] Keyword(s): Syntax-directed translation, grammar transformations, logic grammars, DCG, LambdaProlog..
Abstract:
 An abstract representation for grammar rules that permits an easy implementation of several attributed grammar transformations is presented. It clearly separates the actions that contribute to evaluating attribute values from the circulation of these values, and it makes it easy to combine the representations of several rules in order to build the representation of new rules. This abstract form applies well to such transforms as elimination of left-recursion, elimination of empty derivation, unfolding and factorization. Finally, the technique is applied to DCGs and a LambdaProlog implementation of the abstract form and of the transforms is described.

@InProceedings{ridoux:engineering:jicslp:96,
author = {O. Ridoux},
title = {Engineering Transformations of Attributed Grammars in $\lambda${Prolog}},
year = 1996,
editor = {M. Maher},
pages = {244--258},
booktitle = {Joint Int. Conf. and Symp. Logic Programming},
publisher = {MIT Press},
abstract = {An abstract representation for grammar rules that permits an easy implementation of several attributed grammar transformations is presented. It clearly separates the actions that contribute to evaluating attribute values from the circulation of these values, and it makes it easy to combine the representations of several rules in order to build the representation of new rules. This abstract form applies well to such transforms as elimination of left-recursion, elimination of empty derivation, unfolding and factorization. Finally, the technique is applied to DCGs and a LambdaProlog implementation of the abstract form and of the transforms is described.},
keywords = {Syntax-directed translation, grammar transformations, logic grammars, DCG, LambdaProlog.},
url = {ftp://ftp.irisa.fr/local/lande/or-jicslp96.ps.gz}
}


4. S. Schoenig and M. Ducassé. A Backward Slicing Algorithm for Prolog. In R. Cousot and D.A. Schmidt, editors, Static Analysis Symposium, Aachen, pages 317-331, September 1996. Springer-Verlag, LNCS 1145. [WWW]
Abstract:
 Slicing is a program analysis technique originally developed by Weiser for imperative languages. Weiser showed that slicing is a natural tool for debugging, but it has other numerous applications (program integration, program optimization, etc.) In this article we describe a backward slicing algorithm for Prolog which produces executable slices. The proposed algorithm is applicable at least to pure Prolog extended by some simple built-in predicates that handle the explicit unification =/2 and arithmetic. To our knowledge, this algorithm is the first one to be proposed for Prolog. Because of the indeterminism and lack of explicit control flow of Prolog, existing algorithms cannot be trivially adapted. The two main contributions of this paper are a general definition of slicing adapted to Prolog and a slicing algorithm that produces executable programs.

@InProceedings{sm96,
author = {S. Schoenig and M. Ducassé},
url = {ftp://ftp.irisa.fr/local/lande/ssmd-sas96.ps.gz},
title = {A Backward Slicing Algorithm for Prolog},
booktitle = {Static Analysis Symposium},
year = {1996},
editor = {R. Cousot and D.A. Schmidt},
pages = {317-331},
publisher = {Springer-Verlag, LNCS 1145},
month = {September},
abstract = {Slicing is a program analysis technique originally developed by Weiser for imperative languages. Weiser showed that slicing is a natural tool for debugging, but it has other numerous applications (program integration, program optimization, etc.) In this article we describe a backward slicing algorithm for Prolog which produces executable slices. The proposed algorithm is applicable at least to pure Prolog extended by some simple built-in predicates that handle the explicit unification =/2 and arithmetic. To our knowledge, this algorithm is the first one to be proposed for Prolog. Because of the indeterminism and lack of explicit control flow of Prolog, existing algorithms cannot be trivially adapted. The two main contributions of this paper are a general definition of slicing adapted to Prolog and a slicing algorithm that produces executable programs. }
}


5. S. Schoenig and M. Ducassé. Slicing pour programmes Prolog. In Actes des journées GDR programmation'96, Orléans, Novembre 1996. Université de Bordeaux I. [WWW]
Abstract:
 Le slicing est une technique d'analyse de programme développée à l'origine par Weiser pour les langages impératifs. Weiser a montré que le slicing est un outil naturel de débogage, mais il a également de nombreuses autres applications (intégration de programmes, optimisation, etc.) Dans cet article, nous proposons une définition du slicing pour Prolog et un algorithme. Celui-ci est au moins applicable à Prolog pur étendu par quelques prédicats de base (=/2 et arithmétiques). À notre connaissance, cet algorithme est le premier à être proposé pour Prolog. Les spécificités de Prolog (indéterminisme et manque de flot de contr\^ole explicite), ne permettent pas d'adapter trivialement les algorithmes existants pour langages impératifs.

@InProceedings{sm96b,
author = {S. Schoenig and M. Ducassé},
url = {ftp://ftp.irisa.fr/local/lande/ssmd-gdr96.ps.Z},
title = {Slicing pour programmes Prolog},
booktitle = {Actes des journées GDR programmation'96, Orléans},
publisher = {Université de Bordeaux I},
month = {Novembre},
year = {1996},
abstract = {Le slicing est une technique d'analyse de programme développée à l'origine par Weiser pour les langages impératifs. Weiser a montré que le slicing est un outil naturel de débogage, mais il a également de nombreuses autres applications (intégration de programmes, optimisation, etc.) Dans cet article, nous proposons une définition du slicing pour Prolog et un algorithme. Celui-ci est au moins applicable à Prolog pur étendu par quelques prédicats de base (=/2 et arithmétiques). À notre connaissance, cet algorithme est le premier à être proposé pour Prolog. Les spécificités de Prolog (indéterminisme et manque de flot de contr\^ole explicite), ne permettent pas d'adapter trivialement les algorithmes existants pour langages impératifs. }
}


BACK TO INDEX

Disclaimer:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All person copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Les documents contenus dans ces répertoires sont rendus disponibles par les auteurs qui y ont contribué en vue d'assurer la diffusion à temps de travaux savants et techniques sur une base non-commerciale. Les droits de copie et autres droits sont gardés par les auteurs et par les détenteurs du copyright, en dépit du fait qu'ils présentent ici leurs travaux sous forme électronique. Les personnes copiant ces informations doivent adhérer aux termes et contraintes couverts par le copyright de chaque auteur. Ces travaux ne peuvent pas être rendus disponibles ailleurs sans la permission explicite du détenteur du copyright.

Last modified: Thu Apr 8 17:20:28 2021
Author: ferre.

This document was translated from BibTEX by bibtex2html