函数式思维: 惰性计算,第 1 部分

探索 Java 中的惰性计算

许多函数式编程语言的一个共同特性是惰性计算,也就是说,仅在必要时,而不是在声明时,对表达式进行求值。Java™ 不支持这种风格的惰性,但一些框架和相关语言却支持。本文将介绍如何使用纯 Java 和函数式框架在您的 Java 应用程序中构建惰性。

Neal Ford, 软件架构师, ThoughtWorks Inc.

Neal FordNeal Ford 是一家全球性 IT 咨询公司 ThoughtWorks 的软件架构师和 Meme Wrangler。他的工作还包括设计和开发应用程序、教材、杂志文章、课件和视频/DVD 演示,而且他是各种技术书籍的作者或编辑,包括最近的新书 The Productive Programmer。他主要的工作重心是设计和构建大型企业应用程序。他还是全球开发人员会议上的国际知名演说家。请访问他的 Web 站点



2012 年 12 月 27 日

关于本系列

本系列旨在将您看问题的角度重新调整为函数式思维,帮助您以新的方式看待常见问题,并找出改进日常编码的方法。本文探讨了函数式编程的一些概念、在 Java 语言中实现函数式编程的框架、在 JVM 上运行的函数式编程语言,以及语言设计的一些未来倾向。本系列文章面向那些了解 Java 及其工作原理,但极少或没有使用函数式语言的有经验的开发人员。

惰性计算(尽可能延迟表达式求值)是许多函数式编程语言的特性。惰性集合在需要时提供其元素,无需预先计算它们,这带来了一些好处。首先,您可以将耗时的计算推迟到绝对需要的时候。其次,您可以创造无限个集合,只要它们继续收到请求,就会继续提供元素。第三,mapfilter 等函数的惰性使用让您能够得到更高效的代码(请参阅 参考资料 中的链接,加入由 Brian Goetz 组织的相关讨论)。Java 并没有为惰性提供原生支持,但一些框架和后继语言支持这种惰性,我会在本期和下期文章中探讨它们。

假定使用此伪代码片段来打印列表的长度:

print length([2+1, 3*2, 1/0, 5-4])

如果您尝试执行此代码,结果会因为代码的编程语言类型的不同而有所不同:严格不严格(也被称为惰性)。在严格的编程语言中,执行(或编译)此代码产生一个 DivByZero 异常,原因是列表的第三个元素。在不严格的语言中,其结果是 4,它准确地报告了列表中的项目数。毕竟,我调用的方法是 length(),而不是 lengthAndThrowExceptionWhenDivByZero()!Haskell 是为数不多的仍在使用的不严格语言(请参阅 参考资料)。可惜的是,Java 不支持不严格的计算,但您仍然可以在 Java 中使用惰性的概念。

在 Java 中的惰性迭代器

Java 缺乏对惰性集合的原生支持,但这并不意味着您不能使用 Iterator 模拟一个惰性集合。在本系列的前几篇文章中,我使用了一个简单的素数算法来说明函数式概念。我会在 上期文章 中介绍的优化类的基础上展开本文的讨论,同时提供清单 1 中展示的增强:

清单 1. 确定素数的简单算法
import java.util.HashSet;
import java.util.Set;
import static java.lang.Math.sqrt;

public class Prime {

    public static boolean isFactor(int potential, int number) {
        return number % potential == 0;
    }

    public static Set<Integer> getFactors(int number) {
        Set<Integer> factors = new HashSet<Integer>();
        factors.add(1);
        factors.add(number);
        for (int i = 2; i < sqrt(number) + 1; i++)
            if (isFactor(i, number)) {
                factors.add(i);
                factors.add(number / i);
            }
        return factors;
    }

    public static int sumFactors(int number) {
        int sum = 0;
        for (int i : getFactors(number))
            sum += i;
        return sum;
    }

    public static boolean isPrime(int number) {
        return number == 2 || sumFactors(number) == number + 1;
    }

    public static Integer nextPrimeFrom(int lastPrime) {
        lastPrime++;
        while (! isPrime(lastPrime)) lastPrime++;
        return lastPrime;
    }
}

前面的一期文章 详细讨论了这个类是如何确定某个整数是否是素数的细节。在 清单 1 中,我添加了 nextPrimeFrom() 方法,根据输入的参数生成下一个素数。该方法在本文即将出现的示例中发挥了重要的作用。

一般情况下,开发人员认为迭代器会使用集合作为后备存储,但是支持 Iterator 接口的任何集合都符合这个条件。因此,我可以创建一个素数的无限迭代器,如清单 2 所示:

清单 2. 创建一个惰性迭代器
public class PrimeIterator implements Iterator<Integer> {
    private int lastPrime = 1;

    public boolean hasNext() {
        return true;
    }

    public Integer next() {
        return lastPrime = Prime.nextPrimeFrom(lastPrime);
    }

    public void remove() {
       throw new RuntimeException("Can't change the fundamental nature of the universe!");
    }
}

清单 2 中,hasNext() 方法始终返回 true,因为就我们目前所掌握的知识,素数的数量是无限的。remove() 方法在此处不适用,所以在意外调用情况下,会抛出一个异常。沉稳的做法是使用 next() 方法,它用一行代码处理两件事。第一,它调用我在 清单 1 中添加的 nextPrimeFrom() 方法,根据上一个素数生成下一个素数。第二,它利用了 Java 在单个语句中完成赋值与返回结果的能力,更新内部的 lastPrime 字段。我在清单 3 中执行惰性迭代器:

清单 3. 测试惰性迭代器
public class PrimeTest {
    private ArrayList<Integer> PRIMES_BELOW_50 = new ArrayList<Integer>() {{
                add(2);  add(3);  add(5);  add(7);  add(11);  add(13);
                add(17); add(19); add(23); add(29); add(31);  add(37);
                add(41); add(43); add(47);
            }};

    @Test
    public void prime_iterator() {
        Iterator<Integer> it = new PrimeIterator();
        for (int i : PRIMES_BELOW_50) {
            assertTrue(i == it.next());
        }
    }
}

清单 3中,我创建了一个 PrimeIterator,并验证它会报告前 50 个素数。虽然这不是迭代器的典型用法,但它模仿一些惰性集合的有用行为。


使用 LazyList

Jakarta Commons 包括一个 LazyList 类(请参阅 参考资料),它结合使用了装饰设计模式和工厂。如果要使用 Commons LazyList,则必须包装一个现有列表,使其具有惰性,并为新值创建一个工厂。请考虑使用清单 4 中的 LazyList

清单 4. 测试 Commons LazyList
public class PrimeTest {
    private ArrayList<Integer> PRIMES_BELOW_50 = new ArrayList<Integer>() {{
                add(2);  add(3);  add(5);  add(7);  add(11);  add(13);
                add(17); add(19); add(23); add(29); add(31);  add(37);
                add(41); add(43); add(47);
            }};

    @Test
    public void prime_factory() {
        List<Integer> primes = new ArrayList<Integer>();
        List<Integer> lazyPrimes = LazyList.decorate(primes, new PrimeFactory());
        for (int i = 0; i < PRIMES_BELOW_50.size(); i++)
            assertEquals(PRIMES_BELOW_50.get(i), lazyPrimes.get(i));
    }
}

清单 4 中,我创建一个新的空白 ArrayList 并将它包装在 Commons LazyList.decorate() 方法中,还有一个 PrimeFactory 用于生成新值。Commons LazyList 使用列表中已存在的值,不论该值是什么,当对一个尚未赋值的索引调用 get() 方法时,LazyList 会使用工厂(在本例中为 PrimeFactory())生成和填充值。PrimeFactory 出现在清单 5 中:

清单 5. LazyList 使用的 PrimeFactory
public class PrimeFactory implements Factory {
    private int index = 0;

    @Override
    public Object create() {
        return Prime.indexedPrime(index++);
    }
}

所有惰性列表都需要使用某种方法来生成后续的值。在 清单 2 中,我使用了 next() 方法和 PrimenextPrimeFrom() 方法的组合。对于 清单 4 中的 Commons LazyList,我使用了 PrimeFactory 实例。

Commons LazyList 实现有一个特点,就是在请求新值时,没有信息传递给工厂方法。根据设计,它甚至没有传递所请求元素的索引,强制在 PrimeFactory 类上维护当前状态。这产生了对返回列表的不必要的依赖(因为它必须初始化为空,以便让索引和 PrimeFactory 的内部状态保持同步)。Commons LazyList 是最好的基础实现,但还有更好的开源替代方案,如 Totally Lazy。


Totally Lazy

Totally Lazy 是一个框架,它将一流的惰性添加到 Java(请参阅 参考资料)。在 前面的一期文章 中,我介绍过 Totally Lazy,但介绍得并不详细。该框架的目标之一是使用静态导入集合来创建一个高度可读的 Java 代码。清单 6 中简单的素数查找程序在编写时充分利用了这个 Totally Lazy 特性:

清单 6. Totally Lazy,充分利用静态导入
import com.googlecode.totallylazy.Predicate;
import com.googlecode.totallylazy.Sequence;

import static com.googlecode.totallylazy.Predicates.is;
import static com.googlecode.totallylazy.numbers.Numbers.equalTo;
import static com.googlecode.totallylazy.numbers.Numbers.increment;
import static com.googlecode.totallylazy.numbers.Numbers.range;
import static com.googlecode.totallylazy.numbers.Numbers.remainder;
import static com.googlecode.totallylazy.numbers.Numbers.sum;
import static com.googlecode.totallylazy.numbers.Numbers.zero;
import static com.googlecode.totallylazy.predicates.WherePredicate.where;

public class Prime {
    public static Predicate<Number> isFactor(Number n) {
        return where(remainder(n), is(zero));
    }

    public static Sequence<Number> factors(Number n){
        return range(1, n).filter(isFactor(n));
    }

    public static Number sumFactors(Number n){
        return factors(n).reduce(sum);
    }

    public static boolean isPrime(Number n){
        return equalTo(increment(n), sumFactors(n));
    }
}

清单 6 中,在完成静态导入后,代码是非典型的 Java,但有很强的可读性。Totally Lazy 的部分灵感来自 JUnit 的 Hamcrest 测试扩展的接口(请参阅 参考资料),它还使用了 Hamcrest 的一些类。isFactor() 方法变成了对 where() 的调用,结合使用了 Totally Lazy 的 remainder() 与 Hamcrest is() 方法。同样,factors() 方法变成了针对 range() 对象调用 filter(),我使用现已熟悉的 reduce() 方法来确定总和。最后,isPrime() 方法使用 Hamcrest 的 equalTo() 方法来确定因数的总和是否等于递增的数字。

细心的读者会注意到,清单 6 中的实现的确优化了我在前面的一期文章 中所提及的实现,使用了更高效的算法来确定因数。优化后的版本如清单 7 所示:

清单 7. 优化的素数查找程序的 Totally Lazy 实现
public class PrimeFast {
    public static Predicate<Number> isFactor(Number n) {
        return where(remainder(n), is(zero));
    }

    public static Sequence<Number> getFactors(final Number n){
        Sequence<Number> lowerRange = range(1, squareRoot(n)).filter(isFactor(n));
        return lowerRange.join(lowerRange.map(divide().apply(n)));
    }

    public static Sequence<Number> factors(final Number n) {
        return getFactors(n).memorise();
    }

    public static Number sumFactors(Number n){
        return factors(n).reduce(sum);
    }

    public static boolean isPrime(Number n){
        return equalTo(increment(n), sumFactors(n));
    }
}

清单 7 中有两个主要变化。首先,我改进了 getFactors() 算法,以获得平方根下的因数,然后生成平方根之上的对称因数。在 Totally Lazy 中,即使像 divide() 这样的操作也可以使用连贯接口样式来表达。第二个变化涉及内存,它会自动缓存使用相同参数的函数调用,我已经修改了 sumFactors() 方法,以便使用 getFactors() 方法,它是内存化的 getFactors() 方法。Totally Lazy 将内存实现为框架的一部分,因此,实现此优化并不需要更多的代码,但框架的作者将其拼写为 memorise(),而不是更传统的(如在 Groovy 中)memoize()

像 Totally Lazy 这个名称所声明的那样,Totally Lazy 试图​​在整个框架中尽可能使用惰性。事实上,Totally Lazy 框架本身就包含了一个 primes() 生成程序,它使用框架的构建块实现素数的无限序列。请考虑 Numbers 类的节选代码,如清单 8 所示:

清单 8. 实现无限素数的 Totally Lazy 节选代码
public static Function1<Number, Number> nextPrime = new Function1<Number, Number>() {
       @Override
       public Number call(Number number) throws Exception {
       	      return nextPrime(number);
      }
};

public static Computation<Number> primes = computation(2, computation(3, nextPrime));

public static Sequence<Number> primes() {
       return primes;
}
 
public static LogicalPredicate<Number> prime = new LogicalPredicate<Number>() {
    public final boolean matches(final Number candidate) {
        return isPrime(candidate);
    }

};

public static Number nextPrime(Number number) {
    return iterate(add(2), number).filter(prime).second();
}

nextPrime() 方法创建了一个新的 Function1,它是一个伪高阶函数的 Totally Lazy 实现,该方法旨在接受单一 Number 参数,并产生一个 Number 结果。在本例中,它返回 nextPrime() 方法的结果。primes 变量已创建,用于存储素数的状态,使用 2(第一个素数)作为种子值执行计算,并使用一个新的计算来产生下一个素数。这是惰性实现中的典型模式:保存下一个元素,加上用于产生随后的值的方法。prime() 方法仅仅是一个包装程序,围绕之前执行的 prime 计算。

为了确定 清单 8 中的 nextPrime(),Totally Lazy 创建了一个新的 LogicalPredicate,以封装已确定的素数,然后创建 nextPrime() 方法,它在 Totally Lazy 中使用良好的接口来确定下一个素数。

在 Java 中使用低层的静态导入,以促进可读代码的使用,Totally Lazy 在这方面表现得很出色。许多开发人员认为 Java 对于内部的域特定语言是较差的主机,但 Totally Lazy 消除了这种态度。它积极地采用惰性,延缓所有可能的操作。


结束语

在这一期文章中,我探索了惰性计算,首先在 Java 中使用迭代器创建一个模拟惰性集合,然后使用了来自 Jakarta Commons Collections 的基本 LazyList 类。最后,我利用了 Totally Lazy 来实现示例代码,在内部与素数的惰性无限集合中,使用惰性集合来确定素数。Totally Lazy 也说明了良好接口表示,并使用静态导入来提高代码的可读性。

在下一期文章中,我将继续探索惰性计算,并将重心转移到 Groovy、Scala 和 Clojure。

参考资料

学习

  • Haskell:Haskell 是一个开源的高级函数式编程语言,经过多年研究而研究出的产品。
  • LazyList:这是 Jakarta Commons LazyList 实现的 API 页面。
  • "State of the Lambda: Libraries Edition":Brian Goetz 讨论了惰性在代码生成中的优势。
  • Totally Lazy:Totally Lazy 框架将大量函数式扩展添加到 Java,使用类似于 DSL 的直观接口。
  • Hamcrest:Hamcrest 提供匹配程序对象(也被称为约束或谓词)的库,支持以声明方式定义 “匹配” 规则,以便在其他框架中使用。(Hamcrest 已被 移植到 GitHub。)
  • "演化架构和紧急设计: 连贯接口"(Neal Ford,developerWorks,2010 年 7 月):看看连贯接口如何从代码的语法中删除不必要的噪音,使其更具可读性。
  • Design Patterns: Elements of Reusable Object-Oriented Software (Erich Gamma et al., Addison-Wesley, 1994):您可以在 Gang of Four 关于设计模式的经典作品中阅读 Decorator 模式。
  • Scala:Scala 是在 JVM 上的一个现代的函数式语言。
  • Clojure:Clojure 是在 JVM 上运行的一个现代的函数式 Lisp。
  • "Execution in the Kingdom of Nouns"(Steve Yegge,2006 年 3 月):有关 Java 语言设计某些方面的一个有趣的批评。
  • developerWorks Java 技术专区:这里有数百篇关于 Java 编程各个方面的文章。

获得产品和技术

讨论

条评论

developerWorks: 登录

标有星(*)号的字段是必填字段。


需要一个 IBM ID?
忘记 IBM ID?


忘记密码?
更改您的密码

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件

 


在您首次登录 developerWorks 时,会为您创建一份个人概要。您的个人概要中的信息(您的姓名、国家/地区,以及公司名称)是公开显示的,而且会随着您发布的任何内容一起显示,除非您选择隐藏您的公司名称。您可以随时更新您的 IBM 帐户。

所有提交的信息确保安全。

选择您的昵称



当您初次登录到 developerWorks 时,将会为您创建一份概要信息,您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。

昵称长度在 3 至 31 个字符之间。 您的昵称在 developerWorks 社区中必须是唯一的,并且出于隐私保护的原因,不能是您的电子邮件地址。

标有星(*)号的字段是必填字段。

(昵称长度在 3 至 31 个字符之间)

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件.

 


所有提交的信息确保安全。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Java technology, Open source
ArticleID=852569
ArticleTitle=函数式思维: 惰性计算,第 1 部分
publish-date=12272012