高階函數謎題：雙倍調用

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