Efficient Execution of HiLog in WAM-based Prolog implementations

Click on the title to obtain a gzip-ed PostScript version of the paper (67K).

Abstract:

In this paper we address the problem of efficiently implementing HiLog, a logic programming language with higher-order syntax and first-order semantics. In contrast to approaches proposed in the literature that modify, or abandon the WAM framework in order to implement HiLog, our approach to the problem stems from a belief that the WAM should be an adequate abstract machine for the execution of any logic language with first-order semantics. To show how to implement HiLog by staying within the WAM framework, we identify the reasons for poor performance characteristics of HiLog programs, present requirements for efficient HiLog execution, and propose a complete solution to the problem.

Our proposal, which can be viewed either as a compile-time program specialisation preprocessing step, or as an enhancement to the HiLog encoding in predicate calculus presented by Chen, Kifer, and Warren, allows HiLog to be efficiently implemented on any Prolog system by simply modifying Prolog's input/output predicates to handle terms that are expressed using the flexible higher-order syntax of HiLog.

We formally prove that our proposal allows all HiLog programs that do not use any higher-order features to execute at the same speed as Prolog programs. Furthermore, we present performance results showing that generic HiLog predicates when compiled using the compilation scheme execute at least an order of magnitude faster than generic Prolog predicates, and with only minimal overhead compared to non-generic Prolog ones.