News aggregator

How to run a tree transformer on the GPU?

Haskell on Reddit - Tue, 04/29/2014 - 1:16am

Suppose I have a simple recursive binary-tree like:

data T = Add T T | Mul T T | Sub T T | Div T T | Num Int

Now say I define a recursive function on that datatype:

eval :: T -> T eval (Add a b) = (eval a) + (eval b) eval (Mul a b) = (eval a) * (eval b) eval (Div a b) = (eval a) / (eval b) eval (Sub a b) = (eval a) - (eval b) eval (Num a) = a

If I am not wrong, algorithms like this one, that fold over trees without context, are embarrassingly parallel.

eval (Add (Add 1 2) (Mul 3 4))

Here, (Add 1 2) and (Mul 3 4) could be executed in parallel. My question, is: is there a way to take similar functions, and make them run in parallel, on the GPU?

submitted by SrPeixinho
[link] [42 comments]
Categories: Incoming News

Christopher Done: The Identity monad trick

Planet Haskell - Mon, 04/28/2014 - 6:00pm

Update: Got the link! The Trivial Monad. Thanks, John. Naturally, all interesting Haskell things eventually lead back to Dan Piponi.

I heard about this from John Wiegley a while ago, but every time I recall it, I can’t remember how it goes, so I thought I’d write it down for myself. I think there’s a paper about it, but I can’t find it. Hopefully I’m recalling it correctly.

The Identity monad trick: Let’s say I want to expose an API that lets you work with a data structure. I want you to be able to keep hold of that data structure and pass it back into my library, and I’ll give it back to you later and we can go back and forth.

But I don’t want you to actually give you the data structure freely so you can go and give it to your friends. So instead I force you into the Identity monad, via a newtype wrapper that only I can unpack.

newtype Secret a = Secret { unSecret :: Identity a } deriving (Monad,Functor,Applicative)

And I have some function exposing it like:

getSecret :: Foo -> Secret Text

Here, use that. What can you do with it? You can’t extract the value out, you can only compose it with more functor or monad stuff:

fmap (map T.toUpper) (getSecret foo)

Or:

do text <- getSecret foo if all T.isUpper text then return (T.reverse text) else return text

Note that the whole type of this expression is Secret Text. You still don’t have the secret, you’ve got a computation over it.

You’ve used the value, but it never escaped1 the actual Identity monad. It’s like I’m giving you the value, but I’m also not giving you the value.

  1. As always, there’s a difference between “secure against your own stupidity” and “secure against attackers.” For the former, this is satisfied.

    For the latter, bottom complicates it, so you should force it in the IO monad and catch any exceptions e.g.

    extract :: Secret a -> IO (Maybe a)

    This prevents people from using

    (v >>= \a -> error ("The value is " ++ show a))

    To try to get around it.

    unsafePerformIO and other non-standard Haskell can get around it, but if you’re defending against developers, you probably have control over the environment, so you can just white-list the imports and extensions and there’s nothing they can do. This is what tryhaskell (via mueval) does.

Categories: Offsite Blogs

When will hackage.haskell.org be upgraded to cabal 1.20?

Haskell on Reddit - Mon, 04/28/2014 - 4:19pm

With cabal 1.20 being available now--does anyone know when hackage.haskell.org will be upgraded?

submitted by tempo3000
[link] [1 comment]
Categories: Incoming News

[n00b]A General Question on Program Architecture: How do I Manipulate and Preserve Data Structures?

Haskell on Reddit - Mon, 04/28/2014 - 2:16pm

I'm a 2nd year computer science student and I've been studying Haskell for about 2 months. I'd say I have a good handle on how the language works and what it is capable of. I would definitely like to continue to work in Haskell after my studies have concluded.

I have encountered a mental roadblock though. How do I write programs that work in the real world, and not just in the limited GHCi sandbox? More specifically, when using a data structure like a tree or a table, how do I manipulate said structure while still preserving a consistent reference to it?

Here's an example of a tree I wrote to help illustrate my problem:

-- leaf-labelled trees of arbitrary data type -- a tree is either empty or is a node with an element and two sub-trees data BinTree a = Empty | Node a (BinTree a) (BinTree a) -- inductive case deriving (Eq, Ord, Show) --make a new tree newTree :: BinTree Int newTree = Empty --check if node is leaf isLeaf :: (Eq a) => BinTree a -> Bool isLeaf (Node _ c b) = if c == Empty && b == Empty then True else False isLeaf Empty = False --create a new leaf leaf :: a -> BinTree a leaf x = Node x Empty Empty --insert an element insert :: (Ord a) => a -> BinTree a -> BinTree a insert x Empty = leaf x insert x (Node v c1 c2) | x >= v = Node v c1 newc2 |otherwise = Node v newc1 c2 where newc2 = insert x c2 newc1 = insert x c1

With this code I can make an empty tree, add element to it, and with minimal work I could write code to traverse the tree as well. However, when actually running my code, how do I preserve changes to the tree?

For example, in GHCi:

let tree = newtree --make new tree Empty --result insert 5 tree -- add 5 to the tree Node 5 Empty Empty -- awesome, a tree with a non empty node is returned

Now here's my hangup. The only way I see to preserve the changes I've made to the tree would be to "save" the return value to a new "variable" (since function names cannot be reassigned). The original tree that I made can never be altered. If I cannot save my changes, how on earth do I move forward and write programs in haskell?

The only potential solutions I see here are:

  • Use IO to constantly read and write to a text file, thus preserving changes to data.
  • Monads? Do monads help here somehow? I actually have yet to use these, not clear on what's going on here.

Any feedback here would be great. I've read a lot into haskell, and a lot of high level topics are often covered in great detail, but none of the material I've read really seems to explicitly cover software engineering topics in functional programming. Am I missing something here?

submitted by Joel_gh719
[link] [11 comments]
Categories: Incoming News

What functionality can you cram into the typesystem?

Haskell on Reddit - Mon, 04/28/2014 - 12:30pm

As a beginner to Haskell, I am a little skeptical about the gains claimed by having strong types, as many of the bugs I see are not about wrong types, but rather a lack of anticipation of particular values.

Perhaps I am just not fully grasping the abilities of the type system. Can haskell handle scenarios like this?:

  • A string with no more than 3 'a' characters
  • An integer-like type which is only ever prime numbers
  • A binary tree, which must be balanced

If not, are there any languages which can do this?

submitted by DrBroccoli
[link] [24 comments]
Categories: Incoming News

My road to Haskell

Haskell on Reddit - Mon, 04/28/2014 - 8:15am
Categories: Incoming News

The printer Haskell deserves

Haskell on Reddit - Mon, 04/28/2014 - 6:21am
Categories: Incoming News

Yesod Web Framework: Disemboweling WAI (aka gutting out conduit)

Planet Haskell - Mon, 04/28/2014 - 4:51am

The Haskell Web Application Interface- or WAI- serves as a low-level interface between web applications and servers. In order to do this in a resource-efficient manner, it avoids lazy I/O and instead uses explicit streaming. The story of how it does that streaming has evolved over time: it initially used its own home-brewed streaming abstraction. Later, Gregory Collins convinced me to switch over to enumerator. In the 1.0 release, it switched to conduit, which was essentially designed for the very purpose of supporting WAI's use cases. While I'm very happy with conduit, baking conduit into WAI makes the barrier to using a different streaming framework (like pipes) higher.

So today, I'm proposing that we go all the way back to the beginning, and remove dependencies on external streaming frameworks from WAI, making it a completely universal web interface for Haskell.

I've been hesitant about doing this in the past due to two different reasons:

  1. Making this change makes it more difficult to write handlers and middleware for WAI.
  2. It's not really possible to get rid of a streaming abstraction entirely; instead, we end up just having a locally baked abstraction, which is less thoroughly tested than existing abstractions.

On the first point, most middlewares and handlers which modify request and response bodies are already maintained by the WAI team (and mostly by me personally), so I'm less concerned about pushing such a burden out onto the community. Thankfully, applications and frameworks can be completely insulated by this change by providing a wai-conduit adapter package.

Regarding the second point, I've recently had some experience with this: refactoring http-client out of http-conduit. It turned out to be relatively painless, though I did end up having to reimplement a number of combinators from conduit (especially in the test suite). Nonetheless, the codebase is about the same level of complexity, given the low-level nature of the http-client library, and there's been an overwhelmingly positive response to the splitting up of those two packages, so I want to try it out with WAI as well.

I've created a no-conduit branch in the WAI repo. Currently, I've converted the wai and warp repos over to be conduit-free (with a few helper functions stubbed out). And Warp passes its full test suite, which is rather promising.

The streaming interface is relatively simple. In order to consume a request body, you use the function:

requestBody :: Request -> IO ByteString

This function returns the next strict ByteString from the request body in the stream, or an empty ByteString if the body has been fully consumed. On the response side, you write an application with the type:

(Maybe Builder -> IO ()) -> IO ()

The argument function is used for emitting data to the user. If you provide a Just value, it sends the data in, and a Nothing value flushes the stream. (Currently, WAI uses the Flush data type from conduit for this purpose.)

The code is not yet ready to be released, but it is ready for some review and discussion. I'm hoping to hear community feedback, both from current users of WAI, and those who are considering using it (either directly in an application, or as part of a framework).

A separate breaking change that came up when working on this feature has to do with safe resource allocation and the definition of Application. In WAI 2.0, we introduced the function responseSourceBracket, which is a version of bracket that works for WAI applications. Internally to Warp (and every other WAI handler), we had to jump through some hoops to make sure async exceptions were all masked and restored properly. We also had to make our definition of ResponseSource a bit ugly to make this all possible.

Now with the move away from Sources, we have two choices: either perpetuate the strangeness in the ResponseStream and ResponseRaw constructor, or add bracket semantics to the entirety of a WAI application. In terms of code, I'm talking about replacing:

type Application = Request -> IO Response

with

type Application = Request -> (forall b. (Response -> IO b) -> IO b)

I've implemented this idea as well. It certainly makes the Warp codebase easier to follow, and allows for some slightly more powerful applications (e.g., acquiring a resource for use in some lazy I/O performed by ResponseBuilder). The downsides are:

  • Yet another breaking change.
  • It's harder to explain the intuition versus the dead simple Application we have now.
  • It will likely make middlewares significantly harder to write, though I'll admit that I haven't tried that yet.

When I discussed this change with Gabriel, he pointed out his Managed data type as a possible approach to make the signatures and usage slightly less scary. That would mean:

newtype Managed r = Managed { _bind :: forall x . (r -> IO x) -> IO x } type Application = Request -> Managed Response

Managed would be nice in that it provides a number of instances (including Monad), but it makes the WAI API a little bit denser to grok. I think I'm leaning against that direction, but wanted to raise this in the discussion as well.

Categories: Offsite Blogs

Monadic Sorting without Space Leaks

Haskell on Reddit - Sun, 04/27/2014 - 8:52pm

I'm always worried that space leaks will sneak up on me. Here's some quick code I sketched out when I was thinking about how to sort with an IO comparator. Is there a space leak?

It's a standard merge sort.

sort aL = merge . map (\x -> [x]) $ aL merge [] = return [] merge [a] = return a merge aL = mergePairs aL >>= merge mergePairs (a1:a2:aL) = do b <- merge2 a1 a2 --maybe here? bL <- mergePairs aL return (b:bL) mergePairs aL = return aL merge2 (a:aL) (b:bL) = do comp <- compareIO a b let (z,aL',bL') = if comp == GT then (b,a:aL,bL) else (a,aL,b:bL) zL <- merge2 aL' bL' --maybe here? return (z:zL) merge2 aL bL = return (aL++bL)

PS: If I'm inside IO, is there a way of doing it so that I can get the first few elements early without doing the whole operation? (even better if it's sometimes possible outside IO, but I don't know if that's possible) I think it's impossible unless you use unsafePerformIO and guarantee/promise that there are no side effects to the comparison operation, but I'm not sure.

submitted by TimTravel
[link] [5 comments]
Categories: Incoming News

Audrey Tang: Programming Languages and RailsGirls.tw

Planet Haskell - Sun, 04/27/2014 - 8:51pm
<article class="en">

(My talk at TEDxTaipei at 2014-04-27, before a panel with Linda Liukas, Matz and Charles Nutter. Slides in Chinese. 逐字稿中文版.)

Thanks, Linda, for sharing your fascinating story.

As my talk is about "Programming Languages and RailsGirls.tw", I'd like to start with a few stories of programming languages.

As we know, Rails is built on the Ruby language. Matz created Ruby by blending his five favorite languages together: Ada, Eiffel, Lisp, Perl, and Smalltalk.

I cannot cover all of them in a 20-minute talk, so let us start with Ada. Ada comes first in this list not only because its name starts with an "A", but also because it was named after Ada Lovelace, the world's first computer programmer.

In 1842, Ada wrote this program for the Analytical Engine, the first general-purpose computer ever designed but not constructed until a century later. Ada was also the first to realize that computers are not limited to work with numbers; she envisioned that people would compose music and create art on a computer.

Ada's mother was Annabella, a gifted scholar of mathematics. Ada's father, the great Romantic poet Byron, nicknamed his wife the "princess of parallelograms" because of her strict morality with a mathematical rigor.

And indeed, the art of computer programming is a blend of mathematics and poetry. Like a mathematical formula, good programs are rigorous and correct. Programmers, however, work like poets — we are creative with our languages, we convey a sense of purpose in a concise way, and we inspire each other to carry on our work.

As Professor Dijkstra put it: "Besides a mathematical inclination, an exceptionally good mastery of one's native tongue is the most vital asset of a competent programmer."

Both mathematicians and poets require a coherent vision to guide their work. The same principle applies to professional programming: Without a coherent vision and design integrity, sloppy programs quickly become unmaintainable, such that any attempts to fix a bug will introduce more bugs.

However, professional programming is not the only kind of programming, or even the most popular one. For nearly twenty years, the most well-known language on the web has been JavaScript, a "scripting language" that's easy to start with, but that also makes it very easy to write sloppy programs with a lot of bugs.

The distinction between scripting and programming languages dates back to the 1970s, with the introduction of the C language, a portable language that runs on almost any computer. Computer scientists in Bell Labs wrote hundreds of programs in C that worked together as a complex operating system, and they called it Unix.

Users of the Unix system were not expected to program in C. Instead they wrote "shell scripts" that were simple to write — mostly just a list of commands — but very difficult to maintain once they got complex.

Throughout the 1980s, the worldview was that there were programs written in complex and powerful languages like Objective-C and C++; and there were scripts written in simple but limited languages like sed and AWK.

The picture here is a linear spectrum with nothing in-between. If a script became too complex to maintain, people would just re-write it in a "real" programming language like C++.

In 1987, Larry Wall said, "We can open up this spectrum and turn it into a space with two dimensions." He saw C's strength as "Manipulexity", the ability to manipulate complexity, while shell scripts excel at "Whipuptitude", the ability to whip things up quickly.

Perl was hatched in this newfound space, as a language that could do a little bit of both, and one that evolves by redefining its own vocabulary. Over time, Perl evolved to be better at Whipuptitude than any shell scripts, and as good as C++ and Java at Manipulexity for all but the most complex programs.

With Perl, one could start with a sloppy script and, through "refactoring" techniques, gradually make it more rigorous and correct over time, without having to switch to a different language.

In the 1990s, a new generation of Perl-influenced languages appeared, such as  Python, PHP, and Ruby. Each of them improved upon Perl toward their own domains; I consider Ruby the most flexible of the three.

In 2005, the Rails project combined Ruby on the server side and JavaScript on the client side into a full-stack web framework. For many people working with C++ or Java, Rails showed them for the first time that "scripting" languages can build web programs that are more complex, and of larger scale, than contemporary "programming" languages could.

Rails succeeded in part because of its use of meta-programming, which provided way to program the Ruby language itself into domain-specific languages such as ActiveRecord.

Since that time, popular frameworks such as jQuery and AngularJS have taken the same approach to JavaScript, allowing programmers to express our vision and design integrity with a re-programmed language that's much more rigorous and safe.

In the 2010s, Rails adopted CoffeeScript, a Ruby-like language that compiles into "the good parts" of JavaScript, to complement its use of the jQuery framework. This is an extension of the meta-programming idea — changing a language by keeping the best parts of it.

People in the Perl community took CoffeeScript to create the Coco language, and people in the Haskell community took Coco to create LiveScript. Nowadays, most of my programming is done in LiveScript, which allows me to express the same vision in a way that looks like Ruby, or looks like Perl, or looks like Haskell, whichever way that's most appropriate for the poem, er, program.

So those are my stories about Rails and programming languages. For the next half of my talk, I'd like to talk about the "Girls" part in Rails Girls.

In the first half of the 20th century, people working for women's rights have achieved a lot of legal victories, bringing equality in rights of voting, of education, of individual economy, of marriage and divorce to many people in the world.

However, this equality in law does not readily translate to equality in practice. As Simone de Beauvoir observed in 1949, many societies make women feel inferior not by law, but through the act of "Othering" in languages and in actions. Men are presumed as the default subject, and women are constantly reminded that they are the collective "Other" by the way they are treated, as a group different from the default.

In the 1970s, social workers and thinkers applied Simone's thoughts and observed various socially-constructed expectations known as gender roles. For example, a particular society may confine women into one of two primary roles: either as a Girl — an adorable object of desire, harmless and of inferior status; or as a Mother — a caretaker, provider of emotional support, and a reproductive agent.

What's missing in this picture is, of course, the various destinies that each of us wish upon ourselves. We encounter social pressure whenever we happen to contradict one of the expected roles.

We can fix this problem by adopting the vision: That Biology should not determine Destiny. In practical terms, it is helpful to re-introduce the concepts of "scripts" and "programs", this time from the field of social studies.

Larry Wall said this in his 2007 talk on scripting languages: "Suppose you went back to Ada Lovelace and asked her the difference between a script and a program. She'd probably look at you funny, then say something like: 'Well, a script is what you give the actors, but a program is what you give the audience.' That Ada was one sharp lady..."

Here we see social "scripts" are actions expected of people to act according to their roles. In contrast, a "program" informs participants what to expect from the social "norm", but does not dictate people's behaviors the way scripts do.

As a concrete example, when I began my IT career as the webmaster of a small publishing house "The Informationist" in 1994, I worked both online via a BBS and in the office. Many of our staffs were openly LGBTQ and LGBTQ-supporting; it was a safe space for me to explore my gender expressions.

The press turned into a software company named "Inforian" in 1995, when I became its CTO, and started participating in the global Free Software community. While Taiwan's software sector at that time was generally gender-balanced, it shocked me to find that male-dominant scripts were prevalent in online Free Software communities.

After a while, I learned that many women on forums and chatrooms used male-sounding nicknames, not because it was their preferred gender expression, but as a protection against harassment. This was obviously a problem.

In 1998, the Open Source movement started and I helped run a few startups in the Silicon Valley, China, and Taiwan. As I started attending conferences and giving talks, I couldn't help but notice the lack of variety in gender expressions and in ethnic distribution.

For example, I heard the question "are you here with your boyfriend?" asked many times in these conferences, but not once "are you here with your girlfriend?" or "are you here with your partner?" — it was clearly a social script to make the recipient feel identified as an "other" — an outsider instead of a participant in the space.

After I returned to Taiwan to work on local open culture communities, I started consciously using the feminine pronoun in all my Chinese online writings, in an attempt to turn around the language's "othering" aspect.

When we started organizing our own conferences in 2003, I also took efforts to invite only the most socially compassionate speakers from abroad, who helped establish a more relaxed atmosphere where people can enjoy a safe space.

However, as Open Source gained commercial popularity, sexualized practices of IT industries' trade shows started to affect our conferences as well. One of these practices is promotional models, hired to drive interests to a vendor's booth; another is offensive imagery in conference contents, including from prominent speakers in both Free Software and Open Source communities.

In 2009, Skud, a long-time fellow hacker in the Perl community, started to speak widely at conferences on this subject. She created "Geek Feminism", a wiki-and-blog platform to list the issues and work together to improve them.

After a year's work, participants in the wiki created a "Code of Conduct" template, a social "program" that sets the expected norms. Valerie Aurora and Mary Gardiner, two Geek Feminism contributors from the Linux community, co-founded the Ada Initiative in 2011, so they can work full-time to support women in open technology and culture.

With help from many contributors, the Ada Initiative worked with over 100 conference organizers to adopt the code of conduct program. I'm very glad to see the upcoming "Rails Girls Summer of Code" event among the list of adopters.

There are three main elements of such a program:

  • Specific descriptions of common but unacceptable behavior (sexist jokes, etc.)
  • Reporting instructions with contact information
  • Information about how such policies are enforced

Together, they ensure a space where people can be aware of their own social scripts and their effects on each other and refactor them into a more sustainable community with openness and variety as a coherent vision.

There are many more activities from the Ada Initiative, and we have a list of resources and communities on the Geek Feminism wiki, which I'd like to invite you to visit.

To me, the most enlightening bit is perhaps not in the code itself, but in its programming — the fine-tuning of a conduct that fits best with the local culture.

When we create a safe space for a community's participants, to observe and decide our own social scripts, we can collectively program a social norm that is both rigorous and creative — just like the best formulas, poems, and programs.

In conclusion, I'd like to share two poetic fragments of mine with you:

    I would like to know you
        not by your types,
            classes or roles —
    — but by your values.

...and:

    Saying "Life is what we make it to be",
        is like saying "Language is what we make it to be" —
            True, but not at once;
                — just one bit at a time.

Thank you.

</article>
Categories: Offsite Blogs

Some implementation questions

Haskell on Reddit - Sun, 04/27/2014 - 7:10pm

I'm learning Haskell (as some who have graciously responded to other questions already know) and I have a couple of questions about implementation and optimization. Now I'm well aware that premature optimization is a bad thing but I'm slightly troubled about a couple of things and would appreciate some insights.

1) Lists --- I know lists can be treated as lazy but assuming that all elements in a list will be accessed, how does one deal with really large lists or (more often) trees when there's a change? The articles I've read (so far) seem to imply that these structures are immutable and so a complete copy of the tree (and presumably whatever it contains) is made anytime there's a change. This would seem to me to be infeasible if you have large (hundreds of thousands of elements) structures.

2) Data structure representation: suppose I create a simple data structure like the following:

data Bar = Bar Double Double Double Double

how much actual space (if any) beyond that needed to represent the 4 doubles is required? If you have a list of these things wrapped in an Either a b structure, how much information is kept around beyond the actual floating point numbers?

Thanks,

submitted by dhjdhj
[link] [14 comments]
Categories: Incoming News

PureScript 0.5 Released

Haskell on Reddit - Sun, 04/27/2014 - 4:28pm
Categories: Incoming News

Game programming in Haskell: is it possible to replace Unity3D's deploying style?

Haskell on Reddit - Sun, 04/27/2014 - 3:42pm

Is there a way to write a 3D game in Haskell, such that, after creating it, you are able to deploy to many different platforms? Unity3D is really nice because, once you create a game, you can export it to Android, iOS and even for the Browser.

I fear that by creating a game in Haskell, it would probably be a good learning experience, but then I'd be left with a impossible to deploy product, which would only work on desktop OSes and would require my user to download it. Nobody wants to download software those days.

submitted by SrPeixinho
[link] [8 comments]
Categories: Incoming News