Initial experiments with a graph reduction model for nondeterministic program control indicate that this is a viable and natural approach. Appropriate reduction rules for and and or combinators together with a new type of tagged node (alt nodes) enable the straightforward compilation of declarative language statements to graph sections whose reduction by simple rewrite rules will effect backtracking. Other graph reduction approaches to logic languages place this burden on the metalanguage. The matching of an operational graph reduction model with a denotational semantics for the declarative language B provides an elegant framework for extension to full logic programming and the future incorporation of more advanced control structures. Although the current model abstracts the complexities of state by making explicit a state argument, there are appropriate alternative strategies that can be employed in the extension. Other investigators are currently producing graph reduction models incorporating appropriate behavior for logic variables, which will be considered in our extension. The main objective is to develop the current model to correctly and efficiently model sophisticated control for declarative languages. Investigation of methods to superimpose Prolog's cut is already underway. The model will seek ways to incorporate the necessary control information into the graph. The success of simple alt nodes in modeling nondeterminism is an encouraging start.
