jump to navigation

Programming Language Seduction September 8, 2010

Posted by Andre Vellino in Constraints, Knowledge Representation, Logic, Logic Programming.
trackback

Maarten van Emden has written a new piece, “The Fatal Choice” (companion to his earlier post “Who Killed Prolog“) which aims at explaining the fierce loyalty that devotees have to programming languages such as Lisp and Prolog.

One can’t help but notice in this post, a slight undertow of resentment – as if Maarten had been jilted. To wit:

The US had acted as transmitter of the Prolog bug without being itself infected.

… as though Prolog were a European disease against which Americans (but not Canadians) were (thankfully) immune.

And again:

The examples that follow are not useful, but are chosen to convey the seductive nature of Prolog.

… as though she were an evil temptress whose beauty is merely skin deep!

As a lover (of Prolog) myself, I can definitely attest to its seductiveness.  I still love Prolog – for some of the reasons that the subsequent generation of Python and Ruby affecionados do: the freedom from the limitations of strict typing, dynamic interpretation, conciseness… Shall I compare thee to a summer’s day?

But what has smitten me for life is not really unification and backtracking – it’s Constraint Programming.  There are lots of programming languages deisgned for solving constraint satisfaction problems. There are even spreadsheet plugins for solving CSPs.  But what makes Logic Programming the perfect paradigm for constraint programming – as do speadsheets, actually, and for the same reason – is the declarative nature of relations between constrained variables.

One of my favourite toy program that illustrates the declarative character of CSPs in a logic programming framework is the N-Queens problem.  The program below can be run with the Finite Domain (FD) solver in GNU Prolog.

queens(N, L) :-
    length(L, N),
    domain(L, 1, N),
    safe(L),
    fd_labeling(L).
safe([]).
safe([X|Xs]) :-
    safe_between(X, Xs, 1),
    safe(Xs).
safe_between(X, [], M).
safe_between(X, [Y|Ys], M) :-
    no_attack(X, Y, M),
    M1 is M+1,
    safe_between(X, Ys, M1).
 no_attack(X, Y, N) :-
    X #\= Y,
    X+N #\= Y,
    X-N #\= Y.
 domain(L,S,E) :-
    values(S,E,V),
    fd_domain(L,V).
values(N,N,[N]):-!.
values(N,M,[M|R]):-
     L is M - 1,
     values(N,L,R).

I like this program not because it is 66% shorter (in than the equivalent [backtracking and recursive]) Java program but because the constraints are laid out declaratively by inequality constraints (in “no_attack”) and the work is done by a constraint propagation engine whose conceptual model is a natural extension of unification.  In fact, constraint propagation on finite domains and on closed intervals on the real line have a semantic model given by the theory of lattices, which Bill Older and I wrote up in a paper  in 1994.

What I find seductive is about constraint logic programming is the mathematical elegance of its underlying semantics and I haven’t yet fallen out of love.

Comments»

No comments yet — be the first.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: