SCOPING CONSTRUCTS IN LOGIC PROGRAMMING - IMPLEMENTATION PROBLEMS ANDTHEIR SOLUTION

The inclusion of universal quantification and a form of implication in goals in logic programming is considered. These additions provide a l ogical basis for scoping, but they also raise new implementation probl ems. When universal and existential quantifiers are permitted to appea r in mixed order in goals, the devices of logic variables and unificat ion that are employed in solving existential goals must be modified to ensure that constraints arising out of the order of quantification ar e respected. Suitable modifications that are based on attaching numeri cal tags to constants and variables and on using these tags in unifica tion are described. The resulting devices are amenable to an efficient implementation and can, in fact, be assimilated easily into the usual machinery of the Warren Abstract Machine (WAM). The provision of impl ications in goals results in the possibility of program clauses being added to the program for the purpose of solving specific subgoals. A n aive scheme based on asserting and retracting program clauses does not suffice for implementing such additions for two reasons. First, it is necessary to also support the resurrection of an earlier existing pro gram in the face of backtracking. Second, the possibility for implicat ion goals to be surrounded by quantifiers requires a consideration of the parameterization of program clauses by bindings for their free var iables. Devices for supporting these additional requirements are descr ibed as also is the integration of these devices into the WAM. Further extensions to the machine are outlined for handling higher-order addi tions to the language. The ideas presented here are relevant to the im plementation of the higher-order logic programming language lambda Pro log.