- Haskell-Cafe - Haskell.org

Avoiding name collisions by using value spaces instead of modules
by Brian Hulley 18 Jan '06

18 Jan '06

Hi - A main problem I've found with Haskell is that within a module, too many things are put into the same scope. For example data Tree a b = Leaf a | Node {elem::b, lhs::Tree a b, rhs::Tree a b} puts Leaf, Node, elem, lhs, and rhs, into the module's namespace, as well as Tree. This means that if you want another kind of tree in the same module you've got to try and think of another word for Leaf, or else prefix every value constructor with some prefix of the tycon to try and prevent name collisions. I propose that the above declaration should introduce a *new module* Tree, as a sub module of the containing module, and Leaf, Node, elem etc will be put into this module, and not the module containing the data declaration itself. Identifiers in this child module could then either be used qualified or unqualified as long as they don't conflict with anything in the parent (containing) module, thus in the parent module, we could have: a = Tree.Leaf 3 b = Node{elem = 6, lhs = Leaf 2, rhs = Leaf 3} c = Tree.elem b c = b^elem where ^ is just a helpful sugar which binds tighter than function application and can be used anywhere to allow an "object oriented" way of thinking where the first arg is put on the left of the function (more on this later). Also, we could generalise the GHC GADT style data declarations by allowing any declarations to appear in the where part, and allow modules to consist of a single data declaration (ie begin with the keyword data instead of module) so that the contents of the Data.Set module would instead be something like: data Ord a => Set a = .... where insert :: Set a -> a -> Set a ... This would allow Set to be imported qualified into other modules where we could refer to the Set type by the single word Set instead of Set.Set (which I always think looks very strange indeed) ie module M where import qualified Data.Set as Set f :: a -> Set a -- no longer need to write a -> Set.Set a In fact, the whole complexity asociated with hiding components of a module and allowing unqualified imports could be discarded, since the correct resolution for each identifier would be determined by its typed context, just as in OOP the resolution is determined by the type of the object. So to summarise so far, for any value f :: T0 -> T1 -> ... -> Tn, we construct the tuple (Q0, Q1, ... Qn) where for each i, Qi is obtained from Ti by ignoring all predicates and quantification and replacing each tyvar by the symbol '?'. For example, for module M where foo :: forall b. Eq a => Set (Tree a) -> Tree ([a],b) -> [Tree (a,b)] we ignore the forall and Eq, and replace tyvars and tuple the results to get: M.(Set (Tree ?), Tree ( (,) ( [] ?) ?), [] (Tree ( (,) ? ?))).foo as the fully qualified reference to the entity we've just declared. If we call the tuple (Set, ...) the "ty-tuple", which specifies a space of values (ie something that each value is considered to "belong" to - the analogue of the object in OOP), then we can define a projection from a space into a containing space as follows: 1) Let Qi == Ui Si0 Si1 ... Sik be any element of a ty-tuple P. Then we can form a new ty-tuple P' by replacing Qi by Ui. 2) Let Qi be any element of a ty-tuple P of arity n+1. Then we can form P' == (Q0, ..., Qi-1, Qi+1, ... Qn) of arity n In both cases, we can use P' to qualify the identifier to get a value reference as long as this still has enough information for disambiguating other uses of the identifier in M. Applying these transformations of the ty-tuple to the example above, any of the following could be used as a partial qualification of foo in M: (Set Tree, Tree ([],?), [Tree]).foo (Set, Tree, []).foo Tree.foo foo Rule 2 allows us to propagate identifiers back up to their ancestor modules as long as there are no conflicts along the way. The type inference algorithm could then be modified (I hope) to use the top-level annotation for a value declaration to determine the entities that identifiers refer to, by searching in the appropriate value spaces determined by the types of the args and return value. label :: Tree a -> Int -> (Tree a, Int) label (Leaf x) i = (Leaf i, i+1) The identifier Leaf is resolved in the current namespace augmented by the namespace for module Tree, thus we don't have to explicitly write Tree.Leaf even though the declaration of label occurs outside the Tree module itself. (I suggest that top-level type annotations should be mandatory since without them one just drowns in a sea of TI confusion when there is a type error. By making them mandatory the TI algorithm could make real use of them to resolve identifier bindings as in OOP) Similarly: foo :: a -> Set a foo x = singleton x There is no need to say Set.singleton x, because we know that the result of foo has type Set a therefore we search in the current module augmented by the contents of the Set module (every type is also a module) for a binding for "singleton" which maps from a to Set a. Finally (apologies for this long post), returning to the use of ^ to allow an object oriented way of thinking consider: insert :: a -> Set a -> Set a ps = singleton 3 qs = insert 4 ps rs = ps^insert 4 When resolving "insert" used in the binding for rs, the compiler should see that we are looking for some function Set Int -> Int -> Set Int, and hence will be looking in the current module augmented by the Set module. However the Set module only has a binding for insert with type a -> Set a -> Set a. So the compiler should generate a new function insert' from insert by moving the first Set a arg to the front. Summary: 1) Every value binding belongs to a value space represented by a ty-tuple which abstracts away from the details of the actual type 2) The space of ty-tuples forms a lattice, and in particular this means qualification is optional when there are no conflicts (we can use Leaf 3 instead of Tree.Leaf 3), and we can use partial qualification to supply just the disambiguation info needed. 3) The TI algorithm should use the type of the expression (generated top-down from the top-level annotation) to search in the correct value spaces to resolve identifiers 4) Record field selection doesn't need any special scoping rules, and is just one example of a general object-oriented way of thinking about function application. 5) We can get all the advantages of automatic namespace management the OOP programmers take for granted, in functional programming, by using value spaces as the analogue of objects, and can thereby get rid of complicated import/export directives and improve code readability with less typing (but making more use of typing - excuse the pun :-)) I'm in the process of trying to implement a pre-processor for Haskell which would use the algorithms sketched above (as well as fixing a few other things I think are wrong with Haskell such as the way the current layout rule allows one to write code that would break if you replaced an identifier with one that had a different number of characters in it etc), so any feedback on these ideas would be welcome. Thanks for reading so far! Brian Hulley PS Everything above is purely intended for resolving the kind of ad-hoc overloading that is not amenable to treatment by type classes (which transforms some subset of the ad-hoc-overloaded functions which share the same shape into a single function with implicit dictionary arguments (in the usual implementation)).

5 16

Yet another top-level IO proposal
by Robert Dockins 18 Jan '06

18 Jan '06

Fellow haskellers, I have a proposal I would like to enter into the eternal top-level IO debate. The proposal involves a minor language extension and some runtime support for thread local reference cells. I believe it has the potential to meet many of the needs of those requesting top level IO. My apologies for this rather lengthy message, but given the volatility of discussion on this matter in the past, it seemed best to lay out my thoughts as precisely as possible at the beginning. So without further ado, the proposal. The language extension: -- Add a new keyword 'threadlocal' and a top level declaration with the syntax threadlocal <identifier> <type expression> <initializer expression> -- The declaration consists of three parts 1) the name of the reference cell 2) the type of data stored in the cell and 3) an initializer action. -- The name of the cell declared with 'threadlocal' shares the function namespace and introduces a CAF with the type 'TLRef a', where 'a' stands for the type given in the declaration. -- The initializer action must be an expression with type 'TL a', where 'a' stands for the the type given in the 'threadlocal' declaration, and 'TL' is the thread-local initialization monad (a little like the ACIO monad, more on this below). The semantics: -- Each thread in a program (the main thread and threads sparked from forkIO and forkOS) has a "bank" of thread local variables. Writes to and reads from a thread- local cell are only written to/read from the bank of the thread performing the write/read. -- For any given bank, a thread-local cell may be "empty" (which means it holds no value) or "full" with a value of its declared type. -- There is a phantom bank of thread-local values belonging to no thread in which the value of all thread-local cells is "empty". This represents the state of thread local variables before program start. -- Whenever a thread is sparked (including the main thread) and before it begins executing, its thread-local variables are initialized. For each declared thread-local variable (in the transitive closure of imported modules), the declared initilzation action is run and the generated value initializes the thread-local cell for that thread. The initializer actions are run in an unspecified order. -- The primitives of the TL are strictly limited and include only actions which have no observable side effects (a proposed list of primitives is listed below). A TL action may read from (but NOT write to) thread-local cells in the bank of the sparking thread (the bank of the thread calling forkIO, or the special phantom bank for the main thread). -- Any exceptions generated during a thread-local initilization action are propigated to the thread which called forkIO/forkOS or, in the case of the main thread, directly to the runtime system just as though an uncaught exception bubbled off the main thread. -- New IO primitives are added to read from, write to and clear (set to empty) thread-local variables. Advantages: This proposal seems to hit most of the use cases that I recall having seen (including the very important allocate-a-top-level-concurrency-variable use case) and seems to provide a nice way to reinterpret some of the "magic" currently in the standard libraries. In addition, this proposal does not suffer from the module loading order problem that some previous proposals have; because thread local initializer actions depend only on the "previous" bank of values, the order in which they are run makes very little difference (only for the primitives that read clock time or some such). The value of a thread-local cell is always well-defined, even before the main thread starts. Values in a thread-local have a well defined lifetime that is tied to the owning thread. I think that efficient implementation is possible (maybe we can play some copy-on-write games?). I especially like that variables are only as "global" as desired for any given task; if a library writer uses thread-locals for some manner of shared "global" state, later users are always able to write programs that use more than one instance of the "global" state without needing to alter the library. Disadvantages: Requires a language extension (but I don't know of a serious alternate proposal that doesn't). Requires non-trivial runtime system support. Not sure what effect this has on garbage collection. Adds overhead to thread creation (this could perhaps be mitigated by introducing new primitives that distinguish heavyweight threads with their own thread-local banks from lightweight threads, which do not have separate thread-local banks). Its a bit complicated. You can shoot yourself in the foot (true of most of the other proposals). Some representative use cases: -- Implicit parameter style use case: You want to provide a default value that you expect will be rarely changed. Threading the parameter deeply through the code obsfucates meaning and the code is in the IO monad. Solution: * Define a thread-local variable for the value and set the initializer to set the variable to some default value if it was empty, or to copy the parent thread's value otherwise. * If desired, change the variable's value early in main (before any other threads are sparked); the new value will be propagated to all new threads and be available in main. * If desired, different threads can set different values of the parameter which will then be propagated to their sub-threads. -- Top level synchronization variable use case: You need an MVar to manage some "global" resource. Solution: * Define a thread-local variable to hold the MVar. Define the initializer to create a new MVar if the TLRef was empty, and to copy the parent thread's value otherwise. * Read the MVar from the thread-local var, and use it as usual. * Also, allows you to partition the program into sandboxes which use distinct MVars to manage distinct pools of the "global" resource without needing to change or complicate any underlying libraries. -- Running time statistics use case: You want to easily keep track of how long each thread in a program has been running in wall-clock time. Solution: * Define a thread-local variable with an initializer that reads the current wall-clock time. * Calculate the thread running time by taking the difference between the current wall-clock time and the time in the thread-local var. -- Give better semantics to standard handles use case: You want to make the handling of stdin, stdout and stderr in System.IO less "magic" and baked-in. Solution: * Define a thread-local variable for each of stdin, stdout, and stderr. The initializer action creates appropriate handles for each one in the case that the thread-local was empty, and copies the parent's value otherwise. * Nice feature: allows you to override the values of stdin, stdout and stderr for sub-threads, shell style. -- Give better semantics to getArgs use case: You want getArgs/withArgs and getProgName/withProgName to have better semantics. Solution: * Define a thread-local variable for the list of arguments and for the program name. Define an initializer which reads these values from C land when the thread-local value is empty and copies the parent thread's value otherwise. * Allows you to spark multiple threads in a single program with different "command line" arguments. The proposed list of new primitives: -- thread-locals maintained by the standard libs currentWorkingDirectory :: TLRef FilePath stdin :: TLRef Handle stdout :: TLRef Handle stderr :: TLRef Handle -- in the TL monad readTL :: TLRef a -> TL a -- ^ Reads a thread-local variable in the bank of the parent thread. -- Returns bottom if the cell is empty. tryReadTL :: TLRef a -> TL (Maybe a) -- ^ Reads a thread-local variable in the bank of the parent thread. -- Returns Nothing if the cell is empty. getClocktimeTL :: TL ClockTime getCPUTimeTL :: TL Integer getDefaultStdinHandle :: TL Handle getDefaultStdoutHandle :: TL Handle getDefaultStderrHandle :: TL Handle getDefaultArgs :: TL [String] getDefaultProgramName :: TL String newIORefTL :: a -> TL (IORef a) newMVarTL :: a -> TL (MVar a) newEmptyMVarTL :: TL (MVar a) newSTRefTL :: a -> TL (STRef a) -- in the IO monad readThreadLocal :: TLRef a -> IO a -- ^ bottom on empty tryReadThreadLocal :: TLRef a -> IO (Maybe a) -- ^ Nothing on empty writeThreadLocal :: a -> TLRef a -> IO () clearThreadLocal :: TLRef a -> IO () -- ^ Reset the thread-local to empty clearBank :: IO () -- ^ Clear all thread-local cells in the current thread ------------------------------------------------------------------------ ---------------- In order to get discussion flowing and experiment with the semantics I have put together a demonstration module which implements thread-local variables using the standard "unsafePerformIO" hacks. The module and an example usage are attached. If there is any interest in these ideas, I will post this proposal to the wiki. Please respond with thoughts and comments, Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG

2 2

Space usage problems
by Ian Lynagh 18 Jan '06

18 Jan '06

Hi all, I am having space issues with some decompression code; I've attached a much simplified version as Test1.hs. At the bottom (foo/bar) is the equivalent of deflate. This should be a standalone module which doesn't know about the rest. In the middle (readChunks) is the equivalent of gunzip. It repeatedly calls foo until there is no more input left. At the top is a simple main function that calls them. If I do dd if=/dev/zero of=data bs=1000 count=3000" # making data around 3MB ghc --make Test1 -o Test1 -O -Wall ./Test1 then in top I see Test1 increasing memory usage to around 150MB. I think this is because the "let (ys, zs) = foo xs" means zs holds on to xs (it's hard to be sure as compiling for profiling is too happy to change the behaviour). I tried (Test2) changing foo to be a monad transformer over the calling monad, so the caller's remaining input was updated as we went along, but (as well as memory usage not obviously being fixed) this is giving me a stack overflow. Has anyone got any suggestions for making a constant space, constant stack version? Thanks Ian

5 11

libtiff
by Green Bryan - bgreen 18 Jan '06

18 Jan '06

Does anyone know of libtiff having been wrapped for Haskell? If not, where could I find a good tutorial on wrapping a c library with functions that have variable argument parameters? Thanks, Bryan Green *************************************************************************** The information contained in this communication is confidential, is intended only for the use of the recipient named above, and may be legally privileged. If the reader of this message is not the intended recipient, you are hereby notified that any dissemination, distribution or copying of this communication is strictly prohibited. If you have received this communication in error, please resend this communication to the sender and delete the original message or any copy of it from your computer system. Thank You. ****************************************************************************

2 1

Shootout favouring C
by Daniel Fischer 18 Jan '06

18 Jan '06

Hi, Is it only my machime, or can you confirm that for the Ackermann benchmark, it's very good for C that they chose 9 and not a larger value? For 10, we are significantly faster and for 11,12,13, we can run rings around the C-programme: dafis@linux:~/Documents/haskell/shootout> time ./cacker3 10; time ./acker 10; time ./cacker3 11; time ./acker 11; time ./cacker3 12; time ./acker 12 Ack(3,10): 8189 real 0m0.664s user 0m0.660s sys 0m0.010s Ack(3,10): 8189 real 0m0.405s user 0m0.400s sys 0m0.000s Ack(3,11): 16381 real 0m6.255s user 0m6.220s sys 0m0.000s Ack(3,11): 16381 real 0m1.731s user 0m1.710s sys 0m0.000s Ack(3,12): 32765 real 0m35.270s user 0m35.050s sys 0m0.000s Ack(3,12): 32765 real 0m10.673s user 0m10.590s sys 0m0.000s dafis@linux:~/Documents/haskell/shootout> time ./acker 13; time ./cacker3 13 Ack(3,13): 65533 real 1m4.476s user 1m4.050s sys 0m0.010s Ack(3,13): 65533 real 2m50.645s user 2m47.020s sys 0m0.020s Cheers, Daniel

8 19

Db and STRef
by Brandon Moore 16 Jan '06

16 Jan '06

John Goerzen wrote: ... > I didn't honestly follow the STRef discussion, or how something so > I/O-based could work there. > > -- John The only message I've found was Oleg mentioning the typing that keeps an STRef limited to the scope of the runST it came from. I don't think database access could live in ST either. I think the proposal was to build something like Oleg's Monadic Regions http://okmij.org/ftp/Haskell/types.html#monadic-regions on top of IO I'm assuming you understand how the type on runST and the STRef operations ensure that, even though you *can* smuggle out an STRef in the result from runST, you will never be able to use it again. The idea was to do the equivalent thing with databases: use fancy types to ensure that handle can only be used inside to origination withDB or withCursor or whatever, and the bracketing function can release the resource on the way out, without worrying about it being used again. Brandon > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell

2 2

Shootout rankings
by dons＠cse.unsw.edu.au 16 Jan '06

16 Jan '06

:D Haskell now ranked 2nd overall, only a point or so behind C: http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=all And still a bit more we can squeeze out... -- Don

9 14

Re: What's the current bug report procedure?
by Simon Marlow 16 Jan '06

16 Jan '06

Seth Kurtzberg wrote: > All, > > I have a (minor) but to report in the networking (Network and Network.Socket) libraries. If the /etc/protocols file is missing, an error message is printed saying that a service could not be found. This occurs even when no service is involved (the port number is specified explicitly using the constructor PortNumber). > > I'm aware that the procedure changed; can you point me at the right place to report this and/or the right people/bug tracker/whatever? > > Thanks, > Seth Kurtzberg I believe that's been fixed, but the place to report bugs in the network library is currently the GHC bug tracker, at http://www.haskell.org/ghc/reportabug. Cheers, Simon

1 0

please send your cabal bug reports, wishlist, and patches!
by Isaac Jones 16 Jan '06

16 Jan '06

Greetings, I'm trying hard to get a better hold on the Cabal[1] project, and a more clear idea of all the outstanding work that needs to be done. I've gone through my mailbox to dig up stuff like this, but no doubt some has slipped between the cracks. I started a bug tracker / wiki a few weeks ago, and would like your help to make sure that it reflects _all_ of the work that needs to be done in Cabal. If you've sent me a feature request or bug report that hasn't been added to Cabal, can you please check if it is on the wiki, and if not, create a "ticket" (bug report) for it: Cabal Wiki & Bug Tracker: http://hackage.haskell.org/trac/hackage/ If you're not sure, or don't want to use the bug tracker, just email me. This bug tracker is a great place to make more complex feature requests, as it has full wiki markup. See this ticket for a nice example: http://hackage.haskell.org/trac/hackage/ticket/27 Also, if you've sent me any patches that are not yet applied, please re-send them to me. peace, isaac [1] http://www.haskell.org/cabal

1 0

formal methods & functional programming
by Abigail 16 Jan '06

16 Jan '06

Hi, I have been searching papers about tha raltionship between formal methods in software engineering and functinal programmming, but i haven't found enough information. can u hel me?. Thanks Abigail. __________________________________________________ Correo Yahoo! Espacio para todos tus mensajes, antivirus y antispam ¡gratis! Regístrate ya - http://correo.espanol.yahoo.com/

6 6