Search code examples
functional-programmingprologschemelogicclpfd

Difference in implementation of gcd between logic and functional programming

I'm currently learning programming language concepts and pragmatics, hence I feel like I need help in differentiating two subbranches of declarative language family.

Consider the following code snippets which are written in Scheme and Prolog, respectively:

;Scheme 
(define gcd
    (lambda (a b)
         (cond ((= a b) a)           
               ((> a b) (gcd (- a b) b))
               (else (gcd (- b a) a)))))

%Prolog
gcd(A, B, G) :- A = B, G = A.
gcd(A, B, G) :- A > B, C is A-B, gcd(C, B, G).
gcd(A, B, G) :- B > A, C is B-A, gcd(C, A, G).

The thing that I didn't understand is:

How do these two different programming languages behave differently?

Where do we make the difference so that they are categorized either Functional or Logic-based programming language?

As far as I'm concerned, they do exactly the same thing, calling recursive functions until it terminates.

Solution

  • Since you are using very low-level predicates in your logic programming version, you cannot easily see the increased generality that logic programming gives you over functional programming.

    Consider this slightly edited version of your code, which uses CLP(FD) constraints for declarative integer arithmetic instead of the low-level arithmetic you are currently using:

    gcd(A, A, A).
gcd(A, B, G) :- A #> B, C #= A - B, gcd(C, B, G).
gcd(A, B, G) :- B #> A, C #= B - A, gcd(C, A, G).

    Importantly, we can use this as a true relation, which makes sense in all directions.

    For example, we can ask:

    Are there two integers X and Y such that their GCD is 3?

    That is, we can use this relation in the other direction too! Not only can we, given two integers, compute their GCD. No! We can also ask, using the same program:

    ?- gcd(X, Y, 3).
X = Y, Y = 3 ;
X = 6,
Y = 3 ;
X = 9,
Y = 3 ;
X = 12,
Y = 3 ;
etc.

    We can also post even more general queries and still obtain answers:

    ?- gcd(X, Y, Z).
X = Y, Y = Z ;
Y = Z,
Z#=>X+ -1,
2*Z#=X ;
Y = Z,
_1712+Z#=X,
Z#=>X+ -1,
Z#=>_1712+ -1,
2*Z#=_1712 ;
etc.

    That's a true relation, which is more general than a function of two arguments!

    See for more information.