- Haskell - Haskell.org

Re: arrows
by Ashley Yakeley 03 Jun '02

03 Jun '02

At 2002-05-24 13:40, Wolfgang Jeltsch wrote: >Now, I have a type which would fit wonderfully into the Arrow concept if >arrows wouldn't be expected to have a first operator. ...then it's not an Arrow. It sounds like it might be one of these, however: class Compositor comp where { identity :: comp a a; compose :: comp b c -> comp a b -> comp a c; }; I'm not sure if 'Compositor' is a good name for it, or what. >Parser arrow. And there is also a meaningful definition for pure (arr). >pure f just has to be a parser which reads exactly one token, applies f >to it and outputs the resulting value. >The problem is that there seems to be no appropriate definition for >first. That's why, in my opinion, it would be very good to have only the Can't you have a parser that reads in one token tuple, and apply another parser to the first part of it only? Otherwise, perhaps you could have classes like this: class (Compositor arrow) => Semiarrow arrow where { arr :: (p -> q) -> arrow p q; }; class (Semiarrow arrow) => Arrow arrow where { arrFirst :: arrow p q -> arrow (p,r) (q,r); }; -- Ashley Yakeley, Seattle WA

5 4

RE: [Fwd: F#]
by Ashley Yakeley 03 Jun '02

03 Jun '02

At 2002-05-31 12:48, Don Syme wrote: >One point is that in the absence of extensive purity annotations to >imperative libraries you will need to use monads for operations that >shouldn't need them. But these cases are surely quite rare? In my experience, if it really is pure, chances are Haskell can do it by itself and you don't need a function in the library to do it. Perhaps there are exceptions for maths libraries. It seems to me the simplest thing for foreign libraries is to make all calls monadic. Certainly I do this in JVM-Bridge, all raw FFI calls are in the IO monad and I don't use "unsafe" anything anywhere. There are no particular "pure" Java library functions that are worth making an exception for. -- Ashley Yakeley, Seattle WA

1 0

CfP First International Conference on Security in Pervasive Computing (SPC2003)
by Dieter Hutter 03 Jun '02

03 Jun '02

-------------------------------------------- We are sorry if you receive multiple copies! -------------------------------------------- Call for Papers First International Conference on Security in Pervasive Computing (SPC-2003) March 12 - 14, 2003 in Boppard, Germany http://www.dfki.de/SPC2003 The ongoing compression of computing facilities into small and mobile devices like handhelds, portables or even wearable computers will enhance an ubiquitous information processing. The basic para- digm of such a pervasive computing is the combination of strongly decentralized and distributed computing with the help of diversified devices allowing for spontaneous connectivity via the internet. Computers will become invisible to the users awareness and exchange of information between devices will effectively defy users control. Assuming a broad usage of more powerful tools and more effective ways to use them the quality of every day life will be strongly influenced by the dependability of the new technology. Information stored, processed, and transmitted be the various devices is one of the most critical resources. Threats exploiting vulnerabilities of new kinds of user interfaces, displays, operating systems, networks, and wireless communications will cause new risks of loosing confidentiality, integrity, and availability. Can these risks be reduced by countermeasures to an acceptable level or do we have to redefine political and social demands as it is expressed by the Gartner Group from a privacy perspective: By 2010, driven by the improving capabilities of data analysis ... privacy will become a meaningless concept in Western societies. Topics of Interest: ------------------- The objective of this conference is to develop new security concepts for complex application scenarios based on systems like handhelds, phones, smartcards, and smart labels hand in hand with the emerg- ing technology of ubiquitous and pervasive computing. Particular subjects are methods and technology concerning the identification of risks, the definition of security policies, and the development of security measures that are related to the specific aspects of ubiquitous and pervasive computing like mobility, communication, and secure hardware/software platforms. Submissions: ------------ We welcome the submission of papers from the full spectrum of issues associated with security in pervasive computing. Submissions should describe completed work including descriptions of research, tools, and applications and should not exceed 15 pages in LNCS-style. Papers should be in postscript or pdf format, (lncs-style). Please submit papers by e-mail to spc2003(a)dfki.de Upon submission, name, address, and e-mail of the contact author should be included in the e-mail. Conference Schedule: -------------------- In consideration of the novel character of the conference theme it is planned to have three kinds of events: - invited talks that give an introduction into security related aspects of pervasive computing, - sessions for the presentation of technical papers, and - working groups that focus on particular problems areas. The results of the working groups will be presented and discussed in panel sessions. The final results will be published together with the technical papers in the Lecture Notes Series on Computer Science (LNCS). Location: --------- It will be held at an old former monastery in Boppard, Germany. Boppard is a nice small town located in the rhine valley about one hour away from Frankfurt airport. Organisation: ------------- The conference will be organised jointly by - German Information Security Agency (BSI) - German Research Center for Artificial Intelligence (DFKI) - Institute for Telematics, University of Freiburg. Program Committee ----------------- Michael Beigl (University of Karlsruhe) Joshua Guttman (MITRE) Dieter Hutter (DFKI) (co-organiser) Paul Karger (IBM Watson Research) Friedemann Mattern (ETH Zurich) Catherine Meadows (Naval Research Lab) Guenter Mueller (University of Freiburg) (co-organiser) Joachim Posegga (SAP) Kai Rannenberg (University of Frankfurt) Kurt Rothermel (University of Stuttgart) Ryoichi Sasaki (Tokyo Denki University) Frank Stajano (University of Cambridge) Werner Stephan (DFKI) (co-organiser) Moriyasu Takashi (Hitachi Ltd) Seiji Tomita (NTT Information Platform Laboratories) Markus Ullmann (BSI) (co-organiser) Important Dates: ---------------- - Submission of papers: October 31, 2002 - Notification of acceptance/rejection: December 31, 2002 - Camera ready final version of papers: January 31, 2003

1 0

RE: [Fwd: F#]
by Don Syme 03 Jun '02

03 Jun '02

Hi Manuel, One point is that in the absence of extensive purity annotations to imperative libraries you will need to use monads for operations that shouldn't need them. Having to add the annotations certainly counts as a complication in comparison to what many other languages have to do on .NET. As for monads, this is hardly the place to go into an argument about their relative merits re. all those slightly more widespread approaches to imperative programming. If you think driving imperative libraries using monads will be so great then a Haskell.NET would certainly be a perfect place to try out that theory. Don -----Original Message----- From: Manuel M. T. Chakravarty [mailto:chak@cse.unsw.edu.au] Sent: Fri 31.05.2002 03:27 To: Don Syme Cc: tweed(a)cs.bris.ac.uk; paul.hudak(a)yale.edu; haskell(a)haskell.org Subject: RE: [Fwd: F#] "Don Syme" <dsyme(a)microsoft.com> wrote, > And getting top-notch performance is obviously always a huge challenge > for Haskell, and you can't play some common implementation tricks when > compiling to IL. But the only truly serious complications added by .NET > itself are (a) the general problem of Haskell interop with imperative > libraries, requiring you to reach for monads quite often (or to wrap the > libraries yourself) [..] > IMHO problem (a) will always be the thing that stops Haskell becoming > very very big. But then being non-imperative it's also its main selling > point... So, you are saying that Haskell's problem with .NET is that it is not imperative, but at the same time you don't want to resort to Haskell's imperative sublanguage (the IO monad). I don't quite understand this. Personally, I find[1] Haskell to be very pleasant for imperative programming. In fact, I agree with SPJ, who wrote[2] (slightly provocatively), Haskell is the world's finest imperative programming language. Cheers, Manuel [1] After having written piles of low-level imperative code in Haskell. [2] In ``Tackling the Awkward Squad''

3 2

Direct Email Blaster, Email extractor, email downloader, email verify ...........
by targetemailextractor＠btamail.net.cn 03 Jun '02

03 Jun '02

1 0

Lists representations (was: What does FP do well? (was ...))
by C.Reinke 01 Jun '02

01 Jun '02

Long away and far ago (or something like that;), there was a discussion on Lists implemented as arrays rather than linked structures, during which Jerzy Karczmarczuk commented: > What bothers me quite strongly is the algorithmic side of operations > upon such objects. > > Typical iterations map- (or zip-) style: do something with the head, pass > recursively to the tail, would demand "intelligent" arrays, with the indexing > header detached from the bulk data itself. The "consumed" part could not be > garbage collected. In a lazy language this might possibly produce a considerable > amount of rubbish which otherwise would be destroyed quite fast. The > concatenation of (parts of) such lists might also have very bad behaviour. > > Can you calm my anxiety? > > Jerzy Karczmarczuk The reason I wanted to reply is that I can offer one data point on this. An even longer time ago, there were the various reduction systems developed in Kiel, implementing the Kiel Reduction Language KiR, a variant of Berkling's reduction languages (the Berkling pointed to in Backus' Turing Award Lecture). KiR lacked lots of useful features Haskell has, and Haskell's implementations still lack lots of useful features KiR's had. I dearly miss those features, but that is not the topic here (I don't know whether any of the systems still install or even run, but see the Manual at http://www.informatik.uni-kiel.de/~base/ for more info). The topic here was list representations. KiR's implementations moved from interpreted graph-reduction over compiled graph-reduction with a code interpreter to compiled graph-reduction with compilation via C, all more or less with the same high-level front end. All of these represented lists as vectors (KiR was dynamically and implicitly typed, btw), and the memory was divided into an area for fixed-size descriptors pointing to each other or into the second area, the heap, for variable-sized data blocks. The descriptor area was reference-counted and simply reused free space (most KiR variants were call-by-value), the other area needed memory compactification when space grew fragmented. A list's elements (or pointers to their descriptors) went into a contiguous block in the heap, and the descriptors made it possible to share subsequences of elements between different lists (descriptors were large enough to hold a pointer to the start of the sequence and its length). Quite as Jerzy suspected. Supported operations included both array and list operations, append required the allocation of a new heap block and copying of *both* lists, but was provided as a primitive (the standard approach for systems that started out as interpreters: a good mix of efficient primitives and interpreted user defined constructs). As others have pointed out, this looks rather inefficient, especially for longer lists, so when we set out to make measurements for a JFP paper [1], comparing with the likes of ghc, we expected to be beaten, but hoped to be not too far away, at least with the latest via-C implementation.. Benchmarks are always difficult, but especially so between so different languages: in KiR, we could easily and correctly execute programs that in Haskell, either wouldn't even compile, or wouldn't terminate, or wouldn't show any result (with similar problems the other way round). And after adapting to the common subset of algorithms, a translation to Haskell might mean that a complex program execution might return immediately, as the compiler and runtime system lazily determined that none of it was needed for the program output (compiled Haskell programs report almost no reduction results, only explicit program output, or show-able results). With all these preliminaries and caveats, and the standard disclaimer that all benchmarks are useless, but interesting, the relevant benchmark is the infamous "pretty quicksort" for some 4000 elements (qusort in the paper - lots of finite lists, traversals, fragments and appends, just like the typical Haskell program written without any concern for efficiency; Haskell programs concerned with efficiency tend to look rather different). To our astonishment, even the code interpreting implementation (which should otherwise be in the ballpark of Hugs) outperformed ghc, hbc, and Clean on this example (call-by-value also played a role: compiled sml was in the same area as compiled KiR, but both only slightly faster than code-interpreted KiR, so data representation and primitives seemed to play the main role). This prompted us to include Augustsson's sanitized variant of quicksort (qusortbin in the paper - from the hbc libs) as well, which gave the results everyone expected (it substantially modifies the algorithm to a profile better supported by the current list representation, e.g., no appends). [and before anyone accuses me of advocating functional quicksort: the naive quicksort is useless, and even the real one isn't the best choice in many cases;-] But the moral for the current discussion: a more intelligent list representation could have substantially more benefits for the average Haskell program than any compiler optimization twiddling, and I'd really like to see someone (PhD student?) investigating that topic seriously, as the answers are unlikely to be obvious. The representation chosen in the reduction systems could be a first hint, but as Jerzy points out, things may be more complicated in the context of Haskell. For comparison, Haskell array performance was somewhere between non-existent and terrible in those days (another clear win for both the compiled and the interpreted reduction systems) and has only recently improved somewhat. That needs to continue and, please, someone do the same for lists! Just my old 2 Pfennige (former currency;-), Claus [1] D. Gaertner, W. Kluge: pi-RED+: An Interactive Compiling Graph Reduction System for an Applied Lambda-Calculus Journal of Functional Programming, 6 (5), 1996.

3 2

Re: readFloat
by Wolfgang Jeltsch 31 May '02

31 May '02

On Tuesday, 2002-05-28, 18:57, CEST Simon Peyton-Jones wrote: > Folks > > I'm back to tidying up the Haskell Report. > > In the Numeric library, there is the useful function > > readFloat :: RealFloat a => ReadS a > > But you can't use it for reading rationals, because Rational > isn't in RealFloat! > > This is a Royal Pain, and entirely unnecessary. In fact, > readFloat uses only operations from the RealFrac class, > so it could equally well have type > > readFloat :: RealFrac a => ReadS a > > I'm strongly inclined to make this change. It breaks no > programs, and it fixes a real bug i.e. there is no way to > read a "103" as a Rational. > > Simon It would be strange to name a function readFloat if its type is RealFrac a => ReadS a. I think the function should be named readFrac. For compatibility, one could put the following into the prelude: readFloat :: RealFloat a => ReadS a readFloat = readFrac And one could mark readFloat as depricated and maybe remove it in some future version of Haskell. Ciao, Wolfgang

3 2

RE: [Fwd: F#]
by Don Syme 31 May '02

31 May '02

> GHC supports concurrency, exceptions, weak pointers, foreign calls, > etc, etc. All these need to be mapped onto .NET. ... GHC comes > with a large collection of libraries of its own. These need to be > still available in the .NET version. I don't really agree with these points. If someone tried to support all of this they'd be unlikely to appear out the other end of the swamp. Having actually tried both ways myself, I'd suggest that GHC is simply not the right starting point for a Haskell.NET compiler. Much better to start a fresh compiler, essentially from scratch, with a suitable selection of optimizations, language extensions, library features and interop extensions given the platform and kind of programming you're aiming to support. If you look at history successful compiler projects do not tend to some out of attempts to graft large code bases for alternative purposes (unless you've got loads of resources to throw at the problem). Cheers, Don -----Original Message----- From: Simon Peyton-Jones [mailto:simonpj@microsoft.com] Sent: 31 May 2002 15:31 To: Don Syme; D. Tweed Cc: Paul Hudak; haskell Subject: RE: [Fwd: F#] | Idle curiosity: which aspects of the Haskell language are the | ones that make it complicated -- e.g., long-time stuff like | lazy evaluation, typeclasses & inferrence, etc or newer stuff | like functional dependencies, etc or something else entirely | -- and do they only make it complicated in the context of the | .NET architecture or in any implementation? General remarks about targetting .NET from GHC. * There is no reason in principle why one can't write a back end for GHC to generate .NET IL. * Generating *verifiable* IL is noticeably harder: you have to take much more care; to deal with parametric polymorphism you need Generic IL, which isn't "out" yet; and even then, higher kinded type variables are a serious problem. Being verifiable almost certainly requires some runtime checked type casts, which hurt performance -- and reducing them to a minimum complicates the compiler. * My conclusion: best plan is to generate unverifiable IL, and run it unverified. Situation is then just like an existing code generator: you have to trust the compiler. But it's fast and it's much simpler. * The resulting code will still run quite a bit slower than GHC-complied code. So why would anyone want to use it? Presumably, to get access to the .NET libraries. So that has to be very convenient. Tools are needed to read .NET library meta-data and generate impedence matching glue to make them easily callable from Haskell. Haskell needs some new 'foreign import' stuff to make it easy to call the libraries. There's a big design space here about how much to extend Haskell to make calling .NET convenient. * GHC supports concurrency, exceptions, weak pointers, foreign calls, etc, etc. All these need to be mapped onto .NET. Some might not fit well; for example, Concurrent Haskell assumes extremely lightweight concurrency, whereas .NET threads are OS threads; and asynchronous exceptions might be tricky too. * GHC comes with a large collection of libraries of its own. These need to be still available in the .NET version, so the .NET implementation of GHC needs to be pretty fully-featured (because the libraries use a lot of features). What all this means is that GHC.NET is a lot more than just a code generator. That is, I think, what Don meant when he said that GHC is complicated. (In our defence, it is the very fact that GHC is a rich system that makes it useful. Its complexity is not gratuitous.) Part of my reason for writing this is to encourage anyone out there to take up the challenge. There's nothing too difficult -- it's "just work". Simon and I don't have immediate plans to do anything about this, but we'd be delighted if someone else did. Congratulations to Sigbjorn to doing a great job with Hugs. Simon _______________________________________________ Haskell mailing list Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell

1 0

RE: [Fwd: F#]
by Simon Peyton-Jones 31 May '02

31 May '02

| Idle curiosity: which aspects of the Haskell language are the | ones that make it complicated -- e.g., long-time stuff like | lazy evaluation, typeclasses & inferrence, etc or newer stuff | like functional dependencies, etc or something else entirely | -- and do they only make it complicated in the context of the | .NET architecture or in any implementation? General remarks about targetting .NET from GHC. * There is no reason in principle why one can't write a back end for GHC to generate .NET IL. * Generating *verifiable* IL is noticeably harder: you have to take much more care; to deal with parametric polymorphism you need Generic IL, which isn't "out" yet; and even then, higher kinded type variables are a serious problem. Being verifiable almost certainly requires some runtime checked type casts, which hurt performance -- and reducing them to a minimum complicates the compiler. * My conclusion: best plan is to generate unverifiable IL, and run it unverified. Situation is then just like an existing code generator: you have to trust the compiler. But it's fast and it's much simpler. * The resulting code will still run quite a bit slower than GHC-complied code. So why would anyone want to use it? Presumably, to get access to the .NET libraries. So that has to be very convenient. Tools are needed to read .NET library meta-data and generate impedence matching glue to make them easily callable from Haskell. Haskell needs some new 'foreign import' stuff to make it easy to call the libraries. There's a big design space here about how much to extend Haskell to make calling .NET convenient. * GHC supports concurrency, exceptions, weak pointers, foreign calls, etc, etc. All these need to be mapped onto .NET. Some might not fit well; for example, Concurrent Haskell assumes extremely lightweight concurrency, whereas .NET threads are OS threads; and asynchronous exceptions might be tricky too. * GHC comes with a large collection of libraries of its own. These need to be still available in the .NET version, so the .NET implementation of GHC needs to be pretty fully-featured (because the libraries use a lot of features). What all this means is that GHC.NET is a lot more than just a code generator. That is, I think, what Don meant when he said that GHC is complicated. (In our defence, it is the very fact that GHC is a rich system that makes it useful. Its complexity is not gratuitous.) Part of my reason for writing this is to encourage anyone out there to take up the challenge. There's nothing too difficult -- it's "just work". Simon and I don't have immediate plans to do anything about this, but we'd be delighted if someone else did. Congratulations to Sigbjorn to doing a great job with Hugs. Simon

2 1

RE: [Fwd: F#]
by Don Syme 31 May '02

31 May '02

Hi Paul, The attached message doesn't give the link you might be after, which is http://research.microsoft.com/projects/fsharp. You might also be interested in SML.NET. Re Haskell.NET... We (OK, basically just me) got a fair amount of the way through a .NET backend for GHC, including a fully working compiler, but we got sidetracked into implementation issues that weren't related what we wanted to achieve in the first instance. In particular, (a) GHC is a complex beast, (b) you have to decide what to do about the libraries and (c) I wanted a much "lighter" end system than GHC was going to provide. Given the general complexity of GHC, the longish compile times and the reliance of the GHC library implementation on C and C libraries in so many places I decided to implement a simpler language from scratch. I like the idea that a .NET compiler should be under 10K lines of code if at all possible, as is the case for F#. Those of us at MSR have no particular plans to push further on Haskell.NET right now, but I know a number of other people have talked about taking a crack at it. Best wishes, Don Syme MSR Cambridge -----Original Message----- From: Paul Hudak [mailto:paul.hudak@yale.edu] Sent: 30 May 2002 14:12 To: haskell(a)cs.yale.edu Subject: [Fwd: F#] Hey Simon et al at Micro$oft, when will there be an H#? (Ok, I'll settle for Haskell.NET :-) -Paul

4 5