逻辑和函数编程之间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).

---

我不明白的是:

这两种不同的编程语言如何表现不同？

---

我们在哪里做出差异,以便将它们归类为基于功能或基于逻辑的编程语言？

就我而言,它们完全相同,调用递归函数直到它终止.

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

重要的是,我们可以将其用作真正的关系,这在各个方向都是有意义的.

例如,我们可以问:

是否有两个整数X,并Y 使得他们的GCD是3？

也就是说,我们可以在使用这种关系等方向过!给定两个整数,我们不仅可以计算他们的GCD.没有!我们也可以问,使用相同的程序:

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

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

?- 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.

这是一个真正的关系,它比两个参数的函数更通用!

有关更多信息,请参阅clpfd.

Answer 2

GCD示例仅略微涉及逻辑编程和函数编程之间的差异,因为它们彼此之间的距离比命令式编程更接近.我将专注于Prolog和OCaml,但我相信它具有很强的代表性.

逻辑变量和统一:

Prolog允许表达部分数据结构,例如,在node(24,Left,Right)我们不需要指定什么Left和Right代表什么的术语中,它们可以是任何术语.函数式语言可能会插入一个惰性函数或稍后要求的thunk,但是在创建该术语时,我们需要知道要插入什么.

逻辑变量也可以统一(即相等).OCaml中的搜索功能可能如下所示:

let rec find v = function
 | [] -> false
 | x::_ when v = x -> true
 | _::xs (* otherwise *) -> find v xs

虽然Prolog实现可以使用统一而不是v=x:

member_of(X,[X|_]).
member_of(X,[_|Xs]) :-
  member_of(X,Xs).

为简单起见,Prolog版本有一些缺点(参见下面的回溯).

回溯:

Prolog的优势在于连续实例化易于撤消的变量.如果您使用变量尝试上述程序,Prolog将为您返回所有可能的值:

?- member_of(X,[1,2,3,1]).
X = 1 ;
X = 2 ;
X = 3 ;
X = 1 ;
false.

当您需要探索搜索树时,这尤其方便,但需要付出代价.如果我们没有指定列表的大小,我们将连续创建满足我们属性的所有列表 - 在这种情况下无限多:

?- member_of(X,Xs).
Xs = [X|_3836] ;
Xs = [_3834, X|_3842] ;
Xs = [_3834, _3840, X|_3848] ;
Xs = [_3834, _3840, _3846, X|_3854] ;
Xs = [_3834, _3840, _3846, _3852, X|_3860] ;
Xs = [_3834, _3840, _3846, _3852, _3858, X|_3866] ;
Xs = [_3834, _3840, _3846, _3852, _3858, _3864, X|_3872] 
[etc etc etc]

这意味着您需要更加小心使用Prolog,因为终止更难控制.特别是,这样做的旧式方式(切割操作员!)很难正确使用,并且仍然有一些关于最近方法的优点的讨论(推迟目标(例如dif),约束算法或者具体化的if) .在函数式编程语言中,回溯通常通过使用堆栈或回溯状态monad来实现.

可逆程序:

也许使用Prolog的另一个开胃菜:函数式编程有一个评估方向.我们只能使用该find函数来检查某些v是否是列表的成员,但是我们无法询问哪些列表满足此要求.在Prolog中,这是可能的:

?- Xs = [A,B,C], member_of(1,Xs).
Xs = [1, B, C],
A = 1 ;
Xs = [A, 1, C],
B = 1 ;
Xs = [A, B, 1],
C = 1 ;
false.

这些正是具有三个元素的列表,其中包含(至少)一个元素1.遗憾的是,标准算术谓词不可逆,并且两个数字的GCD始终是唯一的这一事实是您在功能和逻辑编程之间找不到太多差异的原因.

总结一下:逻辑编程具有变量,允许更容易的模式匹配,可逆性和探索搜索树的多个解决方案.这是以复杂的流量控制为代价的.根据问题,更容易进行回溯执行(有时会受到限制)或者添加回溯到功能语言.