Strict And Non-Strict Independent And-Parallelism In Logic Programs: Correctness, Efficiency, And Compile-Time Conditions

Machine (WAM) [33]. &- Prolog, the source language in this model, is basically Prolog, with the addition of the parallel conjunction operator "&" and a set of parallelism-related builtins, which includes several types of groundness and independence checks, and synchronization primitives. Parallel conditional execution graphs (which cause the execution of goals in parallel if certain conditions are met) can be constructed by combining these elements with the normal Prolog constructs, such as "-?" (if-then-else). For syntactic convenience (and historical reasons) an additional construct, the CGE, is also provided. We now study the correctness of CGEs. Definition 8. (CGE) A CGE (Conditional Graph Expression) is a structure of the form ( i cond =? goal 1 & goal 2 & ... & goal n ) where i cond is an independence condition as defined previously, and each goal i , i = 1; : : : ; n, is either a literal or (recursively) a CGE. CGEs appear as literals in the bodies of clauses. From an operat..