Loading ...
Sorry, an error occurred while loading the content.
 

Re: "ocaml_beginners"::[] Is it possible to get an instantiatable pattern matching?

Expand Messages
  • Stalkern 2
    ... 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
    Message 1 of 10 , Dec 31, 2004
      Code 17 wrote:
      > Pattern matching is one of the most powerful tools in functional languages
      > 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.
      >

      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.

      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
      you.
      "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
      datumType="strBoolFloatIntFloatFloatIntIntFloatStrIntIntBoolList"
      or
      datumType="aFunOnAFloatAndOnAIntAndIntAndString3ple"
      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
      strBoolFloatIntFloatFloatIntIntFloatStrIntIntBoolList
      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!

      Ernesto
    • code17
      Hi ... Yes, I agree that there are some type related problems in that. At least, there obviously should be some special pattern type that could handle every
      Message 2 of 10 , Jan 1, 2005
        Hi

        Yamagata Yoriyuki <yoriyuki@...> writes:

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

        Yes, I agree that there are some type related problems in that.
        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. :)

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

        Thanks for suggestion.
        This does give some freedom to the user, however, the actual tuning way
        here is "equal" not "matching". :)

        Thanks.

        >
        > --
        > Yamagata Yoriyuki
      • code17
        Hi Thanks for your very clear answer. I think you are right. To conclude a bit: 1) The reason why we can t manage to do this is that pattern is not first class
        Message 3 of 10 , Jan 1, 2005
          Hi

          Thanks for your very clear answer. I think you are right. To conclude a
          bit:

          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.

          Thanks

          "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
          > time.
          >
          > 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.
          >
          > andrew
          >
          >
        • code17
          Hi, thanks ... Although not a universal solution, this is quite an interesting hack working for some purposes. It does help in a way that the user writes and
          Message 4 of 10 , Jan 1, 2005
            Hi, thanks

            "ethan_aubin" <ethan.aubin@...> writes:
            > Mentally yes, but in Ocaml patterns are not first class, so
            > you cannot create a list of (pattern * values).
            >

            Although not a universal solution, this is quite an interesting hack
            working for some purposes. It does help in a way that the user writes
            and complements new pattern rules as OCAML pattern matching
            functions.

            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
            > http://www-staff.it.uts.edu.au/~cbj/Publications/chronological.html
            > for an idea what I'm talking about.
            >
            > -- ethan.aubin@...
            >
          • code17
            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. ... Yes, partly
            Message 5 of 10 , Jan 1, 2005
              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:
              >
              > 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.

              Yes, partly agree. But note that "matching" is more than just
              "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!


              -- code17
              >
              > 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
              > you.
              > "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
              > datumType="strBoolFloatIntFloatFloatIntIntFloatStrIntIntBoolList"
              > or
              > datumType="aFunOnAFloatAndOnAIntAndIntAndString3ple"
              > 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
              > strBoolFloatIntFloatFloatIntIntFloatStrIntIntBoolList
              > 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!
              >
              > Ernesto
              >
            • andrew cooke
              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
              Message 6 of 10 , Jan 1, 2005
                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
                order functions.

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

                cheers,
                andrew

                --
                ` __ _ __ ___ ___| |_____ 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
              Your message has been successfully submitted and would be delivered to recipients shortly.