高阶函数谜题：双倍调用

函数是计算机编程的核心。Scheme 等 Lisp 系编程语言提供了完善的函数功能。如可在任意代码位置创建函数，一个函数的参数或返回值也可以是函数，这种函数称为高阶函数 (Higher-Order Function) 。合理使用高阶函数可帮助 构建合理的抽象层次 ，更好的复用代码， 提升代码可读性和健壮性 。一些语言将这些特性称为函数式编程。

C 语言不一样， C 专注简单和高性能，一跃成为并稳居最广泛使用的编程语言老大。天下语言多为 C 系， Lisp 系语言虽用户数量不多，但仍保持其强韧的生命力。如今这两系语言有互相融合 (互相吸收优点) 的趋势， Scheme 有 ChezScheme 这样的高性能实现，许多 C 系语言也在积极引入和完善函数功能支持，甚至扎根底层的 C++ 也在 C++ 11 引入了 lambda 等许多函数式编程特性。

MIT 著名编程入门教材《计算机程序的构造和解释》(《Structure and Interpretation of Computer Programs》，英文名简称 SICP) 练习 1.41 给出了一道高阶函数练习题，看起来似乎简单，做起来才发现暗藏玄机。

练习

练习题目使用 Scheme 语言描述如下：

;; 定义一个函数 inc , 返回其参数增加 1 后的值.
(define (inc x) (+ x 1))

;; 定义一个高阶函数 double , 其返回函数将连续调用两次输入函数 (双倍调用) .
(define (double f)
  (lambda (x) (f (f x))))

;; 请问: 下列表达式的值是多少 ?
(((double (double double)) inc) 5)

打开 Scheme 解释器，依次输入上述 3 条语句，即可揭晓答案。

高阶函数是一个通用概念，这个练习不局限于 Scheme 或 Lisp 系语言，使用其他编程语言 (支持函数式编程的) 也很容易重写这个练习。

JavaScript

使用 JavaScript 可简单重写此练习代码如下。许多语言 (主要是 C 系语言?) 中 double 通常表示双精度浮点数类型，因此我们将此函数重命名为 doubleApplied 以避免冲突。

function inc(x) {
    return x + 1;
}

function doubleApplied(f) {
    return function (x) { return f(f(x)); };
}

console.log(doubleApplied(doubleApplied(doubleApplied))(inc)(5));

将以上代码保存为脚本文件 "double-applied.js" ，安装 Nodejs 后执行 node double-applied.js 即可看到结果。或者直接打开浏览器 Web 开发者工具，在 Web 控制台输入执行以上 JavaScript 代码即可看到结果。

C++

C++ 11 引入了许多函数式编程特性，此练习可使用 C++ 代码重写如下。C++ 是静态类型语言，因此增加了一些静态类型适配代码。使用 C++ 模板可编写类型安全的通用模板函数 doubleApplied ，编译时将校验此函数的参数必须是一个函数 (std::function) 。

#include <iostream>
#include <functional>

int inc(int x) {
    return x + 1;
}

template<typename T>
std::function<T(T)> doubleApplied(std::function<T(T)> f) {
    return [=](T x) { return f(f(x)); };
}

int main(int argc, char *argv[]) {
    // doubleApplied 参数类型为 C++ 标准 std::function 类型, 
    // 调用 doubleApplied 前先将输入参数转换为此类型.

    // 将普通原生函数 inc 转换为 std::function 类型.
    std::function<int(int)> inc{::inc};

    // 将参数类型为 std::function<int(int)> 的 doubleApplied 模板函数实例 (模板参数为 int) 转换为 std::function 类型.
    std::function<std::function<int(int)>(std::function<int(int)>)> doubleAppliedFnInt{::doubleApplied<int>};

    std::cout << doubleApplied(doubleApplied(doubleAppliedFnInt))(inc)(5) << std::endl;
}

CentOS 7 和 Ubuntu 16.04 及以上版本自带的 g++ 编译器均已支持 C++ 11 。将以上完整代码保存为文件 "double-applied.cxx" ，执行如下命令编译执行此程序，即可看到输出结果。

g++ -std=c++11 double-applied.cxx -o double-applied && ./double-applied

Java

Java 8 起支持使用函数式接口和 lambda 表达式等进行函数式编程，此练习可使用 Java 代码重写如下。

import java.util.function.UnaryOperator;

public interface DoubleApplied {

    static Integer inc(Integer x) {
        return x + 1;
    }

    static <T> UnaryOperator<T> doubleApplied(UnaryOperator<T> f) {
        // Java 函数式接口需要使用 apply 等方法调用.
        return (x) -> f.apply(f.apply(x));
    }

    static void main(String[] args) {
        // 将参数为 UnaryOperator<Integer> 类型的 doubleApplied 方法转换为函数式接口 (类似 C++ 模板函数实例化) .
        UnaryOperator<UnaryOperator<Integer>> doubleAppliedFnInt = DoubleApplied::doubleApplied;
        System.out.println(doubleApplied(doubleApplied(doubleAppliedFnInt)).apply(DoubleApplied::inc).apply(5));
    }

}

Java 11 支持直接执行 Java 源码文件，即自动在内存中将 Java 源码编译为字节码并执行之。将以上完整代码保存为文件 "DoubleApplied.java" ，执行 java DoubleApplied.java 即可看到输出结果。

思考

不同编程语言只是语法的不同，所表达的意思是相同的。使用 Scheme JavaScript C++ Java 几种语言实际验证，得到了相同的结果 (不同才有问题) 。从语法角度看， Scheme 语言是最简洁清晰的。

请思考：

1. 使用你偏好的其他语言能否实现此练习代码？如何实现？
2. 请先思考结果是什么，再执行代码验证。想一想为什么会是这个结果？