Polymorphic Higher-Order Programming in Prolog

by Michael Hanus

Proc. of the Sixth International Conference on Logic Programming (ICLP'89), MIT Press, pp. 382-397, 1989

Pure logic programming lacks some features known from other modern programming languages, e.g., type systems for detection of particular programming errors at compile time and higher-order facilities for treating programs as data objects and writing more compact programs. On the one hand there are several proposals for polymorphic type systems for logic programming, and on the other hand Warren has shown that higher-order programming can be simulated in first-order logic. But the integration of these proposals fails because Warren's first-order programs are ill-typed in the sense of the polymorphic type systems. This paper presents a polymorphic type system for logic programming which allows the application of higher-order programming techniques. For Prolog-like applications of higher-order programming techniques it is possible to compute optimizations by abstract interpretation so that the polymorphic logic programs have the same operational efficiency as untyped Prolog programs.

DVI (63 KB) Postscript (185 KB) BibTeX-Entry