高階函數謎題：雙倍調用

函數是計算機編程的核心。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. 請先思考結果是什麼，再執行代碼驗證。想一想為什麼會是這個結果？