(The) design and implementation of a functional logic language with narrowing

Abstract

In this thesis, we propose AFLOG - a functional logic language, employing narrowing. With narrowing, AFLOG supports equality partially, without losing the efficiency. With this partial equality relation, most data types such as stack and queue can be easily expressed and as equational programming is allowed in AFLOG, the clarity and the understandability of a program are much improved. In implementing AFLOG with narrowing, two important mechanisms - the tree pattern matching and the backtracking mechanism in the reduction procedure are improved. In the tree pattern matching, the restriction called left-sequentiality is removed. In the backtracking mechanism of the reduction procedure, the structure sharing concept prevalently used in resolution procedure is employed and two different proof procedures - resolution and reduction are merged into the same mechanism.