News aggregator

Breathing Code

del.icio.us/haskell - Fri, 03/27/2015 - 1:02am
Categories: Offsite Blogs

Haskell Weekly News: Issue 322

General haskell list - Thu, 03/26/2015 - 11:24pm
New Releases 99 Haskell: A web service by Bram Hoskin Solve live Haskell coding problems based on H-99 in the browser to strengthen your understanding of the language. http://www.99haskell.org/ https://github.com/bramgg/99haskell/ Magic Cookies A commercial Android game is released that is written in Haskell using SDL2 for multimedia and the Arrowized Functional Reactive Programming DSL Yampa. The authors had to "escape their functional comfort zones and come up with smarter abstractions that mutable reality and performance demand". The game consists of 2K lines of code, of which 1K is game specific and 400 are Yampa code. The most complex parts were certain Yampa constructs (arrow-based, with lots of tupling/untupling). http://keera.co.uk/blog/2015/03/19/magic-cookies-released-google-play/ https://play.google.com/store/apps/details?id=uk.co.keera.games.magiccookies https://github.com/keera-studios/keera-hails https://github.c
Categories: Incoming News

ansi-wl-pprint

libraries list - Thu, 03/26/2015 - 9:19pm
ansi-wl-pprint sits underneath a large chunk of our infrastructure: test-framework, criterion, trifecta, etc. Transitively through those dependencies it affects a very large percentage of the Haskell packages we have today, because you can't build almost anybody's testing and benchmarking frameworks without it. We recently had to push out an non-maintainer update for GHC 7.10-rc3 compatibility, and due to NMU update guidelines meant we had to wait 2 weeks before we could do anything. This pretty much ensured that the entire 7.10-rc3 release cycle went by with very very few people able to run their test suites, and little testing was able to be performed in the allotted window. Fortunately, Neil managed to find a rather large regression on his own during this time: http://neilmitchell.blogspot.com/2015/03/finding-ghc-bug.html That said, given that we found issues with linear caused by the changes to Typeable, once we fixed the test suite, this gives me pause. I'm pretty sure nobody downstream of linear tr
Categories: Offsite Discussion

Danny Gratzer: Value vs Monomorphism Restriction

Planet Haskell - Thu, 03/26/2015 - 6:00pm
Posted on March 27, 2015 Tags: sml, haskell

I’m taking the undergraduate course on programming languages at CMU. For the record, I still get really excited about the novelty of taking a class (at school!) on programming languages. I’m easily made happy.

We started talking about System F and before long we touched on the value restriction. Specifically, how most people think of the value restriction incorrectly. To understand why this is, let’s first define the value restriction since it’s probably new to you if you don’t use SML.

The Value Restriction

In SML there are value level declarations just like in Haskell. We can write things like

val x = 1 val y = x + 1

and we end up with x bound to 1 and y bound to 2. Note that SML is strict so these bindings are evaluated right as we reach them. Also like in Haskell, SML has polymorphism, so we can write map

fun map f [] = [] | map f (x :: xs) = f x :: map f xs

And it gets the type ('a -> 'b) -> ('a list -> 'b list). Aside from minor syntatic differences, this is pretty much identical to what we’d write in Haskell. The value restriction concerns the intersection of these two things. In SML, the following should not compile under the standard

val x = rev []

This is because SML requires that all polymorphic val bindings be values! In practice all implementations will do something besides this but we’ll just focus on what the standard says. Now the reason for this value restriction is widely misunderstood. Most people believe that the value restrictions

val r = ref NONE val () = r := SOME 1 val _ = case !r of SOME s => s | NONE => ""

This seems to illustrate a pretty big issue for SML! We’re filling in polymorphic reference with one type and unboxing it with a different one! Clearly this would segfault without the value restriction. However, there’s a catch.

SML is based on System F (did you really think I could get through a blog post without some theory?) which is sometimes called the “polymorphic lambda calculus”. It’s the minimal language with polymorphism and functions. In this language there’s a construct for making polymorphic things: Λ.

In this language we write polymorphism explicitly by saying Λ τ. e which has the type ∀ t. T. So for example we write the identity function as

id ≡ Λ τ. λ x : τ. x () = id[unit] ()

Now SML (and vanilla Haskell) have a limited subset of the power of Λ. Specifically all these lambdas have to appear at the start of a toplevel term. Meaning that they have to be of the form

val x = Λ α. Λ β. ... e

This is called “prenex” form and is what makes type inference for SML possible. Now since we don’t show anyone the hidden Λs it doesn’t make sense to show them the type application that comes with them and SML infers and adds those for us too. What’s particularly interesting is that SML is often formalized as having this property: values start with Λ and are implicitly applied to the appropriate types where used. Even more interesting, how do you suppose we should evaluate a Λ? What for example, should this code do

val x = Λ τ. raise[τ] Fail (* Meaning raise an exception and say we have type τ *) val () = print "I made it here" val () = x[unit]

It seems clear that Λ should be evaluated just like how we evaluate λ, when we apply it. So I’d (and the formalization of SML) would expect this to print "I made it here" before throwing that exception. This might now surprise you just by parallels with code like this

val x = fn () => raise[τ] Fail val () = print "I made it here" val () = x ()

However, what about when those lambdas are implicit? In the actual source language of ML our code snippet would be

val x = raise Fail val () = print "I made it here" val () = x[unit]

Uhoh, this really looks like it ought to throw an exception but it apparently doesn’t! More worringly, what about when we have something like

fun die () = raise Fail val x = die () val () = print "Made it here"

Since x is never specialized, this doesn’t even throw an error! Yikes! Clearly this is a little confusing. It is however, type safe. Consider our original motivation for the value restriction. With explicit type application

val r = Λ τ. ref[τ] NONE val () = r[int] := SOME 1 val _ = case !(r[string]) of SOME s => s | NONE => ""

Since the body of this function is run every time we do something with r, we’re just creating a whole bunch of new references in this code! There’s no type safety failure since !(r[string]) returns a fresh ref cell, completely different from the one we modified on the line above! This code always runs the NONE case. In fact, if this did the wrong thing it’s just a canary in the coal mine, a symptom of the fact that our system evaluates under (big) lambda binders.

So the value restriction is really not at all about type safety, it’s about comprehensibility. Mostly since the fact that a polymorphic expression is evaluated at usage rather than location is really strange. Most documentation seems to be wrong about this, everyone here seems agree that this is unfortunate but such is life.

The Monomorphism Restriction

Now let’s talk about the monomorphism restriction. This is better understood but still worth recapping. In Haskell we have type classes. They let us overload function to behave differently on different types. Everyone’s favoriate example is the type class for numbers which let’s us write

fact :: (Eq a, Num a) => a -> a fact 0 = 1 fact n = n * fact (n - 1)

And this works for all numbers, not just int or something. Under the hood, this works by passing a record of functions like *, fromInteger, and - to make the code work. That => is really just a sort of function arrow that happens to only take particular “implicit” records as an argument.

Now what do you suppose the most polymorphic type this code is?

x = fact 10000

It could potentially work on all numbers so it gets the type

x :: (Num a, Eq a) => a

However this is really like a function! This means that fact :: Integer and fact :: Int evaluate that computation twice. In fact each time we call fact we supply a new record and end up evaluating again. This is very costly and also very surprising to most folks. After all, why should something that looks like a normal number evaluate every time we use it! The monomorphism restriction is essentially

  1. If you have a binding
  2. Whose type is (C1, C2 ...) => t
  3. And has no arguments to the left of the =
  4. Don’t generalize it

This is intended to keep us from the surprise of evaluating a seemingly fully reduced term twice.

Sound familiar? Just like with the value restriction the whole point of the monomorphism restriction is to prevent a hidden function, either type abstraction or type constraints, from causing us to silently and dangerously duplicate work. While neither of them are essential to type safety: without it some really simple looking pieces of code become exponential.

Wrap Up

That about covers things. It turns out that both of these restrictions are just patches to cover some surprising areas of the semantics but both are easily understood when you look at the elaborated version. I deliberately went a bit faster through the monomorphism restriction since quite a lot of ink has already been spilled on the subject and unlike the value restriction, most of it is correct :)

As one final note, the way that Haskell handles the monomorphism restriction is precisely how OCaml handles the value restriction: weak polymorphism. Both of them mark the type variables they refuse to generalize as weak type variables. Whenever we first instantiate them to something we go back and retroactively modify the definition to pretend we had used this type all along. In this way, we only evaluate things once but can handle a lot of simple cases of binding a value and using it once.

The more you know.

<script type="text/javascript"> var disqus_shortname = 'codeco'; (function() { var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true; dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js'; (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq); })(); </script> <noscript>Please enable JavaScript to view the comments powered by Disqus.</noscript> comments powered by Disqus
Categories: Offsite Blogs

Manuel M T Chakravarty: Schrödinger’s Box

Planet Haskell - Thu, 03/26/2015 - 5:43pm

In Objective-C, NSValue provides a universal container that can hold scalars and value types in addition to references. Conversely, in Swift, we quickly learnt to appreciate Box<T> as a wrapper to embed (cyclic) references in enums and structs (especially due to limitations in the initial versions of the Swift compiler):

final public class Box<T> { public let unbox: T public init(_ value: T) { self.unbox = value } }

NSValue is also useful to wrap reference. For example, if we want to turn a strong reference into a weak reference (possibly to store it in a collection, such as NSArray), we can create an NSValue with +valueWithNonretainedObject.

How do we achieve that in Swift without losing type information, as using NSValue would? We use Schrödinger’s Box:

final public class WeakBox<T: AnyObject> { private weak var box: T? public var unbox: T? { get { return box } } public init(_ value: T) { self.box = value } }

You can put something into Schrödinger’s Box, which will or will not be gone by the time you try to retrieve it. It enables, for example, to build a typed collection of weakly referenced objects (to avoid retain cycles).

NB: The definition of WeakBox is fine with the latest Swift 1.2 compiler. However, the Swift 1.1 compiler can only handle it with -Onone; otherwise, it crashes.

Categories: Offsite Blogs

Neil Mitchell: New website with new talks

Planet Haskell - Thu, 03/26/2015 - 4:01pm

My website is now located at ndmitchell.com and has a few new talks on it:

My old website at community.haskell.org is going to stop being updated, and I'll be putting in redirections shortly. That server is going to stop hosting websites, so I bought myself a domain name and setup a GitHub pages website. The repo is here, including all the data, metadata, templates and scripts.

Categories: Offsite Blogs

Do we have idiom for lifting a state monad into pairof states?

haskell-cafe - Thu, 03/26/2015 - 9:28am
Consider you have developed library routines that act on (State s1 a). For some reason, you need more than one state simultaneously. Let's say two side by side for simple example, that is (State (s1,s2) a). To use library functions on one state monad in a two state monad, we need to wrapper that lifts actions of (State s1 a) to (State (s1,s2) a). It is not difficult to write a lifter for such purposes as below. It is kind of like doing liftA in Applicative libarary, but instead of the last argument 'a' but on the fist argument 's' of (State s a). This seems like an idiom that can often come up. So, I tried some searching in some applicative related libraries and monad transformer related libraries but haven't found this idiom yet. If you had a need for idioms like below, what do you call it? Or, is there a way more general way I've missed that makes this a very special case of it. > import Control.Monad.State > import Control.Monad.Error > import Control.Applicative > > -- lift an action ov
Categories: Offsite Discussion

VSTTE 15, Second Call for Papers

General haskell list - Thu, 03/26/2015 - 8:41am
********************************************************************** 7th Working Conference on Verified Software: Theories, Tools, and Experiments July 18 - 19, 2015 San Francisco, California, USA http://www.eecs.berkeley.edu/vstte15 Co-located with 25th Conference on Computer Aided Verification (http://i-cav.org/2015) ********************************************************************** Full Paper Submission Deadline: April 27, 2015 SCOPE: The Seventh Working Conference on Verified Software: Theories, Tools, and Experiments follows a successful inaugural working conference at Zurich in 2005 followed by conferences in Toronto (2008), Edinburgh (2010), Philadelphia (2012), Atherton (2013), and Vienna (2014). The goal of this conference is to advance the state of the art in the science and technology of software verification, through the interaction of theory development, tool evolution, and experimental validation. We welcome submissions describing significant advances in the production of verified s
Categories: Incoming News

I'm gonna Write Myself A Scheme - any things I should look out for (a la the RWH problems)?

Haskell on Reddit - Thu, 03/26/2015 - 8:18am

If you hav any questions, just ask!

Edit: Hey, why the downvote? I'd think requesting errata for one of the most popular intermediate-level Haskell tutorials is "Constructive".

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

how to determine the physical harddrive a file is on?

Haskell on Reddit - Thu, 03/26/2015 - 4:27am

Hello there, I had some haskell in university but have a strong scala background and decided to give haskell a try again. My first haskell post ever...

As an useful exercise, I want to write a duplicate scanner, which shall run in parallel. However, the parallelization factor should match the amount of >physical drives< that have to be scanned. Logical drives / partitions would likely decrease performance because then the HD head has to jump uselessly. For that, I need a way to determine the drive and in particular distinguish logical from physical drives. In scala/ on the JVM, this doesn't seem to be possible, so I resorted to an external bash command. Is this possible in haskell directly?

submitted by ib84
[link] [6 comments]
Categories: Incoming News

FP Complete: Our composable community infrastructure

Planet Haskell - Wed, 03/25/2015 - 11:50pm
Our composable community infrastructure

TL;DR: we propose to factor Hackage into a separate, very simple service serving a stash of Haskell packages, with the rest of Hackage built on top of that, in the name of availability, reliability and extensibility.

One of the main strengths of Haskell is just how much it encourages composable code. As programmers, we are goaded along a good path for composability by the strictures of purity, which forces us to be honest about the side effects we might use, but first and foremost because first class functions and lazy evaluation afford us the freedom to decompose solutions into orthogonal components and recompose them elsewhere. In the words of John Hughes, Haskell provides the necessary glue to build composable programs, ultimately enabling robust code reuse. Perhaps we ought to build our shared community infrastructure along the same principles: freedom to build awesome new services by assembling together existing ones, made possible by the discipline to write these basic building blocks as stateless, scalable, essentially pure services. Let's think about how, taking packages hosting as an example, with a view towards solving three concrete problems:

  • Availability of package metadata and source code (currently these are no longer available when hackage.haskell.org goes down).
  • Long cabal update download times.
  • The difficulty of third party services and other community services to interoperate with hackage.haskell.org and extend it in any direction the community deems fit.
Haskell packages

Today Haskell packages are sets of files with a distinguished *.cabal file containing the package metadata. We host these files on a central package repository called Hackage, a community supported service. Hackage is a large service that has by and large served the community well, and has done so since 2007. The repository has grown tremendously, by now hosting no less than 5,600 packages. It implements many features, some of which include package management. In particular, Hackage allows registered users to:

  • Upload a new package: either from the browser or via cabal upload.

  • Download an index of all packages available: this index includes the full content of all *.cabal files for all packages and all versions.

  • Query the package database via a web interface: from listing all packages available by category, to searching packages by name. Hackage maintains additional metadata for each package not stored in the package itself, such as download counts, package availability in various popular Linux distributions. Perhaps in the future this metadata will also include social features such as number of "stars", à la Github.

Some of the above constitute the defining features of a central package repository. Of course, Hackage is much more than just that today - it is a portal for exploring what packages are out there through a full blown web interface, running nightly builds on all packages to make sure they compile and putting together build reports, generating package API documentation and providing access to the resulting HTML files, maintaining RSS feeds for new package uploads, generating activity graphs, integration with Hoogle and Hayoo, etc.

In the rest of this blog post, we'll explore why it's important to tweeze out the package repository from the rest, and build the Hackage portal on top of that. That is to say, talk separately about Hackage-the-repository and Hackage-the-portal.

A central hub is the cement of the community

A tell-tale sign of a thriving development community is that a number of services pop up independently to address the needs of niche segments of the community or indeed the community as a whole. Over time, these community resources together as a set of resources form an ecosystem, or perhaps even a market, in much the same way that the set of all Haskell packages form an ecosystem. There is no central authority deciding which package ought to be the unique consecrated package for e.g. manipulating filesystem paths: on Hackage today there are at least 5, each exploring different parts of the design space.

However, we do need common infrastructure in place, because we do need consensus about what package names refer to what code and where to find it. People often refer to Hackage as the "wild west" of Haskell, due to its very permissive policies about what content makes it on Hackage. But that's not to say that it's an entirely chaotic free-for-all: package names are unique, only designated maintainers can upload new versions of some given package and version numbers are bound to a specific set of source files and content for all time.

The core value of Hackage-the-repository then, is to establish consensus about who maintains what package, what versions are available and the metadata associated with each version. If Alice has created a package called foolib, then Bob can't claim foolib for any of his own packages, he must instead choose another name. There is therefore agreement across the community about what foolib means. Agreement makes life much easier for users, tools and developers talking about these packages.

What doesn't need consensus is anything outside of package metadata and authorization: we may want multiple portals to Haskell code, or indeed have some portals dedicated to particular views (a particular subset of the full package set) of the central repository. For example, stackage.org today is one such portal, dedicated to LTS Haskell and Stackage Nightly, two popular views of consistent package sets maintained by FP Complete. We fully anticipate that others will over time contribute other views &mdash; general-purpose or niche (e.g. specialized for a particular web framework) &mdash; or indeed alternative portals &mdash; ranging from small, fast and stable to experimental and replete with social features aplenty. Think powerful new search functionality, querying reverse dependencies, pre-built package sets for Windows, OS X and Linux, package reviews, package voting ... you name it!

Finally, by carving out the central package repository into its own simple and reliable service, we limit the impact of bugs on both availability and reliably, and thus preserve on one of our most valuable assets: the code that we together as a community have written. Complex solutions invariably affect reliability. Keeping the core infrastructure small and making it easy to build on top is how we manage that.

The next section details one way to carve the central package repository, to illustrate my point. Alternative designs are possible of course - I merely wish to seek agreement that a modular architecture with at its core a set of very small and simple services as our community commons would be beneficial to the community.

Pairing down the central hub to its bare essence

Before we proceed, let's first introduce a little bit of terminology:

  • A persistent data structure is an data structure that is never destructively updated: when modified, all previous versions of the data structure are still available. Data.Map from the containers package is persistent in this sense, as are lists and most other data structures in Haskell.
  • A service is stateless if its response is a function of the state of other services and the content of the request. Stateless services are trivially scaled horizontally - limited only by the scalability of the services they depend on.
  • A persistent service is a service that maintains its only state as a persistent data structure. Most resources served by a persistent service are immutable. Persistent services share many of the same properties as stateless services: keeping complexity down and scaling them is easy because concurrent access and modification of a persistent data structure requires little to no coordination (think locks, critical sections, etc).

A central hub for all open source Haskell packages might look something like this:

  • A persistent read-only directory of metadata for all versions of all packages (i.e. the content of the .cabal file). Only the upload service may modify this directory, and even then, only in a persistent way.

  • A persistent read-only directory of the packages themselves, that is to say the content of the archives produced by cabal sdist.

  • An upload service, for uploading new revisions of the metadata directory. This service maintains no state of its own, therefore multiple upload services can be spawned if necessary.

  • An authentication service, granting access tokens to users for adding a new package or modifying the metadata for their own existing packages via the upload service(s).

The metadata and package directories together form a central repository of all open source Haskell packages. Just as is the case with Hackage today, anyone is allowed to upload any package they like via the upload service. We might call these directories collectively The Haskell Stash. End-user command-line tools, such as cabal-install, need only interact with the Stash to get the latest list of packages and versions. If the upload or authentication services go down, existing packages can still be downloaded without any issue.

Availability is a crucial property for such a core piece of infrastructure: users from around the world rely on it today to locate the dependencies necessary for building and deploying Haskell code. The strategy for maintaining high availability can be worked out independently for each service. A tried and tested approach is to avoid reinventing as much of the wheel as we can, reusing existing protocols and infrastructure where possible. I envision the following implementation:

  • Serve the metadata directory as a simple Git repository. A Git repository is persistent (objects are immutable and live forever), easy to add new content to, easy to backup, easy to mirror and easy to mine for insights on how packages changes over time. Advanced features such as package candidates fall out nearly for free. Rather than serving in its entirety a whole new static tarball of all package metadata (totalling close to 9MB of compressed data) as we do today, we can leverage the existing Git wire protocol to transfer new versions to end users much more efficiently. In short, a faster cabal update!.

    The point here is very much not to use Git as a favoured version control system (VCS), fine as it may be for that purpose, at the expense of any other such tool. Git is at its core an efficient persistent object store first and foremost, with a VCS layered on top. The idea is to not reinvent our own object store. It features a simple disk format that has remained incredibly stable over the years. Hosting all our metadata as a simple Git repository means we can leverage any number of existing Git hosting providers to serve our community content with high uptime guarantees.

  • Serve package source archives (produced by cabal sdist) via S3, a de facto standard API for file storage, supported by a large array of cloud providers. These archives can be large, but unlike package metadata, their content is fixed for all time. Uploading a new version of a package means uploading a new source archive with a different name. Serving our package content via a standard API means we can have that content hosted on a reliable cloud platform. In short, better uptime and higher chance that cabal install will not randomly fail.

Conclusion

The Haskell Stash is a repository in which to store our community's shared code assets in as simple, highly available and composable a manner as possible. Reduced to its bare essence, easily consumable by all manner of downstream services, most notably, Hackage itself, packdeps.haskellers.org, hdiff.luite.com, stackage.org, etc. It is by enabling people to extend core infrastructure in arbitrary directions that we can hope to build a thriving community that meets not just the needs of those that happened to seed it, but that furthermore embraces new uses, new needs, new people.

Provided community interest in this approach, the next steps would be:

  1. implement the Haskell Stash;
  2. implement support for the Haskell Stash in Hackage Server;
  3. in the interim, if needed, mirror Hackage content in the Haskell Stash.

In the next post in this series, we'll explore ways to apply the same principles of composability to our command-line tooling, in the interest of making our tools more hackable, more powerful and ship with fewer bugs.

Categories: Offsite Blogs