Difference between logic programming and functional programming

Question

I have been reading many articles trying to understand the difference between functional and logic programming, but the only deduction I have been able to make so far is that logic programming defines programs through mathematical expressions. But such a thing is not associated with logic programming.

I would really appreciate some light being shed on the difference between functional and logic programming.

Answer 1

I wouldn't say that logic programming defines programs through mathematical expressions; that sounds more like functional programming. Logic programming uses logic expressions (well, eventually logic is math).

In my opinion, the major difference between functional and logic programming is the "building blocks": functional programming uses functions while logic programming uses predicates. A predicate is not a function; it does not have a return value. Depending on the value of it's arguments it may be true or false; if some values are undefined it will try to find the values that would make the predicate true.

Prolog in particular uses a special form of logic clauses named Horn clauses that belong to first order logic; Hilog uses clauses of higher order logic.

When you write a prolog predicate you are defining a horn clause: foo :- bar1, bar2, bar3. means that foo is true if bar1, bar2 and bar3 is true. note that I did not say if and only if; you can have multiple clauses for one predicate:

foo:-    bar1. foo:-   bar2. 

means that foo is true if bar1 is true or if bar2 is true

Some say that logic programming is a superset of functional programming since each function could be expressed as a predicate:

foo(x,y) -> x+y. 

could be written as

foo(X, Y, ReturnValue):-    ReturnValue is X+Y. 

but I think that such statements are a bit misleading

Another difference between logic and functional is backtracking. In functional programming once you enter the body of the function you cannot fail and move to the next definition. For example you can write

abs(x) ->     if x>0 x else -x 

or even use guards:

abs(x) x>0 -> x; abs(x) x=<0 -> -x. 

but you cannot write

abs(x) ->    x>0,    x; abs(x) ->    -x. 

on the other hand, in Prolog you could write

abs(X, R):-    X>0,    R is X. abs(X, R):-    R is -X. 

if then you call abs(-3, R), Prolog would try the first clause, and fail when the execution reaches the -3 > 0 point but you wont get an error; Prolog will try the second clause and return R = 3.

I do not think that it is impossible for a functional language to implement something similar (but I haven't used such a language).

All in all, although both paradigms are considered declarative, they are quite different; so different that comparing them feels like comparing functional and imperative styles. I would suggest to try a bit of logic programming; it should be a mind-boggling experience. However, you should try to understand the philosophy and not simply write programs; Prolog allows you to write in functional or even imperative style (with monstrous results).

Answer 2

In a nutshell:

In functional programming, your program is a set of function definitions. The return value for each function is evaluated as a mathematical expression, possibly making use of passed arguments and other defined functions. For example, you can define a factorial function, which returns a factorial of a given number:

factorial 0 = 1                       // a factorial of 0 is 1 factorial n = n * factorial (n - 1)   // a factorial of n is n times factorial of n - 1  

In logic programming, your program is a set of predicates. Predicates are usually defined as sets of clauses, where each clause can be defined using mathematical expressions, other defined predicates, and propositional calculus. For example, you can define a 'factorial' predicate, which holds whenever second argument is a factorial of first:

factorial(0, 1).               // it is true that a factorial of 0 is 1 factorial(X, Y) :-             // it is true that a factorial of X is Y, when all following are true:     X1 is X - 1,                   // there is a X1, equal to X - 1,     factorial(X1, Z),              // and it is true that factorial of X1 is Z,      Y is Z * X.                    // and Y is Z * X 

Both styles allow using mathematical expressions in the programs.