Towards a logic programming methodology based on higher-order predicates

被引:8
作者
Hamfelt, A [1 ]
Nilsson, JF [1 ]
机构
[1] TECH UNIV DENMARK, DEPT INFORMAT TECHNOL, DK-2800 LYNGBY, DENMARK
关键词
higher-order and metalogic programming; recursion schemes; composition; parameterization; and modularization of logic programs;
D O I
10.1007/BF03037300
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
This paper outlines a logic programming methodology which applies standardized logic program recursion forms afforded by a system of general purpose recursion schemes. The recursion schemes are conceived of as quasi higher-order predicates which accept predicate arguments, thereby representing parameterized program modules, This use of higher-order predicates is analogous to higher-order functionals in functional programming. However, these quasi higher-order predicates are handled by a metalogic programming technique within ordinary logic programming. Some of the proposed recursion operators are actualizations of mathematical induction principles (e.g. structural induction as generalization of primitive recursion). Others are heuristic schemes for commonly occurring recursive program forms. The intention is to handle all recursions in logic programs through the given repertoire of higher-order predicates, We carry out a pragmatic feasibility study of the proposed recursion operators with respect to the corpus of common textbook logic programs. This pragmatic investigation is accompanied with an analysis of the theoretical expressivity. The main theoretical results concerning computability are (1) Primitive recursive functions can be re-expressed in logic programming by predicates defined solely by non-recursive clauses augmented with a fold recursion predicate akin to the fold operators in functional programming. (2) General recursive functions can be re-expressed likewise since fold allows re-expression of a linrec recursion predicate facilitating linear, unbounded recursion.
引用
收藏
页码:421 / 447
页数:27
相关论文
共 26 条
  • [1] Andrews P, 1986, An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof
  • [2] [Anonymous], 1974, Computability and Logic
  • [3] CAN PROGRAMMING BE LIBERATED FROM VON NEUMANN STYLE - FUNCTIONAL STYLE AND ITS ALGEBRA OF PROGRAMS
    BACKUS, J
    [J]. COMMUNICATIONS OF THE ACM, 1978, 21 (08) : 613 - 641
  • [4] Bird R. S., 1989, Constructive Methods in Computing Science, P151
  • [5] BIRD RS, 1994, CLASSICAL MIND, P17
  • [6] HILOG - A FOUNDATION FOR HIGHER-ORDER LOGIC PROGRAMMING
    CHEN, WD
    KIFER, M
    WARREN, DS
    [J]. JOURNAL OF LOGIC PROGRAMMING, 1993, 15 (03): : 187 - 230
  • [7] FLENER P, 1993, CONSTRUCTING LOGIC P
  • [8] FLENER P, 1995, LOGIC PROGRAM SYNTHE
  • [9] GEGGHARRISON TS, 1995, P 12 INT C LOG PROGR, P467
  • [10] HAMFELT A, 1996, IN PRESS P JOINT INT