Comments welcome!

We present a very simple implementation of lambda expressions in
ISO Prolog that fits into the existing conventions for higher order
predicates based on `call/N`

. No syntax or compiler
extension is needed.

?-How to say thatuse_module(library(clpfd)).?-use_module(library(apply)).

`Y`

is different from all elements in a
list? So `Y #\= X`

for all `X`

in
list `Xs`

.
?-And in a list of lists?Xs = [1,2], maplist(#\=(Y), Xs).Xs = [1, 2], Y in inf..0\/3..sup.

?-And that they are all greaterXss= [[1,2],[3]], maplist(maplist(#\=(Y)), Xss).Xss = [[1, 2], [3]], Y in inf..0\/4..sup.

`Y`

?
That cannot be formulated directly. But we have luck. We can reformulate

into the equivalent`X #> Y`

for all elements`X`

Now,`Y #< X`

for all elements`X`

`X`

is the last
argument. We can therefore use the goal without the last
argument: `#<(Y)`

. Such goals with missing arguments
are called continuations. Unfortunately, we are not always
that lucky.
?-And thatXss= [[1,2],[3]], maplist(maplist(#<(Y)), Xss).Xss = [[1, 2], [3]], Y in inf..0.

`Xss`

+ `Yss`

= `Zss`

with pointwise
addition?
This time we went too far. We have to use an auxiliary definition
like `zplus/3`

. Welcome to the world of superfluous
use-once predicate names!

zplus(X,Y,Z) :- X + Y #= Z. ?-Xss= [[1,2],[3]], maplist(maplist(zplus), Xss, Yss, Zss).Xss = [[1, 2], [3]], Yss = [[_G2492, _G2495], [_G2501]], Zss = [[_G2513, _G2516], [_G2522]], 1+_G2492#=_G2513, 2+_G2495#=_G2516, 3+_G2501#=_G2522.

Can't we do this without the extra definition? After all, predicate
definitions are global which means we have to remember that name. And
finding a good name in Prolog isn't easy. For
instance, `z_z_sum/3`

would have been a more relational
name. Or `'x + y = z'/3`

, but that would have been
ambiguous: Are we talking about elements in **N**, **Z**
or **R**? I can ponder such questions for days. What we would like
to have, is some device for describing all this within the argument
of `maplist/4`

.

That's what lambda expressions are for. There have been many attempts to include them in Prolog, but they do not fit into ISO Prolog. They require syntax and compiler extensions. Fortunately, it is possible to respect ISO Prolog's syntax and get nice lambdas that collaborate with the existing higher order programming conventions. A simple library is all we need. Here is how:

?-The underlined part is the lambda expression. It starts with a backslash and adds a caret after each argument. The scope of variables within lambdas is local. To get a global variable, i.e. a variable that is free within the expression, consideruse_module(lambda).?-Xss= [[1,2],[3]], maplist(maplist(Xss = [[1, 2], [3]], Yss = [[_G3804, _G3807], [_G3813]], Zss = [[_G3825, _G3828], [_G3834]], 1+_G3804#=_G3825, 2+_G3807#=_G3828, 3+_G3813#=_G3834.\X^Y^Z^(X+Y#=Z)), Xss, Yss, Zss).

`Xss`

+ `Y`

= `Zss`

:
?-Instead of a simple backslash, we use nowXss= [[1,2],[3]], maplist(maplist(Y+\X^Z^(X+Y#=Z)), Xss, Zss).Xss = [[1, 2], [3]], Zss = [[_G2965, _G2968], [_G2974]], 3+Y#=_G2974, 2+Y#=_G2968, 1+Y#=_G2965.

`+\`

. The
variables in the term before the `+\`

have a global scope.
For more details see the manual.
`\`

together
with a `^`

for each argument. The `\`

is responsible for
appropriate renaming, whereas the `^`

is responsible for parameter
passing. The `(^)/2`

is frequently used for lambda-like
parameter passing. See Pereira and Shieber's (undervalued) 1987 book
which justifies the choice
of the symbol (1st ed. p.96, digital ed.p.75, PDF p.85):
Thus the lambda expression λ x. x + 1 would be encoded in Prolog asIn Pereira and Shieber's book the`X^(X+1)`

. Similarly, the lambda expression λ x. λ y.wrote(y, x) would be encoded as the Prolog term`X^Y^wrote(Y,X)`

, assuming right associativity of "^".^{3}^{3}There is precedent for the use of the caret to form lambda expressions. The notation that Montague himself used for the lambda expression λ x.φ was (ignoring details of intensionality operators) x^φ, which we have merely linearized.

Remark: the x^ should look like a circumflex, e.g. â

`^`

-notation is only used
for passing parameters. No copying takes place. It therefore resembles
very closely our use of `^`

.
A remark to the remark about Montague using x^ for lambda expressions: This notation is already used in Quine's Mathematical Logic.

`apply/2,3...`

is defined much in the same way as the still
uninvented
`call/2,3...`

The examples below are given in their
original syntax. Note, that `have_property/2`

does not
facilitate nesting, due to the argument order.
have_property([], P). have_property([X|L], P) :- apply(P,X), have_property(L, P).

`R`

and `Y`

must be declared common(R,L,Y) :- have_property(L, lamda(X).R(X,Y)).

common(R,L,Y) :- maplist([R,Y]+\X^call(R,X,Y),L).

common(R, L, Y) :- have_property(L, foo(R,Y)). apply(foo(R,Y),X) :- apply(R,X,Y). apply(pastime,X,Y) :- pastime(X,Y).Note, that

`foo/2`

corresponds closely to the
continuation `call/2`

.
`apply`

is for explicitly constructing
partial expressions.
apply(twice,F,twice(F)). apply(twice(F),X,Z) :- apply(F,X,Y), apply(F,Y,Z). apply(succ,X,Y) :- Y is X + 1. ?-How can we obtain such terms without the ad hoc facts inapply(twice, twice, F1), apply(F1,twice,F2), apply(F2,succ,F3), apply(F3,0,Ans).F1 = twice(twice), F2 = twice(twice(twice)), F3 = twice(twice(twice(twice(succ)))), Ans = 16.

`apply/3`

above? We would have to
use `(=..)/2`

, a.k.a. `boum(2)`

to
transform `twice/0`

to `twice/1`

. But there is a
simpler way. Remark that a continuation `twice(QQ)`

can
also be represented as `call(twice,QQ)`

! This is much in
the same way, as a goal `p(X)`

could be written
as `call(p,X)`

. For a more detailed discussion,
see Richard O'Keefe's elaboration.
twice(Cont,S0,S) :- call(Cont,S0,S1), call(Cont,S1,S). ?-call(call(twice,call(twice,call(twice,call(twice,call(succ))))),0,N).N = 16.

without compiler assistance, lambda-expressions either don't work or require more, and more error-prone, annotation than I think the average programmer would be happy with. I do not want to recommend anything which requires compiler support or even that there be a compiler.We completely agree with his distrust in compiler based approaches. Compilers in this context should reduce resource consumption and should detect certain errors statically, but they should not be required to implement variable scoping.

?- all((\(X, Y) :- Body), Xs, Ys).

?- maplist(\X^Y^Body, Xs, Ys).

common_prefix(Front, Xs, Ys) :- all((\(X, Y) :- append(Front)), Xs, Ys).

common_prefix(Front, Xs, Ys) :- maplist(Front+\append(Front), Xs, Ys).Above code is a shorthand for:

common_prefix(Front, Xs, Ys) :- maplist(Front+\X^Y^append(Front,X,Y), Xs, Ys).

`''/N`

. This corresponds to
our `\`

-notation. The major difference is that
Hiord-lambdas do not permit partial application. The other notation
using positional parameters has no direct counterpart. It is a slight
generalization of the traditional higher order approach. Both depend
on argument ordering. The extensions of Hiord are incompatible with ISO
Prolog and require extensions in various parts of a Prolog system. We
compare our approach with Hiord following the ASIAN
2004 paper, since no implementation is
available. The programs are colored as follows:
- (red) Hiord programs
- (green) our new formulation of lambda expressions, where applicable
- (blue) the traditional call/N based approach
- (grey) common code

list([], _). list([X|Xs], P) :- P(X), list(Xs, P).

:- meta_predicate maplist(1,?). maplist(_, []). maplist(P, [X|Xs]) :- call(P, X), maplist(P, Xs).

all_less(L1, L2) :- map(L1, {''(X,Y) :- X < Y}, L2).

all_less(L1, L2) :- maplist(\X^Y^(X < Y), L1, L2).

same_mother(L) :- list(L, {M-> ''(S) :- child_of(S,M,_)}).

same_mother(L) :- maplist(M+\S^child_of(S,M,_), L).

same_parents(L) :- list(L, {M,F -> ''(S) :- child_of(S,M,F)}, L).

same_parents(L) :- maplist( [M,F] +\S^child_of(S,M,F), L).

same_parents(L) :- list(L, {child_of(#,_M,_F)}).

parents_of(M, F, C) :- child_of(C, M, F). same_parents(L) :- maplist(parents_of(_M,_F), L).

all_less(L1, L2) :- map(L1, {# < #}, L2).

all_less(L1, L2) :- maplist(<, L1, L2).

closure(R,X,Y) :- R(X,Y). closure(R,X,Y) :- R(X,Z), closure(R,Z,Y).

:- meta_predicate closure(2, ?,?). closure(R,S0,S) :- call(R,S0,S). closure(R,S0,S) :- call(R,S0,S1), closure(R,S1,S).

same_father(L) :- list(L, {F -> ''(S) :- child_of(S,_,F)}).

same_father(L) :- maplist(F +\ S ^ child_of(S,_,F), L).

father(F, S) :- child_of(S,_,F).

same_father(L) :- list(L, {father(_,#)}).

same_father(L) :- maplist(father(_), L).

descendent_Y(X,Y) :- closure({father(#,#)},X,Y).

descendent_Y(X,Y) :- closure(father, X,Y).

descendent_Y(X,Y) :- closure({''(F,S) :- child_of(S,_,F)},X,Y).

descendent_Y(X,Y) :- closure(\F^S^child_of(S,_,F), X,Y).

```
:-
set_prolog_flag(occurs_check,error).
```

was very helpful to locate those errors. I can only hope that also
other systems will adopt this feature, which nicely fits into ISO
Prolog's approach to unification (see 13211-1:7.3).
lists_mod(Member, List /*, Reverse*/) :- Me = { ''(X, L, R) :- L = [X|_] ; L = [_|Xs], R(X, Xs, R) }, Member = { Me -> ''(X,L) :- Me(X, L, Me) }, Li = { ''(L, P, R) :- L = [] ; L = [X|Xs], P(X), R(Xs,P,R) }, List = { Li -> ''(L,P) :- Li(L, P, Li) }.

lists_mod(Member, List) :- Me = \X^L^R^ ( L = [X|_] ; L = [_|Xs], call(R, X, Xs, R) ), Member = Me +\Xr1^Lr1^ call(Me, Xr1, Lr1, Me), Li = \Lr1^P^Rr1^ ( Lr1 = [] ; Lr1 = [X|Xs], call(P,X), call(Rr1,Xs,P,Rr1) ), List = Li +\Lr2^Pr1^call(Li,Lr2,Pr1,Li).

main(X) :- lists_mod(Member,_), Member(X,[1,3,4]).

main(X) :- lists_mod(Member,_), call(Member,X,[1,3,4]).

`r1`

x). Compiler support (actually term
expansion would suffice) could produce appropriate error messages to
avoid accidental clashes.
main_member(X,Xs) :- lists_mod(Member,_), call(Member, X, Xs). main_list(Xss) :- lists_mod(Member,List), call(List,Xss,\Xs^call(Member,1,Xs)). main_list2(Xss) :- lists_mod(Member,List), call(List,Xss,\[1]^true).

The lambda is realized in two steps corresponding to different predicates. The first step creates a new instance with variables renamed appropriately. The second step is responsible for argument passing.

`(+\)/2,..`

Instantiation with free variables.`(\)/1,...`

Instantiation without free variables.`(^)/3,..`

Argument passing

^(V1, Goal, V1) :- call(Goal). ^(V1, Goal, V1, V2) :- call(Goal, V2). ^(V1, Goal, V1, V2, V3) :- call(Goal, V2, V3). ^(V1, Goal, V1, V2, V3, V4) :- call(Goal, V2, V3, V4). ^(V1, Goal, V1, V2, V3, V4, V5) :- call(Goal, V2, V3, V4, V5). ^(V1, Goal, V1, V2, V3, V4, V5, V6) :- call(Goal, V2, V3, V4, V5, V6). ^(V1, Goal, V1, V2, V3, V4, V5, V6, V7) :- call(Goal, V2, V3, V4, V5, V6, V7). ^(V1, Goal, V1, V2, V3, V4, V5, V6, V7, V8) :- call(Goal, V2, V3, V4, V5, V6, V7, V8). :- op(201,xfx,+\). +\(GV, FC) :- copy_term(GV+FC,GV+C), call(C). +\(GV, FC, V1) :- copy_term(GV+FC,GV+C), call(C, V1). +\(GV, FC, V1, V2) :- copy_term(GV+FC,GV+C), call(C, V1, V2). +\(GV, FC, V1, V2, V3) :- copy_term(GV+FC,GV+C), call(C, V1, V2, V3). +\(GV, FC, V1, V2, V3, V4) :- copy_term(GV+FC,GV+C), call(C, V1, V2, V3, V4). +\(GV, FC, V1, V2, V3, V4, V5) :- copy_term(GV+FC,GV+C), call(C, V1, V2, V3, V4, V5). +\(GV, FC, V1, V2, V3, V4, V5, V6) :- copy_term(GV+FC,GV+C), call(C, V1, V2, V3, V4, V5, V6). +\(GV, FC, V1, V2, V3, V4, V5, V6, V7) :- copy_term(GV+FC,GV+C), call(C, V1, V2, V3, V4, V5, V6, V7). \(FC) :- copy_term(FC,C), call(C). \(FC, V1) :- copy_term(FC,C), call(C, V1). \(FC, V1, V2) :- copy_term(FC,C), call(C, V1, V2). \(FC, V1, V2, V3) :- copy_term(FC,C), call(C, V1, V2, V3). \(FC, V1, V2, V3, V4) :- copy_term(FC,C), call(C, V1, V2, V3, V4). \(FC, V1, V2, V3, V4, V5) :- copy_term(FC,C), call(C, V1, V2, V3, V4, V5). \(FC, V1, V2, V3, V4, V5, V6) :- copy_term(FC,C), call(C, V1, V2, V3, V4, V5, V6). \(FC, V1, V2, V3, V4, V5, V6, V7) :- copy_term(FC,C), call(C, V1, V2, V3, V4, V5, V6, V7).Above code should run immediately for systems without constraints. With constraints make sure that

`copy_term/2`

does not copy
constraints. Since current Prolog systems differ here quite
significantly, consider one of the following implementations:
- In SWI and YAP use
`copy_term_nat/2`

. - In systems with
`call_residue/2`

use:copy_term_nat(T, TC) :- call_residue(copy_term(T, TC),_).

- In systems with
`copy_term/3`

:copy_term_nat(T, C) :- copy_term(T, C, _).

E.g. lambdas occurring in `maplist/2`

can be expanded
similarly to `library(apply_macros)`

, if all variables are
correctly scoped statically. A clause

p(...) :- ... X ..., maplist(\Y^p(X,Y), L), ...must not compile the lambda, due to the variable

`X`

.
Ideally an error is produced in this case.
Systems that perform semantics altering translations when
converting a term to a clause (13211-1:7.6) do not preserve the
equivalence between a goal and the same goal wrapped
with `call/1`

. They should better refuse incorrectly scoped
lambda expressions altogether. Note that otherwise the only semantics
altering effect of 13211-1:7.6 w.r.t. wrapping a goal
with `call/1`

is the scope of cuts.

- Variable scoping. There is currently no checking for incorrectly
scoped variables. Many errors could be detected
with
`expand_term`

. - Variable renaming. It is tempting to consider an automatic static renaming of variables. However, this does not seem to fit into the dynamic nature of many Prolog programs. Instead, some misuses could be detected during term-expansion based on meta_predicate declarations.
- Superfluous arguments. They are detected and lead to an error.
For the moment it is a 13211-1:7.12f Representation error, which is
never wrong - one can always claim that such things cannot be
represented. But a more specific error like a type error (which type?)
would be preferable. Without the error checking the accidental
presence of a predicate
`(^)/2`

would lead to skipping the remaining arguments. Note that the ISO standard does not define a predicate`(^)/2`

. It is rather an artefact in most current implementations.?-

`maplist(\X^Y^Z^(Z #= X+Y), [1], [3]).`ERROR: user://3:324: Cannot represent due to `lambda_parameters'

`setof/3`

for
a predicate of larger arity? With something
like `country/10`

? You must have noticed the big
problem with existential variables. In Chat-80 a country's
currency is in the last argument of `country/10`

. What are
the currencies on this planet? We could try
?-But we want them in an ascending list without duplicates like the popularcountry(_,_,_,_,_,_,_,_,_,Currency).Currency = afghani ; Currency = lek ; Currency = dinar

`dinar`

. So...
?-Not exactly what we wanted. See it? Now, correct that compactly! I wish you luck. You would have to give all those anonymous variables a name! With lambdas things remain compact:setof(Currency,country(_,_,_,_,_,_,_,_,_,Currency),Currencies).Currencies = [afghani] ; Currencies = [lek] ; Currencies = [dinar]

?-setof(Currency,Currency+\country(_,_,_,_,_,_,_,_,_,Currency),Currencies).Currencies = [?, afghani, ariary, australian_dollar, bahamian_dollar, baht, balboa, bolivar, ... ].

`call/N`

and this library are
sufficient. The real challenge is an effective error detection and an
efficient compilation scheme. But all this can be done within 13211-1
and 13211-2.
- ISO/IEC 13211-1 Programming languages - Prolog - Part 1: General core. Published 1995-06-01.
- ISO/IEC 13211-2 Programming languages - Prolog - Part 2: Modules. Published 2000-06-01.
- ISO/IEC 13211-1:1995/Cor.1:2007. Technical Corrigendum 1. Published 2007-11-15.
- ISO/IEC 13211-1:1995/Cor.2:2012. Technical Corrigendum 2. Published 2012-02-15.

- D. H. D. Warren.

Higher-Order Extensions to Prolog - Are They Needed?, In Hayes, Michie and Pao, Machine Intelligence 10. Ellis Horwood, 1982.Originally: International Machine Intelligence Workshop, Cleveland, April 1981, DAI Research Paper 154.

- D. L. Bowen (ed.), L. Byrd, F. C. N. Pereira, L. M. Pereira and
D. H. D. Warren.

Decsystem-10 Prolog User's Manual. Occasional Paper 27, Dept. of Artificial Intelligence, University of Edinburgh, Scotland, 10 November, 1982. (Corresponds to version 3.47). - R. O'Keefe.

Draft Prolog library proposal online. - F. C. N. Pereira, St. M. Shieber

Prolog and Natural-Language Analysis. (CSLI Lecture Notes 10, ISBN 0-937073-18-0), 1987. Digital version - L. Naish.

Higher-order logic programming in Prolog. Workshop on multi-paradigm logic programming, JICSLP'96. Research report #96-28, TU Berlin. 1996. - D. Cabeza, M. Hermenegildo, and J. Lipton

Hiord: A Type-Free Higher-Order Logic Programming Language with Predicate Abstraction

ASIAN 2004, LNCS 3321, pp. 93-198, 2004. PDF