Encapsulated Search for

Higher-order Concurrent

Constraint Programming1

Christian Schulte and Gert Smolka
German Research Center for Artificial Intelligence (DFKI) Stuhlsatzenhausweg 3, D{66123 Saarbrucken, Germany
fschulte,smolkag@dfki.uni-sb.de

Abstract

The paper presents an extension of the concurrent constraint model providing for higher-order programming, deep guards, and encapsulated search. The paper focuses on a higher-order combinator providing for encapsulated search. The search combinator spawns a local computation space and resolves remaining choices by returning the alternatives as first-class citizens. The search combinator allows to program different search strategies, including depth-first, indeterministic one solution, demand-driven multiple solution, all solutions, and best solution (branch and bound) search. The described computation model is realized in Oz, a programming language and system under development at DFKI.

Keywords Concurrent constraint programming, higher-order programming, encapsulated search, search strategies, Oz.

1 Introduction

Oz [2, 3, 9, 8, 7, 1] is an attempt to create a high-level concurrent programming language providing the problem solving capabilities of logic programming (i.e., constraints and search). Its computation model can be seen as a rather radical extension of the concurrent constraint model [6] providing for higher-order programming, deep guards, state, and encapsulated search. This paper focuses on the most recent extension, a higher-order combinator providing for encapsulated search. The search combinator spawns a local computation space and resolves remaining choices by returning the alternatives as first-class citizens. The search combinator allows to program different search strategies, including depth-first, indeterministic one solution, demand-driven multiple solution, all solutions, and best solution (branch and bound) search.
The idea behind our search combinator is simple and new. It exploits

1Appears in: Logic Programming: Proceedings of the 1994 International Symposium, pages 505{520, edited by Maurice Bruynooghe, 13{17 November, 1994, Ithaca, New York, USA. The MIT-Press.