[Haskell-cafe] mutually recursive modules
As far as can see neither Hugs or GHC really support them. Is this still on the to-do list or is it almost dropped due to implementation difficulties? ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mutually recursive modules
On Fri, 24 Sep 2004, Malcolm Wallace wrote: Hugs doesn't support mutually-recursive modules at all. Ghc and nhc98 support them only if you hand-write a .hi-boot file to bootstrap the compilation. I would guess that better support from the mainstream implementations is unlikely, because it would be a large amount of effort for a situation which occurs only very rarely, and for which there is a relatively easy workaround. Namely? The only workaround I know of is putting all type declarations and functions that depend on each other into one module, import them in the modules they logically belong to and document that the objects should be imported from the redirecting modules rather than from the modules they are defined in. I know of two projects where different tasks had to be merged into one module because of the lack of mutually recursive imports, namely functionalMetaPost and Haskore. It's interesting how other languages solve this problem. In Modula-3 it is solved by explicit module interfaces and partial revelation. One can define type T in module A and type T in module B very abstractly as pointers to something and the complete data structures (which may contain references to either interface) are usually revealed in the implementations of the modules. I'm curious how Oberon solves it, because it doesn't need explicit interfaces but derives them from the implementation files. Probably one can say that Oberon extracts something like a .hiboot file from every module file automatically. Why can't GHC and Hugs go this way? ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mutually recursive modules
Henning Thielemann [EMAIL PROTECTED] writes: As far as can see neither Hugs or GHC really support them. Is this still on the to-do list or is it almost dropped due to implementation difficulties? Hugs doesn't support mutually-recursive modules at all. Ghc and nhc98 support them only if you hand-write a .hi-boot file to bootstrap the compilation. I would guess that better support from the mainstream implementations is unlikely, because it would be a large amount of effort for a situation which occurs only very rarely, and for which there is a relatively easy workaround. Some lesser-known Haskell implementations do fully support mutually-recursive modules however. hhc (formerly Freja, from Henrik Nilsson) allows multiple modules to be stored in a single file, and hence mutual recursion can be achieved by ensuring all the recursive modules are compiled simultaneously from the same file. The PacSoft Haskell system (from the Programatica project at OGI) also fully supports mutually recursive modules, and I believe they can even be in separate files. Regards, Malcolm ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mutually recursive modules
Henning Thielemann [EMAIL PROTECTED] writes: a situation which occurs only very rarely, and for which there is a relatively easy workaround. Namely? ... See below. It's interesting how other languages solve this problem. In Modula-3 it is solved by explicit module interfaces and partial revelation. Essentially this is how ghc and nhc98 solve it too. You must write an explicit module interface (the .hi-boot file). This is the easy workaround. One benefit of these systems over Modula is that you /only/ need to write explicit interfaces where there is module recursion - in all non-recursive contexts, the interface generation is automatic. I'm curious how Oberon solves it, because it doesn't need explicit interfaces but derives them from the implementation files. Probably one can say that Oberon extracts something like a .hiboot file from every module file automatically. Why can't GHC and Hugs go this way? The main obstacle is that Haskell systems generally process one file/module at a time. To extract an interface from each module first, before further processing, would not only require a second pass over the source files, but to load all of them simultaneously, which can be rather space-hungry. Anyway, as Diatchki, Jones, and Hallgren [1] have demonstrated, it is certainly possible to build a Haskell compiler that deals properly with recursive modules. Regards, Malcolm [1] Iavor S. Diatchki, Mark P. Jones, and Thomas Hallgren A Formal Specification for the Haskell 98 Module System ACM Haskell Workshop, 2002, Baltimore http://www.cse.ogi.edu/~diatchki/hsmod/ ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mutually recursive modules
The original Haskell design included interface files usually with names like Main.hi IIRC, Yale Haskell expected them to be hand-written while HBC and GHC machine-generated but allowed the careful user to write them by hand. Sometime around Haskell 1.4 or 98, they were dropped because Yale Haskell had died and there seemed little point in specifying the format of machine-generated files. (Hugs' support for modules was added long after the original Hugs design - it was hard getting it to do as much as it does. At one point, I almost had it supporting mutually recursive modules but I couldn't quite get all the dependencies in the typechecker under control so I settled for just supporting module namespaces and qualifiers.) It is _almost_ possible to generate .hiboot files automatically. If you see a data declaration in the .hs file, copy it to the .hiboot file, if you see a function prototype, copy it, etc. That is, you generate a .hiboot file by just deleting all function definitions. One of the tedious bits is that that you need to do a tricky least fixpoint calculation just to figure out what is exported by a set of mutually recursive modules if they each reexport their imports. Generating .hiboot files by just deleting function definitions fails if there is no prototype for an exported function. A crude approach is to assume the type (\forall a. a) for any function with no prototype but, although this is sound (I think), it will cause valid programs to be rejected. This problem could be overcome by specifying it as the correct behaviour :-) (Is it sound to use (\forall a. a) in the presence of higher-kinded types and all those other extensions?) Hmmm, maybe someone familiar with the Haskell-source libraries could quickly hack up a program to generate .hiboot files automatically and make it available - that would quickly find the issues (and also identify any weaknesses in ghc's error checking of .hiboot files :-). -- Alastair Reid It's interesting how other languages [handle mutually recursive modules] problem. In Modula-3 it is solved by explicit module interfaces and partial revelation. One can define type T in module A and type T in module B very abstractly as pointers to something and the complete data structures (which may contain references to either interface) are usually revealed in the implementations of the modules. I'm curious how Oberon solves it, because it doesn't need explicit interfaces but derives them from the implementation files. Probably one can say that Oberon extracts something like a .hiboot file from every module file automatically. Why can't GHC and Hugs go this way? ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mutually recursive modules
Alastair Reid wrote: Generating .hiboot files by just deleting function definitions fails if there is no prototype for an exported function. A crude approach is to assume the type (\forall a. a) for any function with no prototype but, although this is sound (I think), it will cause valid programs to be rejected. Huh? How can that ever be sound? Are you sure you didn't mean (\exists a.a)? - Andreas -- Andreas Rossberg, [EMAIL PROTECTED] Let's get rid of those possible thingies! -- TB ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mutually recursive modules
On Fri, 24 Sep 2004, Malcolm Wallace wrote: The main obstacle is that Haskell systems generally process one file/module at a time. To extract an interface from each module first, before further processing, would not only require a second pass over the source files, but to load all of them simultaneously, which can be rather space-hungry. I don't see where it is necessary to load more modules than usually. Modula doesn't support cycles in the dependencies. Each implementation depends only on interfaces of other modules and the interfaces must not depend cyclicly. Haskell compilers can reduce the problem to the situation of Modula by extracting the interface from the implementation. Maybe it's better if the user explicitly allows mutually recursive modules with a command line option which will invoke an automatic interface generation. The generation of an interface file should depend only on the corresponding implementation file, as it is the case for manual .hiboot creation. For mutually recursive functions across modules the signature had to be specified by the user to avoid the simultaneous loading of all modules. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mutually recursive modules
An anecdotal note - hbcc (the front end to the pH and Eager Haskell compilers, and also of GRIN) contained several mutually recursive modules both in the compiler and in the prelude. One of the best things we ever did was get rid of the mutual recursion. The resulting refactoring helped us to group related pieces which had (for historical reasons) ended up scattered. It also cut our rebuild time dramatically, and let us do cross-module inlining and optimization safely. In short, using mutual recursion was probably a bad idea, and we found we were better off without it. -Jan-Willem Maessen ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mutually recursive modules
Alastair: A crude approach is to assume the type (\forall a. a) for any function with no prototype Andreas: Huh? How can that ever be sound? You're right, it's not - my mistake. I guess that leaves two options: 1) Insist on a prototype for any exported function. 2) Insist on a prototype for any imported function which is used. The latter is more in keeping with Haskell's lazy checking of import clashes. (There's a third option where you assume a type which you don't know anything about like (\exists a. a) but I'd be surprised if this let you typecheck any more useful programs.) -- Alastair ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mutually recursive modules
G'day all. Quoting Henning Thielemann [EMAIL PROTECTED]: Why can't GHC and Hugs go this way? As Alastair noted, the problem is that Haskell allows you to export symbols from a module whose types are unknown unless you type-check modules that it imports. Simple example: module A where import B a = b module B where import A b = a This is only a problem for exported symbols which have no type declarations. As Alastair said: I guess that leaves two options: 1) Insist on a prototype for any exported function. 2) Insist on a prototype for any imported function which is used. The latter is more in keeping with Haskell's lazy checking of import clashes. That's true, but you have to ask why you're exporting a function if you're not going to use it. On the other hand, in the presence of Haskell's export everything feature, it makes a certain amount of sense. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe