逻辑编程和函数式编程在gcd实现上的区别
Difference in implementation of gcd between logic and functional programming
我目前正在学习编程语言概念和语用学，因此我觉得我需要帮助来区分声明式语言家族的两个子分支。
考虑以下分别用 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?
就我而言，它们做完全相同的事情，调用递归函数直到它终止。
从一个例子来看，区别不是很明显。编程语言根据它们支持的一些特性被分类为逻辑、功能……，因此它们的设计是为了让每个领域的程序员更容易（逻辑、功能……）。例如，命令式编程语言（如 c）与面向对象的语言（如 java、C++）非常不同，这里的差异更为明显。
更具体地说，在您的问题中，Prolog 编程语言采用了逻辑编程哲学，这对于对数理逻辑有所了解的人来说是显而易见的。 Prolog 有谓词（而不是函数——基本上 几乎 相同）return true 或 false 基于我们定义的 "world" 例如什么事实和我们已经定义了子句，定义了哪些数学事实等等……所有这些都是数学逻辑（命题逻辑和一阶逻辑）继承的。所以我们可以说 Prolog 被用作逻辑模型，它使逻辑问题（如游戏、拼图......）更容易解决。此外，Prolog 具有通用语言所具有的一些特性。例如，您可以在示例中编写一个程序来计算 gcd:
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).
在您的程序中，如果 G 与 A、B 的 GCD 统一，则在 returns 中使用谓词 gcd 为 TRUE，并且您使用多个子句来匹配所有情况。当您查询 gcd(2,5,1). 时， return 为真（请注意，在 shceme 等其他语言中，您不能将结果作为参数给出），而如果您查询 gcd(2,5,G).，它将 G 与 A 的 gcd 统一,B 和 returns 1, 这就像问 Prolog G 应该是什么才能使 gcd(2,5,G). 为真。所以你可以理解，这完全取决于谓词何时成功，因此你可以有多个解决方案，而在函数式编程语言中你不能。
- 函数式语言基于函数，所以总是 return 相同
结果类型。这并不总是在 Prolog 中，你可以有一个谓词
predicate_example(Number,List). 和查询 predicate_example(5,List). which returns List=... （一个列表）并且还查询
predicate_example(Number,[1,2,3]). 和 return N=...（一个数字）。
- 结果应该是唯一的，在数学中，函数是一种关系
在一组输入和一组允许的输出之间，属性 每个输入都与 恰好一个 输出
相关
- 应该清楚return编辑的变量是什么参数
例如 gcd 函数的类型是：
N * N -> R 所以得到属于 N（自然数）和 returns gcd 的 A、B 参数。但是序言（在您的程序中进行了一些更改）可以 return 参数 A，因此查询 gcd(A,5,1). 将给出所有可能的 A ，使得谓词 gcd successes,A=1,2,3,4,5 。
- Prolog为了找到gcd想方设法选择
points 所以在每一步它都会尝试你们所有的三个子句并且会
找到所有可能的解决方案。函数式编程语言
另一方面，类似的功能应该有明确定义的独特步骤
找到解决方案。
所以你可以理解函数式语言和逻辑语言之间的区别可能并不总是显而易见的，但它们基于不同的哲学思维方式。
想象一下在 Scheme 中解决井字游戏或 N 皇后问题或人羊狼卷心菜问题会有多难。
GCD 示例仅略微涉及了逻辑编程和函数式编程之间的差异，因为它们彼此之间的关系比命令式编程要近得多。我会专注于 Prolog 和 OCaml，但我认为它很有代表性。
逻辑变量和合一：
Prolog 允许表达部分数据结构，例如在术语 node(24,Left,Right) 中，我们不需要指定 Left 和 Right 代表什么，它们可以是任何术语。函数式语言可能会插入一个 lazy function or a 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 会 return 你所有可能的值：
?- 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 始终唯一的事实，这就是为什么您无法在函数式编程和逻辑编程之间找到太多区别的原因。
总而言之：逻辑编程具有变量，可以更轻松地进行模式匹配、可逆性和探索搜索树的多种解决方案。这是以复杂的流量控制为代价的。根据问题的不同，回溯执行有时会受到限制，或者将回溯添加到函数式语言中会更容易。
由于您在逻辑编程版本中使用的是非常低级 谓词，因此您无法轻易看出逻辑编程为您提供的通用性高于函数式编程。
考虑这个略微编辑过的代码版本，它使用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?
也就是说，我们可以在other方向too使用这个关系！给定两个整数，我们不仅可以计算它们的 GCD。不！我们可以也使用相同的程序询问：
?- gcd(X, Y, 3).
X = Y, Y = 3 ;
X = 6,
Y = 3 ;
X = 9,
Y = 3 ;
X = 12,
Y = 3 ;
etc.
我们还可以post更一般的查询并且仍然获得答案：
?- 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。
我目前正在学习编程语言概念和语用学，因此我觉得我需要帮助来区分声明式语言家族的两个子分支。
考虑以下分别用 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?
就我而言，它们做完全相同的事情，调用递归函数直到它终止。
从一个例子来看，区别不是很明显。编程语言根据它们支持的一些特性被分类为逻辑、功能……，因此它们的设计是为了让每个领域的程序员更容易（逻辑、功能……）。例如，命令式编程语言（如 c）与面向对象的语言（如 java、C++）非常不同，这里的差异更为明显。
更具体地说，在您的问题中，Prolog 编程语言采用了逻辑编程哲学，这对于对数理逻辑有所了解的人来说是显而易见的。 Prolog 有谓词（而不是函数——基本上 几乎 相同）return true 或 false 基于我们定义的 "world" 例如什么事实和我们已经定义了子句，定义了哪些数学事实等等……所有这些都是数学逻辑（命题逻辑和一阶逻辑）继承的。所以我们可以说 Prolog 被用作逻辑模型，它使逻辑问题（如游戏、拼图......）更容易解决。此外，Prolog 具有通用语言所具有的一些特性。例如，您可以在示例中编写一个程序来计算 gcd:
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).
在您的程序中，如果 G 与 A、B 的 GCD 统一，则在 returns 中使用谓词 gcd 为 TRUE，并且您使用多个子句来匹配所有情况。当您查询 gcd(2,5,1). 时， return 为真（请注意，在 shceme 等其他语言中，您不能将结果作为参数给出），而如果您查询 gcd(2,5,G).，它将 G 与 A 的 gcd 统一,B 和 returns 1, 这就像问 Prolog G 应该是什么才能使 gcd(2,5,G). 为真。所以你可以理解，这完全取决于谓词何时成功，因此你可以有多个解决方案，而在函数式编程语言中你不能。
- 函数式语言基于函数，所以总是 return 相同
结果类型。这并不总是在 Prolog 中，你可以有一个谓词
predicate_example(Number,List).和查询predicate_example(5,List).which returns List=... （一个列表）并且还查询predicate_example(Number,[1,2,3]).和 return N=...（一个数字）。 - 结果应该是唯一的，在数学中，函数是一种关系 在一组输入和一组允许的输出之间，属性 每个输入都与 恰好一个 输出 相关
- 应该清楚return编辑的变量是什么参数
例如 gcd 函数的类型是：
N * N -> R所以得到属于 N（自然数）和 returns gcd 的 A、B 参数。但是序言（在您的程序中进行了一些更改）可以 return 参数 A，因此查询gcd(A,5,1).将给出所有可能的 A ，使得谓词 gcd successes,A=1,2,3,4,5 。 - Prolog为了找到gcd想方设法选择 points 所以在每一步它都会尝试你们所有的三个子句并且会 找到所有可能的解决方案。函数式编程语言 另一方面，类似的功能应该有明确定义的独特步骤 找到解决方案。
所以你可以理解函数式语言和逻辑语言之间的区别可能并不总是显而易见的，但它们基于不同的哲学思维方式。
想象一下在 Scheme 中解决井字游戏或 N 皇后问题或人羊狼卷心菜问题会有多难。
GCD 示例仅略微涉及了逻辑编程和函数式编程之间的差异，因为它们彼此之间的关系比命令式编程要近得多。我会专注于 Prolog 和 OCaml，但我认为它很有代表性。
逻辑变量和合一：
Prolog 允许表达部分数据结构，例如在术语 node(24,Left,Right) 中，我们不需要指定 Left 和 Right 代表什么，它们可以是任何术语。函数式语言可能会插入一个 lazy function or a 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 会 return 你所有可能的值：
?- 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 始终唯一的事实，这就是为什么您无法在函数式编程和逻辑编程之间找到太多区别的原因。
总而言之：逻辑编程具有变量，可以更轻松地进行模式匹配、可逆性和探索搜索树的多种解决方案。这是以复杂的流量控制为代价的。根据问题的不同，回溯执行有时会受到限制，或者将回溯添加到函数式语言中会更容易。
由于您在逻辑编程版本中使用的是非常低级 谓词，因此您无法轻易看出逻辑编程为您提供的通用性高于函数式编程。
考虑这个略微编辑过的代码版本，它使用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
XandYsuch that their GCD is 3?
也就是说，我们可以在other方向too使用这个关系！给定两个整数，我们不仅可以计算它们的 GCD。不！我们可以也使用相同的程序询问：
?- gcd(X, Y, 3). X = Y, Y = 3 ; X = 6, Y = 3 ; X = 9, Y = 3 ; X = 12, Y = 3 ; etc.
我们还可以post更一般的查询并且仍然获得答案：
?- 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。