邪恶的语言声称功能性编程语言是“阶乘写作语言”。 这通常被定义为Haskell语言，但是我们将从对Haskell和许多其他语言的功能编程工具的子集（Scheme）产生重大影响的功能语言开始。 至少map和for-each ， filter和reduce以及apply和eval成为了我们最喜欢的编程语言，如果不是来自Scheme的话，那么来自那里。
考虑一些写阶乘计算的可能方法。 同时，您可以对Scheme编程语言有所了解。 我认为这种美妙的语言值得。
我有10个编写函数定义的选项，可以将其简化为3种主要的计算方法：传统的线性递归计算过程，迭代，生成数字序列，然后进行卷积乘法。 我建议更详细地考虑这些选项。 在此过程中，我们将考虑：尾递归优化，高阶函数和元编程，递延计算，无限列表，备忘录，在Scheme中创建静态变量的方法以及卫生宏。
为了进行实验，我们使用了良好的旧方言Scheme R5RS和流行的美术原则“最小的手段-最大的印象”。
所有Scheme实例都是在DrRacket 6.2中以R5RS模式准备的。 运行时测量是在OpenSUSE Leap 15 OS环境中的Guile 2.0中进行的。
首先，您可以递归定义阶乘，然后简单地在Scheme上重写公式：
(define (factorial-classic n) (if (zero? n) 1 (* n (factorial-classic (- n 1)))))
结果是定义了一个用于计算阶乘的函数的定义（就Scheme而言，是一个过程，尽管实际上它是一个函数），可以在无数的编程指南中看到，从H. Abelson和D. Sassman的不朽著作“计算机程序的结构和解释”开始。
您可以像这样阅读和理解此代码：factorial n 在那边 1 如果 n=0 否则- n cdot（n−1）！ 。 因此，此代码对应于数学中采用的阶乘的递归定义。 我们唯一不检查从属关系的东西 n 非负数。
由于是递归的，因此上面的代码包含对值的明显限制 n ：递归调用数据将累积在堆栈上，直到 n 不会达到0。这可能会导致堆栈溢出 n 。
如何取消此限制？ 有必要优化尾部递归：重写代码，以使递归调用变为尾部 （即过程中的最后一个）。 这将使Scheme解释器可以执行优化-用迭代计算代替递归计算。
如果您使用上本书作者的建议，则可以获得以下内容：
(define (factorial-classic-tco n) (define (iteration product counter) (if (> counter n) product (iteration (* product counter) (+ counter 1)))) (iteration 1 1))
该代码是一个常见示例，从“计算机程序的结构和解释”这本书开始，通常在其上解释尾递归的优化。
这是经典。 但是Scheme本身就是灵活性，是否可以用根本不同的方式编写相同的东西？ 最好甚至更短？ 例如，根据条目 n！=1 cdot2 cdot3 cdot〜 cdots〜 cdotn 形成一个序列 1 之前 n （或来自 n 之前 1 ），然后通过乘法将其折叠？ 幸运的是，在Scheme中，这非常简单，这要归功于内置的apply过程，该过程将具有任意数量参数的过程应用于列表：
(define (iota n) (define (iteration sequence i) (if (> in) sequence (iteration (cons i sequence) (+ i 1)))) (iteration '() 1)) (define (factorial-fold n) (apply * (iota n)))
由于“代码和数据的统一性”（正如他们有时所说的Lisp家族的语言一样），Scheme以其方便的符号计算而闻名。 我们使用此功能：我们形成一个表达式来计算数字的阶乘 n 然后计算：
(define (factorial-eval n) (define expression `(* ,@(iota n))) (eval expression (interaction-environment)))
符号“单引号”表示准引号。 无需准引用，可以使用代码(cons '* (iota n))获得用于进一步计算的表达式。 单引号（引号，引号）表示*必须完全按名称（符号）而不是对应值（此处为-过程）的形式替换为表达式。 因此， n=3 我们得到(* 3 2 1) 。 此列表是Scheme中的一个表达式。 它的价值可以在一个合适的环境中执行，最重要的是-在一个包含内置程序和程序中我们定义的程序的环境(interaction-environment)中。 实际上，这就是我们在factorial-eval主体中所做的事情。
Scheme支持延迟计算。 受Scheme严重影响的Haskell使用了一种惰性计算模型，即 在声明这些计算的结果之前，不会计算表达式的值。 这允许程序具有无穷列表等特殊的数据结构。 如果仅从中获取进一步计算所需的部分，则程序将不会循环运行：
ghci> take 4 [1 ..] [1,2,3,4]
表达式[1 ..]生成一个无限的整数列表。 take 4表达式从此列表中获取前4个元素。 由于后续列表项保持无人认领，因此不会计算它们。
在Haskell获得 n！ 从无尽的列表中，您可以这样写：
factorials :: [Integer] factorials = next 0 1 where next n fact = let n' = n + 1 in fact : next n' (fact * n') factorial :: Integer -> Integer factorial n = factorials !! fromIntegral n
ghci> take 7 $ factorials [1,1,2,6,24,120,720] ghci> factorial 6 720
使用几种形式的Scheme delay / force让我们尝试做类似的事情。 delay关键字创建了一个对表达式值进行评估的承诺。 force关键字指示执行这些计算，然后计算并存储结果值。 重复访问时，不会执行新的计算，但是会返回先前计算的值。
在Lisp家族的语言中，列表是成对构造的。 为了构造无限列表，我们引入了“惰性对”的类型-一对，其中第一个元素是计算值，第二个是计算值的承诺。 为此，我们需要用懒惰的版本来补充Lisp家族语言（ cons ， car ， cdr ）的“神圣三位一体”：
(define-syntax lazy-cons (syntax-rules () ((_ first second) (cons first (delay second))))) (define lazy-car car) (define (lazy-cdr lazy-pair) (force (cdr lazy-pair)))
lazy lazy-cons对的构造函数被实现为宏。 这样做是为了避免在创建该对的第二个元素时计算其值。
这个想法是创建一个无休止的值列表，然后从中获取所需的内容。 为此，请定义通过索引获取元素的过程的惰性版本：
(define (lazy-list-ref lazy-list index) (if (zero? index) (lazy-car lazy-list) (lazy-list-ref (lazy-cdr lazy-list) (- index 1)))) (define (generate-factorials) (define (next nn!) (define n+1 (+ n 1)) (lazy-cons n! (next n+1 (* n! n+1)))) (next 0 1))
这里n! n+1是变量的名称。 在Scheme中，与其他语言相比，很少有不能在标识符中使用的字符。
请注意，无限列表生成器generate-factorials不包含递归方法。 但是，它不会循环，因为调用它时，只会计算列表的开头，而尾部将由一个计算值的承诺表示。
现在您可以定义 n！ 如何获得 n 析因表的第th个元素：
(define lazy-factorials (generate-factorials)) (define (factorial-lazy n) (lazy-list-ref lazy-factorials n))
可以用 此外，如果在解释程序的一个会话中计算了不同数量的阶乘，则计算将比严格版本中的计算更快，因为惰性列表中的某些值已经被计算出来。
顺便说一下，Scheme上的代码与Haskell上的代码非常接近。 因此，接收声明!! 大约对应于lazy-list-ref过程lazy-list-ref构造函数:对应于lazy-cons 。 相应地，因为Haskell尽管声称自己是一个惰性计算模型，但是与Scheme中的delay / force不同，它不记得计算出的值。
顺便说一句，为了提高生产率，您可以应用已经计算出的值的存储-存储。 我们将把计算出的值存储在一个关联列表中，其中键是数字，而值是它们的阶乘。 调用时，我们将在列表中查找已经计算出的值。 如果该值在列表中，我们将返回此存储的值。 如果该值不在列表中，我们将对其进行计算，将其放入列表中，然后才返回。 为了确保此列表始终与被调用函数一起使用，而不是在全局环境中，我们将其放置在静态变量中：
(define factorial-memoized (let ((memo '())) (lambda (n) (let ((memoized (assq n memo))) (if memoized (cadr memoized) (if (zero? n) 1 (let ((computed (* n (factorial-memoized (- n 1))))) (set! memo (cons (list n computed) memo)) computed)))))))
方案中的静态变量查看代码
(define proc (let ((static-var initial-value)) (lambda args ...)))
是方案接受的使用静态变量创建过程的方式。 可以通过一个简短的示例方便地解释这种通知的原理-一个返回呼叫数量的过程：
(define count (let ((n 0)) (lambda () (set! n (+ n 1)) n)))
在一个解释器会话中，第一个呼叫(count)将返回1，第二个-2，第三个-3，依此类推。 如何运作？
没有语法糖， count的定义如下所示：
(define count ((lambda (n) (lambda () (set! n (+ n 1)) n)) 0))
因此，自由包含n不带参数(lambda () (set! n (+ n 1)) n)与名称count相关联。 事实证明， n在(lambda () (set! n (+ n 1)) n)的外部环境中定义的，这意味着n的值将在count调用之间保留。 程序启动时，由于将(lambda (n) ...)应用于参数0，因此将值n初始化为零(lambda (n) ...)因此，在全局环境中不存在n ，但始终可以从count访问。
通过在一个解释器会话中重复计算各种数字的阶乘，该实现还有望提高性能。
当然，尾递归优化也可以在这里进行：
(define factorial-memoized-tco (let ((memo '())) (lambda (n) (define (iteration product counter) (cond ((> counter n) product) (else (set! memo (cons (list counter product) memo)) (iteration (* product counter) (+ counter 1))))) (iteration 1 1))))
读者可能会说：“为什么这些舞蹈要用铃鼓呢？” 在命令式编程语言中，可以简单地编写相同的东西-通过循环，它可以快速运行并且没有不必要的内存开销。 Scheme具有用于命令式编程的子集，还具有用于组织循环的一种方法-do的一种特殊形式 。 在其帮助下编写的阶乘的计算过程可能如下所示：
(define (factorial-do n) (define product 1) (do ((i 1 (+ i 1))) ((> in) product) (set! product (* product i))))
do构造相当通用，这就是为什么它不太可读的原因。 以命令式的方式组织自己的周期不是更好吗？ 宏将帮助您：
(define-syntax for (syntax-rules () ((_ (variable init test step) . body) (let loop ((variable init)) (if test (begin (begin . body) (loop step)))))))
由于解释器优化了尾递归，我们得到了一个在命令式编程语言中习惯的循环。 通过优化尾递归，堆栈将不会增长。
为以下项定义阶乘：
(define (factorial-for n) (define product 1) (for (i 1 (<= in) (+ i 1)) (set! product (* product i))) product)
如何运作在此示例中，表达式(for (i 1 (<= in) (+ i 1)) (set! product (* product i)))将与语法规则的模式(_ (variable init test step) . body)匹配。 将执行以下替换：
for → _ i → variable 1 → init (<= in) → test (+ i 1) → step (set! product (* product i)) → body
从这里，语法规则模板将生成以下代码：
(define (factorial-for n) (define product 1) (let loop ((i 1)) ; (if (<= in) ; (begin (begin (set! product (* product i))) ; (loop (+ i 1))))) ; for product)
还有另一个看起来与命令式for循环类似的选项-带有内置的for-each过程：
(define (factorial-for-each n) (define product 1) (for-each (lambda (i) (set! product (* product i))) (iota n)) product)
强大的Scheme语言！ 性能如何？
我们将使用GNU Guile来衡量性能-在这种环境下，您可以最简单地衡量评估表达式所需的时间。
Guile的工作方式如下：将程序的源代码编译为字节码，然后由虚拟机执行。 这只是运行Scheme程序的一种实现，也是几种可能的方式之一，还有其他一些： Racket （使用JIT编译）， Chicken Scheme （使用“诚实的”解释或编译为C的子集）等。 显然，这些环境中程序的局限性和性能可能会略有不同。
我们将以一定值进行测量 n 。 应该是什么 n ？ 因此，最大的 n 将能够“应付”建议的选项。 使用默认的Guile 2.0设置，在具有Intel Core i5和4 GB RAM的PC上，我得到以下信息：
| 程序 | 问题 |
|---|
factorial-classic | 堆栈溢出 n>10\，000 |
factorial-classic-tco | 不（ n=100\，000 ） |
factorial-fold | 堆栈溢出 n>10\，000 |
factorial-eval | 堆栈溢出 n>8\，000 |
factorial-lazy | 在 n=100\，000 使用交换分区并冻结 |
factorial-memoized | 堆栈溢出 n>10000 仅在首次启动时 |
factorial-memoized-tco | 在 n>1\，000 使用交换分区并冻结 |
factorial-do | 不（ n=100\，000 ） |
factorial-for | 不（ n=100\，000 ） |
factorial-for-each | 不（ n=100\，000 ） |
从这里开始，在 n=8\，000 。 结果显示在下表中，其中 trun -交货时间 tGC -垃圾收集器的运行时间以秒为单位。
对于所有过程，除了延迟和记忆化过程外，从三个开始的结果中获得运行时的最小值和垃圾收集器的相应时间。 n=8\，000 。
对于记忆过程和惰性过程，将指示第一个调用的执行时间，然后指示三个调用中的较小者。
| 程序 | trun 与 | tGC 与 | 注意事项 |
|---|
factorial-classic | 0.051 | 0,034 | |
factorial-classic-tco | 0,055 | 0,041 | |
factorial-fold | 0,065 | 0.059 | |
factorial-eval | 0,070 | 0,040 | |
factorial-lazy | 0,076 | 0,036 | 第一次打电话 |
factorial-lazy | 0.009 | -- | 后续通话 |
factorial-memoized | 0,077 | 0,041 | 第一次打电话 |
factorial-memoized | 0.002 | -- | 后续通话 |
factorial-memoized-tco | 0,077 | 0,041 | 第一次打电话 |
factorial-memoized-tco | 0.002 | -- | 后续通话 |
factorial-do | 0,052 | 0,025 | |
factorial-for | 0.059 | 0,044 | |
factorial-for-each | 0,066 | 0,042 | |
我们有4个可以与大型 n 。 在 n=100\，000 它们具有以下计算和垃圾回收时间：
| 程序 | trun 与 | tGC 与 |
|---|
factorial-classic-tco | 8,468 | 6,628 |
factorial-do | 8,470 | 6,632 |
factorial-for | 8,440 | 6,601 |
factorial-for-each | 9.998 | 7,985 |
您可以看到它没有太大 n 最快，同时最短的是第一个。 相同的选择与阶乘的数学定义最完全一致。 尾递归优化选项在性能上并不逊色于它。 这两种选择都是该语言作者惯用的建议。 该结论在很大程度上是显而易见的：除非另有说明，否则至少对于算法或方法的第一种实现，最好采用这种语言“典型”的方法。
同时，使用Scheme语言，我们可以使用非常有限的一组原语（非常“最小的均值-最大的展示次数”）编写许多用于实现阶乘计算的选项。 因此，尽管它有很长的历史并且不太普及，但是仍然可以推荐这种语言用于研究编程：似乎您可以以任何方便的 方式 （和以任何方式）在其上实现任何东西。