A Determinacy Testing Algorithm for Nondeterminate Flat Concurrent Logic Programming Languages
Loading...
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