OOP Visitors在Polymorphic情况下的类型错误

diff --git "a/2023/06/28/OOP-Visitors\345\234\250Polymorphic\346\203\205\345\206\265\344\270\213\347\232\204\347\261\273\345\236\213\351\224\231\350\257\257/index.html" "b/2023/06/28/OOP-Visitors\345\234\250Polymorphic\346\203\205\345\206\265\344\270\213\347\232\204\347\261\273\345\236\213\351\224\231\350\257\257/index.html" new file mode 100644 index 00000000..2f715eea --- /dev/null +++ "b/2023/06/28/OOP-Visitors\345\234\250Polymorphic\346\203\205\345\206\265\344\270\213\347\232\204\347\261\273\345\236\213\351\224\231\350\257\257/index.html" @@ -0,0 +1,243 @@ + + + + + + + + + + + + + + + + + + + + + +OOP Visitors在Polymorphic情况下的类型错误 | 暮秋小屋 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ +

+ + + 暮秋小屋 + + +

+ +

+ 主页 +
+ 技术 +
+ 项目 +
+ 日记本 +
+ 关于 +

+ + +

+ +

+ + + OOP Visitors在Polymorphic情况下的类型错误 + + +

+ + Jun 28, 2023 + +

+ +

像Java里面:

interface Tree {
  public <B> B accept(TreeVisitor<B> v);
}

interface TreeVisitor<B> {
  public B visitLeaf(Leaf t);
}

class Leaf implements Tree {
  public final int value;

  public Leaf(int value) {
    this.value = value;
  }

  public <B> B accept(TreeVisitor<B> v) {
    return v.visitLeaf(this);
  }
}

+ +

要是从字面上直接翻译成OCaml:

class virtual tree =
  object
    method virtual accept : 'a . 'a tree_visitor -> 'a
  end

and virtual ['a] tree_visitor =
  object
    method virtual visit_leaf : (leaf -> 'a)
  end

and leaf (i : int) =
  object (self)
    method get = i

    method accept (v : 'a tree_visitor) : 'a =
      v#visit_leaf (self :> leaf)
  end

+ +

是行不通滴:

File "visitor.ml", line 3, characters 28-54:
3 |     method virtual accept : 'a . 'a tree_visitor -> 'a
                                ^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: The universal type variable 'a cannot be generalized:
       it escapes its scope.

+ +

OCaml的类在定义时是单态的，比如:

class ['a] c (x:'a) = 
  object
    method x = x
  end
and d = 
  object
    method strange = (new c 0)#x
  end

+ +

这里c是:

1	class ['a] c : 'a -> object constraint 'a = int method x : 'a end

+ +

因为在d里面new c 0了一个 int c 的对象。

所以正确的写法应该是:

class virtual ['a, 'leaf, 'node, 'empty] open_tree_visitor = 
  object
    method virtual visit_leaf :  'leaf -> 'a
    method virtual visit_node :  'node -> 'a
    method virtual visit_empty :  'empty -> 'a
  end

class virtual tree = 
  object
    method virtual accept : 'a .
      ('a, 'leaf, 'node, 'empty) open_tree_visitor -> 'a
  end

and leaf (i : int) = 
  object (self:'self)
    inherit tree
    method get = i
    method accept v = v#visit_leaf (self :> leaf)
  end

and node (x : tree) (y: tree) = 
  object (self:'self)
    inherit tree
    method left = x
    method right = y
    method accept v = v#visit_node (self :> node)
  end

and empty = 
  object (self:'self)
    inherit tree
    method accept v = v#visit_empty (self :> empty)
  end

+ + + + + +

+ + + + + + + +

+ + +

+ + + +

+ + + + + + diff --git "a/2023/06/28/caml-release-runtime-system\345\257\274\350\207\264\347\232\204\346\255\273\351\224\201\351\227\256\351\242\230/index.html" "b/2023/06/28/caml-release-runtime-system\345\257\274\350\207\264\347\232\204\346\255\273\351\224\201\351\227\256\351\242\230/index.html" new file mode 100644 index 00000000..77754735 --- /dev/null +++ "b/2023/06/28/caml-release-runtime-system\345\257\274\350\207\264\347\232\204\346\255\273\351\224\201\351\227\256\351\242\230/index.html" @@ -0,0 +1,247 @@ + + + + + + + + + + + + + + + + + + + + + +caml_release_runtime_system导致的死锁问题 | 暮秋小屋 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ +

+ + + 暮秋小屋 + + +

+ +

+ 主页 +
+ 技术 +
+ 项目 +
+ 日记本 +
+ 关于 +

+ + +

+ +

+ + + caml_release_runtime_system导致的死锁问题 + + +

+ + Jun 28, 2023 + +

+ +

给出一个test.ml:

1	Printf.eprintf "hello from OCaml\n%!"

+ +

和test-ocaml-5.c:

#include <stdio.h>
#include <stdlib.h>
#include <caml/misc.h>
#include <caml/callback.h>
#include <caml/threads.h>

int
main (int argc, char *argv[])
  {
    fprintf (stderr, "starting up ...\n");
    caml_startup (argv);
    fprintf (stderr, "acquiring ...\n");
    caml_acquire_runtime_system ();
    fprintf (stderr, "acquired\n");
    // here is where I would be calling an OCaml callback
    // omitted for simplicity
    caml_release_runtime_system ();
    exit (0);
  }

+ +

然后用OCaml5的ocaml native compiler编译一下（这里我用的是ocaml-variants.5.0.0+options）：
ocamlopt -g test-ocaml-5.c test.ml -o test-ocaml-5

运行test-ocaml-5 会出现:

starting up ...
hello from OCaml
acquiring ...
Fatal error: Fatal error during lock: Resource deadlock avoided

[1]    8998 IOT instruction (core dumped)  ./test-ocaml-5

+ +

这里我尝试了一下 4.14.0 和 4.14.1 ，都没有出现这个情况，而如果用threads编译的话:
ocamlopt -g -I +unix unix.cmxa -I +threads threads.cmxa test-ocaml-5.c test.ml -o test-ocaml-5

无论在5.0还是4.14.x，都会挂起。

出现这个问题的一个可能原因是，在test-ocaml-5.c中，我在开头调用了caml_startup()，这会让当前线程获取锁，而caml_acquire_runtime_system()会再次获取它，caml_acquire_runtime_system() 应该在caml_release_runtime_system（）之后调用：

int
main (int argc, char *argv[])
  {
    fprintf (stderr, "starting up ...\n");
    caml_startup (argv);
    fprintf (stderr, "acquiring ...\n");
    caml_release_runtime_system ();
    caml_acquire_runtime_system ();
    fprintf (stderr, "acquired\n");
    exit (0);
  }

+ +

运行结果为:

starting up ...
hello from OCaml
acquiring ...
acquired

+ + + + + +

+ + + + + + + +

+ + +

+ + + +

+ + + + + + diff --git "a/2023/06/28/\351\232\220\350\227\217\344\270\200\344\272\233OCaml-Effect\347\232\204\346\234\272\345\210\266\357\274\214\350\256\251\345\205\266\350\257\255\346\263\225\345\234\250\347\262\276\347\245\236\344\270\212\346\233\264\346\216\245\350\277\221delimcc/index.html" "b/2023/06/28/\351\232\220\350\227\217\344\270\200\344\272\233OCaml-Effect\347\232\204\346\234\272\345\210\266\357\274\214\350\256\251\345\205\266\350\257\255\346\263\225\345\234\250\347\262\276\347\245\236\344\270\212\346\233\264\346\216\245\350\277\221delimcc/index.html" new file mode 100644 index 00000000..cc6471c9 --- /dev/null +++ "b/2023/06/28/\351\232\220\350\227\217\344\270\200\344\272\233OCaml-Effect\347\232\204\346\234\272\345\210\266\357\274\214\350\256\251\345\205\266\350\257\255\346\263\225\345\234\250\347\262\276\347\245\236\344\270\212\346\233\264\346\216\245\350\277\221delimcc/index.html" @@ -0,0 +1,237 @@ + + + + + + + + + + + + + + + + + + + + + +隐藏一些OCaml Effect的机制，让其语法在精神上更接近delimcc | 暮秋小屋 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ +

+ + + 暮秋小屋 + + +

+ +

+ 主页 +
+ 技术 +
+ 项目 +
+ 日记本 +
+ 关于 +

+ + +

+ +

+ + + 隐藏一些OCaml Effect的机制，让其语法在精神上更接近delimcc + + +

+ + Jun 28, 2023 + +

+ +

delimcc_of_fxhandler这个库在OCaml5的effect handlers上实现了一些delimcc原语(shift/reset, control/prompt这些)：

let p = new_prompt () in
assert ([] = push_prompt p (fun () ->
               1::2::take_subcont p (fun _k -> [])));
assert ([1;2] = push_prompt p (fun () ->
               1::2::take_subcont p (fun k -> push_subcont k [])));
assert (135 =
  let p1 = new_prompt () in
  let p2 = new_prompt () in
  let p3 = new_prompt () in
  let pushtwice sk =
    sk (fun () ->
      sk (fun () ->
        shift0 p2 (fun sk2 -> sk2 (fun () ->
          sk2 (fun () -> 3))) ()))
   in
   push_prompt p1 (fun () ->
     push_prompt p2 (fun () ->
       push_prompt p3 (fun () -> shift0 p1 pushtwice ()) + 10) + 1) + 100);

print_endline "Success!"

+ +

另外， avsm这里可以看到一些OCaml的Effect Syntax进展。

还有 multi-shot continuations in OCaml，在这个仓库里面还讨论了一些有趣的问题，例如，OCaml 编译器和runtime会做出一些假设从而进行一些优化，这些优化在使用multi-shot continutation时是不可取的（或完全错误的）。编译器优化导致错误的一个例子是堆到栈的转换，例如:

(* An illustration of how the heap to stack optimisation is broken.
 * This example is adapted from de Vilhena and Pottier (2021).
 * file: heap2stack.ml
 * compile: ocamlopt -I $(opam var lib)/multicont multicont.cmxa heap2stack.ml
 * run: ./a.out *)

(* We first require a little bit of setup. The following declares an
   operation `Twice' which we use to implement multiple returns. *)
type _ Effect.t += Twice : unit Effect.t

(* The handler `htwice' interprets `Twice' by simply invoking its
   continuation twice. *)
let htwice : (unit, unit) Effect.Deep.handler
  = { retc = (fun x -> x)
    ; exnc = (fun e -> raise e)
    ; effc = (fun (type a) (eff : a Effect.t) ->
      let open Effect.Deep in
      match eff with
      | Twice -> Some (fun (k : (a, _) continuation) ->
         continue (Multicont.Deep.clone_continuation k) ();
         continue k ())
      | _ -> None) }

(* Now for the interesting stuff. In the code below, the compiler will
   perform an escape analysis on the reference `i' and deduce that it
   does not escape the local scope, because it is unaware of the
   semantics of `perform Twice', hence the optimiser will transform
   `i' into an immediate on the stack to save a heap allocation. As a
   consequence, the assertion `(!i = 1)' will succeed twice, whereas
   it should fail after the second return of `perform Twice'. *)
let heap2stack () =
  Effect.Deep.match_with
    (fun () ->
      let i = ref 0 in
      Effect.perform Twice;
      i := !i + 1;
      Printf.printf "i = %d\n%!" !i;
      assert (!i = 1))
    () htwice

(* The following does not trigger an assertion failure. *)
let _ = heap2stack ()

(* To fix this issue, we can wrap reference allocations in an instance
   of `Sys.opaque_identity'. However, this is not really a viable fix
   in general, as we may not have access to the client code that
   allocates the reference! *)
let heap2stack' () =
  Effect.Deep.match_with
    (fun () ->
      let i = Sys.opaque_identity (ref 0) in
      Effect.perform Twice;
      i := !i + 1;
      Printf.printf "i = %d\n%!" !i;
      assert (!i = 1))
    () htwice

(* The following triggers an assertion failure. *)
let _ = heap2stack' ()

+ +

+ + + + + +

+ + + + + + + +

+ + +

+ + + +

+ + + + + + -- cgit v1.2.3