如何在C++/Ocaml之间安全地翻译树数据结构？

Question

我有一个用C++编写的遗留数据结构和OCaml中的一个新工具,该工具有望处理这些遗留数据.所以我需要将前者的数据导入/转换为后者.数据采用树形式,通常由访问者处理.

作为一个简单的例子考虑这个最小的DSL:

#include <memory>

using namespace std;

class intnode;
class addnode;

struct visitor {
    virtual void visit(const intnode& n) = 0;
    virtual void visit(const addnode& n) = 0;
};

struct node {
    virtual void accept(visitor& v) = 0;
};

struct intnode : public node {
    int x;

    virtual void accept(visitor& v) { v.visit(*this); }
};

struct addnode : public node {
    shared_ptr<node> l;
    shared_ptr<node> r;

    virtual void accept(visitor& v) { v.visit(*this); }
};

它在OCaml中的表示如下所示:

type node = Int of int
          | Plus of node * node

let make_int x = Int x
let make_plus l r = Plus(l,r)

问题是,如何安全有效地将C++树转换为其OCaml表示？

到目前为止,我有两种方法:

方法1

编写一个调用OCaml构造函数的访问者并生成一个value,例如:

value translate(shared_ptr<node> n);

struct translator : public visitor {
    value retval;

    virtual visit(const intnode& n) {
        retval = call(make_int, Val_int(x->value));
    }

    virtual visit(const addnode& n) {
        value l = translate(n.l);
        value r = translate(n.r);
        retval =  call(make_add, l, r);
    }
};

value translate(shared_ptr<node> n)
{
    translator t;
    t.visit(*n);
}

简单地假设call所有必需的脚手架都要回调到OCaml并调用正确的构造函数.

这种方法的问题是OCaml的garbag收集器.如果GC运行,而C++端有一些valueon是堆栈,那么该值(它毕竟是指向OCaml堆的指针)可能会失效.所以我需要一些方法来告知OCaml关于仍然需要这些值的事实.通常这是通过CAML*宏完成的,但是在这样的情况下我该怎么办呢？我可以在visit方法中使用这些宏吗？

方法2

第二种方法更复杂.当无法安全存储中间引用时,我可以扭转局面并将C++指针推送到OCaml堆中:

type cppnode (* C++ pointer *)

type functions = {
  transl_plus : cppnode -> cppnode -> node;
  transl_int : int -> node;
}

external dispatch : functions -> cppnode -> node = "dispatch_transl"

let rec translate n = dispatch {transl_plus; transl_int = make_int} n

and transl_plus a b = make_plus (translate a) (translate b)

这里的想法是函数"dispatch"将所有子节点包装到CustomVal结构中并将它们传递给OCaml而不存储任何中间值.相应的访问者只会实现模式匹配.这应该明确地与GC一起使用,但是具有稍微低效的缺点(因为指针包装)并且可能不太可读(因为分派和重建之间的区别).

有没有办法通过方法1的优雅获得方法2的安全性？

Answer 1

即使在递归情况下，我也没有发现在 C 堆栈上构建 OCaml 值有任何问题。在您的示例中，您使用结构成员来存储 OCaml 堆值。这也是可能的，但是，您需要使用caml_register_global_rootor和 来使用orcaml_register_generational_root释放它们。事实上，您甚至可以构建一个保存 OCaml 值的智能指针。caml_remove_global_rootcaml_remove_generational_global_root

综上所述，我仍然没有看到任何理由（至少对于您演示的简化示例）为什么您应该为此进入类成员，这就是我解决它的方法：

struct translator : public visitor {

    virtual value visit(const intnode& n) {
        CAMLparam0();
        CAMLlocal1(x);
        x = call(make_int, Val_int(n->value);
        CAMLreturn(x);
    }

    virtual value visit(const addnode& n) {
        CAMLparam0();
        CAMLlocal(l,r,x);
        l = visit(*n.l);
        r = visit(*n.r);
        x = call(make_add, l, r);
        CAMLreturn(x);
    }
};

当然，这是假设您有一个可以返回任意类型值的访问者。如果您没有，并且不想实施，那么您绝对可以逐步构建您的价值：

value translate(shared_ptr<node> n);

class builder : public visitor {
    value result;
 public:
    builder() {
       result = Val_unit; // or any better default
       caml_register_generational_global_root(&result);
    }

    virtual ~builder() {
       caml_remove_generational_global_root(&result);
    }

    virtual void visit(const intnode& n) {
        CAMLparam0();
        CAMLlocal1(x);
        x = call(make_int, Val_int(n->value);
        caml_modify_generational_global_root(&result, x);
        CAMLreturn0;
    }

    virtual void visit(const addnode& n) {
        CAMLparam0();
        CAMLlocal(l,r,x);
        l = translate(n.l);
        r = translate(n.r);
        x = call(make_add, l, r);
        caml_modify_generational_global_root(&result,x)
        CAMLreturn0;
    }
};

value translate(share_ptr<node> node) {
  CAMLparam0();
  CAMLlocal1(x);
  builder b;
  b.visit(*node);
  x = b.result;
  CAMLreturn(x);
}

您还可以查看 Berke Durak 的Aurochs项目，该项目使用 C 构建解析树。