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

[Alessandro Baretta <alex@baretta.com>]

Luc Maranget wrote:

>>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 ?

I would expect the PM compiler to do something like 
precompute an appropriate hash of all constant patterns at 
compile time, and use the runtime hash of the matched value 
to jump directly to the pattern (or patterns) having the 
same hash. This might produce some code bloat, for you'd 
need to have an entry for every hash value, whether or not 
there is corresponding pattern. Further, the number of bits 
of hash would need to be computed at compile time as the 
ceil (log_2 <number of constant patterns>). I'm not saying 
that this is the way to go, but I'm pretty sure there is are 
better ways than just a sequential comparison.

> 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.

I don't think the compiler should treat strings in a special 
way. But it should look into the value, even if it were to 
consider it only as a meaningless blob.

> 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.

Well, the original problem dealt mostly with having a clean 
way to write constant patterns, whether they be strings or 
other.

> 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"

But this is basically what I'm saying. The only difference 
is that I advocate having a sort of standard set of 
preprocessor features--syntax extensions in camlp4 
jargon--that one can simply count on when coding. Constant 
definition is among those basic preprocessor features one 
would expect to have in a general purpose language. I'd say 
the solution DdR proposed is worthy of consideration, but it 
would hardly serve its purpose if there is no consensus on 
its general use in Ocaml programs. I'm thinking in terms of 
source code distributions depending on a standard 
development environment: for such an extension to be truly 
useful, any developer should be able to count on having it 
available on the machine of the user.

Of course, every one of us could develop his or her own set 
of syntax extensions, but this would not favor either 
generality or quality of the solutions, and it would lower 
the degree of readability of the code, since any developer 
might end up reading code depending on scarcely documented 
syntax extensions.

Can we have a basic set of syntax extensions which might be 
considered of general interest (constants and conditionals, 
I'd say) accessible with a single backward compatible 
switch/wrapper, and call it a standard?

Alex

-------------------
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