函数式编程与术语重写之间的联系

Question

我对术语重写系统的使用很感兴趣，我发现术语重写“有助于函数式程序的基本推理”，但我不能理解它的意思。我没有使用过函数式编程，但我知道它的主要原则，比如纯函数和不变性。尽管如此，我还是不明白基本的推理是指什么。另外，它是否以某种方式与术语重写的倒置有关？

Answer 1

它们之所以“相连”，是因为它们依赖于相同的概念：everything is an expression

• 在术语重写中，通过搜索表达式中的模式来执行计算，然后将匹配的表达式(或子表达式)更改为其他表达式(重写)。作为一个非常简单的例子，表达式加法可以转换成表达式5，因为有一条重写规则(我们称之为“数值加法”)知道如何执行这样的规则:函数式编程语言，一个函数是“一等公民”的语言，它可以说是“一切都是一个表达式，包括一个函数”。因此，可以将函数指定为函数(或过程)调用的参数，或者函数(或过程)可以返回函数(higher-order functions)，就像对原始类型所做的那样。

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