编程的科学/你能降到多低？

回顾上一章，关于微积分的符号d表示“取微小部分”。让我们练习取一个数字的微小部分，同时学习一些编程。并且，因为你必须作为未来的计算机科学家，你必须学会放手和变得狂野，我们将取一个微小部分的微小部分，以及那个非常微小部分的微小部分，以此类推，无限地。

此时，您应该在您的系统上安装 Sway。

使用 Sway 解释器

我们首先启动 Sway 解释器，Sway 是您将学习的编程语言。启动后，解释器会用一个提示符来奖励你

   sway>

此提示符表示您需要输入一些代码。当您这样做时，解释器将告诉您运行（或评估或执行）该代码的结果。

   sway> 3;
   INTEGER: 3

要退出解释器，请键入<Ctrl-d>或<Ctrl-c>。这些按键组合通过按住 Control 键并在同一时间轻敲 'd' 或 'c' 键生成。^[1]在这里，我们输入了一个 3 后跟一个分号（分号告诉解释器我们已经完成了代码输入）。Sway（实际上是 Sway 解释器）通过说 3 是一个值为 3 的整数来响应。当然，我们已经知道这一切，所以解释器似乎并没有那么有用。但你知道 43 乘以 112 等于 4816 吗？

   sway> 43 * 112;
   INTEGER: 4816

Sway 知道！让我们利用解释器擅长数学运算的事实来计算一个大数字的微小部分。假设一个微小部分是 ${\frac {1}{16}}$ 整体。^[2]首先，让我们计算一下 ${\frac {1}{16}}$ 作为十进制数或实数，因为这样更容易输入

   sway> 1/16;
   SOURCE CODE ERROR
   file stdin,line 1
   an expression was expected, found token of type BAD_NUMBER
   error occurred prior to: 16;[END OF LINE]

糟糕。Sway 不喜欢紧跟着 '1' 的 '/'. 事实上，在大多数情况下，Sway 要求在除号等符号周围留有空格。让我们再试一次

   sway> 1 / 16;
   INTEGER: 0

好多了，至少我们得到了答案而不是错误。但是，解释器似乎并不擅长数学。如果我们戴上夏洛克·福尔摩斯的帽子思考一下，我们会发现解释器说 1 除以 16 的结果是整数，但我们知道它应该是实数。事实证明，Sway 语言，就像大多数编程语言一样，使用一条规则，即组合两种相同类型的事物会产生相同类型的结果。在这种情况下，零恰好是小于所需结果的最大整数。换句话说，解释器截断了实数的小数部分，并给了我们剩下的整数。让我们试验一下是否如此

   sway> 7 / 2;
   INTEGER: 3

似乎是。所以回到我们最初的问题，我们如何找到 1 除以 16 的实数结果？让我们将数字作为实数而不是整数输入

   sway> 1.0 / 16.0;
   REAL_NUMBER: 0.0625000000

好多了！

现在让我们计算一下一百万的微小部分是多少（使用我们对微小的假设）

   sway> 1000000 * 0.0625;
   REAL_NUMBER: 62500.0000000000

六万二千五百。从绝对意义上讲仍然很大，但比一百万小得多。让我们变得狂野和疯狂，取一个微小部分的微小部分

   sway> 1000000 * .0625 * .0625;
   REAL_NUMBER: 3906.2500000000

大约 4000。小得多。

此时，您应该熟悉Sway 原语和组合，包括 Sway 的优先级和结合性规则。

使用变量

我们是否应该继续取越来越小的部分？

在我们这样做之前，我必须承认，我内心深处是一个懒惰的人，就像大多数计算机科学家一样。^[3]输入所有这些数字实在是太麻烦了！我将使用两个简短的符号来分别表示一百万和分数

   sway> var x = 1000000;
   INTEGER: 1000000
   sway> var f = .0625;
   REAL_NUMBER: 0.0625000000

我所做的是创建了一个变量来代替一百万，以及一个变量来代替分数，分别为x和f。^[4]现在我可以使用这些变量来代替数字。让我们检查一下我是否做对了

   sway> x * f * f;
   REAL_NUMBER: 3906.2500000000

看起来我做对了。让我们更进一步

   sway> x * f * f * f;
   REAL_NUMBER: 244.1406250000

变量似乎是一种减少输入量的好方法。唯一的缺点是记住变量代表什么。这就是为什么用一种便于您回忆其含义的方式命名变量非常重要的原因。通常，单个字母变量名'不是一个好主意（尽管此规则存在例外）。

要了解更多信息，请参阅Sway 变量。

使用函数

我们可以继续这样做，但您还没有理解我的懒惰的深度。即使反复输入* f对于我的敏感性来说也太多。我将定义（或编写）一个函数来帮我完成工作（如果您像我一样懒惰，不想自己输入，可以将此函数复制粘贴到解释器中）

   function smaller(amount,fraction)
       {
       inspect(amount * fraction);
       }

无论您是粘贴还是输入，您都应该从解释器中获得以下响应

   sway>     function smaller(amount,fraction)
   more>         {
   more>         inspect(amount * fraction);
   more>         }
   FUNCTION: <function smaller(amount,fraction)>

themore>提示表示 Sway 解释器正在等待更多代码。

在处理函数时，您必须做两件事，（1）定义它们和（2）调用它们。在这里，我们刚刚定义了一个函数；现在我们需要调用它。我们将通过键入函数的名称，后跟一个包含参数的括号列表来调用它。有时我们说这是“将参数传递给函数”。

在调用函数smaller^[5]时，参数的值将绑定到变量amount和fraction，它们在函数定义中的函数名之后找到。这些变量被称为函数的形式参数。这种传递和绑定本质上为我们定义了这些变量。请注意，参数和形式参数确实需要用空格分隔；逗号用作分隔符。

在这些隐式变量定义之后，花括号 {} 之间的代码将被评估，就像您直接将其键入到解释器中一样。这就是我在上一章中说函数可以为您完成工作的原因。如果我们查看我们刚刚定义的函数的代码（或主体），我们会看到一个名为inspect的函数被调用。由于我们还没有定义inspect，因此我们可以假设此函数已存在于解释器中。从它的名称可以推测，它将告诉我们当我们将amount乘以fraction时会发生什么

   sway> smaller(x,f);
   amount * fraction is 62500.000000
   REAL_NUMBER: 62500.000000

这里有很多内容需要解释。首先是x（1000000）的值被绑定到函数smaller的形式参数amount。同样，f（0.0625）的值被绑定到形式参数fraction。然后评估函数smaller的主体，触发对inspect函数的调用。inspect所做的是打印出其文字参数，后跟字符串“ is ”，后跟其参数的值。由于对 inspect 的调用是smaller的最后一件事情，因此inspect返回的任何内容都将由smaller返回。此返回值似乎是已评估的参数。

请注意，解释器报告了两件事。第一个是inspect生成的字符串。第二个是我们之前看到过的返回值报告。我们将对调用函数外部产生影响的操作（在本例中，inspect的打印）称为副作用。

要了解更多信息，请参阅Sway 函数。

递归

现在，到了这一步，你可能在想，我不仅懒惰，而且一定很笨，因为我在编写smaller函数并调用它上面花费了比直接输入更多的精力。

   sway> x * f;
   REAL_NUMBER: 62500.000000

如果这就是我要做的全部，那么你的评估是完全正确的。但我还没有完成。现在我将使smaller变得更加强大。

   function smaller(amount,fraction)
       {
       inspect(amount * fraction);
       smaller(amount * fraction,fraction);
       }

请注意，在调用inspect函数之后，我添加了对smaller函数的调用。当一个函数调用自身时，它被称为递归函数，它表现出递归的特性，并且在递归调用的点上，函数递归。^[6] 进一步注意，在那个内部调用中，smaller的第一个参数将发送一个（希望是）更小的数字到smaller函数。在那个调用中，smaller将再次被调用，并传入一个更小的数字，依此类推。让我们试一试。

   sway> smaller(1000000,.0625);
   amount * fraction is 62500.0000000000
   amount * fraction is 3906.2500000000
   amount * fraction is 244.1406250000
   amount * fraction is 15.2587890625
   amount * fraction is 0.9536743164
   amount * fraction is 0.0596046448
   amount * fraction is 0.0037252903
   amount * fraction is 0.0002328306
   amount * fraction is 1.4551915228e-05
   amount * fraction is 9.0949470177e-07
   ...
   amount * fraction is 0.0000000000e+00
   amount * fraction is 0.0000000000e+00
   amount * fraction is 0.0000000000e+00
   amount * fraction is 0.0000000000e+00
   amount * fraction is 0.0000000000e+00
   amount * fraction is 0.0000000000e+00
   amount * fraction is 0.0000000000e+00
   amount * fraction is 0.0000000000e+00
   encountered a fatal error...
   stack overflow.

哇！除非你的眼睛非常快，否则你看到的只是此输出的底部部分。发生了什么？我们所做的是定义一个函数，当我们调用它时，它陷入了无限循环。无限循环发生是因为我们从未告诉我们的函数何时停止调用自身。因此，它试图无限地调用自身。当然，计算机的内存是有限的，因此在这种特定情况下，调用不可能永远持续下去。^[7] 让我们重新定义我们的函数，以便它在每次检查后暂停，以便我们能够减慢输出速度。

   function smaller(amount,fraction)
       {
       inspect(amount * fraction);
       pause();
       smaller(amount * fraction,fraction);
       }

您可以再次启动 Sway 解释器并将我们修改后的函数定义粘贴进去。

现在，当我们调用我们的函数时，我们将看到此输出（假设您反复按下键盘上的 Enter 键）。

   sway> smaller(1000000,.0625);
   amount * fraction is 62500.0000000000
   
   amount * fraction is 3906.2500000000
   
   amount * fraction is 244.1406250000
   
   amount * fraction is 15.2587890625
   
   amount * fraction is 0.9536743164
   
   amount * fraction is 0.0596046448
   
   amount * fraction is 0.0037252903
   
   amount * fraction is 0.0002328306

您可以通过输入 <Ctrl>-c 来停止解释器，该命令通过在按下 Control 键的同时点击一次“c”键从键盘输入。

我们可以看到amount * fraction很快就会变得非常小。如果您重新开始并继续，您将看到amount * fraction最终达到零。理论上，它不会，但在某个时刻，数量变得小于 Sway 可以表示的数量，因此 Sway 报告为零。

您应该阅读更多关于递归的内容，并在继续之前学习关于if 表达式的内容。

让我们尝试一个新版本的函数，这个函数在停止之前会调用自身给定次数。

   function smaller(x,f,n)
       {
       if (n == 0)
           {
           :done;
           }
       else
           {
           inspect(x);
           smaller(x * f,f,n - 1);
           }
       }

这次，我们有一个新的形式参数n，它表示函数递归调用自身的次数。我们还更改了对inspect的调用以打印出x的值。请注意，递归调用不仅使x变小，还使n变小。当n变得足够小时，函数将返回符号done。

我们必须记住向调用添加一个额外的参数。让我们传入 8 作为递归调用的次数。

   sway> smaller(1000000,.0625,8);
   x is 1000000
   x is 62500.000000
   x is 3906.2500000
   x is 244.14062500
   x is 15.258789062
   x is 0.9536743164
   x is 0.0596046448
   x is 0.0037252903
   SYMBOL: :done

耶！我们的程序停止了无限递归。正式地说，函数内部的if有两个情况：基本情况，它不包含递归调用；和递归情况，它包含递归调用。当基本情况从未达到时，就会发生无限递归循环，通常是由于基本情况条件的陈述错误或对基本情况条件中正在测试的形式参数所取值的范围的误解造成的。

回到微积分

这个找到越来越小的数字的练习与微积分有什么关系？好吧， $d$ 符号表示“取一小部分”。多小？无限小，或者换句话说，由无限次递归调用smaller计算的值。当然，这比我们所能想象的要小，但这并不重要。我们无法理解我们的大脑是如何工作的，但我们相处得还不错，或者至少我们大多数人是这样。

问题

所有公式均使用小学算术优先级编写。

1. 当你组合一个整数和一个实数时会发生什么？

2. 此问题和后续问题指的是smaller的最后一个版本。为什么对smaller的调用返回了一个实数？

3. 重新定义smaller，以便它打印出九次检查而不是八次，对于 8 的相同初始值。

4. 当将零作为计数传递给smaller时会发生什么？

5. 当将 -1 作为计数传递给smaller时会发生什么？为什么？

6. 如果smaller中的递归调用被替换为smaller(x *f,f,n)？为什么？

7. 编写一个 Sway 函数来表示 $y=2x^{a}$ ，并针对 $x=1,2,3$ 和 $a=2,4,6$ 进行评估。

8. 使用前面问题中 $y$ 的 Sway 函数，编写一个新的 Sway 函数 $z=ay$ ，并像以前一样进行评估。

9. 级数是一系列相加的项。如果随着越来越多的项相加，这些项的总和越来越接近一个数字k，那么k被称为该级数的极限。本书用芝诺悖论解释了这一点。假设你距离一堵墙 1 个单位的距离，并且每一步你都走完剩余距离的一半到达墙边（为什么这是一个悖论？）。使用递归和 Sway，定义一个函数zeno(n)来演示此过程。zeno的参数是采取的步数，返回值应该是总行程距离。zeno级数的极限是多少？

10. 令 $g(x)=x^{2}$ 且 $h(x)=(g(1+x)-g(1-x))/(3x)$ 。计算 $h(1)$ ， $h(2)$ ， $h(3)$ 和 $h(0.5)$ 。用 $x$ 表示 $h(x)$ 。在 $-2\leq x\leq 2$ 的范围内绘制 h 的图形。

11. 在魔兽世界（一款流行的大型多人在线角色扮演游戏或简称MMORPG）中，非玩家角色（NPC）造成致命一击的概率公式为 $({\mathit {NPCLevel}}*5-{\mathit {PlayerDefense}})*2\%-15\%$ 。对于 70 级 NPC，将其表示为 $PlayerDefense(x)$ 的函数，并给出使概率为 0 的防御值。

12. 角色升级所需的经验值为 $h(x)=g(x)*(1344-((69-x)*((69-x)*4+3)))+155$ ，其中x为角色等级，并且 $g(x)=5x+45$ 是消灭与角色等级相同的怪物获得的基本经验值。计算 $h(61)$ 、 $h(69)$ 、 $h(0.5)$ 和 $h(1)$ 。用x表示 $h(x)$ 。绘制h在 $61\leq x\leq 69$ 范围内的图像。

脚注

↑ 如果您重新启动 Sway 解释器，可以使用键盘上的向上箭头恢复之前的命令。如果向上翻得太远，可以使用向下箭头以相反的方向浏览之前的命令列表。您也可以编辑之前的命令。
↑ 计算机科学家喜欢 2 的幂，例如 1、2、4、8、16、32 等。这些数字的倒数也备受喜爱。
↑ 懒惰，就像我讨厌做本可以（也应该）自动化的工作。
↑ 变量可以被认为是其他事物的名称。但是，它不是那个事物本身，就像您的名字不是您本人，而是一种方便人们称呼您的方式。
↑ 变量smaller实际上并不是一个函数，而只是我们定义的函数的方便名称。但与其说“由变量smaller命名的函数”，我们通常说“函数smaller”。从技术上讲，这是不正确的，但更简单易懂。
↑ 一些可怜的人会使用动词“recurse”而不是正确的“recur”。Recur表示调用自身，Recurse表示再次发誓。不要犯这个错误，否则人们会认为你无知。
↑ 有一些聪明的语言，其中一些无限递归循环不会占用计算机内存。总有一天，Sway 会变得如此聪明，本节将需要重写。

← 可怕的概念 · 一些这样，一些那样 →

[1] 如果您重新启动 Sway 解释器，可以使用键盘上的向上箭头恢复之前的命令。如果向上翻得太远，可以使用向下箭头以相反的方向浏览之前的命令列表。您也可以编辑之前的命令。

[2] 计算机科学家喜欢 2 的幂，例如 1、2、4、8、16、32 等。这些数字的倒数也备受喜爱。

[3] 懒惰，就像我讨厌做本可以（也应该）自动化的工作。

[4] 变量可以被认为是其他事物的名称。但是，它不是那个事物本身，就像您的名字不是您本人，而是一种方便人们称呼您的方式。

[5] 变量smaller实际上并不是一个函数，而只是我们定义的函数的方便名称。但与其说“由变量smaller命名的函数”，我们通常说“函数smaller”。从技术上讲，这是不正确的，但更简单易懂。

[6] 一些可怜的人会使用动词“recurse”而不是正确的“recur”。Recur表示调用自身，Recurse表示再次发誓。不要犯这个错误，否则人们会认为你无知。

[7] 有一些聪明的语言，其中一些无限递归循环不会占用计算机内存。总有一天，Sway 会变得如此聪明，本节将需要重写。

[1]

[2]

[3]

[4]

[5]

[6]

[7]