A technique for doing lazy evaluation in logic

AbstractWe develop a natural technique for defining functions in logic, i.e. PROLOG, which directly yields lazy evaluation. Its use does not require any change to the PROLOG interpreter. Function definitions run as PROLOG programs and so run very efficiently. It is possible to combine lazy evaluation with nondeterminism and simulate coroutining. It is also possible to handle infinite data structures and implement networks of communicating processes. We analyze this technique and develop a precise definition of lazy evaluation for lists. For further efficiency we show how to preprocess programs and ensure, using logical variables, that values of expressions once generated are remembered for future access. Finally, we show how to translate programs in a simple functional language into programs using this technique