Ha4

Coming to the exotic realm of Prolog programming from almost any other background is a difficult but rewarding experience. As usually happens with learning new languages, my first attempts with Prolog were (and still remain) clumsy. I miss Haskell. Most of all, I miss a clean paradigm for functions, and a way to pass them as parameters. Below I take one of the possible directions to solve this - embed a lambda calculus interpreter in Prolog.

Look at this common paradigm:

map((lambda x: x + 1), [1, 2, 3]) #  = [2, 3, 4] (Python)

Prolog, anyone? Well, SWI Prolog has it:

?- maplist(plus(1), [1, 2, 3], R).
R = [2, 3, 4]

This works only because there is a plus predicate defined. Every time you want to do something more esoteric, you need to create a new predicate.

Obviously function passing is possible not only in Haskell or Python. Even the extra ugly languages as C, PHP, or Java allow for it. In C, you can pass pointers; in PHP - function names as strings; as for Java, you can wrap the function you want to pass in an anonymous class.

The problem then is not impossibility. Rather, it is inconvenience. By making function passing tedious, the conventional languages discourage it. By implication, they also discourage the clear thinking that goes with functional design. This is how they become ugly.

There is good news for Prolog. It is often stated that Prolog is Lispish, and it is. The terms form syntactic trees, almost equivalent to S-expressions, and a term can be split into a list, processed, and assembled back by the =.. operator. So, it must be possible to make function passing convenient, by writing an interpreter for terms that understands them as functions.

But wait, what exactly is a function in Prolog? Let us model functions as binary predicates f(In, Out). Can they be passed as arguments to other functions? In a way, yes, one can do g(f, Out) and then have the receiver call it like g(F, Out) :- call(F, arg1, arg2, arg3, Out)..

What makes this tedious is that all functions must map to named predicates. Try defining a function that takes two functions and returns their composition as a function. Ideally, make it a curried function, as the Haskell

(.) :: (b -> c) -> (a -> b) -> a -> c

How to return the (anonymous) resulting function? One could implement this by extending the predicate database.

But I suggest another way. Let us embed a small language for functions. The expressions of this language will be Prolog terms, and they will be callable in the sense that a function such as g(F, Out) :- call(F, arg1, arg2, arg3, Out). will accept these expressions for F.

Now, a great model to think in terms of is lambda calculus. Taking that for inspiration, consider this:

lambda(Pattern, Body, Argument, Result) :-
     Pattern = Argument, Result = Body.

After consulting the file, we test it in the interpreter:

?- F = lambda(X, X+1), call(F, 0, R).
F = lambda(0, 0+1),
X = 0,
R = 0+1
?- F=lambda(X, X+1), maplist(F, [1], R).
F = lambda(1, 1+1),
X = 1,
R = [1+1]
?- F=lambda(X, X+1), maplist(F, [1, 2, 3], R).
No

Well, this works almost as expected, but not quite. Thanks to Prolog pattern matching, the double unification (Pattern to Argument and Result to Body) in lambda is almost exactly what substitution in lambda calculus is all about. However, the above code does no evaluation (notice 0+1). Further, the last example does not work because the variables used in lambda get bound after a first match, and cease being variables.

The last problem is the most nettling, but it can be easily amended by copying the variables afresh before unification. Redefine the above as:

lambda(Pattern, Body, Argument, Result) :-
      copy_term(Pattern-Body, P-B), P = Argument, Result = B.

Now we have:

?- F=lambda(X, X+1), maplist(F, [1, 2, 3], R).
F = lambda(X, X+1),
R = [1+1, 2+1, 3+1]

Basically this would serve at least half of the cases where I missed lambdas in Prolog. What makes it really nice is Prolog's unification rules - you can do some pattern matching, like this:

?- maplist(lambda(X-Y, X=Y), [a-1, b-2, c-3], R).
R = [a=1, b=2, c=3]

However, I did not stop here. Expressions still do not get evaluated, there is no lambda application, no lambda nesting, and it is still close to impossible to define a composition function.

I ended up writing a module for lambda calculations. It is a bit too involved to discuss in detail here, let me just note that it uses normal order evaluation, accepts Prolog terms as basic values, and allows to use global functions (or Lisp special forms) defined either as lambdas or as binary Prolog predicates. In the later case one can make them strict in the argument by reducing it with lambda:r (see math and iff below). The syntax uses ~> for lambda abstraction (instead of lambda) and ~ for lambda application:

:- use_module(lambda).
 
id    - (X ~> X).
const - (C ~> _ ~> C).
curry - (F ~> A ~> B ~> F~(A,B)).
cons  - (H ~> T ~> [H|T]).
comp  - (F ~> G ~> X ~> F~(G~X)).
 
y     - (F ~> (X ~> F ~ (X ~ X)) ~ (X ~> F ~ (X ~ X))).
fac   - (
  F ~> N ~> iff ~ (N  F = const;
    F = (const ~ id)
  ).

There are a number of functions defined here, including the composition (comp). Did you notice the Y combinator? The definition of factorial is a canonical example for lambda calculus, to be used with the Y combinator as this:

?- lambda((y~fac~4), R).
R = 24 ? ;

Right, this is 4! = 1*2*3*4 = 24. It is a bit of a mystery how this works, let the brighter minds ponder. I will just say that while this is a good test of the lambda engine, considering how slack my implementation is, this is surely not the way to use recursion in production.

So here comes the implementation. Just a few words about it - I tried to make it portable to at least SWI and YAP (two free Prologs I have access to), that is why I do not use any modules and reinvent the wheel - association lists, map, append, and the like. And since I am lazy, the association lists are a mess performance-wise. Without further ado, here comes my first Prolog module:

:- module(lambda, [
  lambda/2, '~>'/4, op(1190, xfy, ~>), op(1180, yfx, ~)
]).
:- dynamic('-'/2).     % definitions (convenience)
:- op(1190, xfy, ~>).  % lambda abstraction
:- op(1180, yfx, ~).   % lambda application
 
% representations
 
l(F, H, T) :- F =.. ['~>', H, T].
a(A, H, T) :- A =.. ['~',  H, T].
 
% lambda calculator
 
lambda(E, R) :- cp(E, X), r(X, R).
 
r(E, R) :-
        atom(E) -> d(E, R);
        (var(E); atomic(E); l(E, _, _)) -> R = E;
        a(E, H, T) -> r(H, F), c(F, T, R);
        E =.. Es, map_(r, Es, ES), R =.. ES.
 
c(F, A, R) :-
        l(F, _, _) -> copy_term(F, G),
          l(G, H, T), H = A, r(T, R);
        call_(F, [A, S]), r(S, R).
 
% convenience - definitions lookup.
 
d(E, R) :-
        call_('-', [E, F]), lambda(F, R), !;
        R = E.
 
% example definition - identity
 
user:'-'(id, (X~>X)).
 
% making lambdas usable as callables
 
'~>'(H, T, X, R) :-
        l(F, H, T),
        a(E, F, X),
        copy_term(E, C),
        r(C, R).
 
% convenience
 
call_(F, A) :-
        F =.. [H | T],
        append_(T, A, B),
        G =.. [call, user:H | B],
        call(G).
 
map_(_, [], []).
map_(F, [X|Xs], [Y|Ys]) :-
        call(F, X, Y),
        map_(F, Xs, Ys).
 
append_([], A, A).
append_([H|T], A, [H|B]) :-
        append_(T, A, B).
 
% lambda-aware term copying (normalization)
 
cp(A, B) :-
        cp(A, B, [], _).
 
cp(A, B, E0, E1) :-
        ground(A) ->
        (
            B=A, E1=E0
        );
        var(A) ->
        (
            get_(A, E0, B) -> E1=E0;
            C=B, set_(A, E0, C, E1)
        );
        l(A, H, T) ->
        (
            cp(H, Hb, [], Eh),
            merge_(E0, Eh, Et),
            cp(T, Tb, Et, _),
            l(B, Hb, Tb), E1=E0
        );
        compound(A) ->
        (
            A =.. As,
            cpa(As, Bs, E0, E1),
 
            B =.. Bs
        ).
 
cpa([], [], E, E).
cpa([A|As], [B|Bs], E0, E1) :-
        cp(A, B, E0, E),
        cpa(As, Bs, E, E1).
 
% very inefficient but working association lists
 
get_(K, [A-B|T], V) :-
        A==K -> V=B;
        get_(K, T, V).
 
drop_(_, [], []).
drop_(K, [A-B|T], R) :-
        A==K -> R=T;
        drop_(K, T, S),
        R = [A-B|S].
 
set_(K, X, V, [K-V|Y]) :-
        drop_(K, X, Y).
 
merge_(X, [], X).
merge_(X, [A-B|T], Z) :-
        set_(A, X, B, Y),
        merge_(Y, T, Z).