functional-programming - 逻辑和函数式编程在gcd的实现上的区别

Question

我目前正在学习编程语言概念和语用学，因此我觉得我需要帮助来区分声明性语言家族的两个子分支。

考虑以下分别用 Scheme 和 Prolog 编写的代码片段:

;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).

我不明白的是:

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?

就我而言，它们做完全相同的事情，调用递归函数直到它终止。

Answer 1

因为你用的很低级 在您的逻辑编程版本中使用谓词，您不会轻易看到逻辑编程为您提供的比函数式编程增加的通用性。

考虑这个稍微编辑过的代码版本，它使用 CLP(FD) 约束 对于声明性整数算术而不是您当前使用的低级算术:

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)。

重要的是，我们可以将其用作真正的 关系 ，这在 中是有意义的所有方向 .

例如，我们可以问:

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

也就是说，我们可以在另一个方向使用这个关系太 !给定两个整数，我们不仅可以计算它们的 GCD。不!我们也可以询问，使用 相同 程序:

?- gcd(X, Y, 3)。
X = Y, Y = 3 ;
X = 6,
Y = 3 ;
X = 9,
Y = 3 ;
X = 12，
Y = 3 ;
等等。

我们还可以发布更一般的查询并仍然获得答案:

?- 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 ;
等等。

这是一个真正的关系，它比两个参数的函数更一般!

见 clpfd想要查询更多的信息。