Re: cyclic value construction ("let rec")

From: Markus Mottl (mottl@miss.wu-wien.ac.at)
Date: Mon Apr 03 2000 - 14:57:19 MET DST

  • Next message: Jacques Garrigue: "Re: Semantic of label: The best (only ?) solution to merge both mode"

    > It would be interesting to know whether people have other workarounds.
    > Also, a generic graph module which would implement "map", "iter" etc. in a
    > cycle-safe way (like Marshal) would perhaps be interesting in the
    > 'user-contributed stdlib extension'...

    You will probably always have to rely on "unsafe" things for such
    purposes. My quick hack for problems like this looks as follows:

      type 'a node = { data : 'a; next : 'a node }

      let make_circle n : 'a node =
        let module Dummy = struct
          type 'a t = { data : 'a; mutable next : 'a t } end in
        let res = { Dummy.data = n; Dummy.next = Obj.magic 0 } in
        res.Dummy.next <- res;
        Obj.magic res

      let rec iter f node = f node.data; iter f node.next

      let _ = iter (fun x -> print_int x; print_newline ()) (make_circle 42)

    Type "'a node" is immutable from the outside. However, exploiting the
    undocumented (good reason for this ;-) type casting features of OCaml,
    one can cheat and define an identical type within a local module -
    which is mutable!

    Initialisation, too, relies on "unsafe" features - we simply put a
    reference to a dummy value into the slot until it can be filled with the
    "right" value. The return value is cast back again to the "global type"
    as indicated in the type restriction in the definition of "make_circle"
    - this is important, because otherwise you can crash your program (it
    would have "any" type).

    As far as I know, this should be safe, because the GC doesn't care
    about the static types of the values - it only looks at the value tags
    at runtime. Of course, the above will only work as long as the memory
    layout of the "local" type agrees with the one of the "global type".

    Thus, you can confine the "unsafe" part to specific functions (e.g.
    "make_circle"). The iteration function "iter" does not change anything
    and can therefore work on the "global" type.

    Best regards,
    Markus Mottl

    -- 
    Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl
    



    This archive was generated by hypermail 2b29 : Thu Apr 06 2000 - 15:16:35 MET DST