用魔法打败魔法：C++模板元编程实现的scheme元循环求值器

First Post:

Blog Link:
[site]

前言

寒假时沉迷C++模板元编程，写了个简单的Scheme元循环求值器。可以用类似Scheme的语法写出这样的C++模板代码：

1
2
3
4
5
6
7
_<lambda, _<V(pred), V(lst)>,
    _<letrec, _<_<V(iter), _<lambda, _<V(lst)>,
                            _<cond,
                                _<_<is_null, lst>, B(false)>,
                                _<_<pred, _<car, lst>>, B(true)>,
                                _<elsee, _<iter, _<cdr, lst>>>>>>>,
        _<iter, lst>>>

等价的Scheme代码是这样的：

1
2
3
4
5
6
7
(lambda (pred lst)
  (letrec ((iter (lambda (lst)
                   (cond
                    ((null? lst) #f)
                    ((pred (car lst)) #t)
                    (else (iter (cdr lst)))))))
    (iter lst)))

可以在运行时输出表达式的值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* mutual recursive 1
 * (letrec
 *   (
 *     (even? (lambda (n)
 *       (if (eqv? n zero)
 *         #t
 *         (odd? (sub1 n)))))
 *     (one 1)
 *     (odd? (lambda (n)
 *       (if (eqv? n zero)
 *         #f
 *         (even? (sub1 n)))))
 *     (sub1 (lambda (n) (- n one)))
 *     (zero (sub1 one)))
 *   (even? 12))
 */
using expr = eval<
    _<letrec,
      _<
          _<V(is_even), _<lambda, _<V(n)>,
                          _<iff, _<is_eq, n, V(zero)>,
                            B(true),
                            _<V(is_odd), _<V(sub1), n>>>>>,
          _<V(one), N(1) >,
          _<V(is_odd), _<lambda, _<V(n)>,
                         _<iff, _<is_eq, n, V(zero)>,
                           B(false),
                           _<is_even, _<V(sub1), n>>>>>,
          _<V(sub1), _<lambda, _<V(n)>, _<sub, n, one>>>,
          _<V(zero), _<sub1, one>>>,
      _<is_even, N(12)>>
>;
runtime<expr>::output(std::cout) << std::endl; // #t

还有一些简单的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* mutual recursive 2
 * (letrec
 *   ((fs (cons
 *          (lambda (n)
 *            (if (eqv? n 0)
 *                #t
 *                ((cdr fs) (- n 1))))
 *          (lambda (n)
 *            (if (eqv? n 0)
 *                #f
 *                ((car fs) (- n 1)))))))
 *   ((car fs) 12))
 */
using expr = eval<
    _<letrec,
        _<_<V(fs), _<cons,
            _<lambda, _<V(n)>,
                _<iff, _<is_eq, n, N(0) >,
                    B(true),
                    _<_<cdr, fs>, _<sub, n, N(1)>>>>,
            _<lambda, _<V(n)>,
                _<iff, _<is_eq, n, N(0) >,
                    B(false),
                    _<_<car, fs>, _<sub, n, N(1)>>>>>>>,
        _<_<car, fs>, N(12)>>
>;
runtime<expr>::output(std::cout) << std::endl; // #t
1
2
3
4
5
6
7
8
9
10
11
12
13
/* dot
 * (let
 *   (
 *     (head (lambda (head . tail) head))
 *   (head 1 2 #f))
 */
using expr = eval<
    _<let,
        _<
            _<V(head), _<lambda, _<V(head), dot, V(tail)>, head>>>,
        _<head, N(1), N(2), B(false)>>
>;
runtime<expr>::output(std::cout) << std::endl; // 1
1
2
3
4
5
// (flat-map list (list 1 2) (list 3 4))
using expr = eval<
    _<flat_map, list, _<list, N(1), N(2) >, _<list, N(3), N(4)>>
>; // interleave
runtime<expr>::output(std::cout) << std::endl; // (1 3 2 4)

当然求值的结果也可以在编译期使用，只是懒得实现了（毕竟本质玩具……而且C++编译期计算用constexpr函数就足够了）。

代码以及详细的介绍位于https://github.com/Light-of-Hers/CCTV

写完后就忘了这茬事了……

这学期修了胡振江老师的PL课，突然想起了自己写的这个玩具，便写下此文记录一下。

语法元素

  • 用变参模板来表示scheme中的列表(list)。
  • 用普通类来表示不携带其他信息的token，比如关键词(keyword)、标识符(identifier)等。
  • 用模板类来表示携带额外信息的token，比如字面量(literal)：number、boolean等。
  • 用模板类来表示denotable value，比如pair、closure等。

其中list和token是用户可见的，为了方便用户的书写：

  • keyword提前声明好，这样用户可以直接写lambda来表示scheme中的lambda。
    • 部分keyword和C++的keyword冲突，做了一些修改，如用iff表示if。
  • 表示list的模板名取为_，这样用户就可以用_<a, b, c>来表示scheme中的(a b c)。
  • 用一个macro来声明代表identifier的普通类：#define V(x) struct x，这样用户可以用V(abc)来表示标识符abc了。而且同一个标识符只要用该宏生成一次（同名类只需声明一次），之后的使用可以不再套个宏了。
  • 用宏N(n)来表示number字面量n，用B(b)来表示boolean字面量b。

考虑到keyword、identifier、denotable value等都用类来表示，故使用继承结构来进行区分：

  • lang
    • keyword
      • lambda, iff, …
    • value
      • pair_value
        • pair
      • atom_value
        • null_atom
          • null
        • number_atom
          • number
        • boolean_atom
          • boolean
        • procedure_atom
          • closure
          • primitive

所有没有继承自lang的类都视为identifier。

表达式求值

C++的模板可以进行pattern match，因此求值函数大部分时候写起来还是蛮轻松的，就不多说了。

不过因为C++模板运算是pure functional的，就导致letrec的实现稍微费了点心思。

r6rs和racket的letrec的是借助side effect（let/let*和set!的语法糖）实现的，而用C++模板实现side effect不太现实（让我用state passing style来实现side effect的话还不如要side effect……）。

fix-point组合子倒是很好的解决方案，不过当时我还没有这方面知识……因此想了个稍显古怪但还挺不错的解决方案：

  • 将environment-frame分类为normal-frame和recurse-frame（前者表示lambda和let等普通的绑定生成的frame，后者表示letrec生成的frame）：
    • 每个frame都有一个前驱frame的引用，一个identifier以及其绑定的value。
    • 一个recurse-frame还有一个标记来表示前驱frame是否和该frame由同一个letrec的bindings生成。
  • 求值letrec的bindings时，按照let*的规则进行，只是生成的frame为recurse-frame。
  • 对environment进行lookup时，若匹配到一个recurse-frame

（其所在letrec所生成frame中的最下游frame为），且其绑定的value为包含一个closure ，绑定的environment为，则：

  • 若

的前驱frame 为所绑定的frame的祖先，即，则返回一个新的closure ，只有绑定的environment与不同，为- 。

  • 否则，直接返回

    • 。

后记

谨以此纪念寒假的摸鱼时光。

≡