BACK TO INDEX

 Publications of year 1992
 Books and proceedings
1. M. Ducassé, Y.-J. Lin, and L.Ü. Yalcinalp, editors. Proceedings of IJCSLP'92 Workshop on Logic Programming Environments, November 1992. Note: Technical Report TR 92-143, Case Western Reserve University, Cleveland.
@Proceedings{dly92,
title = {Proceedings of IJCSLP'92 Workshop on Logic Programming Environments},
year = {1992},
editor = {M. Ducassé and Y.-J. Lin and L.Ü. Yalcinalp},
month = {November},
note = {Technical Report TR 92-143, Case Western Reserve University, Cleveland}
}


 Thesis
1. M. Ducassé. An extendable trace analyser to support automated debugging. PhD thesis, University of Rennes I, France, June 1992. Note: European Doctorate.
Abstract:
 The dissertation describes the innovative features of Opium, a high-level debugging environment for Prolog, designed and implemented at ECRC between 1985 and 1991. Debugging is a costly process, and automating it would significantly reduce the cost of software production and maintenance. However, it is unrealistic to aim at fully automating the task. In particular programmers have to understand rapidly changing situations, examining large amounts of data. In the current state of the art it is beyond the capabilities of computers to take the place of programmer's understanding. Nevertheless, computers can significantly help programmers to select the data to be analysed. The data used by program analysis in general is often restricted to the source code of the analysed programs. However, there is a complementary source of information, namely traces of program executions. An execution trace contains less general information than the program source, but it tells how the program behaves in a particular case. Furthermore, there are intrinsically dynamic aspects in a program which are best analysed at execution time, for example uses of read/write. These remarks suggested to build the automated debugging functionalities of Opium on top of an existing tracer, extending it to a general trace and source analyser. The most important features of Opium, not to be found in other debuggers, are as follows. - It provides a trace query language which is a solution to the ever growing command sets of other tracers. With two primitives plus Prolog, users can already specify more precise trace queries than with the hard coded commands of other tracers. - Opium is programmable and extendable. It is thus an environment where debugging strategies can be easily programmed and integrated. Some strategies are already implemented. - Abstract views of executions are proposed as a basis for automated debugging. They help users to understand the behaviours of programs by browsing through executions at a higher level than single steppers. Opium is fully implemented. More than 20 academic sites have recently requested Opium prototype, and some are actually implementing new abstract views.

@PhDThesis{duc92,
author = {M. Ducassé},
title = {An extendable trace analyser to support automated debugging},
school = {University of Rennes I, France},
month = {June},
year = {1992},
note = {European Doctorate},
abstract = {The dissertation describes the innovative features of Opium, a high-level debugging environment for Prolog, designed and implemented at ECRC between 1985 and 1991. Debugging is a costly process, and automating it would significantly reduce the cost of software production and maintenance. However, it is unrealistic to aim at fully automating the task. In particular programmers have to understand rapidly changing situations, examining large amounts of data. In the current state of the art it is beyond the capabilities of computers to take the place of programmer's understanding. Nevertheless, computers can significantly help programmers to select the data to be analysed. The data used by program analysis in general is often restricted to the source code of the analysed programs. However, there is a complementary source of information, namely traces of program executions. An execution trace contains less general information than the program source, but it tells how the program behaves in a particular case. Furthermore, there are intrinsically dynamic aspects in a program which are best analysed at execution time, for example uses of read/write. These remarks suggested to build the automated debugging functionalities of Opium on top of an existing tracer, extending it to a general trace and source analyser. The most important features of Opium, not to be found in other debuggers, are as follows. - It provides a trace query language which is a solution to the ever growing command sets of other tracers. With two primitives plus Prolog, users can already specify more precise trace queries than with the hard coded commands of other tracers. - Opium is programmable and extendable. It is thus an environment where debugging strategies can be easily programmed and integrated. Some strategies are already implemented. - Abstract views of executions are proposed as a basis for automated debugging. They help users to understand the behaviours of programs by browsing through executions at a higher level than single steppers. Opium is fully implemented. More than 20 academic sites have recently requested Opium prototype, and some are actually implementing new abstract views. }
}


 Conference articles
1. Y. Bekkers, O. Ridoux, and L. Ungaro. Dynamic Memory Management for Sequential Logic Programming Languages. In Y. Bekkers and J. Cohen, editors, Int. Worshop on Memory Management, volume 637 of LNCS, pages 82-102, 1992. Springer-Verlag. [WWW] Keyword(s): Memory management, logic programming, garbage collection, usefulness logic..
Abstract:
 Logic programming languages are becoming more complex with the introduction of new features such as constraints or terms with an equality theory. With this increase in complexity, they require more and more sophisticated memory management. This survey gives an insight into the memory management problems in sequential logic programming languages implementations; it also describes the presently know solutions. It is meant to be understood by non-specialists in logic programming with good knowledge of memory management in general. We first describe a "usefulness logic" for run-time objects. Usefulness logic defines non-garbage objects. Next, memory management systems are presented from the most trivial original run-time system, with no real concern for memory problems, to elaborated run-time systems with memory management closely observing the usefulness logic. Finally, the choice of a garbage collection technique is discussed in relation with logic programming specifities.

@InProceedings{bekkers:dynamic:iwmm:92,
author = {Y. Bekkers and O. Ridoux and L. Ungaro},
title = {Dynamic Memory Management for Sequential Logic Programming Languages},
booktitle = {Int. Worshop on Memory Management},
series = {LNCS},
volume = 637,
comment = {Saint-Malo, France},
editor = {Y. Bekkers and J.~Cohen},
publisher = {Springer-Verlag},
pages = {82--102},
year = 1992,
abstract = {Logic programming languages are becoming more complex with the introduction of new features such as constraints or terms with an equality theory. With this increase in complexity, they require more and more sophisticated memory management. This survey gives an insight into the memory management problems in sequential logic programming languages implementations; it also describes the presently know solutions. It is meant to be understood by non-specialists in logic programming with good knowledge of memory management in general. We first describe a "usefulness logic" for run-time objects. Usefulness logic defines non-garbage objects. Next, memory management systems are presented from the most trivial original run-time system, with no real concern for memory problems, to elaborated run-time systems with memory management closely observing the usefulness logic. Finally, the choice of a garbage collection technique is discussed in relation with logic programming specifities.},
keywords = {Memory management, logic programming, garbage collection, usefulness logic.},
url = {ftp://ftp.irisa.fr/local/lande/yborlu-iwmm92.ps.Z}
}


2. P. Brisset and O. Ridoux. The Architecture of an Implementation of $\lambda$Prolog: Prolog/Mali. In Workshop on $\lambda$Prolog, Philadelphia, 1992. [WWW] Keyword(s): LambdaProlog, implementation, compilation, memory management..
Abstract:
 LambdaProlog is a logic programming language accepting a more general clause form than standard Prolog (namely hereditary Harrop formulas instead of Horn formulas) and using simply typed lambda-terms as a term domain instead of first order terms. Despite these extensions, it is still amenable to goal-directed proofs and can still be given procedural semantics. However, the execution of LambdaProlog programs requires several departures from the standard resolution scheme. First, the augmented clause form causes the program (a set of clauses) and the signature (a set of constants) to be changeable, but in a very disciplined way. Second, the new term domain has a semi-decidable and infinitary unification theory, and it introduces the need for a beta-reduction operation at run-time. MALI is an abstract memory that is suitable for storing the search-state of depth-first search processes. Its main feature is its efficient memory management. We have used an original LambdaProlog-to-C translation: predicates are transformed into functions operating on several continuations. The compilation scheme is sometimes an adaptation of the standard Prolog scheme, but at other times it has to handle new features such as types, beta-reduction and delayed unification. Two keywords of this implementation are "sharing" and "folding" of representations. Sharing amounts to recognising that some representation already exists and reusing it. Folding amounts to recognising that two different representations represent the same thing and replacing one by the other. We assume a basic knowledge of Prolog and LambdaProlog.

@InProceedings{bo92b,
author = {P. Brisset and O. Ridoux},
title = {The Architecture of an Implementation of $\lambda${Prolog}: {Prolog/Mali}},
booktitle = {Workshop on $\lambda$Prolog},
year = 1992,
abstract = {LambdaProlog is a logic programming language accepting a more general clause form than standard Prolog (namely hereditary Harrop formulas instead of Horn formulas) and using simply typed lambda-terms as a term domain instead of first order terms. Despite these extensions, it is still amenable to goal-directed proofs and can still be given procedural semantics. However, the execution of LambdaProlog programs requires several departures from the standard resolution scheme. First, the augmented clause form causes the program (a set of clauses) and the signature (a set of constants) to be changeable, but in a very disciplined way. Second, the new term domain has a semi-decidable and infinitary unification theory, and it introduces the need for a beta-reduction operation at run-time. MALI is an abstract memory that is suitable for storing the search-state of depth-first search processes. Its main feature is its efficient memory management. We have used an original LambdaProlog-to-C translation: predicates are transformed into functions operating on several continuations. The compilation scheme is sometimes an adaptation of the standard Prolog scheme, but at other times it has to handle new features such as types, beta-reduction and delayed unification. Two keywords of this implementation are "sharing" and "folding" of representations. Sharing amounts to recognising that some representation already exists and reusing it. Folding amounts to recognising that two different representations represent the same thing and replacing one by the other. We assume a basic knowledge of Prolog and LambdaProlog.},
keywords = {LambdaProlog, implementation, compilation, memory management.},
url = {ftp://ftp.irisa.fr/local/lande/pbor-wlp92.ps.Z}
}


3. M. Ducassé. A general trace query mechanism based on Prolog. In M. Bruynooghe and M. Wirsing, editors, International Symposium on Programming Language Implementation and Logic Programming, volume 631 of Lecture Notes in Computer Science, pages 400-414, August 1992. Springer-Verlag. [WWW]
Abstract:
 We present a general trace query language which is a solution to the ever growing command sets of other tracers. It provides all the required generality while being very simple and efficient. We model a program execution into a trace which is a stream of events. Execution events have a uniform representation, and can be analysed by Prolog programs. With this approach and thanks to the expressive power of Prolog, two high-level primitives plus Prolog are enough to provide a general trace query language. With a few optimizations this language can work on large executions without any loss of performance, if compared to traditional tracers. This paper describes the trace query mechanism from its high level specification down to some implementation details. The proposed model of trace query depends only on the sequentiality of the execution, and the principles behind the design of the optimizations do not depend on the traced language.

@InProceedings{duc92f,
author = {M. Ducassé},
url = {ftp://ftp.irisa.fr/local/lande/md-plilp92.ps.gz},
title = {A general trace query mechanism based on {Prolog}},
booktitle = {International Symposium on Programming Language Implementation and Logic Programming},
year = {1992},
editor = {M. Bruynooghe and M. Wirsing},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
volume = {631},
month = {August},
pages = {400-414},
abstract = {We present a general trace query language which is a solution to the ever growing command sets of other tracers. It provides all the required generality while being very simple and efficient. We model a program execution into a trace which is a stream of events. Execution events have a uniform representation, and can be analysed by Prolog programs. With this approach and thanks to the expressive power of Prolog, two high-level primitives plus Prolog are enough to provide a general trace query language. With a few optimizations this language can work on large executions without any loss of performance, if compared to traditional tracers. This paper describes the trace query mechanism from its high level specification down to some implementation details. The proposed model of trace query depends only on the sequentiality of the execution, and the principles behind the design of the optimizations do not depend on the traced language. }
}


4. M. Ducassé. A trace analyser to prototype explanations. In Proceedings of JICSLP'92 Workshop on Logic Programming Environments, Washington D.C., November 1992. Note: Technical Report TR 92-143, Case Western Reserve University, Cleveland.
Abstract:
 Automated debugging and expert system explanations have in common to aim at helping people to understand executions. We have designed an extendable trace analyser for the purpose of automated debugging, which we propose to use to prototype expert system explanations. Two examples illustrate how simple it is to implement abstract tracing of executions and how easy it is to play with them.

@InProceedings{duc92b,
author = {M. Ducassé},
title = {A trace analyser to prototype explanations},
booktitle = {Proceedings of JICSLP'92 Workshop on Logic Programming Environments},
year = {1992},
month = {November},
note = {Technical Report TR 92-143, Case Western Reserve University, Cleveland},
abstract = {Automated debugging and expert system explanations have in common to aim at helping people to understand executions. We have designed an extendable trace analyser for the purpose of automated debugging, which we propose to use to prototype expert system explanations. Two examples illustrate how simple it is to implement abstract tracing of executions and how easy it is to play with them. }
}


5. M. Ducassé. Analysis of failing Prolog executions. In Actes des Journées Francophones sur la Programmation Logique, Mai 1992.
Abstract:
 The result of a Prolog execution can simply be no'', when the programmer is expecting something else. This symptom is typical of Prolog, and especially requires the help of an execution tracer to get clues of what the problem can be. We present a solution which helps programmers to understand how unexpected failures have occurred. We first propose a hierarchy of failing goals. We argue that there is one kind of leaf failures which is interesting to track at the first place. Then we give the algorithm for our leaf failure tracking and two examples illustrating its use.

@InProceedings{duc92c,
author = {M. Ducassé},
title = {Analysis of failing {Prolog} executions},
booktitle = {Actes des Journées Francophones sur la Programmation Logique},
year = {1992},
month = {Mai},
abstract = {The result of a Prolog execution can simply be no'', when the programmer is expecting something else. This symptom is typical of Prolog, and especially requires the help of an execution tracer to get clues of what the problem can be. We present a solution which helps programmers to understand how unexpected failures have occurred. We first propose a hierarchy of failing goals. We argue that there is one kind of leaf failures which is interesting to track at the first place. Then we give the algorithm for our leaf failure tracking and two examples illustrating its use. }
}


6. M. Ducassé. Opium: An advanced debugging system. In G. Comyn and N. Fuchs, editors, Proceedings of the Second Logic Programming Summer School, September 1992. Esprit Network of Excellence in Computational Logic COMPULOG-NET, Springer-Verlag, LNAI 636. [WWW]
Abstract:
 The data used by program analysis in general is often restricted to the source code of the analysed programs. However, there is a complementary source of information, namely traces of program executions. Usual tracers, which extract this trace information, do not allow for general trace analysis. Opium, our debugger for Prolog, sets up a framework where program sources and traces of program executions can be jointly analysed. As the debugging process is heuristic and not all the debugging strategies have been identified so far, Opium is programmable. In particular, its trace query language gives more flexibility and more power than the hard coded command sets of usual tracers. This trace query language is based on Prolog. Opium is therefore both a helpful tool for Prolog and a nice application of Prolog. The most innovative extensions of Opium compute abstract views of Prolog executions to help users understand the behaviours of programs. In particular they help them understand how error symptoms have been produced. This article briefly recalls some general information about Opium. A debugging session is then commented in detail.

@InProceedings{duc92d,
author = {M. Ducassé},
url = {ftp://ftp.irisa.fr/local/lande/md-lpss92.ps.gz},
title = {Opium: An advanced debugging system},
organization = {Esprit Network of Excellence in Computational Logic {COMPULOG-NET}},
booktitle = {Proceedings of the Second Logic Programming Summer School},
year = {1992},
editor = {G. Comyn and N. Fuchs},
publisher = {Springer-Verlag, LNAI 636},
month = {September},
abstract = {The data used by program analysis in general is often restricted to the source code of the analysed programs. However, there is a complementary source of information, namely traces of program executions. Usual tracers, which extract this trace information, do not allow for general trace analysis. Opium, our debugger for Prolog, sets up a framework where program sources and traces of program executions can be jointly analysed. As the debugging process is heuristic and not all the debugging strategies have been identified so far, Opium is programmable. In particular, its trace query language gives more flexibility and more power than the hard coded command sets of usual tracers. This trace query language is based on Prolog. Opium is therefore both a helpful tool for Prolog and a nice application of Prolog. The most innovative extensions of Opium compute abstract views of Prolog executions to help users understand the behaviours of programs. In particular they help them understand how error symptoms have been produced. This article briefly recalls some general information about Opium. A debugging session is then commented in detail. }
}


 Internal reports
1. P. Brisset and O. Ridoux. The Compilation of $\lambda$Prolog and its execution with MALI. Publication Interne 687, IRISA, 1992. [WWW] Keyword(s): LambdaProlog, implementation, compilation, memory management..
Abstract:
 We present a compiled implementation of LambdaProlog that uses the abstract memory MALI for representing the execution state. LambdaProlog is a logic programming language allowing a more general clause form than Standard Prolog's (namely hereditary Harrop formulas instead of Horn formulas) and using simply typed lambda-terms as a term domain instead of first order terms. The augmented clause form causes the program (a set of clauses) and the signature (a set of constants) to be changeable in a very disciplined way. The new term domain has a semi-decidable and infinitary unification theory, and it introduces the need for a beta-reduction operation at run-time. MALI is an abstract memory that is suitable for storing the search-state of depth-first search processes. Its main feature is its efficient memory management. We have used an original LambdaProlog-to-C translation along which predicates are transformed into functions operating on continuations for handling failure and success in unifications, and changes in signatures and programs. Two keywords of this implementation are sharing'' and folding'' of representations. Sharing amounts to recognising that some representation already exists and to reuse it. Folding amounts to recognising that two different representations represent the same thing and to replace one by the other.

@TechReport{bo92a,
author = {P. Brisset and O. Ridoux},
title = {The Compilation of $\lambda${Prolog} and its execution with {MALI}},
institution = {IRISA},
type = {Publication Interne},
number = {687},
year = 1992,
abstract = {We present a compiled implementation of LambdaProlog that uses the abstract memory MALI for representing the execution state. LambdaProlog is a logic programming language allowing a more general clause form than Standard Prolog's (namely hereditary Harrop formulas instead of Horn formulas) and using simply typed lambda-terms as a term domain instead of first order terms. The augmented clause form causes the program (a set of clauses) and the signature (a set of constants) to be changeable in a very disciplined way. The new term domain has a semi-decidable and infinitary unification theory, and it introduces the need for a beta-reduction operation at run-time. MALI is an abstract memory that is suitable for storing the search-state of depth-first search processes. Its main feature is its efficient memory management. We have used an original LambdaProlog-to-C translation along which predicates are transformed into functions operating on continuations for handling failure and success in unifications, and changes in signatures and programs. Two keywords of this implementation are sharing'' and folding'' of representations. Sharing amounts to recognising that some representation already exists and to reuse it. Folding amounts to recognising that two different representations represent the same thing and to replace one by the other.},
keywords = {LambdaProlog, implementation, compilation, memory management.},
url = {ftp://ftp.irisa.fr/local/lande/pbor-tr-irisa687-92.ps.Z}
}


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.