A Determinacy Testing Algorithm for Nondeterminate Flat Concurrent Logic Programming Languages

Loading...
Thumbnail Image

Date

1990-11

Authors

Tick, E.
Korsloot, M.

Journal Title

Journal ISSN

Volume Title

Publisher

University of Oregon

Abstract

This paper describes an algorithm for the code generation of determinacy testing for nondeterminate flat concurrent logic programming languages. Languages such as Andorra and Pandora require that procedure invocations suspend if there is more than one candidate clause potentially satisfying the goal. The algorithm described has been developed specifically for a variant of flat Pandora based on FGHC, although the concepts are general. We have extended Kliger and Shapiro's decision-graph construction algorithm to compile "don't know" procedures which must suspend for nondeterminate goal invocation. The determinacy test is compiled into a decision graph quite different from those of committed-choice procedures, but we argue that in most cases, the same low space complexity is retained.

Description

39 pages

Keywords

don't-know procedure, decision graph, node generation

Citation