論壇

对于这篇文章，我想从第一性原理在Racket中构建一个数组语言，或者说嵌入式的数组DSL。

这个数组语言的风格接近于APL，其是一种古老的编程语言，并不比Fortran和Lisp晚多少。然而，它的风格却相当特殊，或许可以形容为point-free的组合子式的。

我们并不是要还原APL的编程体验，也不是制作一个嵌入式的APL实现。尽管如此，这个语言在精神上非常接近于APL。

首先我们要思考如何表示一个数组。一个数组可以视为由形状和索引上的函数构成。实际上，虽然这听起来相当fancy，但是历史上第一门编程语言Fortran就采用了这样的观点。（当然了，并不是说Fortran以这种方式实现了数组。）

(struct array (shape indexf) #:transparent)

这是我们对于数组的定义。尽管这个定义相当灵活，留有许多解释的空间，但实际上我们只是利用了很有限的可能性。例如，

(array 100 identity)

代表一个长度为100的数组，这个数组的元素和索引一致，其索引范围是从0到99。

(array '(3 4) +)

代表一个3*4的矩阵，其元素是行与列数之和。

接下来，我们要定义诸多数组上的操作。这些操作充分体现了可复合性。

首先, 我们定义两种操作复合.

(define >>

  (case-lambda

    ((f g) (compose g f))

    ((f g . h*) (apply >> (compose g f) h*))))

这里的>>类似于compose, 但是恰好方向相反.

(define <<

  (case-lambda

    ((x f) (f x))

    ((x f . g*) (apply << (f x) g*))))

这里的<<是将后面的函数按次序应用到第一个参数上.

接着, 我们想要定义Map, 这个非常类似于Racket/Scheme里的map.

(define ((Map f) A)

  (match A

    ((array shape indexf)

     (array shape (compose f indexf)))))

我觉得这个数组语言最为优美的地方在于, 你不是对于逐个元素描述变换, 而是整体通过将函数f与索引函数indexf进行复合来完成了变换. 它可以适用于任意的形状, 但是其实我们什么也没有做.

类似地, 我们可以定义zip-with, 这是来源于那些类型化函数式语言的原语. 虽然我们可以推广Map, 但是暂时我不想这么做, 因为它会使得我们的呈现对于新人而言太过复杂.

(define ((zip-with op) A B)

  (match-define (array shapeA indexfA) A)

  (match-define (array shapeB indexfB) B)

  (unless (equal? shapeA shapeB)

    (error 'zip-with "different shapes: ~s, ~s"

           shapeA shapeB))

  (array shapeA (fork op indexfA indexfB)))

这里的fork也是一种经典的组合子.

(define (fork f g h)

  (λ x (f (apply g x) (apply h x))))

通过这样定义, 可以适应于索引函数接受多个参数的情况.

zip-with要求两个数组A和B具有相同的形状.

接下来, 我们还可以定义Mapi, 其类似于Map, 但是给函数f额外传递了数组元素的位置信息.

(define ((Mapi f) A)

  (match A

    ((array shape indexf)

     (array shape

            (λ indices

              (apply f (apply indexf indices) indices))))))

这样定义的目的仍然是为了适应于多个参数的情况.

接下来我们看Reduce, 这同样是类似于Lisp的reduce (Scheme是Lisp方言, Racket是Scheme方言).

(define ((Reduce f) A)

  (match A

    ((array i indexf)

     (unless (and (integer? i) (> i 0))

       (error 'Reduce "bad shape: ~s" i))

     (let iter ((x 1) (a (indexf 0)))

       (if (= x i)

           a

           (iter (+ x 1) (f a (indexf x))))))))

这个是一维的. 不过, 实际上我们也可以定义适用于任意维度的版本. 只是那仍然对于新人太过复杂, 所以我们只呈现了一维以及后面的二维版本.

(define ((row A) i)

  (match A

    ((array (list _ j) indexf)

     (array j (curry indexf i)))))

(define (rows A)

  (match A

    ((array (list i _) _)

     (array i (row A)))))

(define (Reduce2 f)

  (>> rows

      (Map (Reduce f))

      (Reduce f)))

为了定义二维的版本Reduce2, 我们还定义了row和rows两个函数. row和rows可以推广为对于一般形状降维, 但是我们这里尽可能特殊, 而不考虑一般了. row取一个二维数组的第i行, 这里的定义非常精致, 或许应该揣摩一二. rows也是如此, 其将一个二维数组转换为一个一维数组, 但是每个元素都是二维数组的行. 由此, 通过函数复合, 我们可以优雅地定义Reduce2. 这值得好好品味.

接着, 我们还想定义rho2, 其可以将一维数组转换为二维数组.

(define ((rho2 i j) A)

  (match A

    ((array k indexf)

     (unless (and (integer? k)

                  (= (* i j) k))

       (error 'rho2 "shape mismatch: ~s, ~s, ~s" i j k))

     (array (list i j)

            (λ (x y)

              (indexf (+ (* x j) y)))))))

这只需要元素个数可以对得上即可.

现在我们来思考另外一个问题. 从本质上来说, 我们的数组语言是惰性的 (lazy). 但是, 如果你了解call-by-name和call-by-need的话, 就会知道其实虽然惰性可以避免某些计算, 但是重复的索引会带来重复的计算. 或许我们可以编制一个一般化的备忘化机制, 然而使用某种materialization是最直接的. 其会计算每一个索引处的值, 然后保存固化下来.

(define (materialize1 A)

  (match A

    ((array i indexf)

     (define vec (build-vector i indexf))

     (array i (curry vector-ref vec)))))

(define (build-matrix i j p)

  (build-vector

   i (λ (i)

       (build-vector

        j (λ (j) (p i j))))))

(define (matrix-ref m i j)

  (vector-ref (vector-ref m i) j))

(define (materialize2 A)

  (match A

    ((array (list i j) indexf)

     (define mat (build-matrix i j indexf))

     (array (list i j) (curry matrix-ref mat)))))

接下来, 我们或许还应该定义一些用于构造具体数组的方便原语.

(define (of-array vec)

  (array (vector-length vec)

         (curry vector-ref vec)))

(define (iota n)

  (array n identity))