Joh*_*ohn 5 f# haskell functional-programming scala
这是关于函数式编程的一般性问题,但我也对它在特定语言中的答案感兴趣.
我只有初学者对功能语言的了解,所以请耐心等待.
我的理解是,函数式语言把重点放在不同于命令式语言的数据结构上,因为它们喜欢不变性:持久性数据结构.
例如,它们都有一个不可变列表概念,您可以在其中形成新列表x :: l,y :: l从现有列表l和两个新项目x,y而不l需要复制所有元素.这可能是由新的列表对象实现的,内部指向旧的列表对象作为尾部.
在命令式语言中,很少使用这样的数据结构,因为它们不像c样式数组那样提供良好的引用局部性.
一般来说,找到支持功能风格的数据结构是它自己的努力,所以如果一个人不总是必须这样做会很棒.
现在,我们可以了解如何在函数式编程中使用所有经典数据结构,如果有合适的语言支持的话.
通常,命令式语言中的数据结构具有在其上定义的修改操作(伪代码):
data.modify(someArgument)
写这个的功能方式是
newData = modified(data, someArgument)
一般的问题是,这通常需要复制数据结构 - 除非语言能够知道data实际上不会被其他任何东西使用:然后,修改可以以改变原始的形式完成,没有人可以告诉区别.
有一大类案例,语言可以推断出"从未在别处使用过"的属性:当第一个参数为modified未绑定值时,如下例所示:
newData = modified(modified(data, someArgument))
在这里,data可能会在别处使用,但modified(data, someArgument)显然不是.
这就是C++中被称为"rvalue"的东西,并且在C++的最新版本中,具有讽刺意味的是它根本不起作用,人们可以在这样的rvalues上重载.
例如,人们可以写:
Data modified(Data const& data) { // returns a modified copy }
Data modified(Data && data) { // returns the modified original }
这意味着在C++中,实际上可以采用任何可变的高效数据结构并将其转换为具有不可变的api,可以以纯函数的方式使用,就像命令式版本一样有效.
(有一点需要注意,在C++中,有时候还需要强制转换rvalue.当然,需要注意实现这样的数据结构,即使用rvalue重载时.虽然可能会改进.)
现在我的问题:
实际的函数式语言是否有类似的机制？或者由于某些其他原因这不是必需的吗？
(我标记了一些我特别感兴趣的特定语言.)
确实,持久数据结构比它们的可变对应物慢.对此没有争议.有时差异可以忽略不计(迭代链表与数组),有时它可能很大(反向迭代),但这不是重点.使用不可变数据的选择是(或应该)是有意识的数据:我们为了稳定而交易性能.
考虑这一点:对于大多数(并非所有)现代计划,本地表现不是一个问题.对于今天的程序,真正的性能瓶颈在于并行化 - 在具有共享内存的本地计算机上,以及在不同的计算机上.根据我们现在处理的数据量,挤出内存位置和分支预测的最后一点不会削减它.我们需要规模.并猜测并行程序中的第一个错误来源？那是对的 - 突变.
现代计划的另一个重要问题是稳定性.程序可能会崩溃的日子已经一去不复返了,你刚刚重新启动它并继续工作.今天的程序需要在没有人工干预的无头服务器上工作数月或数年.今天的计划不仅可以抛弃其数字化武器,还希望人类能够找出问题所在.在这种情况下,本地性能远不如稳定性和并行化那么重要:购买(或租用)另外十台服务器要比雇用人员不时重新启动程序便宜得多.
确实,人们可以使用变异来制作可并行化且稳定的程序.理论上这是可能的.这更难了.对于不可变数据,您必须首先瞄准您的脚.
然后,这里有一些观点:我们已经去过那里了.您多久使用goto代码中的指令？你有没有考虑过这是为什么？你可以做各种各样的表演技巧goto,但我们选择不这样做.在编程历史的某些时刻,我们已经确定这goto比它的价值更麻烦.同样的事情发生在原始指针上:许多语言根本没有它们,其他语言则严格保护它们,甚至在那些对原始指针有无限制访问权限的语言中,它现在被认为是一种使用它们的糟糕形式.今天,我们处于下一阶段的中间:首先我们放弃了goto,然后我们放弃了原始指针,现在我们正在慢慢放弃变异.
但是,如果你真的发现自己出于正当理由推动本地性能的发展,并且你已经确定不可变数据确实是瓶颈(记住:先测量,然后优化),那么大多数函数式语言(Haskell和Elm除外)尽管不情愿,但是会让你逃避变异.就像C#中的原始指针一样,你可以有变异,你只需要明确(并且小心)它.例如,在F#中,您可以拥有可变变量,原始数组,可变记录,类,接口等.这是可能的,只是不推荐.到目前为止,普遍的共识是,只要它是局部的(即不会泄漏到外部)就可以使用突变,并且你真的知道你正在做什么,并且你已经记录了它,并将它测试为死亡.
一个常见的例子就是"价值构造",你的函数最终产生一个不可变的值,但在做这个时会做各种各样的混乱.一个例子是F#核心库如何实现List.map:通常,因为列表是从前到后迭代的,但是从前到后构造,所以需要首先通过迭代构造转换后的列表,然后将其反转.所以F#编译器在这里作弊并在构造时改变列表以避免额外的反转.
关于"地方性"问题的另一个说明.还记得我提到过你可以做各种各样的表演技巧goto吗？嗯,那不再那么真实了.由于程序员开始没有编写程序goto,二进制代码变得更加可预测,因为跳转现在由编译器生成,而不是由人类编写.这使得CPU可以预测它们,并根据这些预测优化处理.最终的结果是,现在你实际上可能通过不加选择地使用而不是使用可接受的更高级别的工具(如循环)来获得更差的性能goto.在当天,CPU无法做到那么聪明,因此不使用的选择goto纯粹是一种稳定性措施.但现在事实证明,实际上对性能有帮助,谁会想到？
我认为同样的事情也会因不变性而发生.我不确定它究竟会如何发生,但我确信它会发生.即使在今天,如果没有特殊的硬件,仍然可以在编译时进行一些优化:例如,如果编译器知道变量是不可变的,它可能决定将它缓存在寄存器中很长一段时间,甚至可以提升它完全不变的.确实,今天的大多数实际编译器都没有执行所有这些可能的优化(虽然它们确实执行了一些),但它们会.我们才刚刚开始.:-)
我非常确定像别名分析（检查数据是否在其他地方使用）这样的功能不是 Scala 编译器的一部分（也不是 Haskell 和 Clojure 等其他 FP 语言的一部分）。Scala 中的集合 API（例如）明确分为immutable和mutable包。数据结构使用结构共享immutable的概念来消除复制数据的需要，从而减少使用不可变结构的开销（就时间数据量而言）。
正如您已经指出的，像 cons 这样的方法::会创建一个新的不可变结构，该结构在幕后包含对任何现有不可变数据的引用（而不是复制它）。
mutable类型之间的转换immutable（例如在 Scala 中）会复制数据mutable（通常以惰性方式），而不是使用任何机制，例如检查结构mutable是否未在其他任何地方引用并允许其发生变异。
当我第一次从 Java 迁移到 Scala 时，我最初认为在使用不可变结构时必须创建的（通常）大量时态数据可能会成为性能限制，并且涉及一些巧妙的技术，以在安全的情况下实际允许突变。这样做，但事实并非如此，因为这个想法是不可变的数据永远不会指向更年轻的值。由于在创建旧值时新值并不存在，因此无法在创建时指向它，并且由于值永远不会被修改，因此也无法在以后指向它。结果是像 Scala/Haskell 这样的 FP 语言能够生成所有这些时态数据，因为垃圾收集器能够在很短的时间内将其删除。
简而言之，Scala/Haskell（我不确定 F#）不允许不可变结构的突变，因为像当前 JVM 这样的运行时环境的状态具有非常高效的垃圾收集，因此可以非常快速地删除时态数据。当然，我相信您知道，包含可变元素的不可变结构在像 Scala 这样的 FP 语言中是完全可能的，但是尽管可变元素可以更改，但不可变容器却不能。既不能添加/删除元素。