Logic programming with functions and predicates: The language BABEL.

*(English)*Zbl 0754.68031Summary: We investigate the experimental programming language BABEL, designed to achieve integration of functional programming (as embodied in HOPE, Standard, ML, or MIRANDA) and logic programming (as embodied in PROLOG) in a simple, flexible, and mathematically well-bounded way. The language relies on a constructor discipline, well suited to accommodate PROLOG terms and HOPE-like patterns. From the syntactical point of view, BABEL combines pure PROLOG with a first order functional notation. On the other side, the language uses narrowing as the basis of a lazy reduction semantics which embodies both rewriting and SLD resolution and supports computation with potentially infinite data structures. There is also a declarative semantics, based on Scott domains, which provides a notion of least Herbrand model for BABEL programs. We develop both semantics and prove the existence of least Herbrand models, as well as a soundness result for the reduction semantics w.r.t. the declarative one. We also sketch a completeness result for the reduction semantics and illustrate the features of the language through some programming examples.

##### MSC:

68N17 | Logic programming |

68N15 | Theory of programming languages |

68Q55 | Semantics in the theory of computing |