zbMATH — the first resource for mathematics

Logic and functional programming by retractions. (English) Zbl 0666.68011
A special class of set functions called retractions is used as a link between logic and functional programming. This class of functions is treated by set-theoretic means that reflects the structure of the Herbrand universe in clausal logic. By this way, it is possible to interpret Herbrand terms by a specal type of symbolic data, namely, by constant combinatory expressions.
Derivations on expressions of clausal logic containing logical variables, e.g., narrowing are reformulated as manipulations with combinatory expressions. In this approach, predicates are represented as retractions. The latter allow to combine logic and functional programming in a pure functional programming context. Predicates and functions are represented by the same type of objects.
Reviewer: P.Ŝtêpánek

68N01 General topics in the theory of software
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
03B40 Combinatory logic and lambda calculus
Zbl 0666.68012
Full Text: DOI EuDML
[1] H. ABRAMSON, A Prological Definition of HASL, a Purely Functional Language with Unification Based Conditional Binding Expressions, New Generation Computing, Vol. 2, 1984, pp. 3-35.
[2] J. BACKUS, Can Programming be Liberated from the von Neumann Style?C. ACM, Vol. 21, 1978, pp, 613-641 Zbl0383.68013 MR520392 · Zbl 0383.68013
[3] H. P. BARENDREGT, The LAMBDA Calculus. Its Syntax and Semantics. North-Holland, 1984. Zbl0551.03007 MR774952 · Zbl 0551.03007
[4] R. BARBUTI, M. BELLIA, G. LEVI and M. MARTELLI, LEAF : A Language which Integrates Logic, Equations and Functions, Relations and Equations, D. DEGROOT and G. LINDSTROM, Eds. Prentice-Hall, 1985.
[5] M. BELLIA, G. LEVI and M. MARTELLI, On Compiling Prolog Programs on Demand Driven Architectures, Proc. Logic Programming Workshop’83, 1983, pp. 518-535.
[6] M. BELLA, E. DAMERI, P. DEGANO, G. LEVI and M. MARTELLI, A Formal Model for Lazy Implementation of a PROLOG Compatible Functional Language. In Implementations of PROLOG, J. A. CAMPBELL, Ed. Ellis Horwood, 1984, pp. 309-326.
[7] M. BELLIA and G. LEVI, The Relation Between Logic and Functional Languages : A Survey. J. Logic Programming, 3, 1986, pp. 217-236. Zbl0599.68014 · Zbl 0599.68014
[8] M. BELLIA, Retractions : A Functional Paradigm for Logic Programming. Proc. TAPSOFT’87, LNCS, 250, Springer-Verlag, 1987,pp. 260-275. Zbl0636.68012 MR900620 · Zbl 0636.68012
[9] M. BELLIA, Logic and Functional Programming by Retractions : Operational Semantics.To appear in RAIRO Informatique Théorique et Applications. Zbl0666.68012 MR984584 · Zbl 0666.68012
[10] K. BERKLING, Reduction Languages for Reduction Machines. Proc. 2nd Int. Symp. on Computer Architectures, IEEE Comp. Society Press, 1975, pp. 133-140.
[11] K. BERKLING, J. A. ROBINSON and E. E. SIBERT, A Proposal for a Fifth Generation Logic and Functional Programming System,Based on Highly Parallel Reduction Machine Architecture, Syracuse University, November 1982.
[12] K. A. BOWEN and R. A. KOWALSKI, Amalgamating Language and Metalanguage in Logic Programming. In Logic Programming, K. L. CLARK and S. -A. TARNLUND, Eds., Academic Press, 1982, pp. 153-172.
[13] K. A. BOWEN and T. WEINBERG, A Meta-level Extension of Prolog, Proc. 1985Symp. on Logic Programming IEEE Comp. Society Press 1985, pp. 48-53.
[14] L. BYRD, Understanding the Control Flow of Prolog Programs, First Work-shop on Logic Programming, 1980pp. 127-138.
[15] M. VAN CANEGHEM and D. H. D. WARREN (Eds.), Logic Programming and its Applications, Ablex Pub. Comp., 1984.
[16] K. L. CLARK, F. G. MCCABE and S. GREGORY, IC-Prolog : Language Features. In Logic Programming, K. L. CLARK and S.-A. TARNLUND, Eds., Academic Press, 1982, pp. 254-266.
[17] K. L. CLARK and S. GREGORY, PARLOG : a Parallel Logic Programming Language, Imperial College Research Report 83/5, May 1983. · Zbl 0592.68016
[18] T. J. W. CLARKE, P. J. S. GLADSTONE, C. D. MACLEAN and A. C. NORMAL, SKIM-The S. K. I. reduction machine, Proc. Lisp 80 Conf., 1980, pp. 128-135.
[19] J. DARLINGTON and M. REEVE, ALICE : A Multiprocessor Reduction Machine for the Parallel Evaluation of Applicative Languages. Proc. Int. Symp. Functional Programming Languages and Computer Architectures, 1981, pp. 32-62.
[20] J. DARLINGTON, A. J. FIELD and H. PULL, The Unification of Functional and Logic Languages, In Logic Programming: Functions, Relations and Equations, D. DEGROOT and G. LINDSTROM Eds. Prentice-Hall, 1985.
[21] N. DERSHOWITZ and N. A. JOSEPHSON, Logic Programming by Comple-tion, Proc. 2nd Int. Logic Programming Conf., 1984, pp. 313-320.
[22] N. DERSHOWITZ and D. A. PLAISTED, Logic Programming Cum Applicative Programming, Proc. 1985Symp. on Logic Programming, IEEE Comp. Society Press, 1985, pp. 54-66.
[23] L. FRIBOURG, SLOG : A Logic Programming Language Interpreter Based on Clausal Superposition and Rewriting. Proc. 1985Symp. on Logic Programming, IEEE Comp. Society Press, 1985, pp. 172-184.
[24] H. GALLAIRE and C. LASSERRE, A control Metalanguage for Logic ProgrammingIn Logic Programming, K. L. CLARK and S.-A. TARNLUND Eds., Academic Press, 1982, pp. 173-185.
[25] J. A. GOGUEN and J. MESEGUER, Equality, types, modules and (why not?) generics for logic programming, J. Logic Programming, Vol. 1, 1984, pp. 179-210. Zbl0575.68091 MR759845 · Zbl 0575.68091
[26] C. L. HANKIN, P. E. OSMAN and M. J. SHUTE, COBWEB - A Combinator Reduction Architecture, Proc. Functional Programming Languages and Computer Architecture, LNCS, Vol. 201, Springer-Verlag, 1985, pp. 89-102.
[27] J. HSIANG and N. DERSHOWITZ, Rewrite Methods for Clausal and Non-clausal Theorem Proving, Proc 10th ICALP, 1983. Zbl0523.68080 · Zbl 0523.68080
[28] K. M. KAHN, Uniform : A Language Based Upon Unification which Unifies Much of Lisp, Prolog and Actl, Proc, 7th IJCAI, 1981.
[29] W. E. KLUGE and H. SCHLUTTER, An Architecture for the Direct Execution of Reduction Languages, Proc: Int. Workshop High Level Computer architecture, 1980.
[30] R. A. KOWALSKI and D. KUEHNER, Linear resolution with selection function, Artificial Intelligence, Vol. 2, 1971, pp. 227-260. Zbl0234.68037 MR436677 · Zbl 0234.68037
[31] R. A. KOWALSKI, Predicate Logic as a Programming Language, Proc. Kowalski74] R. IFIP Congress, 1974, 569-574. Zbl0297.68006 MR428765 · Zbl 0297.68006
[32] R. A. KOWALSKI, Algorithms = Logic + Control., C. ACM, Vol. 22, 1979, pp. 424-436. Zbl0404.68010 · Zbl 0404.68010
[33] H. J. KOMOROWSKI, QLOG - The Programming Environment for Prolog in Lisp. In Logic Programming, K. L. CLARK and S.-A. TARNLUND Eds., Academie Press 1982, pp. 315-322.
[34] W. A. KORNFELD, Equality for PROLOG, Proc. 8th IJCAI, 1983, pp.514-519.
[35] G. LINDSTROM, Functional Programming and the Logical Variable, Proc. 12th ACM Symp. on Principles of Programming Languages, 1985.
[36] J. W. LLOYD, Foundations of Logic Programming, Springer-Verlag, 1984. Zbl0547.68005 MR766562 · Zbl 0547.68005
[37] G. A. MAGO, A Cellular Computer Architecture for Functional Programming, Proc. IEEE-COMPCON 80, IEEE Comp. Society Press, 1980, pp. 179-187.
[38] J. MCCARTHY, Recursive Functions and Symbolic Expressions and Their Computation by Machine, C. ACM, Vol. 3, 1960, pp. 184-195. Zbl0101.10413 · Zbl 0101.10413
[39] C. MELLISH and S. HARDY, Integrating PROLOG in the POPLOG Environment. In Implementations of PROLOG, J. A. CAMPBELL Ed., Ellis Horwood, 1984, pp. 147-162.
[40] R. MILNER, Implementation and Application of Scotts Logic for Computable Function, Sigplan Notices, Vol. 7 1972, pp. 1-6.
[41] T. MOTO-OKA, Ed., Fifth Generation Computer Systems, North-Holland, 1982. Zbl0484.68002 · Zbl 0484.68002
[42] L. M. PEREIRA, Logic Control with Logic. In Implementations of PROLOG, J. A. CAMPBELL Ed., Ellis Horwood, 1984, pp.177-193.
[43] U. S. REDDY, On the Relationship Between Logic and Functional Languages. In Logic Programming: Functions, Relations and Equations, D. DEGROOT and G. LINDSTROM Eds, Prentice-Hall, 1985.
[44] P. RETY, C. KIRCHNER, H. KIRCHNER and P. LESCANNE, NARROWER : A New Algorithm for Unification and its Application to Logic Programming, Proc. First Int. Conf. on Rewriting Techniques and Applications, 1985. Zbl0576.68002 · Zbl 0576.68002
[45] J. A. ROBINSON, A Machine-oriented Logic Based on the Resolution Principle, J. ACM, Vol. 12, 1965, pp. 23-44. Zbl0139.12303 MR170494 · Zbl 0139.12303
[46] J. A. ROBINSON and E. E. SIBERT, LOGLISP : Motivations, Design and Implementation. In Logic Programming, K. L. CLARK and S.-A. TARNLUND Eds., Academie Press, 1982, pp. 299-314. MR1628816
[47] J. A. ROBINSON and E. E. SIBERT, LOGLISP : An Alternative to PROLOG, Machine Intelligence, Vol. 10, Ellis Horwood, 1982.
[48] J. A. ROBINSON, Logic Programming : Past, Present and Future, New Generation Computing, Vol. 2, 1983, pp. 107-124.
[49] M. SATO and T. SAKURAI, Qute : a Functional Language Based on Unification, Proc. FGCS’84, 1984, pp.157-165.
[50] D. SCOTT, Data Types as Lattices, SIAM J. on Computing, Vol. 5, 1976, pp. 522-587. Zbl0337.02018 MR437330 · Zbl 0337.02018
[51] SHAPIRO, E. and L. TERLING, The Art of Prolog, MIT Press, 1986. Zbl0605.68002 · Zbl 0605.68002
[52] J. E. STOY, Denotational Semantics. The Scott-Strachey Approach to Programming Languages, MIT Press, Cambridge, 1977. Zbl0503.68059 MR488969 · Zbl 0503.68059
[53] J. T. SHWARTZ, Automatic Data Structure Choise in a Language of Very High Level, C. ACM, Vol. 18, 1975, pp. 772-728. Zbl0316.68012 · Zbl 0316.68012
[54] A. SRIVASTAVA, D. OXLEY and A. SRIVASTAVA, An(other) Integration of Logic and Functional Programming, Proc. 1985 Symp. on Logic Programming, IEEE Comp. Society Press, 1985, pp. 254-260.
[55] P. A. SUBRAHMANYAM and J.-H. You, FUNLOG = -Functions 4-Logic: A Computational Model Integrating Functional and Logic Programming, Proc. 1984, Int.Symp. on Logic Programming, IEEE Comp. Society Press, 1984, pp.144-153.
[56] D. A. TURNER, SASL Language Manual, Dept. of Computational Science, Univ. of St. Andrews, 1979.
[57] D. H. D. WARREN, Higher-order Extensions to PROLOG : are they Needed? Machine Intelligence, Vol. 10, 1982, pp. 441-454.
[58] H. YASUURA, On Parallel Computational Complexity of Unification, Proc. FGCS’84, 1984, pp. 235-243.
[59] T. YOKOMORI, A Note on the Set Abstraction in Logic Programming Language, Proc. FGCS’ 84, 1984, pp.333-340.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.