Adventures in Prolog - General Reading (1)

Today's post is merely the advertisement of a dissertation thesis that might be an interesting read:

Can Logic Programming Execute as Fast as Imperative Programming?
Peter Lodewijk Van Roy

ABSTRACT
The purpose of this dissertation is to provide constructive proof that the logic programming language Prolog can be implemented an order of magnitude more efficiently than the best previous systems, so that its speed approaches imperative languages such as C for a significant class of problems. The driving force in the design is to encode each occurrence of a general feature of Prolog as simply as possible. The resulting system, Aquarius Prolog, is about five times faster than Quintus Prolog, a high performance commercial system, on a set of representative programs. The design is based on the following ideas:

• Reduce instruction granularity. Use an execution model, the Berkeley Abstract Machine (BAM), that retains the good features of the Warren Abstract Machine (WAM), a standard execution model for Prolog, but is more easily optimized and closer to a real machine.
• Exploit determinism. Compile deterministic programs with efficient conditional branches. Most predicates written by human programmers are deterministic, yet previous systems often compile them in an inefficient manner by simulating conditional branching with backtracking.
• Specialize unification. Compile unification to the simplest possible code. Unification is a general pattern-matching operation that can do many things in the implementation: pass parameters, assign values to variables, allocate memory, and do conditional branching.
• Dataflow analysis. Derive type information by global dataflow analysis to support these ideas.

The thesis can be found here.

On that note I would like to mention a paper going for a similar direction, actually I found the thesis because of the paper.

Optimizing Prolog for Small Devices: A Case Study
M. Carro, J. Morales, Henk L. Muller, G. Puebla, M. Hermenegildo

Abstract
In this paper we present the design and implementation of a wearable application in Prolog. The application program is a “sound spatializer.” Given an audio signal and real time data from a head-mounted compass, a signal is generated for stereo headphones that will appear to come from a position in space. We describe high-level and low-level optimizations and transformations that have been applied in order to fit this application on the wearable device. The end application operates comfortably in real-time on a wearable computer, and has a memory foot print that remains constant over time enabling it to run on continuous audio streams. Comparison with a version hand-written in C shows that the C version is no more than 20-40% faster; a small price to pay for a high level description.

The paper can be found here.

The reason why posting these documents, is my thinking of maybe porting or reusing an existing Prolog implementation for the Nintendo DS. Unfortunately, I have not made great progress. But with some time, there may be something out there.