scala – 函数式编程是否会降低Von Neumann的瓶颈？

哦,伙计,这是经典之作. John Backus’ 1977 ACM Turing Award lecture is all about that: “Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs.”(论文“Lambda：The Ultimate Goto”在同一次会议上发表.)

我猜你或者提出这个问题的人都记得那个讲座. Backus所谓的“冯·诺伊曼瓶颈”是“一个连接管,它可以在CPU和商店之间传输一个单词(并向商店发送一个地址).”

CPU仍然有数据总线,但在现代计算机中,它通常足以容纳一个单词矢量.我们也没有摆脱我们需要存储和查找大量地址的问题,例如链接到列表和树的子节点.

但巴克斯不只是谈论物理架构(强调增加)：

Not only is this tube a literal bottleneck for the data traffic of a problem,but,more importantly,it is an intellectual bottleneck that has kept us tied to word-at-a-time thinking instead of encouraging us to think in terms of the larger conceptual units of the task at hand. Thus programming is basically planning and detailing the enormous traffic of words through the von Neumann bottleneck,and much of that traffic concerns not significant data itself but where to find it.

从这个意义上讲,函数式编程在很大程度上成功地让人们编写了更高级的函数,比如地图和缩减,而不是“一次一字一词的思考”,例如C的for循环.如果你试图今天,对C语言中的大量数据执行操作,就像1977年一样,您需要将其编写为顺序循环.潜在地,循环的每次迭代都可以对数组的任何元素或任何其他程序状态执行任何操作,甚至可以使用循环变量本身进行任何操作,并且任何指针都可能对这些变量中的任何变量进行别名.当时,Backus的第一个高级语言Fortran的DO循环也是如此,除了关于指针别名的部分.为了在今天获得良好的性能,你试图帮助编译器弄清楚,不,循环并不真正需要按照你指定的顺序运行：这是一个可以并行化的操作,比如一些减少或转换其他数组或单独的循环索引的纯函数.

但这已不再适合现代计算机的物理架构,现代计算机都是矢量化对称多处理器 – 就像70年代后期的Cray超级计算机一样,但更快.

实际上,C标准模板库现在在容器上具有完全独立于实现细节或数据内部表示的算法,而Backus自己的创建Fortran在1995年添加了FORALL和PURE.

当你看到今天的大数据问题时,你会发现我们用来解决它们的工具类似于功能习语,而不是Backus在50年代和60年代设计的命令式语言.在2018年你不会写一堆for循环去做机器学习;你可以像Tensorflow那样定义一个模型并对其进行评估.如果您想同时使用大量处理器来处理大数据,那么知道您的操作是关联的非常有用,因此可以按任何顺序进行分组然后组合,从而实现自动并行化和矢量化.或者数据结构可以是无锁且无等待的,因为它是不可变的.或者,矢量上的变换是可以使用另一个矢量上的SIMD指令实现的映射.

例子

去年,我用几种不同语言编写了几个短程序来解决一个问题,即找到最小化三次多项式的系数. C11中的蛮力方法在相关部分看起来像这样：

static variable_t ys[MOST_COEFFS];

//      #pragma omp simd safelen(MOST_COEFFS)
      for ( size_t j = 0; j < n; ++j )
        ys[j] = ((a3s[j]*t + a2s[j])*t + a1s[j])*t + a0s[j];

      variable_t result = ys[0];

//      #pragma omp simd reduction(min:y)
      for ( size_t j = 1; j < n; ++j ) {
        const variable_t y = ys[j];
        if (y < result)
          result = y;
      } // end for j

C 14版本的相应部分看起来像这样：

const variable_t result =
    (((a3s*t + a2s)*t + a1s)*t + a0s).min();

在这种情况下,系数向量是std :: valarray对象,STL中的一种特殊类型的对象,它们的组件如何被别名化,并且其成员操作是有限的,并且对操作有很多限制安全地矢量化声音很像纯函数的限制.允许的减少列表,如最后的.min(),是not coincidentally,类似于Data.Semigroup的实例.如果你查看< algorithm>,你会看到类似的故事.在STL.

现在,我不会声称C已经成为一种功能语言.事实上,我让程序中的所有对象都不可变并由RIIA自动收集,但这只是因为我已经有很多功能编程,这就是我现在喜欢的代码.语言本身不会强加诸如不变性,垃圾收集或没有副作用之类的东西.但是,当我们看看Backus在1977年所说的真正的冯·诺伊曼瓶颈时,“一个知识瓶颈让我们一直在思考,而不是鼓励我们用更大的概念单位来思考手头的任务,“这适用于C版本吗？这些操作是系数向量的线性代数,而不是一次一个字. C借用来做这个的想法 – 以及表达模板背后的想法更是如此 – 主要是功能概念. (将该片段与K& R C中的内容进行比较,以及Backus如何在1977年图灵奖演讲的第5.2节中定义了计算内部产品的功能程序.)

我还在Haskell中编写了一个版本,但我不认为它是逃避那种冯诺依曼瓶颈的一个很好的例子.

完全可以编写满足Backus对冯诺依曼瓶颈的所有描述的功能代码.回想一下我本周写的代码,我自己就完成了.构建列表的折叠或遍历？它们是高级抽象,但它们也被定义为一次一个字的操作序列,当您创建和遍历单链表时,通过瓶颈传递的一半或更多数据是地址其他数据！它们是通过von Neumann瓶颈放置数据的有效方式,这就是我为什么这样做的原因：它们是编程冯·诺依曼机器的伟大模式.

但是,如果我们对以不同方式编码感兴趣,那么函数式编程为我们提供了工具. (我不会声称它是唯一可以做到的.)将缩减表示为foldMap,将其应用于正确的向量,并且monoidal操作的关联性可以让您将问题分成任何大小的块你想要并在以后组合这些作品.在单个链接列表以外的数据结构上进行操作而不是折叠,并且可以自动并行化或矢量化.或者以产生相同结果的其他方式进行转换,因为我们已经在更高的抽象级别上表达了结果,而不是一次一个字的特定操作序列.

到目前为止我的例子都是关于并行编程的,但我确信量子计算会从根本上改变程序的外观.