Re: [Caml-list] possible to define a type where = is forbidden ?

Re: [Caml-list] possible to define a type where = is forbidden ?

[yoann padioleau]

> On Oct 10, 2005, at 2:32 PM, yoann padioleau wrote:
> 
> > I am making a program analysis tool  and in my AST I had previously  
> > tokens represented as strings,
> > but now I want also to associate the line numbers of those strings.
> 
> I like to suggest a different technique that does not require to change  
> the representation of all branches in an AST. You can find it in an  
> earlier posting here:
> 
> http://caml.inria.fr/pub/ml-archives/caml-list/2003/09/ 
> f81c8063ed4878e06f1ddd8010256050.en.html

Interesting technique :)  but I think that it would not solve my problem. 

To be more precise my program analysis tool  try to compute "diff" between differents AST.
So we love to use pattern-patching and to (ab)use the polymorphic  =  to compare stuff.

I don't see how your ExprAt technique will make this easier (not to mention that it also makes 
the pattern matching ugly because I would have to wrap every  expression  with his ExprAt  because I want
that the resultting  Ast_diff  contain also line number.

Re: [Caml-list] possible to define a type where = is forbidden ?

[Thomas Fischbacher]

On Mon, 10 Oct 2005, yoann padioleau wrote:

> > http://caml.inria.fr/pub/ml-archives/caml-list/2003/09/ 
> > f81c8063ed4878e06f1ddd8010256050.en.html
> 
> Interesting technique :)  but I think that it would not solve my problem. 
> 
> To be more precise my program analysis tool  try to compute "diff" between differents AST.
> So we love to use pattern-patching and to (ab)use the polymorphic  =  to compare stuff.
> 
> I don't see how your ExprAt technique will make this easier (not to mention that it also makes 
> the pattern matching ugly because I would have to wrap every  expression  with his ExprAt  because I want
> that the resultting  Ast_diff  contain also line number.

When you want to associate extra data to stuff that should retain nice 
comparison properties, another technique which might be useful or not is 
to use a weak pointer hash, mapping subtrees to positions.

I would not go so far as to say that this is the favored approach one 
should use, but sometimes this idea may be useful. At least, it's nice to 
have that trick available.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

EQ hash tables?

[Thomas Fischbacher]

On Mon, 10 Oct 2005, Thomas Fischbacher wrote:

> When you want to associate extra data to stuff that should retain nice 
> comparison properties, another technique which might be useful or not is 
> to use a weak pointer hash, mapping subtrees to positions.

Actually, this brings me to a question I wanted to ask for a long time: 
while I never used this so far, I just assumed that OCaml does provide 
hash tables where keys are compared w.r.t. "being the same" ('==' , that 
is), rather than only hash tables where keys are compared for "being 
equal" (say, '=').

Of course, "EQ hash tables" have to be treated in a slightly special way 
when talking about stop&copy GCing. 

So, do they really exist, or don't they?

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] EQ hash tables?

[Hendrik Tews]

Thomas Fischbacher <Thomas.Fischbacher@Physik.Uni-Muenchen.DE> writes:

   Actually, this brings me to a question I wanted to ask for a long time: 
   while I never used this so far, I just assumed that OCaml does provide 
   hash tables where keys are compared w.r.t. "being the same" ('==' , that 
   is), rather than only hash tables where keys are compared for "being 
   equal" (say, '=').
   
Just look at hash.ml:

    let find h key =
      match h.data.((hash key) mod (Array.length h.data)) with
        Empty -> raise Not_found
      | Cons(k1, d1, rest1) ->
          if compare key k1 = 0 then d1 else
             ^^^^^^^^^^^^^^^^^^

So it's structual equality, which is the same as '=' modulo the
float nan issue.

Bye,

Hendrik

Re: [Caml-list] EQ hash tables?

[Xavier Leroy]

> Actually, this brings me to a question I wanted to ask for a long time:
> while I never used this so far, I just assumed that OCaml does provide
> hash tables where keys are compared w.r.t. "being the same" ('==' , that
> is), rather than only hash tables where keys are compared for "being
> equal" (say, '=').

Easily definable using the functorial interface to hash tables:

module MyEqHashTable =
  Hashtbl.Make(struct
      type t = my_type_for_keys
      let equal = (==)
      let hash = Hashtbl.hash
    end)

> Of course, "EQ hash tables" have to be treated in a slightly special way
> when talking about stop&copy GCing.

No, not "of course".  You're thinking of using the address of a memory
block as its hash value.  This indeed requires GC support.  But you
can get the semantics you want (keys compared by reference) while
still computing the hash code structurally.  This is what the code
snippet above does.

- Xavier Leroy

Re: [Caml-list] EQ hash tables?

[Thomas Fischbacher]

On Wed, 12 Oct 2005, Xavier Leroy wrote:

> Easily definable using the functorial interface to hash tables:
> 
> module MyEqHashTable =
>   Hashtbl.Make(struct
>       type t = my_type_for_keys
>       let equal = (==)
>       let hash = Hashtbl.hash
>     end)
> 
> > Of course, "EQ hash tables" have to be treated in a slightly special way
> > when talking about stop&copy GCing.
> 
> No, not "of course".  You're thinking of using the address of a memory
> block as its hash value.  This indeed requires GC support.  But you
> can get the semantics you want (keys compared by reference) while
> still computing the hash code structurally.  This is what the code
> snippet above does.

Hm, okay. I agree that this does give me the same semantics.

But doesn't this degrade expected lookup performance to an O(n) list 
lookup if I put a lot of stuff into the hash which is (=) but not (==)?

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] EQ hash tables?

[Xavier Leroy]

> Hm, okay. I agree that this does give me the same semantics.
> But doesn't this degrade expected lookup performance to an O(n) list
> lookup if I put a lot of stuff into the hash which is (=) but not (==)?

Yes, of course.  It depends on your application.  For things like
hash-consing, this approach (standard hash function + comparison finer
than (=)) can still work well.  Alternatively, you can always put
unique integers in the data type used as key.

- Xavier Leroy

Re: [Caml-list] EQ hash tables?

[Thomas Fischbacher]

On Wed, 12 Oct 2005, Xavier Leroy wrote:

> Alternatively, you can always put
> unique integers in the data type used as key.

Suppose I define:

type network = Links of network array

and now, I set out to construct a wildly linked such network, which may 
indeed have the property that it "looks the same" from different places. 

Let us assume, for example, that entities of type network represent 
elements of a discrete group that is spawned by two generators, and 
the entries in Links [|a,b,a_inv,b_inv|] are the elements that are reached 
by left-application of the group generators A, B, or their inverses.


How would one write a function that counts the sites in such a network? 
With proper EQ hash tables, it's quite easy.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)