11

我一直在和 Brian Beckman 一起看这个 MSDN 视频，我想更好地理解他所说的话：

每个命令式程序员都会经历这个阶段，学习可以用表查找替换函数

现在，我是一名从未上过大学的 C# 程序员，所以也许在某个地方，我错过了其他人都学会理解的东西。

布赖恩是什么意思：

函数可以用表查找代替

是否有这样做的实际例子，它是否适用于所有功能？他给出了 sin 函数的例子，我可以理解，但我如何更一般地理解这个？

4

3 回答 3

15

Brian 刚刚表明函数也是数据。一般来说，函数只是一个集合到另一个集合y = f(x)的映射：集合 {x} 到集合 {y}: 的映射f:X->Y。这些表也是映射：[x1, x2, ..., xn] -> [y1, y2, ..., yn].

如果函数在有限集上运行（编程中就是这种情况），那么它可以替换为表示该映射的表。正如 Brian 所提到的，每个命令式程序员都会经历这个阶段，即出于性能原因，可以用表查找替换函数。

但这并不意味着所有功能都可以或应该轻松地替换为表格。这仅意味着您理论上可以为每个功能做到这一点。所以结论是函数是数据，因为表是（当然在编程的上下文中）。

于 2012-12-07T17:33:32.793 回答
5

Mathematica 中有一个可爱的技巧，它创建一个表作为评估函数调用作为重写规则的副作用。考虑经典的慢斐波那契

fib[1] = 1
fib[2] = 1
fib[n_] := fib[n-1] + fib[n-2]

前两行为输入 1 和 2 创建表条目。这与说的完全相同

fibTable = {};
fibTable[1] = 1;
fibTable[2] = 1;

在 JavaScript 中。Mathematica 的第三行说“请安装一个重写规则，fib[n_]在将模式变量替换为n_出现的实际参数之后，将替换任何出现的fib[n-1] + fib[n-2]。” 重写器将迭代此过程，并最终fib[n]在指数次数的重写后产生 的值。这就像我们在 JavaScript 中使用的递归函数调用形式

function fib(n) {
  var result = fibTable[n] || ( fib(n-1) + fib(n-2) );
  return result;
}

请注意，在进行递归调用之前，它首先检查表中我们显式存储的两个值。Mathematica 求值器自动执行此检查，因为规则的呈现顺序很重要——Mathematica 首先检查更具体的规则，然后检查更一般的规则。这就是为什么 Mathematica 有两种赋值形式，=并且:=： 前者用于特定规则，其右侧可以在定义规则时进行评估；后者适用于在应用规则时必须评估其右侧的一般规则。

现在，在 Mathematica 中，如果我们说

fib[4]

它被重写为

fib[3] + fib[2]

然后到

fib[2] + fib[1] + 1

然后到

1 + 1 + 1

最后到 3，这在下一次重写时不会改变。你可以想象，如果我们说fib[35]，我们会产生巨大的表达式，填满内存，融化 CPU。但诀窍是用以下内容替换最终的重写规则：

fib[n_] := fib[n] = fib[n-1] + fib[n-2]

这表示“请用一个表达式替换每个出现的值fib[n_]，该表达式将为值安装新的特定规则fib[n]并产生值。” 这个运行得更快，因为它扩展了规则库——值表！-- 在运行时。

我们可以在 JavaScript 中做同样的事情

function fib(n) {
  var result = fibTable[n] || ( fib(n-1) + fib(n-2) );
  fibTable[n] = result;
  return result;
}

这比以前定义的 fib 运行得快得多。

这称为“自动记忆化”[原文如此——不是“记忆化”而是“记忆化”，就像为自己创建备忘录一样]。

当然，在现实世界中，您必须管理创建的表的大小。要检查 Mathematica 中的表格，请执行

DownValues[fib]

要在 JavaScript 中检查它们，只需

fibTable

在诸如 Node.JS 支持的 REPL 中。

于 2012-12-07T23:11:31.940 回答
2

在函数式编程的上下文中，存在引用透明性的概念。对于任何给定的参数（或参数集），可以将引用透明的函数替换为其值，而不会改变程序的行为。

参考透明度

例如，考虑一个接受 1 个参数n的函数F。F 是参照透明的，因此F(n)可以替换为在n处评估的F值。它对程序没有任何影响。

在 C# 中，这看起来像：

public class Square
{
    public static int apply(int n)
    {
        return n * n;
    }

    public static void Main()
    {
        //Should print 4
        Console.WriteLine(Square.apply(2));
    }
}

（我对 C# 不是很熟悉，来自 Java 背景，所以如果这个例子在语法上不太正确，请原谅我）。

很明显，当使用参数 2 调用时，函数apply不能有任何其他值，因为它只是返回其参数的平方。函数的值仅取决于其参数n；换句话说，参考透明度。

Console.WriteLine(Square.apply(2))那么我问你，和之间有什么区别Console.WriteLine(4)。答案是，根本没有区别，因为所有意图都是目的。我们可以遍历整个程序，将 的所有实例替换为Square.apply(n)的返回值Square.apply(n)，结果将完全相同。

那么，Brian Beckman 关于用表查找替换函数调用的声明是什么意思？他指的是引用透明函数的这种属性。如果Square.apply(2)可以替换为4对程序行为没有影响，那么为什么不在第一次调用时缓存值，并将其放入由函数参数索引的表中。的值的查找表Square.apply(n)看起来有点像这样：

              n: 0 1 2 3 4  5  ...
Square.apply(n): 0 1 4 9 16 25 ...

对于任何对的调用，我们可以简单地在表中找到nSquare.apply(n)的缓存值，而不是调用函数，并将函数调用替换为该值。很明显，这很可能会大大提高程序的速度。

于 2012-12-07T17:49:48.073 回答