From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA27491; Thu, 24 Oct 2002 10:01:33 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA27823 for <caml-list@pauillac.inria.fr>; Thu, 24 Oct 2002 10:01:32 +0200 (MET DST)
Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g9O81U518725
	for <caml-list@inria.fr>; Thu, 24 Oct 2002 10:01:31 +0200 (MET DST)
Received: from localhost (suiren.kurims.kyoto-u.ac.jp [130.54.16.25])
	by kurims.kurims.kyoto-u.ac.jp (8.9.3/3.7W) with ESMTP id RAA26682;
	Thu, 24 Oct 2002 17:01:23 +0900 (JST)
To: alex@baretta.com
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Again on pattern matching and strings
In-Reply-To: <3DB79CD7.6040600@baretta.com>
References: <3DB73515.90705@baretta.com>
	<20021023235719.GA9170@cs.unibo.it>
	<3DB79CD7.6040600@baretta.com>
X-Mailer: Mew version 1.94.2 on Emacs 21.2 / Mule 5.0 (SAKAKI)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-Id: <20021024170123O.garrigue@kurims.kyoto-u.ac.jp>
Date: Thu, 24 Oct 2002 17:01:23 +0900
From: Jacques Garrigue <garrigue@kurims.kyoto-u.ac.jp>
X-Dispatcher: imput version 20000228(IM140)
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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