有人可以澄清Joel On Software引用的含义:(功能程序没有副作用)

我今天正在阅读Joel On Software并且遇到了这个引用:

如果不理解函数式编程,就无法发明MapReduce,这种算法使Google具有如此大规模的可扩展性.术语Map和Reduce来自Lisp和函数式编程.回想起来,对于那些从6.001等效编程类中记得纯粹功能性程序没有副作用且因此可以简单地并行化的人来说,MapReduce是显而易见的.

当他说功能性程序没有副作用时,他的意思是什么？这如何使并行化变得微不足道？

当他说功能性程序没有副作用时,他的意思是什么？

大多数人认为编程是创建变量,为它们分配值,向列表添加内容等等.变量"变化",因此名称.

函数式编程是一种设计程序以消除变量的方式 - 一切都是常量或只读.

当乔尔说功能性程序没有任何副作用时,由于它非常容易编写可以修改变量的功能程序,因此涉及到大量的挥手问题- 但很大程度上,当人们谈论函数式编程时,它们意味着没有保持任何可修改的状态.

"但朱丽叶!如果不能修改任何东西,如何编写有用的程序"

好问题!

您可以通过使用已修改状态创建对象的新实例来"修改"事物.例如:

class Customer
{
    public string Id { get; private set; }
    public string Name { get; private set; }

    public Customer(string id, string name)
    {
        this.Id = id;
        this.Name = name;
    }

    public Customer SetName(string name)
    {
        // returns a new customer with the given name
        return new Customer(this.Id, name);
    }
}

所以所有的初始化都发生在构造函数中,我们不能再次修改对象 - 我们创建新的实例,并将我们的修改传递给构造函数.

你会惊讶于你可以在多大程度上进行这种编程风格.

"但朱丽叶!？这怎么可能在所有这些复制中有效？"

诀窍是意识到您不必复制整个对象图,只复制已更改的部分.如果对象图的某些部分没有更改,可以在新对象中重复使用它(复制指针,不要在图形的该部分中新建任何对象的新实例).

你会惊讶于你可以在多大程度上进行这种编程风格.事实上,它非常容易编写许多常见数据结构的不可变版本 - 如不可变的Avl树,红黑树,多种堆等.请参阅此处了解不可变treap的实现.

在大多数情况下,数据结构的不可变版本具有与其可变对应项相同的插入/查找/删除计算复杂度.唯一的区别是插入返回数据结构的新版本而不修改原始版本.

这如何使并行化变得微不足道？

想一想:如果你有一个不可变树或任何其他数据结构,那么你可以在树中插入,删除和查找项目,而无需锁定.由于树是不可变的,因此一个线程不可能将对象置于另一个线程的鼻子下的无效状态 - 所以我们消除了与竞争条件相关的整类多线程错误.由于我们没有竞争条件,因此我们不需要锁,因此我们也消除了与死锁相关的一整类错误.

因为不可变对象本质上是线程安全的,所以它们被认为使并发"微不足道".但这只是故事的一半.这里是当我们需要在一个线程中的变化是看到另一个时代-那么,我们如何做到这一点与不可变对象？

诀窍是重新考虑我们的并发模型.我们将线程视为一种可以发送和接收消息的邮箱,而不是让两个线程彼此共享状态.

因此,如果线程A具有指向线程B的指针,则它可以将消息(更新的数据结构)传递给线程B,其中线程B将其副本与数据结构合并,并将其与接收到的消息中的副本合并.它也可以让一个线程将自己作为消息传递,以便线程A将自身发送给线程B,然后线程B通过它收到的指针将消息发送回线程A.

相信我,上面的策略使并发编程比可变状态锁定容易1000倍.因此,Joel评论的重要部分是:"如果不理解函数式编程,就无法发明MapReduce,这种算法使Google具有如此大规模的可扩展性."

传统的锁定不能很好地扩展,因为为了锁定一个对象,你需要引用它的指针 - 锁定的对象需要与执行锁定的对象在同一个内存中.您无法跨进程获取对象的锁定.

但想想上面的消息传递模型:线程正在传递消息两个并且彼此之间传递消息.将消息传递给同一进程中的线程与将消息传递给线程侦听某个IP地址之间是否真的有区别？并不是的.而且正是因为线程可以跨越流程边界发送和接收消息,消息传递和扩展,因为它没有绑定到单个机器,您可以让您的应用程序在需要的任意数量的机器上运行.

(为了它的价值,你可以使用可变消息实现消息传递,它只是没有人想要的,因为线程无法对消息做任何事情而不锁定它 - 我们已经知道它充满了问题.所以不可变是您使用消息传递并发时的默认方式.)

虽然它的水平非常高并且掩盖了许多实际的实现细节,但上述原则正是Google的MapReduce可以无限扩展的原因.

另见:http://www.defmacro.org/ramblings/fp.html

让我给你维基百科吧

简而言之,纯函数是仅根据给定参数计算事物并返回结果的函数.

将内容写入屏幕或更改全局变量(或数据成员)是一种副作用.依赖于参数中给出的数据以外的数据也会使您的函数不纯,尽管它不是副作用.

编写"纯函数"可以更容易地并行调用它的许多实例.这主要是因为纯粹,你可以肯定它不会影响外部世界,也不会依赖外部信息.

函数式编程旨在创建仅依赖于其输入的函数,并且不会在系统中的其他位置更改状态(即,不会对其执行产生副作用).

这意味着,除其他外,它们是幂等的:同一个函数可以在同一个输入上运行多次,并且因为它没有副作用,所以你不关心它运行了多少次.这对并行化很有用,因为这意味着您不必创建大量开销来跟踪特定节点是否崩溃.

当然,在现实世界中,很难将副作用保留在程序之外(即写入文件).因此,现实世界的程序往往是功能部分和非功能部分的组合.