
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 223232,
September 1996.
GMD Forschungszentrum Informationstechnik GMBH, GMDSTUDIEN Nr.296, ISBN3884572962.
Note: One page abstract also appears in Proc. of the JICSLP'96, MIT Press, ISBN 0262631733.
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 lowlevel tracer would run at about the same speed. However they had no reasonable lowlevel 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 builtin lowlevel 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 lowlevel 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 builtin 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):155200, 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. Highperformance logic programming with the Aquarius Prolog compiler. Computer, 25(1):5468, 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 = {223232},
publisher = {GMD Forschungszentrum Informationstechnik GMBH, GMDSTUDIEN Nr.296, ISBN3884572962},
month = {September},
note = {One page abstract also appears in Proc. of the JICSLP'96, MIT Press, ISBN 0262631733},
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 lowlevel tracer would run at about the same speed. However they had no reasonable lowlevel 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 builtin lowlevel 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 lowlevel 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 builtin 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):155200, 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. Highperformance logic programming with the Aquarius Prolog compiler. Computer, 25(1):5468, January 1992. }
}

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 4761,
1996.
[WWW]
Keyword(s): Logic programming,
typing,
polymorphism,
secondorder lambdacalculus..
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 headcondition is at the heart of these problems, and conclude that it should be enforced. We propose a secondorder 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 = {4761},
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 headcondition is at the heart of these problems, and conclude that it should be enforced. We propose a secondorder 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, secondorder lambdacalculus.},
url = {ftp://ftp.irisa.fr/local/lande/plorplilp96.ps.gz}
}

O. Ridoux.
Engineering Transformations of Attributed Grammars in $\lambda$Prolog.
In M. Maher, editor,
Joint Int. Conf. and Symp. Logic Programming,
pages 244258,
1996.
MIT Press.
[WWW]
Keyword(s): Syntaxdirected 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 leftrecursion, 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 = {244258},
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 leftrecursion, 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 = {Syntaxdirected translation, grammar transformations, logic grammars, DCG, LambdaProlog.},
url = {ftp://ftp.irisa.fr/local/lande/orjicslp96.ps.gz}
}

S. Schoenig and M. Ducassé.
A Backward Slicing Algorithm for Prolog.
In R. Cousot and D.A. Schmidt, editors,
Static Analysis Symposium,
Aachen,
pages 317331,
September 1996.
SpringerVerlag, 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 builtin 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/ssmdsas96.ps.gz},
title = {A Backward Slicing Algorithm for Prolog},
booktitle = {Static Analysis Symposium},
year = {1996},
editor = {R. Cousot and D.A. Schmidt},
pages = {317331},
publisher = {SpringerVerlag, LNCS 1145},
address = {Aachen},
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 builtin 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. }
}

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. Celuici 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/ssmdgdr96.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. Celuici 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. }
}