函数式编程中的 Monad

函数式编程作为一种不同的编程范式(programming paradigm),在编程语言发展的不同历史时期都体现出顽强的生命力。即便在当前面向对象语言主导的编程世界,函数式编程思想依然被广泛借鉴。例如 Kotlin 的函数式编程库 Arrow;C# 中引入的函数式编程;自 Java 8 起提供的 Stream 接口等……但同时我们也明显注意到,由于面向对象和面向过程语言的长期影响,程序开发人员接触的函数式编程概念极为有限——函数是一等公民;纯函数的好处;不可变性等。然而一旦去思考一个函数式语言实现的系统是什么样子的时候,就概念模糊了。而这就进一步限制了我们高效地使用混合型编程范式的语言,尤其是函数式特性的部分。大多数人不了解函数式编程的全貌,认为函数式只适用于处理集合的场景。因此,学习一门纯粹的函数式编程语言对程序开发人员来说,仍旧十分必要。而我也希望通过一系列的文章,来探讨函数式编程的设计原则和方法。

我们都知道,面向对象语言最重要的概念是:封装(encapsulation)、多态(polymorphism)和继承(inheritance)。著名的 SOLID 原则,对前面三个概念稍作展开讨论。为了帮助我们写出可扩展,易维护的程序,四人帮(GoF)又为我们提供了 23 种设计模式(design patterns),在更落地的层面指导我们的日常编程。对应地,在使用函数式语言开发软件时,我们也希望基于函数式的原则,寻找到更加广泛的模式,以解决软件设计中反复出现的问题,提升开发效率。

函数式编程设计原则,则涉及四个重要概念:借鉴数学、类型(type)、函数(function)和组合(composition)。纯函数在函数式编程中被推崇备至,它能带来诸多好处:延迟计算;缓存数据;无执行顺序依赖;并行计算。区别于面向对象中类(class)的概念,函数式编程中的类型,隔离了数据和行为(面向对象中使用类将数据和行为封装绑定在一起)。函数作为一等公民,不依赖于任何类似于面向对象中类的概念,独立存在。类型,既可以是函数的输入和输出类型,也可以是函数本身,如 f: Int -> Int。当有两个函数,function1: Int -> Stringfunction2: String -> Char 时,我们就能通过函数组合得到第三个函数:function3: Int -> Char。当然,函数式编程也提供了类型组合,在此不做赘述。

至此,我们对函数式编程的基本设计原则有了共识。接下来,我们通过案例来引出本文主角,也是我要探讨的第一个函数式设计模式。如下图一,我们在日常编程中常常会看到,由于不确定某个值是否为空,于是我们用大量的 if-else 语句来判断。这种代码一方面降低了我们编码的效率,同时让软件的可维护性大大降低——一定有人在此处添加更多的 if-else 语句。我们直觉性地会使用 Option 来代替并消除 null 这个代码坏味道,如下图二。

null_checks_example
图一:null check 示例
null_checks_with_option
图二:使用 Option 做 null check

我们仍旧不满足这样的代码。所以,我们继续,简单地将 if-else 抽取到单独的小方法里,如下图三。代码看上去确实整洁了一些,但是一定有人质疑这种做法并没解决根本问题—— if-else 语句仍旧是大量重复的,而我们只是将其挪了位置而已。

null_checks_simple_refactoring
图三:使用 Option 做 null check

那么我们继续观察重构过后的代码。if-else 这段模板代码一直在重复被执行—— 先是函数 refactoredNullCheckExample 使用 if-else 的语句调用 dealWithXdealWithX 使用 if-else 的语句调用 dealWithY,以此类推……我们发现一个模式(pattern)—— 函数 simpleChainablePattern!而重写后的 nullCheckExample,变成了 newNullCheckExample,如下图四。

refactored_example
图四:使用 pattern 重构

现在,我们看到代码变得十分简洁流畅。而且,我认为你一定也像我一样认可这个重构。

接下来我们总结一下该 pattern 的特征。如下图五所示。首先,我们有一个一般化的容器(Container,对类型的包装)包装 T 类型的实例,整体作为输入。为了达到链式函数调用的目的,我们期望 addStep 操作的返回值类型仍为该一般化容器包装另一种(或同一种)类型的实例。因此,作为 addStep 参数的函数,必须保证其返回值类型也是该一般化容器,而非靠 addStep 完成类型的转换——pattern 本身应尽量简单通用。由此我们看到,只要遵循这种操作,我们就可以在 addStep 之后继续 addStep,实现这种链式调用,保持流畅性。

图五:pattern 解析

以上这个模式,我们称它为 Monad。 这也就引出了我们本文所要讨论的主题。根据定义,Monad 在函数式编程中的一种设计模式,它通过自动抽离程序逻辑所需的模板代码,让程序结构一般化,通用化。这一类的模式,我们其实经常能够碰到。例如,Kotlin 的 Sequence(如下代码片段)和 Iterable 接口。在操作 Sequence 的实例时,能够非常方便地通过 flatMap 方法,对输入做连续的变换。

fun <T, R> Sequence<T>.flatMap(transform: (T) -> Sequence<R>): Sequence<R>

前面我们讲的都是按顺序调用时应用 Monad 的案例,而我们在日常工作中常常也会遇到非顺序工作流(Non-Sequential workflow)。考虑场景:帮助演讲者预订机票。机票的预订同时依赖 speaker 信息和根据 speaker 信息获取到的 city 信息。这个场景的不同之处在于,我们还必须保存 city 操作之前的计算步骤结果,即 speaker 的信息。于是,我们考虑如下实现(Kotlin 语言),

non_sequential_workflow
图六:non-sequential workflow 示例

我们仍旧应用了 Monad 模式——flatMap 帮助做类型转换。但是我们观察到,这种实现方式带来的问题就像本文最开始讨论的 if-else 示例,代码很快就会变得不可维护。那我们该如何改善这段代码呢?幸运的是,在诸如 C# 和 Kotlin (Arrow) 等编程语言中,为 Monad 提供了高可读性的 async/await 代码。以 Kotlin 的库 Arrow 提供的此类特性为例,

non-sequential_work_flow_monad
图七:Kotlin 中的 Monad 处理非顺序工作流

Arrow 中,任何 Monad 都有一个名为 binding 的方法(上图中的 Monad.fx.monad)。该方法的定义为,

fun <A> monad(c: suspend MonadSyntax<F>.() -> A): Kind<F, A>

,它的参数是一个 suspend 函数。也就是说,binding 方法接收的参数是一个 suspend 函数。Arrow 借助 suspend 函数在 coroutines 上执行的特性,保证了 binding 方法内部按顺序执行。需要强调的是,上图八中,变量名上加括弧,或是显式调用 bind() 方法,其作用等价于调用 Monad 的 flatMap 方法,传递的参数是类似于 { speaker -> speaker.nextTalk() } 的函数。虽然代码看上去仍旧不如按顺序工作流情景下 Monad 模式所带来的流畅度好,但是我们至少保证了单层调用,从而降低代码复杂度。

以上,就是关于函数式编程中 Monad 的一个基本探讨。最后,就像其他所有介绍 Monad 文章,需要提及一下 Monad Laws。记f: (a: A) => F<B>g: (b: B) => F<C>h: (b: C) => F<D>。 运算符 表示两个函数的组合。

  • Left Identify law。即 Monad 的构造是中立的。它不改变被用于构造的值,同时不影响函数(如上例中 flatMap 的参数)调用的结果。亦即 flatMap(just) • f = f
  • Right Identity law。即一个已存在的 Monad,记 M1,将它包装的值用于构造另一个 Monad,记 M2,对其做类型转换(如上例中的 flatMap)之后的结果仍 M1。亦即 flatMap(f) • just = f
  • Associativity law。也就是结合律,函数结合的先后顺序不会影响最终计算的结果。 亦即 flatMap(f) • (flatMap(g) h) = flatMap((flatMap(f) g)) h

对于初学者来说,只建议稍作了解,而不用深入研究。

编程中的「消息通信」

在之前的一篇关于「面向对象编程」讨论的文章中,我想着重强调「消息通信」这一概念在原初设计面向对象系统时的重要性。不过,在二零一九年 OO 大行其道的现状下,来理解「消息通信」和面向对象编程之间的关联,确实不容易。那么如何帮助大家在 2019 年理解这一概念呢?我希望在本文中尝试回答。

在编程的上下文讨论消息传递时,一般有两种定义。第一种定义是大众广泛理解的,在并发编程范式中,消息通信是异步分发的一种方法,用于在进程间的通信。不同的进程甚至可能存在于不同的机器上。通常,不同的并发模型可能会有不同角度的考量,如 receiver 需不需要和 sender 在某地汇合,亦或者,receiver 需不需要为 sender 命名以作区分等等。第二种定义则是 Smalltalk 系编程语言中涉及的,非常简单,即对象的方法调用。在 Smalltalk 中,消息是异步的。也就是说,调用者(caller)会等待被调用者(callee)返回结果。

Smalltalk 的消息通信

Smalltalk 使用「消息通信」可以追溯到它的起源。受 Actor 设计思想的启发和影响,最初被设计出来的 Smalltalk 系语言不是过程式的,它没有过程调用的概念,而是 Actor 式消息传送的变种。但这一设计在之后 Smalltalk 的版本演化中被移除了,原因之一是 Actor 式的计算模型在传统工作站下模拟出来的成本非常高。另外就是受当时 Lisp 研究实际在工作站上运行的结果影响。尽管后来彻底演变成了传统的过程式语言(更像是 Lisp 的变体),但是 Actor 模型下的术语被沿用了下来。再后来随着硬件性能的指数级增长,在过程式计算的硬件设备上模拟基于 Actor 模型的计算变得便宜,Alan Kay 开始后悔当初因性能问题而把 Smalltalk 改变为基于过程式计算模型的编程语言。也因此才有了那篇被激烈讨论的邮件

梳理清楚了面向对象语言中「消息通信」这个名词的来源,让我们继续用该名词,详细看下 Smalltalk 中的消息通信。

Smalltalk 中,可以把消息理解成进行计算的请求。当一个对象接收到消息时,它负责响应消息——执行消息所表示的计算。具体来说,该对象根据消息名,在自己的方法命名空间(method namespace)中匹配并执行方法。方法在 Smalltalk 中亦为对象,它本身包含有算法过程(计算可能有副作用)。概念上,方法可类比于函数(function)或者子进程(subroutine),消息类比于函数或者子进程的调用。消息(或方法)的名字是它的选择器(selector),消息(或方法)选择器表达它本身的意图,同时用以区分不同的消息(或方法)。另外,消息可能含有零个或更多的参数。一般地,方法可能接收零个或者更多参数,所以最终这些消息中的参数也就作为方法所接收的参数。方法命名空间(method namespace)维护了一组方法选择器和方法的映射关系,使用选择器可查找对应要执行的方法。动态消息分发(dynamic message dispatch)代指使用方法命名空间找到对应方法的过程。应注意的是,Kay 博士(Alan Kay,Smalltalk 作者)使用方法(method)这一名词指代那些使用运行时动态消息分发方式,因响应消息而被调用的函数或者子线程。而这也是 Smalltalk 中方法和其他语言中函数的本质不同。也正是因为动态消息分发,发送消息给对象完全取决于接收消息的对象。同样的消息发送给不同的对象,可能会被解释为成完全不同的意义。这是因为,不同的对象可能使用不同的方法命名空间通过消息选择器查找方法,同样的消息选择器可能关联不同的方法。也正因此,消息可以被理解为抽象方法调用,即接收消息的对象来选择具体要执行的方法。此时,消息负责为逻辑计算过程命名,接收该消息的对象则负责实际的计算过程。

举个例子来理解下 Smalltalk 中消息传递的概念。假设我们已经有一个 Student 的类和变量 aPerson,Student 类包含一个 name 方法。让我们来看以下语句,

^Student new name: aPerson name

按照消息执行的顺序,以上的声明语句按照如下顺序执行,

  1. 发送消息 new 至 Student 类;
  2. 发送消息 name 至变量 aPerson 所指向的对象;
  3. 发送消息 name: (连同上一步的返回结果,作为参数)至消息 new 的结果,即实例化 Student 的对象;

由于消息 name: 没有重写默认返回值,因此上述声明语句会返回实例化 Student 的对象,也即消息 name: 消息的接收者。

Elixir 的消息通信

和 Erlang 一样,Elixir 基于 Erlang VM,致力于方便地构建可扩展易维护的应用程序。在借用了 Erlang 的优势的前提下,汲取了其他编程语言的精华,以此来提升 Erlang 中缺失的代码组织的能力——编写,分析和修改的能力。

Elixir 的代码运行在 process 中。不同的 process 彼此独立,它们并行运行的同时通过发送消息来互相沟通。需要注意的是,Elixir 中 process 的概念和我们平时所说的操作系统的进程(process) 完全不是一个层级的概念。Elixir 中的进程极其轻量,也因此,我们可以使用 Elixir 轻松启动数以百万计的进程。

我们通过 Elixir 中 send 和 receive 来进一步说明进程间消息传递的方式。send 用于从当前进程向另外某一进程发送消息,

iex> send self(), {:hello, "world"}
{:hello, "world"}

。以上代码中,当前进程给自己发送了一条消息 {:hello, “world”}。然后我们执行以下 receive 代码处理接受到的消息,

iex> receive do
...> {:hello, msg} -> msg
...> {:world, msg} -> "won't match"
...> end
"world"

。仍旧是当前进程,匹配接收的消息以决定如何处理。

Elixir 的每个进程都有属于自己的信箱(process mailbox),一旦有消息被发送至某个进程,该消息则会立即被存储在目标进程的信箱中。目标进程的 receive 块,会遍历信箱,查找匹配给定模式的消息。上例中如模式 :hello。如果信箱中的消息没有匹配到任何给定模式,则当前进程会一直等待,直到信箱中进来模式匹配成功的消息。(此时一个比较常见的处理方式是制定 timeout)另外,发送消息的进程本身不会产生阻塞,一旦它把消息投递到目标进程的信箱中之后,立即开始执行其他任务。

参考文章:

Smalltalk: Getting The Message

Message passing

 

面向对象编程中的「对称性」

The flexibility provided by Smalltalk’s high degree of symmetry and extreme late binding have proven to help programmer productivity and creativity more than any theoretical benefits that might be derived from the use of static type checking, symmetry-breaking primitive data types or symmetry-breaking syntactic sugar.
(译文:Smalltalk 高度的对称性和极致的延迟(动态)绑定特性所带来的灵活性,帮助提升程序开发人员的工作效率和创造力。这种收益已被证明高于任何静态类型检查,对称性破缺的基础数据类型或者对称性破缺的语法糖所可能带来的理论收益。)

对称性的概念

对称性在几何和代数中有不同的定义。几何中,对称性是指对几何形体施加某种操作使它的位置能完全复原。代数中,对称性被描述为给定的组合定律下闭合,关联和可逆的一组变换。不论哪种功能定义我们都可以得出,对称性的核心即是变换条件下的不变性

分类(classification)与对称性(symmetry)

从认知科学的角度讲,我们人类的思考基于对事物进行分类的能力,分类最终建立起类(class)和实例(instance)的关联。一些该领域的人甚至认为分类支撑了人类的认知,并帮助构建了人类记忆存储的组织结构。在编程领域,面向对象编程语言通常支持两个层次的分类,即对象归类构建类之间的结构关系。基于此,有人认为所有面向对象的概念都可被统一于某种理论模型,并由分类学作解释。这也就提出从一种新的视角,即从生物学(biology)和分类学(taxonomy)的角度,来理解面向对象编程。

面向对象语言中,类是对象的分类。这种分类直接构建起了类的不变性——类的描述适用于该类的所有对象。从这个角度进一步推导,类便拥有了对称性:类赋予了对象多变性,但这种多变性需要遵循该类所定义的结构和行为。类的对称性带来的好处是,它为对象的多变性划分界限,且强制性地保证了类的正确性。

类的概念在基于组件的软件开发中非常有价值。组件可以按照如接口或者行为的兼容性等共有特征,分组为不同的类。于是类就能够用于创建具有共同特征,但各自不同的组件。当应用的需求发生变化时,只要新的组件遵循该组件类的共有特性,那么它就可以用于替换旧的组件。这种可替换性对基于组件的软件开发很有意义。另外,软件维护和演进过程中,替换过时或问题频出的组件已然令人头大的情况下,组件的可替换性也就同样重要。

更为重要的是,对称性和分类之间的联结,为面向对象软件设计提供了理论研究的基础。通过应用对称性原则,软件设计的目的就变成了最大化地识别和保留设计上的不变,同时能良好地支持变化。

接下来我们看另一种对称性。继承(Inheritance),大多时候会和一般化(generalization)与特殊化(specialization)概念挂钩,较少有研究者将之与分类(classification)相关联。面向对象编程中,分类上下文里,继承的角色不如类那样清晰。这是因为继承机制本身的灵活性。继承可以用以扩展类,限制类,或者修改类。这就意味着,子类和其超类可能并非包含关系,并且超类的描述也可能不适用于所有其子类。因此继承并不总能将类做出分类。但是,当继承用于子类型(subtyping)时,它就可以被看作是类的分类,也就保持了子类和其超类行为的一致性,亦即行为的不变性。此处需要明确一下,子类型只是继承扮演的角色之一。例如基于原型编程中对象的继承。因此,只有在子类型的概念下,继承方才用于对类进行分类。子类型和对称性的内联表现为:所有通过子类型方式构建的类,彼此可能大不相同,但一定保持并符合某种相同行为,或者说,它们是相同类型。

当然,我们可以进一步在面向对象编程中找到其他对称性的案例。但是以上两个例子就足以说明对称性在编程中的重要性。接下来,我们换一个视角进一步来了解对称性。

对称性的威力

对应到大众熟知的「面向对象编程」语言,如 Java,C++ 和 Python,「类和继承」的确被放在了核心位置。相应带来的对称性,当然也就体现在这些编程语言中。

作为对比,观察 Smalltalk 这一面向对象编程语言会发现,类,本质上是对象。该对象本身也是另外某个类(这种类被称为类的元类,metaclass)的实例。类是一个元类的唯一实例。所有的元类都是类 Metaclass 的实例。Metaclass 类是「Metaclass class」的实例,而后者又是 Metaclass 的实例。如此递归。Smalltalk 中类的编程只是一些操作数据的程序(program),这些程序本身又是数据(data)——可被其他程序操作。这不同于 Lisp 哲学(Lisp 因使用符号表达式,而让程序即为数据),但殊途同归。

甚至可以更进一步地说,Smalltalk 的对象/类系统的真正威力,不是它的继承特性,而是它的反射(reflection)机制。Smalltalk 运行在它被编写创造出来的上下文中(runs in same context it’s written in)。具体来说,Smalltalk 的运行时系统的元对象(metaobject)可以被具象化为普通的对象,被用以查询甚至查看内部细节。在 Smalltalk 中,元对象可以是类、元类、方法字典、编译过的方法、运行时栈,等等。

 

reflection

 

我们看到,Smalltalk 中体现出了上文所没有涉及到的另一个层次的对称——程序和数据的对称,数据即程序,程序即数据。这种对称在诸如 Java、C++ 和 Python 等面向对象语言中并不存在。甚至,Smalltalk 中体现出的这种独有的对称性,让其「类和继承」特性带来的对称性黯然失色,以至于类的继承仅仅是代码重用的方式。这种数据即程序的对称性,意味着,所有的信息都封装在即时运行的活(living)对象中。它使得 Smalltalk 调试器在程序执行过程中能够暂停,剖析,修改和恢复。这也是为什么 Smalltalk IDE 不仅仅是使用 Smalltalk 编写的,它也是 Smalltalk 语言本身。

后记

在查阅「面向对象」概念相关的文章时,数次出现了「对称(symmetry)」 这个词。让我疑惑的是,编程语言和对称有什么关系?进一步地调查发现,对称性的概念远远超越了设计范围,广泛存在于多种理论中。归根结底,对称性表现出来的哲学意义极具普遍性和指导性。当「变换条件下的不变性」这一个理念,和软件设计结合时,显得恰如其分。我们行业的前辈们,已然做了很多尝试,从编程语言的设计和软件开发的过程两个层面,最终想让软件开发更加轻松地应对变化。当然,这种努力今天仍旧在持续。

最后,希望本篇文章能够对大家有所启发,就像对我有启发。

 

参考文章:

Lisp, Smalltalk, and the Power of Symmetry

Understand symmetry in object-oriented languages