On Warren's method for functional programming in logic
Miao Cheng, M. H. van Emden, Bradley Richards · 1990
Although Warren’s method for the evaluation in Prolog of expressions with higher-order functions appears to have been neglected, it is of great value. Warren’s paper needs to be supplemented in two respects. He showed examples of a translation from λ expressions to clauses, but did not present a general method. Here we present a general translation program and prove it correct with respect to the axioms of equality andthoseofthe λ-calculus. Warren’s paper only argues in general terms that a structuresharing Prolog implementation can be expected to efficiently evaluate the result of his translation. We show a comparison of timings between lisp and a structure-copying implementation of Prolog. The result suggests that Warren’s method is about as efficient as the Lisp method for the evaluation of λ expressions involving higher-order functions. 1