- Haskell-Cafe - Haskell.org

uvector package appendU: memory leak?
by Manlio Perillo 01 Apr '09

01 Apr '09

Hi. As with a previous post, I think I have found a possible memory problem with the uvector package. I have this data structure (for, again, my Netflix Prize project): IntMap (UArr (Word16 :*: Word8)) I was adding elements to the map using something like: v = map singletonU (a :*: b) insertWith appendU k v m However doing this eats a *lot* of memory. Today I have rewritten my program to use `alter` and `snocU`: append Nothing = Just $ singletonU (a :*: b) append (Just u) = Just $ snocU u (a :*: b) alter append k m This, finally, works. Unfortunately I'm still not able to load the entire Netflix Prize training data set, grouping ratings by customers, because my PC has only 2 GB of RAM. The required memory is about 2 GB, but when the system start to swap, I have to kill the program. So the question is: why appending an array of only one element to an existing array causes memory problems? This should be pratically the same as adding an element. Thanks Manlio

4 16

TMVar's are great but fail under ghc 6.10.1 windows
by Alberto G. Corona 01 Apr '09

01 Apr '09

Control.Concurrent.STM.TMVar's combine the best of MVars and TVars: -Unlike TVars, they permit blocking/early retry when the TMVar is being used by other process, so that complete processes are not retried at the end when happens that the TVars have been modified in the meantime. - Unlike MVars, they have no deadlocks, specially when a process is trying to adquire exclusive access to more than one TMVar. however, It happens that fails in my windows box with ghc 6.10.1 , single core here is the code and the results: -----------begin code: module Main where import Control.Concurrent.STM import Control.Concurrent import System.IO.Unsafe import GHC.Conc mtxs= unsafePerformIO $ mapM newTMVarIO $ take 5 $ repeat 0 proc i= atomically $ do unsafeIOToSTM $ putStr $ "init of process "++ show i++"\n" xs<- mapM takeTMVar mtxs mapM (\(mtx,x) ->putTMVar mtx (x+1)) $ zip mtxs xs xs' <- mapM readTMVar mtxs unsafeIOToSTM $ putStr $ "End of processs "++show i ++ " result= "++ show xs'++"\n" main=do mapM (forkIO . proc) [1..5] threadDelay 100000000 -------------end code the rigth result must be (occasionally with some "init of process x" repeated) init of process 1 init of process 2 End of processs 1 result= [1,1,1,1,1] init of process 2 -- retried End of processs 2 result= [2,2,2,2,2] init of process 3 End of processs 3 result= [3,3,3,3,3] init of process 4 End of processs 4 result= [4,4,4,4,4] init of process 5 End of processs 5 result= [5,5,5,5,5] under windows the program produces strange results for example init of process 1 init of process 2 init of process 3 init of process 4 init of process 5 End of processs 1 result= [1,1,1,1,1] End of processs 2 result= [1,1,1,1,1] (deadlock) or this other: init of process 1 init of process 2 init of process 3 init of process 4 init of process 5 End of processs 1 result= [1,1,1,1,1] End of processs 2 result= [1,1,1,1,1] init of process 3 init of process 4 init of process 5 init of process 2 End of processs 4 result= [2,2,2,2,2] End of processs 3 result= [2,2,2,2,2] End of processs 5 result= [2,2,2,2,2] End of processs 2 result= [2,2,2,2,2] init of process 3 init of process 5 init of process 2 End of processs 3 result= [3,3,3,3,3] End of processs 5 result= [3,3,3,3,3]

3 2

Google Summer of Code student application deadline approaches
by Johan Tibell 31 Mar '09

31 Mar '09

Hi, The Summer of Code student application deadline is April 3rd and we need more applications! If you have an idea that you would like to hack on this summer hurry up and apply. Here's an idea that could be implemented in a summer: A Sawzal [1]l like library that processes large volumes of data using monoids to compute aggregate statistics. Foldable makes this possible for smaller data sets than can fit in memory but many interesting data sets are tens or hundreds of gigabytes in size. A simple API with a high performance implementation would make Haskell a nice data analysis tool. Here's a strawman interface for such a library: -- | Given a file of log records compute aggregate statistics by converting each record -- to a monoid @m@ and combine the resulting monoids using 'mappend'. fold :: (Record r, Monoid m) => (r -> m) -> FilePath -> IO m There are lots of interesting optimizations that could be done. Starting with an efficient single threaded implementation using ByteString you could add the ability to either process many files in parallel or splitting one file into many chunks and process each chunk in parallel. The Wide Finder 2 [2] challenge has a fast Ocaml implementation of the latter strategy. One could take the library further by running the processing on multiple machines like in the Google Sawzall implementation. 1. http://research.google.com/archive/sawzall.html 2. http://www.tbray.org/ongoing/When/200x/2008/05/01/Wide-Finder-2 Cheers, Johan

1 0

satchmo: monadic SAT encoding library
by Johannes Waldmann 31 Mar '09

31 Mar '09

Dear all, I am releasing a preliminary version of "satchmo", a monadic library for encoding boolean and integral number constraints to CNF-SAT. It uses minisat (http://minisat.se/) as a backend solver. http://dfa.imn.htwk-leipzig.de/satchmo/ http://hackage.haskell.org/cgi-bin/hackage-scripts/package/satchmo Enjoy - J.W. PS: what would be the proper top level hackage module name for this? I guess it could be Constraint.SAT.Encoding ...

1 0

Re: [Haskell-cafe] abou the Godel Numbering for untyped lambda calculus
by Dan Weston 31 Mar '09

31 Mar '09

DISCLAIMER: The last I studied this was over 20 years ago, so my brain is seriously rusty. You are warned... > you mean the godel function (denoted by # and generally will be in type, > #:term -> number ?) is a kind of functions instead of a particular > function? No. The Godel mirror function (as defined by Godel) is a single function, the product of primes (whose ordering gives the position in the string) with exponents (giving the symbol at that position). However, I think any total injective function with partial injective inverse will do. Don't get hung up on the details of the mirroring (Godel doesn't). Once you accept that it can be done, there is no need to actually do it. There is nothing magic about integers, beyond the fact that elementary arithmetic is "well understood" by humans and should not have inconsistencies (it probably doesn't, but we can't prove it within any language more intuitive than arithmetic, so why should be believe the proof in that language?). Importantly, all but the last step of the proof can be encoded as primitive recursive functions, meaning that they always halt within a predetermined number of steps (satisfying the Finitists). Only the last step cannot be so limited. This is a clear example where non-finite mathematics has demonstrably more power in a fundamentally important way. Why bother going through this encoding? The main reason for the encoding is to overcome the fundamental limitation of structural induction whereby there is no "this" smaller than this. I.e. quoting a sentence only makes it longer. With functions on integers, this limitation is removed, so that although there is no string saying "This statement is not true", (since "This statement" != "\"This statement is not true\""), there *is* some function taking the Godel number of the unquoted This to the Godel number of the string to which it refers. Doing so takes some bit of cleverness, but the original proof in German is only about 8 pages long, as I recall. If we don't go with mirroring and just use strings, we need to introduce some equivalent trick, namely named functions. In a language without pointers and only lambda expressions, there is no way to refer to oneself without repeating the quote in infinite regression. For instance "\x -> 3333333" is longer than "333333". You cannot talk about a string without embedding it as a substring. However, once you add named functions to your metalanguage (Haskell): f 3 = 33333333 Then the string "f 3" is shorter than the string "xxxxxxx". Suppose f 4 = "~xxxxxxx". Now one can talk about the other with the shorter string on the left: length "f 3" < length "~xxxxxxx" but also length "f 4" < length "xxxxxxx". A longer string can talk about a shorter string (but not vice versa), so this mapping is critical to overcoming the limitation about talking about oneself. After that, the rest is easy: encode the Liar's Paradox and voila. once we have the encoding of a language, and construct functions to encode proof transformations, we can reduce derivability to a simple predicate derivable :: String -> Bool and look for some formula f such that derivable (f) == False and derivable("~" ++ f) == False. Godel's First Incompleteness Theorem merely says that there is some integer (which mirrors some well-formed formula) not in the set of integers that mirror "derivable theorems", making your system incomplete. Moreover, if you remedy this situation by adding this integer to the set as an axiom, you immediately can derive another integer which mirrors its negated formula, making your system inconsistent. The metasystem (with symbols for derivable, transformation rules like modus ponens, and the like), are not part of the formal system, but in the metalanguage. By encoding this metalanguage as well and redoing the above, you get Godel's Second Incompleteness Theorem, which says that no system can prove its own consistency, and if an axion is added to assert consistency, you can immediately also prove its negation, making it unsound. Don't look for a hat trick. Encoding the meta-meta-system buys you nothing extra. That's about all I can remember without hypnosis, and I'm afraid of what I might say under hypnosis... :) Dan Algebras Math wrote: > you mean the godel function (denoted by # and generally will be in type, > #:term -> number ?) is a kind of functions instead of a particular > function? If so, what kind of property this kinds of functions have? any > limitation? how capable they will be? > > Thanks > > alg > > On Tue, Mar 31, 2009 at 4:01 AM, Dan Weston <westondan(a)imageworks.com > <mailto:westondan@imageworks.com>> wrote: > > I can't tell exactly what you're asking, but I'll give it a try! :) > > primes :: [Integer] > primes = [2,3,5,7,11,13,17,19,23,29,31,undefined] > > godel :: String -> Integer > godel = product . zipWith (^) primes . map (toInteger . ord) > > -- Here is the identity function (note that double backslash is a > single character > godel "\\x -> x" > 1629920514342441477851613634029704631135430980107335428017064836156091059806450516131002598452000651374890570022191128551421788559667251656959733380229796871976693176094558797489489057311763922507760911447493016261397754567695234219623056037447490713525815311253273691703346455275115486717580778238094808661626709709766328915159206002675716287759792707200037683200000000000000000000000000000000 > > -- = 2^92 * 3^120 * 5^32 * 7^45 * 11^62 * 13^32 * 17^120 > > ungodel :: Integer -> String > -- ungodel . godel = id > > (See http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic > for why this works). > > These numbers get large quickly, but are finite for any finite > string of finite alphabet. > > godel is a total function (every string has a unique integer), and > its inverse (an exercise to the reader involving prime factor > decomposition) would also be total if the alphabet were infinite (so > that ord would be total). > > Frankly, I wouldn't know how to begin encoding the godel numbering > in the type system (shudder!), but being that it is a total > primitive recursive function, I suppose there is no theoretical > impediment. > > In contrast, Godel's Theorems themselves cannot be so encoded > because the last step involves a general recursive function. > > Dan > > > Algebras Math wrote: > > Hi all, > > I am reading the book "The lambda calculus: Its syntax and > Semantics" in the chapter about Godel Numbering but I am > confused in some points. > > We know for Church Numerals, we have Cn = \fx.f^n(x) for some > n>=0, i.e. C0 = \fx.x and C1 = \fx.fx. > > From the above definition, I could guess the purpose of this > kind of encoding is trying to encode numeral via terms. > > How about the Godel Numbering? From definition we know people > say #M is the godel number of M and we also have [M] = C#M to > enjoy the second fixed point theorem : for all F there exists X > s.t. F[X] = X. > > What the mapping function # is standing for? How could I use it? > What the #M will be? How to make use of the Godel Numbering? > > Thank you very much! > > alg > > >

1 0

ANNOUNCE: vacuum: extract graph representations of ghc heap values. (take 2)
by Matt Morrow 31 Mar '09

31 Mar '09

I am pleased to announce the release of vacuum, a library for extracting graph representations of values from the GHC heap, which may then be further processed and/or translated to Graphviz dot format to be visualized. The package website is at http://moonpatio.com/vacuum/ , which contains a gallery section (which i hope to add to over time). The most recent version is 0.0.6, which is available on Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/vacuum/ . Feedback, comments, and gallery submissions will be gratefully received via this email address (contrary to the email address currently on the vacuum Hackage page (i fail at setting up email :)). Matt

2 1

[Probably a dumb question] Quasiquoting
by Andrew Coppin 31 Mar '09

31 Mar '09

Can somebody explain to me how [$expr| 1 + 2 |] is different from ($expr "1 + 2") Other than a superficially different type signature, I'm not seeing what the fundamental difference is...

2 3

Haddock: inserting interactive sessions in the documentation
by Manlio Perillo 31 Mar '09

31 Mar '09

Hi. What is the suggested (if any) convention for inserting an interactive session in the documentation? Right know I'm doing (in random-shuffle package): -- |Convert a sequence @(e1...en)@ to a complete binary tree. -- -- @ -- System.Random.Shuffle> buildTree ['a','b','c','d','e'] -- Node 5 (Node 4 (Node 2 (Leaf 'a') (Leaf 'b')) -- (Node 2 (Leaf 'c') (Leaf 'd'))) -- (Leaf 'e') -- @ buildTree :: [a] -> Tree a As an example, in Python we use """ >>> 3 + 2 5 """ One nice feature of this special syntax is that it can be parsed, using doctest. Thanks Manlio

2 2

type-level programming support library
by spoon 31 Mar '09

31 Mar '09

I've been doing some basic work on a support library for type level programming ( see http://hackage.haskell.org/trac/summer-of-code/ticket/1541 ). I know there have been similar attempts using fundeps ( Edward Kmett showed me some of his work, but I've lost the address... ) but this approach uses type families. Anyway, I would like to hear your critique! Currently I have higher order type functions and ad-hoc parametrized functions. Here's what foldl looks like: type family Foldl ( func :: * -> * -> * ) val list type instance Foldl func val ( Cons first rest ) = Foldl func ( Eval ( func val first ) ) rest type instance Foldl func val Nill = val Notice the use of Eval - this is a trick to enable us to pass around data with kind * -> *, or whatever, and then trip this into becoming a value. Here's an example, using this trick to define factorial: -- multiplication type family Times x y type instance Times x Zero = Zero type instance Times x ( Succ y ) = Sum x ( Times x y ) -- The "first order" function version of Times data TimesL x y -- Where what Eval forced TimesL to become. type instance Eval ( TimesL x y ) = Times x y -- multiplies all the elements of list of Nat together type Product l = Foldl TimesL ( Succ Zero ) l -- here list to creates a list from ( Succ Zero ) to the given number type Factorial x = Product ( ListTo x ) We can now use the function like this: *TPrelude> result ( ) :: Factorial ( Succ ( Succ ( Succ ( Zero ) ) ) ) Succ (Succ (Succ (Succ (Succ (Succ Zero))))) Using the parametrized types kinda reminds me of programming in Erlang: -- What would conventionally be the monad type class, parametized over m type family Bind m ma ( f :: * -> * ) type family Return m a type family Sequence m ma mb Here's the maybe monad: -- Monad instance type instance Bind ( Maybe t ) Nothing f = Nothing type instance Bind ( Maybe t ) ( Just a ) f = Eval ( f a ) type instance Sequence ( Maybe t ) Nothing a = Nothing type instance Sequence ( Maybe t ) ( Just a ) b = b type instance Return ( Maybe t ) a = Just a type instance Eval ( Just x ) = Just x Here's an example: *TPrelude> result ( ) :: Bind ( Maybe Nat ) ( Just Zero ) Just Just Zero For more information and to download the loose collection of module implementing this please see: http://www.killersmurf.com/projects/typelib John Morrice

7 11

GHC on AIX
by nitralime 31 Mar '09

31 Mar '09

Hi, I have tried to install the newest available binary distribution of GHC for AIX (6.8.2). Unfortunately, it didn't work properly. Following the trivial installation steps as described in INSTALL file I executed the following commands: 1) ./configure --prefix=/home/nik/local 2) gmake install But I got the following error message: -------------------------------------------------------------------------------------------------------------------------------------- .... Reading package info from stdin ... done. warning: can't find GHCi lib HSrts.o Saving old package config file... done. Writing new package config file... done. /tmp/ghc-6.8.2/utils/mkdirhier/mkdirhier /home/nik/local/ghc-6.8.2/lib/ghc-6.8.2 for i in libHSrts*.a ; do \ case $i in \ *.a) \ /tmp/ghc-6.8.2/install-sh -c -m 644 $i /home/nik/local/ghc-6.8.2/lib/ghc-6.8.2; \ : /home/nik/local/ghc-6.8.2/lib/ghc-6.8.2/`basename $i` ;; \ *.dll) \ /tmp/ghc-6.8.2/install-sh -c -m 644 -s $i /home/nik/local/ghc-6.8.2/lib/ghc-6.8.2 ;; \ *.so) \ /tmp/ghc-6.8.2/install-sh -c -m 755 $i /home/nik/local/ghc-6.8.2/lib/ghc-6.8.2 ;; \ *.dylib) \ /tmp/ghc-6.8.2/install-sh -c -m 755 $i /home/nik/local/ghc-6.8.2/lib/ghc-6.8.2; \ install_name_tool -id /home/nik/local/ghc-6.8.2/lib/ghc-6.8.2/`basename $i` /home/nik/local/ghc-6.8.2/lib/ghc-6.8.2/`basename $i` ;; \ *) \ /tmp/ghc-6.8.2/install-sh -c -m 644 $i /home/nik/local/ghc-6.8.2/lib/ghc-6.8.2; \ esac; \ done gmake[1]: Leaving directory `/tmp/ghc-6.8.2/rts' gmake -C libraries install DOING_BIN_DIST=YES gmake[1]: Entering directory `/tmp/ghc-6.8.2/libraries' if ifBuildable/ifBuildable base; then \ cd base && \ ../installPackage/installPackage '/tmp/ghc-6.8.2/utils/ghc-pkg/ghc-pkg.bin' '/home/nik/local/ghc-6.8.2/lib/ghc-6.8.2/package.conf' '/home/nik/local/ghc-6.8.2' '/home/nik/local/ghc-6.8.2' '/home/nik/local/ghc-6.8.2/bin' '/home/nik/local/ghc-6.8.2/lib/ghc-6.8.2/lib' '/home/nik/local/ghc-6.8.2/lib/ghc-6.8.2/lib' '/home/nik/local/ghc-6.8.2/share/ghc-6.8.2' '/home/nik/local/ghc-6.8.2/share/doc/ghc/libraries/$pkg' '/home/nik/local/ghc-6.8.2/share/doc/ghc/libraries/$pkg' '/home/nik/local/ghc-6.8.2/share/doc/ghc/libraries/$pkg' ; \ fi Installing: /home/nik/local/ghc-6.8.2/lib/ghc-6.8.2/lib/base-3.0.1.0 gmake[1]: *** [install.library.base] Error 127 gmake[1]: Leaving directory `/tmp/ghc-6.8.2/libraries' gmake: *** [install] Error 2 -------------------------------------------------------------------------------------------------------------------------------------- Am I missing something? Any help is very much appreciated! Regards Nik

1 0