編程範式|程式世界裡的編程範式，探索語言本質

• 2019 年 10 月 3 日
• 筆記

最近看了一些關於編程範式的文章，簡要做一些小結和記錄

什麼是編程範式

在現實生活中，為了適配各種規格的螺帽，我們需要許多種類的螺絲刀。

在編程世界中，靜態語言有許多種類的數據類型。

不過，我們可以發現，無論是傳統世界，還是編程世界，我們都在干一件事情，就是通過使用一種更為通用的方式，抽象和隔離，讓複雜的「世界」變得簡單一些。

C語言的範式例子1：swap函數

原版，swap交換變數（只能交換int型）

void swap(int* x, int* y)  {      int tmp = *x;      *x = *y;      *y = tmp;  }  

改進版，使用void * 抽象化數據類型，範式編程：

void swap(void* x, void* y, size_t size)  {       char tmp[size];       memcpy(tmp, y, size);       memcpy(y, x, size);       memcpy(x, tmp, size);  }  

函數介面中增加了一個size參數。一旦用了 void* 後，類型就會被「抽象」掉，編譯器不能通過類型得到類型的尺寸了，所以需要我們手動加上一個類型長度的標識。

函數的實現中使用了memcpy()函數。因為類型被「抽象」掉了，所以不能用賦值表達式了，很有可能傳進來的參數類型還是一個結構體，不過，為了要交換這些複雜類型的值，我們只能使用記憶體複製的方法了。

函數的實現中使用了一個temp[size]數組。這就是交換數據時需要用的 buffer，會用 buffer 來做臨時的空間存儲。

C語言的範式例子2：search函數

原版C語言函數，搜索target在整型數組中的位置：

int search(int* a, size_t size, int target) {      for(int i=0; i<size; i++) {          if (a[i] == target) {              return i;          }      }      return -1;  }  

把search函數變為泛型，使之不僅能查找整型數組，也能查找適配其他傳入的各種類型參數。

參數a，可以遍歷的數組、結構體數組等
target，void *，不定類型的數據（以適配範式）
cmpFn，函數，用戶程式設計師自定義的各種數據的比較函數

int search(void* a, size_t size, void* target,      size_t elem_size, int(*cmpFn)(void*, void*) )  {      for(int i=0; i<size; i++) {          // 這裡不用memcmp比較，是因為 針對傳入的數據類型是結構體類型時，memcmp會比較記憶體地址。          //使用 unsigned char * 計算地址          if ( cmpFn ((unsigned char *)a + elem_size * i, target) == 0 ) {              return i;          }      }      return -1;  }    //整數比較函數  int int_cmp(int* x, int* y)  {      return *x - *y;  }    //字元串比較函數  int string_cmp(char* x, char* y){      return strcmp(x, y);  }    //結構體比較函數  typedef struct _account {      char name[10];      char id[20];  } Account;    int account_cmp(Account* x, Account* y) {      int n = strcmp(x->name, y->name);      if (n != 0) return n;      return strcmp(x->id, y->id);  }    

上面的泛型search函數缺陷：只支援順序類型的數據結構，遇到複雜的圖、樹等無法抽象化非順序型的數據容器

另外C語言還可以使用宏定義來泛型化。

泛型編程

一個良好的泛型編程需要解決如下幾個泛型編程的問題：
1.演算法的泛型；
2.類型的泛型；
3.數據結構（數據容器）的泛型。

就像前面的search()函數，裡面的 for(int i=0; i<len; i++) 這樣的遍歷方式，只能適用於順序型的數據結構的方式迭代，如：array、set、queue、list 和 link 等。並不適用於非順序型的數據結構。
如哈希表 hash table，二叉樹 binary tree、圖 graph 等這樣數據不是按順序存放的數據結構（數據容器）。所以，如果找不到一種泛型的數據結構的操作方式（如遍歷、查找、增加、刪除、修改……），那麼，任何的演算法或是程式都不可能做到真正意義上的泛型。

比如，如果我要在一個 hash table 中查找一個 key，返回什麼呢？一定不是返回「索引下標」，因為在 hash table 這樣的數據結構中，數據的存放位置不是順序的，而且還會因為容量不夠的問題被重新 hash 後改變，所以返回數組下標是沒有意義的。

對此，我們要把這個事做得泛型和通用一些。如果找到，返回找到的這個元素的一個指針（地址）會更靠譜一些。

所以，為了解決泛型的問題，我們需要動用以下幾個 C++ 的技術。
1.使用「模板」來抽象類型，這樣可以寫出類型無關的數據結構（數據容器）。
2.使用一個「迭代器」來遍歷或是操作數據結構內的元素。

C++的範式例子1:search函數

template<typename T, typename Iter>  Iter search(Iter pStart, Iter pEnd, T target)  {      for(Iter p = pStart; p != pEnd; p++) {          if ( *p == target )              return p;      }      return NULL;  }  

在 C++ 的泛型版本中，我們可以看到：

使用typename T抽象了數據結構中存儲數據的類型。

使用typename Iter，這是不同的數據結構需要自己實現的「迭代器」，這樣也就抽象掉了不同類型的數據結構，迭代器需要數據結構自己去實現。

然後，我們對數據容器的遍歷使用了Iter中的++方法，這是數據容器需要重載的操作符，這樣通過操作符重載也就泛型掉了遍歷，
為了兼容原有 C 語言的編程習慣我們不用標準介面Iter.Next()，不用Iter.GetValue()來取代*。

在函數的入參上使用了pStart和pEnd來表示遍歷的起止。

使用Iter來取得這個「指針」的內容。這也是通過重載 取值操作符來達到的泛型。

說明：所謂的Iter，在實際程式碼中，就是像vector::iterator或map<int, string>::iterator這樣的東西。這是由相應的數據容器來實現和提供的（迭代器）。

C++ STL源碼中的find函數

template<class InputIterator, class T>    InputIterator find (InputIterator first, InputIterator last, const T& val)  {    while (first!=last) {      if (*first==val) return first;      ++first;    }    return last;  }  

C++的範式例子2: Sum 函數

C語言版求和函數

long sum(int *a, size_t size) {      long result = 0;      for(int i=0; i<size; i++) {          result += a[i];      }      return result;  }  

C++泛型版(有問題)：

template<typename T, typename Iter>  T sum(Iter pStart, Iter pEnd) {      T result = 0;      for(Iter p=pStart; p!=pEnd; p++) {          result += *p;      }      return result;  }  

這裡默認了 T result = 0;也就是T假設了 Iter 中出來的類型是T。0假設了類型是int；如果類型不一樣，就會導致轉型的問題

改進版，需要迭代器
Iter在實際調用者那會是一個具體的像vector::iterator的東西
在這個聲明中，int已經被傳入Iter中了；所以定義result的T應該可以從Iter中來。這樣就可以保證類型是一樣的，而且不會有被轉型的問題。

C++ 泛型編程：迭代器

template <class T>  class container {  public:      class iterator {      public:          typedef iterator self_type;          typedef T   value_type;          typedef T*  pointer;          typedef T&  reference;            reference operator*();          pointer operator->();          bool operator==(const self_type& rhs)；          bool operator!=(const self_type& rhs)；          self_type operator++() { self_type i = *this; ptr_++; return i; }          self_type operator++(int junk) { ptr_++; return *this; }          ...          ...      private:          pointer _ptr;      };        iterator begin();      iterator end();      ...      ...  };  

1.首先，一個迭代器需要和一個"數據容器"(類)在一起，因為裡面是對這個容器的具體的程式碼實現，對這個容器的迭代。
2.它需要重載一些操作符，比如：取值操作*、成員操作->、比較操作==和!=，還有遍歷操作++，等等。
3.然後，還要typedef一些類型，比如value_type，告訴我們容器內的數據的實際類型是什麼樣子。
4.還有一些，如begin()和end()的基本操作。
5.我們還可以看到其中有一個pointer _ptr的內部指針來指向當前的數據（注意，pointer就是 T*）。

有了迭代器，我們讓用戶自型傳入模板T的類型，解決T result = 0出現的問題
最終Sum的範式寫法：

template <class Iter>  typename Iter::value_type  sum(Iter start, Iter end, T init) {      typename Iter::value_type result = init;      while (start != end) {          result = result + *start;          start++;      }      return result;  }      int main(){      container<int> c;      container<int>::iterator it = c.begin();      sum(c.begin(), c.end(), 0);      return 0;  }

這就是整個 STL 的泛型方法，其中包括：

1.泛型的數據容器；
2.泛型數據容器的迭代器；
3.泛型的演算法；

reduce函數式編程

如果我們有一個 員工結構體，再想用sum函數來求和怎麼辦？

struct Employee {      string name;      string id;      int vacation;      double salary；  };    

結構體數組增加了很多數據類型，以前sum函數就不知道怎麼辦了吧，

vector<Employee> staff;  //total salary or total vacation days?  sum(staff.begin(), staff.end(), 0);  

這個例子而言，我想計算員工薪水裡面最高的，和休假最少的，或者我想計算全部員工的總共休假多少天。那麼面對這麼多的需求，我們是否可以泛型一些呢？怎樣解決這些問題呢？
引入更抽象化的函數編程——reduce函數

template<class Iter, class T, class Op>  T reduce (Iter start, Iter end, T init, Op op) {      T result = init;      while ( start != end ) {          result = op( result, *start ); //這裡時重點          start++;      }      return result;  }  

reduce函數 需要增加一個參數 op，這個參數可以是一個函數，來完成我們想要的業務操作。

比如下面的業務操作函數：我們來求員工的工資和、最大工資

double sum_salaries =    reduce( staff.begin(), staff.end(), 0.0,                {return s + e.salary;}  );    double max_salary =    reduce( staff.begin(), staff.end(), 0.0,                {return s > e.salary? s: e.salary; } );  

C++STL中的count_if()：

下面這個示例中，先定義了一個函數對象counter（struct里定義函數）。這個函數對象需要一個Cond的函數對象，它是個條件判斷函數，如果滿足條件，則加 1，否則加 0。

然後，用上面的counter函數對象和reduce函數共同來打造一個counter_if演算法

當條件滿足的時候我就記個數，也就是統計滿足某個條件的個數。

//對象counter，滿足Cond函數的條件，就將參數c 加 1。  template<class T, class Cond>  struct counter {      size_t operator()(size_t c, T t) const {          return c + (Cond(t) ? 1 : 0);      }  };    //count_if函數，返回上面文章中編寫使用的reduce函數  template<class Iter, class Cond>  size_t count_if(Iter begin, Iter end, Cond c){      return reduce(begin, end, 0, counter<Iter::value_type, Cond>(c));  }  

當我需要統計薪資超過 1 萬元的員工的數量時，參數3為Cond條件函數，{ return e.salary > 10000; }一行程式碼就完成了

size_t cnt = count_if(staff.begin(), staff.end(), { return e.salary > 10000; });  

函數式編程

修飾器模式

面向對象編程

原型編程範式

邏輯編程範式

前兩小段，是編程範式的簡單介紹，C語言到C++的演化，
未完待續。。。。。