功能程序设计的现代体系结构


是时候了。IO需要可怕的死亡。

作为功能程序员,我们有时会自欺欺人地认为功能代码是始终更容易理解,更具声明性,更强大。

事实并非如此,下面的片段应该可以证明这一点:

blahblah :: Boolean -> Boolean -> Boolean -> IO ()
blahblah b1 b2 b3 = ...
def blahblah(b1: Boolean, b2: Boolean, b3: Boolean): Task[Unit] = ???

那个函数到底是做什么的?为什么我们又要关心它是不是“纯功能性的”?

是的,我知道,我知道:函数返回一个价值代表一个输入输出效应现在调用者对效果有了明确的控制(在命令式编程中,它是被召者这使得推理更加困难。

控制反转是函数式编程魔力的一部分。

但是在这种情况下IO,我可以忽略该值(在这种情况下,为什么函数存在?),或者我可以将它排序成一个计算链(在这种情况下,它简化为普通的命令式编程)。

欧力后者的优点是,因为它是一个值,所以它可以被填充到数据结构中,延迟执行,重试直到成功,等等。这很好,但充其量是一个代币用c语言写同样的东西的好处

来吧,这是2015。我们可以做得更好IO

自由革命

我第一次听说“自由单子”几年前,当我功能好奇但不是真正的函数编程。我有机会挖一个workshop I did for LambdaConf 2014从那以后,我多次使用自由单子,并鼓励在my company

自由单子基本上只是一种在数据结构中填充顺序计算的方法,因此您可以检查该数据结构并在以后“解释”它。

它被称为“免费”,因为你可以免费得到一个单子* -> *类型(与列表是自由幺半群的方式相同,因为它可以采用任何类型,并通过在列表中记录“追加”给你一个该类型的自由幺半群,这可以在以后重放)。

我会保留血淋淋的细节,但我想分享一个简洁的解释Free作为程序的描述(参见我的ScalaWorld 2015演示文稿了解更多信息):

  A description of a program
that will halt, run forever, or 
    produce a value `a`
            |
           / \
          /   \
         /     \
        Free f a
             ^ ^
             |  \
             |   \ Value produced by program
        Operational
          Algebra


Scala: Free[F[_], A]

在这种解释中,Free f a是一个程序的描述,f是程序可以简化为的一组操作(称为代数学在这篇文章中)和a是程序将产生的值,除非它永远停止或运行。

自由单子让我们对任意程序建模,而不是作为一系列机器代码块(即IO方法),而是作为描述语义学我们项目的。

这样的程序描述可以被内省(一次一步)、解释和转换。

此外,不仅代数组成(也就是说,如果你有代数fg,您可以将它们合成一个复合代数Coproduct f g对于一些合适的定义Coproduct),但口译员也写作——两者都是水平的垂直。

如果你能翻译fg分开成一些h你可以把它们代数的余积解释成h。此外,如果你能解释f变成g,和g变成h,那么你可以翻译f变成h(这涉及到高阶绑定,我觉得很酷!)。

自由单子体现了顺序计算的本质,而free applicatives体现并行计算的本质。

因此,使用两者或两者的混合,您可以用顺序和并行计算对任意程序建模,所有这些都简化为具有明确定义的语义的操作。

自由结构的解释

我已经多次使用“解释”这个词。这到底是什么意思?

解释就是所谓的自然转化函子之间:

type Natural f g = forall a. f a -> g a
trait Natural[F[_], G[_]] {
  def apply[A](fa: F[A]): G[A]
}

在自由单子的情况下,你可以解释Free f aFree g a之间有着自然的转换fg(以及其他方式)。这需要g至少和...一样有能力fIO是无限强大的,所以你可以解释任何事情IO)。

注意,如果g本身就是一个Monad,那么你就可以崩溃了Free g a变成g a

一般来说,在大多数自由单子的例子中,代数被直接解释为有效的单子,如IO

虽然这种方法在技术上优于在IO(您获得了隔离和推理效果、模块化解释等能力),有强大得多技术。

这些技术可以永远改变我们编写功能程序的方式。

从煤到钻石

下面的片段展示了我认为的惯用手法,越好越好现代商业应用的逻辑:

saveFile :: Path -> Bytes -> IO Unit
saveFile p f = do
  log ("Saving file" ++ show (name p) ++ " to " ++ show (parentDir p))
  r <- httpPost ("cloudfiles.fooservice.com/" ++ (show p)) f
  if (httpOK r) then log ("Successfully saved file " ++ show p)
  else let msg = "Failed to save file " ++ show p
  in log msg *> throwException (error msg)

该功能通过日志记录和错误处理将资源保存到云存储中。

虽然“纯粹是功能性的”,但这段代码非常糟糕(抱歉,只是存在!):

  1. 这很难理解。
  2. 很难测试。
  3. 它将不同的关注点(日志记录、错误处理、业务逻辑)融合在一起,而解开它们将会引入更多的复杂性。
  4. 它混合了不同的抽象层次(休息应用编程接口和业务逻辑)。
  5. 它分发应该集中的知识(例如在哪里以及如何与云文件应用编程接口交互)。

让我们用自由代数的幂来解决这些问题。

洋葱的层次

我们的第一步是为云文件应用编程接口定义一个代数。

这个应用编程接口应该有明确定义的语义,并且是高级的和可组合的。

也就是说,它应该拥有高级语义,并且应该从尽可能少的正交操作中构建,依靠组合来满足更高级的用例。

在我们的例子中,假设我们只需要两个操作:一个存储文件,一个列出存储的文件:

data CloudFilesF a
  = SaveFile Path Bytes a
  | ListFiles Path (List Path -> a)

有了这个代数,我们可以定义一个轻量级的特定领域语言用于与应用编程接口交互的:

type CloudFilesAPI a = Free CloudFilesF a

saveFile :: Path -> Bytes -> CloudFilesAPI Unit
saveFile path bytes = liftF (SaveFile path bytes Unit)

listFiles :: Path -> CloudFilesAPI (List Path)
listFiles path = liftF (ListFiles path id)

(这太专业了,但暂时忽略它。(

请注意,我们的DSL定义了语义学云文件应用编程接口(甚至可以定义法律对于这些操作),但实际上没有描述怎么提供服务。

事实上,云文件应用编程接口是一个休息应用编程接口,所以我们可以表达CloudFilesF就...而言另一个DSL:一个用于REST应用编程接口。

这个代数的一个简单近似可能是这样的:

data HttpF a
  = GET    Path (Bytes -> a)
  | PUT    Path Bytes (Bytes -> a)
  | POST   Path Bytes (Bytes -> a)
  | DELETE Path (Bytes -> a)

现在,我们可以通过实现以下函数来明确定义云文件应用编程接口的语义如何映射到RESTful应用编程接口的代数中:

cloudFilesI :: forall a. CloudFilesF a -> Free HttpF a

这个解释函数需要一个操作CloudFilesF,并将其解释为HttpF

我们的核心应用可以用高级的、以领域为中心的代数来表达CloudFilesF,而在某个时候,这将被动态地解释为低级的、以协议为中心的代数HttpF

我们还没完。我们最初的片段有日志记录。我们可以定义一个新的代数,而不是把它与域逻辑或协议逻辑纠缠在一起LogF要捕获日志记录:

data LogF a
  = Log Level String a

然后我们可以定义另一个从哪个解释器映射CloudFilesF变成LogF

logCloudFilesI :: forall a. CloudFilesF a -> Free LogF Unit
logCloudFilesI (SaveFile p _ _) = liftF $ Log Debug ("Saving file to " ++ show p) Unit
logCloudFilesI (ListFiles p _)  = liftF $ Log Debug ("Listing files at " ++ show p) Unit

口译员撰写,所以我们可以采取cloudFilesI解释器,并用logCloudFilesI翻译,产生一个新的翻译:

loggingCloudFilesI :: forall a. CloudFilesF a -> Free (Coproduct LogF HttpF) a
loggingCloudFilesI op = toLeft (logCloudFilesI op) *> toRight (cloudFilesI op)

助手在哪里工作toLefttoRight举起aFree f a或者Free g a变成一个Free (Coproduct f g) a分别为。

最后,在世界的尽头,我们将不得不从我们的最终代数中提供一个映射(在这种情况下,Coproduct LogF HttpF)变成类似IO

executor :: forall a. Coproduct LogF HttpF a -> IO a

请注意这种方法带来的一些好处:

  1. 与云文件服务交互的代码不知道也不关心它是如何实现的。云文件层专注于我们的问题领域,并以正确的抽象级别说话。
  2. 从云文件服务的语义到REST APIs的语义的映射是完全集中的,并且与应用程序的其余部分隔离开来。我们甚至不用这个翻译!例如,为了测试,我们可以将云文件服务映射到一个模拟服务中,该服务直接表达高级语义。
  3. 日志记录代码也是集中的和独立的,并且与业务逻辑和REST APIs完全分离(注意,如果我们想将日志记录推广到所有“编译”到REST APIs的服务,我们也可以在REST APIS级别进行日志记录)。日志本身可以是结构化和统一的,而不是随机的,分散在整个程序中。此外,日志记录不需要记录到文件中,因为我们可以提供不同的解释器——一些解释器放弃日志记录,另一些解释器记录到远程应用编程接口。
  4. 一切都是模块化和可组合的。我们可以选择如何解释程序,即使基于运行时间值通过适当组成口译员。

享受洋葱

我们已经从一个低级的、命令式的应用编程接口,变成了对我们的问题域的声明式描述。我们能够在高层次和低层次上描述我们的问题,并提供不同领域和抽象层次之间映射的精确方法。

我们还能够完全解开我们程序的不同方面,比如从一个高级域到一个REST API的映射,或者应用程序活动的记录。

最后,我们能够整合原本会分布在整个程序中的知识:如何将云文件操作转换为REST应用编程接口调用的知识;如何记录和记录什么的知识。

完善方法

我认为这种方法的好处是显而易见的,即使是在这个玩具例子中。然而,在现实世界中,好处应该更有说服力。

也就是说,我们可以调整一些东西来改善它。

1.正交可组合代数

在许多现实世界中,自由代数不是正交的。相反,有大量的重叠操作。

原因之一是实用性:有时提供大量重叠操作比提供少量正交操作更有效。

让我们以文件系统代数为例(FileF)。一种方法是简单地列出文件系统中所有可用的常见操作:

data FileF a
  = MakeDir Path a
  | Delete Path a
  | Copy Path Path a 
  | Rename Path Path a 
  | Move Path Path a 
  | Ls Path (List Path -> a)
  | CreateFile Path Bytes a  
  | ReadFile Path (Bytes -> a)
  | AppendFile Path Bytes a

但是这组操作不是原始的;也就是说,一些操作可以由其他操作组成。为了简化推理、形式化语义和减少代码总量,我们应该用一组完全正交的操作来代替这个列表。

例如:

data FileF a
  = CreateFile Path a
  | CreateDir Path a
  | AppendFile Path Bytes a
  | Duplicate Path Path a
  | Delete Path a
  | Ls Path (List Path -> a)
  | ReadFile Path (Bytes -> a)

在这种形式下,任何操作都不能用其他任何形式来表示。此外,我们还可以为移动等操作提供复合操作:

rename :: Path -> Path -> Free FileF Unit
rename from to =
  (liftF $ Duplicate from to Unit) *>
  (liftF $ Delete from Unit)

虽然从理论角度来看是理想的,但作为一个实际问题,您能想象通过首先创建一个10 GB文件的副本,然后删除旧版本来重命名它吗?!?

这种低效率对大多数现实世界的程序来说是不现实的!

为了解决这个问题,我们可以写一个优化解释器,这是一种特殊的解释器,可以检测模式并用语义上等价但更快的替换来替换它们。

这里有一个限制:自由单子是太强大了优化,因为操作依赖于运行时值(bind!)。

但是,自由应用程序受到了足够的限制,允许我们执行这种优化。或者我们可以用一种特殊的原子排序操作来扩展我们的自由结构*>或者>>)。

无论是哪种情况,这都让我们的解释器能够深入了解程序的结构,以执行语义等价的优化(例如用操作系统级的重命名/移动来替换重复/删除)。

2.概括口译员

我为上面的玩具示例编写的解释器非常具体:它们只能解释一个具体的目标代数。

通过推广这些解释器,我们可以使代码对变化不那么敏感,并最大化我们可以使用它们的地方。

口译员的一般形式如下:

type Interpreter f g = forall a. f a -> Free g a

这意味着一次操作f a变成一个操作程序g

但是与其解释为具体的g,我们希望能够说,我们可以解释为任何的g支持我们需要的能力。

有很多方法可以做到这一点(哈斯克尔的类型级机制,Scala的隐式机制,类型类),但是最直接的方法是利用一些透镜机制:具体来说,就是Prism

APrism让我们构建和(如果可能的话)解构求和类型。

第一步是定义一个可以与函子一起工作的高阶棱镜:

type Inject f g = forall a. PrismP (f a) (g a)

这让我们构建一个f a每当我们有g a

我们现在可以概括解释者的概念:

type Interpreter f g' = forall a g. Inject g g' -> f a -> Free g a

换句话说,只要你能证明g至少和g'(通过提供一个Inject),然后是解释器(这需要g')可以解释成g

这个翻译是完全目标代数中的多态。虽然定义起来有点麻烦,但这种更通用的解释器对代码更改更健壮,可以在更多地方使用。

3.一般化DSL

我们能做的最后一个显而易见的改进是推广DSL。

我之前为云文件应用编程接口引入了以下DSL:

type CloudFilesAPI a = Free CloudFilesF a

saveFile :: Path -> Bytes -> CloudFilesAPI Unit
saveFile path bytes = liftF (SaveFile path bytes Unit)

listFiles :: Path -> CloudFilesAPI (List Path)
listFiles path = liftF (ListFiles path id)

该DSL要求目标代数为CloudFilesF。我们可以用概括解释器的同样方式概括这一点:通过要求目标代数至少像CloudFilesF

下面的概括利用了PureScript的一流记录,尽管还有许多其他方法来避免其他语言中的样板文件:

type CloudFilesDSL g = {
  saveFile  :: Path -> Bytes -> Free g Unit,
  listFiles :: Path -> Free g (List Path) }

cloudFilesDSL :: forall g. Inject g CloudFilesF -> CloudFilesDSL g
cloudFilesDSL p = {
  saveFile  : \path bytes -> liftF $ review p (SaveFile path bytes Unit),
  listFiles : \path       -> liftF $ review p (ListFiles path id) }

现在我们可以在任何目标代数中使用DSL,包括CloudFilesF

摘要

太多的“纯功能”代码是通过顺序执行不透明的机器代码块来编写的。那是IO哈斯克尔的单子,Task在斯卡拉,还有Eff在PureScript中。

这导致了我们在命令式编码中看到的所有反模式:混合抽象层次、分发应该集中的知识、纠缠关注点等等。导致面向方面编程、依赖注入、运行时元编程和其他高尚思想的发明的问题,如果最终试图修复大规模编程的错误的话。

幸运的是,今天的函数式编程工具包有一个更好的解决方案:通过将效果简化为正交的、可组合的操作来描述效果,并使用计算上下文来描述这些操作的计算,如Free

换句话说,在现代FP中,我们不应该写程序——我们应该写描述我们可以随意反思、转换和解释。

这导致了一种编程风格,即大型程序被分解成多个层。这些层代表不同的抽象层次和不同的关注点。

最终,所有这些“层”被编译成类似于IO,但这是程序的边缘。在这两者之间,可以推理和操作的高度受限的代数被表达成越来越宽的代数,它们越来越接近执行所需的“机器代码”。

这篇文章中概述的方法非常肯定函数式编程的未来。这里有一些我还没有谈到的问题,而且大多数语言都没有让这种特殊的编程风格变得非常简单或高效。

但我相信这暗示了未来的样子。我们的程序更像编译器而不是机器指令列表的未来。集成测试已死的未来。即使是最大的程序也可以被分解成更小的部分来理解。

这是我非常期待的未来。

你呢?