TY - GEN
T1 - An abstract machine for fixed-order dynamically stratified programs
AU - Sagonas, Konstantinos
AU - Swift, Terrance
AU - Warren, David S.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.
PY - 1996
Y1 - 1996
N2 - It is known that a fixed computation rule, such as used in most logic programming systems, does not suffice for normal logic programs. For instance, SLS resolution, which evaluates programs according to the well-founded semantics, makes use of an oracle to determine the next literal to select in [5], and of ideal parallelism in [8]. Given these limits, it is natural to define a subclass of normal programs for which a fixed computation rule is adequate. This class, left-to-right dynamically stratified programs, properly includes other stratification classes. Left-to-right dynamically stratified programs are of interest because they are posited to be amenable to efficient implementation. We demonstrate that this is in fact the case with an implementation based on the SLG-WAM of XSB [10]. The SLG-WAM is an extension to the underlying implementation model of Prolog, the WAM, and has been shown to be extremely efficient for definite programs [13]. We show that extending the engine for left-to-right dynamically stratified programs does not slow down execution for definite programs or for Prolog-style SLD evaluation. Indeed, implementation of stratification leads to the technique of early completion which can also benefit definite programs.
AB - It is known that a fixed computation rule, such as used in most logic programming systems, does not suffice for normal logic programs. For instance, SLS resolution, which evaluates programs according to the well-founded semantics, makes use of an oracle to determine the next literal to select in [5], and of ideal parallelism in [8]. Given these limits, it is natural to define a subclass of normal programs for which a fixed computation rule is adequate. This class, left-to-right dynamically stratified programs, properly includes other stratification classes. Left-to-right dynamically stratified programs are of interest because they are posited to be amenable to efficient implementation. We demonstrate that this is in fact the case with an implementation based on the SLG-WAM of XSB [10]. The SLG-WAM is an extension to the underlying implementation model of Prolog, the WAM, and has been shown to be extremely efficient for definite programs [13]. We show that extending the engine for left-to-right dynamically stratified programs does not slow down execution for definite programs or for Prolog-style SLD evaluation. Indeed, implementation of stratification leads to the technique of early completion which can also benefit definite programs.
UR - http://www.scopus.com/inward/record.url?scp=84957685506&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84957685506&partnerID=8YFLogxK
U2 - 10.1007/3-540-61511-3_98
DO - 10.1007/3-540-61511-3_98
M3 - Conference contribution
AN - SCOPUS:84957685506
SN - 3540615113
SN - 9783540615118
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 328
EP - 342
BT - Automated Deduction – Cade-13 - 13th International Conference on Automated Deduction, Proceedings
A2 - Slaney, John K.
A2 - McRobbie, Michael A.
PB - Springer Verlag
T2 - 13th International Conference on Automated Deduction, CADE 1996
Y2 - 30 July 1996 through 3 August 1996
ER -