以大家的老朋友 C# 談 FP

這幾年由於 Reactive Programming 興起,使得 FP 這古老的 Programming Paradigm 又成為顯學,FP 大都使用 JavaScript、Haskell … 等偏 FP 語言闡述,很少人使用 C# 來談 FP,本系列將使用大家的老朋友 C#,帶領大家一步一步進入 FP 世界。

Version


C# 7.2

本文為 Funtional Programming in C# 一書第一章的讀後心得

Introduction


  • FP 是一種 Programming Paradigm,不是 Design Pattern 也不是 Framework,更不是 Language
  • 是一種以 function 為中心的 思考方式程式風格
  • 有別於目前主流 Imperative、OOP,所以被稱為邪教 ?

Imperative

以 command 或 statement 方式,一行一行的執行程式

Function


在討論什麼是 Functional Programming 之前,我們先來定義什麼是 Function :

Mathematical Function

fp000

在數學裡,function 就是 x 與 y = f(x) 的對應關係。

f(x) 結果只與 x 的輸入有關,不會其他任何東西相關。

fp001

  • Domain : 所有的 x 稱為 定義域
  • Codomain : 所有 可能f(x) 稱為 對應域
  • Range : 所有 實際f(x) 稱為 值域

這些都不是什麼高深的數學,在國一的代數我們就會了

1
2
3
4
int func(int x)
{

return 2 * x + 1;
}
  • int : 為 Codomain
  • int x : 為 Domain

Pure Function : Codomain 只與 Domain 相關。

Pure Function 就是 Mathematical Function 在程式語言的實踐

Programming Function

1
2
3
4
5
6
7
8
int z = 1;
int w = 0;

int func(int x)
{

w = 3;
return 2 * x + z + 1;
}

func() 可以讀取 func() 外面的 z,甚至可以改寫 func() 外部的 w,這就是所謂的 Side Effect。

因為讀取與寫入 function 的外部變數造成 Side Effect,使得變數改變的 時機 變得很重要,也就是所謂的 Race Condition。

OS 恐龍書花了很多的篇幅都在解決 Race Condition (Lock、Mutex ….)。

Functional Programming


把 function 當成 data 使用,並避免 State Mutation

  • Function as data (把 function 當成 data 使用)
  • No state mutation (不要修改 data,只要修改資料,就需擔心可能 Race Condition)

Function as Data


比 function 當成 data 使用

  • 能把 function 當 input、把 function 當 return
  • 能將 function 指定給變數
  • 能將 function 存進 Collection

以前 data 能怎麼用,function 就怎麼用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using static System.Console;
using static System.Linq.Enumerable;

namespace ConsoleApp
{
class Program
{
static void Main(string[] args)
{

string triple(int x) => (x * 3).ToString();

Range(1, 3)
.Select(triple)
.ToList()
.ForEach(WriteLine);
}
}
}
// 3
// 6
// 9

10 行

1
string triple(int x) => (x * 3).ToString();

使用 C# 7 的 Local Function 宣告 triple()

12 行

1
Range(1, 3)

使用 Range() 建立 IEnumerable<int>,因為有 using static System.Linq.Enumerable;

using static 在 FP 建議使用,會讓 code 更精簡

13 行

1
.Select(triple)

Select() 就是 FP 的 Map(),為 IEnumerable 的 Extension Method。

Map() 一樣,Select() 並沒有修改原本的 Range(1, 3),而是 return 新的 IEnumerable。

triple 為 function,但如 data 般傳進 Select()Select() 也就是所謂的 Higher Order Function。

在 LINQ 的 . ,若使用 Extension Method,則不是 OOP 的 Method,而是 FP 的 Pipeline

14 行

1
2
.ToList()
.ForEach(WriteLine);

因為 List 才有 ForEach(),所以要先轉成 List。

直接使用 WriteLine,因為有 using static System.Console;

No State Mutation


不要修改 data

7, 6, 1 只取 奇數,並且 由小到大 排序。

Imperative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using System;
using System.Collections.Generic;

namespace ConsoleApp
{
class Program
{
private static void Main()
{

var original = new List<int> {7, 6, 1};
var result = GetOddsByAsc(original);

foreach (var iter in result)
{
Console.WriteLine(iter);
}
}

private static IEnumerable<int> GetOddsByAsc(IEnumerable<int> original)
{

var result = new List<int>();

foreach (var iter in original)
{
if (iter % 2 == 1)
{
result.Add(iter);
}
}

result.Sort();
return result;
}
}
}
// 1
// 7

21 行

1
var result = new List<int>();

Imperative 典型寫法會先建立一個 result 變數。

23 行

1
2
3
4
5
6
7
foreach (var iter in original)
{
if (iter % 2 == 1)
{
result.Add(iter);
}
}

根據 條件 不斷修改變數。

31 行

1
result.Sort();

直接修改 result 資料排序。

Functional

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using System.Collections.Generic;
using System.Linq;
using static System.Console;

namespace ConsoleApp
{
class Program
{
static void Main()
{

var original = new List<int> {7, 6, 1};
var result = GetOddsByAsc(original);

result.ForEach(WriteLine);
}

private static IEnumerable<int> GetOddsByAsc(IEnumerable<int> original)
{

bool isOdd(int x) => x % 2 == 1;
int asc(int x) => x;

return original
.Where(isOdd)
.OrderBy(asc);
}
}
}
// 1
// 7

22 行

1
2
3
return original
.Where(isOdd)
.OrderBy(asc);

original 經由 pipeline 方式,先經過 Where() 找出 奇數,最後再以 asc 排序。

Code 就類似 講話,看不到實作細節,可讀性高。

不需要建立 result 暫存變數,也沒有修改 originalresult,從頭到尾都沒有修改 data,這就是所謂的 No State Mutation,而是每次 pipeline 都建立新的 data。

  • LINQ 的 Where() 就是 FP 的 filter()
  • LINQ 的 OrderBy() 就是 FP 的 sort()

Parallel Computation


1
2
3
4
5
6
7
8
9
10
11
using static System.Linq.Enumerable
using static System.Console;

var nums = Range(-10000, 20001).Reverse().ToList();
// => [10000, 9999, ... , -9999, -10000]
Action task1 = () => WriteLine(nums.Sum());
Action task2 = () => { nums.Sort(); WriteLine(nums.Sum()); };

Parallel.Invoke(task1, task2);
// prints: 92332970
// 0

由於 Sort 會直接去改 nums,造成了 Race Condition。

1
2
3
4
5
6
7
8
9
10
11
using static System.Linq.Enumerable
using static System.Console;

var nums = Range(-10000, 20001).Reverse().ToList();
// => [10000, 9999, ... , -9999, -10000]
Action task1 = () => WriteLine(nums.Sum());
Action task2 = () => WriteLine(nums.OrderBy(x => x).Sum());

Parallel.Invoke(task1, task2);
// prints: 0
// 0

task2 並不會去修改 nums,因此不會 Race Condition。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using System.Collections.Generic;
using System.Linq;
using static System.Console;

namespace ConsoleApp
{
class Program
{
static void Main()
{

var original = new List<int> {7, 6, 1};
var result = GetOddsByAsc(original);

result.ForEach(WriteLine);
}

private static IEnumerable<int> GetOddsByAsc(IEnumerable<int> original)
{

int asc(int x) => x;
bool isOdd(int x) => x % 2 == 1;

return original
.AsParallel()
.Where(isOdd)
.OrderBy(asc);
}
}
}

22 行

1
2
3
4
return original
.AsParallel()
.Where(isOdd)
.OrderBy(asc);

只要加上 AsParallel() 之後,完全無痛升級多核心。

因為 Where(isOdd)OrderBy(asc) 都是 Pure Function,沒有 Side Effect,也就沒有 Race Condition,因此可以放心使用多核心平行運算。

FP vs. OOP


OOP 是大家習慣的編程方式,FP 究竟有哪些觀念與 OOP 不同呢 ?

Encapsulation

  • OOP : data 與 logic 包在 class 內
  • FP : data 與 logic 分家,data 就是 data,logic 就是 function,不使用 class

State Mutation

  • OOP : 繼續使用 Imperative 修改 state
  • FP : No State Mutation => Immutable => No Side Effect => No Race Condition => Pure Function => Dataflow => Pipeline (其實都在講同一件事情)

大部分人最難突破的 FP 點在此,這與傳統程式思維差異很大,為什麼不能改 data 呢 ?

Modularity

  • OOP : 以 class 為單位
  • FP : 以 function 為單元

Dependency

  • OOP : Dependency Injection
  • FP : Higher Order Function (Function Injection)

Loose Coupling

  • OOP : 使用 Interface
  • FP : Function Signature 就是 interface,使用 Function Composition / Function Pipeline

SOLID


SRP

  • OOP : Class 與 Method 要單一職責
  • FP : Module 與 Function 要單一職責

OCP

  • OOP : Interface,使用 Object Composition
  • FP : Function Signature 就是 interface,使用 Function Composition

LSP

  • OOP : 有限度的繼承
  • FP : N/A

ISP

  • OOP : Interface 要盡量小
  • FP : Interface 小到極致就變成 function

DIP

  • OOP : Dependency Injection
  • FP : Higher Order Function

SOLID 原則在 OOP 與 FP 都適用,不過 OOP 與 FP 在實現手法並不一樣,OOP 以 class 實現,FP 以 function 實現

FP 鹹魚翻身


FP 其實是比 OOP 更古老的技術,LISP 早在 1958 年就問世,而 Smalltalk 則在 1972 年發表,但因為 FP 基於數學,且強調 No State Mutation,與 CPU 設計理念不合 (CPU 就是要你不斷改暫存器與記憶體),很多人無法接受而視為 邪教,一直到最近才鹹魚翻身:

  1. 硬體單核心時脈出現瓶頸,CPU 已經無法做出時脈超過 5GHz 以上,因此單執行緒程式速度也面臨瓶頸,但隨著半導體製程進步,單位面積可以塞入更多電晶體,因此 CPU 可以放進更多核心,但 Imperative 寫法依賴 Side Effect,使得多核心很難發揮,但 FP 沒有 Side Effect,很容易多核心平行運算,發揮多核心威力
  2. Side Effect 寫法很難單元測試,因為不保證每次的結果都ㄧ樣,但 FP 的 Pure Function 很適合單元測試
  3. OOP 的 Object Compostion 需依賴 Interface,容易造成 interface 滿天飛與 Over Design,但 FP 的 Function Compostion 不需要額外 interface,只要求你使用 Dataflow 思考,並使用 Pure Function 避免 Side Effect 即可
  4. Reactive Programming 並不適合使用 OOP,但卻異常適合 FP,這使得 FP 找到了 殺手級 應用

C# 適合 FP 嗎 ?


回想 FP 定義 :

  1. Function as Data
  2. No State Mutation

Function as Data

  • C# 從 1.0 就有 Delegate,可以將 function 當成 input 與 output 使用
  • C# 3.0 支援 Lambda,讓 Anonymous Function 更容易實現
  • C# 3.0 支援 Func、Predicate、Action,讓 Anonyoua Delegate 更為方便
  • C# 的 Type Inference 比較弱,必須明確指定 Delegate 或 Func 型別 (不滿意但可接受,希望 C# 對 Type Inference 持續加油)

No State Mutation

  • Primitive Type 只有 stringdatetime 為 Immutable
  • 由於 C# 是從 Imperative 與 OOP 起家,任何 data 預設都是 Mutable,而不像 FP 語言預設 data 都是 Immutable,需自己加上 readonly
  • 自訂型別預設是 Mutable
  • Collection 預設是 Mutable,但已經提供 Immutable Collection

所以大體上除了 Type Inference 與 Immutable 支援比較不足外,C# 7 算是個準 FP 語言,C# 亦持續朝更完整的 FP 邁進 :

  • Record Type (Immutable 自訂 Type)
  • Algebraic Data Type (適合 DDD)
  • Pattern Matching
  • 更強的 Tuple

C# 8 將會是更成熟的 FP 語言。

C# 對 FP 支援

C# 3 與 LINQ

  • LINQ 本質上就是 FP,並不是使用 OOP 技術
1
2
3
4
5
Enumerable
.Range(1, 100)
.Where(i => i % 20 == 0)
.OrderBy(i => -i)
.Select(i => $"{i}%")

Where()OrderBy()Select() 都以 function 為參數,且並沒有去修改原本的 Enumerable.Range(1, 100),完全符合 FP 的基本定義 :

  • Function as Data
  • No State Mutation

且 C# 提供了 Lambda,讓我們以更精簡的方式撰寫 Delegate,對於 FP 這種只使用一次的 Anonymous Function 特別有效,這也使得 C# 更適合寫 FP。

不過 C# 社群大都沒發現 LINQ 的 FP 的本質,只有在處理 IEnumerableIQueryable 才會使用 FP,其他 code 又繼續使用 Imperative 與 OOP,並沒有完全發揮 Functional C# 的潛力,也就是 FP 思維其實沒有深入 C# 社群

C# 6、7

C# 6、7 乍看之下沒有提供實質功能,都是 syntax sugar,若以 OOP 角度來看的確如此,但若以 FP 角度,所有的 syntax sugar 都是為了讓 C# 成為更好的 FP 而準備。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using static System.Math;

public class Circle
{
public double Radius { get; }
public double Circumference => PI * 2 * Radius;

public Circle(double radius) => Radius = radius;

public double Area
{
get
{
double Square(double d) => Pow(d, 2);
return PI * Square(Radius);
}
}

public (double Circumference, double Area) Stats => (Circumference, Area);
}

Using Static

第 1 行

1
2
3
4
5
6
7
8
9
10
using static System.Math;

public double Area
{
get
{
double Square(double d) => Pow(d, 2);
return PI * Square(Radius);
}
}

C# 6 的 using static 讓我們可以直接 PIPow 使用 Math.PIMath.Pow

Q : 為什麼 using static 對 FP 重要 ?

在 OOP,我們必須建立 object instance,然後才能用 method,主要是因為 OOP 的 instance method 會以 Imperative 與 Side Effect 方式使用 data,也就是 field,因此不同的 object instance 就有不同的 field,正就是 OOP 的 Encapsulation : data 與 logic 合一。

但因為 FP 是 data 與 logic 分家,logic 會以 static method 實現,也沒有 field,因此就不須建立 object instance,因此類似 Math 這種 instance variable 在 FP 就顯得沒有意義且多餘,因為 static method 都是 Pure Function,根本不需要 instance variable。

Immutable Type

第 5 行

1
2
public double Radius { get; }
public Circle(double radius) => Radius = radius;

C# 目前的缺點就是沒有 直接 支援 Immutable 自訂型別,C# 6 透過宣告 getter-only 的 auto-property,compiler 會自動建立 readonly 的 field,且只能透過 constructor 設定其值,達到 No State Mutation 的要求。

Expression Body

第 6 行

1
public double Circumference => PI * 2 * Radius;

Property 可直接使用 Expression Body 語法。

Q : 為什麼 Expression Body 對 FP 重要 ?

因為 FP 很習慣寫 小 property小 function,最後再靠 Function Composition 與 Function Pipeleine 組合起來,為了這種只有一行的 小 function ,還要加上 {},除了浪費行數,也不符合 FP 的 Lambda 極簡風。

C# 6 一開始只有在 Property 與 Method 支援 Expression Body,但 C# 7 可以在 Constructor、Destructor、Getter 與 Setter 全面使用 Expression Body。

Local Function

12 行

1
2
3
4
5
get
{
double Square(double d) => Pow(d, 2);
return PI * Square(Radius);
}

Local Function 使我們在 Method 內可直接建立 function。

Q : 為什麼 Local Function 對 FP 重要 ?

由於 FP 常常需要建立 小 function,最後再 compose 或 pipeline,C# 7 之前只能宣告 Func 型別變數並配合 Lambda,但 Func 寫法可讀性實在不高,這也使的 C# 族群不太願意抽 小 function

但 Local Function 的可讀性就很高,也符合一般 function 的 syntax,讓我們更願意抽 小 function 來 compose。

Better Tuple

1
public (double Circumference, double Area) Stats => (Circumference, Area);

為了回傳 Tuple 外,還可以對 element 指定有意義的名字,讓 client 使用 Tuple 時有 Intellisense 支援。

Q : 為什麼 Tuple 對 FP 重要 ?

因為 FP 會在 Function Composition 與 Function Pipeline 時,拆很多小 function 實現 Dataflow,而這些 小 function 在傳遞資料時,就會使用 Tuple,但為這種只使用一次的 data 定義自訂型別,又會造成自訂型別滿天飛的問題,但若使用 Tuple 就可避免此問題。

C# 如何實現 Function ?


這裡的 Function 是所謂的 Mathematical Function,也就是 Pure Function。

Static Method

由於 Pure Function 要求 output 只與 input 有關,也就是 Pure Function 沒有 Side Effect,因此會直接使用 Static Method,如 System.Math 一樣,且還可搭配 C# 6 的 using static,讓程式碼更精簡。

Delegate

FP 要求 Function as Data,也就是 Pure Function 會以參數方式傳進其他 function,C# 1.0 function 包成 Delegate 後,以 Delegate 形式傳進其它 function。

Delegate 要求兩個步驟 :

  • 宣告 Delegate 型別
  • 實作符合 Delegate 型別的 function
1
2
3
4
namespace System
{
public delegate int Comparison<T> (T x, Y x);
}

使用 Delegate 宣告 Comparison 型別。

1
2
3
4
5
6
7
8
9
10
var list = 
Enumerable
.Range(1, 10)
.Select(i => i * 3)
.ToList();

Comparison<int> alphabetically =
(1, r) => l.ToString().CompareTo(r.ToString());

list.Sort(alphabetically);

第 7 行

1
2
Comparison<int> alphabetically = 
(1, r) => l.ToString().CompareTo(r.ToString());

根據 Comparison delegate 型別定義 alphabetically 變數,以 Lambda 描述 function。

若實作不符合 Delegate 定義,compiler 就會報錯,所以 Delegate 也被稱為 Type-Safe Function Pointer。

第 10 行

1
list.Sort(alphabetically);

alphabetically delegate 傳入 List.Sort()

Func & Action

Delegate 讓我們實現 Function as Data,但對於只使用一次的 Anonymous Delegate 型別,到處宣告 Delegate 就類似 interface 一樣,造成檔案爆炸。

1
delegate Greeting Greeter(Person p);

其實相當於

1
Func<Person, Greeting>

.NET Framework 3 之後,以 Func 與 Action 取代 Custom Delegate

Lambda

1
2
3
4
5
6
7
var list = 
Enumerable
.Range(1, 10)
.Select(i => i * 3)
.ToList();

list.Sort((1, r) => l.ToString().CompareTo(r.ToString();

不用再宣告 Comparison<T> Delegate,也不用建立 Comparison<T> 的實作,直接以 Lambda 傳入 List.Sort()

寫 Lambda 時,不用寫型別,compiler 會自動使用 Type Inference 導出參數型別,且會將 Lambda 轉型成 Delegate 型別,判斷是不是符合 List.Sort() 要求

因此 Lamba 雖然寫起來像 弱型別,但絲毫不會影響原本 Delegate 強型別的特性,這就是 Type Inference 強大之處

1
2
3
4
5
6
7
8
var days = Enum.GetValues(typeof(DayOfWeek)).Cast<DayOfWeek>();
// => [Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday]

IEnumerable<DayOfWeek> daysStartingWith(string pattern)
=> days.Where(d => d.ToString().StartsWith(pattern));


daysStartingWith("S")
// => [Sunday, Saturday]

不只 JavaScript 有 Closure,事實上 C# 也是有 Closure。

daysStartingWith() 會回傳 function,但傳入的參數 S 會以 Closure 方式存在於回傳的 function。

Dictionary

既然 Pure Function 只與 input 有關,我們甚至可以使用 查表法 的方式實作 function :

1
2
3
4
5
6
7
var frenchFor = new Dictionary<bool, string>
{
[true] = "Vari",
[false] = "Faux"
};

frenchFor[true];

C# 6 提供了新的 Dictionary 初始化語法,甚至可以使用 truefalse 當 key。

實務上有兩種需求很適合使用 Dictionary

  1. 沒有邏輯可言的 data 轉換
  2. 花時間的運算

Conclusion


  • FP 的 function 指的是 Mathematical Function,也就是 Pure Function,而不是 Programming Function
  • FP 屬於 Paradigm 層次,不是 framework 也不是程式語言,只要語言能支援 First-Class Function,就能以 FP 風格實現,若能支援 Immutable 與 Type Inference 更佳
  • C# 目前已經支援大部分的 FP 功能,隨著 C# 8 的發佈,FP 支援將更為完整

Reference


Math is Fun, Domain, Range and Codomain
Enrico Buonanno, Functional Programming in C#

2018-08-06