Higher-order Lazy Narrowing Calculi in Perspective.
Mircea Marin, Tetsuo Ida, Taro Suzuki · 2000
Higher-order lazy narrowing (HOLN for short) is a computational model for higher-order functional logic programming. It can be viewed as an extension of first-order lazy narrowing with inference rules to solve equations involving lambda-abstractions and higher-order variables. A common feature of the HOLN calculi proposed so far is the high nondeterminism between the inference rules designed to solve equations which involve higher-order variables. In this paper we present various refinements of HOLN towards more deterministic versions. The refinements are defined for classes of higher-order functional logic programs which are useful for programming purposes. Our work draws on two sources: the calculus LN for pattern rewrite systems [Pre98] and the first-order lazy narrowing calculus LNC and its deterministic refinements [MO98].