Hoes of Tech

Conceptualization of Technology

A First Look at Rust

过去的一年半多,我一直沉迷与OOC,原因倒是很简单,OOC是目前为止我所能见到的最容易理解和最容易书写的语言。并且另外一个极其重要的地方是,它可以编译成C代码。编译成C代码,也就意味着优化可以交给高度发展的C语言编译器来做,听起来似乎适合十分高效的方法。

最近几年类似的语言越来越多,从很久很久之前就存在却一直没出名的Haxe,还有最近的Nim-lang,以及采用了类似ruby语法的Crystal,甚至包括编译成C++的felix。这些语言都号称自己考虑了速度(运行速度),至少从编译成C/C++的层面上。

可惜的是,在改进OOC编译器rock的过程中,我遇到了越来越多的问题,这些问题让喜欢速度的人泄气。一个最明显的事情是,这些语言几乎都用了GC,不论是libGC还是自己写的,并且更重要的是,很多语言特性是基于GC设计的——比如闭包,比如iterator的unwrap,在有没GC的情况下,这些东西的设计要复杂的多。在OOC里,由于Generics不是Template,更多的东西开始依存GC,在用了它一年后,当我真正开始在工作里使用的时候,这些问题开始出现,我开始打算关闭GC,但很显然这是不可能的。编译器会把一切搞不清楚的事情踢给GC。

在这个时候,恰好Rust站了出来,静态析构,没有野指针…… 简直就是为有着Compile to C语言苦恼的人设计的。于是我打算在这篇文章里瞄一眼Rust,来看看它是不是我想找的东西。

首先从官方的例子开始,打开Rust的主页就会看到。直接拷贝过来,就是这个样子:

fn main() {
    let program = "+ + * - /";
    let mut accumulator = 0;

    for token in program.chars() {
        match token {
            '+' => accumulator += 1,
            '-' => accumulator -= 1,
            '*' => accumulator *= 2,
            '/' => accumulator /= 2,
            _ => { /* ignore everything else */ }
        }
    }

    println!("The program \"{}\" calculates the value {}",
              program, accumulator);
}

看起来跟现代语言并没有太大差别,至少这个例子还算比较容易阅读,让我们来把这段代码改成类似函数式的写法:

fn main() {
    let program = "+ + * - /";

    let res = program.chars().fold(0, | x, x1 | 
        match x1 {
            '+' => x + 1,
            '-' => x - 1,
            '*' => x * 2,
            '/' => x / 2,
            _ => x
        }
    );

    println!("The program \"{}\" calculates the value {}",
              program, res);
}

这段代码对OOC的用户来说相当亲切,它们实在有些相似,比如相同的lambda语法 | arguments | program,几乎相同的match语法match expr { case => expr }

不过如果仅仅是这样,恐怕Rust不会这么吸引人,下面让我们来看一个稍微复杂点的例子。

这个例子来自Computer Language Benchmark Game的Binary Tree,这也是我最喜欢的一个例子,几乎在了解任何语言时我写的第一个小代码都是Binary Tree。它包含了一些基本的东西——构造体(或类),递归,循环。先来看看我写的Binary Tree,后面会有详细的解说。

use std::env;

struct Tree {
    left: Option<Box<Tree>>,
    right: Option<Box<Tree>>,
    item: i32,
}

impl Tree {
    pub fn new(depth: i32, i: i32) -> Tree {
        if depth <= 0 {
            Tree { item : i, left: None, right: None }
        } else {
            Tree { item : i, 
                left: Some(Box::new(Tree::new(depth - 1, 2 * i - 1))),
                right: Some(Box::new(Tree::new(depth - 1, 2 * i ))),
            }
        }
    }

    pub fn item_check(&self) -> i32 {
        self.item + 
            self.left.as_ref().map(| t | t.item_check()).unwrap_or(0) -
            self.right.as_ref().map(| t | t.item_check()).unwrap_or(0)
    }
}

const MINDEP : i32 = 4;

fn main() {
    let depth = env::args().nth(1).unwrap_or("10".to_string()).parse::<i32>().unwrap_or(10);
    println!("Running program with depth = {}", depth);
    let stretch = depth + 1;
    println!("stretch tree of depth {}\t check: {}", stretch, Tree::new(stretch, 0).item_check());
    let long_lived = Tree::new(depth, 0);
    let res = (MINDEP .. depth + 1).filter(| x | x % 2 == 0).map( | x | 
                    (1 << (depth - x + MINDEP + 1), x, (1 .. (1 << (depth - x + MINDEP)) + 1).fold(0, 
                        | xt , x1 | xt + Tree::new(x, x1).item_check() + Tree::new(x, -x1).item_check())));
    for (iters, i, check) in res { 
        println!("{}\t trees of depth {}\t check: {}", iters, i, check); 
    }

    println!("long lived tree of depth {}\t check: {}", depth, long_lived.item_check());
}

这段程序很短,算上空行也不过总共44行,让我们来看看每一部分都有什么有趣的地方。

struct Tree {
    left: Option<Box<Tree>>,
    right: Option<Box<Tree>>,
    item: i32,
}

这是一个很容易理解的structure定义,让人高兴的是新语言越来越多的使用pascal式的variable : type而不是难于理解的type variable。下面就是具有Rust特点的东西了,跟C,D等语言不同,递归定义时并没有用类似left: &Tree的形式,原因很简单——left和right有可能是空的,而rust不允许这种空指针。为了解决这个问题,Rust提供了一个叫做Option的特殊类型(enum),如果没有内容,那么OptionNone,否则就是Some(T),这样做的好处是不用再考虑nil.item_check()这种可能引起Segmental fault的形式了。

接下来看到的是Box,当然Box也不过是储存Heap上的一个指针而已,在C++等语言里,Box&Tree似乎并没有太大差别。不过在Rust里,&Tree并不是Tree的指针,而是Tree的Borrow,或许你没看明白,没问题,让我们动手把Box修改成&,看看会发生什么:

struct Tree <'a> {
    left: Option<&'a Tree<'a>>,
    right: Option<&'a Tree<'a> >,
    item: i32,
}

impl <'a> Tree <'a> {
    pub fn new(depth: i32, i: i32) -> Tree<'a> {
        if depth <= 0 {
            Tree { item : i, left: None, right: None }
        } else {
            Tree { item : i, 
                left: Some(&Tree::new(depth - 1, 2 * i - 1)),
                right: Some(&Tree::new(depth - 1, 2 * i )),
            }
        }
    }

……………… 下略 ………………

修改完之后程序有了很大的变化,除了把Box改成&之外,我们还添加了lifetime标识。如果之前或多或少知道rust,那么肯定知道rust是如何管理内存的——每一个变量都有一个生命期,超过生命期之后这个变量就会被销毁。因此,对于struct里的变量这种无法推断生命期的东西,需要在代码里指明这些变量到底能存在多长时间。不过很可惜,纵使修改成这个样,这段代码依然无法编译通过——会出现下面的错误:

15:29: 15:60 error: borrowed value does not live long enough
15                 left: Some(&Tree::new(depth - 1, 2 * i - 1)),
                                      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
10:48: 19:6 note: reference must be valid for the lifetime 'a as defined on the block at 10:47...

简单来说,在new函数里面,我们定义的所有变量在new函数结束时就全部被析构了,因此我们没法在其他地方用它。为了解决这个问题,我们需要把Tree分配在Heap上,并且保证它能活得够长。(当然,这并不代表这么做是不可能的,但在这里我们不讨论)

这个话题一旦展开就不得不附带上冗长的解释,毕竟lifetime是rust里最独特的东西,如果想更详细理解lifetime,rust的官方文档是一个好地方。总之,希望你能通过这个不够详细的解释理解&Box的区别。

在说明了lifetime这个概念之后,下面的事情就变得简单多了, pub fn new(depth: i32, i: i32) -> Tree是一个"构造函数",构造函数有引号是因为rust里并没有语言层级的构造函数,new仅仅是一个约定而已。函数的定义跟Ada有些类似,相信所有人第一眼都能看明白这个函数的意义。

下面让我们来看main函数,除去大量的println,重要的代码只有一句:

    let res = (MINDEP .. depth + 1).filter(| x | x % 2 == 0).map( | x | 
                    (1 << (depth - x + MINDEP + 1), x, (1 .. (1 << (depth - x + MINDEP)) + 1).fold(0, 
                        | xt , x1 | xt + Tree::new(x, x1).item_check() + Tree::new(x, -x1).item_check())));

这一句稍微有些函数式的感觉,简单解释,我们找出MINDEPdepth + 1之间的所有偶数,对于每一个偶数,求从1到(1 << (depth - x + MINDEP)) + 1循环,并求对应Tree::item_check的和。相信熟悉函数式的人能够很快搞明白每一句的意思:map把没一个偶数变成一个Tuple,而fold则对区间求和。如果用更普通一点的写法,那么是这样:

    let mut i = MINDEP;
    while i <= depth {
        let iterations = 1 << (depth - i + MINDEP);
        let mut check : i32 = 0;
        for j in 1 .. iterations+1 {
            check += Tree::new(i, j).itemCheck();
            check += Tree::new(i, -j).itemCheck();
        }
        println!("{}\ttrees of depth {}\t check: {}", iterations * 2, i, check);
        i += 2;
    }

可以看到,三行代码可以展开成12行。就如同函数式宗教的信者们所一直在宣讲的一样,相比与循环,map和fold可能更加简洁直观。

不过这些并不是重点,重点是我们看到这些代码里压根没有出现free()这种东西,完全就如同任何一个有GC的语言,定义,然后使用,不必担心哪些东西会吃掉内存。更重要的是Rust压根没有使用GC——也就是说不会有什么东西会突然停掉你的程序然后扫描内存,也不会有gc_malloc这种函数会在你使用的时候花费半个小时去扫描并释放空间,所有的析构都是静态的,也就是相当与自动在C代码里插入了free语句。

这种做法的好处显而易见,不会有什么不确定的东西影响程序的运行,也不会有无法释放的内存。让我们继续修改下这个程序,让它变成多线程:

use std::{env, thread};

………… 中略 …………

    let res = (MINDEP .. depth + 1).filter(| x | x % 2 == 0).map( | x | 
                    (1 << (depth - x + MINDEP + 1), x, thread::spawn(move || (1 .. (1 << (depth - x + MINDEP)) + 1).fold(0, 
                        | xt , x1 | xt + Tree::new(x, x1).item_check() + Tree::new(x, -x1).item_check())))).collect::<Vec<_>>();
    for (iters, i, check) in res { 
        println!("{}\t trees of depth {}\t check: {}", iters, i, check.join().ok().unwrap_or(0)); 
    }

………… 后略 …………

可以看到修改的地方很少,仅仅是在原先的1 .. (1 << (depth - x + MINDEP)) + 1循环外面套了一个thread::new而已,这也是函数式的另一个好处,相比与用for循环来说,实现多线程非常简单。同时,如果有一个C++程序员,那么他很有可能会对thread::new里面的代码表示担心,比如会不会有data race。回到Rust上,Rust有一个owner的概念,也就是说任何一个变量都有一个"所有者",并且只能有一个,虽然前面提到了Rust拥有borrow这个概念,但编译器会限制同一时间只能有一个可修改内容的borrow。那么很显然,只要编译过后没有错误,那么这个程序就不会出现问题——当然你可能需要面对很多的编译错误。这通常是一个trade-off,不过对于多线程程序来说,很明显面对编译器的错误信息要简单的多。

当然,也可以用channel来传递消息:

use std::env;
use std::thread;
use std::sync::mpsc;

………… 中略 …………
    let long_lived = Tree::new(depth, 0);
    let (tx, rx) = mpsc::channel::<(i32, i32, i32)>();
    let res = (MINDEP .. depth + 1).filter(| x | x % 2 == 0).map( | x | {
        let tx = tx.clone();
        thread::spawn(move | | tx.send((1 << (depth - x + MINDEP + 1), x, (1 .. (1 << (depth - x + MINDEP)) + 1).fold(0, 
                        | xt , x1 | xt + Tree::new(x, x1).item_check() + Tree::new(x, -x1).item_check()))))}).collect::<Vec<_>>();
    for _ in res {
        let (iters, i, check) = rx.recv().unwrap();
        println!("{}\t trees of depth {}\t check: {}", iters, i, check); 
    }

………… 下略 …………

唯一需要注意的地方是由于owner的限制,tx(sender)对于每个线程都与要一个克隆。

好了,到这里,这篇文章也算多少介绍了Rust的主要特性,是时候来回头看看它到底怎么样了。对我来说,Rust有一个最大的特征——安心。只要没有编译错误或者fn main() { main() }这种代码,就可以放心的认为自己的程序是正确的,在写了几天Rust之后,可以明显感觉到自己考虑的事情变少了,只要按照自己的想法写出来,剩下的不足全部都由编译器来指出。有一个提升生活质量的设计,我还能要求什么呢?