Rust编程语言学习导论笔记

2022-09-09

Rust学习编程笔记。

编程语言技术发展和应用

基本判断

类型系统是语言的灵魂——类型系统；

语法是类型系统的表象——语法系统；

编译器/运行时是类型系统的实现 ——运行时和IR；

IR是实现的核心；

编程语言的设计追求

流畅书写和阅读

  • 语法系统设计决定

  • Fluent & DRY

避免程序员错误

  • 主要由类型系统设计决定

  • Safety & Soundness

抽象与复用能力

  • 主要由类型系统设计决定
  • Abstract & Reusable

执行效率

  • 类型系统设计决定上限
  • 编译器/运行时决定优化程度
  • Abstract without overhead

类型系统部分

理论进步主要来自PLT

类型系统的进步过程就是Haskell等学术界编程语言中的特性进入工业界的过程；

一个例外：RUST；首次将所有权和生命周期引入到类型系统中。

内容

  • 代数数据类型 Algebraic Data Type
  • 类型系统的安全保证
  • 类型的抽象
  • 类型的演算
  • 依赖类型Dependent Type

代数数据类型 Algebraic Data Type

什么是代数数据类型

Unit/Void Type
Never Type
Sum Type

代数数据类型

用数学方法来分析类型的一种方式，主要关注值空间。

类型 值空间V 取值范围
bool 2 true, false
uint8 255 [0, 255]
union T {A a; B b;} V(A) + V(B) A $\cup$ B
struct T {A a; B b;} V(A) * V(B) (A, B)的组合

注：第三行的类型被称为Sum Type, 第四行被称为Product Type.

Unit/Void Type

合法的类型

可以用在任何其他类型使用的地方：参数、成员变量、返回值。值空间为1.只有一个取值可能：()，意味着无需占用任何空间(Zero-Sized-Type)。

价值：抽象，零成本的抽象
HashMap<K, ()> 可等价于HashSet<K>
doSomething(())无传参开销

注：C++/Java中的void只是特殊符号，并不是真正意义上的类型。

Unit/Void Type示例

fn inc(value: u32) -> u32 {value + 1 }
fn hello1() { println!("hello"); }
//'()'就是 Unit Type
fn hello2(_: ()) {println!("hello"); }

fn twice<T, F: Fn(T) -> T> (arg: T,f: F) {
    f(f(arg))
}

fn main() {
    twice((), hello2);
    println!("result = {}", twice(1, inc));
}

说明

twice可以调度inc或hello2， 却不能调度hello1

利用ZST特征，hello2与hello1在运行开销上并无任何区别(Abstract without overhead)

Never Type

值空间为0，意味着无任何取值可能，所以可以用于表达不可能执行到的分支

编译器报错的代码

function neverReturn() : never {
    throw new Error('Failed');
}

function main() {
    neverReturn();
    
    // 编译器会报错
    doSomethingElse(); // unreachable code
}

安全的Sum Type: Tagged union

C++中的union并不安全

需要额外的字段来对当前的值类型进行标注，并且要由程序员小心的处理类型分支。

enum ValType { Num; Str};
struct Val {
  ValType ty;
  union {
      double num;
      const char* str;
  };
};

现代编程语言中的Sum Type

自带标签，也称Tagged Union

enum Val {
    Num(f64),
    Str(String),
}
type Val = 
	| { ty: 'Num', inner: number }
	| { ty: 'Str', inner: string };
sealed trait Val
object Val {
    case class Num(value: Double) extends Val
    case class Str(value: String) extends Val
}

Sum Type & 模式匹配

模式匹配

是从Sum Type 中获得内部数据访问的唯一基础途径，这种机制保证了安全性Safety.

在Rust中写错：编译失败

fn show_val(val : Val) {
    match val {
        Val::Str(i) => show_num(i),
        Val::Num(i) => show_str(i),
    }
}

在C++中写错：Undefined Behavior

void show_val(Val val) {
    switch (val.ty) {
        case Str: show_num(val.num); break;
        case NUm: show_str(val.str); break;
        default: assert(0 && "unreachable");
    }
}

强制性的分支覆盖检查

现代编程语言中的模式匹配往往伴有强制性的分支覆盖检查功能，漏写了任何一个分支都会导致编译失败Soundness.

常见的Sum Type

option

enum Option<T> {
    Some(T),
    None,
}

Result

enum Result<T, E> {
    Ok(T),
    Err(E),
}

各种语言中的Option

  • JDK 11中的Optional<T>
  • C++ 17中的std::optional<T>
  • Scale中的Optional[T] & Reference[T]
  • Elm/Haskell 中的Maybe

空指针的问题 & Sum Type

逻辑不可能为空时

  • 没有提供不为空的保证

逻辑可能为空时

  • 没有强制程序员处理为空的情况

Java(BAD)

int sum(int base, int[] a) {
    for (var i = 0; i < a.length; ++i) {
        base += a[i];
    }
    return base;
}

Rust(GOOD)

fn sum(base: u32, items: &[u32]) -> u32 {
    items.iter().fold(base, |a, &&i| a + i)
}
fn sum_opt(base: u32, a: Option<&[u32]>) -> u32 {
    match a {
        Some(inner) => sum(base, inner),
        None =>base,
    }
}

SUM TYPE & NEVER

RESULT<T, NEVER>

代表着不可能出现异常，其值空间等于T，代码中如果使用WtiteToStr，编译器生成代码中不会有任何执行路径上的开销

pub trait Writer {
    type Err;
    fn write(&mut self, s: &str) -> Result<(), Self::Err>;
}

impl Writer for WriterToFile {
    type Err = io::Error;
    fn write(&mut self, s: &str) -> Result<(), Self::Err> {/*.*/}
}

impl Writer for WriterToStr {
    type Err = !; // "!" 就是Never
    fn write(&mut self, s: &str) -> Result<(), Self::Err> {
        self.data.push_str(s); Ok(());
    }
}

类型系统的安全保证

  • 不可变性 & 所有权
  • 借用和生命周期

延迟写日志的场景

写日志时将日志记录推入内存缓冲区，整个请求处理结束时，根据是否有错误决定要不要持久化。

两者处理思路

  • 数据不可变：对其中成员的更新会导致一个新的数据副本

  • 所有权的转移：参数传递后被销毁，数据所有权被转移后，原有变量自动失效

RUST的借用和生命周期

特征

  • （所有权）Move by default
  • （借用）共享不可变
  • （借用）可变不共享

生命周期是类型签名的一部分

解决了哪些问题

  • 释放后使用
  • 野指针
  • 多线程竞态
  • 安全而无开销的值传递
  • 无GC的自动化内存管理

类型的抽象

  • Java Interface的问题
  • C++ Template的问题
  • Trait System

C++ Template：类型参数无显式约束

  • 无显式的类型约束

只有在最终完全特化时才能判断是否符合要求，容易误用（只有签名保证，无类型保证）、编译错误信息难以看懂。

  • C++ 20中的Concept

部分借鉴了Rust中的trait来解决这个问题。

Trait System: RUST类型系统的抽象核心

Rust类型系统中的抽象

是Interface/Template能力的超集，语法上也接近，但本质上更靠近Haskell的TypeClass。

特征

  • 支持使用方（场景化）抽象
  • 同时支持动态/静态派发
  • 支持实例化行为和类行为抽象
  • 支持参数化类型和关联类型

Trait System支持使用方抽象

接口（抽象）的实现与类自身的方法解耦，使用方可以为已有的类添加新的抽象，而无需修改原有类的实现代码。

pub trait Editable {
    fn editable(&self) -> bool { false }
}

impl Editable for ui::Lable {}

impl Editable for ui::Checkbox {
    fn editable(&self) -> bool {
        !self.readonly()
    }
}

fn do_with_editable<T: Editable>(c: &T) {
    if c.editable() {
        todo!()
    }
}

Trait System支持使用方抽象动态和静态派发

一套实现代码，同时支持静态派发和动态派发：动态还是静态取决于如何调用，而不是如何实现，动态派发时，采用了FatPtr模型（C++用ThinPtr），避免了多继承虚表带来的复杂度。

fn static_check<T: Editable>(c: &T) {
    if c.editable() {
        println!("editable")
    }
}

fn dynamic_check(c: &dyn Editable) {
    if c.editable() {
        println!("editable")
    }
}

Trait System同时支持类/实例行为抽象

在抽象（接口）定义中，既可以表达实例的能力要求，也可以表达类型的能力要求。

pub struct Ctx{/*...*/}
pub trait Service: Sized {
    fn from_ctx(ctx: &Ctx) -> Self'
    fn run(&self, req: Req) -> Reply;
}

impl Service for Foo {/*...*/}
impl Service for Bar {/*...*/}

impl Ctx {
    fn run<T: Service>(&self, Req req) -> Reply {
        T::from_ctx(self).run(req)
    }
    fn test() {
        let me = Ctx {/*...*/};
        me.run::<Foo>(Req::new());
        me.run::<Bar>(Req::new());
    }
}

依赖类型Dependent Type

由值决定的类型

  • 类型域与值域的连接
  • 类型系统证明下的值域的合法性保障
  • 配合覆盖性检查，是形式化证明的一种路径

Trusted Index

template <int N> class TrustedIndex {
    friend class Array;
    int inner;
}

template <int N, typename T> class Array {
    T* items;
public:
    typedef TrustedIndex<N> TI;
    
    // bound check
    T* at(int i) {return i < N ? &items[i] : NULL;}
    // no bound check
    T* fast_at(TI i) { return &items[i.inner]; }
}

类型的推演

  • 用类型来推演类型，用类型计算类型
  • C++ type traits技巧（利用C++偏特化的能力）
template <typename T> struct Storage<T> {
    typedef T Item;
    Item* alloc(size_t n) { return (Item*)malloc(sizeof(T) * n); }
};

template <> struct Storage<bool> {
    typedef uint8_t Item;
    Item* alloc(size_t n) {return (Item*)malloc((n + 7) / 8); }
};

template < typename T> struct Array<T> {
    Storage<T>::Item* items;
    size_t len;
}

Type Traits的本质

  • 是一种Associate Type的应用技巧
  • 通过T推演得到T::item的过程
trait Storage{
    type Item;
    fn alloc(n: usize) -> *mut Self::Item;
}

impl Storage for bool {/*...*/}
impl Storage for u32 {/*...*/}
struct Array<T: Storage> {
    items: *mut T::Item,
    len: usize,
}

Associate Type -> 进一步的Generic Associate Type.

  • 更复杂的类型推演
declare const num: ParseFn<number>;

const t1 = tuple(num, ws, sym);

类型的演算配合类型推导，可以极大提升类型安全的同时，简化程序员的心智负担。

语法部分

基础语法

  • 类型推导
  • Async/Await
  • Option/Result Chain

高阶语言

  • 反射与注解
  • 宏系统
  • 两阶段语言

类型推导

  • 强有力的类型系统对避免程序员的错误至关重要，但是到处显式的指定类型也让人恼火，因为类型推导能力是现代强类型语言的标配。

Async/Await

协程

  • 高并发（非高并行）问题的应用层解决方案

有栈协程

  • 通过对当前的调用栈现场保留和恢复实现的协程。

无栈协程

  • 通过跨越调度的上下文状态机来实现，性能更高，资源占用更少。

C++函数式编程的复兴

案例分析过程

副作用

int add(const int& x, const int& y){
    return x + y;
}

int add(int& x, int& y){
    return x+=y;
}

无处不在的函数式编程结构

vector<int> vec = {2, 3, 9, 4, 1};
sort(std::begin(vec), std::end(vec));

int arr[] = {2, 3, 9, 4, 1};
sort(std::begin(arr), std::end(arr));

vector<Person> people = {\{"Tome", 21}, {"Jack", 33}, {"Mary", 18}\};

sort(std::begin(people), std::end(people)); //error

auto CompareByAge = [](const Person& lp, const Person& rp) {
    return lp.age > rp.age;
}

sort(std::begin(people), std::end(people), CompareByAge);

上面把CompareByAge作为参数传递给sort，我们把sort称为高阶函数；

高阶函数
  1. 使用其他函数作为参数；
  2. 以便获得高层多态（抽象）；

范畴论

循环的四种写法

for_each(vec.begin(), vec.end(), print);

响应变化

比如以过滤求和为例：

vector<int> numbers = {2, 0, 2, 24, 12};

size_t sum = 0;

// count sum
for(auto i : numbers) {
    sum += i;
}

sum = accumulate(cbegin(numbers), cend(numbers), 0);

//count sum of the greater than 10
for(auto i : numbers) {
    if(i > 10) {
        sum += i;
    }
}

size_t init = 0;
sum = accumulate(cbein(numbers), cend(numbers), init, SumGreaterThanThen);

vector<int> numbersGreaterThanThen = {};

copy_if(cbegin(numbers), cend(numbers), back_inserter(numbersGreaterThanThen), greaterThanTen);

sum = accumulate(cbegin(numbersGreaterThanThen), cend(numbersGreaterThanThen), 0);

const vector<int> Filter(const vector<int>& input, std::function<bool(const int&)> filterFunction) {
    vector<int> filtered = {};
    copy_if(cbegin(intput), cend(input), back_inserter(filtered), filterFunction);
    return filtered;
}

const int Sum(const vector<int>& input) {
    return accumulate(cbegin(input), cend(input), 0);
}

sum = Sum(Filter(numbers));

标准库回顾

Monads / Options / Variant

// 观察者
vector<function<void(int a)>> listeners = {
    [](int a) {cout << a << endl;},
    [](int a) {cout << a + 1 << endl;}
};

for_each(begin(listeners), end(listeners),
	[](auto f) {f(10)};        
);

// 表驱动
std::unordered_map<int, function<void(int a)>> tables = {
    {1, [](int a) {cout << a << endl;}},
    {2, [](int a) {cout << a + 1 << endl;}}
};

int key = 1;
tables[key](2);

int key = 2;
tables[key](2);

一等公民的算法及函数

<algorithm>
<numeric>
<functional>
count/count_if
sort
nth_element
accumulate
reduce
copy/copy_if
for_each
find/find_if
move
any_of/all_of

函数式编程

  1. 一种编程范式，强调对表达式的运算而非执行命令(声明式)
  2. 纯函数(pure function)
  3. 延迟计算(lazy evaluation)
  4. 模式匹配

纯函数在C++中保障：

  1. 没有副作用：class中采用static，const关键字修饰
  2. 始终有返回值
  3. 不变形immutable
  4. 增加mutable

C++20:Ranges, 延迟计算,concepts

iterator

data->filter->tranform->take

  • 函数式
  • 泛型
  • 元编程
  • 过程
  • 面向对象

$\lambda 语法$

C++世界里，函数是对象，忘掉callback

struct Adder {
	Adder(int base) : value(base){};
    int operator() (const int& x) const{
        return x + value;
    }
private:
    int value;
};

类型系统

范畴->对象+函数

pure Function

  1. 元素的变换
  2. 无副作用

类型系统的代数数据类型

编程语言技术发展和应用

编程语言会议

  • POPL
  • PLDI
  • OOPSLA
  • PPoPP
  • ICFP
  • ASPLOS
  • LCTES

Haskell

Lisp+ ML->Haskell