《Java的函数式》第十一章：惰性求值

站长

2023年06月21日 22:49 · 阅读数 9

尽管懒惰通常被视为人的缺点，但在编程语言中，它可以被视为一个有利的特性。在计算机科学的术语中，懒惰是代码评估的严格性或渴望性的对立面。

本章将向您展示如何通过懒惰来提高性能。您将了解严格评估和惰性评估之间的区别，以及它们对代码设计的影响。

懒惰与严格性的对比

严格性描述了代码如何被评估的语义。

严格评估会尽快进行，例如在声明或设置变量时，或将表达式作为参数传递时。然而，非严格评估会在实际需要表达式结果时才进行。这样，即使一个或多个子表达式无法评估，表达式仍然可以具有值。函数式编程语言 Haskell 默认具有非严格语义，从外部到内部评估表达式。这使得您可以创建控制结构或无限数据序列，因为表达式的创建和消费是分开的。

让我们来看看下面这段严格的 Java 代码，它是一个简单的方法，接受两个参数，但只使用其中一个来进行逻辑处理：

int add(int x, int y) {
  return x + x;
}

非严格的 Haskell 等效函数声明更像是变量赋值： add x y = x + x

该函数仅使用其第一个参数，并且根本不对第二个参数 y 进行评估。这就是为什么以下的 Haskell 代码仍然能产生结果的原因： add 5 (1/0) => 10

如果你使用相同的参数调用这个函数的Java等效版本，并传递值1和表达式(1/0)，它将抛出一个异常：

var result = add(5, (1/0));
// => java.lang.ArithmeticException: Division by zero

尽管add调用的第二个参数在任何地方都没有被使用，但作为一种严格的语言，Java会立即评估该表达式。方法参数按值传递，这意味着它们在传递给方法之前被求值，而在这种情况下会抛出一个ArithmeticException异常。

相反，延迟求值被定义为仅在需要其结果时才对表达式进行求值。这意味着表达式的声明不会立即触发其求值，这使得Java的Lambda表达式成为延迟求值的完美选择，正如示例11-1中所示。

int add (IntSupplier x, IntSupplier y) {
  var actualX = x.getAsInt();
  return actualX + actualX;
}

var result = add(() -> 5, () -> 1 / 0);
// => 10

IntSupplier实例的声明，或者它们的内联等价物，是一个严格的语句，会立即进行求值。然而，实际的Lambda主体只有在使用getAsInt进行显式调用时才会进行求值，从而避免了这种情况下的ArithmeticException异常。

从本质上讲，严格性涉及"执行事情"，而惰性涉及"考虑要执行的事情"。

Java有多严格？

大多数编程语言既不完全是惰性的，也不完全是严格的。Java被认为是一种严格的语言，但在语言层面和JDK提供的类型中也有一些值得注意的懒惰的例外情况。

让我们逐个介绍它们。

短路求值

在Java中，语言集成的惰性以逻辑短路求值的形式存在，使用逻辑运算符&&（双与符号）和||（双竖线符号）表示AND和OR。这些运算符从左到右逐个对操作数进行求值，仅在需要时进行求值。如果逻辑表达式由运算符左侧的表达式满足，右侧的操作数根本不会被求值，就像在表11-1中所示。

《Java的函数式》第十一章：惰性求值

尽管逻辑运算符类似于控制结构，但它们不能单独存在。它们必须始终是另一个语句的一部分，比如if块的条件或变量赋值，就像在示例11-2中所示。短路求值在赋值中的另一个优点是它们创建了（实际上是）最终引用，如“实际最终”中所讨论的，使它们非常适合与Java的函数式方法一起使用。

// COMPILES: used as if condition
if (left() || right()) {
    // ...
}

// COMPILES: used as variable assignment
var result = left() || right();

// WON'T COMPILE: unused result
left() || right();**

如果表达式很昂贵或具有任何副作用，或者在左侧已经满足条件的情况下不需要进行评估，那么省略右侧操作数的求值非常有帮助。然而，如果语句被短路并且所需表达式位于右侧，这也可能导致未评估所需的表达式。如果将它们作为决策的一部分，确保仔细设计它们。

任何决策代码都极大地受益于纯函数。预期的行为直接明了，容易理解，没有潜藏的副作用，在重新设计或重构代码时可能会被忽视，从而引入难以找出的微妙错误。您应确保要么根本没有副作用，但在我看来，这太绝对，通常是一个不切实际的目标，要么根据它们的影响为方法命名。

控制结构

控制结构负责改变代码中指令的执行路径。例如，if-else结构是一个条件分支，其中包含一个（if）或多个（if-else）代码块。这些代码块只在它们对应的条件满足时进行求值，这是一种惰性特性。严格地在声明时求值if-else结构的任何部分会破坏将其用作条件分支的目的。这种"对渴望规则的惰性例外"适用于所有的分支和循环结构，如表11-2所列。

《Java的函数式》第十一章：惰性求值

一个绝对严格并且没有惰性控制结构的语言很难想象，如果不是不可能的话。

JDK中的惰性类型

到目前为止，我已经谈到了Java的惰性是如何直接内置在语言中，以运算符和控制结构的形式。然而，JDK还提供了多个内置类型和数据结构，在运行时也具有一定程度的惰性。

Lazy Maps

对于Map来说，一个常见的任务是检查一个键是否已经有映射值，并在缺失时提供一个值。相关的代码需要进行多次检查，并使用非（实际上）最终的变量，如下所示：

Map<String, User> users = ...;

var email = "john@doe.com";

var user = users.get(email);
if (user == null) {
  user = loadUser(email);
  users.put(email, user);
}

根据实际的Map实现，代码可能会有所不同，但要点应该是清楚的。一般来说，这已经是一种懒惰的方法，延迟加载用户直到必要时。在对JDK 8中的许多类型进行功能增强的过程中，Map类型使用其computeIf-方法获得了更简洁和功能性的替代方案。根据键的映射值是否存在，有两个可用的方法：

V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)
V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)

第一个方法是前面示例代码的理想替代方案，如下所示：

Map<String, User> users = ...;

var user = users.computeIfAbsent("john@doe.com", this::loadUser);

该方法需要所需的键作为第一个参数，并且需要一个映射函数 Function<K, V> 作为第二个参数，如果键不存在，则为键提供新的映射值。computeIfPresent方法只有在值存在时才对其进行重新映射。

这两种方法的组合形式也可以通过 V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) 方法实现。根据重新映射函数的结果，它可以更新甚至删除映射值，如图11-1所示。

《Java的函数式》第十一章：惰性求值

函数式方法在Map类型的惰性扩展中清晰可见。不再需要编写冗长且重复的代码来处理Map及其映射值，现在您可以集中精力关注发生了什么以及如何处理键和值。

Streams

Java流(Streams)是惰性函数式流水线的完美例子。您可以定义一个复杂的流水线架构，其中包含昂贵的函数操作，只有在调用终端操作后才开始评估。处理的元素数量完全取决于流水线的设计，通过在数据处理流水线中分离表达式的定义和实际评估，您可以尽量减少所需的工作量。

第6章详细介绍了流(Streams)及其对数据处理的惰性方法。

Optionals

Optional是处理null值的非惰性方式。它们的一般方法类似于Streams，但与Streams相比，它们进行严格的求值。有一些惰性操作可用，例如利用Supplier来延迟执行的T orElseGet(Supplier<? extends T> supplier)方法，只有在绝对必要时才会执行。

第9章对Optional进行了详细介绍，并提供了更多关于如何使用它们的信息。

Lambda表达式和高阶函数

Lambda表达式是在代码级别引入惰性的绝佳方式。它们的声明是一个语句，因此会被严格评估。然而，它们的主体——单个抽象方法——封装了实际的逻辑，并在您的选择下进行评估。这使得它们成为一种简单的方式，用于存储和传递表达式以供以后评估。

让我们来看一些急切的代码，用于向方法提供参数，以及如何通过使用Lambda表达式使其变得惰性。

一种急切的方法

在示例11-3中，一个假设的用户被更新为具有一组角色。更新不总是发生，而是取决于更新方法的内部逻辑。参数是急切地提供的，需要通过DAO进行相当昂贵的查找调用。

User updateUser(User user, List<Role> availableRoles) { 
  // ...
}

// HOW TO USE

var user = loadUserById(23L);
var availableRoles = this.dao.loadAllAvailableRoles(); 
var updatedUser = updateUser(user, availableRoles);

即使在每种用例中都不需要所有可用的角色，也提供给updateUser，这样会导致不必要的数据库调用和性能浪费。那么，如果它并不总是需要，如何使调用非强制性呢？通过引入惰性。

一种更懒惰的方法

在像Java这样的严格语言中，所有方法参数都是一次性提供的，并且如实传递。即使实际上并不需要某个参数，该方法也必须接受它们。当涉及到执行昂贵的操作来预先创建这些参数（例如数据库调用）时，这尤其成为一个问题，这可能会耗尽您的可用资源和性能。

解决不必要的数据库调用的天真方法是将updateUser更改为直接接受DAO，并在需要时使用它：

User updateUser(User user, DAO roleDAO) {
  // ...
}

现在，updateUser方法已经具备了自行加载可用角色所需的所有工具。从表面上看，非惰性数据访问的初始问题得到了解决，但是这种"解决方案"却产生了一个新问题：内聚性。

updateUser方法现在直接使用DAO，不再与获取角色的方式隔离。这种方法将使方法变得不纯，因为访问数据库被视为副作用，使得验证和测试变得更加困难。如果updateUser方法根本不知道DAO类型，由于可能的API边界，情况甚至变得更加复杂。因此，您需要创建另一个抽象来检索角色。与创建额外的抽象层以弥合DAO和updateUser方法之间的差距不同，您可以将updateUser作为高阶函数，并接受一个Lambda表达式。

一种函数式的方法

为了在示例11-3中创建一个用于检索所需用户角色的函数式抽象，您首先必须将问题分解为更抽象的表示形式，找出实际上需要什么作为参数，而不是参数的值是如何产生的。

updateUser方法需要访问可用角色，这反映在原始方法的签名中。这正是引入惰性将为您提供最灵活解决方案的代码点。

Supplier类型是一种最低级的可能性，用于根据需要封装某些逻辑以检索值。不直接向updateUser提供DAO，而是使用lambda表达式作为惰性中间结构来加载角色，如示例11-4所示。

void updateUser(User user, Supplier<List<Role>> availableRolesFn) { 
  // ...

  var availableRoles = availableRolesFn.get();

  // ...
}


// HOW TO USE

var user = loadUserById(23L);

updateUser(user, this.dao::loadAllAvailableRoles);

通过接受一个Supplier来使updateUser成为一个高阶函数，创建了一个表面上的新层，而无需额外的自定义类型来包装角色加载过程。直接使用DAO作为参数消除了以下缺点：

DAO和updateUser方法之间不再有连接，从而创建了一个纯净的、无副作用的方法的可能性。
您不需要额外的类型来表示抽象。已经可用的Supplier函数接口是最简单和最兼容的抽象形式。
恢复了可测试性，无需复杂地模拟DAO。

如果可以避免调用，那么昂贵的操作（如数据库查询）可以从惰性方法中获益。然而，并不意味着将所有方法参数都变成惰性参数而没有实际需要是正确的方法。还有其他解决方案，例如缓存昂贵调用的结果，可能比设计方法调用以接受惰性参数更简单。

使用 Thunk 进行延迟执行

Lambda表达式是一种简单而底层的方法，用于封装表达式以供以后评估。不过，有一个遗漏的地方是在评估后存储结果——即缓存，这在第2章中讨论过——这样可以避免重复调用时重新评估表达式。有一种简单的方法来解决这个问题：Thunk。

Thunk是对计算的封装，延迟到需要结果时才执行。与Supplier（也延迟计算）不同，Thunk仅评估一次，并在后续调用中直接返回结果。

Thunk属于延迟加载/初始化的一般类别，这是常见于面向对象代码的设计模式。这两种技术——延迟加载和延迟初始化——是实现相同目标的类似机制：非严格评估和缓存结果。Supplier仅推迟评估，而Thunk还缓存其结果。

让我们创建一个简单的Thunk，遵循虚拟代理设计模式，作为Supplier的替代品。

创建一个简单的Thunk

最直接的方法是包装一个Supplier实例，并在第一次评估后存储其结果。通过实现Supplier接口，Thunk成为一个可直接替换的对象，如示例11-5所示。

public class Thunk<T> implements Supplier<T> { 

  private final Supplier<T> expression; 

  private T result; 

  private Thunk(Supplier<T> expression) {
    this.expression = expression;
  }

  @Override
  public T get() {
    if (this.result == null) { 
      this.result = this.expression.get();
    }
    return this.result;
  }

  public static <T> Thunk<T> of(Supplier<T> expression) { 
    if (expression instanceof Thunk<T>) { 
      return (Thunk<T>) expression;
    }
    return new Thunk<T>(expression);
  }
}

这个Thunk实现简单而强大。通过使用任何Supplier调用工厂方法来创建一个可直接替换的对象，它添加了记忆化功能。像前面一节中更新User那样，需要将方法引用包装在Thunk.of方法中： updateUser(user, Thunk.of(this.dao::loadAllAvailableRoles));

对于Thunk，函数式的扩展不必止步于此。可以很容易地添加“粘合方法”来支持函数组合，就像在第2章中讨论的那样，如示例11-6所示。

public class Thunk<T> implements Supplier<T> {

  // ...

  public static <T> Thunk<T> of(T value) { 
    return new Thunk<T>(() -> value);
  }

  public <R> Thunk<R> map(Function<T, R> mapper) { 
    return Thunk.of(() -> mapper.apply(get()));
  }

  public void accept(Consumer<T> consumer) { 
    consumer.accept(get());
  }
}

尽管添加了“粘合”方法，Thunk 类型变得更加多功能，可以用于创建单个表达式的惰性流水线。

然而，一个普遍的问题仍然存在：线程安全性。

线程安全的Thunk

对于单线程环境，我在前面讨论的 Thunk 实现会按预期工作。然而，如果在表达式评估时从另一个线程访问它，就可能出现竞争条件导致重新评估。防止这种情况发生的唯一方法是在所有访问线程之间进行同步。

最直接的方法是在 get 方法中添加 synchronized 关键字。然而，这种方法的明显缺点是始终需要同步访问和相关的开销，即使评估已经完成。同步可能不像以前那么慢，但它仍然是每次调用 get 方法的开销，并且肯定会不必要地减慢代码速度。

那么，如何改变实现以消除竞争条件，而对整体性能的影响尽可能小？您需要对可能发生竞争条件的位置和时间进行风险分析。与评估相关的竞争条件风险仅存在于表达式评估之前。之后，不会发生重复评估，因为结果已经返回。这使您只需要同步评估本身，而不是每次调用 get 方法。

示例 11-7 展示了引入一个专用的、同步的 evaluate 方法。很快将解释其实际实现以及如何访问其结果。

public class Thunk<T> implements Supplier<T> {

  private Thunk(Supplier<T> expression) {
    this.expression = () -> evaluate(expression);
  }

  private synchronized T evaluate(Supplier<T> expression) {
    // ...
  }

  // ...
}

之前的 Thunk 版本使用了一个额外的字段 value 来确定表达式是否已经评估过。然而，新的线程安全变体则使用了一个专用的抽象来保存值，替代了存储值及其检查的方式：

private static class Holder<T> implements Supplier<T> {

  private final T value;

  Holder(T value) {
    this.value = value;
  }

  @Override
  public T get() {
    return this.value;
  }
}

Holder承担了两个任务：

保存已评估的值。
实现Supplier接口。

由于Holder实现了Supplier接口，它可以作为字段表达式的替代品。因此，可以使用一种称为比较与交换（CAS）的技术。CAS被用于设计并发算法，通过将变量的值与期望值进行比较，如果相等，则将值替换为新值。这个操作必须是原子的，意味着对底层数据的访问要么全部成功，要么全部失败。这就是为什么evaluate方法必须是同步的。任何线程都可以在评估之前或之后看到数据，但在评估过程中永远不会看到数据，从而消除了竞态条件。

现在，私有字段expression可以被新类型替代，如示例11-8所示。

public class Thunk<T> implements Supplier<T> {

  private static class Holder<T> implements Supplier<T> {
    // ...
  }

  private Supplier<T> holder; 

  private Thunk(Supplier<T> expression) {
    this.holder = () -> evaluate(expression);
  }

  private synchronized T evaluate(Supplier<T> expression) {
    if (Holder.class.isInstance(this.holder) == false) { 
      var evaluated = expression.get();
      this.holder = new Holder<>(evaluated); 
    }
    return this.holder.get();
  }

  @Override
  public T get() {
    return this.holder.get(); 
  }
}

改进后的Thunk实现并不像以前那么简单，但通过将表达式的评估与访问解耦，消除了竞态条件。

首次访问时，holder字段将调用evaluate方法，该方法是同步的，因此是线程安全的。在表达式评估期间的任何其他调用也将调用evaluate方法。但与重新评估不同，holder字段的类型检查会直接跳过，返回this.holder.get()调用的结果。在重新分配holder后的任何访问都会完全跳过同步操作。

就是这样，现在你拥有了一个线程安全、只评估一次的可延迟求值的Supplier替代品。

我们的Thunk实现使用了synchronized，但实现CAS算法有多种方法。可以使用JDK的java.util.concurrent.atomic包中的Atomic-类型之一，甚至可以使用ConcurrentHashMap#computeIfAbsent来防止竞态条件。《Java Concurrency》一书（作者：Brian Goetz等人）是更好地理解原子变量、非阻塞同步和Java并发模型的良好起点。

最后对惰性评价的思考

在本质上，惰性评价的核心思想是将所需的工作推迟到不可或缺的时刻。在创建和使用表达式之间的分离为代码提供了新的模块化轴线。如果某个操作是可选的，而且对于每个使用情况都不是必需的，这种方法可以极大地提高性能。然而，惰性评价也意味着你必须放弃对评价时间的精确控制。

这种被认为和实际上的控制丧失使得代码的性能特性更加难以理解。总体性能要求是所有已评价部分的总和。急切评价允许相当线性和组合性能评估。而惰性评价将实际计算成本从定义表达式的位置转移到使用表达式的位置，并且有可能根本不运行某些代码。这就是为什么习惯上的惰性性能评估更加困难；与急切评价相比，感知性能很可能会立即改善，特别是如果代码中有许多代价高昂但可能是可选的代码路径。整体性能要求可能会因一般上下文和实际评估的代码而异。您需要分析惰性代码的平均使用模式，并在不同场景下估计所需的性能特征，这使得简单的基准测试变得非常具有挑战性。

软件开发是有效利用有限资源以达到期望或要求的性能的持续斗争。像延迟评价或流式数据处理这样的惰性技术是改进代码性能的低成本方法，很容易集成到现有代码库中。这些技术肯定会将所需工作减少到最低甚至零，为其他任务释放宝贵的性能。如果某个表达式或昂贵的计算可以避免，将其变为惰性评价无疑是值得的长期努力。