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 PAA04094; Thu, 24 Oct 2002 15:24:29 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA03805 for ; Thu, 24 Oct 2002 15:24:28 +0200 (MET DST) Received: from beaune.inria.fr (beaune.inria.fr [128.93.8.3]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g9ODORD12889 for ; Thu, 24 Oct 2002 15:24:27 +0200 (MET DST) Received: by beaune.inria.fr (8.8.8/1.1.22.3/14Sep99-0328PM) id PAA0000015374; Thu, 24 Oct 2002 15:24:27 +0200 (MET DST) From: Luc Maranget Message-Id: <200210241324.PAA0000015374@beaune.inria.fr> Subject: Re: [Caml-list] Again on pattern matching and strings To: alex@baretta.com (Alessandro Baretta) Date: Thu, 24 Oct 2002 15:24:26 +0200 (MET DST) Cc: garrigue@kurims.kyoto-u.ac.jp (Jacques Garrigue), caml-list@inria.fr (Ocaml) In-Reply-To: <3DB7E9B5.8020406@baretta.com> from "Alessandro Baretta" at oct 24, 2002 02:38:13 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > > > > Jacques Garrigue wrote: > > > 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:... > > Very strange. I thought the Ocaml compiler sould > precalculate the branch of pattern matching to be taken, and > then jump, thereby avoiding sequential checking. I'm sorry > for my mistake. If you are interested in pm code, I would suggest that you have a look at the produced code after pattern-matching compilation (option -dlambda), before looking at the compiler sources. The issue is not really PM bu rather switches: how to compile a serche in a ordered list of constants ? To sum it up for strings : strings are atoms to the PM compiler which never look into them, it only compares one string against another, for equality only. The match compiler does not make avantage of the known pattern string in any sense. The match compiler does not make avantage of the existence of a lexical ordering on strings. In fact many << optimizations >> are posible here, none is performed. For other ``constants'' from others datatypes (that is at the compiler level for machine integers) the switch compiler performs many optimizations. Basically the compiler mixes tests againts constants (= i < i, etc and a special x in [i1..i2] test) and jump tables. Strings hence remain ``the ghost in the machine'' as regards switch efficiency. All this can be explained by history and by the search of a compromise between compiler complexity on the one hand, and code efficiency on the other. If you want efficient search in a set of strings, PM is not the solution, a library solution is provided by Hastbl or Map. More efficient solutions can be obtained by coding, or provided by third party libraries. As to your original problem, I cannot resist proposing a quick and dirty solution, using cpp, still having meaningful line numbers. yourfile.ml: #define S1 "...." #define S2 "xxxx" ... let f x = match x with | S1 -> ... | S2 -> ... Makefile: CPP=cpp -E -P #Some alternatives... #CPP=/lib/cpp -E -P (Old fashioned Unix) #CPP=gcc -E -P -x c (If you have gcc) .... yourfile.cmo: yourfile.ml ocamlc -pp '${CPP}' -c yourfile.m Of course, this is quite dirty and the previous messages were giving clues to much cleaner solutions. In particular, learning how to use camlp4 is a worthy investment. > Alex Baretta --Luc Maranget ------------------- 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