Deltamaster Tech Center

在学习数据结构和算法的时候，我们一般都会通过分析算法复杂度，来对某个问题选择合适的数据结构和算法。

下面就是一个经典问题：

我们需要一个容器，容器中存放的是int数据。容器中的元素是有序的，对容器有一个插入操作，要求是插入后容器中的元素仍然是有序的。我们应该选择list还是vector？

让我们先从算法复杂度的角度来简单看一下这个问题。首先一点是有序，所以找到要插入的位置，对于list的算法复杂度是O(n)，因为平均需要遍历一半的链表长度，对于vector的算法复杂度是log^2(n)，因为可以进行二分查找确定位置。然后是插入，list的插入操作是O(1)，非常理想的常数级操作，而vector的插入操作是O(n)，因为平均要移动一半的元素。综合下来看，list是要更胜一筹，所以应该选择list。但是事实却与这个推测截然相反？

让我们用C++写一段程序来进行验证：

#include <iostream>
#include <vector>
#include <list>
#include <random>

using namespace std;

template <typename T>
typename T::iterator insert(T& c, typename T::value_type elem)
{
    auto i = c.begin();
    for (; i != c.end(); i++) {
        if (elem <= *i) {
            break;
        }
    }
    return c.insert(i, elem);
}

int main(int argc, char** argv)
{
    vector<int> v;
    list<int> l;
    auto engine = default_random_engine();

    if (argc < 3) return 1;

    if (argv[1] && argv[1][0] == 'v') {
        for (int i = 0; i < atoi(argv[2]); i++) {
            insert(v, engine());
        }
    } else {
        for (int i = 0; i < atoi(argv[2]); i++) {
            insert(l, engine());
        }
    }

    return 0;
}

在这里为了说明问题方便起见，在查找阶段我们让vector和list都使用O(n)的方法进行查找。那么对于这段程序（下面表里的算法复杂度是针对每次插入操作而言的）：

这样，我们通过生成一系列随机数的方式来进行测试。让我们看看不同数据规模下的测试结果如何，表格中的时间单位是秒。

为什么list的性能反而差，而且相差如此悬殊？因为我们之前没有站在体系结构的角度看问题。同样是O(n)的操作，对于计算机而言实际执行的效率可能有着天壤之别。

让我们回顾一下前面程序中的insert函数模板，对于两种容器，我们使用了完全相同的线性查找算法。对于计算机而言，list版本的步进操作（i++），需要多进行一次寻址（根据指针找到下一个节点的位置），而更重要的是，找到的下一个节点，很有可能没有命中缓存，因为通过list中的相邻元素在内存中并没有相邻关系；而vector的步进操作，几乎能够保证命中缓存，因为每次访问的，都是内存中相邻的元素。对于插入操作而言，list虽然只有O(1)复杂度，而且确实非常快，但却要每次进行一次很小的内存分配，而又因为list的每个节点都要包含其他指针信息，对于内存空间也是很大的浪费。

我们从这个测试中得到的启示是：

• 性能分析要用实际测试数据说话，主观推测容易以偏概全；
• 对于体系结构的理解非常重要，缓存命中率是影响性能的重要因素；
• 数据规模小的时候，算法复杂度无关紧要；
• 不要过度优化；
• 节约使用内存！

在程序中使用随机数的需求很普遍，有时候我们还需要用到一些更加复杂的随机数据结构，比如生成一个随机的列表或者二叉树等，探索性测试可以算一个典型的应用场景。

在Scala中生成一个随机整数有现成的函数可用：scala.util.Random.nextInt()。让我们看看我们如何基于它来用优雅简洁的程序构造一些更复杂的generator。

我们首先要对Generator的功能进行必要的抽象：

• 首先，Generator[T]需要一个generate方法来随机产生一个T类型的对象；
• 需要一个map方法，给定一个T=>S类型的映射函数f，产生Generator[S]；（可对比List[T]的map(f: T=>S): List[S]方法理解）
• 需要一个flatMap方法，给定一个T=>Generator[S]类型的映射函数f，产生Generator[S]。（可对比List[T]的flatMap(f: T=>List[S]): List[S]方法理解）

通过上面的陈述，可以看到我们将Generator抽象为一种容器，这将给我们以后的扩展带来很大的便利（利用Scala的for来进行操作，后面我们会看到具体的实例）。

  trait Generator[+T] {
  	self => // an alias for "this"
  	
  	def generate: T
  	
  	def map[S](f: T => S): Generator[S] = new Generator[S] {
  		def generate = f(self.generate)
  	}
  	
  	def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S] {
  		def generate = f(self.generate).generate
  	}
  }

这就是Generator的抽象定义了，其中self是this的别名，注意下面两处使用“self”的地方，请思考一下为什么不能使用“this”，这里就不详细解释了。

基于这个抽象的定义，我们就可以构造一些基本的Generator了。

  def integers = new Generator[Int] {
  	def generate = scala.util.Random.nextInt()
  }

  def booleans = integers map (_ >= 0)

  def single[T](x: T): Generator[T] = new Generator[T] {
  	def generate = x
  }

  def choose(lo: Int, hi: Int): Generator[Int] =
  	for (x <- integers) yield lo + Math.abs(x) % (hi - lo)

  def oneOf[T](xs: T*): Generator[T] =
  	for (idx <- choose(0, xs.length)) yield	xs(idx)

其中：

• integers用于生成随机整数；
• booleans用于生成随机布尔值，这里就使用了map方法，通过Int=>Boolean函数，将类型Generator[Int]映射成了Generator[Boolean]；
• single用于生成特定值；
• choose用于生成位于lo和hi之间的整数（不包含hi）；
• oneOf用于随机取列表中的值，比如oneOf(1, 10, 100, 1000).generate将会随机产生这四个数中的一个。

下面我们要利用这些基本的Generator来构造随机List[Int]，所以我们就需要一个Generator[List[Int]]，生成策略是：

• 首先生成一个随机布尔值，如果为真，则直接返回空列表的Generator，否则返回非空列表的Generator；
• 对于非空列表，head是随机整形，tail是一个随机列表（当然即有可能是空，也可能非空），于是递归这两个步骤直到tail为空。

	def intLists: Generator[List[Int]] = for {
		isEmpty <- booleans
		list <- if (isEmpty) emptyIntLists else nonEmptyIntLists
	} yield list

	def emptyIntLists = single(Nil)

	def nonEmptyIntLists = for {
		head <- integers
		tail <- intLists
	} yield head :: tail

这里就用到了integers、booleans和single三个基本的Generator，同时利用for间接调用map和flatMap方法，产生新的Generator。这样，intLists.generate就会产生一个随机的List[Int]。

再看一个随机二叉树的例子，思路与列表很类似：

	trait Tree {
		def toStringWithIndent(level: Int): String = this match {
			case Leaf(x) => "  " * level + x.toString + "\n"
			case Inner(l, r) => "  " * level + "LNode:\n" + l.toStringWithIndent(level + 1) + "  " * level + "RNode:\n" + r.toStringWithIndent(level + 1)
		}
		override def toString = toStringWithIndent(0)
	}
	case class Leaf(val x: Int) extends Tree
	case class Inner(val l: Tree, val r: Tree) extends Tree
// End of Tree definition

	def leafs: Generator[Leaf] = for  {
		x <- integers
	} yield Leaf(x)

	def inners: Generator[Inner] = for {
		l <- trees
		r <- trees
	} yield Inner(l, r)

	def trees: Generator[Tree] = for {
		isLeaf <- booleans
		tree <- if (isLeaf) leafs else inners
	} yield tree

不难理解，这里就不再详细解释。

再更进一步，对于上面的intLists，我们能否创造一个更加普适的Generator，使得不仅限于产生随机的List[Int]，而是根据给定的Generator[T]，产生List[T]，这意味着我们需要构造一个Generator[List[T]]。

	def lists[T](g: Generator[T]): Generator[List[T]] = for {
		isEmpty <- booleans
		list <- if (isEmpty) emptyLists else nonEmptyLists(g)
	} yield list

	def emptyLists = single(Nil)

	def nonEmptyLists[T](g: Generator[T]) = for {
		head <- g
		tail <- lists(g)
	} yield head :: tail

与上面intLists的不同之处在于，我们将原先使用integers这个Generator的地方，换成了我们指定的g: Generator[T]。我们可以像下面这样使用它：

  lists(integers).generate // equivalent to intLists.generate
  lists(oneOf("Adam", "Brion", "Chris", "Daniel")).generate

其中第一行与intLists.generate等价，第二行使用了oneOf这个Generator，产生的List中将只有这四种字符串。

首先简单描述一下这个经典的找零问题：

已知需要找零的数量，以及可用的硬币面值，求用这些面值的硬币，有多少种方法拼凑出要求的找零数量。

比如要求找零4元，可用的硬币只有1元和2元两种面值，那么所有可能的方案是，[1, 1, 1, 1]、[1, 1, 2]、[2, 2]三种。（不同顺序不作为不同方案）

设计一个函数，接受两个参数：

• money：Int，表示需要拼凑的找零数量。
• coins：List[Int]，所有可用的硬币面值。

简单分析一下这个问题。直观地用递归的思路去考虑，所有可能的方案，就等于以下两部分之和：

• 用一枚某种面值的硬币x后，剩余找零数的找零方案数量；
• 用除了x以外的其他硬币的找零方案数量。

而递归终止条件就是，找零的数量小于或等于0，或者没有硬币可以用了。

  def countChange(money: Int, coins: List[Int]): Int = {
    if (money < 0) 0
    else coins match {
      case Nil => if (money == 0) 1 else 0
      case x::xs => countChange(money - x, coins) + countChange(money, xs)
    }
  }

这段代码用到了Scala的Pattern Matching。Nil是空List对象，继承自List，而x::xs则表示一个非空的List，其中x是用来匹配列表的head，而xs则是列表的tail，xs可以匹配任何List，当然也包括Nil。所以这两个case覆盖了所有的情形，要么为空，要么不为空，如果不为空，则将这个列表decompose成构造参数x和xs，供后面的表达式使用。

许多程序员，尤其是很多稍有一些经验的C++程序员，会陷入一种为了性能而牺牲接口设计可维护性的误区，最终往往在性能上提升很少，甚至没有提高，程序可维护性也大大降低，这是我们都不希望看到的结果。

下面是一个典型的例子，当然进行了一定的抽象和简化。

void getA(A& x)
{
	// do some initialization to "x"
}

void f()
{
	A a;
	getA(a);
	// use "a"
}

我问，为什么不设计成“A getA()”，让对象a在函数getA中进行构造呢？这样接口就更加容易阅读，一般并不鼓励将参数作为输出参数来使用，这样会降低程序的可读性。

他给出的答案是，这样可以避免对象的拷贝构造，能够提升性能。因为如果在getA中构造了A的对象，那么在返回时要调用一次拷贝构造函数将这个对象拷贝构造到调用处，然后再析构getA中临时产生的对象。

事实果真如此吗？让我们阅读一下C++标准的相关章节。

When certain criteria are met, an implementation is allowed to omit the copy/move construction of a class object, even if the constructor selected for the copy/move operation and/or the destructor for the object have side effects. In such cases, the implementation treats the source and target of the omitted copy/move operation as simply two different ways of referring to the same object, and the destruction of that object occurs at the later of the times when the two objects would have been destroyed without the optimization. This elision of copy/move operations, called copy elision, is permitted in the following circumstances (which may be combined to eliminate multiple copies):

• in a return statement in a function with a class return type, when the expression is the name of a non-volatile automatic object (other than a function or catch-clause parameter) with the same cv-unqualified type as the function return type, the copy/move operation can be omitted by constructing the automatic object directly into the function’s return value

让我们根据上面条款来看看，下面的代码会怎么处理。

A getA()
{
	A x; // logically construct "x" here, but actually not
	// do some initialization to "x"
	return x; // logically copy-construct "x" to "a" here, but actually not
	// logically destruct "x", but actually not
}

void f()
{
	A a = getA(); // actually construct "x" directly here
	// use "a"
}

根据标准说明，函数getA的返回值是类型A，并且与返回类型一样是non-const、non-volatile对象，也是automatic对象（逻辑上被分配到栈上），从对象x到调用处（f函数中的变量a）的拷贝构造可以被省略，对象x将会被直接构造在f函数的变量a处（getA中的x和f中的a将被视为同一个对象）。即使拷贝构造函数中有任何副作用，这个调用也仍然可以被省略，并且这种行为被视为正常的语义，而非优化行为。

在gcc编译器中，即使指定优化级别为0，在上面的例子中也不会有两个A对象被构造；而Visual Studio指定了一定优化级别以后，多余的对象构造也会被省略。

因此，第一种写法能够提升性能的说法并不成立，而且接口设计相当丑陋难读。相反，有时第一种写法甚至会损害性能。

请看下面的代码。

A::A(int x, int y, int z) : x(x), y(y), z(z) {}

A getA()
{
	// get height, width, length from somewhere else
	A x(height, width, length);
	return x;
}

void f()
{
	A a = getA();
	// use "a"
}

这段代码说A有一种接受三个参数的构造函数，而这三个参数在getA中可以通过某些逻辑得到，那么可以直接通过带参数的构造函数对A进行初始化，这个带参数的构造函数直接用高效的冒号语法进行初始化。反观第一种方案，如果获取三个参数的逻辑对于函数f是不可见的，那么我们就必须要首先默认构造A对象，然后再进行赋值操作对A对象进行初始化，非但性能低下，且代码丑陋难以维护。

在C++11中引入了右值引用的概念，即使有编译器决定将x构造在getA内部，再用它来构造对象a，这种情形也适用move constructor，而几乎没有可观的性能损耗。当然，在这种情况下，即使定义了move constructor，gcc也不会调用它。

所以，我们不应该想当然地对代码进行优化，尤其是在要牺牲代码可读性的情况下更加应该慎重：

• 首先应该考察，是否确实存在性能低下（在这个例子中没有）
• 如果性能低下，则需考察这个性能问题是否是系统性能的瓶颈
• 如果是，是否能够借助编译器优化提升性能，或者局部性地改变代码使得编译器更容易优化，或许会影响一定的代码的可读性，但对于接口的可读性没有影响
• 如果仍然无法改善，才有可能考虑牺牲接口的可读性

iSCSI（Internet SCSI）是IEFT于2003年发布的存储协议，至今已经超过10年。相比较已有20年历史的FC协议算是后生晚辈，但却在以飞快的速度蚕食FC SAN的市场份额。目前，几乎所有存储厂商都已经提供基于iSCSI协议的块存储设备、存储解决方案和技术支持。

iSCSI协议的负载数据是SCSI命令，而传输则基于久经考验的TCP/IP协议。参照OSI七层网络模型，iSCSI位于第五层会话层，将第七层的SCSI协议包封装映射到第四层的TCP协议包在以太网上进行传输。

SCSI协议是一种客户端/服务器模式的协议，iSCSI在协议封装上大量沿用了SCSI命令的语义，以及Initiator和Target的概念。在一个交互会话中，会话的发起方称为Initiator，而服务方称为Target。IQN（iSCSI Qualified Name）则是用来标识Initiator和Target身份的唯一标识符。

在部署成本方面，FC SAN需要采购专门的光纤、HBA和Fabric，有些特殊需求下还需要采购昂贵的协议分析仪，iSCSI SAN可以充分利用现有的更廉价的LAN网络资源来进行部署。

在安全性方面，由于iSCSI基于TCP/IP协议，因此可以使用IPSec对传输内容进行加密。iSCSI也可以在登陆阶段使用CHAP对会话双方进行身份认证。

在网络隔离性方面，iSCSI可以直接使用VLAN技术对网络进行逻辑分割，或者直接使用独立交换机对网络进行物理分割。

在软件定义的数据中心里，iSCSI SAN也能够更容易地直接部署在基于OpenFlow的虚拟化网络中，实现软件定义的存储。

受益于以太网技术、HBA硬件卸载技术、iSCSI软件技术的高速发展，iSCSI SAN与FC SAN原有的性能差距正在减小。

• 主流操作系统以及存储厂商能够提供成熟、高性能的iSCSI Initiator多路径支持，能够实现端口聚合和负载均衡，防止单点故障。
• 具备TCP卸载和iSCSI卸载特性得到HBA硬件厂商的广泛支持，使iSCSI SAN可以提供更低延迟的存储服务。
• iSER（iSCSI Extensions of RDMA）基于RDMA技术将CPU在内存复制、U-K通信上的性能损耗降到最低，同时特别针对iSCSI协议在TCP层面进行了优化，大幅提升了iSCSI设备的服务能力。
• 10GbE以太网技术的成熟，使iSCSI SAN满足更严苛的性能需求。40GbE和100GbE的以太网设备也在研发中。DCB无损网络机制使得以太网的冲突概率大大降低，使以太网环境更加适合高速率数据传输，以及更好地QoS，iSCSI SAN也能够减少由于丢包带来的性能损耗。

在过程式编程语言中，我们一般用某种collection来定义集合，集合中元素的数量越多，collection就会占用越大的内存空间，如果集合元素无限多，那么collection就要占用无限大的内存空间，那么在实际的计算机上就不可行了。

为了让集合的构建更加灵活，我们需要从集合的数学定义出发来进行实现。对于一个集合S={x|p(x)}，表示如果对于x，p(x)条件为真，x就是集合S的元素。所以，集合的本质就是定义了元素x和集合关系的函数p(x)，p(x)接受某种类型的参数x，返回Boolean。

  type Set = Int => Boolean

这是Scala的类型定义，含义是定义一个新类型Set，等价于接受一个Int类型参数，返回Boolean的函数。

我们再定义一个函数判断x是不是集合s的元素。

  def contains(s: Set, elem: Int): Boolean = s(elem)

我们现在就可以尝试定义一个集合。

  def odd: Set = {_ % 2 != 0}
  def r1 = contains(odd, 1) // true
  def r2 = contains(odd, 2) // false

这里odd就是所有奇数的集合。

然后让我们看看如何构建另一种基本的集合，只包含一个元素的集合。

  def singletonSet(elem: Int): Set = {_ == elem}
  def s: Set = singletonSet(100)
  def r1 = contains(s, 100) // true
  def r2 = contains(s, 101) // false

在定义s的时候使用的elem，被用于将来的比较，这样，我们通过比较传入s的参数和保存下来的elem，就可以知道传入s的参数是不是集合s的元素。

上面这些是集合的基本的building blocks，接下来让我们来定义交、并、差等集合运算，让集合产生新的集合。由于函数式编程的高阶函数特性，构建这种方法非常简单。

  def union(s: Set, t: Set): Set = {
    x: Int => contains(s, x) || contains(t, x)
  }

  def intersect(s: Set, t: Set): Set = {
    x: Int => contains(s, x) && contains(t, x)
  }

  def diff(s: Set, t: Set): Set = {
    x: Int => contains(s, x) && !contains(t, x)
  }

  def filter(s: Set, p: Int => Boolean): Set = {
    x: Int => contains(s, x) && p(x)
  }

上述函数定义完全遵循数学上集合的运算规则。

  def leap: Set = union(diff({_ % 4 == 0}, {_ % 100 == 0}), {_ % 400 == 0})
  def r1 = contains(leap, 2000) // true
  def r2 = contains(leap, 2100) // false

上面是所有闰年的集合定义，简单组合一下上面的方法就可以构建了。

先做一个简化的List定义，List对象由head（第一个元素）和tail（除了第一个元素以外所有后续元素组成的List）组成。Nil是空List对象，由于不论List的泛型类型是什么，空List的含义和行为都没有区别，因此全局只需要存在一个空List对象即Nil。

trait List[+T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
}

class Cons[T](val head: T, val tail: List[T]) extends List[T] {
  def isEmpty = false
}

object Nil extends List[Nothing] {
  def isEmpty: Boolean = true
  def head: Nothing = throw new NoSuchElementException("Nil.head")
  def tail: Nothing = throw new NoSuchElementException("Nil.tail")
}

这样就完成了List的定义。我们可以通过下面的方式来定义List对象了。

  val x: List[String] = Nil
  val ages: List[Int] = new Cons(16, new Cons(22, Nil))

首先让我们注意一下Nil的定义，Nil这个单例对象所属的类，继承自List[Nothing]，为什么可以将List[String]类型的x定义为这个对象？因为泛型类型T是协变的，而Nothing在Scala中是所有其他类的子类。所以List[Nothing]就是List[String]的子类，根据Liskov替换原则，这样的定义是合法的。

下面，我们要像List类增加一个prepend方法，用来生成一个新List，这个新List是在原List头部新增一个元素：

trait List[+T] {
  // omit other methods
  def prepend(elem: T): List[T] = new Cons(elem, this)
}

但是这样的做法是无法通过编译的。为什么？正如上一篇博客所解释的，协变类型不能作为方法的参数类型。而这样的prepend操作看似是非常符合常理的，那么是Scala的这个规则设定不合理吗？

我们再回想一下Liskov替换原则。如果Bird是Animal的子类，那么List[Bird]就是List[Animal]的子类，那么如果List[Animal]可以prepend一个Animal类型的实例，List[Bird]也可以prepend一个Animal类型的实例，可惜按照上面的定义是不可能的，因此违反了Liskov替换原则，这样的定义是错误的。

为了解决这个问题，我们需要引入泛型类型的下界的概念。

trait List[+T] {
  // omit other methods
  def prepend[U >: T](elem: U): List[U] = new Cons(elem, this)
}

这个定义的含义是，prepend方法接受一个类型为U的参数，U必须是T或T的父类（“>:”表示泛型类型的下界，而“<:”则相应地表示上界），返回类型则是List[U]。拿Animal和Bird的例子，再假设Chicken是Bird的子类，那么根据这种定义，List[Bird]可以prepend一个Animal的实例，返回List[Animal]，而prepend一个Chicken的实例并非不允许，而是U类型不会是Chicken，必须将U类型至少提升至Bird，所以prepend一个Chicken的实例，结果是返回List[Bird]。这样的定义满足Liskov替换原则，所有可以对List[Animal]进行的操作，都可以对List[Bird]进行。

接下来再举一个例子，假设BaldEagle和CrownEagle都是Aeroplane的子类，而BaldEagle和CrownEagle没有关系。那么List[BaldEagle]如果prepend一个CrownEagle的实例会是什么结果呢？类型U不能是CrownEagle，而必须被向上提升直到U是BaldEagle或者BaldEagle的父类，因此U将被提升到Aeroplane，所以结果将是返回List[Aeroplane]。

这样，可以容易地推断出Scala对于泛型上下界的规定。

• 协变类型可以作为泛型类型的下界
• 逆变类型可以作为泛型类型的上界

在Scala（以及其他许多编程语言）中，函数也是对象，可以使用、定义其他对象的地方，也可以使用、定义函数。Scala中的函数，具有apply方法的类的实例，就可以当做函数来使用。其中apply接受的参数就是函数的参数，而apply的返回值就是函数的返回值。

首先给出一个接受一个参数的函数的泛型定义。

trait Function1[-T, +U] {
  def apply(x: T): U
}

这种函数接受一个参数，参数类型为泛型类型T，返回类型为泛型类型U。和其他支持泛型的语言一样，实际定义函数时T和U的类型会被确定下来，不过需要注意的是，这边的T之前有一个“-”，而U之前有一个“+”。

在这里引入关于这个符号的说明，在声明Scala的泛型类型时，“+”表示协变，而“-”表示逆变。

• C[+T]：如果A是B的子类，那么C[A]是C[B]的子类。
• C[-T]：如果A是B的子类，那么C[B]是C[A]的子类。
• C[T]：无论A和B是什么关系，C[A]和C[B]没有从属关系。

根据Liskov替换原则，如果A是B的子类，那么能适用于B的所有操作，都适用于A。让我们看看这边Function1的定义，是否满足这样的条件。假设Bird是Animal的子类，那么看看下面两个函数之间是什么关系：

def f1(x: Bird): Animal // instance of Function1[Bird, Animal]
def f2(x: Animal): Bird // instance of Function1[Animal, Bird]

在这里f2的类型是f1的类型的子类。为什么？

我们先看一下参数类型，根据Liskov替换原则，f1能够接受的参数，f2也能接受。在这里f1接受的Bird类型，f2显然可以接受，因为Bird对象可以被当做其父类Animal的对象来使用。

再看返回类型，f1的返回值可以被当做Animal的实例使用，f2的返回值可以被当做Bird的实例使用，当然也可以被当做Animal的实例使用。

所以我们说，函数的参数类型是逆变的，而函数的返回类型是协变的。

那么我们在定义Scala类的时候，是不是可以随便指定泛型类型为协变或者逆变呢？答案是否定的。通过上面的例子可以看出，如果将Function1的参数类型定义为协变，或者返回类型定义为逆变，都会违反Liskov替换原则，因此，Scala规定，协变类型只能作为方法的返回类型，而逆变类型只能作为方法的参数类型。类比函数的行为，结合Liskov替换原则，就能发现这样的规定是非常合理的。

这种函数的泛型特性对于函数式编程非常有用。尽管C++的泛型在语法层面上不支持协变与逆变，但在C++11的function<U(T)>中，返回类型U和参数类型T也同样遵循与Scala相同的协变与逆变规则。

Eratosthenes筛法是以筛选（filter）为基本思想的计算质数的一种数学方法。求解n以内的质数步骤如下：

1. 创建一个[2, n]的自然数列表
2. val p=2（p是找到的第一个质数）
3. for (x = 2; x * p <= n; x++) { 从列表中去掉x*p }
4. p=列表中的下一个数，重复上面一步

当列表中的数遍历完，这个列表就是n以内的所有质数。我们很容易根据上述思路用任何一种语言进行实现。下面我们要利用函数式编程中的延迟求值（lazy evaluation）特性来实现求[2, +Infinity)的所有质数，在这里使用Scala语言中的Stream作为容器。

Stream的功能及操作方法类似与List，但是它的tail部分会在需要tail.head时才对tail.head进行求值，因此我们不担心定义无穷序列会耗尽系统资源，因为只有当取用时才会真正进行求值。

def sieve(s: Stream[Int]): Stream[Int] = 
  s.head #:: sieve(s.tail filter (_ % s.head != 0))

def primes = sieve(from(2))

上面三行就是全部的实现代码了。

其中，sieve就是Eratosthenes筛法中的第三步和第四步的循环，s.head的值就是当前的p，因此留下s.head，在后面所有的元素中，除去能够被p整除的数，使用sieve本身进行筛选。再将s.head prepend到新的tail之前。而from(2)将产生一个从2开始直到正无穷的Stream，作为初始的s，传给sieve方法，就能返回包含所有的质数的Stream。

让我们模拟一下Scala取primes的第一个元素的完整过程：

    primes.head
->  sieve(from(2)).head
->  (from(2).head #:: sieve(from(2).tail filter (_ % from(2).head != 0))).head
->  from(2).head
->  2

可以看到，第三行的#::后面的部分，并不需要进行求值，会等到需要的时候，再进行求值。

让我们再模拟一下取下一个元素的过程，简化的推导过程用->> 表示：

    primes.tail.head
->  sieve(from(2)).tail.head
->> (from(2).head #:: sieve(from(2).tail filter (_ % from(2).head != 0))).tail.head
->> sieve(from(2).tail filter (_ % 2 != 0)).head
->  ((from(2).tail filter (_ % 2 != 0)).head #:: sieve((from(2).tail filter (_ % 2 != 0)).tail) filter (_ % (from(2).tail filter (_ % 2 != 0)).head != 0))).head
->> (3 #:: sieve((from(2).tail filter (_ % 2 != 0)).tail) filter (_ % 3 != 0))).head
->  3

这边filter的语义比较直观，展开又过于繁琐，在这里就进行了简化。

下面我们来简单证明一下这个算法的正确性，即要证明primes中的所有元素都是质数。

首先，我们回顾一下isPrime的逻辑定义：

def isPrime(n: Int) = !((2 to n - 1) exists (n % _ == 0))

首先取s=primes，证明s不包含能被2整除的数（显然）。我们在刚才的模拟过程中已经进行了完整的证明，根据质数的定义，isPrime(2)=true。

然后要证明，如果s中不包含能被从2到s.head-1中的数整除的数（s.head是质数），s中就不包含能被2到s.tail.head-1中的数整除的数（s.tail.head是质数）。

// Condition:
    !(s exists {x => !((2 to s.head - 1) exists {y => x % y == 0})})

    s.tail.head
->> sieve(s.tail filter (_ % s.head != 0)).head

// Therefore (according to definition of "filter"):
->> !((2 to s.head) exists (s.tail.head % _ == 0)

// Hypothesis
    !isPrime(s.tail.head)
->  (2 to s.tail.head - 1) exists (s.tail.head % _ == 0)
->  (s.head + 1 to s.tail.head - 1) exists (s.tail.head % _ == 0)
->> (s.head + 1 to s.tail.head - 1) contains s.tail.head // Impossible, contradiction

    isPrime(s.tail.head)
    !(s exists {x => !((2 to s.tail.head - 1) exists {y => x % y == 0})})

先看一下下面的代码：

var a = function(x) {document.write(x + "\n");}(1); // OK - output "1"
function(x) {document.write(x + "\n");}(1); // Uncaught SyntaxError: Unexpected token (

小伙伴们就议论开了，为什么第一行的程序运行成功，而第二行的程序有语法错误呢？错误信息里提到的“(”是指哪一个括号呢？

之后又诞生了一系列的写法，来分别验证结果：

function f(x){document.write(x + "\n");}(1); // No output
(function(x) {document.write(x + "\n");})(1); // OK - output "1"
(function(x) {document.write(x + "\n");}(1)); // OK - output "1"
+function(x) {document.write(x + "\n");}(1); // OK - output "1"
~function(x) {document.write(x + "\n");}(1); // OK - output "1"

在这里先直接揭晓答案，在语句开头出现function，则被视为函数声明（FunctionDeclaration），否则视为函数表达式（FunctionExpression）。两者都同样构造一个函数对象，但是有两个区别：

1. 函数声明必须有函数名作为函数标识符，而对于函数表达式则是可选的。（上面报出语法错误的那行代码，实际上是说不允许函数声明不含有标识符）
2. 函数声明是与语句（Statement）平级，不求值的语法元素，而表达式有返回值。（上面没有输出的那行代码，是因为被视为一句函数声明，还有一句是(1);语句）

为何这样设计？

当解释器进行语法分析时，期待读入一个Statement或FunctionDeclaration，此时读入到词法元素“function”。此时就有了二义性，这里既可能是FunctionDeclaration的第一个词法元素，也可能是ExpressionStatement的第一个语法元素（即其中FunctionExpression的第一个词法元素），为了避免这种二义性，规定在这种情况下，将这个“function”视作FunctionDeclaration的第一个词法元素，于是就有了上面的结论和实验结果。