Haskell/图约简

Haskell 性能

介绍
逐步示例
图约简
惰性
时间和空间分析
严格性
算法复杂度
数据结构
 并行

笔记和待办事项

待办事项：将惰性中的惰性求值解释融入这个模型。
待办事项：更好的章节名称。
待办事项：思考图形的图形表示。
- 没有图形表示，用 let .. in 来做。优点：约简以这种方式最容易执行。缺点：没有图形。
- 类似于 Bird&Wadler 中的 ASCII 艺术 / 线形艺术？优点：仅显示相关部分，真正地作为图形，易于在纸上执行。缺点：难看，不能用它来表示大型图形。
- 带有 @-节点的完整图形？优点：看起来像图形。缺点：没有人需要知道 @-节点来理解图约简。可以在实现部分解释。
- 没有 @-节点的图形。优点：易于理解。缺点：函数式编程中的柯里化怎么办？
！保持本章简短。读者越快知道如何手动评估 Haskell 程序，越好。
前面的章节紧随 Bird&Wadler

介绍

编程不仅是关于编写正确的程序，由语义学回答，也是关于编写快速且占用少量内存的程序。为此，我们需要了解它们在机器上的执行方式，通常由操作语义给出。本章解释了 Haskell 程序如何在真实的计算机上执行，因此为分析 Haskell 程序的时间和空间使用提供基础。请注意，Haskell 标准故意不给出操作语义，实现可以自由选择自己的语义。但到目前为止，每个 Haskell 实现或多或少地遵循惰性求值的执行模型。

在下文中，我们将详细介绍惰性求值，并随后使用此执行模型来解释和举例说明关于 Haskell 程序的时间和内存复杂度的推理。

通过惰性求值评估表达式

约简

执行函数式程序，即评估表达式，意味着重复应用函数定义，直到所有函数应用都被展开。以表达式 pythagoras 3 4 和定义为例

      square x = x * x
pythagoras x y = square x + square y

一组可能的约简序列是

pythagoras 3 4
 ⇒ square 3 + square 4   (pythagoras)
 ⇒    (3*3) + square 4   (square)
 ⇒        9 + square 4   (*)
 ⇒        9 + (4*4)      (square)
 ⇒        9 + 16         (*)
 ⇒          25

每个约简都用一个等效的表达式替换一个子表达式，称为可约简表达式或简称redex，无论是通过调用函数定义（如 square）还是使用内置函数（如 (+)）。没有 redex 的表达式被称为正规形式。当然，一旦达到正规形式，执行就会停止，因此正规形式是计算的结果。

显然，执行的约简越少，程序运行速度越快。我们不能期望每个约简步骤都花费相同的时间，因为其在真实硬件上的实现看起来非常不同，但在渐进复杂度方面，这个约简数是一个准确的度量。

约简策略

有很多可能的约简序列，约简的次数可能取决于约简执行的顺序。以表达式 fst (square 3, square 4) 为例。一种系统性的可能性是在应用函数定义之前评估所有函数参数

fst (square 3, square 4)
 ⇒ fst (3*3, square 4)   (square)
 ⇒ fst ( 9 , square 4)   (*)
 ⇒ fst ( 9 , 4*4)        (square)
 ⇒ fst ( 9 , 16 )        (*)
 ⇒ 9                     (fst)

这被称为最内约简策略，最内 redex 是一个没有其他 redex 作为其内部子表达式的 redex。

另一种系统性的可能性是首先应用所有函数定义，然后才评估参数

fst (square 3, square 4)
 ⇒  square 3             (fst)
 ⇒  3*3                  (square)
 ⇒  9                    (*)

它被称为最外约简，总是约简最外 redex，这些 redex 不在其他 redex 内部。这里，最外约简使用的约简步骤比最内约简少。为什么？因为函数 fst 不需要对的第二个分量，而约简 square 4 是多余的。

终止

对于一些表达式，如

loop = 1 + loop

可能没有约简序列终止，程序执行进入无限循环，这些表达式没有正规形式。但也有一些表达式，其中一些约简序列终止，而另一些没有终止，例如

fst (42, loop)
 ⇒  42                   (fst)

fst (42, loop)
 ⇒  fst (42,1+loop)      (loop)
 ⇒  fst (42,1+(1+loop))  (loop)
 ⇒  ...

第一个归约序列是最外层归约，第二个是最内层归约，它试图徒劳地评估loop，即使它会被fst忽略。只有在需要时才评估函数参数的能力是使最外层归约在终止方面成为最佳选择的原因。

定理（Church Rosser II）: 如果存在一个终止归约，那么最外层归约也会终止。

图归约（归约+共享）

尽管能够丢弃参数，但最外层归约并不总是比最内层归约需要更少的归约步骤。

square (1+2)
 ⇒  (1+2)*(1+2)          (square)
 ⇒  (1+2)*3              (+)
 ⇒      3*3              (+)
 ⇒       9               (*)

这里，参数(1+2)被复制，并随后被归约两次。但由于它是一个相同的参数，因此解决方案是将归约(1+2) ⇒ 3与该参数的所有其他化身共享。这可以通过将表达式表示为图来实现。例如，

 __________
|   |     ↓
◊ * ◊     (1+2)

表示表达式(1+2)*(1+2)。现在，square (1+2)的最外层图归约按如下方式进行

square (1+2)
 ⇒  __________           (square)
    |   |     ↓
    ◊ * ◊     (1+2)
 ⇒  __________           (+)
    |   |     ↓
    ◊ * ◊      3

 ⇒ 9                     (*)

并且工作已经共享。换句话说，最外层图归约现在最多只归约每个参数一次。出于这个原因，它总是比最内层归约需要更少的归约步骤，我们将在讨论时间时证明这一点。

表达式共享也通过let和where结构引入。例如，考虑海伦公式，它用于计算边长为a、b和c的三角形的面积

area a b c = let s = (a+b+c)/2 in
     sqrt (s*(s-a)*(s-b)*(s-c))

将其实例化为等边三角形将归约为

area 1 1 1
 ⇒        _____________________             (area)
          |  |    |     |      ↓
    sqrt (◊*(◊-a)*(◊-b)*(◊-c))  ((1+1+1)/2)
 ⇒        _____________________             (+),(+),(/)
          |  |    |     |      ↓
    sqrt (◊*(◊-a)*(◊-b)*(◊-c))  1.5
 ⇒
    ...
 ⇒
    0.433012702

即 ${\sqrt {3}}/4$ 。换句话说，let绑定只是为图中的节点赋予名称。事实上，可以完全放弃图形符号，只依赖let来标记共享并表达图结构。^[1]

任何 Haskell 的实现都以某种形式基于最外层图归约，因此它为推理时间和内存分配的渐近复杂性提供了良好的模型。达到范式所需的归约步骤数对应于执行时间，图中项的大小对应于使用的内存。

练习

使用最内层和最外层图归约将square (square 3)归约为范式。
考虑快速幂算法
```
power x 0 = 1
power x n = x' * x' * (if n `mod` 2 == 0 then 1 else x)
  where x' = power x (n `div` 2)
```
它将x计算到n次幂。使用最内层和最外层图归约将power 2 5归约。执行了多少次归约？一般power 2 n的渐近时间复杂度是多少？如果我们使用“无图”的最外层归约，算法会发生什么？

模式匹配

到目前为止，我们对最外层图归约的描述在模式匹配和数据构造函数方面仍然存在不足。解释这些要点将使读者能够追踪大多数归约策略的情况，而这种策略通常是实现非严格函数式语言（如 Haskell）的基础。它被称为按需调用或惰性求值，这是为了暗示它“惰性地”将函数参数的归约推迟到最后一刻。当然，其余细节将在后续章节中介绍。

为了了解模式匹配如何需要规范，例如考虑布尔析取

 or True  y = True
 or False y = y

以及表达式

 or (1==1) loop

其中loop = not loop是非终止的。以下归约序列

or (1==1) loop
 ⇒ or (1==1) (not loop)        (loop)
 ⇒ or (1==1) (not (not loop))  (loop)
 ⇒ ...

只归约最外层可归约项，因此是最外层归约。但

or (1==1) loop
 ⇒ or True   loop              (or)
 ⇒ True

更有意义。当然，我们只希望应用or的定义，并且只归约参数来决定选择哪个方程。以下 Haskell 模式匹配规则捕捉了这种意图

左手边自上而下匹配
当匹配左手边时，参数自左至右匹配
只评估参数以决定它们是否匹配。

因此，对于我们的示例or (1==1) loop，我们必须将第一个参数归约为True或False，然后评估第二个参数以匹配变量y模式，然后展开匹配的函数定义。由于与变量的匹配总是成功的，因此第二个参数根本不会被归约。这是上面第二个归约部分再现了这种行为。

有了这些准备，读者现在应该能够评估大多数 Haskell 表达式。以下是一些随机遇到的测试这种能力的示例

练习

使用惰性求值将以下表达式归约为范式。假设来自 Prelude 的标准函数定义。

```
length [42,42+1,42-1]
```
```
head (map (2*) [1,2,3])
```

head $ [1,2,3] ++ (let loop = tail loop in loop)

```
zip [1..3] (iterate (+1) 0)
```

head $ concatMap (\x -> [x,x+1]) [1,2,3]

take (42-6*7) $ map square [2718..3146]

高阶函数

剩下需要澄清的一点是高阶函数和柯里化的归约。例如，考虑以下定义

 id x = x
 a = id (+1) 41

 twice f = f . f
 b = twice (+1) (13*3)

其中id和twice都只用一个参数定义。解决方案是将多个参数视为对一个参数的后续应用，这被称为柯里化

 a = (id    (+1)) 41
 b = (twice (+1)) (13*3)

为了归约任意应用expression₁ expression₂，按需调用首先归约expression₁，直到它变成一个函数，其定义可以使用参数expression₂展开。因此，归约序列为

a
 ⇒ (id (+1)) 41          (a)
 ⇒ (+1) 41               (id)
 ⇒ 42                    (+)

b
 ⇒ (twice (+1)) (13*3)   (b)
 ⇒ ((+1).(+1) ) (13*3)   (twice)
 ⇒ (+1) ((+1) (13*3))    (.)
 ⇒ (+1) ((+1)  39)       (*)
 ⇒ (+1) 40               (+)
 ⇒ 41                    (+)

诚然，这个描述有点含糊，下一节将详细说明一种清晰地表达它的方法。

虽然模式匹配似乎是时间密集型计算的主力军，而高阶函数只用于捕捉算法的本质，但函数确实可以用作数据结构。一个例子是差分列表 ([a] -> [a])，它允许在 $O(1)$ 时间内进行串联，另一个例子是通过折叠表示流。事实上，所有数据结构都用纯 lambda 演算表示，而纯 lambda 演算是所有函数式编程语言的根源。

练习！还是不练习？差分列表最好使用foldl (++)完成，但这需要了解 fold 示例。哦，我们到底在哪里介绍 foldl VS. foldr 示例？嗯，Bird&Wadler 在“控制归约顺序和空间需求”的结尾偷偷地插入了一个额外的部分“再次遇到 fold”，用于 (++) 示例 :-/ 当论证reverse时，解释了 (++) 的复杂性。

弱头范式

为了精确地阐述惰性求值如何选择其归约序列，最好放弃等式函数定义，并用表达式导向的方法替换它。换句话说，我们的目标是将像f (x:xs) = ...这样的函数定义转换为f = expression的形式。这可以使用两个原语来完成，即 case 表达式和 lambda 提取。

在它们的原始形式中，case 表达式只允许对最外层构造函数进行区分。例如，列表的原始 case 表达式具有以下形式

case expression of
  []   -> ...
  x:xs -> ...

lambda 提取是一个参数的函数，因此以下两个定义是等效的

f x = expression
f   = \x -> expression

以下是将zip的定义

 zip :: [a] -> [a] -> [(a,a)]
 zip []      ys      = []
 zip xs      []      = []
 zip (x:xs') (y:ys') = (x,y):zip xs' ys'

转换为 case 表达式和 lambda 提取

 zip = \xs -> \ys ->
    case xs of
       []    -> []
       x:xs' ->
          case ys of
             []    -> []
             y:ys' -> (x,y):zip xs' ys'

假设所有定义都已转换为这些原语，那么现在每个可归约项都具有以下两种形式之一

函数应用 (\variable->expression₁) expression₂
或 case 表达式case expression of { ... }

惰性求值.

弱头范式: 如果表达式是以下之一，那么它处于弱头范式，

一个构造函数（可能应用于参数），例如True、Just (square 42)或(:) 1
一个应用于过少参数（可能没有参数）的内置函数，例如(+) 2或sqrt。
或一个 lambda 提取\x -> expression。

函数类型无论如何都无法进行模式匹配，但狡猾的 seq 仍然可以将它们评估为 WHNF。“弱”= 在 lambda 下不进行归约。“头”= 首先进行函数应用，然后进行参数应用。

严格和非严格函数

非严格函数不需要其参数。严格函数需要其参数处于 WHNF，只要我们不区分非终止的不同形式（例如，f x = loop 不需要其参数）。

控制空间

"空间"在这里可以更好地被可视化为图的遍历。既可以是数据结构，也可以是诱导的依赖关系图。例如：Fibonacci(N) 依赖于：如果 N = 0 或 N = 1 则无；否则依赖于 Fibonacci(N-1) 和 Fibonacci(N-2)。由于 Fibonacci(N-1) 依赖于 Fibonacci(N-2)，因此诱导的图不是树。因此，实现技术和数据结构遍历之间存在对应关系。

对应的实现技术	数据结构遍历
记忆化	深度优先搜索（将所有中间结果存储在内存中）
并行计算	广度优先搜索（也将所有中间结果存储在内存中）
共享	有向无环图遍历（仅在内存中维护“边界”）
常规递归	树遍历（填充堆栈）
尾递归	列表遍历 / 贪心搜索（常数空间）

经典的

fibo 0 = 1
fibo 1 = 1
fibo n = fibo (n-1) + fibo (n-2)

是将树遍历应用于有向无环图的糟糕情况。优化版本

fibo n = 
  let f a b m =
     if m = 0 then a
     if m = 1 then b
     f b (a+b) (m-1)
  in f 1 1 n

使用 DAG 遍历。幸运的是，边界大小是常数，因此它是一个尾递归算法。

注意：本章 Haskell/Strictness 旨在详细说明此处的內容。

注意：在这一节之前要介绍严格函数的概念。

现在是时候展示占空间的 fold 示例了

foldl (+) 0 [1..10]

介绍 seq 和 $!，它们可以强制表达式为 WHNF。 => foldl'。

棘手的空间泄漏示例

(\xs -> head xs + last xs) [1..n]

(\xs -> last xs + head xs) [1..n]

由于 Haskell 中的求值顺序仅由数据依赖关系决定，并且既没有 head xs 依赖于 last xs 也不反之，两者都可以先执行。这意味着，根据编译器，一个版本运行在 O(1) 空间，而另一个版本运行在 O(n) 空间（一个足够智能的编译器可能会将这两个版本都优化到 O(1) 空间，但 GHC 9.8.2 在我的机器上没有做到这一点——只有第二个版本运行在 O(1) 空间）。

共享和 CSE

注意：与时间段重叠。嗯，要多加一个记忆化部分吗？

如何共享

foo x y =
  where s = expensive x -- s is not shared
foo x = \y -> s + y
  where s = expensive x -- s is shared

"Lambda-lifting"，"完全惰性"。编译器不应该执行完全惰性。

空间和时间之间权衡的一个经典且重要的例子

sublists []      = [[]]
sublists (x:xs)  = sublists xs ++ map (x:) (sublists xs)
sublists' (x:xs) = let ys = sublists' xs in ys ++ map (x:) ys

这就是为什么编译器不应该将公共子表达式消除作为优化。 (GHC 做了吗？)。

尾递归

注意：这应该放在空间部分吗？我认为是的，它与堆栈空间有关。

Haskell 中的尾递归看起来不同。

关于时间推理

注意：在上限时间之前介绍严格性可以省去一些解释的麻烦？

惰性求值 < 积极求值

在推理执行时间时，手动执行图约简来了解发生了什么通常是不可行的。事实上，人类很难预测惰性求值采取的求值顺序，追踪积极求值的路径要容易得多，在将参数提供给函数之前，会先将它们约简为范式。但是，知道惰性求值总是执行比积极求值更少的约简步骤（展示证明！），我们可以很容易地通过假装我们的函数被积极求值来获得约简次数的上限。

例子

or = foldr (||) False
isPrime n = not $ or $ map (\k -> n `mod` k == 0) [2..n-1]

=> 积极求值总是需要 n 步，惰性求值不会超过这个数字。但是它实际上会更少。

丢弃参数

对于那些无论如何都会将其参数检查为范式的函数，时间界限是精确的。函数需要其参数的属性可以通过指称语义简洁地捕捉到

f ⊥ = ⊥

尽管如此，参数仅在 WHNF 中。运算上：非终止 -> 非终止。 (虽然这只是一个近似值，因为 f anything = ⊥ 不“需要”其参数)。非严格函数不需要其参数，并且积极时间界限不精确。但是，函数是否是严格的这一信息在分析中已经可以被很好地利用。

isPrime n = not $ or $ (n `mod` 2 == 0) : (n `mod` 3 == 0) : ...

知道 or True ⊥ = True 就足够了。

其他例子

foldr (:) [] vs. foldl (flip (:)) [] 以及 ⊥。
能否只用 ⊥ 分析 head . mergesort？无论如何，这个例子太复杂了，属于 Haskell/Laziness。

持久性与摊销

注意：最好将本节留给数据结构章节，因为上面的子节涵盖了大多数程序员（不关注数据结构/摊销）会遇到的情况。

持久性 = 不进行原地更新，旧版本仍然存在。摊销 = 将运行时间不均分布在一个操作序列中。两者在严格环境中都不兼容。惰性求值可以调和它们。借记不变式。例如：以二进制形式递增数字。

图约简的实现

关于 G-机器等的简短说明。主要定义

闭包 = thunk = 堆上的代码/数据对。它们做什么？考虑 $(\lambda x.\lambda y.x+y)2$ 。这是一个返回函数的函数，在本例中，它返回 $\lambda y.2+y$ 。但是，当你想编译代码时，实际上在内存中执行替换并用 2 替换 $x$ 的所有出现是不可取的。所以，你返回一个闭包，它由函数代码 $\lambda y.x+y$ 和一个环境 $\{x=2\}$ 组成，该环境将值分配给其中出现的自由变量。

GHC（？，大多数 Haskell 实现？）完全避免使用自由变量，并使用超组合子。换句话说，它们被提供为额外的参数，并且观察到参数过少的 lambda 表达式不需要被约简，因为它们的 WHNF 并没有太大区别。

请注意，这些术语是实现方面的技术术语，惰性求值在没有这些术语的情况下也能很好地运行。请不要在以上任何章节中使用这些术语。

注释

↑ Maraist, John; Odersky, Martin; Wadler, Philip (May 1998). "The call-by-need lambda calculus". Journal of Functional Programming. 8 (3): 257–317.

参考文献

Bird, Richard (1998). Introduction to Functional Programming using Haskell. Prentice Hall. ISBN 0-13-484346-0.
Peyton-Jones, Simon (1987). The Implementation of Functional Programming Languages. Prentice Hall.

图归约

习题解答

Haskell 性能

简介 >> 逐步示例 >> 图归约 >> 惰性求值 >> 时间和空间分析 >> 严格性 >> 算法复杂度 >> 数据结构 >> 并行