June 2005 - Glasgow-haskell-users

RE: Bignums in Haskell
by Simon Peyton-Jones 22 Jun '05

22 Jun '05

There's nothing inherently imperative about bignums. The current algorithms may have an imperative flavour, but that may be partly because that's what suits the implementation language. If the algorithms are divide-and-conquer, perhaps a tree representation would work very nicely. And even in the imperative case there is no reason in principle why a runST-encapsulated imperative algorithm should be slower than C --- although at the moment GHC does not do a consistently good job of compiling imperative code. So I rather agree with John: implementing bignums in Haskell, and trying to make an efficient implementation based on the state of the art on the numerical side (as opposed to just writing the first code that comes into your head), would be an interesting project for someone to try. It might also expose useful optimisations that are missing in GHC or jhc. It's essential to optimise the 'small bignum' case. In practice, most "bignums" easily fit in 32 bits. Simon | -----Original Message----- | From: glasgow-haskell-users-bounces(a)haskell.org [mailto:glasgow-haskell-users- | bounces(a)haskell.org] On Behalf Of Marco Morazan | Sent: 22 June 2005 00:39 | To: karczma(a)info.unicaen.fr | Cc: glasgow-haskell-users(a)haskell.org | Subject: Re: Bignums in Haskell | | This is a rather interesting question. Most "efficient" | implementations use array-based representations for bignums that are | mutable. The use of mutable arrays appears to be justified, because of | divide-and-conquer multiplication and division algorithms (e.g. | Karatsuba) that perform these operations in place. The problem, | however, is not this straighforward. Array-based implementations | require copying bigits into the array. A list-based implementation | simply points to the rest of the bignum avoiding any copying. | | If bignums are immutable structures (as in a true functional data | structure), then we should not be surprised if list-based | representations are as good or better than array-based | implementations. In this case, arrays are forced to copy bigits to new | memory locations while lists can continue to point to pieces of a | bignum. To avoid excessive memory allocation for pure bignums | real-time garbage collection on bignum operations can be used. | | It is certainly a rich and interesting line of research. It also | appears to me that having native support for bignums is desirable. It | would certainly make using bignum libraries seamless. | | Best wishes, | | Marco | | On 6/21/05, karczma(a)info.unicaen.fr <karczma(a)info.unicaen.fr> wrote: | > John Meacham writes: | > | > > I wonder if it would be feasable to implement arbitrary precision | > > integers in pure haskell. unboxed values would probably want to be used | > > in some places for speed and it would be very motivating to improve | > > ghc's optimizer. There should be no reason manually unboxed haskell code | > > should compile slower than C. | > | > Of course, bignums (integers) can be quite nicely implemented in Haskell, | > this is btw. a known student exercise. The implementation is nice, elegant, | > etc., but the efficiency... This is not only having unboxed chunks, but | > also the global policy of memory allocation. Putting number chunks in lazy | > lists involves a substantial overhead. I am not sure how slow it will be, | > since our pedagogic games didn't care at all, but we can try to benchmark | > it one day... | > | > | > Jerzy Karczmarczuk | > | > | > _______________________________________________ | > Glasgow-haskell-users mailing list | > Glasgow-haskell-users(a)haskell.org | > http://www.haskell.org/mailman/listinfo/glasgow-haskell-users | > | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users(a)haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

1 0

RE: Bignums in Haskell
by Simon Marlow 21 Jun '05

21 Jun '05

On 21 June 2005 12:47, Ketil Malde wrote: > Marco Morazan <morazanm(a)gmail.com> writes: > >> Do any of you have insight into why GHC uses GMP as opposed to >> another library for arbitrary precision numbers? > > Did you have any particular other library in mind? I'm not too > well-versed in this, but I think GMP is fairly efficient, well tested > and portable. So why not? Right - that's three reasons to use it. Some reasons *not* to use it are: it has an awkward license, it's big, it needs updating, and we run into problems when the Haskell program wants to use GMP itself via the FFI (it's possible by essentially renaming everything in our local copy of GMP so it doesn't conflict, but we haven't done that). There are other good bignum libraries out there: the one that comes with OpenSSL springs to mind. Cheers, Simon

1 0

Bignums in Haskell
by Marco Morazan 21 Jun '05

21 Jun '05

Hello all, Do any of you have insight into why GHC uses GMP as opposed to another library for arbitrary precision numbers? Also, why would bignums not be directly implemented for the GHC or other implementations of Haskell? Best wishes, Marco

4 3

Error building GHC from darwin ports
by David Menendez 17 Jun '05

17 Jun '05

I currently have GHC installed using darwin ports, and I've been trying to upgrade from 6.4_0 to 6.4_8, but I keep hitting a file-not-found error. Looking at the paths in question, I'm guessing the problem has to do with the path segment "/var/db/dports/build/file._opt_local_var_db_dports_sources_rsync.rsync. opendarwin.org_dpupdate_dports_lang_ghc/work/ghc-bootstrap/" appearing twice. Unfortunately, I don't understand the makefiles well enough to track down where this is happening. I'm running Mac OS X 10.4 with XCode 2.0 and darwinports 1.001. Here are the relevant errors: ----------------------------- /opt/local/var/db/dports/build/file. _opt_local_var_db_dports_sources_rsync.rsync.opendarwin. org_dpupdate_dports_lang_ghc/work/ghc-bootstrap/bin/ghc -M -optdep-f -optdep.depend -osuf o -H16m -O -I/usr/include -I/opt/local/include -L/usr/lib -L/opt/local/lib -cpp -fglasgow-exts -O AbsSyn.lhs First.lhs GenUtils.lhs GetOpt.lhs Grammar.lhs Info.lhs LALR.lhs Lexer.lhs Main.lhs ParseMonad.lhs Parser.hs ProduceCode.lhs ProduceGLRCode.lhs Set.lhs Target.lhs Version.hs /opt/local/var/db/dports/build/file. _opt_local_var_db_dports_sources_rsync.rsync.opendarwin. org_dpupdate_dports_lang_ghc/work/ghc-bootstrap/bin/ghc: line 5: /opt/local/var/db/dports/build/file. _opt_local_var_db_dports_sources_rsync.rsync.opendarwin. org_dpupdate_dports_lang_ghc/work/ghc-bootstrap/var/db/dports/build/file ._opt_local_var_db_dports_sources_rsync.rsync.opendarwin. org_dpupdate_dports_lang_ghc/work/ghc-bootstrap/lib/ghc-6.4/ghc-6.4: No such file or directory /opt/local/var/db/dports/build/file. _opt_local_var_db_dports_sources_rsync.rsync.opendarwin. org_dpupdate_dports_lang_ghc/work/ghc-bootstrap/bin/ghc: line 5: exec: /opt/local/var/db/dports/build/file. _opt_local_var_db_dports_sources_rsync.rsync.opendarwin. org_dpupdate_dports_lang_ghc/work/ghc-bootstrap/var/db/dports/build/file ._opt_local_var_db_dports_sources_rsync.rsync.opendarwin. org_dpupdate_dports_lang_ghc/work/ghc-bootstrap/lib/ghc-6.4/ghc-6.4: cannot execute: No such file or directory gmake[2]: *** [depend] Error 126 gmake[1]: *** [boot] Error 1 gmake[1]: Leaving directory `/opt/local/var/db/dports/build/file. _opt_local_var_db_dports_sources_rsync.rsync.opendarwin. org_dpupdate_dports_lang_ghc/work/ghc-6.4/happy' gmake: *** [/opt/local/var/db/dports/build/file. _opt_local_var_db_dports_sources_rsync.rsync.opendarwin. org_dpupdate_dports_lang_ghc/work/ghc-6.4/happy/src/happy-inplace] Error 2 Warning: the following items did not execute (for ghc): com.apple.destroot com.apple.build Error: Unable to upgrade port: 1 -- David Menendez <zednenem(a)psualum.com> | "In this house, we obey the laws <http://www.eyrie.org/~zednenem> | of thermodynamics!"

2 3

(no subject)
by Amit rohatgi 17 Jun '05

17 Jun '05

hello all, I am new to using ghc . I want to install DARSC and for that i need GHC .. I dont have any old version of Ghc already on the comp so i need the *.hc files from any version 6-?-? to compile ghc. till now i havent been able to locate those files. Please help me to find these files. Hoping for a positive reply Regards Amit --

2 1

ghc 6.4 without libreadline4
by Geoffrey Alan Washburn 16 Jun '05

16 Jun '05

Does anyone have a prebuilt version of ghc 6.4 that works with libreadline5? The generic Linux version on http://www.haskell.org/ghc/download_ghc_64.html requires libreadline4, but the system I am using does not have it installed. Nor am I the administrator, so I can't go installing libraries willy-nilly sadly. Or is really the best solution here to get my administrator to do so? Will building my own version and setting my LD_LIBRARY_PATH work reasonably well too? Thanks.

2 5

RE: testing current 6-4-branch
by Simon Marlow 16 Jun '05

16 Jun '05

On 15 June 2005 11:23, Serge D. Mechveliani wrote: > I am trying to do the following. > > (1) to install the current GHC of 6.4 branch from CVS > with ghc-6.4 for recent Debian Linux. > > (2) To test how ghc-current understands the field > `hs-source-dirs' in a package for multiple subdirectories > (is `hs-source-dirs' in the current GHC ?), > and to test module name clash resolution between the packages. The GHC 6.4 branch does not have hs-source-dirs. You need to checkout the HEAD to get it (but bear in mind that the HEAD is likely to be more unstable than the 6.4 branch). Cheers, Simon

2 1

Generating unique random numbers
by Robert van Herk 15 Jun '05

15 Jun '05

Hello all, Is it possible to generate random numbers that are "unique" in O(1) in Haskell? I mean something like the GUID-thingy Windows uses. Of course, I could create unique numbers by incrementing a global value, but for security reasons I need random numbers. Also, I could use a list of numbers already in use, but this would mean that I'd not be able to generate a new number in O(1). Any ideas? Regards, Robert

4 4

RE: irrelevant package
by Simon Marlow 15 Jun '05

15 Jun '05

On 14 June 2005 10:55, Serge D. Mechveliani wrote: >> When you install a package >> P that includes a module M, you prevent the user from having any >> modules called M unless they say '-hide-package P' > > ? > First, it is very natural to have several common module names among > the installed packages. > > Suppose the user package P depends on P2, P3. To build P, Cabal finds > the minimal needed set S of packages for P. No, Cabal does not do this. > For my particular aforementioned example, this should be sufficient. > Because the packages from S occur not to have common module names, > and ghc-CVS-current will find this. Right? I'm not sure what you mean - we don't find the minimal set of depended-upon packages at all. You are required to explicitly list dependencies in the build-depends field. > Now, suppose, for some another example, it occurs a clash: P2 and P3 > occur in S and the name DPrelude (.hs) is both in P2 and P3 > (and usually these modules have different interface and > implementation). > Probably, the Cabal system needs to warn about this. It's more than just a warning: it's an error. GHC will issue an error message in this case. > But, of course, it is not difficult for Cabal to distinguish these > two modules. Because it is visible that one is P2.DPrelude and > another is P3.DPrelude. > So, before compilation, the modules are resolved. I don't know what P2.DPrelude means. Is it a module name, or are you proposing to prefix module names with package names? You should read recent discussions on the libraries(a)haskell.org mailing list, where this issue has been dissected at some length. Cheers, Simon

1 0

RE: When to run the garbage collector
by Simon Marlow 15 Jun '05

15 Jun '05

On 14 June 2005 10:35, Robert van Herk wrote: > I noticed that it is possible to run the garbage collector > explicitely... > > Currently, I am writing a stateful webserver, that once in a while > (e.g. every 30 minutes) can discard a lot of memory (because every 30 > minutes sessions time out and their state can be thrown away). > > Would it be wise to call the garbage collector explicitely, directly > after this cleanup is done? Sounds reasonable, otherwise it might be a while before a major GC runs. In CVS we have a new idle GC feature: the GC is run automatically after a specified amount of idle time. This might be useful in your case, too. (it is only activated in -threaded mode right now). Cheers, Simon

1 0