组合性是组件设计的一个方面,它旨在让人们能够自由地选择和组合通用组件,以几乎任意的配置来支持各种各样的应用,甚至包括组件设计者未曾预料到的应用。例如,电气组件通常被设计成开关、接线盒和负载可以几乎以任何顺序配置,以满足各种各样的应用。组件设计者不需要知道应用的具体细节,而组件用户也不会受到设计者任意选择的过度约束。同样,在机械工程中,许多应用可以完全由通用支架、铰链、紧固件等构建而成,这些组件在设计之初就考虑到可以以尺寸、螺距、材料强度等标准化所允许的任何顺序和布局进行配置。
在本文中,我们使用 LINQ(语言集成查询)作为组合性的指导性示例。LINQ 是专门为可组合性而设计的高阶运算符规范。该规范广泛适用于任何符合“集合”宽松定义的对象,从内存中的对象到异步数据流,再到云中分布的资源。通过这样的设计,开发人员可以通过以各种顺序链接转换和过滤器,以及通过嵌套链(即,通过构建运算符的表达式树)来构建复杂性。
在分布式系统的层级之间编码和传输这种运算符树具有许多具体的好处,最显著的是
• 通过将过滤器注入到更靠近数据和流的生产者处来节省带宽,避免将不需要的数据传输回消费者。
• 通过在云端执行计算来提高计算效率,因为云端可用的计算能力远大于客户端。
• 通过向数据消费者提供通用的转换和过滤服务来提高可编程性,避免数据生产者站点需要预先知晓地预先设置查询和数据模型。
本文还介绍了如何通过 REST(具象状态传输)将程序中的组合性提升到云端,程序中的表达式与 URI(统一资源标识符)中的资源规范之间的映射;并且它还探讨了为组合性设计带来的细微风险:看似不重要、任意的选择可能会使设计从根本上变得不可组合。
为组合性而设计不仅仅是单纯地分离接口和实现。它还意味着接口的某种统一性:一种元设计原则。如果每个电源插座和插头的设计都是定制的且具有独特的形状,即使该设计足以承载所需的电流,也不会有什么好处。正是因为插座和插头的形状是标准化的,我们才获得了几乎任意配置组合它们的灵活性。
物理工程学科(例如,电气和机械)在为组合性设计方面有着悠久的传统,因为其好处非常明显且压倒一切,但这些好处在软件工程中也变得越来越清晰。软件设计者长期以来一直接受黑盒化:需要将实现细节封装在接口内部,这些接口暴露最少、精确、完整的契约。设计者现在开始抽象化接口本身,并意识到组合性的组合优势。
纯函数式编程学科,以编程语言 Haskell (http://www.haskell.org) 及其前身 Miranda (http://en.wikipedia.org/wiki/Miranda_(programming_language)) 为例,将数学函数的绝对组合性保证带入了编程世界。它们的影响,加上命令式和面向对象编程的传统,代表了近期、深刻且重要的巩固:一个大的概念,函数,将几个较小的概念作为案例纳入其中。关系、对象、状态和流都以函数式风格自然地表示。这种风格越来越受欢迎,以下证据可以证明
• 将高阶函数 (http://en.wikipedia.org/wiki/First-class_function; http://en.wikipedia.org/wiki/Higher-order_function) 用于转换、过滤和聚合数据,纳入日常的命令式编程语言,最值得注意的是 C# 和 JavaScript。
• 普遍认识到不变性是一种优势,尤其是在并发和分布式系统中;请参阅 Eric Lippert 的评论 (http://blogs.msdn.com/b/ericlippert/archive/2007/11/13/immutability-in-c-part-one-kinds-of-immutability.aspx) 以及 Python 用户论坛中的相关主题 (http://groups.google.com/group/comp.lang.python/browse_thread/thread/29c62cbee7a6b598/df5b676f6f695eb9)。
• LINQ (http://en.wikipedia.org/wiki/Language_Integrated_Query) 和 underscore.js (https://github.com/documentcloud/underscore) 等库的普及。
• Scala、F# 和 Clojure 等完整的语言。
• coffee-script (https://github.com/jashkenas/coffee-script) 等语言覆盖层。
LINQ 是一个案例研究,它通过指定一组可组合的高阶函数(SQO,标准查询运算符;http://en.wikipedia.org/wiki/Language_Integrated_Query#Standard_Query_Operators)将函数的组合性更进一步。这种特定设计概括了集合的宽松抽象,并涵盖了广泛的领域
• 内存中的数据结构(列表、树、图、队列...)。
• 数据库中的表(甚至带有主键和外键约束)。
• 异步数据流(RX;http://msdn.microsoft.com/en-us/data/gg577609)。
• URI 中的斜杠分隔术语;因此,云中的资源。
• 信号处理原语(例如,卷积和傅里叶变换)。
• CodedDOM(代码文档对象模型);表达式树;AST(抽象语法树)—即,关于编程语言本身。
• HTML、XML 和 JSON(JavaScript 对象表示法)文档。
• 延续、异常、备选项等等。
这种设计为所有这些领域带来了相同的彻底的可组合运算符集合。你可以说 LINQ 将组合性本身带入了这些领域。如果你实现了 SQO,那么你就可以保证组合性。LINQ 不是第一个,当然也不是唯一的方法,但它足够具有示范性,可以支持本文中的其他观察结果,即
• 将程序中的组合性提升到云中的组合性。
• 说明潜在的可组合设计面临的风险。
那么,LINQ 的 SQO 充当了我们组合性本身的元设计原则的典范。正如通常在程序中实现的那样,SQO 以各种方式将函数应用于集合,将函数视为程序中可组合组件之间自然的交互约定。
从程序内的组合性跃升到云中的组合性,你必须在云中可组合组件之间自然的交互约定(无论它是什么)之上“实现” SQO。这只是 LINQ 的另一个领域,它被视为对任何满足 LINQ 集合宽松抽象的事物进行可组合操作的规范。云只是由 URI 指定的资源的松散集合。
“云中可组合组件之间自然的交互约定”是什么?今天最重要的此类交互约定也许是 REST (http://en.wikipedia.org/wiki/REST),其中客户端和服务器通过 HTTP 交互,通过表示资源的不透明 URI。REST 没有指定 URI 的语义,只指定了非常轻量级的斜杠分隔术语后缀语法。诸如 OData (http://www.odata.org/) 之类的协议使用 URI 编码和 REST 向云提供数据框架,特别是通过授权客户端将所需计算或查询的结果指定为资源。为此,让我们添加以下想法
• 彻底的组合性。用户通过以任意顺序链接 SQO 表达式序列来构建复杂性,而不是像 OData 中那样通过预设数据模型的丰富语法来构建。
• 双向映射。这是程序中的表达式链和 URI 中的资源规范之间的映射。给定这样的映射,你可以像对待同一个事物一样推理程序中的表达式和云交互中的资源。
• 可注入性。表达式链的接收者可以维护跨多个通信的常驻操作,以节省带宽。例如,客户端请求“我附近的中国餐馆”的流,可以一次性向服务器注入过滤器,这样服务器就可以避免在未来的推送通知序列中向客户端发送其他不相关的商业记录。服务器被来自客户端过于频繁的位置更新淹没,可以在客户端中注入一个过滤器,指示“仅每十次更新一次”,客户端在执行物理通信之前应用该过滤器。
• 广泛的适用性。相同的可组合设计适用于静态数据资源和时间相关的异步数据流(以及其他领域)。
在这一点上,假设程序中的可组合运算符链表达式与云中的可组合资源规范之间存在自然的对应关系。以下部分介绍了一种使这种对应关系机械化的具体方法,但这种对应关系本身允许你以相同的方式推理在程序中有效的方法和在云中有效的方法。
LINQ 的典型实现嵌入在支持高阶函数的编程语言中。然而,采用 LINQ 仅意味着接受 SQO 的规范。LINQ 作为一种设计,根本不需要普通的编程语言。通过注意到 (1) 运算符的嵌套树可以转换为纯后缀运算符链;以及 (2) 编程语言中用点分隔的运算符链在形式上与 URI 中用斜杠分隔的术语链同构,你可以将任何 LINQ 链嵌入 URI 语法中,并使用 HTTP 作为 RESTful Web 服务中的“表达式嵌入语言”。
例如,想象一下以下伪 C# 表达式,它表示最近购买过的客户的电话号码
Customers
.Where(customer =>
(DateTime.Now - customer.Orders.Last().dateTime)
< TimeSpan.FromDays(365))
.Select(customer => customer.PrimaryContactPhone)
;
这表示,“保留客户Where (条件是)现在日期和时间与上次购买的日期和时间之差少于 365 天,然后Select (选择)来自每个客户结果集合的主要电话联系号码。”Where (条件是)和Select (选择)都是 LINQ SQO。每个都接受两个参数—每个点左侧的数据集合参数和括号内的高阶函数—并且每个都产生一个新的集合。这就是它们链式组合性的本质:每个 SQO 表达式都表示一个数据集合,可以从左到右顺序点缀到链中的下一个 SQO 中。
的更高阶函数参数Where (条件是)SQO 是一个谓词,写成 lambda 表达式
customer => ...取决于客户的函数体表达式...
将其解读为“客户的函数,它执行由函数体表达式指定的计算,并产生表达式的结果值。”由于这个特定的 lambda 表达式表示一个谓词,它应该产生一个布尔值。在 JavaScript 中,你会写出完全相同的东西,如下所示
function(customer) {return ...函数体表达式...;}
的更高阶函数参数Select (选择)SQO 是另一个 lambda 表达式,它只是从客户记录中挑选出电话号码字段,但它可以进行任意计算。
大多数语言或库都称之为Select (选择)运算符map (映射),但 LINQ 的设计者选择了名称Select (选择)以吸引 SQL 开发人员。在一些理论讨论中,该运算符也称为Project (投影)。让我们暂时坚持使用Select (选择)。
由于表达式链不包含嵌套运算符,如果我们认为 lambda 表达式是原子的,那么它已经是浅后缀形式。这种浅后缀形式是
Customers.Where(...lambdaW...).Select(...lambdaS...)
只需在前面加上协议和域名,并将点替换为斜杠
https://myQueries.com/Customers/Where(...lambdaW...)/Select(...lambdaS...)
然后对 lambda 进行 URL 编码,最终得到类似这样的结果
https://myQueries.com/Customers/Where(customer%3D%3E(DateTime.Now-customer.Orders.Last().dateTime)%3CTimeSpan.FromDays(365))/Select(customer%3D%3Ecustomer.PrimaryContactPhone)
因此,你在 URI 中拥有了整个表达式的表示形式。RESTful 服务器可以在安全沙箱中解释这样的表达式,并提供非常通用的查询服务,而无需内置的、预先设置的查询。
如果你不能或不想将 lambda 视为原子的,那么你可以完全采用深后缀形式,将整个 AST 以后缀形式编写并将其编码到 URI 中。
你可以分两个阶段完成此操作:首先保持 lambda 内爆,这样你就可以看到深前缀和浅前缀之间的区别;然后展开 lambda。首先以前缀形式重写查询,将查询运算符点左侧的所有内容拖到右侧,放在第一个位置的运算符的括号内。这将表达式像毛衣的袖子一样由内而外翻转,如下所示
Select(Where(Customers, ...lambdaW...), ...lambdaS...)
现在,很容易看出每个级别都是一个二元运算符,第一个参数槽中有一个数据集合,第二个参数槽中有一个 lambda。这对应于图 1 中的 AST。在不展开 lambda 的情况下,从那里进行从左到右、深度优先的遍历会产生深后缀形式,lambda 仍然是内爆的
https://myQueries.com/Customers/2.lambdaW/Where/4.lambdaS/Select
它看起来类似于浅后缀形式,只是 SQO 是后 lambda,就像是这样。SQO 出现在 lambda 之后,而不是将 lambda 托管在它们的括号内。在深后缀形式中,永远没有括号,这就是重点。这应该让你想起 PostScript 或 Forth 或 RPN(逆波兰表示法)计算器,因为它们都是深后缀的 (http://en.wikipedia.org/wiki/Concatenative_programming_language)。
现在,将 lambda 展开到图 2 所示的 AST 中。在没有括号的情况下,其在 URI 中的 RESTful 编码非常简单
https://myQueries.com/Customers/DateTime.Now/customer/.Orders/Last/.dateTime/-/365/Const/TimeSpan.FromDays/Lt/lambda.customer/Where/customer/.PrimaryContactPhone/lambda.customer/Select
其余的点表示属性访问器调用、系统调用或 lambda 变量声明,而不是 SQO 调用。URI 编码用斜杠替换了所有 SQO 调用之前的点。
请注意,还有其他用于在后缀中编码 lambda 的选项。此示例使用一种表示形式,其中变量在声明之前出现。这需要一个执行模型,该模型将变量和依赖操作符号化地保存在堆栈上,以便在声明变量的 lambda 术语到达时稍后解析。其他胜任的选择也很多。例如,PostScript 和 Factor 在数组中编码 lambda 表达式,其中变量声明在函数体之前。这相当于嵌入在其他后缀语言中的作弊前缀表示法。
我们已经离开了人类可读语法的领域(除了 Forth 爱好者),但我们已经找到了一种 URI 编码 AST 的方法,这种方法对于机器来说读取和写入都很简单。即使对于嵌套的 LINQ,我们也可能不需要走这么远。括号计数可以像保留人类可读性一样轻松地管理嵌套。
对于一个带有嵌套 SQO 的示例,想象一下以下表达式,同样用伪 C# 编写,它表示来自客户列表的高价值订单的行项目
Customers
.Where(customer => customer.Orders
.SelectMany(order => order.LineItems)
.Sum() > 1000)
.SelectMany(customer => customer.Orders)
.SelectMany(order => order.LineItems)
;
通过将 lambda 变量替换为customer (客户)替换为更短的c并将 lambda 变量order (订单)替换为更短的替换为o
来节省一些笔墨。你可以毫不犹豫地写出 URI 形式
https://myQueries.com/Customers/Where(c%3D%3Ec.Orders/SelectMany(o%3D%3Eo.LineItems)/Sum()%3E1000)/SelectMany(c%3D%3Ec.Orders)/SelectMany(o%3D%3Eo.LineItems)
为组合性设计中的风险
虽然 LINQ 是一个很好的可组合设计示例,它在内存中的对象和云中的资源上同样有效,但它肯定不是唯一的。然而,拥抱彻底组合性的设计者将面临一些风险。如果他们在设计中稍有偏差,那么用户将无法在设计中指定他们需要的内容。
Customers
在一个典型的示例中,假设你需要一个来自大额消费客户的所有订单的集合。你的库提供了一种过滤掉低消费客户的方法,并且它提供了一种可组合的方法来获取每个客户的订单。到目前为止,一切都很好。在伪 C# 中,你可以尝试
.Where(customer => customer.TotalSpending() > 1000)
;
.Select(customer => customer.Orders)
但这并没有产生所需的订单集合;相反,它产生了一个订单集合的集合—每个客户一个内部订单集合。你需要展平顶层集合。你必须离开库并编写自定义代码。
在云设置中,离开库意味着为每个未涵盖的案例扩散自定义代码,限制了仅从可组合构建块构建新颖表达式的能力。在任何你有类似上面表达式的地方,你都必须执行带外操作来删除不需要的额外结构。在程序设置中,离开库意味着冒着在系统中的各个位置插入脆弱的变通代码的风险。也许程序员知道Orders (订单)在程序设置中,离开库意味着冒着在系统中的各个位置插入脆弱的变通代码的风险。也许程序员知道是数组,因此编写块复制操作来展平它们。稍后,当
将实现从数组更改为 gzipped XML 时,此代码会意外失败。但是,如果库最初提供了所需的SelectMany (选择多个)
Customers
在一个典型的示例中,假设你需要一个来自大额消费客户的所有订单的集合。你的库提供了一种过滤掉低消费客户的方法,并且它提供了一种可组合的方法来获取每个客户的订单。到目前为止,一切都很好。在伪 C# 中,你可以尝试
,那么程序员将编写以下代码,该代码与之前的代码只有一处不同(带下划线)
;
组合性本身的广度和深度
令人惊奇的是,诸如 LINQ 的 SQO 之类的单个运算符规范同样适用于异步数据流和内存中的对象—但事实确实如此。用户不仅可以指定对拉取数据资源的任意转换,还可以使用同一组 SQO 指定对推送异步数据流的任意转换。在这两种情况下,表达式组件都可以透明地注入到数据生产者机器(无论是客户端还是服务器)的上游,在源头转换和过滤数据,以节省带宽并减少“聊天性”。
然而,在一个自指的玩笑中,在程序中的函数上工作的同一组 SQO 也在云中分布的资源上工作。因此,相同的 SQO 设计有八重应用
• 在程序内或云端数据上运行的 SQO。
• 在空间中分布的数据或在时间中分布的数据。
• 在数据生产者站点与数据消费者站点执行的转换和过滤器,尊重带宽、延迟和安全性等方面的考虑。??LINQ 再次从 Haskell,特别是从其名为 Prelude 的初始化库中借用了其基本概念。该技术的核心是事物的集合的宽松抽象—例如(不要打哈欠),客户、订单、项目。每个客户都有许多订单,每个订单都有许多项目。从模式的角度来看,这些客户是在内存中,还是
在某个时间点传递给回调,还是通过延续线程化,还是在可通过 Web 服务调用访问的脱机文档存储中,都无关紧要。重要的是,在你的系统中某个地方存在一个表示它们的抽象,你想要操作它们。所需的可组合运算符分为以下几类(来自 LINQ 和 Haskell Prelude 的示例)• INSERT (插入)元素到集合中(例如, / new List(...)return (返回)
)。这就是你进入集合的方式。例如,将客户记录转换为单条记录的表;创建一个单例列表(包含单个客户对象)。• TRANSFORM (转换)元素并生成一个新集合(例如, / .Select (选择)map (映射)
)。例如:从客户列表中生成客户的主要电话号码列表,每个客户一个电话号码。• FILTER (过滤)基于谓词从集合中过滤出元素(例如, / .Where (条件)filter (过滤器)
)。例如,生成大订单客户的列表;一般来说,这些客户的数量将少于原始集合中的数量。• EXPAND (展开)将来自一个集合的元素展开为新的子集合,并组合或连接新集合(例如, / .SelectMany (选择多个), concatMap (连接映射)bind, >>= (绑定,>>=)
)。例如,获取客户的所有一度朋友;获取所有客户的所有订单;获取所有订单的所有行项目。• AGGREGATE (聚合)元素并产生一个依赖于所有元素的结果(例如, / .Aggregate (聚合) fold (折叠);以及和.Take (获取) / .Skip (跳过), take (获取)drop (丢弃)
也属于此类)。这就是你如何离开集合(从技术上讲,这是一个共单子运算符,EXTRACT)。例如,获取所有客户的平均消费。
如何毁掉一个库
你不必完全编写 LINQ SQO;如果你理解基本原理,就会有很大的自由度。然而,一个很大的失败方式是忽略 EXPAND 类别,设计者经常这样做,因为它不符合某些方面熟悉的 map/filter/fold 口头禅。EXPAND 类别是必不可少的;事实上,它是最重要的一个。没有它,库就无法表示最通用的集合类型,因此无法扩展到新的设置,例如异步数据流或云中的资源。有了它(以及 INSERT),所有其他类别都可以精确地模拟(有关更多信息,请参阅 http://channel9.msdn.com/Shows/Going+Deep/Bart-De-Smet-MinLINQ-The-Essence-of-LINQ )。
图 3 中的图表演示了运算符的类别。这些图表共同展示了为什么 EXPAND 类别最重要。它是 FILTER 的必要双胞胎,即使它更通用。map (映射)毁掉库的另一种方法是弄错参数的顺序。为了链接运算符,更不用说将它们嵌入到 URI 和 REST 中,你总是希望将集合参数放在第一位。传统上,Lisp 的方言将函数参数放在首位,至少对于map (映射),因为它使表达式读起来像是“将此函数映射到该集合上”。具有 Lisp 背景的库设计者可能会只是条件反射式地这样编写map (映射),又名Select (选择),破坏了模式,并且除了在开头之外,不能在点链中组合。例如,假设你想要从一系列供应商处获取特定数码相机的排序价格列表
CameraVendors (相机供应商)
.Where(vendor => vendor.Offers.Contains(mySelectedCamera))
.Select(vendor => vendor.Offers
.FirstWhere(offer => offer.Item == mySelectedCamera))
.OrderBy(offer => offer.Price)
.ForEach(offer => offer.Print())
;
假设你修改表达式以在考虑运费后重新考虑价格。只需在链的中间组合插入另一个Select (选择)(以下划线显示),保持其他所有内容不变
CameraVendors (相机供应商)
.Where(vendor => vendor.Offers.Contains(mySelectedCamera))
.Select(vendor => vendor.Offers
.FirstWhere(offer => offer.Item == mySelectedCamera))
.Select(offer =>
offer.Price + offer.Shipping(myZipCode, myShippingOptions))
.OrderBy(offer => offer.Price)
.ForEach(offer => offer.Print())
;
现在,假设Select (选择)被传统地设计,因此它将其集合参数放在第二个位置,而不是放在点的左侧,这实际上是第一个位置。你将从类似这样的内容开始
SelectUgly(vendor => vendor.Offers
.FirstWhere(offer => offer.Item == mySelectedCamera),
CameraVendors)
.OrderBy(offer => offer.Price)
.ForEach(offer => offer.Print())
;
添加考虑运费的转换需要沿以下方向进行主要的语法手术,添加带下划线的文本并删除删除线文本
SelectUgly(offer =>
offer.Price + offer.Shipping(myZipCode, myShippingOptions),
SelectUgly(vendor => vendor.Offers
.FirstWhere(offer => offer.Item == mySelectedCamera),
CameraVendors)
.OrderBy(offer => offer.Price)
.ForEach(offer => offer.Print())
)
.OrderBy(offer => offer.Price)
.ForEach(offer => offer.Print())
;
这完全破坏了组合结构。你必须展开(取消嵌套和重新嵌套)表达式,而不是仅仅在适当的位置插入一行。参数的顺序可能看起来是一个小问题,但如果你弄错了,它会完全破坏所需的可组合性。
LINQ 的模式是万无一失且普遍适用的,适用于惊人广泛的软件领域,例如异步流、有状态计算、I/O、异常、备选项—任何符合“事物集合”宽松抽象的事物。该模式始终在表达式树中可组合,其中依赖的运算符以嵌套序列相互跟随。它可以同样好地编码在普通编程语言语法中,也可以编码在纯后缀表示法(例如 URI)中。
由于云符合“事物集合”的宽松定义,LINQ 的可组合转换模式涵盖了云中的分布式资源,就像它涵盖了程序中本地可寻址的资源一样。打包子表达式并将它们注入到更靠近数据生产站点的位置,可以让你在 RESTful Web 服务中获得带宽、聊天性和安全性优势。
喜欢它,讨厌它?请告诉我们
Brian Beckman 目前在 Bing 的地图和信号部门工作,自 1992 年以来曾在微软担任过多个职位,从 Crypto (SET) 到 Biztalk,再到函数式编程研究。他在 1984-1989 年在 Caltech Hypercube 上编写了第一个版本的 Time Warp 操作系统。他拥有普林斯顿大学天体物理学博士学位(1982 年),并已提交了 80 多项专利,其中 27 项已获得授权。
© 2012 1542-7730/12/0200 $10.00
最初发表于 Queue vol. 10, no. 2—
在 数字图书馆 中评论本文
Matt Godbolt - C++ 编译器中的优化
在向编译器提供更多信息方面需要权衡:这可能会使编译速度变慢。诸如链接时优化之类的技术可以让你两全其美。编译器中的优化在不断改进,即将到来的间接调用和虚拟函数分派的改进可能很快就会带来更快的多态性。
Ulan Degenbaev, Michael Lippautz, Hannes Payer - 作为合资企业的垃圾回收
跨组件跟踪是解决跨组件边界的引用循环问题的一种方法。只要组件可以形成任意对象图,并且跨 API 边界具有重要的所有权,就会出现此问题。CCT 的增量版本在 V8 和 Blink 中实现,从而能够以安全的方式有效且高效地回收内存。
David Chisnall - C 语言不是一种低级语言
在最近的 Meltdown 和 Spectre 漏洞之后,值得花一些时间来研究根本原因。这两个漏洞都涉及处理器推测性地执行超出某种访问检查的指令,并允许攻击者通过侧信道观察结果。导致这些漏洞以及其他几个漏洞的功能被添加,是为了让 C 程序员继续相信他们正在使用低级语言进行编程,而这种情况在几十年前就已经不是这样了。
Tobias Lauinger, Abdelberi Chaabane, Christo Wilson - 你不应该依赖我
大多数网站都使用 JavaScript 库,其中许多库已知是易受攻击的。了解问题的范围以及包含库的许多意外方式,只是改善情况的第一步。此处的目的是,本文中包含的信息将有助于为社区提供更好的工具、开发实践和教育工作。