Skip to main content
Top

1997 | Book

Clause and Effect

Prolog Programming for the Working Programmer

Author: Dr. William F. Clocksin

Publisher: Springer Berlin Heidelberg

insite
SEARCH

About this book

This book is for people who have done some programming, either in Prolog or in a language other than Prolog, and who can find their way around a reference manual. The emphasis of this book is on a simplified and disciplined methodology for discerning the mathematical structures related to a problem, and then turning these structures into Prolog programs. This book is therefore not concerned about the particular features of the language nor about Prolog programming skills or techniques in general. A relatively pure subset of Prolog is used, which includes the 'cut', but no input/output, no assert/retract, no syntactic extensions such as if­ then-else and grammar rules, and hardly any built-in predicates apart from arithmetic operations. I trust that practitioners of Prolog program­ ming who have a particular interest in the finer details of syntactic style and language features will understand my purposes in not discussing these matters. The presentation, which I believe is novel for a Prolog programming text, is in terms of an outline of basic concepts interleaved with worksheets. The idea is that worksheets are rather like musical exercises. Carefully graduated in scope, each worksheet introduces only a limited number of new ideas, and gives some guidance for practising them. The principles introduced in the worksheets are then applied to extended examples in the form of case studies.

Table of Contents

Frontmatter
Chapter One. Getting Started
Abstract
Prolog is the most widely used programming language to have been inspired by logic programming research. There are a number of reasons for the popularity of Prolog as a programming language:
  • Powerful symbol manipulation facilities, including unification with logical variables. Programmers can consider logical variables as names ‘holes’ in data structures. Unification also serves as the parameter passing mechanism, and provides a constructor and selector of data structures. When combined with recursive procedures and a surface syntax for data structures, the simple manipulation possibilities of Prolog surpass those of other languages.
  • Automatic backtracking provides generate-and-test as the basic control flow model. This is more general than the strict unidirectional sequential flow of control in conventional languages. Although generate-and-test is not appropriate for some applications, other control flow models can be programmed to correspond to the demands of a particular application.
  • Program clauses and data structures have the same form. This gives a unified model for representing data as programs and programs as data. Other languages such as Lisp also have this features.
William F. Clocksin
Chapter Two. Data Structures
Abstract
So far the only programs we have looked at are those using constants and variables. Now we shall turn to structured data. As we saw before, structured data is represented by compound terms. One useful elementary data structure is the list. A list is an arbitrarily long finite sequence of terms called elements of the list. Prolog has a source syntax for lists, in which the elements of the list are separated by commas and enclosed in square brackets.
William F. Clocksin
Chapter Three. Mapping
Abstract
In the previous chapters we have been concerned with valuations. If we consider a goal as an implementation of a box to which we give an input and obtain an output, valuations are kinds of goals (or boxes) that give a point value.
William F. Clocksin
Chapter Four. Choice and Commitment
Abstract
Prolog makes available a special built-in predicate spelled ‘!’, and pronounced ‘cut’. The purpose of this predicate is to give control over the backtracking control flow of the executing program. When called, the cut always succeeds, but has the side-effect of removing any alternative choices in effect at the time. It follows that if ‘cut’ is called when there is only one possible solution, then the ‘cut’ has no effect.
William F. Clocksin
Chapter Five. Difference Structures
Abstract
The difference structure is a powerful data representation technique unique to Prolog. Difference structures simplify and increase the efficiency of programs by permitting ‘partial’ or ‘incomplete’ data structures to be specified and built up incrementally as the program executes. Variables are used as named ‘holes’ that can stand for parts of the data structure that are not yet computed. Difference structures are a generalisation of the idea of an accumulator. Where we have used accumulators to represent the ‘result so far’ during a computation, it is also possible for the idea of the accumulator to be extended to arbitrary data structures.
William F. Clocksin
Chapter Six. Case Study: Term Rewriting
Abstract
In this case study we shall look at various applications of term rewriting: symbolic differentiation, algebraic matrix products, and simplification. Most of the ideas illustrated in this case study will be used in subsequent case studies.
William F. Clocksin
Chapter Seven. Case Study: Manipulation of Combinational Circuits
Abstract
One popular use of logic in computer science is the representation of boolean logic circuits, named after British mathematician George Boole (1815–1864). This case study will show one way in which Prolog can be used for the representation and manipulation of boolean logic circuits. We shall confine ourselves to combinational circuits (stateless logic functions). These are sometimes called ‘combinatorial’ circuits, but I prefer the term combinational partly because these circuits are combinations of boolean functions, and partly to distinguish the term combinatorial by its use in describing the complexity of algorithms.
William F. Clocksin
Chapter Eight. Case Study: Manipulation of Clocked Sequential Circuits
Abstract
A previous case study showed how Prolog can be used for direct simulation of combinational circuits. We now turn to the problem of clocked sequential circuits. There are two issues to define first. It is only possible to model sequential circuit components because we are willing to make some assumptions about (a) their internal state and (b) their timing delays. We shall use a very simple model in which each component will be responsible for representing its own internal state, and all delays will be of unit duration. Every component will be synchronised by the same clock. The clock can be represented simply as a list of pulses, for example the list [1, 1, 1, 1, 1] shows five pulses of the clock signal.
William F. Clocksin
Chapter Nine. Case Study: A Compiler for Three Model Computers
Abstract
The purpose of a compiler is to translate a program in the source language to a program in a target language. Usually the source program is written in a high-level programming language, and the target program is an assembly listing for a particular computer. Because compilation is often considered as a recursive task that transforms one data structure into another, compilation is a natural application for Prolog. Most Prolog compilers and interpreters are written in Prolog.
William F. Clocksin
Chapter Ten. Case Study: The Fast Fourier Transform in Prolog
Abstract
It is not widely appreciated that Prolog has a role to play in the development of numerical methods. As an example of an unexpected but satisfying application of Prolog, this case study will demonstrate how Prolog can be used to derive a formulation of the Fast Fourier Transform.
William F. Clocksin
Chapter Eleven. Case Study: Higher-Order Functional Programming
Abstract
Higher-order programming permits greater reuse of code and encourages the use of abstractions. This case study illustrates higher-order functional programming techniques in Prolog, and introduces new improvements to methods known to logic programmers for more than a decade. These are illustrated by defining an evaluator, written in Prolog, for higher-order functional programs.
William F. Clocksin
Backmatter
Metadata
Title
Clause and Effect
Author
Dr. William F. Clocksin
Copyright Year
1997
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-58274-5
Print ISBN
978-3-540-62971-9
DOI
https://doi.org/10.1007/978-3-642-58274-5