functional-programming - 函数式编程和术语重写之间的联系

Question

我对术语重写系统的使用很感兴趣，我发现术语重写“有助于对函数式程序进行基本推理”，但我不明白它的含义。我没有使用过函数式编程，但我知道主要原则，比如纯函数和不变性。尽管如此，我还是不明白基本推理是指什么。此外，它是否与术语重写的反转有关？

Answer 1

它们是“连接的”，因为它们依赖于相同的概念：一切都是表达式：

• 在术语重写中，计算是通过搜索表达式中的模式，然后将匹配的表达式（或子表达式）更改为其他表达式（重写）来执行的。作为一个非常简单的示例，表达式2 + 3可以转换为表达式5，因为有一个重写规则（我们称为“数值加法”）知道如何执行这种转换。

• 在函数式编程语言中，函数是语言的“一等公民”，可以说是“一切都是表达式，包括函数”。因此，可以将函数指定为函数（或过程）调用的参数，或者函数（或过程）可以返回函数（高阶函数），就像使用原始类型一样。

此外，由于在术语重写中“一切都是表达式”，它们中的每一个都必须产生一个值，就像一个函数一样，因此术语重写的计算可以看作是函数的连续应用。