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

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

[Alessandro Baretta]

Fred Smith wrote:
> Hi,
> 
> Instead of altering the language why not
> 
> type printerCommands = PrinterSetUnit | ...;;
> 
> and the function
> 
> match <scanning function> with
> | "\027(U\001\000\005" -> PrinterSetUnit
> | ... -> (* other cases *)
> | "" -> assert false
> 
> The rest of your program can then be independent of these bizarre strings.

Not really. I need to use these strings in a couple of 
different places, so I'd like to be able to define them only 
once, as constant identifiers, or aliases, and forget them 
entirely.

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] Again on pattern matching and strings

[Daniel de Rauglaudre]

[-- Attachment #1: Type: text/plain, Size: 1689 bytes --]

Hi,

Here attached, a proposition of Camlp4 standard syntax extension for
macros. The file is named "pa_macro.ml". To compile it do:
      ocamlc -pp camlp4r -I +camlp4 -c pa_macro.ml

To use it for a file "foo.ml", do:
   To compile:
       ocamlc -pp "camlp4o ./pa_macro.cmo" foo.ml
   To just pretty print the resulting source:
       camlp4o ./pa_macro.cmo pr_o.cmo foo.ml

The added statements are indicated in the beginning of the file
pa_macro.ml.

Keywords uppercase or lowercase?

I choosed to write the keywords in uppercase because I consider that
they must be visible in the source, just like the "#define" and other
"#ifdef" of C are visible, because of the "#" and because of the fact
that they are in the first column.

And I have considered also that in an expression, it is important
to differentiate "ifs" as conditional compilation and normal "ifs".

On Thu, Oct 24, 2002 at 03:16:24PM +0200, Basile STARYNKEVITCH wrote:

>    #ifdef WANT_DEBUG
>    #define DEBUGME(V) if (debugflag) printf("%d", V)
>    #else
>    #define DEBUGME(V) {}
>    #endif

With pa_macro.cmo, you can write it like this:

   IFDEF WANT_DEBUG THEN
     DEFINE DEBUGME(v) = if (debugflag) then printf("%d", v)
   ELSE
     DEFINE DEBUGME(v) = ()
   END

To define "WANT_DEBUG" you can either insert in the source:
   DEFINE DEBUGME

Or add "-DWANT_DEBUG" as option:
   camlp4o ./pa_macros.cmo pr_o.cmo -DWANT_DEBUG foo.ml
   ocamlc -pp "camlp4o ./pa_macros.cmo -DWANT_DEBUG" foo.ml

> 5. having the equivalent of __FILE__ and __LINE__ is very useful

Ok file __FILE__.
For __LINE__, it is complicated. I added __LOCATION__.

Any comments?

-- 
Daniel de RAUGLAUDRE
http://cristal.inria.fr/~ddr/

[-- Attachment #2: pa_macro.ml --]
[-- Type: text/plain, Size: 7171 bytes --]

(* camlp4r *)
(* $Id$ *)

(*
Added statements:

  At toplevel (structure item):

     DEFINE <uident>
     DEFINE <uident> = <expression>
     DEFINE <uident> (<parameters>) = <expression>
     IFDEF <uident> THEN <structure_items> END
     IFDEF <uident> THEN <structure_items> ELSE <structure_items> END
     IFNDEF <uident> THEN <structure_items> END
     IFNDEF <uident> THEN <structure_items> ELSE <structure_items> END

  In expressions:

     IFDEF <uident> THEN <expression> ELSE <expression> END
     IFNDEF <uident> THEN <expression> ELSE <expression> END
     __FILE__
     __LOCATION__

  As Camlp4 options:

     -D<uident>
     -U<uident>

  After having used a DEFINE <uident> followed by "= <expression>", you
  can use it in expressions *and* in patterns. If the expression defining
  the macro cannot be used as a pattern, there is an error message if
  it is used in a pattern.

  The expression __FILE__ returns the current compiled file name.
  The expression __LOCATION__ returns the current location of itself.

*)

#load "pa_extend.cmo";
#load "q_MLast.cmo";

open Pcaml;

type item_or_def 'a =
  [ SdStr of 'a
  | SdDef of string and option (list string * MLast.expr)
  | SdUnd of string
  | SdNop ]
;

value rec list_remove x =
  fun
  [ [(y, _) :: l] when y = x -> l
  | [d :: l] -> [d :: list_remove x l]
  | [] -> [] ]
;

value defined =
  ref [("OCAML_305", None); ("CAMLP4_300", None); ("NEWSEQ", None)]
;

value is_defined i = List.mem_assoc i defined.val;

value loc = (0, 0);

value subst mloc env =
  loop where rec loop =
    fun
    [ <:expr< if $e1$ then $e2$ else $e3$ >> ->
         <:expr< if $loop e1$ then $loop e2$ else $loop e3$ >>
    | <:expr< $e1$ $e2$ >> -> <:expr< $loop e1$ $loop e2$ >>
    | <:expr< $lid:x$ >> | <:expr< $uid:x$ >> as e ->
        try <:expr< $anti:List.assoc x env$ >> with
        [ Not_found -> e ]
    | <:expr< ($list:x$) >> -> <:expr< ($list:List.map loop x$) >>
    | <:expr< { $list:pel$ } >> ->
        let pel = List.map (fun (p, e) -> (p, loop e)) pel in
        <:expr< { $list:pel$ } >>
    | e -> e ]
;

value substp mloc env =
  loop where rec loop =
    fun
    [ <:expr< $e1$ $e2$ >> -> <:patt< $loop e1$ $loop e2$ >>
    | <:expr< $lid:x$ >> ->
        try <:patt< $anti:List.assoc x env$ >> with
        [ Not_found -> <:patt< $lid:x$ >> ]
    | <:expr< $uid:x$ >> ->
        try <:patt< $anti:List.assoc x env$ >> with
        [ Not_found -> <:patt< $uid:x$ >> ]
    | <:expr< $int:x$ >> -> <:patt< $int:x$ >>
    | <:expr< ($list:x$) >> -> <:patt< ($list:List.map loop x$) >>
    | <:expr< { $list:pel$ } >> ->
        let ppl = List.map (fun (p, e) -> (p, loop e)) pel in
        <:patt< { $list:ppl$ } >>
    | x ->
        Stdpp.raise_with_loc mloc
          (Failure
             "this macro cannot be used in a pattern (see its definition)") ]
;

value incorrect_number loc l1 l2 =
  Stdpp.raise_with_loc loc
    (Failure
       (Printf.sprintf "expected %d parameters; found %d"
          (List.length l2) (List.length l1)))
;

value define eo x =
  do {
    match eo with
    [ Some ([], e) ->
        EXTEND
          expr: LEVEL "simple"
            [ [ UIDENT $x$ -> Pcaml.expr_reloc (fun _ -> loc) 0 e ] ]
          ;
          patt: LEVEL "simple"
            [ [ UIDENT $x$ ->
                  let p = substp loc [] e in
                  Pcaml.patt_reloc (fun _ -> loc) 0 p ] ]
          ;
        END
    | Some (sl, e) ->
        EXTEND
          expr: LEVEL "apply"
            [ [ UIDENT $x$; param = SELF ->
                  let el =
                    match param with
                    [ <:expr< ($list:el$) >> -> el
                    | e -> [e] ]
                  in
                  if List.length el = List.length sl then
                    let env = List.combine sl el in
                    let e = subst loc env e in
                    Pcaml.expr_reloc (fun _ -> loc) 0 e
                  else
                    incorrect_number loc el sl ] ]
          ;
          patt: LEVEL "simple"
            [ [ UIDENT $x$; param = SELF ->
                  let pl =
                    match param with
                    [ <:patt< ($list:pl$) >> -> pl
                    | p -> [p] ]
                  in
                  if List.length pl = List.length sl then
                    let env = List.combine sl pl in
                    let p = substp loc env e in
                    Pcaml.patt_reloc (fun _ -> loc) 0 p
                  else
                    incorrect_number loc pl sl ] ]
          ;
        END
    | None -> () ];
    defined.val := [(x, eo) :: defined.val];
  }
;

value undef x =
  try
    do {
      let eo = List.assoc x defined.val in
      match eo with
      [ Some ([], _) ->
          do {
            DELETE_RULE expr: UIDENT $x$ END;
            DELETE_RULE patt: UIDENT $x$ END;
          }
      | Some (_, _) ->
          do {
            DELETE_RULE expr: UIDENT $x$; SELF END;
            DELETE_RULE patt: UIDENT $x$; SELF END;
          }
      | None -> () ];
      defined.val := list_remove x defined.val;
    }
  with
  [ Not_found -> () ]
;

EXTEND
  GLOBAL: expr str_item sig_item;
  str_item: FIRST
    [ [ x = macro_def ->
          match x with
          [ SdStr [si] -> si
          | SdStr sil -> <:str_item< declare $list:sil$ end >>
          | SdDef x eo -> do { define eo x; <:str_item< declare end >> }
          | SdUnd x -> do { undef x; <:str_item< declare end >> }
          | SdNop -> <:str_item< declare end >> ] ] ]
  ;
  macro_def:
    [ [ "DEFINE"; i = ident; def = opt_macro_value -> SdDef i def
      | "UNDEF"; i = ident -> SdUnd i
      | "IFDEF"; i = ident; "THEN"; d = str_item_or_macro; "END" ->
          if is_defined i then d else SdNop
      | "IFDEF"; i = ident; "THEN"; d1 = str_item_or_macro; "ELSE";
        d2 = str_item_or_macro; "END" ->
          if is_defined i then d1 else d2
      | "IFNDEF"; i = ident; "THEN"; d = str_item_or_macro; "END" ->
          if is_defined i then SdNop else d
      | "IFNDEF"; i = ident; "THEN"; d1 = str_item_or_macro; "ELSE";
        d2 = str_item_or_macro; "END" ->
          if is_defined i then d2 else d1 ] ]
  ;
  str_item_or_macro:
    [ [ d = macro_def -> d
      | si = LIST1 str_item -> SdStr si ] ]
  ;
  opt_macro_value:
    [ [ "("; pl = LIST1 LIDENT SEP ","; ")"; "="; e = expr -> Some (pl, e)
      | "="; e = expr -> Some ([], e)
      | -> None ] ]
  ;
  expr: LEVEL "top"
    [ [ "IFDEF"; i = ident; "THEN"; e1 = expr; "ELSE"; e2 = expr; "END" ->
          if is_defined i then e1 else e2
      | "IFNDEF"; i = ident; "THEN"; e1 = expr; "ELSE"; e2 = expr; "END" ->
          if is_defined i then e2 else e1 ] ]
  ;
  expr: LEVEL "simple"
    [ [ LIDENT "__FILE__" -> <:expr< $str:Pcaml.input_file.val$ >>
      | LIDENT "__LOCATION__" ->
          let bp = string_of_int (fst loc) in
          let ep = string_of_int (snd loc) in
          <:expr< ($int:bp$, $int:ep$) >> ] ]
  ;
  ident:
    [ [ i = UIDENT -> i ] ]
  ;
END;

Pcaml.add_option "-D" (Arg.String (define None))
  "<string> Define for IFDEF instruction."
;
Pcaml.add_option "-U" (Arg.String undef)
  "<string> Undefine for IFDEF instruction."
;

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

[Luc Maranget]

> > 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.
> 
> So, i suppose replacing all strings in a pattern matching by an integer
> pointing to hashtable or something would improve performance a lot if
> the same string is pattern matched over and over again ?
> 
> Friendly,

Indeed, but there are other possibilities, such as tries.
In the style
match x with
| "a" -> 1
| "ab" -> 2
| "abc" -> 3
| _ -> 4

===>

switch get_char 0 x with
| 'a' ->
   begin switch get_char 1 x with
   | eos -> 1 (* end of string ... *)
   | 'b' -> (switch get_char 2 x with ...)
   | _ -> 4
   end
| _ -> 4

Where switch operates on machine integers.

> 
> Sven Luther
> 


--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] Again on pattern matching and strings

[Sven Luther]

On Thu, Oct 24, 2002 at 03:24:26PM +0200, Luc Maranget wrote:
> > 
> > 
> > 
> > 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.

So, i suppose replacing all strings in a pattern matching by an integer
pointing to hashtable or something would improve performance a lot if
the same string is pattern matched over and over again ?

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] Again on pattern matching and strings

[Alessandro Baretta]

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

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

[Luc Maranget]

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

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

[Basile STARYNKEVITCH]

>>>>> "Daniel" == Daniel de Rauglaudre <daniel.de_rauglaudre@inria.fr> writes:

    Daniel> Hi, On Thu, Oct 24, 2002 at 11:50:46AM +0200, Stefano
    Daniel> Zacchiroli wrote:

    >> What about "DEFINE" / "UNDEF"?

    Daniel> There is already a Camlp4 syntax extension "pa_ifdef.cmo"
    Daniel> which adds "define" and "ifdef" (in lowercases). This is
    Daniel> more for conditional compilation.

Some thoughts on these macro issues.

1. I think it is extremly important to add the ability to have 
    expression macros
    pattern macros
    compile time flags (ifdef) for conditional compilation
   inside the same source file (also containing usual Ocaml code,
    perhaps using these extensions).

2.  There are cases where variadic macros could be useful. I know it is
     tricky to implement them.

3.  If it make Daniel's life easier, having different keywords to
    define expression macros, pattern macros, flags, could be ok, eg
    DEFEXPRMACRO DEFPATTERNMACRO 

4. mixing macros and flags is important in my opinion. I mean that in
   C it is usual to code

   #ifdef WANT_DEBUG
   #define DEBUGME(V) if (debugflag) printf("%d", V)
   #else
   #define DEBUGME(V) {}
   #endif

   I really would like compile flags & macros to be also mixable in
   Ocaml

5. having the equivalent of __FILE__ and __LINE__ is very useful

Above all, I really appreciate Camlp4 and do hope it will continue to
grow!

Regards.

-- 

Basile STARYNKEVITCH         http://starynkevitch.net/Basile/ 
email: basile<at>starynkevitch<dot>net 
alias: basile<at>tunes<dot>org 
8, rue de la Faïencerie, 92340 Bourg La Reine, France
-------------------
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] Again on pattern matching and strings

[Daniel de Rauglaudre]

Hi,

On Thu, Oct 24, 2002 at 11:50:46AM +0200, Stefano Zacchiroli wrote:

> What about "DEFINE" / "UNDEF"?

There is already a Camlp4 syntax extension "pa_ifdef.cmo" which adds
"define" and "ifdef" (in lowercases). This is more for conditional
compilation.

In C macros, you have the two system with the same #define directive:
   #define FOO
   #define FOO(x) (...)

The first form suggests that you are going to do a conditional compilation
somewhere with #ifdef or #ifndef (and you can do it also in the command
line by -DFOO: the pa_ifdef.cmo Camlp4 extension adds also this option
-D).

The second form suggests that you are going to do a macro substitution.

Is is a good idea to follow the same idea in Camlp4 macros?
I.e. having one construction for both cases? I don't know.
I think it is possible, but perhaps a little bit tricky.
Does anybody have an opinion?

-- 
Daniel de RAUGLAUDRE
http://cristal.inria.fr/~ddr/
-------------------
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] Again on pattern matching and strings

[Daniel de Rauglaudre]

Hi,

On Thu, Oct 24, 2002 at 02:34:00PM +0200, Alessandro Baretta wrote:
> 
> Does "evaluated at parse time" mean that you define a syntax 
> tree transformation as opposed to a character stream 
> transformation?

Right. The general idea of Camlp4, anyway, is manipulation of
syntax tree. Every syntax extension work with syntax trees, not
character stream.

The extension DEFMACRO or DEFINE, which I propose to add in Camlp4,
uses correct syntax trees. The syntax of this construction uses the
normal lexing and parsing of OCaml expressions. The substitutions of
possible parameters will be scans of the syntax trees and tree
substitution.

(Virtual) Example:

   DEFMACRO f(x) (x, x)
   f(3+y)
   function f(2) -> 0

would be interpreted as:
   (3+y, 3+y)
   function (2, 2) -> 0

We may be interested in "inlining" with this system: but in this
case, if we accept any expression, it would not work in pattern
position. Example:
   DEFMACRO f(x) (x+3)
   f(2)
would be interpreted as:
   2+3
but
   function f(2) -> 0
has no meaning.

> This is more or less what I had in mind. The only problem 
> with this scheme is probably with compile-time error 
> reporting. If this is not somehow linked with the compiler, 
> how will the compiler be able to tell us that that something 
> we wrote makes no sense?

Indeed if the macro is a complicated expression, the typing error
might be difficult to understand. As location, I can only underline
all the macro call:

   DEFMACRO f(x) (x, "hello")
   function
     (x, y) -> (x + 2, y + 5)
   | f(3) -> (22, 35)
     ^^^^
This pattern has type string and is used with type int.

Something like that...

-- 
Daniel de RAUGLAUDRE
http://cristal.inria.fr/~ddr/
-------------------
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] Again on pattern matching and strings

[Alessandro Baretta]

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.

Alex Baretta

-------------------
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] Again on pattern matching and strings

[Alessandro Baretta]

Daniel de Rauglaudre wrote:
> Hi,
> 
> In this case, the <ident> is added as keyword in the grammar,
> evaluated at parse time, transformed into the <expression/pattern>
> depending on its position. The possible parameters are possibly
> substituted by their actual value in the expression pattern.

Does "evaluated at parse time" mean that you define a syntax 
tree transformation as opposed to a character stream 
transformation? I ask because I'd like this scheme to avoid 
the bug-prone interactions between C macros and surrounding 
code.

> ...We can have also:
>      UNDEFMACRO <ident>
> 
> To remove it from the grammar.

This is more or less what I had in mind. The only problem 
with this scheme is probably with compile-time error 
reporting. If this is not somehow linked with the compiler, 
how will the compiler be able to tell us that that something 
we wrote makes no sense? If the macro is small and self 
evident, this might not be a problem, but if you use such 
macros to match, for example, the Epson ESC/P command set, 
drawing a connection between a compiler error--reported with 
reference to the pure Caml syntax tree--and the 
CamlP4-extended source code might be difficult.

In all other respects, this approach seems to be satisfactory.

> Would it be OK? General enough? Other propositions?
> 


Thank you,
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] Again on pattern matching and strings

[Noel Welsh]

--- Stefano Zacchiroli <zack@cs.unibo.it> wrote:
> What about "DEFINE" / "UNDEF"?
> 
> The first is more C-like and macro substitution is
> really a C-like construct.

Macros by textual substitution is a C concept.  Macros
by expression substitution come from Lisp; hence the
defmacro.  Lisp macros have a long and glorious
history and are still an active research topic.  A
recent paper (presented scarcely 4 weeks ago) is

  http://www.cs.utah.edu/plt/publications/macromod.pdf

It should provide enought references for the
interested scholar to assess the current state of the
art.

Noel



__________________________________________________
Do you Yahoo!?
Y! Web Hosting - Let the expert host your web site
http://webhosting.yahoo.com/
-------------------
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] Again on pattern matching and strings

[Stefano Zacchiroli]

On Thu, Oct 24, 2002 at 10:51:36AM +0200, Daniel de Rauglaudre wrote:
> Would it be OK? General enough? Other propositions?

What about "DEFINE" / "UNDEF"?

The first is more C-like and macro substitution is really a C-like
construct.
For the other one ("UNDEF") I don't know if cpp have a macro to undefine
macros, but ... it seems to me a good choice, also "UNDEFINE" can be
good but it's a bit too verbose for my personal taste.

Cheers.

-- 
Stefano Zacchiroli - undergraduate student of CS @ Univ. Bologna, Italy
zack@cs.unibo.it | ICQ# 33538863 | http://www.cs.unibo.it/~zacchiro
"I know you believe you understood what you think I said, but I am not
sure you realize that what you heard is not what I meant!" -- G.Romney
-------------------
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] Again on pattern matching and strings

[Daniel de Rauglaudre]

Hi,

On Thu, Oct 24, 2002 at 09:43:53AM +0200, Alessandro Baretta wrote:
> 
> So yes: CamlP4 can do it. Since I don't want to reinvent the wheel,
> has anyone written--and documented for the syntax laymen--such an
> extension?

I have been thinking to implement that. Proposing a syntax extension
to make macros with Camlp4 (in this case, you don't have to write
Camlp4 code, but just use the extension file). I propose that syntax:
     DEFMACRO <ident> <(optional-parameters)> = <expression/pattern>

where <expression/pattern> is input text which can be interpreted as
expression or pattern (variables, constants, constructors, records).

In this case, the <ident> is added as keyword in the grammar,
evaluated at parse time, transformed into the <expression/pattern>
depending on its position. The possible parameters are possibly
substituted by their actual value in the expression pattern.

We can have also:
     UNDEFMACRO <ident>

To remove it from the grammar.

Would it be OK? General enough? Other propositions?

-- 
Daniel de RAUGLAUDRE
http://cristal.inria.fr/~ddr/
-------------------
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] Again on pattern matching and strings

[Jacques Garrigue]

From: Alessandro Baretta <alex@baretta.com>
> Stefano Zacchiroli wrote:
> > What about:
> > 
> >   | Some m when m = printer_set_unit -> ...
> >   | Some m when m = printer-reset -> ...
> >   | Some m when m = printer_formfeed -> ...
> >   ...
> >   | Some (_) -> assert false
> >   | None -> ()
> > 
> > It isn't so bad ...
> 
> Eh, no! This is really unacceptable as a general solution. 
> Of course, I could have coded my function this way, but this 
> technique is not scalable, especially from the perspective 
> of computational efficiency. Your code is compiled as a 
> sequence of comparisons on a strings. Hence, the matched 
> string is scanned once for every pattern. With constant 
> patterns, on the other hand, the compiler should scan the 
> string only once and jump to appropriate code. This is more 
> compact, but not necessarily more efficient, as Jacques 
> pointed out a while ago.
> ( http://caml.inria.fr/archives/200101/msg00111.html )

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:
# function Some s when s = a -> 0 | Some s when s = b -> 1
  | Some s when s = c -> 2 | Some _ -> assert false | None -> 3;;
(let
  (a/64 (apply (field 0 (global Toploop!)) "a")
   b/65 (apply (field 0 (global Toploop!)) "b")
   c/66 (apply (field 0 (global Toploop!)) "c"))
  (function param/73
    (if param/73
      (let (s/70 (field 0 param/73))
        (if (string_equal s/70 a/64) 0
          (if (string_equal s/70 b/65) 1
            (if (string_equal s/70 c/66) 2
              (raise
                (makeblock 0 (global Assert_failure/26g) [0: "" 94 106]))))))
      3)))
- : string option -> int = <fun>

So efficiency is actually not a reason to avoid this style...
(Verbosity may be one.)

   Jacques Garrigue
-------------------
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] Again on pattern matching and strings

[Alessandro Baretta]

Olivier Andrieu wrote:
>  Alessandro Baretta [Thursday 24 October 2002] :
>  > I write this message because I would like to know what kind 
>  > of complications would need to be added to the compiler to 
>  > make the above trick work.
> 
> None ! You can do it with camlp4 ! Unless I'm mistaken, what's
> described there :
> <http://caml.inria.fr/camlp4/tutorial/tutorial007.html#toc49> seems
> to apply to your case.

Ah, woe is me! I put ashes on my head. I do not understand 
the example, but yes, what I am asking for is essentially, a 
substitution of constant expressions for their alias in the 
syntax tree of the program. So yes: CamlP4 can do it. Since 
I don't want to reinvent the wheel, has anyone written--and 
documented for the syntax laymen--such an extension?

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] Again on pattern matching and strings

[Stefano Zacchiroli]

On Thu, Oct 24, 2002 at 09:10:15AM +0200, Alessandro Baretta wrote:
> Eh, no! This is really unacceptable as a general solution. 
> Of course, I could have coded my function this way, but this 
> technique is not scalable, especially from the perspective 
> of computational efficiency. Your code is compiled as a 

Yes, but your mail, expecially the part I quoted, complained about
elegancy of the code, not about efficiency.

> >Anyway from a more general point of view I'm also interested in seeing
> >"aliasing" or constant definition in the compiler, it is of general
> >interest, not only in pattern matching.
> 
> To my great surprise, I'm unable to think of an example 
> relating to anything other than pattern matching.

For example: the classic magic numbers problem used in almost all
programs, for example a global variable "debug" which can be safely a
constant (or an alias as you called it) instead of a global "let val".

Cheers.

-- 
Stefano Zacchiroli - undergraduate student of CS @ Univ. Bologna, Italy
zack@cs.unibo.it | ICQ# 33538863 | http://www.cs.unibo.it/~zacchiro
"I know you believe you understood what you think I said, but I am not
sure you realize that what you heard is not what I meant!" -- G.Romney
-------------------
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] Again on pattern matching and strings

[Alessandro Baretta]

Stefano Zacchiroli wrote:
> On Thu, Oct 24, 2002 at 01:47:33AM +0200, Alessandro Baretta wrote:
> 
>>| Some ( "\027(U\001\000\005" ) -> ...
>>| Some ( "\027@" ) -> ...
>>| Some ( "\012" ) -> ...
> 
> 
> What about:
> 
>   | Some m when m = printer_set_unit -> ...
>   | Some m when m = printer-reset -> ...
>   | Some m when m = printer_formfeed -> ...
>   ...
>   | Some (_) -> assert false
>   | None -> ()
> 
> It isn't so bad ...

Eh, no! This is really unacceptable as a general solution. 
Of course, I could have coded my function this way, but this 
technique is not scalable, especially from the perspective 
of computational efficiency. Your code is compiled as a 
sequence of comparisons on a strings. Hence, the matched 
string is scanned once for every pattern. With constant 
patterns, on the other hand, the compiler should scan the 
string only once and jump to appropriate code. This is more 
compact, but not necessarily more efficient, as Jacques 
pointed out a while ago.
( http://caml.inria.fr/archives/200101/msg00111.html )

> Anyway from a more general point of view I'm also interested in seeing
> "aliasing" or constant definition in the compiler, it is of general
> interest, not only in pattern matching.

To my great surprise, I'm unable to think of an example 
relating to anything other than pattern matching.

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] Again on pattern matching and strings

[Christopher Quinn]

Alessandro Baretta wrote:
> 
> I write this message because I would like to know what kind of 
> complications would need to be added to the compiler to make the above 
> trick work.
> 
> Alex

there is John Reppy's Abstract Value Constructors (no weblink found but i have the paper).

example syntax:
const K = <some pattern>
const K(a,b) = <pattern with holes a&b>

i have a patch but its against 3.01.
the main problem is that making a constant abstract via a signature means referencing it incurs an unavoidable function call (under the bonnet), which is mightily inefficient compared to the usual compiled match. in effect the client code gets the module containing the definition to do the pattern matching for it. 
of course, to retain efficiency simply don't bother with an mli on modules containing const definitions! (or internal signatures) 
since separate compilation is then lost this would be an argument against such a practice. but it is no worse a situation than variant constructors in a signature file because in that case no change can be made to the definition in the implementation file that does not require having to do the same in the interface file. hence re-compilation of all dependent code.
a practical approach to minimise the effect of this is to put one's constant definitions into their own .ml file (ie. no other values that might have dependents in addition to those of the constants)

but a final solution to this might be a similar one to work on functor elimination(?) - develop conscientiously with abstracted modules, but then do a final recompilation that ignores abstraction and inlines constants, for efficiency sake.

in any case the patch includes a compiler switch to 
turn off signature coercion, by which i mean any present signature is properly matched against the implementation as normal but is discarded afterwards in favour of whatever the compiler inferred for the implementation itself. result: inlined constants in the presence of signature abstraction.
this is largely untested, is definitely incomplete with respect to functors, and likely to cause the typechecker to complain in certain situations (not constraining a type as intended by sig.)

also i think i neglected to sort out the case of ocamlopt when a signature defines a different order for values than they actually occur in the implementation (a coercion issue).

there is another minor limitation with respect to functors but otherwise named patterns work as expected.

- chris

-------------------
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] Again on pattern matching and strings

[Stefano Zacchiroli]

On Thu, Oct 24, 2002 at 01:47:33AM +0200, Alessandro Baretta wrote:
> | Some ( "\027(U\001\000\005" ) -> ...
> | Some ( "\027@" ) -> ...
> | Some ( "\012" ) -> ...

What about:

  | Some m when m = printer_set_unit -> ...
  | Some m when m = printer-reset -> ...
  | Some m when m = printer_formfeed -> ...
  ...
  | Some (_) -> assert false
  | None -> ()

It isn't so bad ...

Anyway from a more general point of view I'm also interested in seeing
"aliasing" or constant definition in the compiler, it is of general
interest, not only in pattern matching.

Cheers.

-- 
Stefano Zacchiroli - undergraduate student of CS @ Univ. Bologna, Italy
zack@cs.unibo.it | ICQ# 33538863 | http://www.cs.unibo.it/~zacchiro
"I know you believe you understood what you think I said, but I am not
sure you realize that what you heard is not what I meant!" -- G.Romney
-------------------
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] Again on pattern matching and strings

[Alessandro Baretta]

Gentlemen,

Let me discuss one further aspect of pattern matching, which 
relates to matching strings.

I am writing an Epson ESC/P printer driver from a text 
formatter I wrote. I have come across the need to scan 
buffers of printer commands to post process them before 
actually sending them to the printer. Since printer commands 
tend to get rather complex to write I have thought that a 
very natural way to make my program more readable would be 
to define identifiers to stand for such commands. Here's an 
example.

let printer_set_unit = "\027(U\001\000\005"

This commands sets the unit of measurement for subsequent 
commands to 5/3600 in.

I also have a scanning function which returns a string 
option, which either contains None, if no printer command is 
recognized, or Some(s) where an ESC/P command is recognized.

I want to use pattern matching on the result of my string 
scanning to determine what to do depending on the command 
identified by the scanner. Intuitively, I wrote the 
following, which is obviously wrong.

match <scanning function> with
| Some ( printer_set_unit ) -> ...
| Some ( printer_reset ) -> ...
| Some ( printer_formfeed )   -> ...
...
| Some (_) -> assert false
| None -> ()

Naturally, this does not work, because instead of evaluating 
  printer_set_unit, printer_set_pagesize and 
printer_formfeed and defining patterns based on these, the 
compilers redefines the identifiers based on the matched 
string in the local scope. But this leaves me no alternative 
to writing
match ... with
| Some ( "\027(U\001\000\005" ) -> ...
| Some ( "\027@" ) -> ...
| Some ( "\012" ) -> ...

And so on. This is completely unreadable. I think this 
problem requires a solution like C++ const variables: values 
which the compiler considers compile time constants and 
directly substitutes into the code in place of the 
identifier name. Now, "const" is rather meaningless in a 
functional language, so I suggest "alias" as a better 
alternative. For example

alias printer_set_unit = "\027(U\001\000\005"

whereby such an identifier cannot be hidden by a new let 
binding (compile-time error) and is considered a constant in 
patterns.

If the compiler allowed the aliasing of constant expressions 
with an identifier, the above pattern matching would make 
sense. Of course, such a technique also applies to other 
cases as well, besides programming Epson printer drivers. In 
general, any pattern matching where complex constant 
patterns are used would benefit from this feature, for the 
programmer would be able to write a better readable code.

I write this message because I would like to know what kind 
of complications would need to be added to the compiler to 
make the above trick work.

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] Again on pattern matching and strings

[Alexander V.Voinov]

Hi Alessandro,

From: Alessandro Baretta <alex@baretta.com>
Subject: [Caml-list] Again on pattern matching and strings
Date: Thu, 24 Oct 2002 01:47:33 +0200

> | Some ( "\027(U\001\000\005" ) -> ...
> | Some ( "\027@" ) -> ...
> | Some ( "\012" ) -> ...
> 
> And so on. This is completely unreadable. I think this 
> problem requires a solution like C++ const variables: values 
> which the compiler considers compile time constants and 
> directly substitutes into the code in place of the 
> identifier name. Now, "const" is rather meaningless in a 
> functional language, so I suggest "alias" as a better 
> alternative. For example
> 
> alias printer_set_unit = "\027(U\001\000\005"
> 
> whereby such an identifier cannot be hidden by a new let 
> binding (compile-time error) and is considered a constant in 
> patterns.

You can use camlp4 for this. One of the entry level examples
concern introduction of named constants. 

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