Programming Language Seduction September 8, 2010Posted by Andre Vellino in Constraints, Knowledge Representation, Logic, Logic Programming.
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.
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.