Nondeterminism and unification in LogScheme: integrating logic and functional programming
Erik Ruf, Daniel Weise · 1989
LogScheme is an experiment in adding the main features of logic programming, nondeterminism and unification, into the (mostly) functional language Scheme.We use a minimaliit approach, based on the observation that nondeterminism and unification are separable both in concept and in implementation.LogScheme adds only two new primitive functions and one new special form to Scheme.Using these primitives, we can write programs in the style of Scheme, Icon, Prolog, or any mixture thereof.We have found that a style of programming that uses both logical and functional techniques can be more powerful than the use of either technique alone.Nondeterminism:How is it implemented?Is it implicit or explicit?How much control does the user have over backtracking choices?Can we come up with a good functional representation for choice points?Logic Variables: How are they represented and how are they bound to values?Are they syntactically different from ordinary parameter values?Is unification implicit or explicit?How are logic variable scopes controlled?Functions versus Relations:Are functions and relations different?Can relations have functional properties like return values?Can functions and relations be made to act the same?Truth and Falsity: Are explicit truth values (like tt and #f) retained, or is truth implicit in the notions of "success" and "failure"?Are both ways possible?Side Effects: Are they allowed?Why or why not?If they are, are they persistent across backtracking?Are there cases where side effects are desirable or necessary?Continuations:How do first-class continuations interact with the logic variable mechanism?Is it necessary for them to encapsulate logic variable bindings?Should the continuations used for backtracking be treated differently from those used for other control purposes?This paper has four sections.It first covers nondeterminiem, giving a formal semantics, an implementation, and examples.Section 2 describes logic variables and unification in a similar manner.The third section shows that Scheme plus nondeterminism and unification is greater than either Scheme or Prolog.The last section discusses how LogScheme might be extended or compiled.1 Nondeterminism 1.1