4.2　现实中的“投影”

从上述大师们的理论和观点中我们看到了语言与思维之间存在着某种联系。那么两者间的这种联系在真实编程世界中的投影又是什么样子的呢？我们来看一个简单的编程问题——素数筛。

问题描述：素数是一个自然数，它具有两个截然不同的自然数除数：1和它本身。这里的问题是如何找到小于或等于给定整数n的素数。针对这个问题，我们可以采用埃拉托斯特尼素数筛算法。

算法描述：先用最小的素数2去筛，把2的倍数筛除；下一个未筛除的数就是素数（这里是3）。再用这个素数3去筛，筛除3的倍数……这样不断重复下去，直到筛完为止（算法图示见图4-1）。

图4-1　素数筛算法图示

下面是该素数筛算法的不同编程语言的实现版本。

（1）C语言版本

// chapter1/sources/sieve.c

#include <stdio.h>

#define LIMIT  50
#define PRIMES 10

void sieve() {
    int c, i,j,numbers[LIMIT], primes[PRIMES];

    for (i=0;i<LIMIT;i++){
        numbers[i]=i+2; /*fill the array with natural numbers*/
    }
    for (i=0;i<LIMIT;i++){
        if (numbers[i]!=-1){
            for (j=2*numbers[i]-2;j<LIMIT;j+=numbers[i])
                numbers[j]=-1; /* 筛除非素数 */
        }
    }
    c = j = 0;
    for (i=0;i<LIMIT&&j<PRIMES;i++) {
        if (numbers[i]!=-1) {
            primes[j++] = numbers[i]; /*transfer the primes to their own array*/
            c++;
        }
    }
    for (i=0;i<c;i++) printf("%d\n",primes[i]);
}

（2）Haskell版本

// chapter1/sources/sieve.hs

sieve [] = []
sieve (x:xs) = x : sieve (filter (\a -> not $ a `mod` x == 0) xs)

n = 100
main = print $ sieve [2..n]

（3）Go语言版本

// chapter1/sources/sieve.go

func Generate(ch chan<- int) {
    for i := 2; ; i++ {
        ch <- i
    }
}

func Filter(in <-chan int, out chan<- int, prime int) {
    for {
        i := <-in
        if i%prime != 0 {
            out <- i
        }
    }
}

func main() {
    ch := make(chan int)
    go Generate(ch)
    for i := 0; i < 10; i++ {
        prime := <-ch
        print(prime, "\n")
        ch1 := make(chan int)
        go Filter(ch, ch1, prime)
        ch = ch1
    }
}

对比上述三个语言版本的素数筛算法的实现，我们看到：

• C版本的素数筛程序是一个常规实现。它定义了两个数组numbers和primes，“筛”的过程在numbers这个数组中进行（基于纯内存修改），非素数的数组元素被设置为-1，便于后续提取。
• Haskell版本采用了函数递归的思路，通过“filter操作集合”，用谓词（过滤条件）\a -> not $ a `mod` x == 0筛除素数的倍数，将未筛除的数的集合作为参数传递归递给下去。
• Go版本程序实现了一个并发素数筛，它采用的是goroutine的并发组合。程序从素数2开始，依次为每个素数建立一个goroutine，用于作为筛除该素数的倍数。ch指向当前最新输出素数所位于的筛子goroutine的源channel。这段代码来自Rob Pike的一次关于并发的分享[1]。Go版本程序的执行过程可以用图4-2立体地展现出来。

图4-2　Go版本素数筛运作的示意图