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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
(************************************************************************)
(* v * The Coq Proof Assistant / The Coq Development Team *)
(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2012 *)
(* \VV/ **************************************************************)
(* // * This file is distributed under the terms of the *)
(* * GNU Lesser General Public License Version 2.1 *)
(************************************************************************)
(** Generic hash-consing. *)
(** {6 Hashconsing functorial interface} *)
module type HashconsedType =
sig
(** {6 Generic hashconsing signature}
Given an equivalence relation [equal], a hashconsing function is a
function that associates the same canonical element to two elements
related by [equal]. Usually, the element chosen is canonical w.r.t.
physical equality [(==)], so as to reduce memory consumption and
enhance efficiency of equality tests.
In order to ensure canonicality, we need a way to remember the element
associated to a class of equivalence; this is done using a hidden state
generated by the [Make] functor.
*)
type t
(** Type of objects to hashcons. *)
type u
(** Type of hashcons functions for the sub-structures contained in [t].
Usually a tuple of functions. *)
val hashcons : u -> t -> t
(** The actual hashconsing function, using its fist argument to recursively
hashcons substructures. It should be compatible with [equal], that is
[equal x (hashcons f x) = true]. *)
val equal : t -> t -> bool
(** A comparison function. It is allowed to use physical equality
on the sub-terms hashconsed by the [hashcons] function, but it should be
insensible to shallow copy of the compared object. *)
val hash : t -> int
(** A hash function passed to the underlying hashtable structure. [hash]
should be compatible with [equal], i.e. if [equal x y = true] then
[hash x = hash y]. *)
end
module type S =
sig
type t
(** Type of objects to hashcons. *)
type u
(** Type of hashcons functions for the sub-structures contained in [t]. *)
val generate : unit -> (u -> t -> t)
(** This has the side-effect of creating (internally) a hashtable of the
hashconsed objects. The result is a function taking the sub-hashcons
functions and an object, and hashconsing it. It does not really make sense
to call [generate] with different sub-hcons functions. That's why we use the
wrappers [simple_hcons], [recursive_hcons], ... The latter just take as
argument the sub-hcons functions (the tables are created at that moment),
and returns the hcons function for [t]. *)
end
module Make (X : HashconsedType) : (S with type t = X.t and type u = X.u)
(** Create a new hashconsing, given canonicalization functions. *)
(** {6 Wrappers} *)
(** These are intended to be used together with instances of the [Make]
functor. *)
val simple_hcons : (unit -> 'u -> 't -> 't) -> ('u -> 't -> 't)
(** [simple_hcons f sub obj] creates a new table each time it is applied to any
sub-hash function [sub]. *)
val recursive_hcons : (unit -> ('t -> 't) * 'u -> 't -> 't) -> ('u -> 't -> 't)
(** As [simple_hcons] but intended to be used with well-founded data structures. *)
val recursive2_hcons :
(unit -> ('t1 -> 't1) * ('t2 -> 't2) * 'u1 -> 't1 -> 't1) ->
(unit -> ('t1 -> 't1) * ('t2 -> 't2) * 'u2 -> 't2 -> 't2) ->
'u1 -> 'u2 -> ('t1 -> 't1) * ('t2 -> 't2)
(** As [recursive_hcons] but with two mutually recursive structures. *)
(** {6 Hashconsing of usual structures} *)
module type HashedType = sig type t val hash : t -> int end
module Hstring : (S with type t = string and type u = unit)
(** Hashconsing of strings. *)
module Hlist (D:HashedType) :
(S with type t = D.t list and type u = (D.t list -> D.t list)*(D.t->D.t))
(** Hashconsing of lists. *)
module Hobj : (S with type t = Obj.t and type u = (Obj.t -> Obj.t) * unit)
(** Hashconsing of OCaml values. *)
|
