×

Uniform proofs as a foundation for logic programming. (English) Zbl 0721.03037

Cut-free Gentzen-type systems for first and second order classical, intuitionistic and minimal logic are considered. A uniform proof is a derivation in which (viewed bottom-up) a succedent rule is applied whenever possible: if the succedent of a sequent S is non-atomic, then S is a conclusion of the succedent rule. If uniform proofs are complete for a class of sequents, then the proof-search for this class can be done in goal-directed manner by analysing non-atomic goals and expanding atomic goals using unification in a PROLOG-like manner. This justifies the definition of an abstract logic programming language as a triple \(<{\mathcal D},{\mathcal G}>\) such that uniform intuitionistic proofs are complete for the sequents \(X\to G\) with finite \(X\subset {\mathcal D}\) and G in \({\mathcal G}\). Four abstract logic programming languages are considered. First order Horn clauses \({\mathcal H}_ 1\) (with a definition equivalent to the familiar one up to equivalence), higher order Horn clauses \({\mathcal H}_ 2\), first and higher order hereditary Harrop formulas \({\mathcal D}_ 3\) and \({\mathcal D}_ 4\) (with suitable definitions of goals). \({\mathcal H}_ 1\), \({\mathcal H}_ 2\) are Glivenko classes (i.e. classical validity of \(X\to G\) in the corresponding language implies intuitionistic derivability), while \({\mathcal D}_ 3\), \({\mathcal D}_ 4\) are not. \({\mathcal H}_ 1\) is Herbrand universe for \({\mathcal H}_ 2\), and \({\mathcal H}_ 2\) is Herbrand universe for \({\mathcal D}_ 4\), i.e. it is sufficient to use the \(\lambda\)- abstraction of formulas in \({\mathcal H}_ 1\), \({\mathcal H}_ 2\) in substitutions for higher order quantifiers. A survey of implemented applications of this approach seems to show that they are more diverse than known applications of other systems based on automatic or interactive proofs in higher order intuitionistic logic.
Reviewer: G.Mints (Tallinn)

MSC:

03F05 Cut-elimination and normal-form theorems
68N17 Logic programming
03B35 Mechanization of proofs and logical operations

Software:

Hornlog
Full Text: DOI

References:

[1] Apt, K.; van Emden, M. H., Contributions to the theory of logic programming, J. Assoc. Comput. Mach., 29, 841-862 (1982) · Zbl 0483.68004
[2] Church, A., A formulation of the simple theory of types, J. Symbolic Logic, 5, 56-68 (1940) · JFM 66.1192.06
[3] Clark, K., Negation as failure, (Gallaire, H.; Minker, J., Logic and Databases (1978), Plenum: Plenum New York), 293-322
[4] Felty, A.; Miller, D., Specifying theorem provers in a higher-order logic programming language, Proc. Ninth Internat. Conference on Automated Deduction, 61-80 (1988), Argonne, IL · Zbl 0645.68097
[5] Fitting, M., Intuitionistic Logic, Model Theory and Forcing (1969), North-Holland: North-Holland Amsterdam · Zbl 0188.32003
[6] Fitting, M., A Kripke-Kleene semantics for logic programming, J. Logic Programming, 4, 295-312 (1985) · Zbl 0589.68011
[7] Gabbay, D. M.; Reyle, U., N-Prolog: an extension of Prolog with hypothetical implications. I, J. Logic Programming, 1, 319-355 (1984) · Zbl 0576.68001
[8] Gallier, J.; Raatz, S., Hornlog: a graph-based interpreter for general Horn clauses, J. Logic Programming, 4, 119-156 (1987) · Zbl 0641.68145
[9] Gentzen, G., Investigations into logical deductions, (Szabo, M. E., The Collected Papers of Gerhard Gentzen (1969), North-Holland: North-Holland Amsterdam), 68-131 · Zbl 0209.30001
[10] Hannan, J.; Miller, D., Uses of higher-order unification for implementing program transformers, (Brown, K.; Kowalski, R., Proc. Fifth Internat. Conference and Symposium on Logic Programming (1988), MIT Press: MIT Press Cambridge, MA)
[11] Harrop, R., Concerning formulas of the types \(A→B ∨ C, A →( Ex )B(x)\) in intuitionistic formal systems, J. Symbolic Logic, 25, 27-32 (1960) · Zbl 0098.24201
[12] Huet, G., A unification algorithm for typed λ-calculus, Theoret. Comput. Sci., 1, 27-57 (1975) · Zbl 0337.68027
[13] Huet, G.; Lang, B., Proving and applying program transformations expressed with second-order patterns, Acta Inform., 11, 31-55 (1978) · Zbl 0389.68008
[14] Miller, D., Hereditary Harrop formulas and logic programming, Proc. VIII Internat. Congress of Logic, Methodology, and Philosophy of Science (1987), Moscow
[15] Miller, D., A logical analysis of modules in logic programming, J. Logic Programming, 6, 79-108 (1989) · Zbl 0681.68022
[16] Miller, D., Solutions to λ-terms equations under a mixed prefix (1989), submitted
[17] Miller, D., Lexical scoping as universal quantification, Proc. Sixth Internat. Conference on Logic Programming (1989), Lisbon, Portugal
[18] Miller, D.; Nadathur, G., Some uses of higher-order logic in computational linguistics, Proc. 24th Annual Meeting of the Association for Computational Linguistics, 247-255 (1986)
[19] Miller, D.; Nadathur, G., Higher-order logic programming, Proc. Third Internat. Logic Programming Conference, 448-462 (1986), London · Zbl 0611.68057
[20] Miller, D.; Nadathur, G., A logic programming approach to manipulating formulas and programs, Proc. 1987 Symposium on Logic Programming, 379-388 (1987), San Francisco, CA
[21] Miller, D.; Nadathur, G.; Scedrov, A., Hereditary Harrop formulas and uniform proofs systems, Proc. Second Annual Symposium on Logic in Computer Science, 98-105 (1987), Ithaca, NY
[22] Nadathur, G., A higher-order logic as the basis for logic programming, Ph.D. Dissertation (1987), Univ. Pennsylvania
[23] Nadathur, G.; Miller, D., An overview of λProlog, Proc. Fifth Internat. Logic Programming Conference, 810-827 (1988), Seattle
[24] G. Nadathur and D. Miller, Higher-order Horn clauses, J. Assoc. Comput. Mach., submitted.; G. Nadathur and D. Miller, Higher-order Horn clauses, J. Assoc. Comput. Mach., submitted. · Zbl 0711.68091
[25] Paulson, L., Natural deduction as higher-order resolution, J. Logic Programming, 3, 237-258 (1986) · Zbl 0613.68035
[26] Pfenning, F., Partial polymorphic type inference and higher-order unification, Proc. 1988 ACM Conference on Lisp and Functional Programming, 153-163 (1988), Snowbird, UT
[27] Pfenning, F.; Elliott, C., Higher-order abstract syntax, Proc. SIGPLAN ’88 Symposium on Language Design and Implementation, 199-208 (1988), Atlanta, GA
[28] Prawitz, D., Natural Deduction (1965), Almqvist & Wiksell: Almqvist & Wiksell Uppsala · Zbl 0173.00205
[29] Sterling, L.; Shapiro, E., The Art of Prolog: Advanced Programming Techniques (1986), MIT Press · Zbl 0605.68002
[30] Troelstra, A., Metamathematical Investigation of Intuitionistic Arithmetic and Analysis, Lecture Notes in Math., 344 (1973), Springer: Springer New York · Zbl 0275.02025
[31] Emden, M. van, First-order predicate logic as a common basis for relational and functional programming, Proc. Second Annual Symposium on Logic in Computer Science, 179 (1987), Ithaca, NY
[32] Emden, M. van; Kowalski, R., The semantics of predicate logic as a programming language, J. Assoc. Comput. Mach., 23, 733-742 (1976) · Zbl 0339.68004
[33] Warren, D. H.D., Higher-order extensions to Prolog: are they needed?, (Hayes, J. E.; Michie, D.; Pao, Y-H., Mach. Intell., 10 (1982), Halsted Press: Halsted Press New York), 441-454
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.