-
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}
}
-
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},
address = {Philadelphia},
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}
}
-
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. }
}
-
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},
address = {Washington D.C.},
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. }
}
-
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. }
}
-
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. }
}