Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Need for an equality comparing closures #7633

Closed
vicuna opened this issue Sep 19, 2017 · 3 comments
Closed

Need for an equality comparing closures #7633

vicuna opened this issue Sep 19, 2017 · 3 comments

Comments

@vicuna
Copy link

vicuna commented Sep 19, 2017

Original bug ID: 7633
Reporter: ChriChri
Status: acknowledged (set by @xavierleroy on 2017-09-29T17:50:49Z)
Resolution: open
Priority: normal
Severity: feature
Version: 4.05.0
Category: standard library
Monitored by: ChriChri @gasche

Bug description

If you have a library that needs to memoise a function, without knowing the type of the argument, this will not work with usual equality on functions. In
my use case I really nned to have (f 2) = (f 2) returning true
for any function f.

First, lets say that this equality is definable using the marshal module.
And Hashtbl.hash accepts function. But this definition is bad: it uses memory for nothing and worst does not stop at physically equal nodes.

So why not propose an equality that would compare closures.

By the way, this should probably not replace (=), but it could be the default equality for polymorphic hashtbl ?

This should be rather easy using the code for marshaling.

@vicuna
Copy link
Author

vicuna commented Sep 24, 2017

Comment author: ChriChri

Here is a proposal using Obj ... I am not sure for infix_tag ?

let eq_closure : type a. a -> a -> bool =
  fun f g ->
    let open Obj in
    (* repr f == repr g
       || (Marshal.to_string f [Closures] = Marshal.to_string g [Closures]) *)
    let adone = ref [] in
    let rec fn f g =
      f == g ||
        match is_int f, is_int g with
        | true, true -> f == g
        | false, true | true, false -> false
        | false, false ->
           (*      if !debug_lvl > 10 then Printf.eprintf "*%!";*)
           let ft = tag f and gt = tag g in
           if ft = forward_tag then (
             (*      if !debug_lvl > 10 then Printf.eprintf "#%!";*)
             fn (field f 0) g)
           else if gt = forward_tag then (
             (*      if !debug_lvl > 10 then Printf.eprintf "#%!";*)
             fn f (field g 0))
           else if ft = custom_tag || gt = custom_tag then f = g
           else if ft <> gt then false
           else
           if ft = string_tag || ft = double_tag || ft = double_array_tag
             then f = g
           else if ft = abstract_tag || ft = out_of_heap_tag
                   || ft = no_scan_tag then f == g
           else if ft = infix_tag then
             let off_f = Int32.of_int (size f) in
             let off_g = Int32.of_int (size g) in
             off_f = off_g &&
               fn (Obj.add_offset f off_f)
                    (Obj.add_offset g off_g)
           else
               size f == size g &&
               let rec gn i =
                 if i < 0 then true
                 else fn (field f i) (field g i) && gn (i - 1)
               in
               List.exists (fun (f',g') -> f == f' && g == g') !adone ||
                (List.for_all (fun (f',g') -> f != f' && g != g') !adone &&
                 (adone := (f,g)::!adone;
                  let r = gn (size f - 1) in
                  r))

    in fn (repr f) (repr g)

@vicuna
Copy link
Author

vicuna commented Sep 29, 2017

Comment author: @xavierleroy

Yes, this equality function can probably be written using the Obj module.

This said, I don't think this equality function is useful nor desirable. For memoizing higher-order functions, you would probably get better results by using (==) (physical equality) as the equality function for comparing arguments of function types. (A good memoization library should let the user choose custom equalities for function arguments.)

I move to close this PR without changes.

@github-actions
Copy link

github-actions bot commented May 7, 2020

This issue has been open one year with no activity. Consequently, it is being marked with the "stale" label. What this means is that the issue will be automatically closed in 30 days unless more comments are added or the "stale" label is removed. Comments that provide new information on the issue are especially welcome: is it still reproducible? did it appear in other contexts? how critical is it? etc.

@github-actions github-actions bot added the Stale label May 7, 2020
@github-actions github-actions bot closed this as completed Jun 8, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant