Re: [Caml-list] Again on pattern matching and strings

[Jacques Garrigue <garrigue@kurims.kyoto-u.ac.jp>]

From: Alessandro Baretta <alex@baretta.com>
> Stefano Zacchiroli wrote:
> > What about:
> > 
> >   | Some m when m = printer_set_unit -> ...
> >   | Some m when m = printer-reset -> ...
> >   | Some m when m = printer_formfeed -> ...
> >   ...
> >   | Some (_) -> assert false
> >   | None -> ()
> > 
> > It isn't so bad ...
> 
> Eh, no! This is really unacceptable as a general solution. 
> Of course, I could have coded my function this way, but this 
> technique is not scalable, especially from the perspective 
> of computational efficiency. Your code is compiled as a 
> sequence of comparisons on a strings. Hence, the matched 
> string is scanned once for every pattern. With constant 
> patterns, on the other hand, the compiler should scan the 
> string only once and jump to appropriate code. This is more 
> compact, but not necessarily more efficient, as Jacques 
> pointed out a while ago.
> ( http://caml.inria.fr/archives/200101/msg00111.html )

That message was about polymorphic variants, which are encoded as
integers, and for which pattern-matching is a decision tree.

However, if you look in bytecomp/matching.ml, you will see that string
patterns are just checked sequentially (the ordering is not used).
Moreover, the match compiler seems to be clever enough to compile
properly the above style:
# function Some s when s = a -> 0 | Some s when s = b -> 1
  | Some s when s = c -> 2 | Some _ -> assert false | None -> 3;;
(let
  (a/64 (apply (field 0 (global Toploop!)) "a")
   b/65 (apply (field 0 (global Toploop!)) "b")
   c/66 (apply (field 0 (global Toploop!)) "c"))
  (function param/73
    (if param/73
      (let (s/70 (field 0 param/73))
        (if (string_equal s/70 a/64) 0
          (if (string_equal s/70 b/65) 1
            (if (string_equal s/70 c/66) 2
              (raise
                (makeblock 0 (global Assert_failure/26g) [0: "" 94 106]))))))
      3)))
- : string option -> int = <fun>

So efficiency is actually not a reason to avoid this style...
(Verbosity may be one.)

   Jacques Garrigue
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners