SWI Prolog documentation mentions "closures" - but these are not the "closures" you are looking for

Good day.

I have been wondering for some time about whether to bring this up, but in the end I decided that yes, it may be worth it.

In the SWI Prolog manual, we find the page for library “yall” (which stands for “Yet Another Lambda Library”).

The library provides a very interesting capability, namely to write anonymous wrappers around predicate calls. The library implements Logtalk’s “lambda expressions” syntax. Indeed, it has been authored by Paulo Moura, Logtalk designer/developer, and Jan Wielemaker, SWI-Prolog maintainer. See also: Logtalk Lambda Expression.

Well, I am a bit bothered by the terminology.

The yall library documentation says:

Prolog realizes high-order programming with meta-calling. The core predicate of this is call/1, which simply calls its argument. This can be used to define higher-order predicates such as ignore/1 or forall/2. The call/N construct calls a closure with N-1 additional arguments. This is used to define higher-order predicates such as the maplist/N family or foldl/N.

The Logtalk glossary defines “closure” in this way:

A callable term (i.e. an atom or a compound term) passed to a meta-predicate call where it is extended with additional arguments to form a goal called by the meta-predicate.

I really feel that “closure” is used inappropriately here.

The above does not describe a closure but a bunch of parameters for an indirect call:

  • A tuple
    • with the name of the predicate to call and
    • the arguments to be used for the call.

This is similar to a Java “method call by reflection” (say), only a lot less horrible and with logical variables (which are really references to shared, versioned tree structures, what I like to call “blackboards”).

The term “closure” is also used in several other places in the SWI Prolog documentation, apparently as a synonym for “goal” (which is of course a term proper to logic programming, unlike “closure”). When you search for closure, you get a few hits. (But you don’t get library yall or a few other pages that one would expect. Is there a problem in indexing?) For example:

  • prolog_unlisten/2: Remove matching closures registered with prolog_listen/3.
  • prolog_listen/2: Call Closure if an event that matches Channel happens inside Prolog.
  • prolog_listen/3: Call Closure if an event that matches Channel happens inside Prolog.

The above are not closures either. They are goals for event handlers.

Wikipedia has a rather good definition of Closure:

In programming languages, a closure, also lexical closure or function closure, is a technique for implementing lexically scoped name binding in a language with first-class functions. Operationally, a closure is a record storing a function together with an environment. The environment is a mapping associating each free variable of the function (variables that are used locally, but defined in an enclosing scope) with the value or reference to which the name was bound when the closure was created. Unlike a plain function, a closure allows the function to access those captured variables through the closure’s copies of their values or references, even when the function is invoked outside their scope.

Note in particular that “closure” is a concept inherent to Functional Programming. Using it in Logic Programming is confusing.

So what are the problems?

  • Prolog is not a language based on functions (barring whatever is on the right-hand side of the is operator). Perforce there are no constructible and returnable functions. Perforce there no closures.
  • Predicates are not “first-class citizens”. You cannot define them, pass them, and in particular return them. Perforce there are no predicates equivalent to closures.
    • Although you might be able to laboriously construct predicates by building terms for the predicate’s clauses and assert those into the database.
    • You can of course call predicates indirectly by their name (used in the same way as a function pointer by having call/x lift a term to the “predicate plane” and call that. Which is what we are talking about.
  • There is no context to “close over”. Prolog is lacking in contexts (maybe a disadvantage). It has the global namespace and the context of the clause. Nothing else. There are no variables to look up in a context. The clause’s context does not survive return.

So no closures. Just indirect calls.

How would a real “logic programming closure” look like in Prolog? Here is a bad attempt:

  • Uppercase lambda Λ marks predicate logic variables, as well as the “anonymous clause head”.
  • Arrow down ↓ marks a copy-term operation from a term in the clause context to a term in the anonymous clause context.
create_poly_in_x(C0,C1,C2,ΛP) :- 
   ΛP is (Λ(X,R) :- R is ↓C0*X*X + ↓C1*X + ↓C2)

?- create_poly_in_x(4,4,6, ΛP), ΛP(12,R).
R = 630.

This would a dog when backtracking. And how does one go about when actual predicates are involved, not just “predicaty-looking” functions? But that’s for another time.

I would argue that what library yall provides is not even a lambda expression, which is another thing with a clear meaning only in the context of functional languages:

Again, from Wikipedia, the Anonymous Function or “Lambda Expression” (colloquially, “Lambda”)

In computer programming, an anonymous function (function literal, lambda abstraction, or lambda expression) is a function definition that is not bound to an identifier. Anonymous functions are often arguments being passed to higher-order functions, or used for constructing the result of a higher-order function that needs to return a function. If the function is only used once, or a limited number of times, an anonymous function may be syntactically lighter than using a named function. Anonymous functions are ubiquitous in functional programming languages and other languages with first-class functions, where they fulfill the same role for the function type as literals do for other data types.

What yall provides, however, is the possibility to define shims or wrappers around predicates:

From Shim:

“In computer programming, a shim is a library that transparently intercepts API calls and changes the arguments passed, handles the operation itself or redirects the operation elsewhere. Shims can be used to support an old API in a newer environment, or a new API in an older environment. Shims can also be used for running programs on different software platforms than they were developed for.”

There is also the term wrapper library, which is basically the same thing.

In fine, I do think the use of the term “closure” should be banished until the next generation of LP languages.

Addendum: Example

Let’s take a simple polynomial, a function of two variables:

  • In lambda notation: p := λx.λy.x³+y²
  • Or in traditional notation: p(x,y) := x³ + y²

In Prolog, the above function is modeled by a predicate e.g. poly/3.

That predicate behaves as a function because two arguments have an “input” role and must be ground for evaluation to proceed (in other words, the mode of the logic variables is ++). yall, however, can work in more general settings.

Expressed with a procedure:

poly(X,Y,R) :- R is X*X*X + Y*Y.

?- poly(2,3,R).
R = 17.

We can perform indirect calls (not to be confused with call-by-name) by constructing a term and handing it to call. Again, this is not “calling a first-class function”, it’s just an indirect call:

?- call(poly(2,3,R)).
R = 17.

?- call(poly(2,3),R).
R = 17.

?- call(poly(2),3,R).
R = 17.

?- call(poly,2,3,R).
R = 17.

Same, but more flexibly, with apply (variadic arguments? yes, please!):

?- apply(poly,[2,3,R]).
R = 17.

It is said that the above is slower than call/x.

This can of course be done recursively, building up the apply onion:

?- apply(apply(poly,[2,3,R]),[]).
R = 17.

Now we want to “wrap” the call to poly/3 to define a new function.

So, create a named shim poly_new/2 around poly/2 (with Xo, Ro standing for “X-outer”, “R-outer”). Note that in this example modification of values happens on “information inflow” and “information outflow”:

poly_new(Xo,Ro) :- X is Xo/2, poly(X,Xo,R), Ro is R*3. 

?- poly_new(2,Ro).
Ro = 15.

This evidently computes:

poly_new_another(X,R) :- R is (X*X*X*3/8 + 3*X*X).

Using the yall library, we can avoid having to explicitly define poly_new/2 predicate, writing the shim inline:

poly_new_yall(Xo,Ro) :- 
   call( [Xo,Ro] >> (X is Xo/2, poly(X,Xo,R), Ro is R*3), Xo, Ro ).

or using apply/2:

poly2yall(Xo,Ro) :- 
   apply( [Xo,Ro] >> (X is Xo/2, poly(X,Xo,R), Ro is R*3), [Xo, Ro] ).

Note that the parentheses are important. What is inside apply is a term, with the toplevel functor >>.

Sadly (and maybe unexpectedly) one cannot write:

badpoly(Xo,Ro) :- ([Xo,Ro] >> (X is Xo/2, poly(X,Xo,R), Ro is R*3)).

The above compiles, but then:

?- badpoly(2,R).
ERROR: Domain error: `lambda_parameters' expected, 
found `[2,_3938]>>(user:(_3956 is 2/2,poly(_3956,2,_3978),_3938 is _3978*3))'

The apply-less syntax would demand native Prolog support. Until a new ISO Prolog standard has been written or Prolog diverges more from the standard, you have to call or apply around the >>.

Again, this is just a shim, plumbing around poly. There is no closure, nothing can be passed, nothing that is lexically scoped is retained for later:

The usefulness as a shorthand to avoid naming predicates becomes clear when you don’t use call or apply but use other predicates taking terms that can be completed and lifted to goals, like maplist:

Instead of:

?- maplist(poly_new,[1,2,3,4,5],Out).
Out = [3.375, 15, 37.125, 72, 121.875].

write directly:

?- maplist(
   [Xo,Ro] >> (X is Xo/2, poly(X,Xo,R), Ro is R*3),
   [1,2,3,4,5], 
   Out).
Out = [3.375, 15, 37.125, 72, 121.875].
4 Likes

Just a partial answer to your detailed post; great title :slightly_smiling_face:.

As you wrote, Prolog (or Logtalk) are not based on functions. Thus, the definition of closure was adopted and reinterpreted in the context of logic programming. This is quite common and, unfortunately, doesn’t help when learning new languages as concepts use the same words with close meaning but also differences in what is regarded as key characteristics. Other good examples are event, object, delegation, forwarding, …

When an encapsulation mechanism is present, e.g. Prolog modules or Logtalk objects, there is a context to "close over*, i.e. an environment. That environment is used to decide at runtime, notably, the context where the constructed meta-call will take place (i.e. in which module or object). Logtalk and some Prolog systems do provide access to this context. This may deviate from the idea of environment as in the Wikipedia article you cite but, again, it’s a consequence of reinterpreting a functional concept in a different programming paradigm.

All in all, I think the interpretation of closure is settled in logic programming, at least as far as Prolog and Logtalk go. Maybe what’s need is more general discussion of the concept that encompass more programming paradigms rather than be presented from the perspective of a single one, even if the concept originate there?

1 Like

Traditionally the meta predicate argument specifiers 0, 1, 2, … are called closure index. You see the arity of the closure, how much currying they expect.

Example:

:- meta_predicate maplist(2,?,?).

This means the first closure argument to maplist takes two (2) extra arguments. You can also easily check that closures are real closures in Prolog, since they dont freeze variables:

?- C = 5, maplist([A,B]>>(B is A+C), [1, 2, 3], X). 
C = 5, 
X = [6, 7, 8]. 

In the above the closures sees, that at runtime C was bound to 5. So closures in Prolog have external environment references. But I guess much more environment is not possible in Prolog.

Edit 06.02.2020:
Concering your badpoly/2 example, I guess it wouldn’t type check, because the body of a clause needs closure index 0. But you mention a closure with closure index 2. You would need to invent a Prolog language extension somehow for that.

If you want Prolog rules to define things with closure index different from 0, you need to blow up the arguments, and you can use the defined predicate nevertheless with a higher order closure index. This is how you would blow up the previous addition example:

add(C, A, B) :- B is A+C

And you can still use what you defined with a higher order closure index:

?- maplist(add(5), [1, 2, 3], X).
X = [6, 7, 8].

When you define predicates this way, you need to mention the enviroment parameters first and then the closure parameters, since closure parameters are appended as defined in ISO call/n.

1 Like

With the Logtalk linter:

:- object(closures).

	:- public(badpoly/2).
	badpoly(Xo,Ro) :-
		([Xo,Ro] >> (X is Xo/2, poly(X,Xo,R), Ro is R*3)).

:- end_object.

you get:

?- {closures}.
*     Lambda expression [A,B]>>(C is A/2,poly(C,A,D),B is D*3) parameter variable A used elsewhere in clause
*       while compiling object closures
*       in file /Users/pmoura/Desktop/closures.lgt between lines 5-6
*     
*     Lambda expression [A,B]>>(C is A/2,poly(C,A,D),B is D*3) parameter variable B used elsewhere in clause
*       while compiling object closures
*       in file /Users/pmoura/Desktop/closures.lgt between lines 5-6
*     
*     Unclassified variables [A,B] in lambda expression: [C,D]>>(A is C/2,poly(A,C,B),D is B*3)
*       while compiling object closures
*       in file /Users/pmoura/Desktop/closures.lgt between lines 5-6
*     
!     Representation error: lambda_parameters
!       in clause for predicate badpoly/2
!       in file /Users/pmoura/Desktop/closures.lgt between lines 5-6
!     
false.

Sorry for the self reply. Multi-tasking here…

I believe the badpoly/2 you’re looking for is:

:- object(closures).

	:- public(badpoly/2).
	badpoly(X,R) :-
		({X,R} / (Xo is X/2, poly(Xo,X,Ro), R is Ro*3)).

	poly(X,Y,R) :-
		R is X*X*X + Y*Y.

:- end_object.

Sample call:

?- {closures}.
% [ /Users/pmoura/Desktop/closures.lgt loaded ]
% (0 warnings)
true.

?- closures::badpoly(2,R).
R = 15.

But, of course, there’s no point here in using a lambda expression. Just an academic exercise, I assume? Still Free/Lambda expressions are useful for bagof/3 and setof/3 calls. See e.g. https://github.com/LogtalkDotOrg/logtalk3/blob/7d2ad1b041af8c0c13b95990f6aaa213653e8420/examples/lambdas/lambdas.lgt

1 Like

Thank you Paulo. Yes, that’s right (both for the “free variables” and the “academic exercise” part).

I had missed the {} vs [] part. I have to think again.