- Haskell - Haskell.org

RE: Implicit parameters:
by Simon Peyton-Jones 04 Feb '05

04 Feb '05

| Sent: 19 January 2005 14:42 | Unbound implicit parameter (?global_counter::IORef a) | arising from use of `get_unique' at Test.hs:17:13-22 | | Is this a bug? Is there some reason why this is not possible? (and if it | is not possible | shouldn't the documentation be changed to reflect this)... Keean's program has made me realise (yet again) that implicit parameters are a bit different to class constraints. Consider module Main where main = let ?x = 5 in print foo foo = woggle 3 woggle :: (?x :: Int) => Int -> Int woggle y = ?x + y GHC's current rules say that 'foo' is monomorphic, so we get foo :: Int but we also get an unbound top-level constraint (?x::Int). GHC emits a message like: Unbound implicit parameter (?x::Int) arising from use of `woggle' at ... The point is that THERE IS NO WAY FOR THIS CONSTRAINT TO GET BOUND, because we don't have a top-level binding form for implicit parameters. So it's stupid for 'foo' to be monomorphic. The situation is a bit different for class constraints: module Main where main = print fooC fooC = woggleC 3 woggleC :: Num a => a -> a wogglec y = y+1 'fooC' is monomorphic, so we get foo :: a, with a top-level constraint (Num a); and the defaulting mechanism fixes a=Integer, so all is well. Even in the absence of monomorphism, we might get some other use of 'fooC' in the module which fixes fooC's type. So it's *not* stupid for foo to be monomorphic. Possible conclusions A) Emit an error message at the definition of foo, saying that it needs a type signature. B) Change the rule so that we always generalise over the implicit parameters of *top-level* definitions, even in definitions that fall under the MR. C) Change the rule so that we always generalise over implicit parameters, whether top-level or nested. I'll do (A) for now, I think, since it improves the error message. For those that care, there are quite extensive notes about generalisation and implicit parameters in GHC's source code, here: http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/typecheck /TcSimplify.lhs?rev=1.144 (search for "Notes on implicit parameters"). Interestingly, the notes argue for (C), but that's not what is currently implemented in GHC, for reasons I don't remember. Perhaps compatibility with other implementations. Simon | -----Original Message----- | From: glasgow-haskell-users-bounces(a)haskell.org [mailto:glasgow-haskell-users- | bounces(a)haskell.org] On Behalf Of Keean Schupke | Sent: 19 January 2005 14:42 | To: glasgow-haskell-users(a)haskell.org | Subject: Implicit parameters: | | Question regarding implicit parameters... The GHC manual says: | | "Dynamic binding constraints behave just like other type class | constraints in that they are automatically propagated." | | But the following code produces an error: | | ------------------------------------------------------------------------ --------------------------------- | | main = do | var <- newIORef (0::Int) | let ?global_counter = var in f | | | f = do | a <- get_unique | putStr (showInt a "\n") | b <- get_unique | putStr (showInt b "\n") | c <- get_unique | putStr (showInt c "\n") | | | get_unique :: (?global_counter :: IORef Int) => IO Int | get_unique = readIORef ?global_counter | | ------------------------------------------------------------------------ ---------------------------------- | | If "(?global_counter :: IORef Int)" were a class constraint the type | signature | for 'f' could be derived automatically... but we get: | | Unbound implicit parameter (?global_counter::IORef a) | arising from use of `get_unique' at Test.hs:17:13-22 | | Is this a bug? Is there some reason why this is not possible? (and if it | is not possible | shouldn't the documentation be changed to reflect this)... | | Keean. | | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users(a)haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

1 0

ANN: MissingPy First Release
by John Goerzen 04 Feb '05

04 Feb '05

Announcing MissingPy 0.1.0 http://quux.org/devel/missingpy ------------------------- What is MissingPy? ------------------------- It's two things: 1. A Haskell binding for many C and Python libraries for tasks such as data compression, databases, etc. This can be found in the MissingPy module tree. 2. A low-level Haskell binding to the Python interpreter to enable development of hybrid applications that use both environments. This can be found in the Python module tree. The Haskell bindings above use this environment. MissingPy permits you to call Python code from Haskell. It does NOT permit you to call Haskell code from Python. ------------------------- Major Features ------------------------- * GZip and BZip2 compression and decompression using the generic Handle-like HVIO interface * *dbm persistent storage using the generic AnyDBM interface * Low-level interface to Python for extending your own Haskell code * Many unit tests to verify proper functionality ** THIS IS CURRENTLY BETA-QUALITY CODE; MAJOR API FLUCTUATIONS MAY YET OCCUR. Future releases will likely feature HVFS virtual filesystem interfaces to ZIP and tar files, integration of Python's PCREs into Pesco's regexp system, a Haskell binding to PyOpenSSL, and other similar items. -- John Goerzen Author, Foundations of Python Network Programming http://www.amazon.com/exec/obidos/tg/detail/-/1590593715

1 0

ANN: MissingH 0.9.0
by John Goerzen 03 Feb '05

03 Feb '05

Announcing MissingH 0.9.0 This release is being made now because it introduces several features that are important for my work on MissingPy (announcement forthcoming). New feature summary: * Perl-like regular expression operators (MissingH.Regex.Pesco) This module builds atop the standard POSIX Text.Regex module, extending it to be far more convenient with easier maching, grouping, and substitution operations. (Integrated from Pesco) * strToAL, strFomAL (MissingH.List) Converts any [(String, String)] and many other association lists to a simple string representation that can be stored on-disk or sent across the network. Also, re-generates the original list upon parsing the string representation. Used internally by MissingH.AnyDBM.StringDBM. * Persistent or non-persistent DBM storage class MissingH.AnyDBM is an abstraction for various mapping systems. MissingH itself provides an implementation using a non-persistent HashTable or FiniteMap, as well as a persistent StringDBM. Bindings to dbm, gdbm, dbhash, etc. are in the works and will be simple members of this typeclass. * Major cleaning up of the build system. Description of MissingH from README: ------------------------- What is MissingH? ------------------------- It's a collection of Haskell-related utilities. It is an extension of my earlier work developing MissingLib for OCaml. You can download MissingH from http://quux.org/devel/missingh. There is a mirror, with a few days' lag, at http://ftp.debian.org/debian/pool/main/m/missingh. ------------------------- Major Features ------------------------- * Powerful Logging Framework for Haskell This framework provides a system of hierarchical loggers and modular handlers permitting fine-grained logging with a great deal of control and yet a simple and fast interface. It's based on log4j for Java and logging for Python. Also included is a native-Haskell Syslog client. * Versatile modules to simplify everyday tasks: + FTP client library + E-mail client library + MIME types library to determine MIME types from files or URLs + Configuration file parser/generator * IO utilities make it easier to work with line-based text files and binary files * IO object virtualization so you can use one set of code to work on files of many different types * Filesystem virtualization so you can access variuos items with the same ease as your system's filesystem * Network utilities to streamline connections * List utilities including association list tools, list splitting, truncation, and delimiter joining * String utilities including removal of leading or trailing whitespace, joining, splitting, and truncation * Other utilities for threads, parers, filenames, etc. * Printf utilities for formatting strings * GZip decompression * Hundreds of unit tests to verify proper functionality * DBM module abstraction # arch-tag: 0.9.0 announcement

1 0

Job Posting (Looking for a few good functional programmers)
by Yaron Minsky 03 Feb '05

03 Feb '05

Jane Street Capital (an affiliate of Henry Capital <http://henrycapital.com>) is a proprietary trading company located in Manhattan. The quantitative research department is responsible for analyzing, improving, and generating trading strategies. It's an open and informal environment (you can wear shorts and a t-shirt to the office), and the work is technically challenging, including systems work, machine learning, statistical analysis, parallel processing, and anything that crosses our path that looks useful. One unusual attraction of the job is that the large majority of our programming is done in OCaml. Pay is competitive, and we're a reasonably small company (around 85 employees), so advancement is pretty quick for someone who performs well. Here's what we're looking for: - Top-notch mathematical and analytic skills. We want people who can solve difficult technical problems, and think clearly and mathematically about all sorts of problems. - Strong programming skills. Pretty much all of our programming is in OCaml, so being a solid caml hacker is a big plus. But we're also interested in great programmers who we are convinced will be able to pick up OCaml quickly, so anyone with a high-level of proficiency with functional languages could be a good match. - Strong Unix/Linux skills --- We're looking for someone who knows their way around the standard unix tools, can write makefiles, shell scripts, etc. We use a beowulf cluster for compute-intensive jobs, so experience programming for and administering clusters is a big plus. If you're interested (or have any students you think might be a good match) and would be willing to relocate to New York, please send a cover-letter and resume to: yminsky(a)janestcapital.com

3 3

The Monad.Reader - Become an author for the Haskell eZine!
by Shae Matijs Erisson 03 Feb '05

03 Feb '05

There are plenty of academic papers about Haskell, and plenty of informative pages on the Haskell Wiki. But there's not much between the two extremes. The Monad.Reader aims to fit in there; more formal than a Wiki page, but less formal than a journal article. Want to write about a tool or application that deserves more attention? Have a cunning hack that makes coding more fun? Got that visionary idea people should know about? Write an article for The Monad.Reader! Contact Shae Erisson ( shae(a)ScannedInAvian.com ) to become an author, or talk to shapr on the #haskell irc channel on irc.freenode.net. Check the current roster - http://www.haskell.org/hawiki/TheMonadReader Publishing Format: * Input is LaTeX (or just plaintext and images). * Output is Web and PDF/PS. * Release once a month. * Each article in a darcs repo for easy collaboration between author and editor. License: *BSD-like, feel free to read it, teach it, hack it, copy it, improve it. The Monad.Reader: sequencing your input since 2005 -- Shae Matijs Erisson - http://www.ScannedInAvian.com/ - Sockmonster once said: You could switch out the unicycles for badgers, and the game would be the same.

1 0

Re: [Haskell] space behaviour of lazy recursive lists
by Axel Jantsch 03 Feb '05

03 Feb '05

Hi, Both variants of the strict zipWith solved the gibs problem I posed: gibs = 1 : 1 : f gibs (tail gibs) where f (x:xs) (y:ys) = z `seq` z : f xs ys where z = min (x + y) 10 by Simon MArlow and zipWith' f (x:xs) (y:ys) = let z = f x y in z `seq` (z : zipWith' f xs ys) zipWith' _ _ _ = [] by Adrian Hey However, they do not directly solve my problem in the bigger program which still has the same linearly growing memory requirement. The problem seems to be very, very hard to find. I suspect it is related to lazyness as in the gibs example, but I just cannot put my finger on the code that needs to be changed. Is there any good method to track down this kind of problem? (I tried all the ghc memory profiling techniques, that seemed promising to me.) Thanks to all that responded to my question! --Axel Axel Jantsch writes: > > Hi, > > How can I get constant space behaviour for lazy, recursive streams? > > Consider: > >> gibs = 1 : 1 : (zipWith f gibs (tail gibs)) >> where f x y = min (x + y) 10 > > This is derived from the fibs text book example, modified to bound the > memory requirement for each list element. > > Evaluating gibs should require constant amount of memory, since the > computed parts of the list are not needed any more and can be reclaimed. > > However, hugs says: > Main> nth 100 fibs > 10 > (2818 reductions, 3730 cells, 1 garbage collection) > Main> nth 200 fibs > 10 > (5618 reductions, 7430 cells, 1 garbage collection) > > which suggests linear space behaviour. Also, ghc shows the same behaviour > with a linearly growing stack size as shown by the profiler (+RTS -hc -xt) > and sooner or later the program runs out of memory with a stack overflow. > > It seems the entire list up to the last evaluated element is stored. Since > I want to use lazy streams to simulate process networks, I want to run the > simulation arbitrarily long without *ever* running out of memory. > > So my question is, how can I process recursive, lazy streams in constant > space? > > Or, in other words, how can I force the garbage collector to reclaim the > memory of the head of the list after I have processed it, since I will > never ever reference it again? > > With best regards > Axel Jantsch > > > --- > Phone: +46 8 790 4124, Email: axel(a)imit.kth.se, Web: www.imit.kth.se/~axel > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell > > --- Phone: +46 8 790 4124, Email: axel(a)imit.kth.se, Web: www.imit.kth.se/~axel

2 1

Re: [Gph] [Fwd: Re: [Haskell] Implicit parallel functional programming]
by Phil Trinder 03 Feb '05

03 Feb '05

Satnam, > Does anyone know of any other work on implicitly > parallelizing functional programs for fine grain parallel execution? The skeletons community implicitly replace higher-order functions with parallel implementations: http://homepages.inf.ed.ac.uk/mic/Skeletons/ There's an excellent survey of parallel FP in Research Directions in Parallel Functional Programming, Hammond K. and Michaelson G. (Eds) Springer Verlag ISBN 1-85233-092-9 (2000). http://www-fp.dcs.st-and.ac.uk/pfpbook/ > there is interesting work with pH at MIT. Is anyone working on pH at the moment? Phil > ---------------------------- Original Message ---------------------------- > Subject: Re: [Haskell] Implicit parallel functional programming > From: mgross(a)dorsai.org > Date: Wed, January 19, 2005 4:36 am > To: "Satnam Singh" <satnams(a)microsoft.com> > Cc: Haskell(a)haskell.org > -------------------------------------------------------------------------- > > > > > > On Tue, 18 Jan 2005, Satnam Singh wrote: > >> I'm trying to find out about existing work on implicit parallel > functional programming. I see that the Glasgow Haskell compiler has a > parallel mode which can be used with PVM and there is interesting work > with pH at MIT. Does anyone know of any other work on implicitly > parallelizing functional programs for fine grain parallel execution? >> >> The emergence of multi-core processors makes me think that we should > look at implicit parallel functional programming in a new light. >> > At Brooklyn College, we are working on a version of Parallel Haskell that > does not require PVM. Instead, we use Internet protocols and the Mosix > patches to Linux. > > Murray Gross > Brooklyn College, CUNY > Metis Project > > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell > > > > _______________________________________________ > Gph mailing list > Gph(a)macs.hw.ac.uk > http://www.macs.hw.ac.uk/mailman/listinfo.cgi/gph > -------------------------------------------------- Phil Trinder School of Mathematical and Computer Sciences Heriot-Watt University Edinburgh, EH14 4AS E-mail: trinder(a)macs.hw.ac.uk Teleph: +44 (0)131 451 3435 Depart: +44 (0)131 451 3328 Fasmly: +44 (0)131 451 3327 Intrnt: http://www.macs.hw.ac.uk/~trinder

1 0

RE: [Haskell] Polymorphic types without type constructors?
by Simon Peyton-Jones 02 Feb '05

02 Feb '05

| It seems to me that the difference is: in the case of the second | definition of exp, the type variable in N can be instantiated to | a **monomorphic** type (the same with add and mul). | | exp2 = \m::N -> \n::N -> \f::(b -> b) -> \b::b -> | n [b] (m[b]) f b | | (where square brackets denote type application) | while in the first exp, n::N is instantiated to a **polymorphic** type | (another N): | | exp = \m::N -> \n::N -> \f::(b -> b) -> \b::b -> | (n[N] (mul m) one)[b] f b | | (SLPJ: note that N is a polymorphic type) You have it exactly right. The key word is "predicative". GHC has a predicative type system, that only allows you to instantiate a type variable with a monotype, not a polytype. An impredicative system (which is the one you want here) is more expressive, but it makes type inference very much more difficult. The algorithm is more difficult because type inference algorithms usually work with meta-type variables representing as-yet-unknown types; as the algorithm runs these meta-type variables are gradually substituted with their final type. But if this gradual substitution can involve polymorphic types, then type instantiation should have occurred earlier.... Try it yourself. Difficult is not impossible. If you are interested, look at MLF, a fantastic piece of work from INRIA (Remy & Le Botlan), that describes type inference for an impredicative, higher-rank type system. | I tried to add more type signatures to inform GHC of the fact | that n::N is to be instantiated to a polymorphic type. However | none of the attempts worked so far. Your intuition is good. Somehow, one might expect that if you told GHC *at the moment of instantiation* what to instantiate to, it ought to work, because there is no guessing involved. For example you ought to be able to say exp2 :: N -> N -> N exp2 n m = n {N} m Here, the {N} is a type argument to n. But I have not implemented this (yet). The main difficulty I encountered when thinking about is this. GHC uses prenex polytypes. If you write f :: Int -> (forall a. a->a) GHC behaves as if you'd written f :: forall a. Int -> a -> a That is, GHC's types never have a for-all to the right of an arrow. (You can read about this in "Practical type inference for higher rank types" on my home page.) Currently, this is a simple syntactic transformation on user-written types. But if you could instantiate a type variable with a polytype, then for-alls could occur to the right of an arrow as a result of the instantiation. My current plan is to throw out the prenex-polytype invariant, and find another way to deal with the problem that pushed me that way in the first place. Something like coloured type inference. I'm working on that with Dimitrios Vytiniotis and Stephanie Weirich. Anyway, thanks for an interesting example. Simon

2 1

Re: Polymorphic types without type constructors?
by oleg＠pobox.com 02 Feb '05

02 Feb '05

> I have been thinking about using Haskell (extended with > higher ranked polymorphism) to demonstrate to my colleagues > some ideas in second-order lambda calculus. It turned out, > however, I am puzzled by the type system myself. So I've > written to seek for help. :) > > I started with define Church numerals as > > > type N = forall a . (a -> a) -> a -> a > > (The syntax above works only for GHC. In Hugs I would have to write > type N a = (a -> a) -> a -> a > and replace every N below with (forall a. N a)) > I should have used newtype or data instead of a type synonym, > but I wanted it to look more like seond-order lambda calculus > so I tried to omit the constructor if possible. Let us consider a simpler example than the type N. > f1:: (forall a. a->a) -> b -> b > f1 g x = g x > -- *P1> f1 id True > -- True > > foo:: forall c notimportant. (c->c) -> notimportant > foo = undefined If we try > *P1> foo f1 we get an error > <interactive>:1: > Inferred type is less polymorphic than expected > Quantified type variable `a' escapes > Expected type: (a -> a) -> a -> a > Inferred type: (forall a1. a1 -> a1) -> b -> b > In the first argument of `foo', namely `f1' > In the definition of `it': it = foo f1 And indeed: the type of `foo' says that its argument must be a function from some type `c' to exactly the same type. The function f1 has the type (forall a. a->a) -> (forall b. b->b) The question then becomes: is (forall a. a->a) the same as (forall b. b->b) ? Not to Haskell. That would require a higher-order unification. However, not everything is lost. There is a way to convince GHC that the two quantified types are really the same. We just need a suitable envelope. Nominal equivalence does come handy sometimes. Here's the code > {-# OPTIONS -fglasgow-exts #-} > > module P1 where > > import Prelude hiding (succ) > > newtype N = N (forall a . (a -> a) -> a -> a) > un (N x) = x > > zero :: N > zero = N ( \f a -> a ) > > succ :: N -> N > succ n = N ( \f a -> f (un n f a) ) > > one:: N > one = succ zero > > add, mul :: N -> N -> N > add m n = N( \f a -> un m f (un n f a) ) > mul m n = N( \f a -> un m (un n f) a ) > > exp :: N -> N -> N > exp m n = un n (mul m) one > > exp2 :: N -> N -> N > exp2 m n = N (\f a -> un n (un m) f a) > > test1 = un (P1.exp two three) (+1) 0 > where two = succ one > three = succ two > > test2 = un (P1.exp2 two three) (+1) 0 > where two = succ one > three = succ two I must note that in this code, one may not replace N (...) with N $ ( ...). This is yet another case where ($) is not the same as an application with a lower precedence. The code has a redeeming feature: the data constructor N marks the places of explicit big-lambda introductions. The function 'un' marks the places of explicit big lambda eliminations (that is, type applications).

1 0

Re: Polymorphic types without type constructors?
by Shin-Cheng Mu 02 Feb '05

02 Feb '05

Hi, Shin-Cheng Mu wrote: > exp2 = \m::N -> \n::N -> \f::(b -> b) -> \b::b -> > n [b->b] (m[b]) f b Oops.. it should be exp2 = \m::N -> \n::N -> \f::(b -> b) -> \b::b -> n [b] (m[b]) f b sincerely, Shin-Cheng Mu

1 0