Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-19T07:19:50.214Z Has data issue: false hasContentIssue false
  • English
  • Français

A structured alternative to Prolog with simple compositional semantics

Published online by Cambridge University Press:  06 July 2011

ANTÓNIO PORTO
ANTÓNIO PORTO*
Affiliation:
LIACC/Department of Computer Science, Faculty of Sciences, University of Porto, Portugal (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Prolog's very useful expressive power is not captured by traditional logic programming semantics, due mainly to the cut and goal and clause order. Several alternative semantics have been put forward, exposing operational details of the computation state. We propose instead to redesign Prolog around structured alternatives to the cut and clauses, keeping the expressive power and computation model but with a compositional denotational semantics over much simpler states—just variable bindings. This considerably eases reasoning about programs, by programmers and tools such as a partial evaluator, with safe unfolding of calls through predicate definitions. An if-then-else across clauses replaces most uses of the cut, but the cut's full power is achieved by an until construct. Disjunction, conjunction and until, along with unification, are the primitive goal types with a compositional semantics yielding sequences of variable-binding solutions. This extends to programs via the usual technique of a least fixpoint construction. A simple interpreter for Prolog in the alternative language, and a definition of until in Prolog, establish the identical expressive power of the two languages. Many useful control constructs are derivable from the primitives, and the semantic framework illuminates the discussion of alternative ones. The formalisation rests on a term language with variable abstraction as in the λ-calculus. A clause is an abstraction on the call arguments, a continuation, and the local variables. It can be inclusive or exclusive, expressing a local case bound to a continuation by either a disjunction or an if-then-else. Clauses are open definitions, composed (and closed) with simple functional application β-reduction). This paves the way for a simple account of flexible module composition mechanisms. Cube, a concrete language with the exposed principles, has been implemented on top of a Prolog engine and successfully used to build large real-world applications.

Keywords

PrologCutCompositional semanticsDenotational semantics
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Special Issue 4-5: 27th International Conference on Logic Programming , July 2011 , pp. 611 - 627
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aït-Kaci, H. 1991. Warren's Abstract Machine: A Tutorial Reconstruction. MIT.Google Scholar
Andrews, J. H. 2003. The witness properties and the semantics of the prolog cut. Theory Practice Logic Programming 3 (1), 1–59.Google Scholar
Bossi, A., Gabbrielli, M., Levi, G. and Martelli, M. 1994. The s-semantics approach: Theory and applications. The Journal of Logic Programming 19/20, 149–197.CrossRefGoogle Scholar
Clark, K. L. 1978. Negation as failure. In Logic and Databases (New York), Gallaire, H. and Minker, J., Eds. Plenum, 293–322.Google Scholar
Colmerauer, A. 1993. Prolog and infinite trees. In Logic Programming, Clark, K. and Tärnlund, S.-A., Eds. A.P.I.C. Studies in Data Processing, vol. 16. Academic, 231–251.Google Scholar
de Bruin, A. and de Vink, E. 1989. Continuation semantics for PROLOG with cut. In TAPSOFT '89; Proceedings of the International Joint Conference on Theory and Practice of Software Development, Díaz, J. and Orejas, F., Eds. Springer, 178–192.Google Scholar
Debray, S. K. and Mishra, P. 1988. Denotational and operational semantics for Prolog. Journal of Logic Programming 5 (1), 81–91.Google Scholar
Deransart, P., Ed-Dbali, A. and Cervoni, L. 1991. Prolog: The Standard; reference manual. Springer.Google Scholar
Kakas, A., Kowalski, R. and Toni, F. 1993. Abductive logic programming. Journal of Logic and Computation 2 (6), 719–770.Google Scholar
Li, B. Z. 1994. A pi-calculus specification of Prolog. In ESOP '94 Proceedings of the 5th European Symposium on Programming: Programming Languages and Systems. Sannella, D., Ed. Springer, 379–393.Google Scholar
Monteiro, L. and Porto, A. 1989. Contextual logic programming. In Logic Programming, Proceedings of the Sixth International Conference, Levi, G. and Martelli, M., Eds. Lisbon, Portugal, MIT, 284–299.Google Scholar
Monteiro, L. and Porto, A. 1998. Entailment-based actions for coordination. Theoretical Computer Science 192, 259–286.Google Scholar
Naish, L. July 1986. Negation and quantifiers in NU-Prolog. In Proceedings of the Third International Conference on Logic Programming, London, UK, Springer, 624–634.CrossRefGoogle Scholar
Porto, A. 2002. Structural abstraction and application in logic programming. In Functional and Logic Programming, 6th International Symposium, FLOPS 2002, Proceedings, Hu, Z. and Rodríguez-Artalejo, M., Eds. Lecture Notes in Computer Science, vol. 2441. Springer, 275–289.Google Scholar
Porto, A. 2003. An integrated information system powered by Prolog. In Practical Aspects of Declarative Languages, 5th International Symposium, Proceedings, Dahl, V. and Wadler, P., Eds. Lecture Notes in Computer Science, vol. 2562. Springer, 92–109.CrossRefGoogle Scholar
Seres, S., Spivey, M. and Hoare, T. 1999. Algebra of logic programming. In Proceedings of the 1999 international conference on Logic programming. Massachusetts Institute of Technology, Cambridge, MA, USA, 184–199.Google Scholar
Somogyi, Z., Henderson, F. and Conway, T. 1996. The execution algorithm of Mercury, an efficient purely declarative logic programming language. Journal of Logic Programming 29 (1–3), 17–64.Google Scholar
Spoto, F. 2000. Operational and goal-independent denotational semantics for prolog with cut. Journal of Logic Programming 42 (1), 1–46.Google Scholar
van Emden, M. H. and Kowalski, R. A. 1976. The semantics of predicate logic as a programming language. Journal of the ACM 23 (4), 733–742.CrossRefGoogle Scholar