[Haskell-cafe] ANN: unification-fd 0.7.0
-- unification-fd 0.7.0 The unification-fd package offers generic functions for single-sorted first-order structural unification (think of programming in Prolog, or of the metavariables in type inference)[1][2]. The library *is* sufficient for implementing higher-rank type systems a la [Peyton Jones, Vytiniotis, Weirich, Shields], but bear in mind that unification variables are the metavariables of type inference--- not the type-variables. An effort has been made to make the package as portable as possible. However, because it uses the ST monad and the mtl-2 package it can't be H98 nor H2010. However, it only uses the following common extensions which should be well supported[3]: Rank2Types MultiParamTypeClasses FunctionalDependencies -- Alas, necessary for type inference FlexibleContexts -- Necessary for practical use of MPTCs FlexibleInstances -- Necessary for practical use of MPTCs UndecidableInstances -- For Show instances due to two-level types -- Changes (since 0.6.0) This release is another major API breaking release. Apologies, but things are a lot cleaner now and hopefully the API won't break again for a while. The biggest change is that the definition of terms has changed from the previous: data MutTerm v t = MutVar !v | MutTerm !(t (MutTerm v t)) To the much nicer: data UTerm t v = UVar !v | UTerm !(t (UTerm t v)) The old mnemonic of mutable terms was inherited from the code's previous life implementing a logic programming language; but when I was playing around with implementing a type checker I realized that the names don't really make sense outside of that original context. So the new mnemonic is unification terms. In addition to being a bit shorter, it should help clarify the separation of concerns (e.g., between unification variables vs lambda-term variables, type variables, etc.). The swapping of the type parameters is so that UTerm can have instances for Functor, Monad, etc. This change should've been made along with the re-kinding of variable types back in version 0.6.0, since the UTerm type is the free monad generated by t. I've provided all the category theoretic instances I could imagine some plausible reason for wanting. Since it's free, there are a bunch more I haven't implemented since they don't really make sense for structural terms (e.g., MonadTrans, MonadWriter, MonadReader, MonadState, MonadError, MonadCont). If you can come up with some compelling reason to want those instances, I can add them in the future. Since the order of type parameters to BindingMonad, UnificationFailure, Rank, and RankedBindingMonad was based on analogy to the order for terms, I've also swapped the order in all of them for consistency. I've removed the eqVar method of the Variable class, and instead added an Eq superclass constraint. Again, this should've happened with the re-kinding of variables back in version 0.6.0. A major benefit of this change is that now you can use all those library functions which require Eq (e.g., many of the set-theoretic operations on lists, like (\\) and elem). I've added new functions: getFreeVarsAll, applyBindingsAll, freshenAll; which are like the versions without All, except they're lifted to operate over Foldable/Traversable collections of terms. This is crucial for freshenAll because it allows you to retain sharing of variables among the collection of terms. Whereas it's merely an optimization for the others (saves time for getFreeVarsAll, saves space for applyBindingsAll). The type of the seenAs function has also changed, to ensure that variables can only be seen as structure rather than as any UTerm. Thanks to Roman Cheplyaka for suggesting many of these changes. -- Description The unification API is generic in the type of the structures being unified and in the implementation of unification variables, following the two-level types pearl of Sheard (2001). This style mixes well with Swierstra (2008), though an implementation of the latter is not included in this package. That is, all you have to do is define the functor whose fixed-point is the recursive type you're interested in: -- The non-recursive structure of terms data S a = ... -- The recursive term type type PureTerm = Fix S And then provide an instance for Unifiable, where zipMatch performs one level of equality testing for terms and returns the one-level spine filled with pairs of subterms to be recursively checked (or Nothing if this level doesn't match). class (Traversable t) = Unifiable t where zipMatch :: t a - t b - Maybe (t (a,b)) The choice of
Re: [Haskell-cafe] ANN: Haskell Platform Versions Comparison Chart
This includes both, packages that come with ghc and platform packages. Source is on GitHub[1]. Nice. Any chance you could get the packages sorted alphabetically so that it's easier to look things up directly? Sure, now they are sorted alphabetically (case-insensitive). Before it was more like two alphabetically sorted lists (case-sensitive), GHC boot libs first, and platform libs second (determined by the latest release, exactly what `ghc-pkg list` gives you). Ideally boot libs and platform libs would go into two separate tables, but packages may move between those (e.g. syb did). Cheers, Simon PS: If directly means manually, than I'd strongly advise against doing that ;) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Google Summer of Code idea of project application
Hi Damien A translator might be a lot of work. Matthew Naylor had a translator between Haskell and Clean [1], which performed well according to [2]. The translator was his Master project in the UK so I think that means it would represent approximately a years work. [1] http://www-users.cs.york.ac.uk/~mfn/hacle/hacle.pdf [2] http://www.st.cs.ru.nl/papers/2010/groj10-Haskell_front_end_Clean.pdf The paper [2] covers the Clean groups own interop between Haskell and Clean and points to more related work alongside Matthew Naylor's. Best wishes Stephen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: Haskell Platform Versions Comparison Chart
Hi, Am Sonntag, den 18.03.2012, 10:08 +0100 schrieb Simon Hengel: I compiled a chart that gives a side-by-side comparison of package versions in various Haskell Platform releases. http://sol.github.com/haskell-platform-versions-comparison-chart/ This includes both, packages that come with ghc and platform packages. Source is on GitHub[1]. nice, and much prettier version than http://people.debian.org/~nomeata/platform.html Do you see a way that you could incorporate distribution information? You could maybe parse and (optionally) present the information that Hackage reads, e.g. http://people.debian.org/~nomeata/cabalDebianMap.txt for Debian? Greetings, Joachim -- Joachim nomeata Breitner Debian Developer nome...@debian.org | ICQ# 74513189 | GPG-Keyid: 4743206C JID: nome...@joachim-breitner.de | http://people.debian.org/~nomeata signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Google Summer of Code - Lock-free data structures
A lock-free concurrent queue alone would be worth a summer project IMO. G On Mon, Mar 19, 2012 at 3:25 AM, Florian Hartwig florian.j.hart...@gmail.com wrote: On 19 March 2012 00:59, Chris Smith cdsm...@gmail.com wrote: On Mar 18, 2012 6:39 PM, Florian Hartwig florian.j.hart...@gmail.com wrote: GSoC stretches over 13 weeks. I would estimate that implementing a data structure, writing tests, benchmarks, documentation etc. should not take more than 3 weeks (it is supposed to be full-time work, after all), which means that I could implement 4 of them in the time available and still have some slack. Don't underestimate the time required for performance tuning, and be careful to leave yourself learning time, unless you have already extensively used ThreadScope, read GHC Core, and worked with low-level strictness, unpacking, possibly even rewrite rules. I suspect that the measurable performance benefit from lockless data structures might be tricky to tease out of the noise created by unintentional strictness or unboxing issues. And we'd be much happier with one or two really production quality implementations than even six or seven at a student project level. -- Chris Smith Thank you, Hofstadter's law definitely rears its head in many of my projects. I do have some experience with ThreadScope and strictness issues, but you I agree that I'm probably underestimating the time I need to learn. I also agree that my focus would be on quality rather than quantity. I quite like the modularity of this project, because it minimises the chance of having a lot of half-finished but useless code at the end of summer. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Gregory Collins g...@gregorycollins.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Google Summer of Code - Lock-free data structures
On 19 March 2012 09:56, Gregory Collins g...@gregorycollins.net wrote: A lock-free concurrent queue alone would be worth a summer project IMO. G Ryan Newton is already doing that (https://github.com/rrnewton/haskell-lockfree-queue). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Google Summer of Code - Lock-free data structures
The MichaelScott lockefree queues in that repository pass tests and should work. Additional stress testing and feedback would be appreciated. There are some other queues in the literature that might be worth implementing but I think other data structures are higher priority. As Adam Foltzer mentioned in the trac ticket a really good structure would be the concurrent bags from this paper: http://www.cse.chalmers.se/~tsigas/papers/Lock%20Free%20Bag%20SPAA11.pdf We separately did a C implementation of those and they performed really well in our bake-off of producer consumer data structures (vs. TBB queues, and many other implementations). By the way, we can share the code for this little bake-off as a performance baseline for the Haskell versions. I'm less familiar with the literature on concurrent hash tables. TBB's have been a little bit underwhelming in performance. But it's definitely an important structure. Ditto for priority queues. In any case, I welcome your interest in the topic, Florian! Cheers, -Ryan On Mon, Mar 19, 2012 at 7:33 AM, Florian Hartwig florian.j.hart...@gmail.com wrote: On 19 March 2012 09:56, Gregory Collins g...@gregorycollins.net wrote: A lock-free concurrent queue alone would be worth a summer project IMO. G Ryan Newton is already doing that (https://github.com/rrnewton/haskell-lockfree-queue). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Google Summer of Code 2012
It is that time of year again; the Google Summer of Code is upon us! If you are a student and want to sign up to make $5,000 for hacking on the code you love over the summer or are willing to help out as a mentor, now is the time to act. Please sign up by adding your name to the list at: http://hackage.haskell.org/trac/summer-of-code/wiki/People2012 Our main wiki entry for the Summer of Code 2012 is now online: http://hackage.haskell.org/trac/summer-of-code/wiki/Soc2012 If you are interested in applying as a student, here are some guidelines: http://hackage.haskell.org/trac/summer-of-code/wiki/StudApply2012 Student signups with Google start next week, but it is a good idea to start discussing things with potential mentors as soon as possible. The official * deadline* for student applications with Google is April 6th, but if you are interested please add your name to the People2012 page above, as soon as possible! *Interested in helping out, but not sure how?* There are a number of ideas that we've been collecting for projects available through the trac http://hackage.haskell.org/trac/summer-of-code/report/1 and which have been collecting over time in a reddit we used to use in years past: http://www.reddit.com/r/haskell_proposals/top/ While that reddit and the larger http://reddit.com/r/haskell reddit is a great place to discuss proposals, we had to choose one mechanism to supply Google with our ideas officially, so please submit proposals to the trac if you can think of something you like to work on, or which would be an appropriately beneficial project for a summer worth of work. *Helping Out Darcs* Haskell.org is planning to continue to act as an umbrella organization covering darcs for the Summer of Code once more. If you are interested in helping them out, they also have a page full of project ideas as well: http://wiki.darcs.net/GoogleSummerOfCode Again, please submit proposals as tickets to the trac if you can think of something you'd like to work on or have a neat idea for something someone else might want to work on (especially if you'd be willing to mentor it!) Of course, you can always feel free to email me or inquire on irc.freenode.net on #haskell or #haskell-soc or with the darcs folks over on #darcs for more information. If you don't have an IRC client, you can get there from: http://webchat.freenode.net Thank you all very much and we look forward to another successful Summer of Code! -Edward Kmett ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Are there arithmetic composition of functions?
By arithmetic I mean the everyday arithmetic operations used in engineering. In signal processing for example, we write a lot of expressions like f(t)=g(t)+h(t)+g'(t) or f(t)=g(t)*h(t). I feel it would be very natural to have in haskell something like g::Float-Float --define g here h::Float-Float --define h here f::Float-Float f = g+h --instead of f t = g t+h t --Of course, f = g+h is defined as f t = g t+h t I guess as long as all operands have the same number of arrows in there types then they should have the potential to be composed like this. Or g::Float-Float-Float --define g here h::Float-Float-Float --define h here f::Float-Float-Float f = g+h --means f x y = g x y + h x y -- f = g+h is defined as f x = g x+h x which in turn is defined as f x y = g x y+h x y This should be easy to implement, with TH perhaps. And I thought there would be a library (not in the language itself, of course) for this, but I haven't find one. Can someone tell me whether there is some implementation of such composition? If there isn't then I may build one. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
import Control.Applicative f, g :: Float - Float f x = x + 1 g x = 2 * x h = (+) $ f * g Cheers, =) -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
If you are willing to depend on a recent version of base where Num is no longer a subclass of Eq and Show, it is also fine to do this: instance Num a = Num (r - a) where (f + g) x = f x + g x fromInteger = const . fromInteger and so on. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
Hi,
If you are feeling adventurous enough, you can define a num instance for
functions:
{-# LANGUAGE FlexibleInstances #-}
instance Num a = Num (a - a) where
f + g = \ x - f x + g x
f - g = \ x - f x - g x
f * g = \ x - f x * g x
abs f = abs . f
signum f = signum . f
fromInteger = const . fromInteger
ghci let f x = x * 2
ghci let g x = x * 3
ghci (f + g) 3
15
ghci (f+g+2) 2
17
HTH,
Ozgur
On 19 March 2012 16:57, sdiy...@sjtu.edu.cn wrote:
By arithmetic I mean the everyday arithmetic operations used in
engineering.
In signal processing for example, we write a lot of expressions like
f(t)=g(t)+h(t)+g'(t) or f(t)=g(t)*h(t).
I feel it would be very natural to have in haskell something like
g::Float-Float
--define g here
h::Float-Float
--define h here
f::Float-Float
f = g+h --instead of f t = g t+h t
--Of course, f = g+h is defined as f t = g t+h t
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
The 17 at the end should be 12, or the 2 passed into (f+g+2) should be 3.
On Mon, Mar 19, 2012 at 10:38 AM, Ozgur Akgun ozgurak...@gmail.com wrote:
Hi,
If you are feeling adventurous enough, you can define a num instance for
functions:
{-# LANGUAGE FlexibleInstances #-}
instance Num a = Num (a - a) where
f + g = \ x - f x + g x
f - g = \ x - f x - g x
f * g = \ x - f x * g x
abs f = abs . f
signum f = signum . f
fromInteger = const . fromInteger
ghci let f x = x * 2
ghci let g x = x * 3
ghci (f + g) 3
15
ghci (f+g+2) 2
17
HTH,
Ozgur
On 19 March 2012 16:57, sdiy...@sjtu.edu.cn wrote:
By arithmetic I mean the everyday arithmetic operations used in
engineering.
In signal processing for example, we write a lot of expressions like
f(t)=g(t)+h(t)+g'(t) or f(t)=g(t)*h(t).
I feel it would be very natural to have in haskell something like
g::Float-Float
--define g here
h::Float-Float
--define h here
f::Float-Float
f = g+h --instead of f t = g t+h t
--Of course, f = g+h is defined as f t = g t+h t
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
On 19 March 2012 17:43, David Thomas davidleotho...@gmail.com wrote: The 17 at the end should be 12, or the 2 passed into (f+g+2) should be 3. It was the latter :) Copy/paste error, sorry. Ozgur ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
On Mar 19, 2012 11:40 AM, Ozgur Akgun ozgurak...@gmail.com wrote:
{-# LANGUAGE FlexibleInstances #-}
instance Num a = Num (a - a) where
You don't want (a - a) there. You want (b - a). There is nothing about
this that requires functions to come from a numeric type, much less the
same one.
--
Chris Smith
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
Hi Chris,
On 19 March 2012 17:58, Chris Smith cdsm...@gmail.com wrote:
On Mar 19, 2012 11:40 AM, Ozgur Akgun ozgurak...@gmail.com wrote:
{-# LANGUAGE FlexibleInstances #-}
instance Num a = Num (a - a) where
You don't want (a - a) there. You want (b - a). There is nothing about
this that requires functions to come from a numeric type, much less the
same one.
Thanks for catching this one, you are absolutely correct. I was carried
away by the original post using Float - Float for the example functions.
Cheers,
Ozgur
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Google Summer of Code idea of project application
2012/3/19 Richard O'Keefe o...@cs.otago.ac.nz On 19/03/2012, at 8:01 AM, Damien Desfontaines wrote: The project I suggest is mainly inspired by Ticket #1555 [1] : I think that would be a great idea to make it possible to call some Haskell code into OCamL. In particular, this would contribute to the spreading of Haskell in countries where OCamL is proeminent, mainly France and Italy. The idea would be the following : building a translator which would turn Haskell code into (purely functional) OCamL code, in order to enable the use of Haskell functions and libraries within OCamL programs, in a human-readable way (the OCamL source code generated would ideally be understandable enough to be manually modified). You might want to consider targeting F# as well as (or instead of) OCaml. I've had nothing but trouble with GODI, to the point where I gave up on OCaml entirely. On the other hand, F# came with Mono... Thank you for answering that fast and for your advices. I'm afraid I have absolutely no experience with F#. I guess I can learn it in several months, I heard it is derived from OCaml, but I think I would be really less efficient working with a brand new language such as F# instead of OCaml, which I already master. But the real question is : what would be the most useful ? I am quite convinced that I could work faster and most efficiently with OCaml than with F#, but if the community considers that such a project would be far more useful if I would translate Haskell into F# instead of OCaml, I can adapt. F# has built-in support for lazy evaluation (although it is not the default), so this might simplify your task. Indeed, F# has comprehensions too, so the main impedance mismatch would be typeclasses. This would make an F# target a sensible half-way point for an OCaml target. OCaml has a built-in module for lazy evaluation as well (even if it is not in the Pervasives (= default) module, and a syntax for list comprehensions as well. So, in my opinion, the main challenge would be dealing with typeclasses, exactly like in F#. 2012/3/19 Stephen Tetley stephen.tet...@gmail.com: Hi Damien A translator might be a lot of work. Matthew Naylor had a translator between Haskell and Clean [1], which performed well according to [2]. The translator was his Master project in the UK so I think that means it would represent approximately a years work. Thanks for your answer. I must admit that I do not really realize how much work such a project represents. I will probably need the help of someone who is more experienced than me to decide my timeline, and perhaps to restrict the final goal of my work (perhaps to a syntaxic subset of Haskell ?). If someone is interested in mentoring me for this work, I would be glad to discuss those technical details with him. Damien D. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Google Summer of Code idea of project application
Damien Desfontaines ddfontai...@gmail.com wrote: Thanks for your answer. I must admit that I do not really realize how much work such a project represents. I will probably need the help of someone who is more experienced than me to decide my timeline, and perhaps to restrict the final goal of my work (perhaps to a syntaxic subset of Haskell ?). I'll be a bit blunt, in the interest of encouraging you to be realistic before going too far down a doomed path. I can't imagine anyone at all thinking that a translator from a toy subset of Haskell into a different language would be useful in any way whatsoever. The goal of GSoC is to find a well-defined project that's reasonable for a summer, and is USEFUL to a language community. Restricting the project to some syntactic subset of Haskell is what people are *afraid* will happen, and why you've gotten some not entirely enthusiastic answers. It just won't do us any good, especially when there's no visible community of people ready to pick up the slack and finish the project later. One possible way out of this trap would be if, perhaps, the variant of Haskell you picked were actually GHC's core language. That could actually have a lot of advantages, such as avoid parsing entirely, removing type classes, laziness (I think... GHC did make the swap to strict core, didn't it?), and many other advanced type system features entirely, and being at least a potentially useful result that works with arbitrary code and all commonly used Haskell language extensions on top of the entire language. At least you are back into plausible territory. It still seems far too ambitious for GSoC, though. And I remain unconvinced how useful it really is likely to be. I'll grant there are other people that care a lot more about ML than I do. -- Chris Smith ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Google Summer of Code idea of project application
On Mon, Mar 19, 2012 at 17:06, Chris Smith cdsm...@gmail.com wrote: One possible way out of this trap would be if, perhaps, the variant of Haskell you picked were actually GHC's core language. That could (...) It still seems far too ambitious for GSoC, though. And I remain unconvinced how useful it really is likely to be. I'll grant there are other people that care a lot more about ML than I do. Core to F# gets GHC on the CLR, which if nothing else makes the Windows support situation for GHC look quite a lot better. (I am still bemused by MSR not being interested in better Windows support for GHC) -- brandon s allbery allber...@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
One problem with hooking functions into the Haskell numeric classes is right at the beginning: class (Eq a, Show a) = Num a where (+) (-) (*) negate abs signum fromInteger where functions are for good reason not members of Eq or Show. Look at http://www.haskell.org/haskellwiki/Numeric_Prelude for a different set of numeric classes that should suit you better. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
On Mon, Mar 19, 2012 at 7:16 PM, Richard O'Keefe o...@cs.otago.ac.nz wrote: One problem with hooking functions into the Haskell numeric classes is right at the beginning: class (Eq a, Show a) = Num a This is true in base 4.4, but is no longer true in base 4.5. Hence my earlier comment about if you're willing to depend on a recent version of base. Effectively, this means requiring a recent GHC, since I'm pretty sure base is not independently installable. -- Chris Smith ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
Richard O'Keefe: class (Eq a, Show a) = Num a where (+) (-) (*) negate abs signum fromInteger where functions are for good reason not members of Eq or Show. This is an old song, changed several times. I have no intention to discuss, but please, Richard O'Keefe: WHICH *GOOD* REASONS?? Thank you. Jerzy Karczmarczuk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Google Summer of Code idea of project application
On scoping the project: be clear about the actual goal. If you want to take existing Haskell libraries and use them in OCaml, then you pretty much have to deal with the full language. You should start by using as much as you can of an existing compiler, or by getting an unmodified compiler to convert source code to Core syntax. As just one example, a recent thread concerned implementing lock-free containers. I don't expect converting one of those to OCaml to be easy... If, however, you want to make it possible for someone to write code in a sublanguage of Haskell that is acceptable to a Haskell compiler and convert just *that* to OCaml, you might be able to produce something useful much quicker. It has long been my opinion that the TV series Butt-Ugly Martians was inspired by OCaml syntax. I keep being attracted by other features of OCaml, but unable to bring myself to use its syntax. (I have much the same problem with F#, and if SML.NET -- www.cl.cam.ac.uk/research/tsg/SMLNET/ -- had been updated in the last nearly 6 years I would not be looking at F# at all.) Never mind popularising Haskell to OCaml users; this could be a way of popularising OCaml to Haskell users. One of the reasons Harrop gives for preferring F# to OCaml is that F# supports true multicore concurrency, while OCaml apparently still doesn't. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Google Summer of Code - Lock-free data structures
On 19 March 2012 11:46, Ryan Newton rrnew...@gmail.com wrote: As Adam Foltzer mentioned in the trac ticket a really good structure would be the concurrent bags from this paper: http://www.cse.chalmers.se/~tsigas/papers/Lock%20Free%20Bag%20SPAA11.pdf We separately did a C implementation of those and they performed really well in our bake-off of producer consumer data structures (vs. TBB queues, and many other implementations). I've just read the paper and they look both useful and interesting to implement. Adam mentioned that GHC would need to be extended first, and I can't really judge how much work that would be. Can anyone chime in on how feasible that is? I'm less familiar with the literature on concurrent hash tables. TBB's have been a little bit underwhelming in performance. But it's definitely an important structure. Ditto for priority queues. The data structures I mentioned were just my initial ideas, I'm open to any other suggestions. In my (limited) experience with parallel programming, queues and priority queues tend to come up quite a bit, but I'd be happy to get input from anyone with more experience regarding what would be useful/important. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
On 20 March 2012 12:27, Jerzy Karczmarczuk jerzy.karczmarc...@unicaen.fr wrote: Richard O'Keefe: class (Eq a, Show a) = Num a where (+) (-) (*) negate abs signum fromInteger where functions are for good reason not members of Eq or Show. This is an old song, changed several times. I have no intention to discuss, but please, Richard O'Keefe: WHICH GOOD REASONS?? Because there are no sensible ways of writing such instances? -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com http://IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
On 20/03/2012, at 2:21 PM, Chris Smith wrote: On Mon, Mar 19, 2012 at 7:16 PM, Richard O'Keefe o...@cs.otago.ac.nz wrote: One problem with hooking functions into the Haskell numeric classes is right at the beginning: class (Eq a, Show a) = Num a This is true in base 4.4, but is no longer true in base 4.5. I didn't say GHC, I said Haskell. class (Eq a, Show a) = Num a where (+), (-), (⋆):: a - a - a negate :: a - a abs, signum :: a - a fromInteger :: Integer - a -- Minimal complete definition: -- All, except negate or (-) x - y= x + negate y negate x = 0 - x comes straight from the Haskell 2010 report: http://www.haskell.org/onlinereport/haskell2010/haskellch9.html#x16-1710009 There are other Haskell compilers than GHC. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
On 20/03/2012, at 2:27 PM, Jerzy Karczmarczuk wrote: Richard O'Keefe: class (Eq a, Show a) = Num a where (+) (-) (*) negate abs signum fromInteger where functions are for good reason not members of Eq or Show. This is an old song, changed several times. I have no intention to discuss, but please, Richard O'Keefe: WHICH GOOD REASONS?? It is still there in the Haskell 2010 report. The UHC user manual at http://www.cs.uu.nl/groups/ST/Projects/ehc/ehc-user-doc.pdf lists differences between UHC and both Haskell 98 and Haskell 2010, but is completely silent about any change to the interface of class Num, and in fact compiling a test program that does 'instance Num Foo' where Foo is *not* an instance of Eq or Show gives me this response: [1/1] Compiling Haskell mynum (mynum.hs) EH analyses: Type checking mynum.hs:3-11: Predicates remain unproven: preds: UHC.Base.Eq mynum.Foo: This is with ehc-1.1.3, Revision 2422:2426M, the latest binary release, downloaded and installed today. The release date was the 31st of January this year. GHC 7.0.3 doesn't like it either. I know ghc 7.4.1 is out, but I use the Haskell Platform, and the currently shipping version says plainly at http://hackage.haskell.org/platform/contents.html that it provides GHC 7.0.4. You may have no intention of discussing the issue, but it seems to *me* that this will not work in 2012 Haskell compiler mostly conforming to Haskell 2010 because Haskell 2010 says it shouldn't work is a pretty sound position to take. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
I don't understand this discussion. He explicitly said If you are willing to depend on a recent version of base. More precisely, he meant GHC 7.4 which includes the latest version of base. Yes, this is incompatible with the Haskell2010 standard, but it did go through the library submission process (unless I'm mistaken). It is also easy to add nonsense instances for functions to make this work with the Haskell2010 definition of the Num class. instance Eq (a - b) where f == g = error Cannot compare two functions (undecidable for infinite domains) instance Show (a - b) where show _ = function Yes, these instances are not very useful, but they let you get around this unnecessary restriction of the Num class. (I expect this to be fixed in future versions of the Haskell standard.) On 20 March 2012 02:37, Richard O'Keefe o...@cs.otago.ac.nz wrote: On 20/03/2012, at 2:27 PM, Jerzy Karczmarczuk wrote: Richard O'Keefe: class (Eq a, Show a) = Num a where (+) (-) (*) negate abs signum fromInteger where functions are for good reason not members of Eq or Show. This is an old song, changed several times. I have no intention to discuss, but please, Richard O'Keefe: WHICH GOOD REASONS?? It is still there in the Haskell 2010 report. The UHC user manual at http://www.cs.uu.nl/groups/ST/Projects/ehc/ehc-user-doc.pdf lists differences between UHC and both Haskell 98 and Haskell 2010, but is completely silent about any change to the interface of class Num, and in fact compiling a test program that does 'instance Num Foo' where Foo is *not* an instance of Eq or Show gives me this response: [1/1] Compiling Haskell mynum (mynum.hs) EH analyses: Type checking mynum.hs:3-11: Predicates remain unproven: preds: UHC.Base.Eq mynum.Foo: This is with ehc-1.1.3, Revision 2422:2426M, the latest binary release, downloaded and installed today. The release date was the 31st of January this year. GHC 7.0.3 doesn't like it either. I know ghc 7.4.1 is out, but I use the Haskell Platform, and the currently shipping version says plainly at http://hackage.haskell.org/platform/contents.html that it provides GHC 7.0.4. You may have no intention of discussing the issue, but it seems to *me* that this will not work in 2012 Haskell compiler mostly conforming to Haskell 2010 because Haskell 2010 says it shouldn't work is a pretty sound position to take. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Push the envelope. Watch it bend. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Google Summer of Code idea of project application
On Mon, Mar 19, 2012 at 7:52 PM, Richard O'Keefe o...@cs.otago.ac.nz wrote: As just one example, a recent thread concerned implementing lock-free containers. I don't expect converting one of those to OCaml to be easy... If you translate to core first, then the only missing bit is the atomic compare-and-swap primop that these structures will depend on. Maybe that exists in OCaml, or maybe not... I wouldn't know. If not, it would be perfectly okay to refuse to translate the atomic compare-and-swap primop that lockless data structures will use. That said, though, there are literally *hundreds* of GHC primops for tiny little things like comparing different sized integers and so forth, that would need to be implemented all on top of the interesting task of doing language translation. That should be kept in mind when estimating the task. If, however, you want to make it possible for someone to write code in a sublanguage of Haskell that is acceptable to a Haskell compiler and convert just *that* to OCaml, you might be able to produce something useful much quicker. I'm quite sure, actually, that implementing a usable sublanguage of Haskell in this way would be a much larger project even than translating core. A usable sublanguage of Haskell would need a parser, which could be a summer project all on its own if done well with attention to errors and a sizeable test suite. It would need an implementation of lazy evaluation, which can be quite tricky to get right in a thread-safe and efficient way. It would need type checking and type inference that's just different enough from OCaml that you'd probably have to write a new HM+extensions type checker and inference engine on your own, and *that* could again be far more than a summer project on its own, if you plan to build something of production quality. It would need a whole host of little picky features that involve various kinds of desugarings that represent man-decades worth of work just on their own. After a bit of thought, I'm pretty confident that the only reasonable way to approach this project is to let an existing compiler tackle the task of converting from Haskell proper to a smaller language that's more reasonable to think about (despite the problems with lots of primops... at least those are fairly mechanical). Not because of all the advanced language features or libraries, but just because re-implementing the whole front end of a compiler for even a limited but useful subset of Haskell is a ludicrously ambitious and risky project for GSoC. -- Chris Smith ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are there arithmetic composition of functions?
On 3/19/12 12:57 PM, sdiy...@sjtu.edu.cn wrote: By arithmetic I mean the everyday arithmetic operations used in engineering. In signal processing for example, we write a lot of expressions like f(t)=g(t)+h(t)+g'(t) or f(t)=g(t)*h(t). I feel it would be very natural to have in haskell something like You should take a look at Ralf Hinze's _The Lifting Lemma_: http://www.cs.ox.ac.uk/ralf.hinze/WG2.8/26/slides/ralf.pdf The fact that you can lift arithmetic to work on functions comes from the fact that for every type T, the type (T-) is a monad and therefore is an applicative functor. The output type of the function doesn't matter, except inasmuch as the arithmetic operations themselves care. This pattern has been observed repeatedly, even long before Haskell was around. But one reason it's not too common in production Haskell code is that it's all too easy to make a mistake when programming (e.g., you don't mean to be adding functions but you accidentally forget some argument), and if you're using this trick implicitly by providing a Num instance, then you can get arcane/unexpected/unhelpful error messages during type checking. But then you do get some fun line noise :) twiceTheSumOf = (+) + (+) squareTheSumOf = (+) * (+) cubeTheSumOf = (+) * (+) * (+) -- N.B., the names only make sense if all arguments -- are numeric literals. Don't look at the types. addThreeThings = (+) . (+) addFourThings = (+) . (+) . (+) addFiveThings = (+) . (+) . (+) . (+) -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Google Summer of Code idea of project application
On Mon, Mar 19, 2012 at 9:12 PM, Chris Smith cdsm...@gmail.com wrote: On Mon, Mar 19, 2012 at 7:52 PM, Richard O'Keefe o...@cs.otago.ac.nz wrote: As just one example, a recent thread concerned implementing lock-free containers. I don't expect converting one of those to OCaml to be easy... If you translate to core first, then the only missing bit is the atomic compare-and-swap primop that these structures will depend on. Maybe that exists in OCaml, or maybe not... I wouldn't know. If not, it would be perfectly okay to refuse to translate the atomic compare-and-swap primop that lockless data structures will use. That said, though, there are literally *hundreds* of GHC primops for tiny little things like comparing different sized integers and so forth, that would need to be implemented all on top of the interesting task of doing language translation. That should be kept in mind when estimating the task. If, however, you want to make it possible for someone to write code in a sublanguage of Haskell that is acceptable to a Haskell compiler and convert just *that* to OCaml, you might be able to produce something useful much quicker. I'm quite sure, actually, that implementing a usable sublanguage of Haskell in this way would be a much larger project even than translating core. A usable sublanguage of Haskell would need a parser, which could be a summer project all on its own if done well with attention to errors and a sizeable test suite. It would need an implementation of lazy evaluation, which can be quite tricky to get right in a thread-safe and efficient way. It would need type checking and type inference that's just different enough from OCaml that you'd probably have to write a new HM+extensions type checker and inference engine on your own, and *that* could again be far more than a summer project on its own, if you plan to build something of production quality. It would need a whole host of little picky features that involve various kinds of desugarings that represent man-decades worth of work just on their own. After a bit of thought, I'm pretty confident that the only reasonable way to approach this project is to let an existing compiler tackle the task of converting from Haskell proper to a smaller language that's more reasonable to think about (despite the problems with lots of primops... at least those are fairly mechanical). Not because of all the advanced language features or libraries, but just because re-implementing the whole front end of a compiler for even a limited but useful subset of Haskell is a ludicrously ambitious and risky project for GSoC. One can get a prototype up and running with a relatively low amount of effort by translating either GHC's core or stg. While core isn't fully strict, it is a much easier input language than Haskell. Stg is even lower level and easier to translate to imperative machines. I've read two papers where translators were built on or in GHC using this approach in a period that I would assume to be similar to what GSoC provides. In the case of the JVM, performance was an issue and may not be with CLR. The JVM lacking tailcalls and having a GC tuned to the wrong use patterns made optimization hard. I guess the way closures/thunks are implemented on the JVM side can be problematic for GC too; making it easy to run out of permgen space. After reading some papers and talking to the relevant folks a bit, I think the hardest part of translating Haskell to the JVM is building the RTS support. I assume the same will be true, but with different details, in the case of .NET/CLR. Both of the projects I'm thinking of just worked on Haskell 98, but to be good for real programs you want to support lots of RTS features. Once you've solved the RTS problems well enough to get people's attention the hurdle becomes the semantics of the FFI. You'll want to be compatible with the other VM languages. To mirror the critiques of others on this thread, I too have concerns about the community impact of the proposed translator. I'd also like to see this proposal written against an existing FOSS project. For example, if the proposal was to dust off LambdaVM (http://wiki.brianweb.net/LambdaVM/LambdaVM), update it to ghc HEAD and make reasonable progress on the implementation that seems much more useful to me. With that said, actually finishing a Haskell - .NET or Haskell - JVM implementation to the point of usable seems to be a PhD worth of work, not a single summer of work even if F# or Scala is the target language. I could also imagine the proposal being tweaked to talk about some improvement in the internals of GHC that make targeting JVM/CLR easier, although I don't personally know enough about GHC internals to suggest anything. I hope that helps, Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
