Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

LIFE is a programming language proposing to integrate logic programming, functional programming, and object-oriented programming. It replaces first-order terms with &psgr;-terms, data structures that allow computing with partial information. These are approximation structures denoting sets of values. LIFE further enriches the expressiveness of &psgr;-terms with functional dependency constraints. We must explain the meaning and use of functions in LIFE declaratively, as solving partial information constraints. These constraints do not attempt to generate their solutions but behave as demons filtering out anything else. In this manner, LIFE functions act as declarative coroutines. We need to show that the &psgr;-term's approximation semantics is congruent with an operational semantics viewing functional reduction as an effective enforcing of passive constraints. In this article, we develop a general formal framework for entailment and disentailment of constraints based on a technique called relative simplification. We study its operational and semantical properties, and we use it to account for functional application over &psgr;-terms in LIFE.

REFERENCES

• 1: Hassan Aït-Kaci, Warren's abstract machine: a tutorial reconstruction, MIT Press, Cambridge, MA, 1991
• 2: Hassan Aït-Kaci, An algebraic semantics approach to the effective resolution of type equations, Theoretical Computer Science, v.45 n.3, p.293-351, Sept., 1986
• 3: AiT-KAcI, H. AND NASR, R. 1989. Integrating logic and functional programming. Lisp Symb Comput. 2, 51-89.
• 4: H Aït-Kaci , R Nasr, Login: A logic programming language with built-in inheritance, Journal of Logic Programming, v.3 n.3, p.185-215, Oct. 1986 [doi>10.1016/0743-1066(86)90013-0]
• 5: Hassan Aït-Kaci , Andreas Podelski, Entailment and Disentailment of Order-Sorted Feature Constraints, Proceedings of the 4th International Conference on Logic Programming and Automated Reasoning, p.1-18, July 13-20, 1993
• 6: AIT-KACI, H. AND POI)ELSKI, A. 1993b. Towards a meaning of LIFE. J. Logic Program. 16, 3-4 (July-Aug), 195-234.
• 7: AiT-KACI, H. AND PODELSKI, A. 1991. Functions as passive constraints in LIFE. PRL Res. Rep. 13. (June), Paris Research Laboratory, Digital Equipment Corporation, Rueil-Malmaison, France.
• 8: Hassan Aït-Kaci , Andreas Podelski , Gert Smolka, A feature constraint system for logic programming with entailment, Theoretical Computer Science, v.122 n.1-2, p.263-283, Jan. 3, 1994 [doi>10.1016/0304-3975(94)90209-7]
• 9: BACKOFEN, R. AND SMOLKA~ G. 1992. A complete and dectdable feature theory DFKI Res Rep. RR-30-92, German Research Center for Amficml Intelligence, Saarbrticken, Germany.
• 10: BONNIER, S. AND MALUSZYI~ISKI, J. 1988. Towards a clean amalgamation of logic programs with external procedures in b)gtc Programming. Proceedmgs of the 5th lnternattonal Conference and Symposmm. MIT Press, Cambridge, Mass., 311-326.
• 11: CLARK, K. L. 1978 Negation as failure. In Logt~ and Data Bases. Plenum Press, New York, 293-322.
• 12: COLMERAUER, A. 1984. Equations and inequations on finite and infimte trees. In Proceedings oJ the 2nd International Conference on Frith Generation Computer Systems. ICOT, Tokyo, 85-99
• 13: COLMERAUER, A. 1982a. Prolog and infinite trees In l_x~gic Programming. Academic Press, New York, 153-172.
• 14: COLMERAUER, t. 1982b. Prolog If' Manuel de rdfdrence et modble thdorique Rapport technique (March), Unlversltd de Marseflle, Groupe d'Intelligence Artificielle, Facultd des Sciences de Lummy, Marsedle, France.
• 15: COURCELLE, B. 1983. Fundamental properties of infinite trees Theor Comput. Scz 25, 95-169.
• 16: Seif Haridi , Sverker Janson, Kernel Andorra Prolog and its computation model, Logic programming, MIT Press, Cambridge, MA, 1990
• 17: Seif Haridi , Sverker Janson , Catuscia Palamidessi, Structural operational semantics for AKL, Future Generation Computer Systems, v.8 n.4, p.409-421, Sept. 1992 [doi>10.1016/0167-739X(92)90072-J]
• 18: HARPER, R., MILNER, R., AND TOFTE, M. 1988. The definmon of standard ML - Version 2 Rep LFCS-88-62, Univ. of Edinburgh, Edinburgh, UK
• 19: HSI4FELD, M. AND SMOLKA, G. 1988 Definite relations over constraint languages LILOG Rep 53 (October), IWBS, IBM Deutschland, Stuttgart, Germany
• 20: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• 21: J.-L. Lassez , M. J. Maher , K. Marriott, Unification revisited, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 22: MAHER, M. 1987 Logic semantics for a class of committed-choice programs In Logic Programming, Proceedings of the 4th Internattonal Conference MIT Press, Cambridge, Mass., 858-876
• 23: Lee Naish, Negations and quantifiers in NU-Prolog, Proceedings on Third international conference on logic programming, p.624-634, September 1986, London, United Kingdom
• 24: Viswanath Ramachandran , Pascal Van Hentenryck, Incremental Algorithms for Constraint Solving and Entailment over Rational Trees, Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, p.205-217, December 15-17, 1993
• 25: Vítor Santos Costa , David H. D. Warren , Rong Yang, Andorra I: a parallel Prolog system that transparently exploits both And-and or-parallelism, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.83-93, April 21-24, 1991, Williamsburg, Virginia, United States [doi>10.1145/109625.109635]
• 26: Vijay A. Saraswat , Martin Rinard, Concurrent constraint programming, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, December 1989, San Francisco, California, United States [doi>10.1145/96709.96733]
• 27: SMOLKA, G. 1991 Residuation and guarded rules for constraint logic programming PRL Res Rep. 12, Paris Research Laboratory, Digital Equipment Corporation, Rued-Malmatson, France To appear in Constraint Logtc Programming Selected Research. M IT Press, Cambridge, Mass.
• 28: SMOLKA, G. AND TREINEN, R. 1992. Records for logm programming. In tx~gic Programming, Proceedings oJ the Joint Internanonal ConJerence and Symposium on Logic Programming M IT Press, Cambridge, Mass, 240-254

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax
      D.3.2 Language Classifications
          Subjects: Nonprocedural languages**; Concurrent, distributed, and parallel languages; Applicative (functional) languages
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures; Data types and structures; Coroutines

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees; Graphs and networks

General Terms:
Design, Languages, Theory

Keywords:
&psgr;-terms, committed-choice languages, concurrent constraint programming, coroutining, first-order terms, matching, relative simplification, residuation, unification