元編程 (meta-programming)

元編程 (meta-programming)

術語

meta：英語前綴詞根，來源於希臘文。中國大陸一般翻譯成」元「。

在邏輯學中，可以理解為：關於X的更高層次，同時，這個更高層次的範圍仍然在X的範圍之內。

meta-data

meta-function

meta-bank

meta-verse

meta-programming

因何而生

誕生必然性：需要非常靈活的程式碼來適應快速變化的需求，同時保證性能。

定義

元編程 (meta-programming) 通過操作 程式實體 (program entity)，在 編譯時 (compile time) 計算出 運行時 (runtime) 需要的常數、類型、程式碼的方法。

區別：

一般程式碼的操作對象是數據。

元編程的操作對象是程式碼。code as data。

如果編程的本質是抽象，那麼元編程就是更高層次的抽象。

Metaprogramming is writing code that writes code.

用處

數值計算和類型計算。

  • 提高運行時性能
  • 提高類型安全

程式語言的支援

電腦語言有兩種類型：

  • 從彙編起步，C、C++、Java
  • 從數學模型起步，Lisp、Julia

Lisp是第一個實現了「將程式碼作為數據」的語言。

元編程機制是現代程式語言的標配。

C++：Boost MPL、Facebook fatal（Facebook Template Library）、Blitz++。

Julia：天生自帶。

C++

C++是一個語言聯邦，集眾家之所長。C++之父表示「我只是熟悉」。

五種編程範式

  • 面向過程
  • 面向對象
  • 泛型
  • 模板元
  • 函數式

其中，」模板元「是最難的，有些程式碼像看天書。

隨著C++20版本的發布，按照後續發展趨勢，這些範式會融為一體，彼此沒有非常明確的界限，混合範式是將來的趨勢。

img

「面向過程」和「面向對象」是最基本的範式，是C++的基礎，無論如何都是必須要掌握的。

如果是開發直接面對用戶的普通應用（Application），那麼可以再研究一下「泛型」和「函數式」。

如果是開發面向程式設計師的庫（Library），那麼非常有必要深入了解「泛型」和「模板元」，優化庫的介面和運行效率。

模板元編程

最開始，模板技術是為了實現泛型的，是泛型編程的基礎。

後來，偶然發現模板可以用來實現元編程機制，並且證明了模板技術是圖靈完備的。

於是模板元編程（template meta-programming，TMP）就誕生了。

模板能做元編程完全是個意外，所以其語法其丑無比。

模板語法很醜，但是它很強大。

C++以模板為基礎，歷經多個版本，把元編程這個坑越挖越大，也越來越漂亮。

Q：如果模板不能實現元編程機制，C++中的元編程機制會如何實現？

A：如果模板不能實現元編程機制，C++也會通過其他方式來實現元編程機制。原因：高性能是C++不可能放棄的方向。

核心思想

基本的程式結構：順序、選擇、循環。

  • 順序結構：按照語句出現的先後順序一次執行

  • 選擇結構：根據條件判斷是否執行相關語句

  • 循環結構：當條件成立時，重複執行某些語句

圖靈完備。理論上可以實現任何可實現的演算法。

基礎設施

操作對象

模板元編程使用C++中的靜態語言成分，所以不能操作變數，只能操作類型和常量。

輸入

命名約定：類型_Ty、常量_Val。

非強制約定。

輸出

命名約定：類型type、常量value。也有用_t、_v封裝。

強制約定。

template< class T >
using remove_reference_t = typename remove_reference<T>::type;

template< class T >
inline constexpr bool is_class_v = is_class<T>::value;

還有一種輸出：程式碼。一般指程式碼展開。

基本結構

元編程是以模板為基礎，準確的說應該是模板特化和遞歸。

image-20220119151339514

image-20220119153222319

image-20220119171843044

種類

值元編程（Value Metaprogramming）

C++11之前用遞歸的模板實例化來實現，比較複雜。

template<unsigned int n>
struct Factorial {
	enum { value = n * factory<n - 1>::value };
};
template<>
struct Factorial<0> {
	enum { value = 1 };
};
int main() {
	Factorial<4>::value;
	return 0;
}

C++11引入了constexpr， 另一種實現。

template<unsigned int n>
struct Factorial {
	static constexpr int value = n * Factorial<n - 1>::value ;
};
template<>
struct Factorial<0> {
	static constexpr int value = 1;
};
int main() {
	Factorial<4>::value;
	return 0;
}

C++14完善了constexpr，大大簡化了這個實現。

template <typename T>
constexpr T Factorial(T x) {
	if (x <= 1) {
		return 1;
	}
	T s = 1;
	for (T i = 2; i <= x; i++) {
		s *= i;
	}
	return s;
}

int main() {
    static_assert(Factorial(4) == 24, "error");
    return 0;
}

遞歸實現

constexpr int Factorial(unsigned int n) {
	if (n <= 1) {
		return 1;
	} else {
		return n * Factorial(n - 1);
	}
}

int main() {
	static_assert(Factorial(4) == 24, "error");
	return 0;
}

constexpr ：表示修飾的對象可以在編譯期算出來，修飾的對象可以當做常量。

  • 修飾變數：

    這個變數就是編譯期常量。

  • 修飾函數：

    如果傳入的參數可以在編譯時期計算出來，那麼這個函數就會產生編譯時期的值。

    否則，這個函數就和普通函數一樣了。

  • 修飾構造函數：

    這個構造函數只能用初始化列表給屬性賦值並且函數體要是空的。

    構造函數創建的對象可以當作常量使用。

constexpr的特點：

  1. 給編譯器足夠的信心在編譯期去做優化，優化被constexpr修飾的表達式。
  2. 當其檢測到函數參數是一個常量字面值的時候，編譯器才會去對其做優化，否則，依然會將計算任務留給運行時。
  3. constexpr修飾的是函數，不是返回值。
  4. constexpr修飾的函數，默認inline。

Q：const和constexpr的區別？

A：在 C 裡面，const 很明確只有「只讀 read only」一個語義，不會混淆。C++ 在此基礎上增加了「常量 const」語義，也由 const 關鍵字來承擔，引出來一些奇怪的問題。C++11 把「常量」語義拆出來，交給新引入的 constexpr 關鍵字。

在 C++11 以後，建議凡是「常量」語義的場景都使用 constexpr，只對「只讀」語義使用 const。

constexpr簡化了值元編程的難度，但是應用範圍有限。constexpr的初衷是為了承擔「常量」語義。

類型元編程（Type Metaprogramming）

template <class _Ty>
struct remove_reference {
    using type                 = _Ty;
};

template <class _Ty>
struct remove_reference<_Ty&> {
    using type                 = _Ty;
};

template <class _Ty>
struct remove_reference<_Ty&&> {
    using type                 = _Ty;
};

template <class _Ty>
using remove_reference_t = typename remove_reference<_Ty>::type;

//以下寫法等價
int a;
remove_reference_t<int>   a;
remove_reference_t<int&>  a;
remove_reference_t<int&&> a;

混合元編程

計算array的點積。

#include <iostream>
#include <array>
using namespace std;

template<typename T, std::size_t N>
struct DotProductT {
	static inline T result(const T* a, const T* b) {
		return (*a) * (*b) + DotProductT<T, N - 1>::result(a + 1, b + 1);
	}
};

template<typename T>
struct DotProductT<T, 0> {
	static inline T result(const  T*, const  T*) {
		return T{};
	}
};
template<typename T, std::size_t N>
auto dotProduct(std::array<T, N> const& x, std::array<T, N> const& y) {
	return DotProductT<T, N>::result(x.data(), y.data());
}

int main() {
	array<int, 3> A{1, 2, 3};

	auto x = dotProduct(A, A);
	cout << x << endl;
	return 0;
}

編譯時：生成了程式碼結構，把for循環展開。

運行時：執行生成的程式碼，計算出結果。

一般約定

為了統一，返回值的命名為「value」，返回類型的命名為「type」。

實踐證明，對於現代C++編程而言，元編程最大的用場並不在於編譯期數值計算，而是用於類型計算（type computation）。

類型計算的約定

類型計算分為兩類：

  1. 通過運算得到一個新類型
  2. 判斷類型是否符合某種條件
template< class T >
using remove_reference_t = typename remove_reference<T>::type;

template< class T >
inline constexpr bool is_class_v = is_class<T>::value;

進一步統一，返回「value」的都改為返回「type」，通過一個類模板封裝：

修改前：

template <typename T> struct is_reference      { static constexpr bool value = false; };    
template <typename T> struct is_reference<T&>  { static constexpr bool value = true; };     
template <typename T> struct is_reference<T&&> { static constexpr bool value = true; };

修改後：

template <bool b>
struct bool_ { static constexpr bool value = b; };

template <typename T> struct is_reference      { using type = bool_<false>; };
template <typename T> struct is_reference<T&>  { using type = bool_<true>; };
template <typename T> struct is_reference<T&&> { using type = bool_<true>; };

在調用 is_reference 時，也是使用 「type」 這個名字，如果想訪問結果中的布爾值，使用 is_reference<T>::type::value 即可。

保證外界在使用類型計算時，都以 「type」 作為唯一的返回值。

目的是規範元編程的程式碼，使其更具可讀性和兼容性。

斷言和契約

編譯時斷言

C++11 引入了關鍵字static_assert。

static_assert(1 + 1 == 2, "error");

編譯時契約（約束）

C++20 concept、requires

#include <iostream>
#include <type_traits>
using namespace std;

template<typename T>
concept Integral = is_integral_v<T>;

template<Integral T>
T Add(T a, T b) {
	return a + b;
}

template<typename T>
	requires Integral<T>
T Add2(T a, T b) {
	return a + b;
}

template<typename T>
T Add3(T a, T b) requires Integral<T> {
	return a + b;
}

Integral auto Add4(Integral auto a, Integral auto b) {
	return a + b;
}

int main() {
	Add(1, 2);
	//Add(1.1, 2.2); //error 「Add」: 未滿足關聯約束
	return 0;
}

還支援不同參數設置不同的約束。

template<typename T>
concept Floating = ::is_floating_point_v<T>;

auto Add5(Integral auto a, Floating auto b) {
	return a + b;
}

template<typename T1, typename T2>
	requires Integral<T1> && Floating<T2>
double Add6(T1 a, T2 b) {
	return a + b;
}

concept替代了C++11的enable_if。

concept可以使程式碼清晰不少，還可以使編譯錯誤提示更直觀。

C++20的四大特性：concept、ranges、coroutine、module

concept 語法的出現，大大簡化了泛型編程和元編程的難度。

語法

類型參數、模板參數、typedef/using、enum/static/constexpr、內嵌類成員

SFINAE（Substitution Failure Is Not An Error）：替換失敗不是一個錯誤。

C++11 enable_if、conditional

C++20 concept、requires

介紹下<type_traits>基礎類，integral_constant包裝了指定類型的靜態常量。

template <class _Ty, _Ty _Val>
struct integral_constant {
    static constexpr _Ty value = _Val;

    using value_type = _Ty;
    using type       = integral_constant;

    constexpr operator value_type() const noexcept {
        return value;
    }
    
    // since c++14
    _NODISCARD constexpr value_type operator()() const noexcept {
        return value;
    }
};

template <bool _Val>
using bool_constant = integral_constant<bool, _Val>;

using true_type  = bool_constant<true>;
using false_type = bool_constant<false>;

Julia

數值計算

JuMP (“Julia for Mathematical Programming”)

using JuMP
using GLPK
model = Model(GLPK.Optimizer)
@variable(model, x >= 0)
@variable(model, 0 <= y <= 3)
@objective(model, Max, 12x + 20y)
@constraint(model, c1, 6x + 8y <= 100)
@constraint(model, c2, 7x + 12y <= 120)
print(model)
optimize!(model)

@show termination_status(model)
@show primal_status(model)
@show dual_status(model)
@show objective_value(model)
@show value(x)
@show value(y)
@show shadow_price(c1)
@show shadow_price(c2)

輸出：

julia> 
Max 12 x + 20 y
Subject to
 c1 : 6 x + 8 y <= 100.0
 c2 : 7 x + 12 y <= 120.0
 x >= 0.0
 y >= 0.0
 y <= 3.0
termination_status(model) = MathOptInterface.OPTIMAL
primal_status(model) = MathOptInterface.FEASIBLE_POINT
dual_status(model) = MathOptInterface.FEASIBLE_POINT
objective_value(model) = 204.99999999999997
value(x) = 15.000000000000005
value(y) = 1.249999999999996
shadow_price(c1) = 0.24999999999999922
shadow_price(c2) = 1.5000000000000007

多重派發（multiple dispatch）

可以看下這個//www.youtube.com/watch?v=SeqAQHKLNj4

多重派發技術可以實現元編程機制。圖靈完備。

C++模板的加強版，Julia的語法寫起來更優雅。

dispatch:根據參數的類型，選擇同名函數的不同實現

static dispatch表示根據編譯時類型選擇

dynamic dispatch根據運行時類型選擇

single dispatch表示根據函數第一個參數的類型選擇

multiple dispatch表示根據函數所有參數類型選擇

C++: multiple static dispatch + single dynamic dispatch

Julia: multiple dynamic dispatch

參考

//zhuanlan.zhihu.com/p/138875601

//zhuanlan.zhihu.com/p/378356824

//max.book118.com/html/2017/0713/122000037.shtm

//zhuanlan.zhihu.com/p/266086040

//www.youtube.com/watch?v=SeqAQHKLNj4

//zhuanlan.zhihu.com/p/105953560

Tags:

VirMach 便宜 VPS

QNews

QNews