Re: "ocaml_beginners":: Is it possible to get an instantiatable pattern matching?
- Code 17 wrote:
> Pattern matching is one of the most powerful tools in functional languagesAs far as I can read in this message, your _pattern_ is a key for a
> like OCaml. Based on a general form of pattern matching
> let pattern_fun x =
> match x with
> pattern_1 -> value_1
> | pattern_2 -> value_2
> | default_pattern -> default_value
> We can see that pattern rules can be abstracted as a list of (pattern * value).
> In most common cases, we can just write fixed patterns and associated values
> (or actions) to get the functionality we need. However, in some other cases,
> we probably want a generic pattern matching to be instantiated by matching rules
> provided by some USER data, e.g. provided a user defined data structure of
> type (pattern * value) list, then return the instantiated pattern
> matching function
> above. I think this is the situation in many applications.
_value_ and you search a value by its key using the _pattern_fun_,
that _is aware of some specific associations between a key and a value,
_and provides a way to query these associations by key.
One point: I would not start with a function crushing together both the
data and the access method. Look at the Hashtable module to see what I
mean: functions for managing hashtables (or whatever) are built
regardless of the data that you'll use them for, and the type of the
data that they can work with is defined as widely as possible so start
with polymorphic multi-mighty powers ;-)
And so far, IMHO you don't need to knock at the type inference of Ocaml
and ask it to come out to the user, thus asking him/her to program for
"Structures" are also "data" until they are brought to life, so in short
your user has to provide you with DATA, and maybe a few META-DATA. I
mean, you should have a little idea about what your user would
reasonably want to do, and succeed in making the task easier, otherwise
why not ask the user to program by himself/herself? So I assume that
you'd not really need to unleash the power of Ocaml over the user and
choke him/her, but to create a little filter for letting the user do the
right things without too much overkill. In a place like Ocaml where the
functions themselves can be passed as arguments, a user filter like that
does not seems too difficult if your purpose is basically to allow the
storage and retrieval of typed data.
( Again: if your purpose is to let the user know Ocaml so well that
he/she could explain it to you, please remember to ask him/her also to
join the Ocaml Beginners' list ;-)) )
In a production environment, what you would do could be as simple as
telling the user that you use a set of types, defined e.g. as you would
define lexing tokens in ocamllex - so for instance tell the user that
you'll consider 1 as an integer and 1. like a float. Fair enough, isn't
it? This would not require writing a book named "My Obscure Input
Interfaces for dummies". When types will get more complex, like
you'll just add some docs or some GUI enhancements.
Then you get everything as string, well, values and meta-values, I mean
strings that you can examine and assign to other types, of any
complexity, shall they be basic or functional. You parse your input, in
any way (regexps, Scanf, CAMLP4, ASTs, Ocamllex/ocamlyacc) and that's it.
If you expect the user to be not always able to provide you with a
(str * bool * float * int * float * float * int * int * float * str *
int * int * bool ) list,
use option types and write guards for the case of missing items.
And if you like the sorcery of linearizing, you can take a look at the
fruits of the Marshal module as well... where everything ends with being
a string-like thing.
Hope this helps
BTW - Happy New Year to everybody!
Yamagata Yoriyuki <yoriyuki@...> writes:
> Hi,Yes, I agree that there are some type related problems in that.
> From: Code 17 <code17@...>
> Subject: "ocaml_beginners":: Is it possible to get an instantiatable pattern matching?
> Date: Fri, 31 Dec 2004 14:09:44 +0100
> Your mechanism in its general form breaks the type checking. There is
> no way for the compiler to know what type will be accepted to a
> runtime-generated pattern.
At least, there obviously should be some special pattern type that
could handle every possible typed patterns being provided before this
mechanics could hold. This could (or not) be done by the ocaml
compiler. It's just interesting to know whether it is possible to make
pattern as first class value now or in the future. :)
>Thanks for suggestion.
> However, for the simple case, you can use "when" clauses for the
> similar effects.
> let today = 31
> match date with
> (today', this_month', this_year') when today' = today ... ->
> <do something>
This does give some freedom to the user, however, the actual tuning way
here is "equal" not "matching". :)
> Yamagata Yoriyuki
Thanks for your very clear answer. I think you are right. To conclude a
1) The reason why we can't manage to do this is that pattern is not first
class value in OCaml
2) The reason why we can't try do some hacks to archive this DIRECTLY is
that all elements appear on the left side of pattern rules are either
constants or LOCAL variables. No way for importing user defined
patterns on the left side (see also the suggestion by ethan aubin, in
which the user defined data imported in the right side, so it has
to be itself a pattern matching function)
3) Two possible solutions suggested by you (and also the only ways I
could think of):
1. Out of the system
which means generate the final OCaml pattern matching source
according to the user data each time and then compile.
2. Implement the pattern matching internally by oneself
this doesn't means one can get a generic pattern matching similar
to the OCaml one but generic. It just takes rules and produces the
FINAL function of pattern matching mechanics inside.
Thank you for all these.
ps: I'm a little interested in the implementation of pattern matching.
If I just want to manually implement some pattern matching mechanics in
OCaml by hand, what kind of literature or source code do you suggested
to read? The OCaml compiler source could probably be nice, but I'm not
sure whether the pattern matching function is written in OCaml or
belongs to the core part written in C.
"andrew cooke" <andrew@...> writes:
> the pattern introduces variables (like a "let") so it has a semantics that
> can't just be "pulled out" of the ocaml source and put in a tuple. at
> least, i don't know of any way to do so. i believe this is related to
> issues with the kind of type system used. see below.
> i'll describe a similar problem and how i handled it:
> i am implementing (in ocaml) an interpreter for a simple language which
> includes pattern matching. if i could do what you suggest then i could
> use this to "pass through" the pattern matching to ocaml. instead, i have
> to take the parse tree of my language and implement that pattern matching
> myself (which is itself a kind of parsing), with a hashtable to associate
> values to variables. in this way i implement pattern matching at run
> i can also "cross compile" programs written in my language to ocaml
> cource. in this case i take the parse tree and use it to generate ocaml
> code. then i can generate "match" statements directly that do the pattern
> matching for me. however, this ocaml code then has to be compiled.
> so my two solutions are either to reproduce the functionality myself, or
> get the ocaml compiler to do it for me. it may be that the second of
> these can be done dynamically - it is not a problem for me to have a
> two-stage process, so i haven't looked at this.
> there is a problem related to types in all this - i don't know enough
> theory to be certain, but i would guess it requires dependent types to
> work properly. to get a glimpse of the problem note that my translation
> code may compile (ie not contain type errors), but when i run it i may
> generate ocaml code which *does* contain errors (if i have incorrect logic
> in my cross-compiler, say). so if this process all occurred dynamucally
> at runtime, then you would get type errors (from the "compilation"). this
> contradicts the idea that a ocaml program is type safe.
> this is a bit rambling and may be incorrect - i'm as interested as you to
> hear a clearer answer.
- Hi, thanks
"ethan_aubin" <ethan.aubin@...> writes:
> Mentally yes, but in Ocaml patterns are not first class, soAlthough not a universal solution, this is quite an interesting hack
> you cannot create a list of (pattern * values).
working for some purposes. It does help in a way that the user writes
and complements new pattern rules as OCAML pattern matching
The advantage is it gives freedom to other part of the program (e.g. the
parts defined by user). The disadvantage is that the user has to program
in OCaml, which is in fact what we want to avoid in some cases and
also the reason why we want a configurable pattern matching, otherwise
why don't we just ask the user give a OCaml pattern-matching
function. This happens especially in the case when we program an
interpreter for other language using OCaml.
Anyway, this does help. I'm a beginner of OCaml. I didn't even notice
the polymorphic variants feature without your post. It appears in the
last part of the OReilly book which I didn't reach yet. :)
But now I got there, Thanks.
> In the case of polymorphic variants, something like this can
> be accomplished:
> let print_none (empty : [> ]) =
> print_string "<unknown polymorphic variant>"
> let print_built_ins ~print_others x = match x with
> | `Int(x) -> print_int x
> | `String(s) -> print_string s
> | _ -> print_others x
> (* The user supplied (pattern, value) list, as a function *)
> let print_user_types x = match x with
> | `Person(name,age) -> print_string name; print_int age
> | _ -> print_none x
> let print_all = print_built_ins ~print_others:print_user_types;;
> I would be very interesting in generic pattern matching for
> things like records or objects. First class labels, anyone?
> For an even more esoteric challenge, is there an idiom to
> pattern match according to the structure of datatypes in
> Ocaml, (something like generic programming with arbitrary
> data structures). See 'The Pattern Calculus' at
> for an idea what I'm talking about.
> -- ethan.aubin@...
- Hi, thanks
I'm not sure I've caught your meaning totally (I'm oriental :) ), but
thanks for the long post. I will try to answer as I can.
Stalkern 2 <stalkern2@...> writes:
>Yes, partly agree. But note that "matching" is more than just
> As far as I can read in this message, your _pattern_ is a key for a
> _value_ and you search a value by its key using the _pattern_fun_,
> that _is aware of some specific associations between a key and a value,
> _and provides a way to query these associations by key.
"searching" as well as "pattern" can not just be considered as
"key". To implement a "key searching" is just easy, but to implement
pattern matching mechanics as powerful as the one provided by OCaml
definitely needs more. However, this is not an important point.
My original intention is that I need some instantiatable pattern
matching, however, I can't directly use the very powerful matching
mechanics already provided in OCaml, instead, I have to re-implement it
by myself which seems a bit wasteful. (This could be annoying problems in
some cases, especially when implementing a language interpreter with
pattern matching features as in andrew cooke's post, you just feel
annoying that you can't directly use the already provided one by OCaml
but have to code it manually.)
As far as I could understand from the remain part of your post, you
suggested to parser it outside of the main program and get the final
OCaml matching I need. I totally agree that this could be done, as in my
reply to andrew cooke. This is the "can do" solution, however, all
repliers here seem also interested in that whether a generic patterns
mechanics could be possibly achieved.
Thanks you very much and A Happy New Year to Everyone!
It seems a right choice for me to post here instead of the official OCaml
list, where I'm afraid my question would be considered naive :( Just
feel happy to get so many warm hearted answers here. That's really nice!
> One point: I would not start with a function crushing together both the
> data and the access method. Look at the Hashtable module to see what I
> mean: functions for managing hashtables (or whatever) are built
> regardless of the data that you'll use them for, and the type of the
> data that they can work with is defined as widely as possible so start
> with polymorphic multi-mighty powers ;-)
> And so far, IMHO you don't need to knock at the type inference of Ocaml
> and ask it to come out to the user, thus asking him/her to program for
> "Structures" are also "data" until they are brought to life, so in short
> your user has to provide you with DATA, and maybe a few META-DATA. I
> mean, you should have a little idea about what your user would
> reasonably want to do, and succeed in making the task easier, otherwise
> why not ask the user to program by himself/herself? So I assume that
> you'd not really need to unleash the power of Ocaml over the user and
> choke him/her, but to create a little filter for letting the user do the
> right things without too much overkill. In a place like Ocaml where the
> functions themselves can be passed as arguments, a user filter like that
> does not seems too difficult if your purpose is basically to allow the
> storage and retrieval of typed data.
> ( Again: if your purpose is to let the user know Ocaml so well that
> he/she could explain it to you, please remember to ask him/her also to
> join the Ocaml Beginners' list ;-)) )
> In a production environment, what you would do could be as simple as
> telling the user that you use a set of types, defined e.g. as you would
> define lexing tokens in ocamllex - so for instance tell the user that
> you'll consider 1 as an integer and 1. like a float. Fair enough, isn't
> it? This would not require writing a book named "My Obscure Input
> Interfaces for dummies". When types will get more complex, like
> you'll just add some docs or some GUI enhancements.
> Then you get everything as string, well, values and meta-values, I mean
> strings that you can examine and assign to other types, of any
> complexity, shall they be basic or functional. You parse your input, in
> any way (regexps, Scanf, CAMLP4, ASTs, Ocamllex/ocamlyacc) and that's it.
> If you expect the user to be not always able to provide you with a
> i.e. a
> (str * bool * float * int * float * float * int * int * float * str *
> int * int * bool ) list,
> use option types and write guards for the case of missing items.
> And if you like the sorcery of linearizing, you can take a look at the
> fruits of the Marshal module as well... where everything ends with being
> a string-like thing.
> Hope this helps
> BTW - Happy New Year to everybody!
- pattern matching can be implemented using recursive descent parsing, which
is described in cousineau and mauny (using ocaml!).
the idea is that you want to construct a function that takes some
structure and either performs an action (binding values to names in a
hashtable) or "fails". if you use explicit state (pure functional
programming) you can backtrace on failure and try alternative patterns
quite easily. and it turns out that you can do all this using higher
the data you are matching is read from a stream. streams are a lot like
lists, with a head and tail operation. so you take the head of the
stream, see if you can match it and, if so, pass the tail on to the next
bit of matching. if not, you return None and something else gets a chance
to match the stream.
i was going to post an explanation in more detail, but i'm realising that
it's quite some work! search around for "recursive descent" "parsing"
"streams" and try cousineau + mauny. there's also some info at around
page 110 of the ocaml book (developing applications...)
warning - i think both c&m and the ocaml book use ocaml's own streams.
i've not used those and they may behave slightly different to the model i
have in my head, but i've hardly given any details here so i doubt there's
an important contradiction.
i'd really encourage you to learn about this stuff - i found it took a
while to understand, but once i actually implemented the code myself, it
made sense and has been one of the most useful things i've ever learnt in
` __ _ __ ___ ___| |_____ work web site: http://www.ctio.noao.edu/~andrew
/ _` / _/ _ \/ _ \ / / -_) personal web site: http://www.acooke.org/andrew
\__,_\__\___/\___/_\_\___| list: http://www.acooke.org/andrew/compute.html