Functional programing and the logical variable

ABSTRACT

Logic programming offers a variety of computational effects which go beyond those customarily found in functional programming languages. Among these effects is the notion of the “logical variable.” i.e. a value determined by the intersection of constraints, rather than by direct binding. We argue that this concept is “separable” from logic programming, and can sensibly be incorporated into existing functional languages. Moreover, this extension appears to significantly widen the range of problems which can efficiently be addressed in function form, albeit at some loss of conceptual purity. In particular, a form of side-effects arises under this extension, since a function invocation can exert constraints on variables shared with other function invocations. Nevertheless, we demonstrate that determinacy can be retained, even under parallel execution. The graph reduction language FGL is used for this demonstration, by being extended to a language FGL+LV permitting formal parameter expressions, with variables occurring therein bound by unification. The determinacy argument is based on a novel dataflow-like rendering of unification. In addition the complete partial order employed in this proof is unusual in its explicit representation of demand, a necessity given the “benign” side-effects that arise. An implementation technique is suggested, suitable for reduction architectures.

REFERENCES

• 1: [1] H. Abramson. Unification-Based Conditional Binding Constructs. In Proc. First International Logic Programming Conference. Marseille, 1982.
• 2: [2] H. Abramson. A Prological Definition of HASL, a Purely Functional Language with Unification Based on Conditional Binding Expressions. New Generation Computing 2:3-35, 1984.
• 3: [3] Department of Computer Sciences, Chalmers University of Technology, Aspenas, Sweden. Symposium on Functional Languages and Computer Architecture, Laboratory on Programming Methodology, 1981.
• 4: [4] R. Barbuti, M. Bellia, G. Levi and M. Martelli. On the Integration of Logic Programming and Functional Programming. In D. DeGroot (editor), International Symposium on Logic Programming, pages 160-166. IEEE, Atlantic City. N. J., February, 1984.
• 5: Alan Borning, The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.353-387, Oct. 1981 [doi>10.1145/357146.357147]
• 6: [6] J. A. Goguen and J. Meseguer. Equality, Types, Modules and Generics for Logic Programming. In Sten-Ake Tarnlund (editor), Second International Logic Programming Conference, pages 114-125. Uppsata University, Uppsala, Sweden, July, 1984.
• 7: [7] S. Haridi. Logic Programming Based on a Natural Deduction System. PhD thesis, Royai Inst. of Tech., 1981.
• 8: [8] K. Kahn. The Implementation of Uniform -- a Knowledge-Representation/Programming Language Based on Equivalence of Descriptions. In ECAI. Orsay, France, 1982.
• 9: [9] R. M. Keller. G. Lindstrom, and S. Patil. A Loosely-Coupled Applicative Multi-Processing System. In AFIPS Conference Proceedings, pages 613-622. June, 1979.
• 10: [10] R. M. Keller, B. Jayaraman, D. Rose, G. Lindstrom. FGL (Function Graph Language) Programmers' Guide. Technical Report AMPS Technical Memorandum No. 1, University of Utah, Computer Science Department, July. 1980.
• 11: [11] R. M. Keller. Semantics and Applications of Function Graphs. Technical Report UUCS-80-112. University of Utah, Computer Science Department, 1980.
• 12: [12] R. M. Keller and G. Lindstrom. Hierarchical Analysis of a Distributed Evaluator In Proc. International Conference on Parallel Processing, pages 299-310. August, 1980.
• 13: [13] R. M. Keller. FEL (Function Equation Language) Programmer's Guide. Technical Report 7, University of Utah, Department of Computer Science, AMPS Technical Memorandum, 1982.
• 14: [14] R. M. Keller, G. Lindstrom. E. Organick. Rediflow: A Multiprocessing Architecture Combining Reduction and Data-Flow. In PAW 83: Visuals used at the Parallel Architecture Workshop. Department of Energy, Office of Basic Energy Sciences, University of Colorado, Boulder, January, 1983.
• 15: [15] R. M. Keller, F. C. H. Lin. and J. Tanaka. Rediflow Multiprocessing. In IEEE Compcon '84, pages 410-417. Feb., 1984.
• 16: [16] G. Lindstrom and R. Wagner. Incremental Recomputation on Data-Flow Graphs. In Symposium on Functional Languages and Computer Archtecture. pages 472-489. Department of Computer Sciences, Chalmers University of Technology. Aspenas. Sweden, June, 1981.
• 17: [17] G. Lindstrom and F. E. Hunt Consistency and Currency In Functional Databases In Proc. Infocom 83, pages 352-361 IEEE. San Diego, April, 1983.
• 18: [18] G. Lindstrom and P. Panangaden. Stream-based execution of logic programs. In Proc. 1984 Int'l. Symp. on Logic Programming, pages 168-176. February, 1984.
• 19: [19] G. Lindstrom. OR-parallelism on applicative architectures. In Sten-Ake Tarnlund (editor), Proc. Second International Logic Programming Conference, pages 159-170. Uppsala University. July, 1984.
• 20: [20] U. S. Reddy. On the Relationship Between Functional and Logic Languages. In D. DeGroot and G. Lindstrom (editors). Logic and Functional Programming. Prentice Hall, 1985 To appear.
• 21: [21] J. A. Robinson and E. E. Sibert. Loglisp: an alternative to Prolog. In Hayes, Michie, and Pao (editors), Machine Intelligence. pages 399-419. Ellis Horwood, 1982.
• 22: [22] E. Y. Shapiro. A Subset of Concurrent Prolog and its Interpreter. Technical Report TR-003, Institute for New Generation Computer Technology, January. 1983.
• 23: Guy Lewis Steele, Jr. , Gerald Jay Sussman, Constraints, Proceedings of the international conference on APL: part 1, p.208-225, May 30-June 01, 1979, New York, New York, United States
• 24: [24] P. A. Subrahmanyam and J.-H. You. Conceptual Basis and Evaluation Strategies for Integrating Functional and Logical Programming. In D. DeGroot (editor), International Symposium on Logic Programming. IEEE, Atlantic City, N.J., February, 1984.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Design, Languages, Performance, Theory