协调抽象和高性能: MetaOCaml方法

摘要

生成式编程的一个常见应用是生成高度特化于手头问题的高性能计算内核. 一个典型的线性代数内核会针对数值域 (有理数, 浮点数, 双精度浮点数, 等等), 循环展开因子, 数组布局和先验知识 (例如, 矩阵是正定的) 进行特化. 手动特化 (编写相同算法的诸多变种) 是乏味无聊且容易出错的.

广泛使用的生成器, 例如ATLAS和SPIRAL, 能够可靠地产生高度特化的代码, 但是很难扩展. 对于ATLAS而言, 其使用printf生成代码, 甚至连括号匹配都成为了挑战. 根据ATLAS的作者所言, debug如同梦魇.

第1章 引入

第1.1节 为什么元编程?

第1.2节 为什么这个教程?

第1.3节 为什么MetaOCaml

第1.4节 概览

第1.5节 获得MetaOCaml

第2章 第一步

第2.1节 Now or later

第2.2节 幂

尽管已经成为陈词滥调, power这个例子仍然是介绍元编程的最快方式之一. 以下的power函数可以计算xn:

let square x = x * x
let rec power : int -> int -> int = fun n x ->
  if n = 0 then 1
  else if n mod 2 = 0 then square(power (n/2) x)
  else x * (power (n-1) x)
我们已经显式地附加了类型签名, 尽管并无必要: 类型可以推断出来. 不过, 给top-level的函数添加签名一般而言是个好的想法: 它可以使得代码更容易编写, 之后更容易理解, 并且能够使得错误信息更加清晰.

设我们的程序需要计算x7很多次, 那么我们可以定义

let power7 x = power 7 x
来命名和分享这部分求值.

在MetaOCaml里, 我们也可以特化幂函数于一个特定的值n, 得到之后可以接受x并计算xn的代码.