Re: [Caml-list] Pattern matching and strings

Re: [Caml-list] Pattern matching and strings

[Alessandro Baretta]

Of course: everything from irreversible thermodynamics to 
XML technologies. I happen to have a weak spot on CamlP4. 
Either in Langages or Compilation, someone could have 
mentioned stream parsers and LL1, for example. I grew up in 
the innocent misunderstanding that all "real" parser were 
LALR...

Alex

Luc Maranget wrote:
>>I really must get around to learning Camlp4. Why did no one 
>>teach it to me when I was at the X?
>>
> 
> 
> Normaly, you were (also) taught to learn by yourself there...!
> 
> --Luc
> 
> 

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

[Caml-list] Pattern matching and strings

[Alessandro Baretta]

I have to do a little bit of pattern matching on strings. My 
first instict was to write something like the following.

let foo x = ...
let bar x = ...
... = function
| "foo" ^ rest -> foo rest
| "bar" ^ rest -> bar rest
| _ -> raise Unrecognized

Of course, this is not possible because (^) is an operator 
rather than a constructor. Since I believe that the above 
code is much more natural and idiomatic than code based on 
regexps, I wonder how much compiler magic it would take to 
make it work. Probably all it takes is some syntax-magic 
since the above can be mapped onto the following:

open Scanf

... = function x -> begin
   try sscanf x "foo%[^]" foo with Scan_failure _ ->
   try sscanf x "bar%[^]" bar with Scan_failure _ ->
     raise Unrecognized
end

An equivalent mapping could be done with the Str library or 
any other regexp library.

However, the former is much cleaner. If it could be had, I'd 
appreciate it.

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

Re: [Caml-list] Pattern matching and strings

[Luc Maranget]

> 
> I have to do a little bit of pattern matching on strings. My 
> first instict was to write something like the following.
> 
> let foo x = ...
> let bar x = ...
> ... = function
> | "foo" ^ rest -> foo rest
> | "bar" ^ rest -> bar rest
> | _ -> raise Unrecognized
> 
> Of course, this is not possible because (^) is an operator 
> rather than a constructor. Since I believe that the above 
> code is much more natural and idiomatic than code based on 
> regexps, I wonder how much compiler magic it would take to 
> make it work. Probably all it takes is some syntax-magic 
> since the above can be mapped onto the following:

Hum, I am not found of such an idea. As you tell yoursef,  ``(^)  is
an operator rather than a  constructor''. Making a special case for
(^) is a bad idea from the start.
The special thing about a pattern is that is contains constructors,
variables, (and constants) and nothing else.
This restriction allows efficient
compilation and lots of static checks in some uniform framework.
Getting out of the uniform framework is a risk
(cf. n+k patterns in Haskell eg).

> 
> open Scanf
> 
> ... = function x -> begin
>    try sscanf x "foo%[^]" foo with Scan_failure _ ->
>    try sscanf x "bar%[^]" bar with Scan_failure _ ->
>      raise Unrecognized
> end
> 
you mean

 ... = function x -> begin
    try sscanf x "foo%s" foo with Scan_failure _ ->
    try sscanf x "bar%s" bar with Scan_failure _ ->
      raise Unrecognized
 end



> An equivalent mapping could be done with the Str library or 
> any other regexp library.
Those libs are optional.... (at present).

I agree, having some kind of fusion between ML pattern-matching and
regexp-matching is an issue, there is research work on this.
But this means lot of work...

> 
> Alex


--Luc 


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

Re: [Caml-list] Pattern matching and strings

[Sven Luther]

On Wed, Oct 02, 2002 at 04:12:34PM +0200, Alessandro Baretta wrote:
> I have to do a little bit of pattern matching on strings. My 
> first instict was to write something like the following.
> 
> let foo x = ...
> let bar x = ...
> ... = function
> | "foo" ^ rest -> foo rest
> | "bar" ^ rest -> bar rest
> | _ -> raise Unrecognized

What about :

... = function
  | str when String.sub str 0 3 = "foo" -> foo (String.sub str 2 (String.length str - 3))
  | str when String.sub str 0 3 = "bar" -> bar (String.sub str 2 (String.length str - 3))
  | _ -> raise Unrecognized

Sure, this code is not very optimal, i guess you could write a nicer
function which will test the string incrementally using just String.get
or something such, but i suppose it will do the thing you want.

Friendly,

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

Re: [Caml-list] Pattern matching and strings

[Andreas Rossberg]

Sven Luther wrote:
> 
> On Wed, Oct 02, 2002 at 04:12:34PM +0200, Alessandro Baretta wrote:
> > I have to do a little bit of pattern matching on strings. My
> > first instict was to write something like the following.
> >
> > let foo x = ...
> > let bar x = ...
> > ... = function
> > | "foo" ^ rest -> foo rest
> > | "bar" ^ rest -> bar rest
> > | _ -> raise Unrecognized
> 
> What about :
> 
> ... = function
>   | str when String.sub str 0 3 = "foo" -> foo (String.sub str 2 (String.length str - 3))
>   | str when String.sub str 0 3 = "bar" -> bar (String.sub str 2 (String.length str - 3))
>   | _ -> raise Unrecognized
> 
> Sure, this code is not very optimal, i guess you could write a nicer
> function which will test the string incrementally using just String.get
> or something such, but i suppose it will do the thing you want.

The SML basis library provides the nice but often overlooked concept of
substrings (or more generally, vector slices,
http://SML.sourceforge.net/Basis/substring.html). Ported to Caml the
Substring module would enable

> ... = function
>   | s when Substring.is_prefix "foo" s -> foo (Substring.triml 3 s)
>   | s when Substring.is_prefix "bar" s -> bar (Substring.triml 3 s)
>   | _ -> raise Unrecognized

where your parsing functions operate on substrings instead of strings.
Such an approach seems like a good compromise between use of a heavy
regexp lib and inefficient repeated copying of parts of strings.

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids; I mean if Pac Man affected us
 as kids, we would all be running around in darkened rooms, munching
 magic pills, and listening to repetitive electronic music."
 - Kristian Wilson, Nintendo Inc.
-------------------
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

Re: [Caml-list] Pattern matching and strings

[Kontra, Gergely]

[..]
>The SML basis library provides the nice but often overlooked concept of
>substrings (or more generally, vector slices,

It seems, that core ocaml doesn't have any kind of good string
processing :(. Ok, it has some, but you need to type very much...
+-[Kontra, Gergely @ Budapest University of Technology and Economics]-+
|         Email: kgergely@mcl.hu,  kgergely@turul.eet.bme.hu          |
|  URL:   turul.eet.bme.hu/~kgergely    Mobile: (+36 20) 356 9656     |
+-------"Olyan langesz vagyok, hogy poroltoval kellene jarnom!"-------+
.
Magyar php mirror es magyar php dokumentacio: http://hu.php.net

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

Re: [Caml-list] Pattern matching and strings

[Luc Maranget]

> I have to do a little bit of pattern matching on strings. My
 > first instict was to write something like the following.
 >
 > let foo x = ...
 > let bar x = ...
 > ... = function
 > | "foo" ^ rest -> foo rest
 > | "bar" ^ rest -> bar rest
 > | _ -> raise Unrecognized


I have thought about that a little.

My first guess is that such matching should be distinct from
ordinary PM, mixing the two would be an implementor nightmare.

My second guess is that what you want is regexp matching + a construct
for binding subparts of the matched string (maybe I am wrong here).

Using ocamllex syntax for patterns (+ as) your exemple could be written

regexpmatch s with
| "foo" (_* as x)  -> foo x
| "bar" (_* as x)  -> bar x
| _*               -> raise Unrecognized


This would be much nicer than using various regexp packages API, the
real add-on being the variables in place of \1, \2 etc.

Of course this would work only in the case where all patterns are known
statically and implementation is not 100% trivial, if you want some
warnings and compile-time production of matching automata.
(ie if you do not rely on regexp package).

In fact such, an extension is probably feasible using camlp4 and this
would probably be the best solution, to avoid extra-complexity in the
compiler itself.


In the end, do not hold your breath. I won't probably do that.
But it can be a interesting project for a compiler course...

--Luc



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

Re: [Caml-list] Pattern matching and strings

[Alessandro Baretta]

Luc Maranget wrote:

> I have thought about that a little.
> 
> My first guess is that such matching should be distinct from
> ordinary PM, mixing the two would be an implementor nightmare.
> 
> My second guess is that what you want is regexp matching + a construct
> for binding subparts of the matched string (maybe I am wrong here).
> 
> Using ocamllex syntax for patterns (+ as) your exemple could be written
> 
> regexpmatch s with
> | "foo" (_* as x)  -> foo x
> | "bar" (_* as x)  -> bar x
> | _*               -> raise Unrecognized

This is basically what I was looking for.

> This would be much nicer than using various regexp packages API, the
> real add-on being the variables in place of \1, \2 etc.

Precisely.

> ...
> 
> In fact such, an extension is probably feasible using camlp4 and this
> would probably be the best solution, to avoid extra-complexity in the
> compiler itself.

I really must get around to learning Camlp4. Why did no one 
teach it to me when I was at the X?

> In the end, do not hold your breath. I won't probably do that.
> But it can be a interesting project for a compiler course...
> 
> --Luc

;)

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

Re: [Caml-list] Pattern matching and strings

[Sven LUTHER]

On Fri, Oct 04, 2002 at 02:00:37PM +0200, Andreas Rossberg wrote:
> Sven Luther wrote:
> > 
> > On Wed, Oct 02, 2002 at 04:12:34PM +0200, Alessandro Baretta wrote:
> > > I have to do a little bit of pattern matching on strings. My
> > > first instict was to write something like the following.
> > >
> > > let foo x = ...
> > > let bar x = ...
> > > ... = function
> > > | "foo" ^ rest -> foo rest
> > > | "bar" ^ rest -> bar rest
> > > | _ -> raise Unrecognized
> > 
> > What about :
> > 
> > ... = function
> >   | str when String.sub str 0 3 = "foo" -> foo (String.sub str 2 (String.length str - 3))
> >   | str when String.sub str 0 3 = "bar" -> bar (String.sub str 2 (String.length str - 3))
> >   | _ -> raise Unrecognized
> > 
> > Sure, this code is not very optimal, i guess you could write a nicer
> > function which will test the string incrementally using just String.get
> > or something such, but i suppose it will do the thing you want.
> 
> The SML basis library provides the nice but often overlooked concept of
> substrings (or more generally, vector slices,
> http://SML.sourceforge.net/Basis/substring.html). Ported to Caml the
> Substring module would enable
> 
> > ... = function
> >   | s when Substring.is_prefix "foo" s -> foo (Substring.triml 3 s)
> >   | s when Substring.is_prefix "bar" s -> bar (Substring.triml 3 s)
> >   | _ -> raise Unrecognized
> 
> where your parsing functions operate on substrings instead of strings.
> Such an approach seems like a good compromise between use of a heavy
> regexp lib and inefficient repeated copying of parts of strings.

Well, like i said, it was just a quick implementation, but i am sure you
can do this more or less optimaly with a hand coded String.get using
comparison function. I don't know if you really can escape the use of
the final copying of the string though.

Friendly,

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