[Caml-list] recursive modules redux, & interface files

[Caml-list] recursive modules redux, & interface files

[Chris Hecker]

Two questions/problems:

1.  So, I understand that doing recursive types across modules is hard (but I'd say very important for decoupling large software), but is it true that I can't even call across modules recursively?  Even with mli files to resolve the types?  I find that incredibly hard to believe, but I can't get it to work and it seems the docs say it's impossible as well (so why am I posting about it, you ask?  Disbelief that it's not possible, I guess. :).

What is the point of separate mli files if they can't be used to declare a callable interface separate from the implementation?  Is this just a small feature that needs to be added to the linker (defer binding unseen modules until all the object files have been seen), or is there something really subtle going on?  Since everything compiles and type checks fine, and the subtleties that I don't understand in ocaml usually have to do with the type checker, I'm having trouble seeing how this could be that hard.  Example below.  Am I missing something?

2. Also, on a related note, why do the interface file and the implementation file (or equivalently, I believe, the signature and structure) both have to have all the concrete types duplicated?  I can see the value of having interfaces that hide some implementation stuff and abstract types, but if I've got a big fully-specified variant type in a .mli file, it's annoying and error prone (yes, I know the compiler will catch it) to have to retype the whole thing into the ml file (which I have to do if I want to hide anything else in the ml file, meaning I can't just have an ml without an mli).  Is this something the "include" keyword takes care of?  Heck, "#include<foo.mli>" would be an improvement over duplicating all the types. :)  One of the things I hate about C++ and is having to type function declarations/definitions multiple times.

Thanks,
Chris

---------
Example for Question 1:

--- t1.mli ---
val foo: int -> int
--- t1.ml ---
let foo x = if x = 1 then T2.bar x else x
--- t2.mli ---
val bar: int -> int
--- t2.ml ---
let bar x = if x = 2 then T1.foo (x-1) else x
--- main.ml ---
let _ = print_int (T2.bar 2)

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Brian Rogoff]

On Sun, 18 Mar 2001, Chris Hecker wrote:
> Two questions/problems:

Just one answer/solution I'm afraid, but I also give a grotesque
workaround...

> 2. Also, on a related note, why do the interface file and the
> implementation file (or equivalently, I believe, the signature and
> structure) both have to have all the concrete types duplicated?  I can
> see the value of having interfaces that hide some implementation stuff
> and abstract types, but if I've got a big fully-specified variant type
> in a .mli file, it's annoying and error prone (yes, I know the compiler
> will  catch it) to have to retype the whole thing into the ml file
> (which I have to do if I want to hide anything else in the ml file, meaning I
> can't just have an ml without an mli).  Is this something the
> "include" keyword takes care of?  

No, but if you are finding this really onerous then you can use "open" by 
creating a "pure" mli file with your gignatic variant type and opening it 
in the mli and ml file where it is needed. Does that help?

-- Brian

PS : There are some ways to get around the fact that the linker requires
     ordering, either by putting the mutually recursive functions in the 
     same module (I assume you know this) or by breaking the cycle with 
     an indirection (first rule of programming: any problem can be solved
     with another level of indirection :-). In this case, the indirection
     can be provided by passing in functions to foo and bar. Yeah, it's 
     ugly and all that but it is a workaround.

(* t1.mli *)
val foo : (int -> int) -> int -> int
(* t2.mli *)
val bar: (int -> int) -> int -> int
(* t1.ml *)
let foo f x = if x = 1 then f x else x
(* t2.ml *)
let bar f x = if x = 2 then f (x-1) else x
(* main.ml *)
let rec foo_aux x = T2.bar bar_aux x 
and bar_aux x = T1.foo foo_aux x

let _ = print_int (T2.bar bar_aux 2)


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[John Max Skaller]

Chris Hecker wrote:
> 
> Two questions/problems:
> 
> 1.  So, I understand that doing recursive types across modules is hard (but I'd say very important for decoupling large software), but is it true that I can't even call across modules recursively? 

	Yes. More precisely, you cannot forward reference any symbol,
however you _can_ call forward by passing a function backward as an
argument.
[This sucks though]

> 2. Also, on a related note, why do the interface file and the implementation file (or equivalently, I believe, the signature and structure) both have to have all the concrete types duplicated? 

	Because types in a given implementation may or may not be present
in the interface.

	IF you have a file containing ONLY types, then there is no need
to have an .ml file for it. If you have even one val (function, class),
you need the .ml file.


-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Chris Hecker]

>        Because types in a given implementation may or may not be present
>in the interface.

Right, that's fine, but I only want to have them once, whereever they are.  So, if it's a private type, it's in the ml file, and if it's public it's in the mli file (assuming I want one, if I don't then everything's public).  How does having them duplicated buy me anything but trouble?

Chris

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[John Max Skaller]

Chris Hecker wrote:
> 
> >        Because types in a given implementation may or may not be present
> >in the interface.
> 
> Right, that's fine, but I only want to have them once, whereever they are.  So, if it's a private type, it's in the ml file, and if it's public it's in the mli file (assuming I want one, if I don't then everything's public).  How does having them duplicated buy me anything but trouble?
> 
> Chris

In C++, a function is either extern or static. 
There are only two options. [And non-local classes are _always_ extern]
This is not so in Ocaml: you may wish to provide access to a component
such as a function with a type more constrained than the actual
implementation.
For example:

	(* twoint.mli *)
	val twoint: int -> int * int

	(* twoint.ml *)
	let twoint x = (x,x)

Here, the implementation is actually polymorphic, it will work
for more than ints, but clients of the module 'twoint' cannot
use this function to make a pair of floats.

Here is another example:

	(* abstr.mli *)
	type t
	val get: t -> int
	val make: int -> t

	(* abstr.ml *)
	type t = int * int
	let get x = fst x
	let make x = (x,x+1)	


Here, the type t is implemented as a pair of ints.
But the implementation is hidden from the client of the module.
Note that the type 't' itself is not hidden.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Chris Hecker]

> There are only two options. [And non-local classes are _always_ extern]
> This is not so in Ocaml: you may wish to provide access to a component
> such as a function with a type more constrained than the actual
> implementation.

Yes yes yes, I know this.  I'm saying I understand why I need to type
stuff if there's a difference betwen the .ml and .mli versions (hiding
stuff, restricting stuff, abstracting stuff), and that's fine.  I'm
asking why I need to retype stuff if it's identical.  Check out some
of the source code in the compiler, or any ocaml project I've seen
(the ICFP winners, whatever).  There are tons of really huge variants
that are just duplicated in mli and ml.  That seems bad, for the same
reason that typing a C++ function declaration 2 times is bad.

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Patrick M Doane]

I agree that checking interface/implementation of modules could be
improved.

For projects that I've worked on that have huge variant types, I have
typically placed the variants in a module by themselves with no .mli file. 
This technique hasn't worked too well for me in practice and is still
annoying for the smaller variants. 

A reasonable modification to the language would allow a module expression
to not include type definitions when they are defined in the module type
and include their type information. 

This would mean that

  module X : sig type t = int end = struct end

would be accepted, but

  module X : sig type t end = struct end

would be rejected because the abstract field 't' is required but missing.


Would this proposal address all the issues you had in mind?

Patrick Doane

On Tue, 20 Mar 2001, Chris Hecker wrote:

> 
> > There are only two options. [And non-local classes are _always_ extern]
> > This is not so in Ocaml: you may wish to provide access to a component
> > such as a function with a type more constrained than the actual
> > implementation.
> 
> Yes yes yes, I know this.  I'm saying I understand why I need to type
> stuff if there's a difference betwen the .ml and .mli versions (hiding
> stuff, restricting stuff, abstracting stuff), and that's fine.  I'm
> asking why I need to retype stuff if it's identical.  Check out some
> of the source code in the compiler, or any ocaml project I've seen
> (the ICFP winners, whatever).  There are tons of really huge variants
> that are just duplicated in mli and ml.  That seems bad, for the same
> reason that typing a C++ function declaration 2 times is bad.
> 
> Chris
> 
> 
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr
> 

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Chris Hecker]

> This would mean that
>   module X : sig type t = int end = struct end
> would be accepted, but
>   module X : sig type t end = struct end
> would be rejected because the abstract field 't' is required but missing.
> Would this proposal address all the issues you had in mind?

Yep, that's what I had in mind!

Chris

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[John Max Skaller]

Patrick M Doane wrote:
 
> For projects that I've worked on that have huge variant types, I have
> typically placed the variants in a module by themselves with no .mli file.
> This technique hasn't worked too well for me in practice and is still
> annoying for the smaller variants.

	Try placing them in a .mli file instead (no ml file).

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Patrick M Doane]

I don't see that it makes much of a difference. Besides, the reason it
hasn't worked well for me is that inevitably I want to add some
functions to the module that has the variant type. For example, pretty
printers. The next compromise is to continue the path without a .mli file
until I don't want some of these utilities to be exported.  In the end,
I'm back to the source of the problem, having to duplicate a large variant
type.

On Thu, 22 Mar 2001, John Max Skaller wrote:

> Patrick M Doane wrote:
>  
> > For projects that I've worked on that have huge variant types, I have
> > typically placed the variants in a module by themselves with no .mli file.
> > This technique hasn't worked too well for me in practice and is still
> > annoying for the smaller variants.
> 
> 	Try placing them in a .mli file instead (no ml file).
> 
> -- 
> John (Max) Skaller, mailto:skaller@maxtal.com.au
> 10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
> checkout Vyper http://Vyper.sourceforge.net
> download Interscript http://Interscript.sourceforge.net
> 

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Brian Rogoff]

On Wed, 21 Mar 2001, Patrick M Doane wrote:
> I don't see that it makes much of a difference. Besides, the reason it
> hasn't worked well for me is that inevitably I want to add some
> functions to the module that has the variant type. For example, pretty
> printers. The next compromise is to continue the path without a .mli file
> until I don't want some of these utilities to be exported.  In the end,
> I'm back to the source of the problem, having to duplicate a large variant
> type.

What's the problem with the hack I suggested earlier: put the huge variant 
(and other duplicated types) in a "pure" .mli file (I hate using .ml for
that) and "open"ing it where you need it, once in the .mli file and once in the 
.ml file? This way you reduce the duplication to two lines.

I know some people are open-phobes, but I find this use of open to be 
acceptable.

-- Brian

> 
> On Thu, 22 Mar 2001, John Max Skaller wrote:
> 
> > Patrick M Doane wrote:
> >  
> > > For projects that I've worked on that have huge variant types, I have
> > > typically placed the variants in a module by themselves with no .mli file.
> > > This technique hasn't worked too well for me in practice and is still
> > > annoying for the smaller variants.
> > 
> > 	Try placing them in a .mli file instead (no ml file).
> > 
> > -- 
> > John (Max) Skaller, mailto:skaller@maxtal.com.au
> > 10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
> > checkout Vyper http://Vyper.sourceforge.net
> > download Interscript http://Interscript.sourceforge.net
> > 
> 
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr
> 

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] duplication implementation/interface

[Judicael Courant]

Brian Rogoff a écrit :
> 
[...]
> What's the problem with the hack I suggested earlier: put the huge variant
> (and other duplicated types) in a "pure" .mli file (I hate using .ml for
> that) and "open"ing it where you need it, once in the .mli file and once in the
> .ml file? This way you reduce the duplication to two lines.
> 
> I know some people are open-phobes, but I find this use of open to be
> acceptable.
> 

As for open-phobes, somebody gave me a good solution a few days ago: you
can locally define a module with a very short name.

Example : put your type in my_beautiful_type.mli with constructors Node,
Leaf, ..., and where you need it do

module T = My_beautiful_type

then you can use it with a small overhead of 2 chars per use of a
constructor of My_beautiful_type: T.Node, T.Leaf, ...

This is quite elegant IMHO as it makes your code very clear.

As an aside, if you consider applying the same treatment for exceptions
(also duplicated), you need to put them in a .ml file (not a .mli) as a
.cmo is needed for linking (an exception actually creates at run-time a
fresh exception identifier).

Judicaël
-- 
Judicael.Courant@lri.fr, http://www.lri.fr/~jcourant/
(+33) (0)1 69 15 64 85
"Montre moi des morceaux de ton monde, et je te montrerai le mien"
Tim, matricule #929, condamné à mort.
http://rozenn.picard.free.fr/tim.html
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] about typedefs... (was: duplication implementation/interface)

[Olivier Andrieu]

 Judicael Courant [Thursday 22 March 2001] :
 > Brian Rogoff a écrit :
 > > 
 > [...]
 > > What's the problem with the hack I suggested earlier: put the
 > > huge variant (and other duplicated types) in a "pure" .mli file
 > > (I hate using .ml for that) and "open"ing it where you need it,
 > > once in the .mli file and once in the .ml file? This way you
 > > reduce the duplication to two lines.
 > > 
 > > I know some people are open-phobes, but I find this use of open
 > > to be acceptable.
 > > 
 > 
 > As for open-phobes, somebody gave me a good solution a few days
 > ago: you can locally define a module with a very short name.

There's something I've been wondering about type definitions :

In type definitions, you can specify type equation and representation.
 - when none is specified, the defined type is abstract ;
 - when an equation is given, you get an alias of an already existing
type ;
 - with a representation, a new variant or record is defined.

But it is possible to use both, so that you get an alias of an already
defined variant and record but with the fields or constructors attached to
the new type. 

It don't really see the point of such a definition : now the type
representation is in 4 different places, and the only gain I see is
that you don't have to prefix the fields names with a module
path. That's no big deal since you can redefine the module with a short
name (one letter).

So, is this form of type definitions actually used, does it have another
purpose besides this namespace issue ?

	Olivier
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] duplication implementation/interface

[Brian Rogoff]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: TEXT/PLAIN; charset=X-UNKNOWN, Size: 2261 bytes --]

On Thu, 22 Mar 2001, Judicael Courant wrote:
> Brian Rogoff a écrit :
> > 
> [...]
> > What's the problem with the hack I suggested earlier: put the huge variant
> > (and other duplicated types) in a "pure" .mli file (I hate using .ml for
> > that) and "open"ing it where you need it, once in the .mli file and once in the
> > .ml file? This way you reduce the duplication to two lines.
> > 
> > I know some people are open-phobes, but I find this use of open to be
> > acceptable.
> > 
> 
> As for open-phobes, somebody gave me a good solution a few days ago: you
> can locally define a module with a very short name.
> 
> Example : put your type in my_beautiful_type.mli with constructors Node,
> Leaf, ..., and where you need it do
> 
> module T = My_beautiful_type
> 
> then you can use it with a small overhead of 2 chars per use of a
> constructor of My_beautiful_type: T.Node, T.Leaf, ...
> 
> This is quite elegant IMHO as it makes your code very clear.

Oh yes, this is the common solution in Ada-land for "use-phobes" (their
analogue of open-phobes :) to long package names. They have it a little 
better in that "use" can be in any declarative region so it makes it
easier to find which module things come from. It is possible to do this 
in OCaml with the local module feature but I don't see it as much in code 
I've read.

> As an aside, if you consider applying the same treatment for exceptions
> (also duplicated), you need to put them in a .ml file (not a .mli) as a
> .cmo is needed for linking (an exception actually creates at run-time a
> fresh exception identifier).

Excellent point. However, I don't tend to define that many exceptions, far
fewer than the size of variant types (which easily get tens of
constructors even for a single type) so that duplication doesn't bother me
as much as for types. Still, I should perhaps rethink my aversion to using
a ".ml" as the file holding the duplicated info. 

This entire discussion has the seeds of a few more FAQ entries. Is our
esteemed erstwhile moderator going to do it, or should I take a stab and 
then mail it along?

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Francois Pottier]

On Wed, Mar 21, 2001 at 07:03:55PM -0500, Patrick M Doane wrote:
>
> I'm back to the source of the problem, having to duplicate a large variant
> type.

I think you have missed the point of John's (or was it Brian's?) suggestion,
which is to place large type (or module type) definitions in a separate .mli
(or .ml) file, then refer to it from your .mli *and* your .ml file. This has
the unfortunate consequence of breaking every module into three files (shared
definitions, interface, and implementations), making the program structure
somewhat more cryptic. But it usually works well.

Regarding your suggestion,

>  For every module definition M that has a signature S
>    For every type definition t in S that contains optional
>               type-information and is not defined in M
>      Add the type definition of t to M (preserving the order from S)
                                          ^^^^^^^^^^^^^^^^^^^^

I think the problematic part is in the ordering. The order in which bindings
appear may be different in M and S, to start with. So, where do we insert the
definition, and (assuming we know where) what do we do if some names referred
to by the definition aren't yet defined in M at that point?

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[John Prevost]

>>>>> "pd" == Patrick M Doane <patrick@watson.org> writes:

    pd> This would mean that

    pd>   module X : sig type t = int end = struct end

    pd> would be accepted, but

    pd>   module X : sig type t end = struct end

    pd> would be rejected because the abstract field 't' is required
    pd> but missing.

What about "module X : sig type t end = struct type t end", where
values of the type can't actually be constructed?  (Except possibly by
C code.)

John.
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Patrick M Doane]

Hi John,

It seems to me that this would be perfectly legal. It is accepted by the
current Ocaml language, and by the extension I proposed unless there is
something I'm missing.  Is this the behavior you're expecting?

Patrick

On 21 Mar 2001, John Prevost wrote:

> >>>>> "pd" == Patrick M Doane <patrick@watson.org> writes:
> 
>     pd> This would mean that
> 
>     pd>   module X : sig type t = int end = struct end
> 
>     pd> would be accepted, but
> 
>     pd>   module X : sig type t end = struct end
> 
>     pd> would be rejected because the abstract field 't' is required
>     pd> but missing.
> 
> What about "module X : sig type t end = struct type t end", where
> values of the type can't actually be constructed?  (Except possibly by
> C code.)
> 
> John.
> 

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[John Max Skaller]

Chris Hecker wrote:
> 
> > There are only two options. [And non-local classes are _always_ extern]
> > This is not so in Ocaml: you may wish to provide access to a component
> > such as a function with a type more constrained than the actual
> > implementation.
> 
> Yes yes yes, I know this.  I'm saying I understand why I need to type
> stuff if there's a difference betwen the .ml and .mli versions (hiding
> stuff, restricting stuff, abstracting stuff), and that's fine.  I'm
> asking why I need to retype stuff if it's identical. 

	You don't. There is a tool:

	ocamlc -i fred.ml > fred.mli

which will generate the mli file for you. (Use the -i option on the
compiler).

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[John Max Skaller]

Chris Hecker wrote:
> 
> > There are only two options. [And non-local classes are _always_ extern]
> > This is not so in Ocaml: you may wish to provide access to a component
> > such as a function with a type more constrained than the actual
> > implementation.
> 
> Yes yes yes, I know this.  I'm saying I understand why I need to type
> stuff if there's a difference betwen the .ml and .mli versions (hiding
> stuff, restricting stuff, abstracting stuff), and that's fine.  I'm
> asking why I need to retype stuff if it's identical. 

	BTW: you DON'T actually need an .mli file. Try it.
It is only needed when there IS a constraint on 'everything public'.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Markus Mottl]

On Mon, 19 Mar 2001, John Max Skaller wrote:
> 	Yes. More precisely, you cannot forward reference any symbol,
> however you _can_ call forward by passing a function backward as an
> argument.
> [This sucks though]

Note that you can always use local modules + functors so as not having
to pass around functions backwards, e.g.:

  module MakeM (Spec : sig val f : int -> int end) = struct
    open Spec

    let foo x = f x
    let bar x y = f x + f y
  end

  let bla g =
    let module Spec = struct let f = g end in
    let module M = MakeM (Spec) in
    print_int (M.foo 42 + M.bar 1 2)

  let _ = bla succ

Put the functions that should be "backwards parameterized" into functor
"MakeM". Then generate its specifcation "Spec" at runtime in some function
"bla" (here: "f" should be some function "g" passed at runtime) and apply
the functor "MakeM" to the specification "Spec". Now you can access the
"backwards parameterized" functions using the qualified module path "M."

If you feel annoyed by the fully qualified path, just write another
local module, in which you can "open" module "M" and provide some "start"
function in this new module to continue execution.

If you want even more hardcore moduling, you might be interested in trying
out the new "include"-keyword for structures (my favourite new language
extension! Thanks!) with the tricks above. You can do tremendous things
with it, like overriding specific functions of modules at runtime, etc.,
with hardly any effort.

The only remaining question here is: how efficiently can OCaml handle
local modules and local functor applications? I haven't measured it,
but I guess that this could be expensive.

Regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Xavier Leroy]

> 1.  So, I understand that doing recursive types across modules is
> hard (but I'd say very important for decoupling large software), but
> is it true that I can't even call across modules recursively?  Even
> with mli files to resolve the types?  I find that incredibly hard to
> believe, but I can't get it to work and it seems the docs say it's
> impossible as well (so why am I posting about it, you ask?
> Disbelief that it's not possible, I guess. :).

You're right that cross-module recursion even between functions is not
supported, and you're right that this is not because of typing
difficulties -- the type-checking of such recursions is easy.

This is because value components of modules can be the result of
arbitrary computations, and the only way to ensure that these
computations succeed is by making sure they occur sequentially.
Consider for instance:

    A.mli    val x : int                B.mli    val y : int
    A.ml     let x = B.y + 1            B.ml     let y = A.x * 3

We don't know how to evaluate these definitions correctly -- indeed,
there is no integer solution to this recursive definition.

Other languages avoid this problem in one of two ways.  C and C-like
languages only allow global identifiers to be defined as functions or
compile-time constants, but not results of arbitrary computations.
Haskell and other lazy languages rely on lazy evaluation to perform
on-demand initialization (i.e. compute the definition the first time
it's needed), and aborting computation if a dynamic dependency cycle
is detected (as in the example above).

Java goes pretty much the Haskell way, relying on dynamic class
loading to lazily evaluate static field definitions; originally, it
raised an exception on discovering a dynamic dependency cycle;
nowadays, I think it just pre-initializes static fields to 0 or null,
then compute the initial values based on this (so that in the example
above you'd get x = 1 and y = 3 if the program refers to B.y first,
and y = 0 and x = 1 if the program refers to A.x first :-).

The Haskell solution is semantically cleanest, but lazy evaluation
of module components entails a performance penalty and some increase
in code size (the compiler must emit "am I initialized already?" tests
on every module value access).  (The semantics of Java class
initialization entail similar penalties, although they partially hide
them by relying on JIT compilation -- blech.)

A possible approach for Caml would be to have a link-time analysis
that detects cross-module value recursions that involve only function
definitions, and allow these (because they are safe -- like in C!).
Fabrice Le Fessant posted a patch to OCaml a while ago that does
pretty much this.  I'm still hoping more general, principled solutions
exist, but they sure are hard to design!

> 2. Also, on a related note, why do the interface file and the
> implementation file (or equivalently, I believe, the signature and
> structure) both have to have all the concrete types duplicated?  I can
> see the value of having interfaces that hide some implementation stuff
> and abstract types, but if I've got a big fully-specified variant type
> in a .mli file, it's annoying and error prone (yes, I know the
> compiler will catch it) to have to retype the whole thing into the ml
> file (which I have to do if I want to hide anything else in the ml
> file, meaning I can't just have an ml without an mli).

Yes, it's annoying, and it's more or less a consequence of the
ideology behind the ML module system: that structures define things,
and that signatures can later be ascribed to these structures to hide
or abstract some of these things.  With this ideology, every type that
is declared in a signature -- even if it's a concrete declaration that
includes as much information as a type definition! -- must be matched
by a type definition in the corresponding structure. It's just very
principled and logical -- just a bit inconvenient at times :-)

Another way to think about it is that every structure (or
implementation file) must "stand on its own" and make sense without
the signature (or interface file) that will be ascribed to it later
on.  It makes sense when the signature is not known when the structure
is defined, e.g.

        module M = struct type t = A | B ... end
        (* 5000 lines later: *)
        module M' = (M : sig type t = A | B ... end)

It becomes practically inconvenient when the signature is known at the
time of the structure definition:

        module M : sig type t = A | B ... end =
          struct type t = A | B ... end

Which is the case with interface and implementation files.

In this case, one could envision an automatic completion of the
structure / implementation file so that concrete type specifications
from the signature do not need to be implemented in the structure.
Doing this right is not obvious, though.  First, it's not enough to
say that a concrete type spec does not need to be matched in the
structure.  This would type-check

        module M : sig type t = A | B end = struct end

but not

    module M : sig type t = A | B  val v : t end = struct let v = A end

In other terms, the unmatched concrete type specs in the signature
need to be somehow reintroduced in the structure definition, so that
other parts of the structure may refer to them.  While I think it can
be done in most practical cases, it's a bit of a kludge and I'm not
sure how to do this in all cases.

Is the practical value of this kludge enough to forget that it's a
kludge?  Can't we live with the current duplication of concrete type
definitions in the name of systematic, principled module systems?  
I really don't know.

Best,

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Patrick M Doane]

Hi Xavier,

Your example demonstrates that a proposal for such an extension
should be more explicit about how it should work.  I had a particular
implementation in mind from my post yesterday:

  For every module definition M that has a signature S
    For every type definition t in S that contains optional
               type-information and is not defined in M
      Add the type definition of t to M (preserving the order from S)

  Proceed with the usual algorithms for type checking, matching
      structures,  etc.

I think this should work properly. Anything I might have missed? You seem
to elude to special cases that are not immediately obvious.

I agree that it becomes kludgy to remove the separation that currently
exists between structures and signatures.  However, as a programmer
maintaining the duplicate types also seems kludgy . After all, the
compiler has the information available, why doesn't it use it?

This seems to be a case where a compromise between theory and practice
should be explored.

Patrick


On Wed, 21 Mar 2001, Xavier Leroy wrote:

> It becomes practically inconvenient when the signature is known at the
> time of the structure definition:
> 
>         module M : sig type t = A | B ... end =
>           struct type t = A | B ... end
> 
> Which is the case with interface and implementation files.
> 
> In this case, one could envision an automatic completion of the
> structure / implementation file so that concrete type specifications
> from the signature do not need to be implemented in the structure.
> Doing this right is not obvious, though.  First, it's not enough to
> say that a concrete type spec does not need to be matched in the
> structure.  This would type-check
> 
>         module M : sig type t = A | B end = struct end
> 
> but not
> 
>     module M : sig type t = A | B  val v : t end = struct let v = A end
> 
> In other terms, the unmatched concrete type specs in the signature
> need to be somehow reintroduced in the structure definition, so that
> other parts of the structure may refer to them.  While I think it can
> be done in most practical cases, it's a bit of a kludge and I'm not
> sure how to do this in all cases.
> 
> Is the practical value of this kludge enough to forget that it's a
> kludge?  Can't we live with the current duplication of concrete type
> definitions in the name of systematic, principled module systems?  
> I really don't know.

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Hendrik Tews]

Hi,

I would like to vote for solutions that work for the common case
when writing large programs, even if they are hacks, considered
from a theoretical point of view.

Xavier Leroy writes:

     [cross module recursion]
   
       A.mli    val x : int                B.mli    val y : int
       A.ml     let x = B.y + 1            B.ml     let y = A.x * 3
   
   We don't know how to evaluate these definitions correctly -- indeed,
   there is no integer solution to this recursive definition.
   
I think that in this case the theoretical cleaness is overrated.
Cross module recursion of functions is soo useful, that it
should be made to work --- even if the solution seems stupid with
respect to the example above.

   [duplications in signatures and structures]

   Is the practical value of this kludge enough to forget that it's a
   kludge?  

Sure.

   Can't we live with the current duplication of concrete type
   definitions in the name of systematic, principled module systems?  

No, at least I cannot. Also here I would suggest to have a
solution that works for the common case. What about changing
include, such that including a signature into a structure
includes all types and all exceptions?


Bye,

Hendrik
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Markus Mottl]

Hendrik Tews schrieb am Thursday, den 22. March 2001:
> I would like to vote for solutions that work for the common case
> when writing large programs, even if they are hacks, considered
> from a theoretical point of view.

I am not so fond of sacrificing theoretical beauty: it usually seems
to be the case that there are working solutions that are also elegant -
it's only a matter of thinking about them long enough. You might speed
up development a bit by allowing hacks if you cannot immediately find
a sound solution, but IMHO it is hardly ever a good idea in the long run.

> I think that in this case the theoretical cleaness is overrated.

In general? Probably not. If there is a problem with expressiveness or
else, it seems to be better to first try harder to find a solution with
the existing system before crying for a hacky extension. And if this
doesn't work, let's try to find a more expressive theory rather than
abandoning theory completely.

> Cross module recursion of functions is soo useful, that it
> should be made to work --- even if the solution seems stupid with
> respect to the example above.

Nearly everytime I had thought "now I need recursive modules", I found
other, even elegant ways to do it. If we really want them, please
let's don't put aside theory but take existing clean solutions (e.g.
see Claudio Russo's thesis).

>    [duplications in signatures and structures]
> 
>    Is the practical value of this kludge enough to forget that it's a
>    kludge?  
> 
> Sure.

The solution to put the whole signature into a separate .ml-file requires
hardly any work and solves this problem neatly. Why introduce a kludge
if there are reasonable ways to do it?

> No, at least I cannot.

Do you have examples where the current system is just too awkward to use?

> Also here I would suggest to have a
> solution that works for the common case. What about changing
> include, such that including a signature into a structure
> includes all types and all exceptions?

But you can do this (and I do it regularly) by putting the signature stuff
into a separate module (or .ml-file): then you can "include" things in
your structures to your hearts delight (thanks to the new way of using
"include" with structures).

Regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Brian Rogoff]

On Thu, 22 Mar 2001, Markus Mottl wrote:
> Hendrik Tews schrieb am Thursday, den 22. March 2001:
> > I would like to vote for solutions that work for the common case
> > when writing large programs, even if they are hacks, considered
> > from a theoretical point of view.
> 
> I am not so fond of sacrificing theoretical beauty: it usually seems
> to be the case that there are working solutions that are also elegant -
> it's only a matter of thinking about them long enough. You might speed
> up development a bit by allowing hacks if you cannot immediately find
> a sound solution, but IMHO it is hardly ever a good idea in the long run.

I agree with this general principle, and to be honest, I haven't found in
my own programming a compelling case where module spanning mutually
recursive function definitions were an issue. Is it possible to produce a 
reasonably sized example, Hendrik (or Chris)? I'm annoyed by the inability
to have a mutually recursive *type* definition and functor instantiation,
and that problem can be solved with recursive modules (Claudio Russo says 
it works in a development version of Mosml), but I haven't had this
problem with functions yet. 

As an aside, Claudio mentioned that it would be easy to extend OCaml to 
support this feature: are there any plans to do so? If not, maybe I'll 
push for it when the Consortium is set up. 

> > Cross module recursion of functions is soo useful, that it
> > should be made to work --- even if the solution seems stupid with
> > respect to the example above.

I agree that the workaround is a tiny bit ugly, but I'm not convinced that
the problem is so great that it justifies any kind of new kludge. Convince 
me! My mind is open (or include'ed :) 

> Nearly everytime I had thought "now I need recursive modules", I found
> other, even elegant ways to do it. 

How about the case I mention above? I think that there are a few cases
where some extensions are necessary, however...

> If we really want them, please let's don't put aside theory but take
> existing clean solutions (e.g. see Claudio Russo's thesis).

Yes. Let's have the extensions be clean, well founded ones. Even some
people in industry realize that this is the right way to go. :-)

I've snipped the module inclusion stuff because I think that while the 
need for a workaround is unfortunate, I think that there are bigger fish
to fry.

-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Daniel de Rauglaudre]

Hi everybody,

My usual hack for mutually recursive functions in different modules:

File foo.ml:
   let g_ref = ref (fun _ -> failwith "Bar.g not yet defined")
   let g x = !g_ref x
   let f ... = .... g ...

File bar.ml:
   let g .... = .... Foo.f ...
   Foo.g_ref := g

By extending the language using Camlp4, by the constructions "forward" and
"define_forward" doing the right thing, you could have:

File foo.ml:
   forward g
   let f ... = .... g ...

File bar.ml:
   let g .... = .... Foo.f ...
   define_forward g

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Fergus Henderson]

On 22-Mar-2001, Brian Rogoff <bpr@best.com> wrote:
> 
> I haven't found in
> my own programming a compelling case where module spanning mutually
> recursive function definitions were an issue. Is it possible to produce a 
> reasonably sized example, Hendrik (or Chris)?

In the Mercury compiler, we have made significant use of module spanning
mutually recursive procedures.  For example, the code generator
is split among several modules, roughly for each language construct
(e.g. ite_gen handles code generation for if-then-elses,
switch_gen handles code generation for switches, etc.),
and since if-then-elses can contain switches (and vice versa),
the procedures in these modules are mutually recursive.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Brian Rogoff]

On Sat, 24 Mar 2001, Fergus Henderson wrote:
> On 22-Mar-2001, Brian Rogoff <bpr@best.com> wrote:
> > I haven't found in
> > my own programming a compelling case where module spanning mutually
> > recursive function definitions were an issue. Is it possible to produce a 
> > reasonably sized example, Hendrik (or Chris)?
> 
> In the Mercury compiler, we have made significant use of module spanning
> mutually recursive procedures.  For example, the code generator
> is split among several modules, roughly for each language construct
> (e.g. ite_gen handles code generation for if-then-elses,
> switch_gen handles code generation for switches, etc.),
> and since if-then-elses can contain switches (and vice versa),
> the procedures in these modules are mutually recursive.

Interesting. A similar example occurred in a discussion in comp.lang.ml 
between Matthias Blume and Greg Morrissett (concerning datatypes not
functions) where MB argued as an SML/NJ maintainer that such recurrences
were best placed in the same module and GM thought it best that they be
split even though recursive. Clearly I lean towards MB's view on this 
though I take it that there are other schools of thought. 

What is your criteria for splitting the functions into different modules?

-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

[Caml-list] Why People Aren't Using OCAML? (was Haskell)

[Mattias Waldau]

Something we should think about also for Ocaml

http://www.jelovic.com/articles/why_people_arent_using_haskell.htm

"What can be done about this? First and foremost the Haskell community must
make a standard distribution of Haskell that contains enough libraries to be
useful. That should include a regular expression library, an Internet
protocol library, a library for dealing with standard internet data and
encoding, a crypto library, a multimedia library and a GUI library.

Next, the Haskell community must step out of its research circles and start
publicizing Haskell to the practicing programmers. Write articles in DDJ and
similar publications. Publish real-world programs written in Haskell."

Most of this is also relevant for Ocaml, for example there are
crypto libraries and XML-support (for example PXP, which require wlex, which
is a hazzle).

I stumbled over Ocaml, thanks to Mercury and ICFP-contest.

/mattias

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Fergus Henderson]

On 23-Mar-2001, Brian Rogoff <bpr@best.com> wrote:
> On Sat, 24 Mar 2001, Fergus Henderson wrote:
> > 
> > In the Mercury compiler, we have made significant use of module spanning
> > mutually recursive procedures.  For example, the code generator
> > is split among several modules, roughly for each language construct
> > (e.g. ite_gen handles code generation for if-then-elses,
> > switch_gen handles code generation for switches, etc.),
> > and since if-then-elses can contain switches (and vice versa),
> > the procedures in these modules are mutually recursive.
> 
> Interesting. A similar example occurred in a discussion in comp.lang.ml 
> between Matthias Blume and Greg Morrissett (concerning datatypes not
> functions) where MB argued as an SML/NJ maintainer that such recurrences
> were best placed in the same module and GM thought it best that they be
> split even though recursive. Clearly I lean towards MB's view on this 
> though I take it that there are other schools of thought. 
> 
> What is your criteria for splitting the functions into different modules?

Our criteria are pretty informal: each module should consist of closely
related code, preferably with a single purpose that can be summed up
in a concise title, e.g. "code generation for if-then-elses".

In this case, I think the code was originally in a single module,
but was split into sub-modules when it became too large.
Here's the line counts of the relevant modules:

       768 call_gen.m
      1296 code_gen.m
        67 commit_gen.m
       324 disj_gen.m
       360 ite_gen.m
       283 par_conj_gen.m
      1254 pragma_c_gen.m
       313 switch_gen.m
       897 unify_gen.m
       245 dense_switch.m
       549 lookup_switch.m
       246 string_switch.m
      1100 tag_switch.m
       584 middle_rec.m
      ----
      8286

Generally we prefer to make modules in the range of about 200-2000
lines of code each.  If a module gets much larger than that, then
it tends to get a bit unwieldy, and recompilation times start to become
inconvenient, so we prefer to split up modules that get larger than that.
8000 lines is definitely way too big.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[John Max Skaller]

Brian Rogoff wrote:

> I agree with this general principle, and to be honest, I haven't found in
> my own programming a compelling case where module spanning mutually
> recursive function definitions were an issue. Is it possible to produce a
> reasonably sized example, Hendrik (or Chris)? 

	I have such an example. In the Vyper interpreter, there is a
very large module which handles execution of ASTs, which contains
almost all the interpretive code. It was not possible to break this
module into further pieces because of the mutual recursion.
[I actually _did_ do this, then undid it, because of the excessive
number of extra arguments that had to be passed to make it work]

	Vyper is an extension of Python, which does things like:

	1. The expression x + y is addition of numbers if x and y are
	  numbers, otherwise, if x or y are objects of class type,
	  method calls.

	2. The expression eval(string) evaluates string in the current context

which require mutual recursion across widely separates levels of 
otherwise fairly logical layers. I used indirection for most of these
recursions (via a class object), but the lower level core execution
was best handled by putting all the routines in one module.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Brian Rogoff]

On Wed, 28 Mar 2001, John Max Skaller wrote:
> Brian Rogoff wrote:
> > I agree with this general principle, and to be honest, I haven't found in
> > my own programming a compelling case where module spanning mutually
> > recursive function definitions were an issue. Is it possible to produce a
> > reasonably sized example, Hendrik (or Chris)? 
> 
> 	I have such an example. In the Vyper interpreter, there is a
> very large module which handles execution of ASTs, which contains
> almost all the interpretive code. It was not possible to break this
> module into further pieces because of the mutual recursion.

This seems simialr to Fergus Henderson's example in the Mercury compiler. 
I thought his rationale was convincing (the file just got too big) and 
I assume he and you considered various refactorings to keep from splitting 
the module and decided against them. So even though there's practically no
better example of functions that belong in the same module as mutually
recursive ones, pragmatics suggests that you split them. None of the
compiler like programs I've worked on have become that big yet. 

> [I actually _did_ do this, then undid it, because of the excessive 
> number of extra arguments that had to be passed to make it work]

Yes, that can be a problem with the trick/hack of passing extra arguments. 
Did you consider the trick Daniel showed using function references which
get initialized in the right order during the calls? I don't like
introducing references unnecessarily but it might be useful until there is 
a cleaner solution. 

-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[John Max Skaller]

Brian Rogoff wrote:

> Did you consider the trick Daniel showed using function references which
> get initialized in the right order during the calls?

	Yes, but it's also just too messy. Many of the workarounds are
probably OK for a few uses, but they don't really scale. 
With a 'fat' module, we get the simplest, cleanest, code, even if the
module is rather large: interfaces are only useful if they help reduce
complexity.

	The most scalable solution I found was to use classes to
'clump' related functions together, allowing a set of functions to
be passed as a single argument (a class object). This also allowed
some state to be put in the object instead of using a functional
closure.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] recursive modules redux, & interface files

[Hendrik Tews]

Hi,

Markus Mottl writes:
   From: Markus Mottl <mottl@miss.wu-wien.ac.at>
   Date: Thu, 22 Mar 2001 14:01:57 +0100
   Subject: Re: [Caml-list] recursive modules redux, & interface files
   
   Hendrik Tews schrieb am Thursday, den 22. March 2001:
   > I would like to vote for solutions that work for the common case
   > when writing large programs, even if they are hacks, considered
   > from a theoretical point of view.
   
   I am not so fond of sacrificing theoretical beauty: it usually seems
   to be the case that there are working solutions that are also elegant -
   it's only a matter of thinking about them long enough. You might speed
   up development a bit by allowing hacks if you cannot immediately find
   a sound solution, but IMHO it is hardly ever a good idea in the long run.
   
[As an aside: In principle I do not agree that usually there
 exist elegant solutions. This would imply that for most problems
 there are elegant solutions, whereas the attribute elegant can
 only apply to a small subset of all solutions (unless everything
 is elegant).
]

But for the main problem of mutual recursion: I would also
appreciate a theoretically nice solution. But ocaml and its
predecessors have been around now for long time, so it seems that
it is not that easy to find a good solution for mutal recursion
between modules. So instead of waiting another three years I
would prefer a solution now, even if it is intermediate and not
so clean.

   If there is a problem with expressiveness or
   else, it seems to be better to first try harder to find a solution with
   the existing system before crying for a hacky extension. And if this
   doesn't work, let's try to find a more expressive theory rather than
   abandoning theory completely.
   
I agree, don't let's abandoning theory. But let's make a few
compromises, where a good solution is not available in the near
future. 

   Nearly everytime I had thought "now I need recursive modules", I found
   other, even elegant ways to do it. 

I know, with some effort you can put every system in a linear
structure and avoid module spanning recursion. But I do not want
to restructure the whole project, only because I need some
recursive functions. The more important point is that in a
project with several people the overall complexity of the system
structure must stay below a certain limit. If you create a system
structure that is above this limit, then the project will fail.

   
   >    [duplications in signatures and structures]
   
   The solution to put the whole signature into a separate .ml-file requires
   hardly any work and solves this problem neatly. Why introduce a kludge
   if there are reasonable ways to do it?
   
I have the same argument here. Keeping three files instead of two
is more complex. As a programmer you have to pay for this
complexity and it doesn't buy you anything. The result is that
people do not write interfaces because they do not like the
additional effort it requires. 


Bye,

Hendrik
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

[Caml-list] parser combinators

[Kevin Backhouse]

Is there a parser combinator library for OCaml? I would like to write a
parser for Java and I gather that Java's grammar is LL(1). That might mean
that parser combinators are better suited than yacc.

thanks,

Kevin Backhouse

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] parser combinators

[Daniel de Rauglaudre]

Hello,

On Fri, Mar 30, 2001 at 11:27:55AM +0100, Kevin Backhouse wrote:

> Is there a parser combinator library for OCaml? I would like to write a
> parser for Java and I gather that Java's grammar is LL(1). That might mean
> that parser combinators are better suited than yacc.

No, there is not, but you may consider using Camlp4 and its grammars.

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

some comments on ocaml{lex,yacc} from a novice's POV

[Jack Andrews]

hi,

this is a little long.  i'm new to ocaml, but like most, have been
educated in FLs and experimented with and applied functional languages and
techniques.  python has been the first language i turn to for a few years
now.

i need to parse text as a sequence of records (with odd variations). i
have used ply (python lex-yacc) most recently for parsing and believe it
to be one of the more elegant mechanisms i've seen. 
http://systems.cs.uchicago.edu/ply/ply.html

elegant because there are no lex and yacc input files, but rather the
tokens and grammar rules are defined in python code -- succinctly!  eg:

# calclex.py
import lex
tokens = ( 'NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN',)
t_PLUS    = r'\+'  # in python, the r prefix to a string literal
t_MINUS   = r'-'   #  means as-is.  r'\' in python is "\\" in c
[snip]
def t_NUMBER(t):
    r'\d+'
    try: t.value = int(t.value)
    except ValueError:
         print "Line %d: Number %s is too large!" % (t.lineno,t.value)
         t.value = 0
    return t

by reflection/introspection ply finds all the token definitions in
calclex.py.  the only trick here is the first line of the t_NUMBER
function.  in python, any string literal as the first expression in a
function is the doc_string (accessible by t_NUMBER.__doc__ in this case)

#!/usr/local/bin/python
import yacc
from calclex import tokens  # this is where python builds the lexer

def p_expression_plus(p):
    'expression : expression PLUS term'
    p[0] = p[1] + p[3]
[snip]
def p_factor_expr(p):
    'factor : LPAREN expression RPAREN'
    p[0] = p[2]
# this is where python builds the parser
yacc.yacc()   # or yacc.yacc(method="LALR") for alternate parsing methods
while 1:
   try: s = raw_input('calc > ')
   except EOFError: break
   if not s: continue
   result = yacc.parse(s)
   print result

once again, using the names of functions and their docstrings, ply can
build a parser.

but i want to use ocaml, not python because i know i need (more) speed. 
after using ply, the ocaml{yacc,lex} implementation looks like it's just
glued on GNU tools.  not that there's anything wrong with that, but
integration with the language is nothing like that of ply.

don't get me wrong, i don't think ply is perfect, and i don't know enough
about parsing to be any kind of authority, but it seems to me a bit odd
that a comment in a caml parser is either (**) or /**/ depending on
context and in lexical analysis, a character set is expressed as ['A'-'Z'
'a'-'z' '_'] rather than usual (succinct) regexp syntax: [A-Za-z_]  (less
than half the characters)   really, the .mll and .mly look nothing like
caml

take what i say with a grain of salt, i'm no authority on anything i've said.


jack

Re: [Caml-list] some comments on ocaml{lex,yacc} from a novice's POV

[Jacques Garrigue]

From: "Jack Andrews" <effbiae@ivorykite.com>

> this is a little long.  i'm new to ocaml, but like most, have been
> educated in FLs and experimented with and applied functional languages and
> techniques.  python has been the first language i turn to for a few years
> now.
> 
> i need to parse text as a sequence of records (with odd variations). i
> have used ply (python lex-yacc) most recently for parsing and believe it
> to be one of the more elegant mechanisms i've seen. 
> http://systems.cs.uchicago.edu/ply/ply.html
> 
> elegant because there are no lex and yacc input files, but rather the
> tokens and grammar rules are defined in python code -- succinctly!  eg:
> 
> # calclex.py
> import lex
> tokens = ( 'NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN',)
> t_PLUS    = r'\+'  # in python, the r prefix to a string literal
> t_MINUS   = r'-'   #  means as-is.  r'\' in python is "\\" in c
> [snip]

Interestingly, your example corresponds exactly to the one in the
ocaml tutorial, where it is solved using stream parsers.
Stream parsers are a bit more involved than just writing yacc rules,
but they give you more control on how to combine rules (you can write
parser combinators.) And they are completely integrated in the
language using camlp4.

Alternatively, you can also use ocamllex/ocamlyacc (a little bit more
overhead, but really easy once you're set up), or use the Scanf module
(if you don't need a real parser.)

By the way, Caml 3.1 had complete yacc integration (15 years ago).
I suppose this was considered too monolithic, but it was very nice to
use in practice.

Jacques Garrigue

Parser combinators [was: some comments on ocaml{lex,yacc} from a novice's POV]

[Alex Baretta]

Jacques Garrigue wrote:

> 
> Interestingly, your example corresponds exactly to the one in the
> ocaml tutorial, where it is solved using stream parsers.
> Stream parsers are a bit more involved than just writing yacc rules,
> but they give you more control on how to combine rules (you can write
> parser combinators.) And they are completely integrated in the
> language using camlp4.
> 

Er.. Excuse me for sticking my nose into this, but I think I read 
something interesting. Parser combinators? What do you mean? I'm quite 
sure I have not seen any operators acting on stream parsers, at least if 
by stream parsers you mean the LL1 based on pa_op.cmo camlp4 module.

Alex


-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: [Caml-list] Parser combinators

[Jacques Garrigue]

From: Alex Baretta <alex@barettadeit.com>
> > Interestingly, your example corresponds exactly to the one in the
> > ocaml tutorial, where it is solved using stream parsers.
> > Stream parsers are a bit more involved than just writing yacc rules,
> > but they give you more control on how to combine rules (you can write
> > parser combinators.) And they are completely integrated in the
> > language using camlp4.
> 
> Er.. Excuse me for sticking my nose into this, but I think I read 
> something interesting. Parser combinators? What do you mean? I'm quite 
> sure I have not seen any operators acting on stream parsers, at least if 
> by stream parsers you mean the LL1 based on pa_op.cmo camlp4 module.

The point is that you can define them yourself.
For instance here is the star operator.

let rec star ?(acc=[]) p = parser
    [< x = p ; s >] -> star ~acc:(x::acc) p s
  | [< >] -> List.rev acc

More concretely, here is another version of expression parsing, using
functionals. 

type expr =
    Num of int
  | Var of string
  | Plus of expr * expr
  | Mult of expr * expr

open Genlex

let rec accumulate parse accu = parser
  | [< e = parse accu; s >] -> accumulate parse e s
  | [< >] -> accu
(* val accumulate : ('a -> Genlex.token Stream.t -> 'a) ->
                    'a -> Genlex.token Stream.t -> 'a *)
let left_assoc parse op wrap =
  let parse' accu =
    parser [< 'Kwd k when k = op; s >] -> wrap accu (parse s) in
  parser [< e1 = parse; e2 = accumulate parse' e1 >] -> e2
(* val left_assoc : (Genlex.token Stream.t -> 'a) ->
       string -> ('a -> 'a -> 'a) -> Genlex.token Stream.t -> 'a *)
let rec parse_simple = parser
  | [< 'Int n >] -> Num n
  | [< 'Ident x >] -> Var x
  | [< 'Kwd"("; e = parse_expr; 'Kwd")" >] -> e
and parse_mult s =
  left_assoc parse_simple "*" (fun e1 e2 -> Mult(e1,e2)) s
and parse_expr s =
  left_assoc parse_mult "+" (fun e1 e2 -> Plus(e1,e2)) s
(* val parse_simple : Genlex.token Stream.t -> expr
   val parse_mult : Genlex.token Stream.t -> expr
   val parse_expr : Genlex.token Stream.t -> expr *)

let lexer = Genlex.make_lexer ["+";"*";"(";")"]
let parse_string s =
  match lexer (Stream.of_string s) with parser
    [< e = parse_expr; _ = Stream.empty >] -> e
(* val parse_string : string -> expr *)

I leave as exercise how to extend it to handle "-" and "/" in a
generic way.

Jacques Garrigue