Functional Programming for Mathematical Computing

Matthias Endler

用於數學運算的函數式程式設計

原文由 Matthias Endler 發布,訂閱此部落格

程式語言幫助我們描述問題的通用解法;而這些解法剛好可以被機器執行。每種程式語言都各有不同的優缺點,原因之一在於其語法與語意大幅影響了它能輕鬆處理的問題範圍。

tl;dr: 我認為函數式程式設計比更常見的指令式做法更適合用來做數學運算。

運用內建抽象來處理數學

語言背後的理念(也就是底層的程式設計典範)形塑了圍繞著它所形成的社群特色。開發者會在語言核心之外,打造出由現成函式庫與框架所構成的獨特生態系。因此,有些語言在特定領域特別強大,例如商業應用(可以想到 Cobol),有些則非常適合系統程式設計(如 C 或 Rust)。

談到用電腦解決數學與數值問題時,可能會想到 Fortran。雖然 Fortran 是通用語言,但它最為人所知的還是科學運算。當然,這個語言當初就是為了這個目的而創造的——因此才有了 Formula Translation(公式翻譯)這個名字。

它在這個領域受歡迎的原因之一,是它提供了一些內建的領域特定關鍵字來表達數學概念,同時也兼顧了效能。舉例來說,它有專門用來表示複數的資料型別——COMPLEX——以及一個名為 DIMENSION 的關鍵字,這個詞與數學術語十分相近,可用來建立陣列與向量。

指令式與函數式風格

內建關鍵字雖然有助於將語言的表達能力擴展到特定的問題領域,但這種做法有著嚴重的限制。無止盡地擴充語言核心並不可行;那只會讓語言更難維護、也更難學習。因此,多數語言提供了其他抽象化的方式——例如函式副程式類別物件——來將程式拆解成更小、更易於管理的部分。這些機制或許有助於控制程式的複雜度,但在處理數學問題時,必須小心不要讓樣板程式碼模糊了原本的解法。

範例一:階乘

舉例來說,假設問題是要將下列計算正整數 n 階乘的公式,轉譯為程式碼:

階乘的數學定義:n! = 1 * 2 * 3 … * n

以上公式若用指令式風格的 Java 來實作,可能會長成這樣:

public static long fact(final int n) {
    if (n < 0) {
        // Negative numbers not allowed
        return 0;
    }
    long prod = 1;
    for (int i = 1; i <= n; ++i) {
        prod *= i;
    }
    return prod;
}

對於這麼簡短的問題定義來說,這是個相當冗長的解法。(請注意,刻意寫成從 1 到 n 的顯式迴圈是有用意的;遞迴函式雖然會更短,但它使用了一個在數學公式中並未出現的概念。)

此外,這個程式包含了許多語言專屬的關鍵字,例如 publicstaticSystem.err.println()。除此之外,程式設計師還必須為所有使用的變數明確指定資料型別——這是一項煩人的義務。

這一切都模糊了原本的數學定義。

將它與下列用函數式語言(如 Haskell)寫成的版本相比。

fact n = product [1..n]

這幾乎是將問題定義直接轉譯為程式碼。它不需要顯式的型別、不需要暫存變數,也不需要存取修飾子(如 public)。

範例二:內積

有人可能會說,上述 Haskell 程式的簡潔,是因為該語言剛好為這個特定任務提供了合適的抽象(也就是 product 關鍵字與 [1..n] 的區間語法)。因此,讓我們來看看一個在 Haskell 和 Java 中都沒有內建的簡單函式:兩個向量的內積。其數學定義如下:

向量內積的數學定義:a·b= aibi =a1b1+a2b2+···+anbn =abT

對於三維向量,可以寫成

三維向量的內積:a·b = a1 * b1 + a2 * b2 + a3* b3

首先是 Haskell 的實作:

type Scalar a = a
data Vector a = Vector a a a deriving (Show)
dot :: (Num a) => Vector a -> Vector a -> Scalar a
(Vector a1 a2 a3) `dot` (Vector b1 b2 b3) = a1*b1 + a2*b2 + a3*b3

請注意,數學上的型別各自只需用一行就能定義。另外請注意,我們是以中綴表示法來定義 dot 函式,也就是將 dot 的第一個引數放在函式名稱前面,第二個引數放在後面。這樣一來,程式碼看起來就更接近其數學上的對等寫法。上述函式的呼叫範例如下

(Vector 1 2 3) ’dot’ (Vector 3 2 1)

這樣寫簡短、精確且易於閱讀。

接下來是用 Java 寫的類似實作。

public static class Vector<T extends Number> {
    private T x, y, z;

    public Vector(T x, T y, T z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    public double dot(Vector<?> v) {
        return (x.doubleValue() * v.x.doubleValue() +
                y.doubleValue() * v.y.doubleValue() +
                z.doubleValue() * v.z.doubleValue());
        }
    }

    public static void main(String[] args) {
        Vector<Integer> a = new Vector<Integer>(3, 2, 1);
        Vector<Integer> b = new Vector<Integer>(1, 2, 3);
        System.out.println(a.dot(b));
    }
}

若要讓 Vector 有適當的文字表示方式,還需要覆寫 toString() 方法。在 Haskell 中,如程式碼所示,只需衍生自 Show typeclass 即可。

建立新的抽象

如果函式與型別仍不足以寫出直觀的程式,Haskell 還提供了簡單的結構來建立新的運算子與關鍵字,進而擴充語言核心本身。這讓領域特定語言得以實現,也讓開發者能更直接地處理實際問題本身,而不必繞著程式語言本身的特性打轉(例如記憶體管理或陣列走訪)。Haskell 擁抱這樣的概念;Java 則沒有這類功能。

結論

我在這裡並不是要抨擊 Java 或吹捧 Haskell。兩種語言各有其適用的場景。我只是選擇了 Java,因為很多程式設計師都看得懂它。

這項比較更著重於函數式與指令式兩種做法在數值與符號運算上的差異;而在這方面,我每天都會選擇函數式的做法。它能去除雜亂,產生優雅的解法。它提供了在高抽象層次上工作、以數學語言來表達的便利方法,然而這些優勢仍被許多程式設計師所忽視。

Abraham H. Maslow 在其 1966 年的著作The Psychology of Science 中的觀察似乎相當貼切:

「我想,如果你唯一的工具是一把槌子,那麼把所有東西都當成釘子來對待是很誘人的。」

本文章由 muse-spark-1.2-contributor 進行翻譯

留言