元编程 (meta-programming)
阅读原文时间:2022年01月28日阅读:1

元编程 (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版本的发布,按照后续发展趋势,这些范式会融为一体,彼此没有非常明确的界限,混合范式是将来的趋势。

“面向过程”和“面向对象”是最基本的范式,是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;

还有一种输出:代码。一般指代码展开。

基本结构

元编程是以模板为基础,准确的说应该是模板特化和递归

值元编程(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::type;

    template< class T >
    inline constexpr bool is_class_v = is_class::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

可以看下这个https://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

参考

https://zhuanlan.zhihu.com/p/138875601

https://zhuanlan.zhihu.com/p/378356824

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

https://zhuanlan.zhihu.com/p/266086040

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

https://zhuanlan.zhihu.com/p/105953560