# See it.

I spend too much time in traffic.

So much time, that I start to see things. I see patterns.

You can get stuck in a slow lane because the others are going so fast you never manage to merge. So on average, how much time do you spend stuck in unescapable lanes? Does it make a difference in the cosmic scheme? (No, it doesn’t)

I decided to build a simulator and see how driving styles affect traffic.

Source is on github.

# Developer at Northwestern University (Full-time)

The NetLogo team at Northwestern University (near Chicago) is hiring a full-time developer.

This might interest you if you want to:

• work with researchers at a university
• make things for kids, teachers, and scientists
• write Scala and CoffeeScript
• hack on compilers and interpreters
• do functional programming
• use the Play framework
• write open source software
• do your work on GitHub (https://github.com/NetLogo)

The CCL is looking for a full-time developer to work on NetLogo, focusing on designing web based modeling applications in Javascript, and programming (Scala and/or Java) of the NetLogo desktop application, including GUI work.

This Software Developer position is based at Northwestern University’s Center for Connected Learning and Computer-Based Modeling (CCL), working in a small collaborative development team in a university research group that also includes professors, postdocs, graduate students, and undergraduates, supporting the needs of multiple research projects. A major focus would be on development of NetLogo, an open-source modeling environment for both education and scientific research. CCL grants also involve development work on HubNet and other associated tools for NetLogo, including research and educational NSF grants involving building NetLogo-based science curricula for schools.

NetLogo is a programming language and agent-based modeling environment. The NetLogo language is a dialect of Logo/Lisp specialized for building agent-based simulations of natural and social phenomena. NetLogo has many thousands of users ranging from grade school students to advanced researchers. A collaborative extension of NetLogo, called HubNet, enables groups of participants to run participatory simulation activities in classrooms and distributed participatory simulations in social science research.

Specific Responsibilities:

• Collaborates with the NetLogo development team in designing features for NetLogo, HubNet and web-based versions of these applications;
• Writes code independently, and in the context of a team of experienced software engineers and principal investigator;
• Creates, updates and documents existing models using NetLogo, HubNet and web-based applications;
• Creates new such models;
• Supports development of new devices to interact with HubNet;
• Interacts with commercial and academic partners to help determine design and functional requirements for NetLogo and HubNet;
• Interacts with user community including responding to bug reports, questions, and suggestions, and interacting with open-source contributors;
• Performs data collection, organization, and summarization for projects;
• Assists with coordination of team activities;
• Performs related duties as required or assigned.

Minimum Qualifications:

• A bachelor's degree in computer science or a closely related field or the equivalent combination of education, training and experience from which comparable skills and abilities may be acquired;
• Enthusiasm for writing clean, modular, well-tested code.

Desirable Qualifications:

• Experience with working effectively as part of a small software development team, including close collaboration, distributed version control, and automated testing;
• Experience with building web-based applications, both server-side and client-side components, particularly with html5 and JavaScript and/or CoffeeScript;
• Experience with at least one JVM language such as Java;
• Experience with Scala programming, or enthusiasm for learning it;
• Experience designing and working with GUIs, including the Swing toolkit;
• Experience with Haskell, Lisp, or other functional languages;
• Interest in and experience with programming language implementation, functional programming, and metaprogramming;
• Experience with GUI design; language design and compilers; Interest in and experience with computer-based modeling and simulation, especially agent-based simulation;
• Interest in and experience with distributed, multiplayer, networked systems like HubNet;
• Experience working on research projects in an academic environment;
• Experience with open-source software development and supporting the growth of an open-source community; experience with Unix system administration;
• Interest in education and an understanding of secondary school math and science content.

The Northwestern campus is in Evanston, Illinois on the Lake Michigan shore, adjacent to Chicago and easily reachable by public transportation.

Get information on how to apply for this position.

# network-conduit, async, and conduit-combinators

I got a request to write up some examples of using network-conduit for server and client apps. I'm going to try to cover a few of the examples requested. I'm also going to be demonstrating some usage of the new conduit-combinators library, as well as Simon Marlow's async package. If you want to test this out locally, start off by running:

cabal install conduit-combinators network-conduit async word8

network-conduit provides some functions for writing network servers and clients using conduit. There's support for TCP, UDP, and Unix sockets, and with network-conduit-tls there's support for SSL/TLS connections. We'll just use plain TCP in this post.

## Server 1: ALL CAPS

The first thing we'll do is write a server that listens on port 4000, and echos back to the client whatever it transmitted, but upper-cased. The code is incredibly short, let's just jump into it and then hit the explanations:

{-# LANGUAGE OverloadedStrings #-}
import           Conduit
import           Data.Conduit.Network
import           Data.Word8           (toUpper)

main :: IO ()
main = runTCPServer (serverSettings 4000 "*") $\appData -> appSource appData $$omapCE toUpper = appSink appData runTCPServer takes two parameters. The first is the server settings, which indicates how to listen for incoming connections. Our two parameters say to listen on port 4000 and that the server should answer on all network interfaces. The second parameter is an Application, which takes some AppData and runs some action. Importantly, our app data provides a Source to read data from the client, and a Sink to write data to the client. (There's also information available such as the SockAddr of the client.) The next line is a very trivial conduit pipeline: we take all data from the source, pump it through omapCE toUpper, and send it back to the client. omapCE is our first taste of conduit-combinators: omap means we're doing a monomorphic map (on a ByteString), and C means conduit, and E means "do it to each element in the container." Go ahead and run that code and telnet to port 4000. Everything you type in should COME BACK LOOKING ANGRY. ## Server 2: doubled characters Let's try another simple server (mostly because we need two servers to try out a later example). Again, let's just jump in. {-# LANGUAGE OverloadedStrings #-} import Conduit import Data.ByteString (pack) import Data.Conduit.Network main :: IO () main = runTCPServer (serverSettings 4001 "*") \appData -> appSource appData$$ concatMapCE (\w -> pack [w, w]) =$ appSink appData

The only changes here are (1) listen on port 4001 instead of 4000, and (2) instead of upper casing, we want to duplicate each incoming byte. Again, we're following the same naming scheme of CE to indicate "conduit, element-wise."

## Client: telnet

Now let's write a client. We want our client to perform the same job as our telnet client: connect to the server we just wrote, pipe all input from stdin to the server, and send all output to stdout:

{-# LANGUAGE OverloadedStrings #-}
import           Conduit
import           Control.Concurrent.Async (concurrently)
import           Data.Conduit.Network

main :: IO ()
main =
runTCPClient (clientSettings 4000 "localhost") $\server -> void$ concurrently
(stdinC $$appSink server) (appSource server$$ stdoutC)

Instead of runTCPServer and serverSettings, we're now using runTCPClient and clientSettings. But we're still dealing with the same Application type, and therefore the same ability to get access to our source and sink separately.

To get our standard input, we'll use stdinC, which is equivalent to sourceHandle stdin. We want to connect that to appSink server. Similarly, we need to connect appSource server to stdoutC. But the important bit is doing this in two separate threads. Remember that it's entirely possible that a server could generate output without corresponding input from our application.

To handle these semantics correctly, we pull in the async package, and in particular, the concurrently function. This function forks each child action into a separate thread, and blocks until both actions complete. If either thread throws an exception, then the other is terminated and the exception is rethrown. This provides exactly the behavior we need.

## Client: data pipeline

Now let's get a bit more complicated. We still want to get input from the user, but now send the output from the first server to a second server, and then send output from that server to standard output. This is actually not much worse than what we had previously:

{-# LANGUAGE OverloadedStrings #-}
import           Conduit
import           Control.Applicative      ((*>))
import           Control.Concurrent.Async (Concurrently (..))
import           Data.Conduit.Network

main :: IO ()
main =
runTCPClient (clientSettings 4000 "localhost") $\server1 -> runTCPClient (clientSettings 4001 "localhost")$ \server2 ->
runConcurrently $Concurrently (stdinC $$appSink server1) *> Concurrently (appSource server1$$ appSink server2) *> Concurrently (appSource server2 $$stdoutC) We now call runTCPClient twice, once for each server. And we need three threads instead of two, since there are three different connections going on. We could just make two calls to concurrently, but async provides a very convenient newtype wrapper- Concurrently- which lets us use its applicative instance to run all three of our threads at the same time. ## Server and client: proxy Now our final example. We'd like to run a proxy server. It will accept incoming connections, connect to a server, transmit all input from the client to the server, and all output from the server to the client. (Bonus points: try to implement this without looking at the example below.) {-# LANGUAGE OverloadedStrings #-} import Conduit import Control.Concurrent.Async (concurrently) import Control.Monad (void) import Data.Conduit.Network main :: IO () main = runTCPServer (serverSettings 4002 "*") \client -> runTCPClient (clientSettings 4000 "localhost") \server -> void concurrently (appSource server$$ appSink client) (appSource client $$appSink server) One important thing here is the order of the calls to runTCPServer and runTCPClient. The way we've set it up, we first start listening for incoming connections. Then, for each new incoming connection, we create a new connection to the server. In other words, there will be as many connections to the server as incoming client connections. This is the right way to implement a proxy, though there are possibly other use cases where you'd want to share server connections across multiple incoming clients. Other than that bit, everything else should be familiar. You should be able to connect to 4002 and talk to OUR ANGRY MAKING SERVER. ## Proxy with authentication All of the examples so far have involved a single operation on our streams of data: sending all of it to a server, upper casing every byte, etc. Let's look at something a bit more complicated: an authenticating proxy. In this case, the proxy will challenge the user for a username and password, the user will enter them, and if they are valid, the proxy session will begin. {-# LANGUAGE OverloadedStrings #-} import Conduit import Control.Concurrent.Async (concurrently) import Control.Monad (void) import Data.ByteString (ByteString) import Data.Conduit.Network import Data.Word8 (_cr) creds :: [(ByteString, ByteString)] creds = [ ("spaceballs", "12345") ] checkAuth :: Conduit ByteString IO ByteString checkAuth = do yield "Username: " username <- lineAsciiC takeCE 80 == filterCE (/= _cr) == foldC yield "Password: " password <- lineAsciiC takeCE 80 == filterCE (/= _cr) == foldC if ((username, password) elem creds) then do yield "Successfully authenticated.\n" else do yield "Invalid username/password.\n" error "Invalid authentication, please log somewhere..." main :: IO () main = runTCPServer (serverSettings 4003 "*") \client -> do (fromClient, ()) <- appSource client$$+ checkAuth =$ appSink client
runTCPClient (clientSettings 4000 "localhost") $\server -> void$ concurrently
(appSource server $$appSink client) (fromClient$$+- appSink server)

creds is just a simple collection of valid username/password combos. checkAuth is where most of our magic happens. First notice its type signature: it's a Conduit from ByteStrings (client input) to ByteStrings (output to client). We could alternatively pass around the client Sink explicitly, but this is more convenient. To say something to the client, we simply yield.

We want to get a line of input data from the user. Let's look at the code more closely:

username <- lineAsciiC $takeCE 80 =$= filterCE (/= _cr) =$= foldC There are a few things we're doing here: • The lineAsciiC combinator streams an entire line to the provided consumer. It ensures that, even if the consumer doesn't take all of the bytes, they will be flushed. • To prevent a memory exhaustion attack, we only keep up to 80 bytes of input. • lineAsciiC automatically strips out trailing line feeds, but does not strip out carriage returns. (Note: I might change that in a future release of conduit-combinators.) So we use filterCE to drop it. • foldC consumes the incoming stream of ByteStrings and folds them together into a single ByteString. We use the same logic for getting the password, and then test if the username/password is in creds. If it is, we give a successful message. Otherwise, we give the user an error message and throw an exception to close the connection. The important change to main is the usage of connect-and-resume (the $$+ operator): (fromClient, ()) <- appSource client$$+ checkAuth =$ appSink client

This allows us to consume some of the input from the client, and then resume the consumption later with a totally different consumer. This is highly convenient: instead of needing to put our authentication logic into the same consumer as the proxy, we can keep things nicely seperated. In order to resume consumption, we need to use the $$+- operator: (fromClient$$+- appSink server)

That's all I've got for the moment. If there are points that are unclear, please let me know. I'd like to make this blog post the official tutorial for network-conduit.

# Creative use of screen-message

I just learnt that the math and computer science student body is using screen-message to power an information screen in their room:

There are five instances of screen-message, configured to use non-standard colors and a fixed-width fonts, and controlled by the rather new remote control feature, where screen-messages repeatedly keeps reading text from standard input until a form feed character (ASCII 0x0C) comes, and displays that. The window manager ratpoison takes care of tiling the instances.

It looks quite a bit like a poor man’s version of dividuum’s great info-beamer. I was told that they also tried out info-beamer, but the Raspberry Pi was too slow and weak for that, while screen-message and ratpoison run happily on such small hardware.

# Blame, coercions, and threesomes, precisely

Blame, coercions, and threesomes, precisely
Jeremy Siek, Peter Thiemann, and Philip Wadler
Draft, March 2014
We systematically present four calculi for gradual typing: the blame calculus of Wadler and Findler (2009); a novel calculus that pinpoints blame precisely; the coercion calculus of Henglein (1994); and the threesome calculus of Siek and Wadler (2010). Threesomes are given a syntax that directly exposes their origin as coercions in normal form, a more transparent presentation than that found in Siek and Wadler (2010) or Garcia (2013).

# Algebraic and Analytic Programming

The professor began my undergrad number theory class by drawing a distinction between algebra and analysis, two major themes in mathematics. This distinction has been discussed elsewhere, and seems to be rather slippery (to mathematicians at least, because it evades precise definition).  My professor seemed to approach it from a synesthetic perspective — it’s about the feel of it.  Algebra is rigid, geometric (think polyhedra) , perfect.  The results are beautiful, compact, and eternal.  By contrast, analysis is messy and malleable.  Theorems have lots of assumptions which aren’t always satisfied, but analysts use them anyway and hope (and check later) that the assumptions really do hold up.  Perelman’s famous proof of Poincare’s conjecture, as I understand, is essentially an example of going back and checking analytic assumptions.  Analysis often makes precise and works with the notion of “good enough” — two things don’t have to be equal, they only need to converge toward each other with a sufficiently small error term.

I have been thinking about this distinction in the realm of programming.  As a Haskell programmer, most of my focus is in an algebraic-feeling programming.  I like to perfect my modules, making them beautiful and eternal, built up from definitions that are compact and each obviously correct.  I take care with my modules when I first write them, and then rarely touch them again (except to update them with dependency patches that the community helpfully provides).  This is in harmony with the current practice of denotative programming, which strives to give mathematical meaning to programs and thus make them easy to reason about. This meaning has, so far, always been of an algebraic nature.

What a jolt I felt when I began work at Google.  The programming that happens here feels quite different — much more like the analytic feeling (I presume — I mostly studied algebraic areas of math in school, so I have less experience).  Here the codebase and its dependencies are constantly in motion, gaining requirements, changing direction.  ”Good enough” is good enough; we don’t need beautiful, eternal results.  It’s messy, it’s malleable. We use automated tests to keep things within appropriate error bounds — proofs and obviously-correct code would be intractable.  We don’t need perfect abstraction boundaries — we can go dig into a dependency and change its assumptions to fit our needs.

Much of the ideological disagreement within the Haskell community and between nearby communities happens across this line.  Unit tests are not good enough for algebraists; proofs are crazy to an analyst.  QuickCheck strikes a nice balance; it’s fuzzy unit tests for the algebraist.  It gives compact, simple, meaningful specifications for the fuzzy business of testing.  I wonder, can we find a dual middle-ground?  I have never seen an analytic proof of software correctness.  Can we say with mathematical certainty that our software is good enough, and what would such a proof look like?

# Proof by contradiction

Intuitionistic logic is deeply misunderstood by people who have not studied it closely; such people often seem to think that the intuitionists were just a bunch of lunatics who rejected the law of the excluded middle for no reason. One often hears that intuitionistic logic rejects proof by contradiction. This is only half true. It arises from a typically classical misunderstanding of intuitionistic logic.

Intuitionists are perfectly happy to accept a reductio ad absurdum proof of the following form:

$$(P\to\bot)\to \lnot P$$

Here means an absurdity or a contradiction; means that assuming leads to absurdity, and means that if assuming leads to absurdity, then you can conclude that is false. This is a classic proof by contradiction, and it is intuitionistically valid. In fact, in many formulations of intuitionistic logic, is defined to mean .

What is rejected by intuitionistic logic is the similar-seeming claim that:

$$(\lnot P\to\bot)\to P$$

This says that if assuming leads to absurdity, you can conclude that is true. This is not intuitionistically valid.

This is where people become puzzled if they only know classical logic. “But those are the same thing!” they cry. “You just have to replace with in the first one, and you get the second.”

Not quite. If you replace with in the first one, you do not get the second one; you get:

$$(\lnot P\to\bot)\to \lnot\lnot P$$

People familiar with classical logic are so used to shuffling the signs around and treating the same as that they often don't notice when they are doing it. But in intuitionistic logic, and are not the same. is weaker than , in the sense that from one can always conclude , but not always vice versa. Intuitionistic logic is happy to agree that if leads to absurdity, then . But it does not agree that this is sufficient to conclude .

As is often the case, it may be helpful to try to understand intuitionistic logic as talking about provability instead of truth. In classical logic, P means that P is true and \lnot P means that P is false. If P is not false it is true, so \lnot\lnot P and P mean the same thing. But in intuitionistic logic P means that P is provable, and \lnot P means that P is not provable. \lnot\lnot P means that it is impossible to prove that P is not provable.

If P is provable, it is certainly impossible to prove that P is not provable. So P implies \lnot\lnot P. But just because it is impossible to prove that there is no proof of P does not mean that P itself is provable, so \lnot\lnot P does not imply P.

Similarly,

$$(P\to\bot)\to \lnot P$$

means that if a proof of would lead to absurdity, then we may conclude that there cannot be a proof of . This is quite valid. But

$$(\lnot P\to\bot)\to P$$

means that if assuming that a proof of is impossible leads to absurdity, there must be a proof of . But this itself isn't a proof of , nor is it enough to prove ; it only shows that there is no proof that proofs of are impossible.

# cabal sandbox tips

In case you missed it, starting from version 1.18 cabal-install has awesome sandboxing capabilities. Here I share a couple of tricks that will make your sandboxing experience even better.

## Location-independent sandboxes

By default, cabal uses sandbox only in the directory where cabal.sandbox.config is present. This is inconvenient when sharing a sandbox among multiple projects, and in general makes it somewhat fragile.

With cabal 1.19 (i.e. cabal HEAD as of now) you can set the CABAL_SANDBOX_CONFIG environment variable to the path to your cabal.sandbox.config, and the corresponding sandbox will be used regardless of your current directory.

I’ve defined convenience functions for myself such as

tasty() {
export CABAL_SANDBOX_CONFIG=$HOME/prog/tasty/sandbox/cabal.sandbox.config sandbox_name=tasty } for every sandbox I commonly use. Notice how I also set the sandbox_name variable to the human-readable name of the sandbox. It can be displayed in the prompt as follows: setopt prompt_subst # force prompt re-evaluation PROMPT='${sandbox_name+[sandbox: $sandbox_name] }%~ %% ' (sandbox name in the prompt idea is due to /u/cameleon) ## Sandbox-aware ghc Sandboxes only affect cabal, but not ghc or ghci when those are invoked directly. At some point in the future we’ll be able to write % cabal exec ghc ... For now I’ve defined the following sandbox-aware wrappers for ghc and ghci: <script src="https://gist.github.com/feuerbach/9365969.js"></script> Clone the repo somewhere % git clone https://gist.github.com/9365969.git ghc_sandbox and include in your .bashrc or .zshrc . ~/path/to/ghc_sandbox/ghc_sandbox.sh (Why am I wrapping ghci instead of using cabal repl? cabal repl has some side-effects, like re-installing packages, that are not always desirable. And ghci is much faster to start, too.) ## March 03, 2014 ### Well-Typed.Com # GHC 7.8.1 RC2 Today, GHC 7.8.1 RC2 has been released. We've closed approximately 45 issues people filed against RC1. Thanks to everyone who has helped out! There are actually quite a few nice improvements since then, and some stuff we'd like to announce. ### iOS cross compiler binaries This release features iOS cross compiler binaries, courtesy of Luke Iannini. You can download either ghc-7.8.0.20140228-arm-apple-ios or ghc-7.8.0.20140228-i386-apple-ios for the iOS ARM compiler or iOS Simulator, respectively. To properly use the binary distribution, be sure to carefully read the README! Hopefully this process can be made less tedious in the future. ### LZMA support for binary distributions In my experience, lots of people use the binary distributions of GHC for their provided platform (to set up test environments, or because the version for their OS is out of date), and a smaller download for users always helps. We're now offering LZMA (.tar.xz) compressed binary distributions. On average, these are half the size of their bzip2 counterparts – in some cases even more. The iOS ARM build, for example, is 125M for LZMA vs 267M for bzip2 – a ratio of greater than 50%. One question now is: with these savings, should we keep supporting .tar.bzip2 distributions? GHC bindists are rather large – xz offers a lot of savings, and is available for every major platform, although it's not typically standard like bzip. But perhaps it's not too much of a burden. Please let us know what you think! (In the future, this will also save considerable space with nightly build infrastructure as well!) ### New PPC64 machine GHC HQ now has a shiny, modern 64-bit POWER7 machine available, courtesy of Gustavo Luiz Duarte. Gustavo is a Fedora PPC64 maintainer, and approached me earlier this year and said he could give us access to a build machine. And now we've got a really nice one! And 7.8.1 works well on it, including dynamic GHCi and shared libraries. This box is running Fedora 20, has 8 hardware threads split across two cores (one per socket) in a NUMA configuration, and a nice amount of RAM. Many thanks to Gustavo for letting us use this – and also to OSUOSL, who is hosting it in their data center for us! Hopefully we'll be able to keep supporting this platform (we get a surprising amount of PPC/PPC64 related tickets!) ### i386/amd64 Ubuntu PPA Earlier this year, Herbert Valerio Riedel took the time to set up Ubuntu PPAs for Travis-CI, making it easy to test your Haskell packages using multiple GHC versions – from GHC 6.12 to 7.8 and HEAD. This PPA repository now contains 7.8.1 RC2 binaries, available for download for both i386 and amd64 on Ubuntu 12.04 Precise. You should immediately be able to take advantage of these builds in your .travis.yml to test your packages. Furthermore, the binaries are separated from other versions and can coexist with existing packages. To get started, add the PPA and install the 7.8.1 build: $ sudo add-apt-repository -y ppa:hvr/ghc
$sudo apt-get update$ sudo apt-get install ghc-7.8.1
$export PATH=/opt/ghc/7.8.1/bin:$PATH
ghc --version The Glorious Glasgow Haskell Compilation System, version 7.8.0.20140228  This PPA is also integrated into Herbert's multi-ghc-travis project that I mentioned earlier. Just follow the instructions in the README.md, and be sure to enable: GHCVER=7.8.1  inside your .travis.yml. You'll then automatically get build reports with RC2, and any future updates we push to the PPA (including the final version of 7.8.1). For example, lens now builds with GHC 7.8.1! Hopefully we can provide builds for all supported Ubuntu configurations in the future – not just Precise. ### deb.haskell.org for your Debian needs Thanks to Joachim Breitner, our resident Debian Developer, we now have GHC HEAD builds available as Debian packages! Currently there aren't 7.8.1 builds yet I'm afraid – but there will be a final version of 7.8.1 available upon release. In the mean time, feel free to use these repositories to test out the latest GHC if you're daring, and report issues to us! And this leads me to... ### Rackspace support Earlier this year, I contacted Rackspace about one of their developer programs. Rackspace is a huge supporter of open source and has some great initiatives to help open source projects. I asked if they could help GHC – we wanted build machines. Rackspace was extremely kind, and with the help of Jesse Noller, they've provided GHC with a few thousand USD per month in services! This was extremely nice of them, and really blew me away. Rackspace is what powers http://deb.haskell.org – and not only that. GHC HQ now has machines available solely for testing/build purposes, including many new Windows and Linux instances. In addition to that, we're using them for haskell.org too – including a FreeBSD backup server (to be revamped soon), and the creation of our new Nagios monitoring infrastructure at monitor.haskell.org. Right now, we've still got budget available to run more services. This venture is a bit of a joint one between GHC HQ and the current haskell.org administrators, as we're using it for both of our needs at the moment. ### What's next We're hoping RC2 will be the final RC, and 7.8.1 proper will follow soon. In the mean time, please download the RC and file bugs if anything goes wrong! ## March 02, 2014 ### Roman Cheplyaka # tasty-0.8 and other news ## tasty-0.8 I’m glad to announce the 0.8 release of tasty, a modern Haskell testing framework. Among the important user-visible changes are: • New running modes --hide-successes and --quiet • Short flags for some existing options (-p for --pattern, -j for --num-threads) • Timeout support • Possibility to pass options via environment variables • Fix of a resources-related bug For details, see the CHANGELOG and README. ## Social tasty now has a mailing list and an IRC channel #tasty at FreeNode. The IRC channel is logged at ircbrowse.net (thanks to Chris Done). ## Volunteers I’d like to thank people who kindly responded to my requests for help with tasty-related packages: ## Dependencies I recently started to pay more attention to (transitive) dependencies of my packages. More transitive dependencies (esp. those that I do not control) means greater probability that something will break, not to mention the compile times. As Vincent Hanquez put it, <script async="async" charset="utf-8" src="http://platform.twitter.com/widgets.js"></script> For comparison, here are dependency graphs for tasty-0.7 and tasty-0.8, produced by John Millikin’s new cabal-graphdeps tool: The gains were achieved by: 1. Dropping the dependency on either. First I just copied the code over to tasty, but then realized that using exceptions in that case was an even better solution. 2. Refusing to depend on reducers. Instead, I just copied the desired pieces. 3. Using unbounded-delays for timeouts instead of data-timeout that I considered initially. This one actually shows the danger of fat dependencies — one of data-timeout’s dependencies fails to build with GHC 7.4 due to an alleged compiler bug affecting some piece of code that is completely irrelevant for my purposes. ### Disciple/DDC # Civilized error messages I spent the weekend fixing bugs in preparation for the upcoming 0.4 release. I've finished all the necessary compiler hacking, but still need to update the cabal files, tutorial, and wiki before releasing it proper. I've made sure to fix all the bugs that would result in a poor user experience for people that just want to spend an afternoon kicking the tyres. Even though DDC still has lots of missing features (garbage collection, compilation for higher order functions etc), the stuff that is implemented is reasonably well baked. If one tries to do something unsupported it should at least give a civilized error message. For example: Trying to use an anonymous type function (higher order functions are not supported yet) module Test with letrec id [a : Data] (x : a) : a = x foo (_ : Unit) : Unit = do id (/\a. x : a). x) ()Fragment violation when converting Tetra module to Salt module. Cannot convert expression. Cannot convert type abstraction in this context. The program must be lambda-lifted before conversion. with: /\(a : Data). \(x : a). x Trying to use higher kinded type arguments (which need an 'Any' region to implement safely, in general) module Test data List (a : Data) where Nil : a -> List a Cons : a -> List a -> List awith letrec foo [a : Data ~> Data] [b : Data] (x : b) : b = x bar (_ : Unit) : Nat# = foo [List] [Nat#] 5# Cannot convert expression. Unsupported type argument to function or constructor. In particular, we don't yet handle higher kinded type arguments. See [Note: Salt conversion for higher kinded type arguments] in the implementation of the Tetra to Salt conversion. with: [List] Trying to partially apply a primitive operator: module Test with letrec thing (_ : Unit) : Nat# -> Nat# = add# [Nat#] 5#Fragment violation when converting Tetra module to Salt module. Cannot convert expression. Partial application of primitive operators is not supported. with: add# [Nat#] 5# In contrast, the old ddc-alpha compiler (which I wrote for my PhD work), would signal its displeasure with partially applied primops by producing a program that segfaulted at runtime. We turn our backs on the bad old days. ### Nested Data Types Pleasingly, the new type inferencer does seem to work with some non-standard programs -- even though these don't compile all the way to object code yet. Here is a Core Tetra program using nested data types: module Test data Tuple2 (a b : Data) where T2 : a -> b -> Tuple2 a b data Nest (a : Data) where NilN : Nest a ConsN : a -> Nest (Tuple2 a a) -> Nest awith letrec thing (_ : Unit) = ConsN 7# (ConsN (T2 1# 2#) (ConsN (T2 (T2 6# 7#) (T2 7# 4#)) NilN)) This example is based on one from the Bird and Meertens 1998 paper. Note that the second argument of the ConsN constructor takes a Nest where the element type is more complex than the original parameter. The type inference algorithm in the alpha compiler would have diverged on this program. ### Higher Rank Types I've also tried out some simple examples with higher ranked types, here is one: module Test with letrec thing1 (blerk : ([a : Data]. a -> a) -> Nat#) : Nat# = blerk (/\a. \(x : a). x) thing2 (u : Unit) = thing1 (\(f : [a : Data]. a -> a). f 5#) thing1 has a rank-3 type because it is a function, that takes a function, that takes a function which is polymorphic. There is a quantifier that appears at depth 3 contravariantly. Writing the type of thing1 in full makes this easier to see:  thing1 :: ((([a : Data]. a -> a) -> Nat#) -> Nat# Again, I can't compile this example to object code yet because code generation for higher order functions isn't finished. However, type inference is a separate concern, and I don't know of any remaining problems in this part. ## March 01, 2014 ### Mark Jason Dominus # Placeholder texts This week there has been an article floating around about “What happens when placeholder text doesn't get replaced. This reminds me of the time I made this mistake myself. In 1996 I was programming a web site for a large company which sold cosmetics and skin care products in hundreds of department stores and malls around the country. The technology to actually buy the stuff online wasn't really mature yet, and the web was new enough that the company was worried that selling online would anger the retail channels. They wanted an a web page where you would put in your location and it would tell you where the nearby stores were. The application was simple; it accepted a city and state, looked them up in an on-disk hash table, and then returned a status code to the page generator. The status code was for internal use only. For example, if you didn't fill in the form completely, the program would return the status code MISSING, which would trigger the templating engine to build a page with a suitable complaint message. If the form was filled out correctly, but there was no match in the database, the program would return a status code that the front end translated to a suitably apologetic message. The status code I selected for this was BACKWATER. Which was all very jolly, until one day there was a program bug and some user in Podunk, Iowa submitted the form and got back a page with BACKWATER in giant letters. Anyone could have seen that coming; I have no excuse. ### language-puppet # Refactoring: from an IO-based monad stack to a pure Program (part 2) In the previous post, I explained how I refactored the language-puppet catalog compiler so that the main monad was a pure Program (from the operational package) instead of an ErrorT Doc (RSST InterpreterReader InterpreterWriter InterpreterState IO). I then wrote an interpreter that would turn it back to this monad stack, so that it could be used with runErrorT and runRSST. It might have been obvious to many readers that this was a pretty strange move, but I didn’t figure it out until operational’s author told me (thanks !). Here is what my interpreter signature was : <figure class="code">  1 2 3  interpretIO :: InterpreterReader -> InterpreterMonad a -> ErrorT Doc (RSST InterpreterReader InterpreterWriter InterpreterState IO) a  </figure> And here is what it should have been from the beginning : <figure class="code">  1 2 3 4  interpretIO :: InterpreterReader -> InterpreterState -> InterpreterMonad a -> IO (Either Doc a, InterpreterState, InterpreterWriter)  </figure> The Program should have been converted to the base monad (IO in this case) in the first place, instead going through the intermediate monad stack transformer step. The interpreter is now a lot easier to read. ### Johan Tibell # Google Summer of Code Projects Every year I put together a list of Google Summer of Code projects I'd like see students work on. Here's my list for this year. As normal the focus is on existing infrastructure. I believe, and I think our experience in the past bears out, that such projects are more successful. ### Improved Hackage login The Hackage login/user system could use several improvements. From a security perspective, we need to switch to a current best practice implementation of password storage, such as bcrypt, scrypt, or PBKDF2. MD5, which is what HTTP Digest Auth uses, has known attacks. From a usability perspective, we need to move to a cookie-based login system. While using HTTP auth is convenient from an implementation perspective, it doesn't work well from a usability perspective (that's why sites that otherwise try to follow the REST approach don't use HTTP auth.) A cookie-based approach allows us to, among other things, • display the current login status of the user, • allow users to conveniently access a user preference page, • allow users to log out, and • adapt the UI to the current user. An example of the latter would be to only show a link to the maintainer section for packages you maintain or show additional actions for the site admins. HTTP auth introduces an extra page transition if you want to move from a list to items to edit that list of items (e.g. you can edit uploaders on /packages/uploaders/, you need to click on the link that takes you to /packages/uploaders/edit.) This is because HTTP auth does authentication on a per HTTP request basis. ### Other Hackage usability improvements There are several other Hackage usability improvements I'd like to see. The homepage is currently a write-up about the new Hackage server. While that made sense when the new Hackage server was brand new, a more useful homepage would include a list of recently updates packages, most popular packages, packages you maintain, and a link to "getting started" material and other documentation. Looking at other languages' package repo homepages for inspiration wouldn't be a bad start. The search result page should include download counts and a more easily scannable result list. The current list is hard to read because the package descriptions don't line up. For example, compare the search result page for "xml" for Hackage and Ruby Gems. ### Faster Cabal/GHC parallel builds Mikhail Glushenkov and others have done a great job making our compiles faster. Cabal already builds packages in paralell and with GHC 7.8 it will build modules in parallel as well. There are still more opportunities for parallelism. Cabal doesn't build individual components or different versions of the same component (e.g. vanilla and profiling) in parallel. Building all the test suites in parallel would save time if you have many test suites and building vanilla and profiling versions at the same time would allow users to turn on profiling by default (in ~/.cabal/config) without paying (much of) a compile time penalty. There's already some work underway here so there might not be enough Cabal work to last a student through the summer. The remaining time could be spent increasing the amount of parallism offered by ghc -j. Today the parallel speed-up offered by ghc -j is quite modest and I believe we ought to be able to increase it. If you exclude link times, if we had N independent modules of the same size we should get close to a N times parallel speed-up, which I don't think we do today. While real packages don't have this much available parallelism, improvements in the embarrasingly parallel case should help the average case. ### Cabal file pretty-printer If we had a Cabal file pretty printer, in the spirit of go-fmt for Go, we could more easily apply automatic rewrites to Cabal files. Having a formatter that applies a standard (i.e. normalizing) format to all files would make rewrites tools much simpler, as they wouldn't have to worry about preserving user formatting. Some tools that would benefit: • cabal freeze, which will be included in Cabal-1.20 • cabal init • A cabal version number bumper/PVP helper I don't think such a pretty-printer should be terribly clever. Since Cabal files don't support pattern matching (like Haskell), aligning things doesn't really help readability much. Something simple like a 2 (or 4) space ident and starting each list of items on a new line below the item "header" ought to be enough. Here's an example: name: Cabal version: 1.19.2 copyright: 2003-2006, Isaac Jones 2005-2011, Duncan Coutts license: BSD3 license-file: LICENSE author: Isaac Jones <ijones@syntaxpolice.org> Duncan Coutts <duncan@community.haskell.org> maintainer: cabal-devel@haskell.org homepage: http://www.haskell.org/cabal/ bug-reports: https://github.com/haskell/cabal/issues synopsis: A framework for packaging Haskell software description: The Haskell Common Architecture for Building Applications and Libraries: a framework defining a common interface for authors to more easily build their Haskell applications in a portable way. . The Haskell Cabal is part of a larger infrastructure for distributing, organizing, and cataloging Haskell libraries and tools. category: Distribution cabal-version: >=1.10 build-type: Custom extra-source-files: README tests/README changelog source-repository head type: git location: https://github.com/haskell/cabal/ subdir: Cabal library build-depends: base >= 4 && < 5, deepseq >= 1.3 && < 1.4, filepath >= 1 && < 1.4, directory >= 1 && < 1.3, process >= 1.0.1.1 && < 1.3, time >= 1.1 && < 1.5, containers >= 0.1 && < 0.6, array >= 0.1 && < 0.6, pretty >= 1 && < 1.2, bytestring >= 0.9 if !os(windows) build-depends: unix >= 2.0 && < 2.8 ghc-options: -Wall -fno-ignore-asserts -fwarn-tabs ## February 28, 2014 ### Douglas M. Auclair (geophf) # 'Arrow' is spelt 'fizz-buzz' A little literate Haskell program: > module Fizzbuzz where So, fizz-buzz through a functional lens > import Control.Arrow Our predicate is for some number, x, we print 'fizz' if it's modulo 3, or we print 'buzz' if it's modulo 5. N.b.: these predicates are not exclusive. So our fizz-buzz predicate follows ('pred'icate 'f'izz-'b'uzz) > predfb :: String -> Int -> Int -> Either String Int > predfb str modulo x | x mod modulo == 0 = Left str > | otherwise = Right x so: > fizz = predfb "fizz" 3 > buzz = predfb "buzz" 5 ... that's really all there is so we just split the input number into the two predicates and then remerge the results following this rule: Left str1 (+) Left str2 = str1 ++ str2 Left str (+) _ = str _ (+) Left str = str Right x (+) _ = show x which transliterates quite nicely (it's nice programming requirement specification as implementation-code when your programming language is declarative) > fbprinter :: (Either String Int, Either String Int) -> String > fbprinter (Left x, Left y) = x ++ y > fbprinter (Left x, _) = x > fbprinter (_, Left y) = y > fbprinter (Right num, _) = show num Now the fizz-buzz game: count from 1 to 100 replacing '3's with fizz and '5's with 'buzz' ... off you go: > fizzbuzz = [1..100] >>= return . (fizz &&& buzz >>> fbprinter) There it is. fizzbuzz in, lessee, 8 lines of implementation code. Any questions? Nope? Q.E.D. Afterthought: Well, there is one improvement. If we look at the Either type as a cartesian product type (which it is), then the print rule looks rather redundant to the monoidal append operation, for, after all m0 (+) (anything) = (anything) (order of arguments superfluous); and, m+ (+) m+ = defined by the semigroupoid-implementation so, the monoidal addition of lists is [] (+) lst = lst; and, (... even if lst == []) lst1 (+) lst2 = lst1 ++ lst2 Can't we just convert our Either String Int type to be a monoid and have the special base case of 'show num' for the (Right num (+) Right num) case? Hm. Yes. I leave this now as an exercise for the reader... ... which is another way of saying that I see a simple solution of mzero == Right num and mplus == Left str in my head, but how to implement that in Haskell is currently puzzling me. Intrepid readers, show me the light! ... at any rate, 'running' fizzbuzz gets you all fizzy-buzzy and you can feel good that you've used a little predicate logic, functional programming, programming with arrows, no less, and you didn't have any redundant boolean logic that you see in other implementation for fizz-buzz: Either took care guarding our conditioned results. Sweet! p.s. The payoff! The payoff! How could I forget the payoff for those of you who don't have Haskell running natively on your 'iron'? (Now, why you don't have haskell running on your platform, I don't want to even think about. Not having haskell on hand to feed yourself your functional-programming (daily/hourly/secondly) fix? geophf shudders) *Fizzbuzz> :l Fizzbuzz.lhs [1 of 1] Compiling Fizzbuzz ( Fizzbuzz.lhs, interpreted ) Ok, modules loaded: Fizzbuzz. *Fizzbuzz> fizzbuzz ["1","2","fizz","4","buzz","fizz","7","8","fizz","buzz","11","fizz","13","14","fizzbuzz","16","17","fizz","19","buzz","fizz","22","23","fizz","buzz","26","fizz","28","29","fizzbuzz","31","32","fizz","34","buzz","fizz","37","38","fizz","buzz","41","fizz","43","44","fizzbuzz","46","47","fizz","49","buzz","fizz","52","53","fizz","buzz","56","fizz","58","59","fizzbuzz","61","62","fizz","64","buzz","fizz","67","68","fizz","buzz","71","fizz","73","74","fizzbuzz","76","77","fizz","79","buzz","fizz","82","83","fizz","buzz","86","fizz","88","89","fizzbuzz","91","92","fizz","94","buzz","fizz","97","98","fizz","buzz"] There ya go! (this program contains its own solution ... meta-quine, anyone?) ## February 27, 2014 ### wren ng thornton # I am so done with this past week. Saturday night I had a fainting spell. Sunday my eyes were burning, I was feverish, weak, and had the beginnings of a migraine. Monday was completely lost in the blaze of a migraine. Tuesday I was starting to feel better— and then, nope; threw up that night. Wednesday I awoke with what felt like a raging sinus infection; spent the whole day in a haze of sudafed and ibuprofen, and went through literally an entire box of tissues. Starting to feel a little better this morning, so I figure this is the end. It was a nice life. Y'might want to bar your doors today, just in case it's locusts. comments ### Yesod Web Framework # Module name conflicts on Hackage For some upcoming improvements to FP Haskell Center, I recently added a new feature to Stackage: the ability to detect module name conflicts. This is where two different packages both export a module of the same name. You can see the full module name conflict list for my most recent build. The file format is fairly dumb: one line lists all of the packages using a common module name, and the following line contains all of the module names shared. (JSON, YAML, or CSV would have been better file formats for this, but one of the goals of the Stackage codebase is to avoid extra package dependencies wherever possible.) Most of these conflicts don't seem problematic at all. The fact that base, haskell98, haskell2010, and base-compat share a lot of the same module names, for example, should be expected, and users really do need to choose just one of those packages to depend on. Some other cases, on the other hand, might cause issues. For example, both hashmap and unordered-containers export the Data.HashSet module. This can negatively affect users of GHCi who have both packages installed and try to import Data.HashSet. Also, if for some reason a cabal package depended on both, you'd need to use package imports to disambiguate. There can also be an issue of confusion: if I see Data.HashSet at the top of a module, it would be nice to know which package it comes from without having to check a cabal file or running ghc-pkg. I'm mostly writing this blog post as I think it's the first time we've had any kind of collection of this information, and I don't think we've had a community discussion about conflicting module names. I don't know if the problem is significant enough to even warrant further analysis, or how have thoughts on how to proceed if we do want to try and disambiguate module names. Here are some of the conflicting module names, and the packages using them: • System.FilePath.Glob • Glob • filemanip • Test.Framework • HTF • test-framework • Control.Monad.Trans.List • List • transformers • Control.Monad.CatchIO • MonadCatchIO-mtl • MonadCatchIO-transformers • Test.QuickCheck.Instances • checkers • quickcheck-instances • Crypto.Random • crypto-api • crypto-random • Data.HashSet • hashmap • unordered-containers • Language.Haskell.Lexer • haskell-lexer • haskell-src • Test.Hspec • hspec • nanospec • Data.String.UTF8 • hxt-unicode • utf8-string ### Mark Jason Dominus # 2banner, which tells you when someone else is looking at the same web page I was able to release a pretty nice piece of software today, courtesy of my employer, ZipRecruiter. If you have a family of web pages, and whenever you are looking at one you want to know when someone else is looking at the same page, you can use my package. The package is called 2banner, because it pops up a banner on a page whenever two people are looking at it. With permission from ZipRecruiter, I have put it on github, and you can download and use it for free. A typical use case would be a customer service organization. Say your users create requests for help, and the the customer service reps have to answer the requests. There is a web page with a list of all the unserviced requests, and each one has a link to a page with details about what is requested and how to contact the person who made the request. But it might sometimes happes that Fred and Mary independently decide to service the same request, which is at best a waste of effort, and at worst confusing for the customer who gets email from both Fred and Mary and doesn't know how to respond. With 2banner, when Mary arrives at the customer's page, she sees a banner in the corner that says Fred is already looking at this page!, and at the same time a banner pops up in Fred's browser that says Mary has started looking at this page! Then Mary knows that Fred is already on the case, and she can take over a different one, or Fred and Mary can communicate and decide which of them will deal with this particular request. You can similarly trick out the menu page itself, to hide the menu items that someone is already looking out. I wanted to use someone else's package for this, but I was not able to find one, so I wrote one myself. It was not as hard as I had expected. The system comprises three components: • The back-end database for recording who started looking at which pages and when. I assumed a SQL database and wrote a component that uses Perl's DBIx::Class module to access it, but it would be pretty easy throw this away and use something else instead. • An API server that can propagate notifications like “user X is now looking at page Y” and “user X is no longer looking at page Y” into the database, and which can answer the question “who else is looking at page Y right now?”. I used Perl's Catalyst framework for this, because our web app already runs under it. It would not be too hard to throw this away and use something else instead. You could even write a standalone server using HTTP::Server, and borrow most of the existing code, and probably have it working in under an hour. • A JavaScript thingy that lives in the web page, sends the appropriate notifications to the API server, and pops up the banner when necessary. I used jQuery for this. Probably there is something else you could use instead, but I have no idea what it is, because I know next to nothing about front-end web programming. I was happy to have the chance to learn a little about jQuery for this project. Often a project seems easy but the more I think about it the harder it seems. This project was the opposite. I thought it sounded hard, and I didn't want to do it. It had been an outstanding request of the CS people for some time, but I guess everyone else thought it sounded hard too, because nobody did anything about it. But the longer I let it percolate around in my head, the simpler it seemed. As I considered it, one difficulty after another evaporated. Other than the jQuery stuff, which I had never touched before, the hardest part was deciding what to do about the API server. I could easily have written a standalone, special-purpose API server, but I felt like it was the wrong thing, and anyway, I didn't want to administer one. But eventually I remembered that our main web site is driven by Catalyst, which is itself a system for replying to HTTP requests, which already has access to our database, and which already knows which user is making each request. So it was natural to say that the API was to send HTTP requests to certain URLs on our web site, and easy-peasy to add a couple of handlers to the existing Catalyst application to handle the API requests, query the database, and send the right replies. I don't know why it took me so long to think of doing the API server with Catalyst. If it had been someone else's suggestion I would probably feel dumb fror not having thought of it myself, because in hindsight it is so obvious. Happily, I did think of it, because it is clearly the right solution for us. It was not too hard to debug. The three components are largely independent of one another. The draft version of the API server responded to GET requests, which are easier to generate from the browser than the POST requests that it should be getting. Since the responses are in JSON, it was easy to see if the API server was replying correctly. I had to invent techniques for debugging the jQuery stuff. I didn't know the right way to get diagnostic messages out of jQuery, so I put a big text area on the web page, and had the jQuery routines write diagnostic messages into it. I don't know if that's what other people do, but I thought it worked pretty well. JavaScript is not my ideal language, but I program in Perl all day, so I am not about to complain. Programming the front end in JavaScript and watching stuff happen on the page is fun! I like writing programs that make things happen. The package is in ZipRecruiter's GitHub repository, and is available under a very lenient free license. Check it out. (By the way, I really like working for ZipRecruiter, and we are hiring Perl and Python developers. Please send me email if you want to ask what it is like to work for them.) ## February 26, 2014 ### language-puppet # Refactoring: from an IO-based monad stack to a pure Program (part 1) ## UPDATE (2014/03/01) It turns out that there was a better way to do this, please see this new post. ## Rationale I am currently experimenting with the operational package. This post provides a rough outline on how I moved from an IO based monad stack to an isomorphic pure representation of the computation. I am unfortunately not well endowed on the theoretical side, so this will be a very practical post. It might contain some glaring mistakes, as I just spend a few hours acquainting myself with the concepts and migrating everything, and didn’t test it extensively. I marked the places where I am unsure on how to do something with a number, such as (0). Here is the type of the main monad, before and after the change : <figure class="code">  1 2 3 4  -- Before type InterpreterMonad = ErrorT Doc (RSST InterpreterReader InterpreterWriter InterpreterState IO) -- After type InterpreterMonad = ProgramT InterpreterInstr (State InterpreterState)  </figure> I first tried a simple Program InterpreterInstr for the main monad, but I could not write the MonadState instance, as there was a conflicting instance (1). This is the reason why the State monad is there, at the base of the transformer stack. The goal is to build a representation of the catalog compilation process, in a pure monad, and then transform it into another representation that will actually be executed. In order to do so, all the “effects” need to be encoded as a single type (designated as instr in the operational haddocks). In this case, this is the InterpreterInstr type, detailed here. You might observe that commands of type m a -> m b become constructors of type m a -> instr b, and not instr a -> instr b (which makes sense if you think about what you are doing, but was not immediately obvious to me when I started writing the types). ## Implementing the Program monad First of all, all the effects given by the original transformer stacks have their own instructions : ErrorT has the ErrorThrow and ErrorCatch instructions, and a similar treatment has been realized on the MonadWriter part of the original RSST transformer (it’s like RWST, except faster and not leaky). The MonadState doesn’t need special instructions, as InterpreterMonad is already an instance of MonadState. The MonadWriter has been dropped, in favor of more specific instructions (the original reader structure can be directly observed in the new instruction set, along with the exposed PuppetDBAPI). Finally, some additional utility functions have been thrown in, as they rely on IO. With all of this in place, it becomes trivial to write the following instances : <figure class="code">  1 2 3 4 5 6 7 8  instance MonadError Doc InterpreterMonad where throwError = singleton . ErrorThrow catchError a c = singleton (ErrorCatch a c) instance MonadWriter InterpreterWriter InterpreterMonad where tell = singleton . WriterTell pass = singleton . WriterPass listen = singleton . WriterListen  </figure> Now the refactoring becomes mechanical, and surprisingly non invasive. As can be seen in the patch, it’s mostly about replacing every use of the view and liftIO with the corresponding “singleton” command. I have seen that people write short functions for commonly used instructions, such as : <figure class="code">  1  pdbGetResources = singleton . PDBGetResources  </figure> I didn’t go for this, as most functions are used at most a couple times. ## Running the computation The interpreter is right here, and is pretty painful to read. Its type is however pretty straightforward : given the “Reader” data and a ProgramT, it will create an equivalent (or not) computation represented by another monad. It is exactly(2) as writing in a DSL, and running it through an interpreter. I was surprised that I had to write the explicit type signatures for the functions that are in the where section of the interpretIO function, but other than that this was a straightforward exercise. As a reaction to a recent popular reddit thread, the “Overview” given in operational’s documentation was invaluable to get started quickly. ## Conclusion I have seen this kind of design mentioned at several places, as a common way to keep things pure and easy to reason about. I however thought it was better to think about it earlier in the design process, as changing the base monad of all computations would require a significant rewrite. The first pleasant surprise was that it only took me a few hours to go from “reading the haddocks” to “refactoring done”. The second, in some sense, even more pleasant surprise was that there doesn’t seem to be any performance penalty whatsoever. ### Functional Jobs # NixOS/Haskell DevOps Engineer at Zalora (Full-time) Full-Time Remote Position in a Distributed Team ZALORA is an online fashion retailer with millions of customers and 1,000+ employees throughout South East Asia (headquartered in Singapore). We're building a new globally-distributed, remote DevOps team. We have built a small, tightly-knit team of global talent following the functional programming philosophy. You'll be reporting directly to an engineer with experience managing DevOps for an Alexa top-150 worldwide website. There is substantial legacy code from a period of fast growth, so there will be some pain in moving on from the previous tech stack. We're disassembling the monolithic LAMP architecture (PHP, MySQL, Memcache, Solr) and building a service-oriented architecture in its place. Most of the servers are currently managed via Puppet, but we've already begin moving them over to NixOS/NixOps. Our Development Philosophy • Automate everything. • Use purely functional principles. • Build properly, however long it takes (no deadlines). We don't say this lightly: we have the backing from management on this after they saw the results of building quickly with hacks. Benefits • No hours, no dress code, no physical presence required—just worry about keeping things running smoothly. • Enjoy the freedom to solve problems in the way you see fit. All tech choices are your call if you take responsibility. • Release your code as Open Source and get recognized for any tools you build. Selection We will hire almost purely based on your code quality and ability to deploy it. Send us: • Your Github profile or code samples OR • The code for part 1 of the selection task below and your SSH key. If we like it, you'll receive instructions for part 2 (deploying your code). We promise feedback within 48 hours—previous hires were made as shortly as 30 hours after first contact. Selection Task - Part 1 Write a FastCGI program (preferably in Haskell) that provides a restful API to manage the cgroups of a server. It should support the following: • list available cgroups • list the tasks (PIDs) for a given cgroup • place a process into a cgroup You can assume that the server is running a Linux 3.4 kernel with the cgroup root mounted via sysfs. Include a default.nix to build your program as a nix package. Bonus points for including a NixOS module.nix. Get information on how to apply for this position. ### Silk # Bump it up We just released a new version of your Cabal package tool bumper. Bumper lets you transitively bump sets of packages that you are developing so you don’t have to manually edit version constraints. Silk consists of a lot of packages, modifying all the dependencies by hand turned into quite the chore so we needed a tool to automate the process of releasing new versions. The typical work flow is to make changes to a set of packages, run bumper, run bumper again with the same arguments along with --dry-run piped to a script that uploads to our internal Hackage server, and finally push the changes to github (which notifies our build server). See the readme in the repository for more information on how bumper works, or install it from Hackage. Silk is hiring! Check out jobs.silk.co to see if that might be something for you or someone you know ### Alson Kemp # Simple Decoders for Kids My wife created simple symbol-letter decoders for my son. He thought they were a lot of fun and wanted to share them with friends, so I productized them. Screenshot here: Simple, straightforward way to build fun little puzzles for kids. Play with it here. Besides changing the phrase, you can add additional confounding codes or remove codes to force kids to guess at the phrase. Then click the Print button and you’ll have a nice printout with the control panel hidden. I’m building a 2-D version for the codes, too, so that will be along later this week. ## February 25, 2014 ### Wolfgang Jeltsch # Hyperreal numbers on Estonian TV On 13 February, I talked about hyperreal numbers in the Theory Lunch. I have not yet managed to write a blog article about this, but my notes on the whiteboard have already been featured on Estonian TV. The background is that the head of the Software Department of the Institute of Cybernetics, Ahto Kalja, recently received the Order of the White Star, 4th class from the President of Estonia. On this account, Estonian TV conducted an interview with him, during which they recorded also parts of my notes that were still present on the whiteboard in our coffee room. You can watch the video online. The relevant part, which is about e-government, is from 18:14 to 21:18. I enjoyed it very much hearing Ahto Kalja’s colleague Arvo Ott talking about electronic tax returns and seeing some formula about limits immediately afterwards. At 20:38, there is also some Haskell-like pseudocode. Tagged: Ahto Kalja, Arvo Ott, e-government, Eesti Televisioon, Haskell, hyperreal number, Order of the White Star, Theory Lunch, TTÜ Küberneetika Instituut ### Jon Kristensen # Pontarius XMPP 1.0 Alpha 11 Released Another update to Pontarius XMPP, a client XMPP library for Haskell, has now been released, courtesy of Philonous. In addition to a bunch of general improvements and bugfixes, this new version supports plugins (the possibility to transform incoming and outgoing stanzas) and lenses (allowing users to access XMPP-related types more conveniently and composably). Since one of the bugs fixed is quite major (Pontarius XMPP didn’t check the JID of IQResult stanzas), we recommend that all Pontarius XMPP users upgrade. The Pontarius project will use this new plugin feature to build end-to-end security on top of Pontarius XMPP. Stay tuned for further updates! ### Kevin Reid (kpreid) # How to really fix a bug If you're feeling virtuous: 1. Figure out what's going on. 2. Figure out why what's going on wasn't immediately obvious. 3. Make it so that such failures are caught and reported obviously. 4. Make it so that the rest of the system recovers from such failures. 5. Write a test for the bug, and a couple more while you're at it. 6. Write the actual fix. (I ought to do more actual concrete blogging, like what I've been doing lately. This crossed my mind as a light and easy piece — I actually followed part of this procedure yesterday after pushing a version (of what, I'll get to later) that was rather broken.) ### Vincent Hanquez # unix memory On unix system, we get access to syscalls that maps files or devices into memory. The main syscall is mmap, but there’s also some others syscalls in the same family to handle mapped memories like mlock, munlock, mprotect, madvise, msync. Some limited mmap access is available through the mmap or bytestring-mmap packages, but both provide a high level access to those API. To the rescue, I’ve released unix-memory. This provide low level access to all those syscalls. In some place, the API presented is slightly better than the raw API. This package is supposed to be ephemeral; The goal is to fold this package to the venerable unix package when this becomes less experimental, more stable and is known to work on different unixoid platforms. If and when this happens, then this package will just provide compatibility for old versions and eventually be deprecated. Manipulating memory is unsafe in general, so don’t expect any safety from this package, by design. Also if you don’t know what you’re doing, don’t use those APIs; It’s difficult to get right. But it also allow interesting patterns when you cooperate with the operating system to efficiently map files, and devices as virtual memory. A simple example opening the “/dev/zero” device first memory page, and reading 4096 bytes from it:  1 2 3 4 5 6 7 8 9 10 11  import System.Posix.IO import System.Posix.Memory import Control.Monad import Control.Exception (bracket) import Foreign.C.Types import Foreign.Storable bracket (openFd "/dev/zero" ReadWrite Nothing defaultFileFlags) closeFd \fd -> bracket (memoryMap Nothing 4096 [MemoryProtectionRead] MemoryMapPrivate (Just fd) 0) (\mem -> memoryUnmap mem 4096) (\mem -> mapM (peekElemOff mem) [0..4095]) ### Jasper Van der Jeugt # Profiteur: a visualiser for Haskell GHC .prof files # Introduction GHC comes with some amazing tools to do profiling of Haskell programs. In .prof files, you can see exactly in which function most time is spent and where most allocation is done. However, at Erudify, we have a huge amount of Haskell code – and at this point .prof files can become very unwieldy, and the text representation is harder to grok. This is why I coded profiteur, a simple HTML-based visualiser for GHC .prof files. # Installation Installation is easy:  cabal install profiteur # Usage Let us grab a sample program from the HaskellWiki. The code of this sample program can be found in the appendix. I saved this file as binary-trees.hs. First, we compile it with profiling enabled:  ghc --make -auto-all -prof -rtsopts binary-trees.hs [1 of 1] Compiling Main ( binary-trees.hs, binary-trees.o ) Linking binary-trees ... We run it in profiling mode:  ./binary-trees 10 +RTS -p -RTS stretch tree of depth 11 check: -1 2048 trees of depth 4 check: -2048 512 trees of depth 6 check: -512 128 trees of depth 8 check: -128 32 trees of depth 10 check: -32 long lived tree of depth 10 check: -1 This generates the file binary-trees.prof. We can pass that to profiteur:  profiteur binary-trees.prof Wrote binary-trees.prof.html Open the resulting file in your favorite (modern) browser and you are good to go! Here is the resulting HTML file so you can have a look without installing profiteur. As always, patches and pull requests are welcome on GitHub. # Appendix Code used: {-# LANGUAGE BangPatterns #-} {-# OPTIONS_GHC -funbox-strict-fields #-} -- -- The Great Computer Language Shootout -- http://shootout.alioth.debian.org/ -- -- Contributed by Don Stewart -- import System.Environment import Data.Bits import Text.Printf data Tree = Nil | Node !Int Tree Tree minN = 4 io s !n !t = printf "%s of depth %d\t check: %d\n" s n t main = do n <- getArgs >>= readIO . head let maxN = max (minN + 2) n stretchN = maxN + 1 -- stretch memory tree let c = check (make 0 stretchN) io "stretch tree" stretchN c -- allocate a long lived tree let long = make 0 maxN -- allocate, walk, and deallocate many bottom-up binary trees let vs = depth minN maxN mapM_ (\((m,d,i)) -> io (show m ++ "\t trees") d i) vs -- confirm the the long-lived binary tree still exists io "long lived tree" maxN (check long) -- generate many trees depth :: Int -> Int -> [(Int,Int,Int)] depth !d !m | d <= m = (2*n,d,sumT d n 0) : depth (d+2) m | otherwise = [] where !n = 1 shiftL (m - d + minN) -- allocate and check lots of trees sumT :: Int -> Int -> Int -> Int sumT !d 0 t = t sumT d i t = sumT d (i-1) (t + a + b) where a = check (make i d) b = check (make (-i) d) -- traverse the tree, counting up the nodes check :: Tree -> Int check Nil = 0 check (Node i l r) = i + check l - check r -- build a tree make :: Int -> Int -> Tree make i 0 = Node i Nil Nil make i d = Node i (make (i2-1) d2) (make i2 d2) where i2 = 2*i; d2 = d-1 ## February 24, 2014 ### Neil Mitchell # The Build System Shootout Summary: I am collecting examples to show how build systems relate in terms of power. Contributions welcome. A while back I tried to classify the relative power of various build systems. I did that by reasoned argument, which, unsurprisingly, meant I didn't get it right. In an attempt to properly clarify the relative power of various build systems I've started the Build System Shootout. Compared to the Computer Language Shootout, this Shootout attempts to answer whether a build system is capable of expressing a particular dependency structure, but does not measure performance. The following build systems have at least seven entries: • Make (GNU version), the de facto standard build system. • Ninja, as used by Chrome. • Shake, my Haskell build system. • tup, contributed by Andrew Wagner. • fabricate, with help from the fabricate mailing list. The project currently consists of twelves examples, each of which has pseudo-code for the equivalent untracked straight-line shell script and a set of test cases that are used to decide if a fragment correctly expresses the build example. I welcome contributions, including: • Examples in different build systems (e.g. Scons, Ant, Waf). • New implementations for existing build systems (e.g. parallelism for fabricate). • New test cases (provided they show something interesting) (e.g. dependencies by hash not modification time). • Corrections of my egregious errors. ### Functional Jobs # functional software developer at OpinionLab (Full-time) functional software developer OpinionLab is seeking a Software Developer with strong agile skills to join our Chicago, IL based Product Development team in the West Loop. As a member of our Product Development team, you will play a critical role in the architecture, design, development, and deployment of OpinionLab’s web-based applications and services. You will be part of a high-visibility agile development team empowered to deliver high-quality, innovative, and market leading voice-of-customer (VoC) data acquisition and feedback intelligence solutions. If you thrive in a collaborative, fast-paced, get-it-done environment and want to be a part of one of Chicago’s most innovative companies, we want to speak with you! Key Responsibilities include: • Development of scalable data collection, storage, processing & distribution platforms & services. • Architecture and design of a mission critical SaaS platform and associated APIs. • Usage of and contribution to open-source technologies and framework. • Collaboration with all members of the technical staff in the delivery of best-in-class technology solutions. • Proficiency in Unix/Linux environments. • Work with UX experts in bringing concepts to reality. • Bridge the gap between design and engineering. • Participate in planning, review, and retrospective meetings (à la Scrum). Desired Skills & Experience: • BDD/TDD, Pair Programming, Continuous Integration, and other agile craftsmanship practices • Desire to learn Clojure (if you haven’t already) • Experience with both functional and object-oriented design and development within an agile environment • Polyglot programmer with mastery of one or more of the following languages: Lisp (Clojure, Common Lisp, Scheme), Haskell, Scala, Python, Ruby, JavaScript • Experience delivering real-time, distributed systems in large scale production environments • Knowledge of one or more of: AWS, Lucene/Solr/Elasticsearch, Storm, Chef • Familiarity with Java, Clojure, Ruby and/or Python ecosystems Database experience, including but not limited to RDBMSs like PostgreSQL, Oracle, etc. • Experience with design and development of externally facing RESTful APIs • Familiarity with message-based (RabbitMQ, 0MQ or similar), asynchronous, and event-driven architectures • Ability to thrive in informal and relaxed environments • Fluency with DVCSs like Git/GitHub and/or Bitbucket • Ruby on Rails development (version 3+) • Experience with JS and CSS compiling, linting, minifying, cache busting • Experience with Cross-Browser, responsive Design meeting Accessibility Standards (508, WCAG) • Knowledge of one or more modern CSS frameworks (e.g., Bootstrap, Foundation, Bourbon, Neat) • Knowledge of one or more modern JavaScript frameworks (Backbone, Ember, Angular, Knockout, MVC) Compensation: • Commensurate with experience. • Generous benefits include medical, dental, life and disability insurances, paid holidays, vacation and sick days, 401K with employer match, FSA plan Get information on how to apply for this position. # Platform Engineer at Signal Vine LLC (Full-time) About Signal Vine Signal Vine, LLC is an exciting early-stage company with customers and revenue which is growing quickly and looking for our next technical hire. We are building an incredible company that helps solve social issues with technology. We recognize that the key to our growth and success is hiring great people. Our ideal candidate for this position is someone who has the enthusiasm for creative problem solving, but maintains the dedication and focus to achieve desired results. We have built a communication platform for educational organizations to reach today's youth. Our platform combines text messaging with data analytics to deliver a highly personalized and interactive experience for students. Our platform helps educational organizations achieve their goals by allowing them to engage their students in a way that is natural and easy for both parties. About the Job Our stack is Haskell, Ruby, Git, Ubuntu and we are primarily looking for a Haskeller with a deep understanding of computer language development to help build the next generation of the Signal Vine platform. Your main focus will be building our custom DSL, you will also be expected to work on all aspects of the Signal Vine tech platform, including tasks such as maintaining our Ruby on Rails application as necessary, responding to customer support requests, and preparing demo content. Further, we expect you to maintain a holistic view of how technology can be used to further the Signal Vine vision. You... • Have built release quality software with Haskell • Are able to create custom DSLs • Can do self directed work • Work well with others • Are intellectually honest • Can express technical concepts to a non-technical audience • Are trust worthy and conscientious It’d be cool if you... • Have experience with Ruby, Scala, AngularJs • Are interested in dev-ops and build automation • Have used web frameworks to build one or more applications (i.e. RoR, NancyFx, Flask, Play, etc....) • Can use CSS effectively • Know Unix well • Have public examples of projects you’ve completed • Have published technically relevant articles, blog posts or books • Maintain a social media presence that represents your technical interests and ability We will... • Pay a competitive salary including equity and health insurance • Buy you a shiny new MacBook Pro • Respect your work schedule and habits by focusing on results • Offer you a chance to go on an exciting ride as the company grows Get information on how to apply for this position. ### Christopher Done # Attempto Controlled English Attempto Controlled English is a formally defined unambiguous language which is a subset of the English language. It’s pretty sweet. I’ve known about it for some time, but I never fiddled with it because the standard implementation setup is rather elaborate. I wanted a nice, simple package in Haskell which would define a parser and a printer only, much like haskell-src-exts does. That way I can use ACE to parse some simple English for all sorts of purposes1, with a simple familiar API that I can peruse on Hackage. Partly it’s also a good learning experience. So I went through the paper The Syntax of Attempto Controlled English to see whether it was comprehensive enough to write a parsec parser out of. It was! I first wrote a tokenizer in with Attoparsec and wrote some tests. From those tokens I produced a set of combinators for Parsec, then I wrote a parser. While writing the parser I produced a set of test-cases for each grammar production. Finally, I wrote a pretty printer, and wrote some tests to check that print . parse . print . parse = id. Newbies to Haskell parsing might find it an interesting use-case because it tokenizes with Attoparsec (from Text) and then parses its own token type (Token) with Parsec. A common difficulty is to avoid parsing from String in Parsec, which most tutorials use as their demonstration. The Hackage package is here. I find the documentation interesting to browse. I tried to include helpful examples for the production rules. You shouldn’t have to know syntax theory to use this library. Here is an ACE sample. We can parse the sentence “a <noun> <intrans-verb>” like this: λ> parsed specification "a <noun> <intrans-verb>." Right (Specification (SentenceCoord (SentenceCoord_1 (SentenceCoord_2 (SentenceCoord_3 (TopicalizedSentenceComposite (CompositeSentence (Sentence (NPCoordUnmarked (UnmarkedNPCoord (NP (SpecifyDeterminer A) (N' Nothing (N "<noun>") Nothing Nothing Nothing)) Nothing)) (VPCoordVP (VP (V' Nothing (ComplVIV (IntransitiveV "<intrans-verb>")) [])))))) Nothing) Nothing) Nothing) Nothing) Nothing) Anything to do with vocabulary is written as <foo>. The parser actually takes a record of parsers so that you can provide your own parsers for each type of word. These words are not of interest to the grammar, and your particular domain might support different types of words. If we pretty print the parsed phrase, we get: λ> fmap pretty (parsed specification "a <noun> <intrans-verb>.") Right "a <noun> <intrans-verb>." I.e. we get back what we put in. I also wrote a HTML printer. A more complicated sentence demonstrates the output: for each <noun> <var> if a <noun> that <trans-verb> some <noun> and <proper-name>’s <noun> <trans-verb> 2 <noun> then some <noun> <intrans-verb> and some <noun> <distrans-verb> a <intrans-adj> <noun> <proper-name>’s <noun> <adverb>. Can be printed with fmap (renderHtml . toMarkup) . parsed specification and the output is: for each <noun> <var> if a <noun> that <trans-verb> some <noun> and <proper-name>'s <noun> <trans-verb> 2 <noun> then some <noun> <intrans-verb> and some <noun> <distrans-verb> a <intrans-adj> <noun> <proper-name>'s <noun> <adverb>. The colors and parenthesizing embellishments are just to demonstrate what can be done. I’m not sure this output would actually be readable in reality. This is a good start. I’m going to leave it for now and come back to it later. The next steps are: (1) write more tests, (2) add feature restrictions and related type information in the AST, (3) add a couple sample vocabularies, (4) implement the interrogative (useful for query programs) and imperative moods (useful for writing instructions, e.g. text-based games). 1. Specifically, I want to use this to experiment with translating it to logic-language databases and queries, and from that produce interactive tutorials, and perhaps experiment with a MUD-like game that utilizes it. ## February 23, 2014 ### Marcos Pividori # Apple Push Notification Service Apple Push Notification service is a robust and highly efficient service for propagating information to devices iOS. Each device establishes an accredited and encrypted IP connection with the service and receives notifications over this persistent connection. To send notifications, the provider connects to APNS through a permanent and secure connection. When there is new information to be sent, the provider prepares and sends a notification through the APNS channel, which pushes the notification to the target device. (https://developer.apple.com/library/ios/documentation/NetworkingInternet/Conceptual/RemoteNotificationsPG/Art/remote_notif_simple_2x.png) A notification is a short message consisting of two main parts of data: the device token and the payload: * The device token identifies the device and application on the client side. * The payload is a JSON-defined property list that specifies how the user of an application on a device is to be alerted. Each provider requires a unique provider certificate and private cryptographic key for validation of its connection to the APN. This certificate, provisioned by Apple, must identify the particular topic published by the provider; the topic is the bundle ID of the client application. For more information: Apple Developers - Apple Push Notification Service ## February 22, 2014 ### Paul Johnson # A Review of the joint CNN and BBC production: "The War On Terror" The War on Terror is the latest epic in the long-running World War franchise. The previous serial in the franchise, World War II, was slammed by the critics for its cardboard-cutout villains, unrealistic hero and poor plot-lines, although it actually achieved decent ratings. The first season of Terror started with a retcon. At the end of World War II it looked like the Soviet Union had been set up as the Evil Empire for yet another World War, but the writers seem to have realised that replaying the same plot a third time wasn't going to wow the audience. So at the start of Terror we get a load of back story exposition in which the Soviet Union has collapsed for no readily apparent reason, leaving America running a benevolent economic hegemony over the allies from the previous series and also its former enemies, Germany and Japan. There was also mention of a very one-sided Gulf War, apparently to emphasize that America's economic power was still matched by its military, even though it didn't seem to have anyone left to fight. Then in the second episode a bunch of religious fanatics from nowhere flew hijacked airliners into important buildings. While the premise may have been a bit thin the episode managed a level of grandeur and pathos that the franchise hadn't achieved since the Pearl Harbour episode, with the special effects being used to build drama rather than just having huge fireballs. But after this promising start the rest of the season became increasingly implausible, with a buffoonish president launching two pointless wars on countries whose governments turned out to have almost nothing to do with the attack he was trying to revenge. The weak plot and unsympathetic characters make the last few episodes of the season hard to watch. However in the second season the series grew a beard. The writers replaced the old president with a good looking black guy who clearly wanted to do the right things, finally giving the audience someone to root for, and the focus switched sharply from armed conflict to corrupt politics. Instead of huge set-piece battles featuring ever-more improbable weaponry, the drama now focuses on the political situation within America itself. The battles and weapons are still there of course, but no longer driving the plot. Instead the president is shown as a tragic figure as he tries to stop wars, free prisoners and sort out his country's economic problems, but every time some combination of corporate executive, greedy banker and/or General Ripper will block his reforms, sometimes with an obstructive bureaucrat thrown in for comic relief. He has his hands on the levers of power, but in contrast with his predecessor in World War II those levers don't seem to be connected to anything any more. Although each episode stands on its own as a story, several plot arcs are becoming clearer as season 2 draws to a close. Events seem to presage the Fall of the Republic, a plot similar to the Star Wars prequel trilogy, but much better done. Whereas Lucas' Old Republic was destroyed by a single corrupt ruler who wanted to become The Emperor, the American Republic in Terror is being destroyed by the very things that made it strong in the previous series: its industrial capacity, financial power and military strength. This is most clearly seen in the episode Drone Strike, where the president was asked to authorise an attack by a remote controlled aircraft against a suspected terrorist convoy on the other side of the world. America is one of the few countries with the technology and money to field these unmanned warplanes, and they have become an important part of American power. Then we saw the president's face as he was told that the supposed convoy had actually been a wedding party. At the end of the episode he was reduced to defending his actions at a press conference because the people who had got him into this mess were too powerful to sack. At the same time there are stories of individual determination and hope set in contrast against the darker backdrop. The recent episode Watching the Watchers showed a soldier and a bureaucrat in different parts of the secret spy agency (or agencies; America seems to have several) independently deciding to rebel against the system they are a part of, by releasing embarrassing secrets to the public. At the same time the episode revealed a hidden factor in previous plot lines. Fans are now reviewing old episodes, even back into the first season, looking for the throwaway lines and improbable coincidences which only now make sense. The vision of the writers of Terror is now becoming clear; the real war on terror is not the one being fought with guns and robot aircraft, it is the one being fought in the shadows against a loose and ever-shifting coalition of rich, powerful individuals who have discovered that a terrorised population is willing to give them even more money and power, and therefore want to keep it that way. The president's initiatives aren't being blocked by some grand secret conspiracy, its just that all of these people know how to work together if they want stop something happening. But this actually makes them more dangerous; in a conventional conspiracy story the hero just has to find the conspiracy and unmask them, but that isn't going to happen in Terror. In one chilling scene a club of bankers get together for a party to laugh at the rest of the country for continuing to pay them huge amounts after they have wrecked the economy that they were supposed to be running. A journalist sneaks in and tells the story, but it doesn't make any difference because throwing a party is not a conspiracy. So Terror goes into its third season in much better shape than it was at the end of the first. The writers have escaped from the constraints of set-piece battles between huge armies, and found instead a solid theme of individual heroism in a believable world of ambiguous morality and complex politics. It all makes for powerful drama and compelling viewing. ### Philip Wadler # An obsession with targets and impacts is killing off the blue-sky thinking that helped Higgs to a Nobel prize From the Guardian. "Higgs would not find his boson in today's 'publish or perish' research culture". Also from the Guardian. "Peter Higgs: I wouldn't be productive enough for today's academic system". ### Ken T Takusagawa # [rzzllapd] Nonrandomness of the first random sample The first random sample after a call to mkStdGen seed is extremely poorly distributed: module Main where { import System.Random (StdGen, mkStdGen, randomR); import Data.Array.IArray (Array, accumArray, assocs); rollDice :: StdGen -> (Int, StdGen); rollDice = randomR (1,6); get_first :: Int -> Int; get_first seed = fst rollDice mkStdGen seed; histogram :: [Int] -> Array Int Int; histogram l = accumArray (+) 0 (1,6) do { x <- l; return (x,1) }; main :: IO (); main = mapM_ print assocs histogram map get_first [0..53667]; }  Output, with GHC 7.4.2: (1,0) (2,0) (3,0) (4,0) (5,0) (6,53668)  All seeds from 0 to 53667 roll an initial 6. The second sample seems not bad (maybe even too good!), suggesting a fix of discarding the first sample: better_mkStdGen seed = snd rollDice mkStdGen seed; (1,8947) (2,8942) (3,8943) (4,8948) (5,8944) (6,8944)  Here is a comparable C++ program which demonstrates that glibc does a good job for the first sample, which is not too surprising given the extensive set up in the internal procedure __srandom_r(). #include <cstdlib> #include <cstdio> int rollDice(){ return rand() / (RAND_MAX + 1.0) * 6 + 1; } int get_first(unsigned int seed){ srand(seed); return rollDice(); } int main(){ //We only need 1 through 6, quick hack around 0-indexing. int histogram[7] = {0}; for (unsigned int seed=0; seed<=53667; ++seed) { histogram[get_first(seed)]++; } for (int i=1;i<=6;++i){ printf("%d %d\n", i, histogram[i]); } }  Output with GCC 4.7.2: 1 8984 2 9112 3 8929 4 8885 5 8788 6 8970  My previous commentary on GHC Random. ## February 21, 2014 ### Douglas M. Auclair (geophf) # Quotes-map-reduce-close-quotes "So, geophf," I was asked during a recent interview for a software quality-assurance tester job, "have you heard of the product map-reduce?" "Well," sez I, "no, but I'm familiar with the concept from functional programming." That was a good enough answer for me. The test manager had heard of functional programming and (from me) category theory. I was talking with Ph.D.s who were test managers. A refreshing conversation, actually. "Yes," he said, "but what is all this stuff good for?" I gave him a "you've got to be kidding me" look. What is category theory good for? Coming on the heels of have I heard of map-reduce? Like where did the concept of map-reduce come from? So, here's what it's good for. ### The Joke An infinite number of mathematicians walk into a bar. The first math dude sez, "Bartender, I'll have half-a-beer." The next one sez, "I'll have half what he's having." Then next: "I'll have half of hers." And the next one goes to speak. And they want to get in this specification, because that's how mathematicians roll, but the bartender holds up his hands. "Ladies and gentlemen," he says, "know your limits, please!" And pours out one beer which the infinite number of mathematicians enjoy. The proof in the pudding let nat = [1..] let halflings = map (\x → 1 / 2 ** x) nat let onebeer = sum halflings onebeer Now, that may take some time to return (geophf cackles evilly at his phrasing of 'some time'), but we've just used map-reduce. How? map we used directly above in halflings, as you see, and reduce (a.k.a. the fold function) is embedded in the definition of sum: let sum :: Num a ↠ [a] → a = foldl (+) 0 So, if we look at the the above we just used map-reduce to solve the beering-mathematicians problem (as opposed to solving the dining philosophers problem, because, anyway, those philosophers really should go on a diet. Just sayin'). Piece of cake, right? Well, not really. Our solution, to use a technical term, sucks. Let's look at it. What does our set of equations reduce to? The reduce to this one formula: let onebeer = sum (map (\x → 1 / 2 ** x) [1..]) What's wrong with this? Well, for any n, where n is the length of the set of natural numbers, we have a least a double-linear complexity to solve this problem. But let's look at the sequence we create by unwinding the problem. First we have [1,2,3,4, ...] Then we have [1/2, 1/4, 1/8, 1/16, ...] Then we have [1/2 (+ 0), 1/4 + 1/2, 1/8 + 3/4, 1/16 + 7/8, ...] Huh. What's interesting about this pattern? Story time Once upon a time, there was a bad little boy in maths class, named Gauss, and he was held after school. The teacher told him he could go home after he summed the first 100 'numbers' (positive integers, I believe the teacher meant). Gauss left for home after writing the solution down in less than one second. The teacher was furious, believing that Gauss had cheated. He didn't. He just noticed a pattern. 1 = 1 1 + 2 = 3 1 + 2 + 3 = 6 1 + 2 + 3 + 4 = 10 sum [1..n] = ... what? Well, what does it equal? When n = 1, sum [1..1] = n when n = 2, sum [1..2] = n + 1 when n = 3, sum [1..3] = n * 2 when n = 4, sum [1..4] = ... hm, well, it equals ... what? It equals n (n + 1) / 2, doesn't it. n = 100, sum [1..100] = 100 * 101 / 2 = 5,050 ... and Gauss was done. He went home, serving the shortest detention ever, and put egg on his prof's face, too. Good times. Good times. Well, what about this problem? We can map and sum all we want, but can't we do what Gauss did and reduce the double-linear (at least) problem complexity down to some constant on the number n? Yes, we can. The pattern is this, after we've done our reduction to the simplest forms: [1/2, 3/4, 7/8, 15/16, ... blah-blah-blah, boring-boring-boring] Who needs map-reduce when we just simply return limn (1 - 1 / 2n for any n even as n approaches infinity? Who, indeed. The take-away? Yes, I could have used map and reduce and exponentiation and all that to get to the answer, but sometimes we just have to take a step back from trying to solve a problem and just observe what we're solving. "Hey," algorist exclaims, "I'm just solving to get this simple fraction! I don't have to map-sum anything!" It's amazing what meta-problem-solving saves us as we go about solving problems, isn't it? Epilogue Oh, map is reduce, did you know that? Specifically, for every function f, there is a reduce function that is isomorphic to map f. What is it? # A little κ-calculus conversation So, "wan plas wan is doo" in the κ-calculus. Because why? Because if you can prove addition in some calculus, you can prove anything. Well, prove any primitively-recursive thing in that calculus, and that's good enough for most anything (except Ackermann and some others), which is close enough to a latte at Caribou café for me. SO! without further ado: 1 + 1 = 2, κ-style. First of all, some basics. What is the κ-calculus? κ-calc: application is composition: f: A B is κ x . f : (C x A) B and the lifting ('identity') function C : 1 C is lift : A (C x A) Then, for addition we need the category Nat and the following arrows: 0 : 1 → Nat; and, (so, 0 ~> 0) succ : Nat → Nat (so, succ o succ o 0 ~> "2") but we also need the iterator function for natural numbers: (a) it(a, f) o 0 ~> a; and (b) it(a, f) o succ o n ~> f o it(a, f) o n from this we can declare the function add in the κ-calculus: add : Nat x Nat → Nat ≡ (κ x . it(x, succ)) Note how we don't care what the second (snd) argument of the tuple is, we just iterate succ over it, so with add defined above we can now prove 1 + 1 = 2 add o (succ o 0, succ o 0) = (κ x . it(x, succ)) o lift (succ o 0) o succ o 0 (lift distribution) = it(x, succ)[succ o 0] o succ o 0 (composition) = it(x [succ o 0/x], succ [succ o 0/x]) o succ o 0 (substitution) = it(succ o 0, succ) o succ o 0 (substitution) = succ o (it(succ o 0, succ) o 0) (iteration (b)) = succ o (succ o 0) = 2 (iteration (a)) Q.E.D. Piece of cake, right? Using categories (for types), we reduce 200 pages of the Principia Mathematica down to a couple of axioms, a couple of types and one function (it), then a few lines of proof and we're done. Awesomesauce! But then, my daughters became curious about what the Papa was doing, so this conversation ensued with my 10-year-old. "But, Papa," Li'l Iz asked with big-big eyes, "what does snd have to do with 2?" So, I explained. A tuple is of the form: (a, b) So for example we have: (3, 4) So the tupling functions are: fst (3, 4) ~> 3 snd (3, 4) ~> 4 And therefore for the tuple (1,1) fst (1, 1) ~> 1 snd (1, 1) ~> 1 So, to prove 1 + 1 = 2 we thence have: add o (1, 1) Therefore: fst (1, 1) o add o snd (1, 1) = 2 and that's why snd (1, 1) has everything to do with 2. :p wa, wa, waaaaaaaa (this my daughter wrote) ### Ian Ross # Using Images in Haddock Documentation on Hackage # Using Images in Haddock Documentation on Hackage A useful but little used feature of Haddock is the ability to include inline images in Haddock pages. Here are a few examples. You can use images for diagrams or for inserting mathematics into your documentation in a readable way. In order to use an image, you just put <<path-to-image>> in a Haddock comment. The image can be of any format that browsers support: PNG, JPEG, SVG, whatever. Until the most recent (1.18) version of Cabal, using this feature was kind of a pain because there was no way to ensure that your image files ended up in a reasonable place in the documentation tree. That meant either hosting the images somewhere other than Hackage, or inserting the image data directly into your Haddock comments, which is painful in the extreme. Now though, Cabal has a new extra-doc-files option you can specify in the Cabal file for your package, which lists files that should be copied from your source tree into the documentation tarball. That means you can get your image files into just the right place with no pain at all. As an example, in the arb-fft package I use a couple of SVG images to render some equations in the documentation. In the source tree there’s a directory called doc-formulae that contains a couple of bits of LaTeX and a Makefile that processes them and uses dvisvgm to turn the resulting DVI output into SVG files. The Cabal file contains a line saying extra-doc-files: doc-formulae/*.svg which ensures that the SVG images end up in the Haddock documentation tarball. I can then refer to them in Haddock comments as something like <<doc-formulae/fft-formula.svg>>, which is really convenient. This should now work for any new uploads to Hackage after a fix last night by Duncan Coutts. <script src="http://zor.livefyre.com/wjs/v3.0/javascripts/livefyre.js" type="text/javascript"></script> <script type="text/javascript"> (function () { var articleId = fyre.conv.load.makeArticleId(null); fyre.conv.load({}, [{ el: 'livefyre-comments', network: "livefyre.com", siteId: "290329", articleId: articleId, signed: false, collectionMeta: { articleId: articleId, url: fyre.conv.load.makeCollectionUrl(), } }], function() {}); }()); </script> ## February 20, 2014 ### Philip Wadler # A formative day for Georg Cantor ## February 18, 2014 ### wren ng thornton # What is the type of the derivative operator? I've been mucking about with real analysis lately. One of the things I've always hated about real analysis (and complex analysis, and other calculus) is the unrepentant lack of types. It's easy to get confused about what's going on and what goes where when you think everything is a real number (or complex number, or tensors thereof). In particular, because of this "everything is a real array" assumption, libraries for performing optimization etc end up with utterly inscrutable APIs and other nastiness like needing to manually flatten your parameters into a single array. So this has got me thinking, what should the API for optimization libraries look like? Which in turn brings me back to an age-old conundrum I've toyed around with before, namely: what is the type of the derivative operator? From the "everything is a real number" perspective we'd say deriv : (ℝ ↝ ℝ) → ℝ → ℝ, where the A ↝ B function space are "nice" functions (e.g., continuous, smooth, analytic, whatever). However, this only works out because we're conflating a number of important differences. For example, for any affine space A we have the difference space ∆A— that is, values in ∆A denote differences or differentials of values in A (e.g., for any a : A and b : A we have a-b : ∆A). However, it turns out that there's a bijection between ℝ and ∆ℝ. It also turns out that the difference of arrays, ∆(ℝn), is isomorphic to an array of differences, (∆ℝ)n. Putting these together we get the common conflation between points (ℝn) and vectors (∆(ℝn)). For another example, consider linear transformations, written A ⊸ B. We have a bijection between linear transformations (ℝm ⊸ ℝn) and matrices (ℝn×m), and hence more specifically a bijection between ℝ and ℝ ⊸ ℝ. So here's what I'm currently thinking: deriv : (F X ↝ Y) → F X → F(∆X ⊸ ∆Y) For now, just ignore F; instantiate it as the identity functor. Thus, the total derivative of f : X ↝ Y at the point x : X is a linear transformation from minor perturbations about x to minor perturbations about f x. We can think of ∆X ⊸ ∆Y as being the "slope" of this mapping between minor perturbations. In particular, when X=ℝ and Y=ℝ, we get a bijection between ∆ℝ ⊸ ∆ℝ and ℝ, so this coincides with the traditional notion of the slope of a one-dimensional curve. Now, let's think about the gradient rather than the total derivative. Assume that F is a "nice" functor (i.e., representable, traversable, etc). Because the functor is representable, we have an isomorphism between F A and I → A (natural in A), where I is the type of positions/indices in F. Thus, the gradient of a function g : F X ↝ Y at the point z : F X is essentially a function from F-indices, i : I, to the i-th partial derivative of g at z. Why partial derivative? Because the linear transformation only takes ∆X as an argument —not ∆(F X)—, thus we can only modify a single "scalar" at a time, and the other scalars in z must remain fixed. Edit 2014.02.17 (#1): Actually, things are a bit more complicated than the above. For example, consider a function f : ℝn ↝ ℝ. The derivative of f with respect to its vector of inputs is not a vector of partial derivatives— rather, it's a covector of partial derivatives! (i.e., deriv (f : ℝn×1 ↝ ℝ) : ℝn×1 → ℝ1×n.) Thus, we should really have that the return type of deriv is some Fop(∆X ⊸ ∆Y) where Fop is some sort of "dual" of F. It's not clear a priori which notion of "duality" is in play here, however. Edit 2014.02.17 (#2): And here's what I'm currently thinking about how to incorporate the Jacobian into the above. Consider this particular instance of the derivative operator, deriv : (F X ↝ G Y) → F X → Fop(∆X ⊸ ∆(G Y)). When G is some type of vectors (e.g., G Y = Yn for some fixed n), we get ∆(G Y) = G(∆Y) as mentioned before. And let's assume ∆X ⊸ G(∆Y) = G(∆X ⊸ ∆Y); presumably this follows immediately by linearity, though I haven't verified that yet. And finally, in our standard real analysis we get that G∘Fop and Fop∘G are the same— that is, vectors-of-covectors and covectors-of-vectors are essentially the same thing; they're just the row-major and column-major representations of matrices, respectively. And then, putting all these together we get that the original return type Fop(∆X ⊸ ∆(G Y)) is isomorphic to G(Fop(∆X ⊸ ∆Y)). So when X=ℝ and Y=ℝ we get the expected deriv : (ℝm ↝ ℝn) → ℝm → ℝn×m. Now, it remains to show how this extends to other choices of F and G... Edit 2014.02.17 (#3): It was pointed out on reddit that the above is "well known"— at least for those who are familiar with differentiable manifolds and tangent spaces. Now, I don't know much about manifolds, but it certainly wasn't well-known to me— which, in itself, says a lot about how little this knowledge has spread to the rest of mathematics. I'm glad to hear there's some followup reading to be done here, but I still don't think the necessary work has been done in terms of turning this into a decent API for optimization libraries. comments ## February 17, 2014 ### Philip Wadler # The Truth About Numbers From Tom the Dancing Bug. "That book is full of secular lies! Here's the only 'math' book you'll ever need!" # Will Snowden be Glasgow University's next Rector? From the Glasgow Herald. Spotted by Mitch Wand. Chris Cassells, a member of the "Elect Snowden as Rector" campaign at Glasgow University, said a Snowden victory would be a gesture against surveillance culture "Having Edward Snowden as rector would give us a megaphone with which we can project our views to a global audience particularly on the issue of state surveillance and the very valid and welcome role of whistleblowers in a democracy," explained the PhD student, 27. "I think he has done a great service to citizens across the world in exposing the corrupt and immoral practises of the NSA and our very own GCHQ. "Studying at the university is dependent on the free exchange of information and freedom of speech, and I think Snowden's revelations hit to the heart of that." ### Silk # Using DOM Mutation Events for node stack traces The Silk client is a single-page application with lots of moving parts. Being new to the codebase, I often find myself wondering when and where a certain page component is created. Basically: which function inserted this particular DOM element? There’s a simple trick to find out. Remember DOM Mutation Events? Widely mocked for being “verbose, slow, and crashy,” they’re marked for deprecation in the DOM spec—but they still work, at least in Chrome and Firefox. And for this use case, their flaws are actually what make them useful: they let us hook into DOM node insertion with the call stack intact. This behavior is problematic for many use cases, and it incurs a performance penalty. So with the newer API, Mutation Observers, handling is postponed and batched into entire subtree insertions, which is more efficient. But it also means useful info is lost; in particular, there’s no way to find out anything about the execution context of the code that inserted each node. With good old mutation events, it’s trivial! So the basic idea is just to attach a mutation event handler for DOM node insertion that captures the current stack trace and saves it for debugging purposes. I chose to save the stack trace as a data attribute on the node itself; this way I can see them easily in the browser’s DOM inspector. Here is the simplest way to do this (pardon the jQuery): (document).bind('DOMNodeInserted', function (e) { (e.target).attr('data-trace', (new Error).stack); });  With this handler in place, every dynamically inserted DOM element gets a property with a stack trace from its point of insertion. With many such elements, the DOM inspector becomes cluttered with big stack traces. To clean it up a bit, we can do some substitutions on the stack trace. This is messy, since the format of the (non-standardized) Error#stack property differs between JavaScript engines. Here’s a quick hack that works in Chrome: (document).bind('DOMNodeInserted', function (e) { (e.target).attr('data-trace', (new Error).stack .split("\n").splice(6).join("\n") .replace(/( +at )|\([^()]+/g,"") .replace(/\n/g,"/ ")); });  This results in a one-line stack trace without source locations, skipping a few uninteresting lines related to the event handler itself. It’s useful if you only need a bit of context. To make this useful across browsers, one could use the Stacktrace.js library, which has a whole arsenal of clever regular expressions to get uniform stack traces. This is left as an exercise for the reader… Another fun trick is to also add some styling to the dynamically-inserted nodes; jQuery UI’s highlight effect, perhaps? A simple border is nice, too. Finally, this little debugging snippet (minus the jQuery) is also suitable as a bookmarklet, in case you want to debug a site without changing its source. This is the bookmarklet I use for Chrome. Try it on your favorite site with dynamic content! Since DOM mutation events are thoroughly deprecated, this trick has a tragic destiny. It would be a nice feature to have built into the browser debugging tools. But until that day, let us celebrate the sunset of this star-crossed API. Silk is hiring! Check out jobs.silk.co to see if that might be something for you or someone you know ## February 16, 2014 ### Yesod Web Framework # Announcing mono-traversable, chunked-data, and conduit-combinators I'm happy to announce the release of a number of packages today, in particular: I want to discuss the purpose of these packages and recent changes. I'm very excited about some of the opportunities these packages are presenting for future growth and use. ## mono-traversable 0.3 mono-traversable's core concept is abstracting over a common pattern: data structures that look like containers, but which may be monomorphic. The primary example of this is ByteString and Text, though this abstraction has proven useful for other cases as well, such as unboxed and storable Vectors, where some typeclass constraint limits the allowed value type. In my experience so far, the most powerful abstraction has been MonoFoldable. Unlike MonoFunctor and MonoTraversable, you don't end up losing any flexibility in data types, since we do not need to retain the original data structure. As such, I've switched over to using MonoFoldable variants of functions in place of Foldable ones in all of my new code. In addition to this core abstraction, mono-traversable provides abstractions for Sets and Maps, non-empty data types, and sequences. This last point can serve as a replacement for a number of list-like abstractions which have been implemented separately over the years. Since the 0.2 release, Greg and I have worked on the following improvements: • Additional instances for Either (thanks to João Cristóvão). • An optimized mapM_ implementation for ByteString. • Greatly improved test coverage. • Remove a number of type classes. As an example, we used to have a separate typeclass for non-empty types which had elements which could be ordered, which allowed for a total and optimized implementation of maximum and minimum. Instead, in version 0.3, MonoFoldable provides a maximumEx function, which can be optimized for an individual datatype, but may throw an exception, and then any non-empty data type may use maximum as a total function. We've done similar things for head, tail and others. • Added unsafe functions like unsafeHead when you need more performance (thanks to John Lato for the idea). • Greatly expanded the collection of Map and Set functions. • A new Data.MinLen module (still experimental), which extends the concept of non-null. Instead of simply encoding size as a boolean, we use type-level naturals to encode the minimum known length of a value. This allows, for example, such total functions as head tail $mlappend listLen1 listLen1. Greg and I have decided to release this initially as an experimental module and, if it works well, replace the current Data.NonNull with it. The core functionality of mono-traversable is pretty stable, and I highly encourage people to give it a shot. ## chunked-data mono-traversable started as extracting some of the typeclass-based functionality from classy-prelude in a principled, law-abiding manner. About half of that functionality fell under the rubrik of monomorphic containers. The other half was an abstraction of different kinds of chunked data: reading a chunk of data from a Handle, textual encoding/decoding, lazy sequences, builders, and zipping. chunked-data contains the remainder of this functionality. This package should be considered somewhat experimental. However, most of the code is simply extracted from classy-prelude, where it's already had quite a bit of testing. So those of you who are somewhat adventurous should definitely jump in and play with it now. If you're more conservative, give in another month or so before experimenting. ## conduit-combinators This is the release I'm most excited about. There's quite a lot going on here, and I'll probably write a separate blog post going into the details of this package. But here's the basic idea. Until now, the primary combinator collection for conduit was the Data.Conduit.List module. This module contains many commonly used functions, like map and isolate. However, there are two things I'm unhappy with in the current module: • The API only works on non-chunked data. For chunked data (like Text and ByteString), you need to use Data.Conduit.Text and Data.Conduit.Binary, respectively. John Lato and I have discussed this a bit in the past, and he made a very convincing argument to me that providing a unified chunked data API is superior. • The naming scheme of Data.Conduit.List does not always encourage best practices. For example, take consumes all incoming values into memory. This was a decision inherited from enumerator, and made sense back when the library was first created. But common usage has changed. This doesn't mean that there's anything broken in Data.Conduit.List, and therefore I have no intention of breaking backwards compatibility by changing the functions there. However, I think it's time to introduce a new, more modern module providing even more combinators, chunked variations, and a more consistent naming scheme. That's where conduit-combinators comes into play. As a quick rundown: • provides generalized versions of all (unless I missed something) functions from Data.Conduit.List, Data.Conduit.Binary, and Data.Conduit.Text • The package makes heavy use of mono-traversable and chunked-data to let this happen, which is what originally instigated my work on those two packages in this development cycle. • since it's higher on the dependency chain, it can depend on packages like vector, and provide specific functions for it (like sinkVector) • adds a lot of missing functions (like takeWhile and mapWhile) • exports a module intended for qualified import: Data.Conduit.Combinators • exports a new module, Conduit, which provides a one-stop-shop for all commonly needed conduit functionality. Combinator names are munged by appending a C. I know many people out there are quite happy with qualified imports, but for those of you like me who enjoy writing a short import list and then having all of the functionality you need available, I think the new Conduit module will be a real pleasure. Since I've been giving stability forecasts, I'll do the same thing here. For the basic functions like map and sinkList, it's highly unlikely that there will ever be a change. However, as I get feedback on the library, I'm likely to make some tweaks to behavior of other functions. One example: there are two sets of behavior that the drop function could reasonably have: • Drop the given number of items, and let the next monadically composed component consume the rest. In this case, drop would be a Consumer. • Drop the given number of items, and then yield the rest of the items downstream. In this case, drop would be a Conduit. I've chosen the former, but I'm open to discussion on the topic. So if you're using conduit in any significant way in your codebase, it's definitely worth checking out this new package. I wouldn't port large codebases over to use it yet unless you're okay needing to refactor again in the next month or so. But I anticipate this package reaching a stable point in the very near future (less than 3 months from now), as it will be a vital component of some work I'm doing at FP Complete. One nice fact about this library: it is currently sitting at 100% HPC test coverage, and I intend to maintain that level going forward. ## classy-prelude 0.8 The most exciting thing about the 0.8 release of classy-prelude is what's not there: any significant code! After the work I've mentioned above, classy-prelude (and -conduit and -yesod) has now become a simple re-export module for functionality defined elsewhere. This is great: the core generalizations have been made available for wider usage, and classy-prelude is merely a convenience for getting at all of that functionality at once. Since classy-prelude is based on the packages above, the same stability guidelines apply. In particular, classy-prelude-conduit may see quite a bit of turbulence as conduit-combinators changes. And if you used the chunked-data or Data.MinLen re-exports from ClassyPrelude, those may be updated in the future. But the vast majority of classy-prelude has remained stable for the past number of versions (accounting for well over a year), and will continue to do so in the future. One question that I've raised and am looking for feedback on: should ClassyPrelude export mtl data types and functions? I opened a Github issue for discussion, and am interested if others have any thoughts on the matter. Look forward to some blog posts demonstrating usage of these libraries over the next few weeks. And if you have any recommendations for improvement, please bring them up! ### Arch Haskell News # Another build of ghc 7.8 available Yesterday evening I pushed out a new build of ghc 7.8 to [haskell-testing] and now all packages and the DB are signed so the stanza to use is  [haskell-testing] Server = http://xsounds.org/~haskell/testing/$arch 

Please make sure to put it right after [main] to pacman doesn’t accidentally mix in Haskell packages from [extra] or [contrib].

Enjoy!

# Hidden Markov Models for Natural Language Tagging, in Haskell

I became intrigued in Hidden Markov Models after reading Kurzweil, who claims they can be used to model the thinking process in the brain. There is much debate about that, but these are interesting AI structures. This page I think has a good introduction.

I was working though the (partial) online book on Natural Language Processing with Haskell, and thought of combining the two. I used Mike Izbicki's hmm library for a one order Hidden Markov Model implementation. Once I initialized the model properly using the training data, I got around 91% accuracy on tagging, which is on par with the rules based approach presented in the nlpwp book.

I used the strategy outline in this paper to deal with unknown words (words in the test set not met in the training set): replace these words with a token that is also used for low frequency words in the training set. So far I've used only one token but I suppose being a bit more fined grained (to distinguish words starting with a capital letter, currency amounts, numbers) will improve results.

Performance is not very good even with some parallelism, so I think I need to spend more time on it, but it's definitely encouraging. It'll be a little bit of time till I have a thinking brain, though, but there is hope!

# announcement: tls-1.2 is out

One year ago, I’ve started some big changes on the tls package. I’ve finally manage to wrap it up in something that people can use straight out of hackage.

## State improvements

One major limitation of previous tls versions, was that you wouldn’t be able to read and write data at the same time, since all the state was behind a big-lock single mvar. Now the state is separated between multiple smaller states with can be concurrently used:

• the RX state for receiving data.
• the TX state for sending data.
• the handshake state for creating new security parameters to replace RX/TX state when the handshake is finished
• Misc state for other values.

For many protocols like HTTP, this was never an issue as the reading and writing are disjoints. But some others protocols that do intertwined read and write (AMQP, IMAP, SMTP, ..) were rightfully having difficulties to use tls.

This provide a more scalable implementation, and optimise the structure changes to the minimum needed.

## Certificate improvements

The second pharaonic change was a major rewrite of ASN.1, X509 and the handling of certificate. The support libraries are now splitted in more logical units, and provide all the necessary foundations for a much simplified handling of certificates.

ASN.1 that was previously all in asn1-data is splitted into asn1-types for the high level ASN.1 Types, asn1-encoding for BER and DER binary encoding support, and asn1-parse to help with parsing ASN.1 representation into high level types. Generally, the code is nicer and able to support more cases, and also more stress tested.

Certificate certificate is splitted too and is now deprecated in favor of:

• x509: Contains all the format parser and writer for certificate, but also now support CRL. The code has been made more generic and better account certificate formats from the real world.
• x509-store: Contains some routines to store and access certificates on disk; this is not very different than what was in [certificate](http://hackage.haskell.org/package/certificate“).
• x509-system: Contains all routines to access system certificates, mainly the trusted CA certificates supported. The code is not different from [certificate](http://hackage.haskell.org/package/certificate“) package, except there’s now Windows supports for accessing the system certificate store.
• x509-validation: One of the main security aspect of the TLS stack, is certificate validation, which is a complicated and fiddly process. The main fiddly aspect is the many input variables that need to be considered, combined with errata and extensions. The reason to have it as a separate package it to make it easy to debug, while also isolating this very sensitive piece of code. The feature is much more configurable and tweakable.

On the TLS side, previous version was leaving the whole validation process to a callback function. Now that we have a solid stack of validation and support for all main operating systems, tls now automatically provide the validation function enabled and with the appropriate security parameters by default. Of course, It’s still possible to change validation parameters, add some hooks and add a validation cache too.

The validation cache is a way to take a fingerprint and get cached yes/no answer about whether the certificate is accepted. It’s a generic lookup mechanism, so that it could work with any storage mechanism. The same mechanism can be overloaded to support Trust-on-first-use, and exceptions fingerprint list.

Exceptions list a great way to use self-signed certificates without compromising on security; You have to do the validation process out-of-band to make sure the certificate is really the one, and then store a tuple of the name of the remote accessed associated with a fingerprint. The fingerprint is a simple hash of the certificate, whereas the name is really just a simple (hostname, service) tuple.

## Key exchange methods

Along with RSA signature, there’s now DSA signature support for certificate.

Previous versions only supported the old RSA key exchange methods. After a bit of refactoring, we now have DHE-RSA and DHE-DSS support. DHE is ephemereal Diffie Hellman, and provide Forward Secrecy.

In the future, with this refactoring in place, ECDHE based key exchange methods and ECDSA signature will be very easy to add.

## API and parameters changes

The initialization parameters for a context is now splitted into multiples smaller structures:

• one for the supported parameters (versions, ciphers methods, compressions methods, ..)
• one for shared access structures (x509 validation cache, x509 CA store, session manager, certificate and keys)
• the client and server parameters are now 2 distinct structures. this is not anymore a common structure with a role part.

All this change allow better separation of what parameters are for the client and the server, and should also make it easier to setup better default, and allow tweaking of the configuration to be more self contain. The aim is only to have to set your “Shared” structure, and for the remaining structures uses default.

tls-extra has been merged in tls.

## TLS Protocol Versions

Previous tls packages were not able to downgrade protocol version. This is now completely fixed, and by default tls will try to use the maximum supported version (by default, TLS 1.2) instead of the version specified by the user (by default, TLS 1.0).

## Client use

For client connection, I recommend to use connection instead of tls directly.

## Closing note

And finally this is the extents of the modifications just in tls:

 82 files changed, 5528 insertions(+), 4568 deletions(-)

Enjoy,

# Ghc 7.8.0 rc1 in testing repo

I’ve just finished uploading a few packages compiled with Ghc 7.8.0 rc1. Please try it out and report how it goes!

[haskell-testing] Server = http://xsounds.org/~haskell/testing/$arch SigLevel = Never The packages included are Crypto 4.2.5.1 Diff 0.3.0 FileManipCompat 0.18 GLURaw 1.4.0.0 GLUT 2.5.1.0 Glob 0.7.3 HTTP 4000.2.10 HUnit 1.2.5.2 IfElse 0.85 MonadCatchIO-mtl 0.3.1.0 MonadCatchIO-transformers 0.3.1.0 ObjectName 1.0.0.0 OpenGL 2.9.1.0 OpenGLRaw 1.4.0.0 QuickCheck 2.6 SHA 1.6.4 StateVar 1.0.0.0 Unixutils-shadow 1.0.0 X11 1.6.1.1 X11-xft 0.3.1 abstract-deque 0.2.2.1 abstract-par 0.3.3 alex 3.1.3 anansi 0.4.5 ansi-terminal 0.6.1 ansi-wl-pprint 0.6.7.1 async 2.0.1.5 attoparsec 0.11.1.0 base-unicode-symbols 0.2.2.4 base16-bytestring 0.1.1.6 base64-bytestring 1.0.0.1 bktrees 0.3.1 blaze-builder 0.3.3.2 blaze-builder-conduit 1.0.0 blaze-html 0.7.0.1 blaze-markup 0.6.0.0 byteable 0.1.1 case-insensitive 1.1.0.3 cereal 0.4.0.1 cmdargs 0.10.7 cmdlib 0.3.5 colour 2.3.3 conduit 1.0.13 cpphs 1.17.1 crypto-api 0.13 cryptohash 0.11.2 csv 0.1.2 curl 1.3.8 data-default 0.5.3 data-default-class 0.0.1 data-default-instances-base 0.0.1 data-default-instances-containers 0.0.1 data-default-instances-dlist 0.0.1 data-default-instances-old-locale 0.0.1 date-cache 0.3.0 digest 0.0.1.2 dlist 0.6.0.1 edit-distance 0.2.1.2 entropy 0.2.2.4 erf 2.0.0.0 exceptions 0.3.3 extensible-exceptions 0.1.1.4 fast-logger 2.1.5 fgl 5.4.2.4 filemanip 0.3.6.2 ghc-paths 0.1.0.9 ghc-syb-utils 0.2.1.2 graphviz 2999.16.0.0 happy 1.19.3 hashable 1.2.1.0 haskeline 0.7.1.2 hasktags 0.68.7 hastache 0.5.1 hinotify 0.3.6 hostname 1.0 hs-bibutils 5.0 hscolour 1.20.3 hslogger 1.2.3 hslua 0.3.10 html 1.0.1.2 http-attoparsec 0.1.1 http-date 0.0.4 http-types 0.8.3 hxt 9.3.1.3 hxt-charproperties 9.1.1.1 hxt-regex-xmlschema 9.1.0 hxt-unicode 9.0.2.1 ieee754 0.7.3 interlude 0.1.2 io-choice 0.0.5 json 0.7 language-haskell-extract 0.2.4 largeword 1.0.5 libxml-sax 0.7.4 lifted-base 0.2.1.1 maccatcher 2.1.5 math-functions 0.1.4.0 mmap 0.5.9 mmorph 1.0.2 monad-control 0.3.2.2 monad-logger 0.3.4.0 monad-loops 0.4.2 monad-par 0.3.4.6 monad-par-extras 0.3.3 monads-tf 0.1.0.1 mtl 2.1.2 mwc-random 0.13.1.1 nats 0.1.2 network 2.4.2.2 network-conduit 1.0.2.1 network-info 0.2.0.3 optparse-applicative 0.7.0.2 parallel 3.2.0.4 parallel-io 0.3.3 parsec 3.1.5 path-pieces 0.1.3.1 polyparse 1.9 pool-conduit 0.1.2 primitive 0.5.1.0 pureMD5 2.1.2.1 pxsl-tools 1.0.1 random 1.0.1.1 regex-base 0.93.2 regex-compat 0.95.1 regex-pcre 0.94.4 regex-posix 0.95.2 resource-pool 0.2.1.1 resourcet 0.4.10 safe 0.3.4 scientific 0.2.0.1 semigroups 0.12.2 shellish 0.1.4 silently 1.2.4.1 simple-sendfile 0.2.13 split 0.2.2 statistics 0.10.5.2 stm 2.4.2 stm-chans 3.0.0 strict 0.3.2 syb 0.4.1 system-argv0 0.1.1 system-fileio 0.3.12 system-filepath 0.4.9 tagged 0.7 tagsoup 0.13.1 tar 0.4.0.1 temporary 1.2.0.1 test-framework 0.8.0.3 test-framework-hunit 0.3.0.1 test-framework-quickcheck2 0.3.0.2 text 0.11.3.1 th-lift 0.5.6 th-orphans 0.8 time-compat 0.1.0.3 transformers-base 0.4.1 uniplate 1.6.12 unix-compat 0.4.1.1 unix-time 0.2.2 unordered-containers 0.2.3.3 utf8-string 0.3.7 uuid 1.3.3 vault 0.3.0.3 vector 0.10.9.1 vector-algorithms 0.6.0.1 vector-binary-instances 0.2.1.0 void 0.6.1 wai 2.0.0 warp 2.0.3 wl-pprint-text 1.1.0.2 xhtml 3000.2.1 xml 1.3.13 xml-types 0.3.4 xmlgen 0.6.2.1 xmonad 0.11 zip-archive 0.2 zlib 0.5.4.1 ### Well-Typed.Com # Performance profiling with ghc-events-analyze ghc-events-analyze is a new simple Haskell profiling tool that uses GHC's eventlog system. It helps with some profiling use cases that are not covered by the existing GHC profiling modes or tools. It has two major features: • While ThreadScope shows CPU activity across all your cores, ghc-events-analyze shows CPU activity across all your Haskell threads. • It lets you label periods of time during program execution (by instrumenting your code with special trace calls) and then lets you visualize those time periods or get statistics on them. It is very useful for profiling code when ghc's normal profiling mode is not available, or when using profiling mode would perturb the code too much. It is also useful when you want time-profiling information with a breakdown over time rather than totals for the whole run. We developed the tool at Well-Typed while working on client projects where we had profiling needs that were not covered by the existing tools. We are releasing the tool in the hope that it will be useful to others. ## Motivating Example Suppose we want to understand the runtime performance of the following simple multi-threaded application: import Control.Concurrent (threadDelay) import Control.Concurrent.Async (async, wait)  -- Intentionally slow fib fib :: Integer -> Integer fib 0 = 1 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2)  printFib :: Integer -> IO () printFib n = print (fib n)  blips :: IO () blips = do putStrLn "BLIP" threadDelay 5000000 putStrLn "BLIP"  main :: IO () main = do a1 <- async$ mapM_ printFib [30, 32 .. 38]
a2 <- async $mapM_ printFib [31, 33 .. 39] threadDelay 5000000 a3 <- async$ blips
mapM_ wait [a1, a2, a3]


We can compile this application and ask it to produce an eventlog:

ghc ex0 -eventlog
./ex0 +RTS -l


But when we open this eventlog in ThreadScope the result is not particularly enlightening:

The program was compiled without the -threaded flag, forcing all work to run on a single HEC (Haskell Execution Context — roughly, a CPU core). This makes it impossible to see the distribution of workload across the various application threads. This will be true whenever multiple threads are executed by a single HEC (i.e., almost always). Of course ThreadScope is really designed for looking at parallel programs, and that's not what we've got here. Here we're trying to understand the behaviour of a simple concurrent program.

If we run the same eventlog through ghc-events-analyze instead we get

Some points to note:

• ghc-events-analyze applies quantization; the total execution time is divided up into n buckets (by default 100; for these examples we chose 50) and computes for each bucket and each thread what percentage of that bucket the thread was active.
• This percentage is used to colour each block in the diagram; darker means a larger percentage. If the thread was not active at all the block is grey, but a percentage q other than 0 is shown as a darkness 0.1 + 0.9 * q. This means that we can visually see when a thread does anything at all; for instance, it is immediately clear from the diagram when the blips thread (with ID 4) is doing something. If we used the percentage q directly as darkness then a thread doing nothing would be visually indistinguishable from a thread doing just a print, say.
• We can see that initially both threads are equally busy (the scheduler is assigning approximately 48% CPU time to both), until the first thread completes and the second thread gets 97% of CPU (ghc-events-analyze also generates the same report in textual form with precise values for each block).
• The lifetime of each thread is also immediately clear.

### Instrumentation

If we instrument our code, we can improve this diagram in a number of ways. We can use labelThread from GHC.Conc to give our threads names, so that it becomes easier to see what's what.

Moreover, ghc-events-analyze lets us give labels to periods of time during execution which we can then visualise or get statistics on. To label a period of time we use the event tracing functions from Debug.Trace. We mark the start of a period with

traceEventIO "START <eventName>"


and the end with

traceEventIO "STOP <eventName>"


Use traceEventIO if you are in an IO context, while in a pure context you can use traceEvent.

Note that these labelled time periods are completely independent of threads; they can overlap each other, span multiple threads, etc. Here's our example application again, but with some instrumentation added:

import Control.Concurrent (myThreadId, threadDelay)
import Control.Concurrent.Async (Async, async, wait)
import Control.Exception (bracket_)
import Debug.Trace (traceEventIO)

event :: String -> IO a -> IO a
event label =
bracket_ (traceEventIO $"START " ++ label) (traceEventIO$ "STOP "  ++ label)

async' :: String -> IO a -> IO (Async a)
async' label act = async $do tid <- myThreadId labelThread tid label act  -- Intentionally slow fib fib :: Integer -> Integer fib 0 = 1 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2)  printFib :: Integer -> IO () printFib n = event ("fib" ++ show n)$ print (fib n)

blips :: IO ()
blips = do
putStrLn "BLIP"
putStrLn "BLIP"

main :: IO ()
main = do
a1 <- async' "evens" $mapM_ printFib [30, 32 .. 38] a2 <- async' "odds"$ mapM_ printFib [31, 33 .. 39]
a3 <- async' "blips"  blips mapM_ wait [a1, a2, a3]  Running ghc-events-analyze over the eventlog generated by this code yields If we run the same code using the threaded runtime (but still on a single core), we get and if we run it on two cores We can see that the evens and odds threads are now in fact running in parallel, and that the computation of fib 38 is finished well before the computation of fib 39. ### Totals Bear in mind, however, that ghc-events-analyze divides the total time up into n buckets, so what you can not see from these last two diagrams is that the total time taken is less when running on two cores. ghc-events-analyze also outputs some totals. For the single core case it tells us GC 1343672000ns 1.344s USER EVENTS (user events are corrected for GC) fib39 24480557000ns 24.481s fib38 21493145000ns 21.493s fib37 12702151000ns 12.702s fib36 7823058000ns 7.823s fib35 4797324000ns 4.797s fib34 2966990000ns 2.967s fib33 1800136000ns 1.800s fib32 1097888000ns 1.098s fib31 663900000ns 0.664s fib30 419270000ns 0.419s TOTAL 78244419000ns 78.244s THREAD EVENTS 1 138000ns 0.000s IOManager (2) 296000ns 0.000s 3 106000ns 0.000s evens (4) 16826523000ns 16.827s odds (5) 27488818000ns 27.489s blips (6) 63000ns 0.000s 7 27000ns 0.000s TOTAL 44315971000ns 44.316s  and for the two cores case GC 1171012000ns 1.171s USER EVENTS (user events are corrected for GC) fib39 18769541000ns 18.770s fib38 12009913000ns 12.010s fib37 7515686000ns 7.516s fib36 4692912000ns 4.693s fib35 2852639000ns 2.853s fib34 1774758000ns 1.775s fib33 1095500000ns 1.096s fib32 674125000ns 0.674s fib31 395699000ns 0.396s fib30 240785000ns 0.241s TOTAL 50021558000ns 50.022s THREAD EVENTS 1 138000ns 0.000s IOManager (2) 269000ns 0.000s 3 88000ns 0.000s evens (4) 19338615000ns 19.339s odds (5) 30086294000ns 30.086s blips (6) 73000ns 0.000s 7 9000ns 0.000s TOTAL 49425486000ns 49.425s  For the user-labelled time periods the tool is giving us the wall-clock time between the "START" and "STOP" events, excluding time spent doing GC. If there are multiple start/stop periods for the same label then it gives us the total time. We exclude GC time because GC happens at essentially arbitrary points and it would not be helpful to account the full cost of a GC to one user-labelled time period (which might otherwise be very short indeed). Some notes for this example: • The total amount of time for our fibNN-periods is more in the one core case than the two core case, because in the single core case neither of the threads evaluating fib calls are running all the time — since the two threads have to share the one core. • However, the total time across all threads is approximately the same in both cases; we are still doing the same amount of work, it's just that in the two core case the work of some of those threads is overlapped. • It is important not to confuse user-labelled time periods with a thread running and doing real work. We can see in this example in the single-core case that the sum of all the fibNN time periods is much longer than the total execution time of all threads in the program (78.2 seconds vs 44.3 seconds). That is because we have two threads running these fib tasks but each of those threads is only getting about 50% of the CPU. In the two-core case the two threads each get a core to themselves and so the total of our fibNN time periods is very close to the total thread execution time (50.0 seconds vs 49.4 seconds). ## Real World Application 1 Well-Typed have been developing a server application for a client. The client reported that after certain kinds of requests the server had unexpected spikes in CPU usage. For technical reasons we could not compile the server application in profiling mode, and hence profiling information was not available. Moreover, GHC's normal time profiling would have given us totals across the whole program run (broken down by cost centre), but we needed a breakdown of CPU usage over time. We could however generate an eventlog. Visualizing the eventlog with threadscope yielded We can make certain educated guesses from this picture: the spikes in activity are probably different requests coming in to the server, and the reported unexpected CPU usage reported by the client might be related to garbage collection (the orange blobs that threadscope shows). However, instrumenting the code (by labelling some threads and labelling time periods that correspond to the server handling different kinds of requests) and then running it through ghc-events-analyze yielded a more informative picture: (ghc-events-analyze's reports are fully customizable through a simple scripting language; many of the diagrams in this blogpost are generated using custom scripts in order to improve readability.) The labelled time periods now clearly show when the server is handing requests of type A and B, and we see corresponding spikes in CPU activity in the server's main thread (with ID 6). Threads 4 and 5 handle communication between the client and server, and we see "blips" at the start and end of each request, as expected. The garbage collection during the A requests is expected, both because of domain specific knowledge about what type A requests are, but also from the diagram: there are spikes in CPU usage of the server's Main thread. However, garbage collection during the B requests is not expected: again, both from domain specific knowledge about type B requests, but also from the diagram: there is barely any activity in the system at all, so why so much garbage collection? This lead us to suspect "idle GC". The GHC garbage collector will run in two cases: (1) when required when we're out of memory, and (2) after the whole program has been idle for a bit. The latter is known as idle GC. The point of idle GC is the hope that we might be able to return some memory to the OS. The default is to do a GC 0.3 seconds after the program becomes idle. This means if your program does a tiny bit of work every 0.4 seconds but is otherwise idle then you're going to be paying for a major GC every 0.4 seconds. We can adjust the timeout for when idle GC happens, or even disable it entirely using the +RTS -Ix flag. In our case, running the server with a much longer timeout for idle GC cycles yielded this picture: Note how we no longer see much garbage collection during B requests; we still get garbage collection during A requests, but that is expected. Moreover, we don't see any garbage collection after the second B request either. We found that this had been due to a new thread (199) that was spawned by the second B request. This thread was running occasionally but because it was the only active thread it determined whether the whole system was idle. It was letting the system go idle just long enough to trigger idle GC, then doing a tiny bit of work, more idle GC etc. These collections are not cheap because they are major collections that scan the whole heap. The simple thing to do in this situation is to just disable idle GC entirely with +RTS -I0. We decided to keep it because it is still useful to return memory to the system in this case, we just use a much longer timeout. ## Real World Application 2 Well-Typed was asked by a client to help improve the performance of an application. At one point during this work we needed to determine what proportion of overall execution time a certain family of functions were taking, and a breakdown between these functions. GHC's normal time profiling was not appropriate for a few reasons: • Assigning manual cost centers to the family of functions of interest would have been tricky for technical reasons: they were not separate named functions but one class-overloaded function and we wanted to count each instance separately. • The application had some parts heavily optimized already, and the instrumentation added by using a profiling build would skew the results too much. • The program took a long time to run as it was; enabling profiling would make the edit-run development cycle too slow. The overhead added by enabling the eventlog is negligible however. Moreover, we can easily use traceEvent to label the execution of our class-overloaded function for each of its various instances (like we did in the fib example, above). The totals reported by ghc-events-analyze enabled us to easily get the total time taken by this family of functions and the breakdown by instance, and to guide our subsequent improvements (like normal profiling would). GC 25421789435ns 25.422s A-X 53959674392ns 53.960s  DETAILED BREAKDOWN T 10574202528ns 10.574s F 5776369439ns 5.776s D 4389066320ns 4.389s A 3939896208ns 3.940s K 3135897321ns 3.136s Q 2706127000ns 2.706s O 2586121945ns 2.586s W 2295049375ns 2.295s C 2198859200ns 2.199s R 1791326834ns 1.791s X 1734910406ns 1.735s V 1727701880ns 1.728s B 1709562291ns 1.710s E 1385853161ns 1.386s P 1383600793ns 1.384s S 1165241932ns 1.165s H 1128639979ns 1.129s M 860537704ns 0.861s L 810106269ns 0.810s I 691345817ns 0.691s U 595493497ns 0.595s N 499041244ns 0.499s G 462912372ns 0.463s J 411810877ns 0.412s  We have replaced the real names from this program with labels AX. By comparing the overall execution time excluding GC (which we get from +RTS -s) we can see that the total of all these calls made up the vast majority of the program execution time. So this tells us that we don't need to worry about optimising the rest of the program and can concentrate on this family of functions. We can also see that the top few most expensive variants of the function account for the majority of that time. Thus we were able to focus our attention on the parts of the code where there was greatest opportunity to make improvements. In this case the visualization of CPU usage over time does not tell us much extra: except that our family of functions are indeed busy very consistently after an initial setup (at about 60% of CPU, with the garbage collector running at about 25% CPU). It is worth noting that when we generated the eventlog for this application we selected only user events and GC events (+RTS -l-agu -RTS). Excluding the thread scheduler events dramatically reduces the size of the eventlog, which in this case would have been too big otherwise. ghc-events-analyze does still work without the thread scheduler events being available, but you do then miss out on the per-thread breakdown of CPU activity. Moreover, since the creation of this diagram is relatively time consuming for large eventlogs, you can ask ghc-events-analyze to omit it if you are interested only the totals and the breakdown. ## Availability ghc-events-analyze is available from Hackage; the source code is available from github. Patches for bug fixes or feature enhancements are welcome! The code is written to be easily extensible with additional reports or analyses. ### Keegan McAllister # x86 is Turing-complete with no registers In which x86 has too many registers after all. # Introduction The fiendish complexity of the x86 instruction set means that even bizarrely restricted subsets are capable of arbitrary computation. As others have shown, we can compute using alphanumeric machine code or English sentences, using only the mov instruction, or using the MMU as it handles a never-ending double-fault. Here is my contribution to this genre of Turing tarpit: x86 is Turing-complete with no registers. # No registers? What do I mean by "no registers"? Well, really just whatever makes the puzzle interesting, but the basic guideline is: No instruction's observable behavior can depend on the contents of any ordinary user-space register. So we can't read from R[ABCD]X, R[SD]I, R[SB]P (that's right, no stack), R8-R15, any of their smaller sub-registers, or any of the x87 / MMX / SSE registers. This forbids implicit register access like push or movsb as well as explicit operands. I think I would allow RIP-relative addressing, but it's probably not useful when you're building a single executable which loads at a fixed address. We also can't use the condition flags in EFLAGS, so conditional jumps and moves are right out. Many instructions will set these flags, but those dead stores are okay by me. All memory access depends on segment selectors, the page table base in CR3, and so on. We trust that the OS (Linux in my example) has set up a reasonable flat memory model, and we shouldn't try to modify that. Likewise there are debug registers, parts of EFLAGS (such as the trap bit), and numerous MSRs which can influence the execution of nearly any instruction. We ignore all that too. Basically, the parts of CPU state which normal user-space code doesn't touch are treated as constants. So what's left that we can work with? Just • the instruction pointer, • memory operands, and • self-modifying code. But it would be too easy to self-modify an instruction into having a register operand. The above restrictions must hold for every instruction we execute, not just those appearing in our binary. Later on I'll demonstrate experimentally that we aren't cheating. # The instruction set In a RISC architecture, every memory access is a register load or store, and our task would be completely impossible. But x86 does not have this property. For example we can store a constant directly into memory. Here's machine code along with NASM (Intel syntax) assembly: c6042500004000ba mov byte [0x400000], 0xba66c7042500004000dbba mov word [0x400000], 0xbadbc7042500004000efbead0b mov dword [0x400000], 0xbadbeef48c7042500004000efbead0b mov qword [0x400000], 0xbadbeef In the latter case the 4-byte constant is sign-extended to 8 bytes. We can also perform arithmetic on a memory location in place: 8304250000400010 add dword [0x400000], 0x10 But moving data around is going to be hard. As far as I know, every instruction which loads from one address and stores to another, for example movsb, depends on registers in some way. Conditional control flow is possible thanks to this gem of an instruction: ff242500004000 jmp qword [0x400000] This jumps to whatever address is stored as a 64-bit quantity at address 0x400000. This seems weird but it's really just a load where the destination register is the instruction pointer. Many RISC architectures also allow this. # Compiling from Brainfuck Let's get more concrete and talk about compiling Brainfuck code to this subset of x86. Brainfuck isn't the simplest language out there (try Subleq) but it's pretty familiar as an imperative, structured-control language. So I think compiling from Brainfuck makes this feel "more real" than compiling from something super weird. A Brainfuck program executes on a linear tape of (typically) byte-size cells. TAPE_SIZE equ 30000tape_start: times TAPE_SIZE dq cell0head equ tape_start + (TAPE_SIZE / 2) Like many Brainfuck implementations, the tape has a fixed size (more on this later) and we start in the middle. head is not a variable with a memory location; it's just an assembler constant for the address of the middle of the tape. Since our only way to read memory is jmp [addr], the tape must store pointers to code. We create 256 short routines, each representing one of the values a cell can hold. cont_zero: dq 0cont_nonzero: dq 0out_byte: db 0align 16cell_underflow: jmp inc_cellalign 16cell0: mov byte [out_byte], 0 jmp [cont_zero]%assign cellval 1%rep 255 align 16 mov byte [out_byte], cellval jmp [cont_nonzero] %assign cellval cellval+1%endrepalign 16cell_overflow: jmp dec_cell There are two things we need to do with a cell: get its byte value for output, and test whether it's zero. So each routine moves a byte into out_byte and jumps to the address stored at either cont_zero or cont_nonzero. We produce most of the routines using a NASM macro. We also have functions to handle underflow and overflow, so a cell which would reach -1 or 256 is bumped back to 0 or 255. (We could implement the more typical wrap-around behavior with somewhat more code.) The routines are aligned on 16-byte boundaries so that we can implement Brainfuck's + and - by adding or subtracting 16. But how do we know where the head is? We can't store it in a simple memory variable because we'd need a double-indirect jump instruction. This is where the self-modifying code comes in. test_cell: jmp [head]inc_cell: add qword [head], 16 jmp test_celldec_cell: sub qword [head], 16 jmp test_cellmove_right: add dword [inc_cell+4], 8 add dword [dec_cell+4], 8 add dword [test_cell+3], 8 jmp [cont_zero]move_left: sub dword [inc_cell+4], 8 sub dword [dec_cell+4], 8 sub dword [test_cell+3], 8 jmp [cont_zero] Recall that head is an assembler constant for the middle of the tape. So inc_cell etc. will only touch the exact middle of the tape — except that we modify the instructions when we move left or right. The address operand starts at byte 3 or 4 of the instruction (check the disassembly!) and we change it by 8, the size of a function pointer. Also note that inc_cell and dec_cell jump to test_cell in order to handle overflow / underflow. By contrast the move instructions don't test the current cell and just jump to [cont_zero] unconditionally. To output a byte we perform the system call write(1, &out_byte, 1). There's no escaping the fact that the Linux system call ABI uses registers, so I allow them here. We can do arbitrary computation without output; it's just nice if we can see the results. Input is messier still but it's not fundamentally different from what we've seen here. Code that self-modifies by calling read() is clearly the future of computing. Putting it all together, I wrote a small Brainfuck compiler which does little more than match brackets. For each Brainfuck instruction it outputs one line of assembly, a call to a NASM macro which will load cont_[non]zero and jump to one of test_cell, inc_cell, etc. For the program [+] the compiler's output looks like k00000000: do_branch k00000003, k00000001k00000001: do_inc k00000002k00000002: do_branch k00000003, k00000001k00000003: jmp exit which blows up into something like 401205: 48c70425611240005c124000 mov qword ptr [0x401261], 0x40125c401211: 48c704256912400022124000 mov qword ptr [0x401269], 0x40122240121d: e90cefffff jmp 40012e <test_cell>401222: 48c70425611240003f124000 mov qword ptr [0x401261], 0x40123f40122e: 48c70425691240003f124000 mov qword ptr [0x401269], 0x40123f40123a: e9f6eeffff jmp 400135 <inc_cell>40123f: 48c70425611240005c124000 mov qword ptr [0x401261], 0x40125c40124b: 48c704256912400022124000 mov qword ptr [0x401269], 0x401222401257: e9d2eeffffe9d2eeffff jmp 40012e <test_cell>40125c: e9c1eeffff jmp 400122 <exit> Even within our constraints, this code could be a lot more compact. For example, a test could be merged with a preceding inc or dec. # Demos Let's try it out on some of Daniel B Cristofani's Brainfuck examples.  curl -s http://www.hevanet.com/cristofd/brainfuck/rot13.b | ./compiler$echo 'Uryyb, jbeyq!' | ./ripHello, world!$ curl -s http://www.hevanet.com/cristofd/brainfuck/fib.b | ./compiler$./rip011235813… And now let's try a Brainfuck interpreter written in Brainfuck. There are several, but we will choose the fastest one (by Clive Gifford), which is also compatible with our handling of end-of-file and cell overflow. $ curl -s http://homepages.xnet.co.nz/~clive/eigenratios/cgbfi2.b | ./compiler$(curl -s http://www.hevanet.com/cristofd/brainfuck/rot13.b; echo '!Uryyb, jbeyq!') | ./ripHello, world! This takes about 4.5 seconds on my machine. # Verifying it with ptrace How can we verify that a program doesn't use registers? There's no CPU flag to disable registers, but setting them to zero after each instruction is close enough. Linux's ptrace system call allows us to manipulate the state of a target process. uint64_t regs_boundary;void clobber_regs(pid_t child) { struct user_regs_struct regs_int; struct user_fpregs_struct regs_fp; CHECK(ptrace(PTRACE_GETREGS, child, 0, &regs_int)); if (regs_int.rip < regs_boundary) return; CHECK(ptrace(PTRACE_GETFPREGS, child, 0, &regs_fp)); // Clear everything before the instruction pointer, // plus the stack pointer and some bits of EFLAGS. memset(&regs_int, 0, offsetof(struct user_regs_struct, rip)); regs_int.rsp = 0; regs_int.eflags &= EFLAGS_MASK; // Clear x87 and SSE registers. memset(regs_fp.st_space, 0, sizeof(regs_fp.st_space)); memset(regs_fp.xmm_space, 0, sizeof(regs_fp.xmm_space)); CHECK(ptrace(PTRACE_SETREGS, child, 0, &regs_int)); CHECK(ptrace(PTRACE_SETFPREGS, child, 0, &regs_fp)); clobber_count++;} For the layout of struct user_regs_struct, see /usr/include/sys/user.h. We allow registers in the first part of the program, which is responsible for system calls. regs_boundary is set by looking for the symbol FORBID_REGS in the binary. We run the target using PTRACE_SINGLESTEP, which sets the trap flag so that the CPU will raise a debug exception after one instruction. Linux handles this exception, suspends the traced process, and wakes up the tracer, which was blocked on waitpid. while (1) { // For this demo it's simpler if we don't deliver signals to // the child, so the last argument to ptrace() is zero. CHECK(ptrace(PTRACE_SINGLESTEP, child, 0, 0)); CHECK(waitpid(child, &status, 0)); if (WIFEXITED(status)) finish(WEXITSTATUS(status)); inst_count++; clobber_regs(child);} And the demo: $ gcc -O2 -Wall -o regclobber regclobber.c$curl -s http://www.hevanet.com/cristofd/brainfuck/rot13.b | ./compiler$ echo 'Uryyb, jbeyq!' | time ./regclobber ./ripHello, world!Executed 81366 instructions; clobbered registers 81189 times.0.36user 1.81system 0:01.96elapsed 110%CPU (0avgtext+0avgdata 1392maxresident)k

At almost two seconds elapsed, this is hundreds of times slower than running ./rip directly. Most of the time is spent in the kernel, handling all those system calls and debug exceptions.

I wrote about ptrace before if you'd like to see more of the things it can do.

# Notes on universality

Our tape has a fixed size of 30,000 cells, the same as Urban Müller's original Brainfuck compiler. A system with a finite amount of state can't really be Turing-complete. But x86 itself also has a limit on addressable memory. So does C, because sizeof(void *) is finite. These systems are Turing-complete when you add an external tape using I/O, but so is a finite-state machine!

So while x86 isn't really Turing-complete, with or without registers, I think the above construction "feels like" arbitrary computation enough to meet the informal definition of "Turing-complete" commonly used by programmers, for example in the mov is Turing-complete paper. If you know of a way to formalize this idea, do let me know (I'm more likely to notice tweets @miuaf than comments here).

# van Laarhoven Free Monad

As I mentioned some time ago, Mauro Jaskelioff and I have been working on a paper discussing Twan van Laarhoven’s representation of second order functionals used in van Laarhoven lenses and traversals. Mauro’s theorem is a generalization of Milewski’s proof that, by using two applications of the Yoneda lemma, one can exhibit an isomorphism between PStore i j a and forall f. Functor f => (i -> f j) -> f a where PStore is the parameterized store comonad defined below.

data PStore i j a = PStore { pos :: i; peek :: j -> a }

Mauro’s theorem, discovered independently at the same time as Milewski’s, adds an adjunction to the mix leading to an isomorphism that works for lenses, traversals, affine traversals, and more. It is the ‘and more’ that I want to discuss.

One application of Mauro’s theorem is the van Laarhoven free monad representation for algebraic effects, or van Laarhoven free monad for short. The basic theorem states that FreeMonad (PStore i j) a and forall m. Monad m => (i -> m j) -> m a are isomorphic. The advanced version states that FreeMonad (Σ n. PStore in jn) a and forall m. Monad m => (Π n. in -> m jn) -> m a are isomorphic.

data FreeMonad f a = Return a | FreeMonad (f (FreeMonad f a))

A free monad of a sum of store functors is the exactly the sort of free monad that Swierstra uses to model I/O interactions in Data Types à la Carte. For example, Swierstra models teletype I/O by a free monad generated from the following functor.

data Teletype a = GetChar (Char -> a) | PutChar Char a

The Teletype functor is isomorphic to PStore () Char + PStore Char (), thus is the sum of store functors. This means FreeMonad Teletype a is isomorphic to the van Laarhoven free monad type forall m. Monad m => TeletypeOps m -> m a where TeletypeOps is the following record type.

data TeletypeOps m = TeletypeOps { getChar :: m Char; putChar :: Char -> m () }

A value of type forall m. Monad m => TeletypeOps m -> m a can be interpreted in the standard way by passing in the record TeletypeOps Prelude.getChar Prelude.putChar :: TeletypeOps IO, but we are free to give other interpretations. For example, if we have a handle h :: Handle in our context then we can interpret our value by passing in the record TeletypeOps (Prelude.hGetChar h) (Prelude.hPutChar h) :: TeletypeOps IO. We could give a ‘pure’ interpretation to our value in order to use it in testing à la IOSpec library. We could give a console interpretation where we also log all inputs. We could give an interpretation where we replay logged inputs. The list of possibilities is endless.

The van Laarhoven free monad is a monad. Below is how one can implement it in Haskell. Try not to let the impredicativity hurt your head too much.

-- (ops m) is required to be isomorphic to (Π n. i_n -> m j_n)
newtype VLMonad ops a = VLMonad { runVLMonad :: forall m. Monad m => ops m -> m a }

return a = VLMonad (\_ -> return a)
m >>= f = VLMonad (\ops -> runVLMonad m ops >>= f' ops)
where
f' ops a = runVLMonad (f a) ops

Swierstra notes that by summing together functors representing primitive I/O actions and taking the free monad of that sum, we can produce values use multiple I/O feature sets. Values defined on a subset of features can be lifted into the free monad generated by the sum. The equivalent process can be performed with the van Laarhoven free monad by taking the product of records of the primitive operations. Values defined on a subset of features can be lifted by composing the van Laarhoven free monad with suitable projection functions that pick out the requisite primitive operations. No doubt someone will develop a library implementing a type class(y) hierarchy to make this process transparent, which may or may not be a good idea.

The van Laarhoven free monad provides yet another way of representing a monadic foreign function interface to Kmett’s list of representations. Now, I am not much for practical applications of theory, so I will leave it to others to determine how practical the van Laarhoven free monad representation is. I am optimistic it will be competitive with Kmett’s representation, and might even be cheaper.

# Joy and caution with -XNegativeLiterals in GHC 7.8

The new NegativeLiterals extension in GHC 7.8 scratches an itch I have had for a long time. Namely:

> y = (-41940.917505092) *~ kilo meter

With NegativeLiterals users of dimensional can finally write:

> y = -41940.917505092 *~ kilo meter

Thanks GHC HQ and contributors!

However, be careful so the extension doesn’t break your calculations. Here is an example (not using dimensional) of how you could get bitten. Without NegativeLiterals:

> Prelude> -2 ^ 2
> -4

With NegativeLiterals:

> Prelude> -2 ^ 2
> 4

I certainly prefer the latter behaviour, but having some regression tests in place when enabling NegativeLiterals might be a good idea.

# Numtype(-tf) and dimensional(-tf) updated for GHC 7.8.1

My numtype and numtype-tf libraries both needed one line changes to be compatible with the GHC 7.8.1 release candidate. Versions 1.1 and 0.1.2 (respectively) have been uploaded to hackage.

The update to numtype also necessitated an update to dimensional, mainly to bump the upper bounds of the numtype dependency, but a few API additions snuck in too. The change log for the new version (0.12.3), as well as the other versions that have been uploaded to hackage since my previous version announcement can be found at the bottom of this post.

Dimensional-tf didn’t need an update for GHC 7.8 but has been updated with the same API additions as dimensional.

# Dimensional’s changelog

## 0.13 (2014-02)

• Bump numtype dependency to 1.1 (GHC 7.8.1 compatibility fix).
• Added Torque.
• Added D.. for the type synonym quantities (e.g., Angle).

## 0.12.2 (2013-11)

• Added FirstMassMoment, MomentOfInertia, AngularMomentum.
• Improved unit numerics.

## 0.12.1 (2013-07)

• Typeable Dimensionals.

## 0.12 (2013-06)

• Polymorphic _0 (closes issue 39).
• Added astronomicalUnit.
• Added imperial volume units.
• Added ‘mil’ (=inch/1000).
• Added tau.
• Added KinematicViscosity.

## 0.10.1.2 (2011-09)

• Bumped time dependency to < 1.5.

## 0.10.1.2 (2011-08)

• Bumped time dependency to < 1.4.

## 0.10.1 (2011-08)

GHC 7.2.1 compatibility fix:

• Increased CGS context-stack to 30.

# Some ideas for pipes-parse

I haven't mentioned them before, but many times in the past, I've played around with from-scratch implementations of conduit to test out new theories. I've tried having versions without automatic termination of any sort, different orderings of finalizers, various different ways of handling leftovers, and strict adherence to the category laws. Each one of them has taught me something, but since the 1.0 release, none of them were enough of an improvement on what exists already to warrant the pain in switching. And frankly, most of them were far worse than what we already have.

A few days ago, Gabriel Gonzalez wrote a blog post about the newest release of pipes-parse. Given that we've had many conversations over the years- both publicly and privately- about the directions of our libraries, I wasn't surprised that the core idea behind this library is something we'd discussed once before, and in fact was an idea I'd even tried out for conduit once. Based on that experience, I'd like to share some ideas on how Gabriel (or others) could approach the problem a bit differently, and possibly avoid some user-facing issues.

## Proliferation of APIs

Before discussing the details of leftovers themselves, let mention what I consider the primary issue. It seems that each new feature added to pipes is introducing a completely separate API. Consider, for example, a simple question: how do you get the next value in a stream? In the conduit world, the answer is await. There are also some convenience functions built on top of await: awaitForever, peek, mapM_, etc. But there is just one primitive for awaiting values, and it has the same type everywhere:

await :: Monad m => Consumer i m (Maybe i)

In the pipes world, there are now (to my knowledge) three different "get the next value" primitives:

await :: Monad m => Consumer' a m a
next :: Monad m => Producer a m r -> m (Either r (a, Producer a m r))
draw :: Monad m => Parser a m (Maybe a)

This in turn means that utility functions need to be written multiple times, in different ways, depending on the context in which they're needed. For example, takeWhile in Pipes.Prelude works on a "normal" Pipe, but will silently discard one extra value from the stream since a normal Pipe does not support leftovers. span from Pipes.Parse performs essentially the same functionality, but works in the Parser/leftover aware realm.

One of the biggest changes to come to the conduit library was the unification of the Source, Sink, and Conduit datatypes into a single datatype, called Pipe. And the reason it's called Pipe is, as you might guess, because it was inspired from the pipes world (via Twan van Laarhoven). Though I was skeptical at first about the confusion in error messages and type signatures which may have ensued, the net result was, in my mind, undeniably positive.

It seems to me like pipes is now at that same kind of crossroads. There are a large number of different data types and type synonyms, different ways of composing things together, and different functionality depending on what type you're using. I'd recommend standardizing on one as the canonical entry point to pipes, and make the standard libraries all use that API.

It seems like the Parser API is the best suited for this task. Unless I'm mistaken, all of the folding functions in Pipes.Prelude (e.g., toList) can be implemented in terms of Parser, and it adds the capability of leftovers. If this change happened, then functions like takeWhile would no longer have to silently discard data from the data stream either.

Side note: you might think that conduit has lots of different kinds of composition due to the three different fusion operators, $=, =$, and =$=. In reality, they're all type-restricted aliases for the same function. The question of whether they should be type restricted at all is a good debate to have, but that's not my topic here. ## Overview of approaches With that more general comment out of the way, let's get into the details of Parser. Leftovers may seem like a really complicated concept, and (at least to me) lens-based parsing sounds pretty intimidating. However, the core concepts here are pretty trivial, and I think most people faced with the same constraints would end up with similar solutions to what the major streaming data libraries have. To motivate this, let's consider the simplest of all streaming data: pure lists. In our case, we'll store our "data producer" (i.e., a list) in a State monad. Getting another value from the stream (a.k.a., awaiting, drawing) means getting the list, popping an element off the top, putting back the smaller list, and returning the popped element. Putting a value back in the stream (a.k.a., undrawing, leftover) means getting the list, sticking an element at the beginning, and putting it back. This can all be embodied in very little Haskell code: import Control.Monad.Trans.State.Strict type Parser a r = State [a] r -- In conduit, this is await draw :: Parser a (Maybe a) draw = do list <- get case list of [] -> return Nothing x:xs -> do put xs return (Just x) -- In conduit, this is leftover unDraw :: a -> Parser a () unDraw a = do list <- get put$ a:list

At its core, this is what pipes-parse is doing. Instead of a pure list, it's using a Producer, which is really just a list transformer. But there's another, slightly less obvious approach that we could take instead. Right now, we're sticking leftovers right back on the same stack, making it impossible to distinguish between values taken from the original stream, and values leftover from the Parser. Instead, we could store a tuple in the State monad: the original list, and the leftovers. This is also pretty easy to code:

import Control.Monad.Trans.State.Strict

type Parser a r = State ([a], [a]) r

-- In conduit, this is await
draw :: Parser a (Maybe a)
draw = do
(list, leftovers) <- get
case leftovers of
x:leftovers' -> do
put (list, leftovers')
return (Just x)
[] ->
case list of
[] -> return Nothing
x:list' -> do
put (list', leftovers)
return (Just x)

-- In conduit, this is leftover
unDraw :: a -> Parser a ()
unDraw a = do
(list, leftovers) <- get
put (list, a:leftovers)

While this certainly works, it seems a little overkill: what possible benefit is there in having this separation? Well, it would allow us to distinguish between "completely unparsed values" and "parsed and leftovered" values. In our discussion so far, and in the documentation for pipes-parse, I see absolutely no reason why this feature would be relevant. However, let me introduce a non-trivial parsing example to motivate things a bit further.

## An archive file format

Let's say for some (probably bad) reason we've decided that the tar file format is unsuitable for our purposes. Instead, we've come up with a new file format that works as follows:

• Each file consists of a textual filename and binary contents.
• The filename will be UTF8 encoded.
• We will encode lengths using a variation on netstrings: the decimal representation of the length followed by a colon.
• Each file will be encoded as the length of the textual filename, its UTF-8 representation, the length of its binary contents, and the contents.

Yes, this example is ridiculous, but I wanted to find something that would demonstrate pipes-parse's ability to handle leftover preserving. To make the above description a bit easier to understand, here's the Haskell code to encode a list of these files:

data File = File
{ fileName     :: !Text
, fileContents :: !ByteString
}
deriving Show

encodeFile :: File -> Builder
encodeFile (File name contents) =
tellLen (T.length name) <>
fromByteString (TEE.encodeUtf8 name) <>
tellLen (S.length contents) <>
fromByteString contents
where
tellLen i = fromByteString $TEE.encodeUtf8$ T.pack $shows i ":" encodeFiles :: [File] -> Builder encodeFiles = mconcat . map encodeFile What's important for the parsing is that we will need to switch back and forth between a binary and a textual stream of data in order to handle this correctly. (Note: in reality, if for some terrible reason you decide to actually implement this format, you should encode the filename length using the byte count, not the character count. I specifically used the character count to force this awkward kind of stream switching.) I've implemented the parser in conduit if anyone's interested in checking it out. The magic leftover-preserving occurs in the withUtf8 function: withUtf8 :: MonadThrow m => ConduitM Text o m r -> ConduitM ByteString o m r withUtf8 = fuseLeftovers toBS (CT.decode CT.utf8) where toBS = L.toChunks . TLE.encodeUtf8 . TL.fromChunks We're saying to convert the stream to text assuming a UTF8 encoding. We'll generate chunks of text on demand (i.e., lazily), and will stop once we hit an invalid UTF8 sequence (that's the behavior of Data.Conduit.Text). Then, after downstream is done, collect all of the leftovers that it generated, and convert them back to their binary representation. Obviously, in order to do this, we need to be able to distinguish between the consumed upstream and the leftovers from downstream. If we cannot make that distinction, we'd be forced to encode the entire stream into text, take out the text that we need, and then convert the rest of the stream back to binary. Moreover, we'd have to perform the conversion back and forth for each time we call withUtf8. And even worse than the performance hit is the fact that it may not work: if the byte stream contains invalid UTF8 character sequences, this may break, depending on how your parser handles such invalid sequences. I'm fairly certain that pipes-parse falls prey to this issue. (If I've misunderstood the library, please correct me, and I'll include the correction here.) conduit handles the issue differently: the "parser" (a.k.a., Sink) has an explicit command for reporting leftovers, and it's up to the composition operator to decide how to handle the leftovers. The standard operators- $=, =$ and =$=- use a similar trick to pipes-parse, and stick the leftovers onto the upstream Source. And that's precisely why they have the behavior of discarding downstream leftovers. However, this is just a sensible default, not a requirement of conduit. It took me under five minutes to write an alternative composition function that had leftover preserving behavior instead.

### Simpler example

I tried to make the above example somewhat realistic, but the details may be a bit overwhelming. Instead, let's consider something much simpler: an isomorphism between two data types. We want to convert the stream from type A to type B, perform some peeking, and then deal with the rest of the stream. An example of doing this with conduit would be:

import           Control.Applicative ((<$>), (<*>)) import Data.Conduit (yield, ($$), (==)) import Data.Conduit.Extra (fuseLeftovers) import qualified Data.Conduit.List as CL import Debug.Trace (traceShow) newtype A = A Int deriving Show newtype B = B Int deriving Show atob (A i) = traceShow ("atob", i) (B i) btoa (B i) = traceShow ("btoa", i) (A i) main :: IO () main = do let src = mapM_ (yield . A) [1..10] res <- src$$ (,,,) <$> fuseLeftovers (map btoa) (CL.map atob) CL.peek
<*> CL.take 3
<*> (CL.map atob =$= CL.take 3) <*> CL.consume print res We have the numbers 1 through 10 as type A. In our Sink, we first convert the stream to type B, peek, and then return the leftovers upstream. Then we take three As, again convert to B and take three more elements, and finally consume the remainder of the stream. I've added trace statements to demonstrate exactly how many conversions are performed: ("atob",1) ("btoa",1) ("atob",4) ("atob",5) ("atob",6) (Just (B 1),[A 1,A 2,A 3],[B 4,B 5,B 6],[A 7,A 8,A 9,A 10]) The conversions that occur are the absolute bare minimum than could occur: the first element has to be converted to B in order to be peeked at, and then converted back to A to return to the original stream. Then, when we later take three more elements of type B, they obviously need to be converted. Let's look at the equivalent in pipes-parse, courtesy of Joseph Abrahamson: {-# LANGUAGE RankNTypes #-} import Control.Applicative import Control.Lens (Iso', from, iso, view, zoom) import Control.Monad.State.Strict (evalState) import Debug.Trace import Pipes import Pipes.Core as Pc import qualified Pipes.Parse as Pp import qualified Pipes.Prelude as P newtype A = A Int deriving Show newtype B = B Int deriving Show atob (A i) = traceShow ("atob", i) (B i) btoa (B i) = traceShow ("btoa", i) (A i) ab :: Iso' A B ab = iso atob btoa piso :: Monad m => Iso' a b -> Iso' (Producer a m r) (Producer b m r) piso i = iso (P.map (view i) <-<) (>-> P.map (view$ from i))

main :: IO ()
main = do
let src = P.map A <-< each [1..10]
let parser = (,,,) <$> zoom (piso ab) Pp.peek <*> zoom (Pp.splitAt 3) Pp.drawAll <*> zoom (Pp.splitAt 3 . piso ab) Pp.drawAll <*> Pp.drawAll let res = evalState parser src print res The result is the same, but look at the traces: ("atob",1) ("btoa",1) ("atob",2) ("btoa",2) ("atob",3) ("btoa",3) ("atob",4) ("btoa",4) ("atob",4) ("atob",5) ("btoa",5) ("atob",5) ("atob",6) ("btoa",6) ("atob",6) ("atob",7) ("btoa",7) ("atob",8) ("btoa",8) ("atob",9) ("btoa",9) ("atob",10) ("btoa",10) (Just (B 1),[A 1,A 2,A 3],[B 4,B 5,B 6],[A 7,A 8,A 9,A 10]) As described above, in pipes-parse you need to convert the entire stream. In our example, the conversion is trivial, and therefore not too worrying. But in the case of either an expensive conversion, or a possibly-failing conversion, this behavior would be incredibly problematic. UPDATE: Davorak on Reddit helped me come up with a better example which demonstrates not just doubled encoding, but a program not completing correctly. The conduit/pipes comparison code is available as a Gist. So my second recommendation would be to tweak Parser to have a stack of leftovers in addition to a Producer, which would allow for more powerful leftover preserving ## Drop lenses If you take the two recommendations above, you'll end up with a large collection of pipes-parse-ready functions, like take and takeWhile. And each of these functions will maintain a stack of leftovers, either to be used by the next monadically-composed Parser, or to perhaps propagate upstream. At this point, the lens-based approach to leftovers is overkill. The problem with the lens approach is twofold. Firstly, it's difficult for people to understand. The core concept is not complex, but the machinery around it obscures its simplicity. But more importantly, it does not seem to compose well. I don't mean that in the sense of lens or function composition: clearly those work as expected. What I mean is that you won't be able to take the existing utility functions I mentioned above and automatically use them in a leftover-propagating manner. I'd recommend borrowing from the conduit solution here directly: just have a separate composition function or operator that returns the downstream leftovers. It's a simple concept, it's easy to show in a type signature, and it's easy to build more complex solutions on top of it. I'll even argue that Gabriel's announcement post is in line with this recommendation: as pointed out, the lens laws are being bent by pipes-parse. If there's a separate solution that requires no law bending, why not use that? Let me be clear: I'm not at all implying that lenses themselves are the problem here. I think the problem is treating leftover propagation as an isomorphism between two producers. I think lenses can actually play very nicely with a streaming data package. I've been working on some conduit data analysis libraries that make heavy usage of lens to let users write much simpler code (things like filterField stockDate (< today)). So to reiterate my third recommendation: provide a composition operator for dealing with leftovers explicitly, let users reuse your existing library of functions, and don't force them to try to write isomorphisms on entire streams where a simple predicate function will suffice. I hope these ideas come across the right way: ideas that I think would improve the pipes ecosystem. These ideas should be taken with a large grain of salt. They are strongly inspired by my experience with conduit, and with the kinds of work I tend to see conduit applied to. ### Disciple/DDC # Bidirectional type inference for DDC DDC now includes a bidirectional type inferencer based on Joshua Dunfield and Neelakantan Krishnaswami's recent ICFP paper "Complete and Easy Bidirectional Type Checking for Higher-Rank Polymorphism". I've extended the base algorithm to infer the kinds of type parameters, as well as to automatically insert type abstractions and applications into the result. ### Type inference for Disciple Source Tetra With both the type inferencer and new coeffect system now working, Disciple source programs are looking significantly less offensive. For example, some simple list functions: data List (a : Data) where Nil : List a Cons : a -> List a -> List asingleton (x : a) : List a = Cons x Nilappend (xx : List a) (yy : List a) : List a = case xx of Nil -> yy Cons x xs -> Cons x (append xs yy)mapS [a b : Data] [e : Effect] (f : a -> S e b) (xx : List a) : S e (List b) = box case xx of Nil -> Nil Cons x xs -> Cons (run f x) (run mapS f xs) etc. etc. The above 'mapS' function is the version using the coeffect system I described in my last post. Using effects currently requires the user to add explicit 'box' and 'run' casts, though these will be automatically inserted in the next DDC release. The DDC command-line interface allows one to apply the type inferencer to such a source file, producing a core file with explicit type annotations, like so: $ bin/ddc -infer -load demo/Tetra/Lists/Lists.dst...module Lists data List (a : Data) where {        Nil : List a;        Cons : a -> List a -> List a;}withletrec {  singleton : [a : Data].a -> List a    = /\(a : Data).       \(x : a).      Cons [a] x (Nil [a]);    append : [a : Data].List a -> List a -> List a    = /\(a : Data).       \(xx yy : List a).      case xx of {        Nil           -> yy;        Cons (x : a) (xs : List a)          -> Cons [a] x (append [a] xs yy)      };  mapS : [a b : Data].[e : Effect].(a -> S e b) -> List a -> S e (List b)    = /\(a b : Data)./\(e : Effect).       \(f : a -> S e b).\(xx : List a).      box      case xx of {        Nil           -> Nil [b];        Cons (x : a) (xs : List a)          -> Cons [b]                (run f x)                (run mapS [a] [b] [e] f xs)      }}...
Such a file can then be converted to C or LLVM for compilation to object code. In the current implementation higher-order programs will type-check, but cannot be compiled all the way to object code. I need to finish the runtime support for that.

### Type inference for Disciple Core Salt

In practical terms, work on the runtime system is already being helped by the new type inferencer. The DDC runtime is written in a first-order imperative fragment named 'Disciple Core Salt', which compiled with DDC itself. Here is the code that allocates a boxed heap object on a 64-bit platform:
allocBoxed        [r : Region] (tag : Tag#) (arity : Nat#) : Ptr# r Obj = do           -- Multiple arity by 8 bytes-per-pointer to get size of payload.        bytesPayload    = shl# arity (size2# [Addr#])        bytesObj        = add# (size# [Word32#])                         (add# (size# [Word32#]) bytesPayload)        -- Check there is enough space on the heap.        case check# bytesObj of         True#  -> allocBoxed_ok tag arity bytesObj         False# -> fail#allocBoxed_ok        [r : Region] (tag : Tag#) (arity : Nat#) (bytesObj : Nat#) : Ptr# r Obj = do           addr            = alloc# bytesObj        tag32           = promote# [Word32#] [Tag#] tag        format          = 0b00100001w32#        header          = bor# (shl# tag32 8w32#) format        write# addr 0# header        -- Truncate arity to 32-bits.        arity32         = truncate# [Word32#] [Nat#] arity        write# addr 4# arity32        makePtr# addr
Some type annotations are still required to specify data formats and the like, but all the day-to-day annotations can be inferred.
bin/ddc -infer -load packages/ddc-code/salt/runtime64/Object.dcs[slightly reformatted]...allocBoxed : [r : Region].Tag# -> Nat# -> Ptr# r Obj = /\(r : Region). \(tag : Tag#).\(arity : Nat#). let bytesPayload : Nat# = shl# [Nat#] arity (size2# [Addr#]) in let bytesObj : Nat# = add# [Nat#] (size# [Word32#]) (add# [Nat#] (size# [Word32#]) bytesPayload) in case check# bytesObj of { True# -> allocBoxed_ok [r] tag arity bytesObj; False# -> fail# [Ptr# r Obj] }; allocBoxed_ok : [r : Region].Tag# -> Nat# -> Nat# -> Ptr# r Obj = /\(r : Region). \(tag : Tag#).\(arity bytesObj : Nat#). let addr : Addr# = alloc# bytesObj in let tag32 : Word32# = promote# [Word32#] [Tag#] tag in let format : Word32# = 33w32# in let header : Word32# = bor# [Word32#] (shl# [Word32#] tag32 8w32#) format in let _ : Void# = write# [Word32#] addr 0# header in let arity32 : Word32# = truncate# [Word32#] [Nat#] arity in let _ : Void# = write# [Word32#] addr 4# arity32 in makePtr# [r] [Obj] addr;... ### Upcoming 0.4 Release There are still some bugs to fix before I can enable type inference by default, but when that is done I will release DDC 0.4, which I'm hoping to get done by the end of the month. ## February 10, 2014 ### Dominic Steinitz # Laplace’s Equation in Haskell: Using a DSL for Stencils # Introduction Suppose we have a square thin plate of metal and we hold each of edges at a temperature which may vary along the edge but is fixed for all time. After some period depending on the conductivity of the metal, the temperature at every point on the plate will have stabilised. What is the temperature at any point? We can calculate this using by solving Laplace’s equation $\nabla^2 \phi = 0$ in 2 dimensions. Apart from the preceeding motivation, a more compelling reason for doing so is that it is a moderately simple equation, in so far as partial differential equations are simple, that has been well studied for centuries. In Haskell terms this gives us the opportunity to use the repa library and use hmatrix which is based on Lapack (as well as other libraries) albeit hmatrix only for illustratative purposes. I had originally intended this blog to contain a comparison repa’s performance against an equivalent C program even though this has already been undertaken by the repa team in their various publications. And indeed it is still my intention to produce such a comparision. However, as I investigated further, it turned out a fair amount of comparison work has already been done by a team from Intel which suggests there is currently a performance gap but one which is not so large that it outweighs the other benefits of Haskell. To be more specific, one way in which using repa stands out from the equivalent C implementation is that it gives a language in which we can specify the stencil being used to solve the equation. As an illustration we substitute the nine point method for the five point method merely by changing the stencil. ## A Motivating Example: The Steady State Heat Equation Fourier’s law states that the rate of heat transfer or the flux $\boldsymbol{\sigma}$ is proportional to the negative temperature gradient, as heat flows from hot to cold, and further that it flows in the direction of greatest temperature change. We can write this as $\displaystyle \boldsymbol{\sigma} = -k\nabla \phi$ where $\phi : \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}$ is the temperature at any given point on the plate and $k$ is the conductivity of the metal. Moreover, we know that for any region on the plate, the total amount of heat flowing in must be balanced by the amount of heat flowing out. We can write this as $\displaystyle \nabla \cdot \boldsymbol{\sigma} = 0$ Substituting the first equation into the second we obtain Laplace’s equation $\displaystyle \nabla^2 \phi = 0$ For example, suppose we hold the temperature of the edges of the plate as follows $\displaystyle \begin{matrix} \phi(x, 0) = 1 & \phi(x, 1) = 2 & \phi(0, y) = 1 & \phi(1, y) = 2 \end{matrix}$ then after some time the temperature of the plate will be as shown in the heatmap below. Notes: 1. Red is hot. 2. Blue is cold. 3. The heatmap is created by a finite difference method described below. 4. The $y$-axis points down (not up) i.e. $\phi(x,1)$ is at the bottom, reflecting the fact that we are using an array in the finite difference method and rows go down not up. 5. The corners are grey because in the five point finite difference method these play no part in determining temperatures in the interior of the plate. # Colophon Since the book I am writing contains C code (for performance comparisons), I need a way of being able to compile and run this code and include it “as is” in the book. Up until now, all my blog posts have contained Haskell and so I have been able to use BlogLiteratelyD which allows me to include really nice diagrams. But clearly this tool wasn’t really designed to handle other languages (although I am sure it could be made to do so). Using pandoc’s scripting capability with the small script provided #!/usr/bin/env runhaskell import Text.Pandoc.JSON doInclude :: Block -> IO Block doInclude cb@(CodeBlock ("verbatim", classes, namevals) contents) = case lookup "include" namevals of Just f -> return . (\x -> Para [Math DisplayMath x]) =<< readFile f Nothing -> return cb doInclude cb@(CodeBlock (id, classes, namevals) contents) = case lookup "include" namevals of Just f -> return . (CodeBlock (id, classes, namevals)) =<< readFile f Nothing -> return cb doInclude x = return x main :: IO () main = toJSONFilter doInclude I can then include C code blocks like this ~~~~ {.c include="Chap1a.c"} ~~~~ And format the whole document like this pandoc -s Chap1.lhs --filter=./Include -t markdown+lhs > Chap1Expanded.lhs BlogLiteratelyD Chap1Expanded.lhs > Chap1.html Sadly, the C doesn’t get syntax highlighting but this will do for now. PS Sadly, WordPress doesn’t seem to be able to handle \color{red} and \color{blue} in LaTeX so there are some references to blue and red which do not render. # Acknowledgements A lot of the code for this post is taken from the repa package itself. Many thanks to the repa team for providing the package and the example code. # Haskell Preamble > {-# OPTIONS_GHC -Wall #-} > {-# OPTIONS_GHC -fno-warn-name-shadowing #-} > {-# OPTIONS_GHC -fno-warn-type-defaults #-} > {-# OPTIONS_GHC -fno-warn-unused-do-bind #-} > {-# OPTIONS_GHC -fno-warn-missing-methods #-} > {-# OPTIONS_GHC -fno-warn-orphans #-}  > {-# LANGUAGE BangPatterns #-} > {-# LANGUAGE TemplateHaskell #-} > {-# LANGUAGE QuasiQuotes #-} > {-# LANGUAGE NoMonomorphismRestriction #-}  > module Chap1 ( > module Control.Applicative > , solveLaplaceStencil > , useBool > , boundMask > , boundValue > , bndFnEg1 > , fivePoint > , ninePoint > , testStencil5 > , testStencil9 > , analyticValue > , slnHMat4 > , slnHMat5 > , testJacobi4 > , testJacobi6 > , bndFnEg3 > , runSolver > , s5 > , s9 > ) where > > import Data.Array.Repa as R > import Data.Array.Repa.Unsafe as R > import Data.Array.Repa.Stencil as A > import Data.Array.Repa.Stencil.Dim2 as A  > import Prelude as P  > import Data.Packed.Matrix > import Numeric.LinearAlgebra.Algorithms  > import Chap1Aux  > import Control.Applicative  # Laplace’s Equation: The Five Point Formula We show how to apply finite difference methods to Laplace’s equation: $\displaystyle \nabla^2 u = 0$ where $\displaystyle \nabla^2 = \frac{\partial^2}{\partial x^2} +\frac{\partial^2}{\partial y^2}$ For a sufficiently smooth function (see (Iserles 2009, chap. 8)) we have \displaystyle \begin{aligned} \frac{\partial^2 u}{\partial x^2}\mathop{\Bigg|_{x = x_0 + k\Delta x}}_{y = y_0 + l\Delta x} &= \frac{1}{(\Delta x)^2}\Delta_{0,x}^2 u_{k,l} + \mathcal{O}((\Delta x)^2) \\ \frac{\partial^2 u}{\partial y^2}\mathop{\Bigg|_{x = x_0 + k\Delta x}}_{y = y_0 + l\Delta x} &= \frac{1}{(\Delta x)^2}\Delta_{0,y}^2 u_{k,l} + \mathcal{O}((\Delta x)^2) \end{aligned} where the central difference operator $\Delta_0$ is defined as $\displaystyle (\Delta_0 z)_k \triangleq z_{k + \frac{1}{2}} - z_{k - \frac{1}{2}}$ We are therefore led to consider the five point difference scheme. $\displaystyle \frac{1}{(\Delta x)^2}(\Delta_{0,x}^2 + \Delta_{0,y}^2) u_{k,l} = 0$ We can re-write this explicitly as $\displaystyle u_{k-1,l} + u_{k+1,l} + u_{k,l-1} + u_{k,l+1} - 4u_{k,l} = 0$ Specifically for the grid point (2,1) in a $4 \times 4$ grid we have $\displaystyle {{u_{1,1}}} + {{u_{3,1}}} + {{u_{2,0}}} + {{u_{2,2}}} - 4{{u_{2,1}}} = 0$ where blue indicates that the point is an interior point and red indicates that the point is a boundary point. For Dirichlet boundary conditions (which is all we consider in this post), the values at the boundary points are known. We can write the entire set of equations for this grid as $\displaystyle \begin{bmatrix} -4.0 & 1.0 & 1.0 & 0.0 \\ 1.0 & -4.0 & 0.0 & 1.0 \\ 1.0 & 0.0 & -4.0 & 1.0 \\ 0.0 & 1.0 & 1.0 & -4.0 \end{bmatrix} \begin{bmatrix} {{u_{11}}} \\ {{u_{21}}} \\ {{u_{12}}} \\ {{u_{22}}} \end{bmatrix} = \begin{bmatrix} -{{u_{10}}} + -{{u_{01}}} \\ -{{u_{20}}} + -{{u_{31}}} \\ -{{u_{02}}} + -{{u_{13}}} \\ -{{u_{23}}} + -{{u_{32}}} \end{bmatrix}$ ## A Very Simple Example Let us take the boundary conditions to be $\displaystyle \begin{matrix} u(x, 0) = 1 & u(x, 1) = 2 & u(0, y) = 1 & u(1, y) = 2 \end{matrix}$ With our $4 \times 4$ grid we can solve this exactly using the hmatrix package which has a binding to LAPACK. First we create a $4 \times 4$ matrix in hmatrix form > simpleEgN :: Int > simpleEgN = 4 - 1 > > matHMat4 :: IO (Matrix Double) > matHMat4 = do > matRepa <- computeP mkJacobiMat simpleEgN :: IO (Array U DIM2 Double)
>   return $(simpleEgN - 1) >< (simpleEgN - 1)$ toList matRepa

ghci> matHMat4
(2><2)
[ -4.0, 1.0
,  1.0, 0.0 ]


Next we create the column vector as presribed by the boundary conditions

> bndFnEg1 :: Int -> Int -> (Int, Int) -> Double
> bndFnEg1 _ m (0, j) |           j > 0 && j < m = 1.0
> bndFnEg1 n m (i, j) | i == n && j > 0 && j < m = 2.0
> bndFnEg1 n _ (i, 0) |           i > 0 && i < n = 1.0
> bndFnEg1 n m (i, j) | j == m && i > 0 && i < n = 2.0
> bndFnEg1 _ _ _                                 = 0.0

> bnd1 :: Int -> [(Int, Int)] -> Double
> bnd1 n = negate .
>          sum .
>          P.map (bndFnEg1 n n)

> bndHMat4 :: Matrix Double
> bndHMat4 = ((simpleEgN - 1) * (simpleEgN - 1)) >< 1 $> mkJacobiBnd fromIntegral bnd1 3  ghci> bndHMat4 (4><1) [ -2.0 , -3.0 , -3.0 , -4.0 ]  > slnHMat4 :: IO (Matrix Double) > slnHMat4 = matHMat4 >>= return . flip linearSolve bndHMat4  ghci> slnHMat4 (4><1) [ 1.25 , 1.5 , 1.4999999999999998 , 1.7499999999999998 ]  # The Jacobi Method Inverting a matrix is expensive so instead we use the (possibly most) classical of all iterative methods, Jacobi iteration. Given $A\boldsymbol{x} = \boldsymbol{b}$ and an estimated solution $\boldsymbol{x}_i^{[k]}$, we can generate an improved estimate $\boldsymbol{x}_i^{[k+1]}$. See (Iserles 2009, chap. 12) for the details on convergence and convergence rates. $\displaystyle \boldsymbol{x}_i^{[k+1]} = \frac{1}{A_{i,i}}\Bigg[\boldsymbol{b}_i - \sum_{j \neq i} A_{i,j}\boldsymbol{x}_j^{[k]}\Bigg]$ The simple example above does not really give a clear picture of what happens in general during the update of the estimate. Here is a larger example Sadly, WordPress does not seem to be able to render $16 \times 16$ matrices written in LaTeX so you will have to look at the output from hmatrix in the larger example below. You can see that this matrix is sparse and has a very clear pattern. Expanding the matrix equation for a ${\text{point}}$ not in the ${\text{boundary}}$ we get $\displaystyle x_{i,j}^{[k+1]} = \frac{1}{4}(x^{[k]}_{i-1,j} + x^{[k]}_{i,j-1} + x^{[k]}_{i+1,j} + x^{[k]}_{i,j+1})$ Cleary the values of the points in the boundary are fixed and must remain at those values for every iteration. Here is the method using repa. To produce an improved estimate, we define a function relaxLaplace and we pass in a repa matrix representing our original estimate $\boldsymbol{x}_i^{[k]}$ and receive the one step update $\boldsymbol{x}_i^{[k+1]}$ also as a repa matrix. We pass in a boundary condition mask which specifies which points are boundary points; a point is a boundary point if its value is 1.0 and not if its value is 0.0. > boundMask :: Monad m => Int -> Int -> m (Array U DIM2 Double) > boundMask gridSizeX gridSizeY = computeP$
>                                 fromFunction (Z :. gridSizeX + 1 :. gridSizeY + 1) f
>   where
>     f (Z :. _ix :.  iy) | iy == 0         = 0
>     f (Z :. _ix :.  iy) | iy == gridSizeY = 0
>     f (Z :.  ix :. _iy) | ix == 0         = 0
>     f (Z :.  ix :. _iy) | ix == gridSizeX = 0
>     f _                                   = 1


Better would be to use at least a Bool as the example below shows but we wish to modify the code from the repa git repo as little as possible.

> useBool :: IO (Array U DIM1 Double)
> useBool = computeP $> R.map (fromIntegral . fromEnum)$
>           fromFunction (Z :. (3 :: Int)) (const True)

ghci> useBool
AUnboxed (Z :. 3) (fromList [1.0,1.0,1.0])


We further pass in the boundary conditions. We construct these by using a function which takes the grid size in the $x$ direction, the grid size in the $y$ direction and a given pair of co-ordinates in the grid and returns a value at this position.

> boundValue :: Monad m =>
>               Int ->
>               Int ->
>               (Int -> Int -> (Int, Int) -> Double) ->
>               m (Array U DIM2 Double)
> boundValue gridSizeX gridSizeY bndFn =
>   computeP $> fromFunction (Z :. gridSizeX + 1 :. gridSizeY + 1) g > where > g (Z :. ix :. iy) = bndFn gridSizeX gridSizeY (ix, iy)  Note that we only update an element in the repa matrix representation of the vector if it is not on the boundary. > relaxLaplace > :: Monad m > => Array U DIM2 Double > -> Array U DIM2 Double > -> Array U DIM2 Double > -> m (Array U DIM2 Double) > > relaxLaplace arrBoundMask arrBoundValue arr > = computeP >$ R.zipWith (+) arrBoundValue
>     $R.zipWith (*) arrBoundMask >$ unsafeTraverse arr id elemFn
>   where
>     _ :. height :. width
>       = extent arr
>
>     elemFn !get !d@(sh :. i :. j)
>       = if isBorder i j
>         then  get d
>         else (get (sh :. (i-1) :. j)
>               +   get (sh :. i     :. (j-1))
>               +   get (sh :. (i+1) :. j)
>               +   get (sh :. i     :. (j+1))) / 4
>     isBorder !i !j
>       =  (i == 0) || (i >= width  - 1)
>          || (j == 0) || (j >= height - 1)


We can use this to iterate as many times as we like.

> solveLaplace
>   :: Monad m
>         => Int
>         -> Array U DIM2 Double
>         -> Array U DIM2 Double
>         -> Array U DIM2 Double
>         -> m (Array U DIM2 Double)
>
> solveLaplace steps arrBoundMask arrBoundValue arrInit
>  = go steps arrInit
>   where
>     go !i !arr
>       | i == 0
>       = return     arr
>
>       | otherwise
>       = do arr' <- relaxLaplace arrBoundMask arrBoundValue arr
>            go (i - 1) arr'


For our small example, we set the initial array to $0$ at every point. Note that the function which updates the grid, relaxLaplace will immediately over-write the points on the boundary with values given by the boundary condition.

> mkInitArrM :: Monad m => Int -> m (Array U DIM2 Double)
> mkInitArrM n = computeP $fromFunction (Z :. (n + 1) :. (n + 1)) (const 0.0)  We can now test the Jacobi method > testJacobi4 :: Int -> IO (Array U DIM2 Double) > testJacobi4 nIter = do > mask <- boundMask simpleEgN simpleEgN > val <- boundValue simpleEgN simpleEgN bndFnEg1 > initArr <- mkInitArrM simpleEgN > solveLaplace nIter mask val initArr  After 55 iterations, we obtain convergence up to the limit of accuracy of double precision floating point numbers. Note this only provides a solution of the matrix equation which is an approximation to Laplace’s equation. To obtain a more accurate result for the latter we need to use a smaller grid size. ghci> testJacobi4 55 >>= return . pPrint [0.0, 1.0, 1.0, 0.0] [1.0, 1.25, 1.5, 2.0] [1.0, 1.5, 1.75, 2.0] [0.0, 2.0, 2.0, 0.0]  ## A Larger Example Armed with Jacobi, let us now solve a large example. > largerEgN, largerEgN2 :: Int > largerEgN = 6 - 1 > largerEgN2 = (largerEgN - 1) * (largerEgN - 1)  First let us use hmatrix. > matHMat5 :: IO (Matrix Double) > matHMat5 = do > matRepa <- computeP$ mkJacobiMat largerEgN :: IO (Array U DIM2 Double)
>   return $largerEgN2 >< largerEgN2$ toList matRepa

ghci> matHMat5
(16><16)
[ -4.0,  1.0,  0.0,  0.0,  1.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0
,  1.0, -4.0,  1.0,  0.0,  0.0,  1.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0
,  0.0,  1.0, -4.0,  1.0,  0.0,  0.0,  1.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0
,  0.0,  0.0,  1.0, -4.0,  0.0,  0.0,  0.0,  1.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0
,  1.0,  0.0,  0.0,  0.0, -4.0,  1.0,  0.0,  0.0,  1.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0
,  0.0,  1.0,  0.0,  0.0,  1.0, -4.0,  1.0,  0.0,  0.0,  1.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0
,  0.0,  0.0,  1.0,  0.0,  0.0,  1.0, -4.0,  1.0,  0.0,  0.0,  1.0,  0.0,  0.0,  0.0,  0.0,  0.0
,  0.0,  0.0,  0.0,  1.0,  0.0,  0.0,  1.0, -4.0,  0.0,  0.0,  0.0,  1.0,  0.0,  0.0,  0.0,  0.0
,  0.0,  0.0,  0.0,  0.0,  1.0,  0.0,  0.0,  0.0, -4.0,  1.0,  0.0,  0.0,  1.0,  0.0,  0.0,  0.0
,  0.0,  0.0,  0.0,  0.0,  0.0,  1.0,  0.0,  0.0,  1.0, -4.0,  1.0,  0.0,  0.0,  1.0,  0.0,  0.0
,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  1.0,  0.0,  0.0,  1.0, -4.0,  1.0,  0.0,  0.0,  1.0,  0.0
,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  1.0,  0.0,  0.0,  1.0, -4.0,  0.0,  0.0,  0.0,  1.0
,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  1.0,  0.0,  0.0,  0.0, -4.0,  1.0,  0.0,  0.0
,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  1.0,  0.0,  0.0,  1.0, -4.0,  1.0,  0.0
,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  1.0,  0.0,  0.0,  1.0, -4.0,  1.0
,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  0.0,  1.0,  0.0,  0.0,  1.0, -4.0 ]

> bndHMat5 :: Matrix Double
> bndHMat5 = largerEgN2>< 1 $mkJacobiBnd fromIntegral bnd1 5  ghci> bndHMat5 (16><1) [ -2.0 , -1.0 , -1.0 , -3.0 , -1.0 , 0.0 , 0.0 , -2.0 , -1.0 , 0.0 , 0.0 , -2.0 , -3.0 , -2.0 , -2.0 , -4.0 ]  > slnHMat5 :: IO (Matrix Double) > slnHMat5 = matHMat5 >>= return . flip linearSolve bndHMat5  ghci> slnHMat5 (16><1) [ 1.0909090909090908 , 1.1818181818181817 , 1.2954545454545454 , 1.5 , 1.1818181818181817 , 1.3409090909090906 , 1.4999999999999996 , 1.7045454545454544 , 1.2954545454545459 , 1.5 , 1.6590909090909092 , 1.818181818181818 , 1.5000000000000004 , 1.7045454545454548 , 1.8181818181818186 , 1.9090909090909092 ]  And for comparison, let us use the Jacobi method. > testJacobi6 :: Int -> IO (Array U DIM2 Double) > testJacobi6 nIter = do > mask <- boundMask largerEgN largerEgN > val <- boundValue largerEgN largerEgN bndFnEg1 > initArr <- mkInitArrM largerEgN > solveLaplace nIter mask val initArr  ghci> testJacobi6 178 >>= return . pPrint [0.0, 1.0, 1.0, 1.0, 1.0, 0.0] [1.0, 1.0909090909090908, 1.1818181818181817, 1.2954545454545454, 1.5, 2.0] [1.0, 1.1818181818181817, 1.3409090909090908, 1.5, 1.7045454545454546, 2.0] [1.0, 1.2954545454545454, 1.5, 1.6590909090909092, 1.8181818181818183, 2.0] [1.0, 1.5, 1.7045454545454546, 1.8181818181818181, 1.9090909090909092, 2.0] [0.0, 2.0, 2.0, 2.0, 2.0, 0.0]  Note that with a larger grid we need more points (178) before the Jacobi method converges. # Stencils Since we are functional programmers, our natural inclination is to see if we can find an abstraction for (at least some) numerical methods. We notice that we are updating each grid element (except the boundary elements) by taking the North, East, South and West surrounding squares and calculating a linear combination of these. Repa provides this abstraction and we can describe the update calculation as a stencil. (Lippmeier and Keller 2011) gives full details of stencils in repa. > fivePoint :: Stencil DIM2 Double > fivePoint = [stencil2| 0 1 0 > 1 0 1 > 0 1 0 |]  Using stencils allows us to modify our numerical method with a very simple change. For example, suppose we wish to use the nine point method (which is $\mathcal{O}((\Delta x)^4)$!) then we only need write down the stencil for it which is additionally a linear combination of North West, North East, South East and South West. > ninePoint :: Stencil DIM2 Double > ninePoint = [stencil2| 1 4 1 > 4 0 4 > 1 4 1 |]  We modify our solver above to take a stencil and also an Int which is used to normalise the factors in the stencil. For example, in the five point method this is 4. > solveLaplaceStencil :: Monad m > => Int > -> Stencil DIM2 Double > -> Int > -> Array U DIM2 Double > -> Array U DIM2 Double > -> Array U DIM2 Double > -> m (Array U DIM2 Double) > solveLaplaceStencil !steps !st !nF !arrBoundMask !arrBoundValue !arrInit > = go steps arrInit > where > go 0 !arr = return arr > go n !arr > = do arr' <- relaxLaplace arr > go (n - 1) arr' > > relaxLaplace arr > = computeP >$ R.szipWith (+) arrBoundValue
>      $R.szipWith (*) arrBoundMask >$ R.smap (/ (fromIntegral nF))
>      mapStencil2 (BoundConst 0) > st arr  We can then test both methods. > testStencil5 :: Int -> Int -> IO (Array U DIM2 Double) > testStencil5 gridSize nIter = do > mask <- boundMask gridSize gridSize > val <- boundValue gridSize gridSize bndFnEg1 > initArr <- mkInitArrM gridSize > solveLaplaceStencil nIter fivePoint 4 mask val initArr  ghci> testStencil5 5 178 >>= return . pPrint [0.0, 1.0, 1.0, 1.0, 1.0, 0.0] [1.0, 1.0909090909090908, 1.1818181818181817, 1.2954545454545454, 1.5, 2.0] [1.0, 1.1818181818181817, 1.3409090909090908, 1.5, 1.7045454545454546, 2.0] [1.0, 1.2954545454545454, 1.5, 1.6590909090909092, 1.8181818181818183, 2.0] [1.0, 1.5, 1.7045454545454546, 1.8181818181818181, 1.9090909090909092, 2.0] [0.0, 2.0, 2.0, 2.0, 2.0, 0.0]  > testStencil9 :: Int -> Int -> IO (Array U DIM2 Double) > testStencil9 gridSize nIter = do > mask <- boundMask gridSize gridSize > val <- boundValue gridSize gridSize bndFnEg1 > initArr <- mkInitArrM gridSize > solveLaplaceStencil nIter ninePoint 20 mask val initArr  ghci> testStencil9 5 178 >>= return . pPrint [0.0, 1.0, 1.0, 1.0, 1.0, 0.0] [1.0, 1.0222650172207302, 1.1436086139049304, 1.2495750646811328, 1.4069077172153264, 2.0] [1.0, 1.1436086139049304, 1.2964314331751594, 1.4554776038855908, 1.6710941204241017, 2.0] [1.0, 1.2495750646811328, 1.455477603885591, 1.614523774596022, 1.777060571200304, 2.0] [1.0, 1.4069077172153264, 1.671094120424102, 1.777060571200304, 1.7915504172099226, 2.0] [0.0, 2.0, 2.0, 2.0, 2.0, 0.0]  We note that the methods give different answers. Before explaining this, let us examine one more example where the exact solution is known. We take the example from (Iserles 2009, chap. 8) where the boundary conditions are: \displaystyle \begin{aligned} \phi(x, 0) &= 0 \\ \phi(x, 1) &= \frac{1}{(1 + x)^2 + 1} \\ \phi(0, y) &= \frac{y}{1 + y^2} \\ \phi(1, y) &= \frac{y}{4 + y^2} \end{aligned} This has the exact solution $\displaystyle u(x, y) = \frac{y}{(1 + x)^2 + y^2}$ And we can calculate the values of this function on a grid. > analyticValue :: Monad m => Int -> m (Array U DIM2 Double) > analyticValue gridSize = computeP fromFunction (Z :. gridSize + 1 :. gridSize + 1) f
>   where
>     f (Z :. ix :. iy) = y / ((1 + x)^2 + y^2)
>       where
>         y = fromIntegral iy / fromIntegral gridSize
>         x = fromIntegral ix / fromIntegral gridSize


Let us also solve it using the Jacobi method with a five point stencil and a nine point stencil. Here is the encoding of the boundary values.

> bndFnEg3 :: Int -> Int -> (Int, Int) -> Double
> bndFnEg3 _ m (0, j) |           j >= 0 && j <  m = y / (1 + y^2)
>   where y = (fromIntegral j) / (fromIntegral m)
> bndFnEg3 n m (i, j) | i == n && j >  0 && j <= m = y / (4 + y^2)
>   where y = fromIntegral j / fromIntegral m
> bndFnEg3 n _ (i, 0) |           i >  0 && i <= n = 0.0
> bndFnEg3 n m (i, j) | j == m && i >= 0 && i <  n = 1 / ((1 + x)^2 + 1)
>   where x = fromIntegral i / fromIntegral n
> bndFnEg3 _ _ _                                   = 0.0


We create a function to run a solver.

> runSolver ::
>   Monad m =>
>   Int ->
>   Int ->
>   (Int -> Int -> (Int, Int) -> Double) ->
>   (Int ->
>    Array U DIM2 Double ->
>    Array U DIM2 Double ->
>    Array U DIM2 Double ->
>    m (Array U DIM2 Double)) ->
>   m (Array U DIM2 Double)
> runSolver nGrid nIter boundaryFn solver = do
>   val     <- boundValue nGrid nGrid boundaryFn
>   initArr <- mkInitArrM nGrid
>   solver nIter mask val initArr


And put the five point and nine point solvers in the appropriate form.

> s5, s9 :: Monad m =>
>           Int ->
>           Array U DIM2 Double ->
>           Array U DIM2 Double ->
>           Array U DIM2 Double ->
>           m (Array U DIM2 Double)
> s5 n = solveLaplaceStencil n fivePoint 4
> s9 n = solveLaplaceStencil n ninePoint 20


And now we can see that the errors between the analytic solution and the five point method with a grid size of 8 are $\cal{O}(10^{-4})$.

ghci> liftA2 (-^) (analyticValue 7) (runSolver 7 200 bndFnEg3 s5) >>= return . pPrint
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
[0.0, -3.659746856576884e-4, -5.792613003869074e-4, -5.919333582729558e-4, -4.617020226472812e-4, -2.7983716661839075e-4, -1.1394184484148084e-4, 0.0]
[0.0, -4.0566163490589335e-4, -6.681826442424543e-4, -7.270498771604073e-4, -6.163531890425178e-4, -4.157604876017795e-4, -1.9717865146007263e-4, 0.0]
[0.0, -3.4678314565880775e-4, -5.873627029994999e-4, -6.676042377350699e-4, -5.987527967581119e-4, -4.318102416048242e-4, -2.2116263241278578e-4, 0.0]
[0.0, -2.635436147627873e-4, -4.55055831294085e-4, -5.329636937312088e-4, -4.965786933938399e-4, -3.7401874422060555e-4, -2.0043638973538114e-4, 0.0]
[0.0, -1.7773949138776696e-4, -3.1086347862371855e-4, -3.714478154303591e-4, -3.5502855035249303e-4, -2.7528200465845587e-4, -1.5207424182367424e-4, 0.0]
[0.0, -9.188482657347674e-5, -1.6196970595228066e-4, -1.9595925291693295e-4, -1.903987061394885e-4, -1.5064155667735002e-4, -8.533752030373543e-5, 0.0]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]


But using the nine point method significantly improves this.

ghci> liftA2 (-^) (analyticValue 7) (runSolver 7 200 bndFnEg3 s9) >>= return . pPrint
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
[0.0, -2.7700522166329566e-7, -2.536751151638317e-7, -5.5431452705700934e-8, 7.393573120406671e-8, 8.403487600228132e-8, 4.188249685954659e-8, 0.0]
[0.0, -2.0141002235463112e-7, -2.214645128950643e-7, -9.753369634157849e-8, 2.1887763435035623e-8, 6.305346988977334e-8, 4.3482495659663556e-8, 0.0]
[0.0, -1.207601019737048e-7, -1.502713803391842e-7, -9.16850228516175e-8, -1.4654435886995998e-8, 2.732932558036083e-8, 2.6830928867571657e-8, 0.0]
[0.0, -6.883445567013036e-8, -9.337114890983766e-8, -6.911451747027009e-8, -2.6104150896433254e-8, 4.667329939200826e-9, 1.1717137371469732e-8, 0.0]
[0.0, -3.737430460254432e-8, -5.374955715231611e-8, -4.483740087546373e-8, -2.299792309368165e-8, -4.122571728437663e-9, 3.330287268177301e-9, 0.0]
[0.0, -1.6802381437586167e-8, -2.5009212159532446e-8, -2.229028683853329e-8, -1.3101905282919546e-8, -4.1197137368165215e-9, 3.909041701444238e-10, 0.0]
[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]


# Bibliography

Iserles, A. 2009. A First Course in the Numerical Analysis of Differential Equations. A First Course in the Numerical Analysis of Differential Equations. Cambridge University Press. http://books.google.co.uk/books?id=M0tkw4oUucoC.

Lippmeier, Ben, and Gabriele Keller. 2011. “Efficient Parallel Stencil Convolution in Haskell.” In Proceedings of the 4th ACM Symposium on Haskell, 59–70. Haskell ’11. New York, NY, USA: ACM. doi:10.1145/2034675.2034684. http://doi.acm.org/10.1145/2034675.2034684.

# Finding dead code with puppetresources

I just released version 0.12.1, along with binary downloads at the usual place.

The main feature of this new version is that puppetresources can now detect dead code. In order to do so, you must supply it with a site.pp containing explicit references to all the nodes you are using, and run it that way :

<figure class="code">
 1  puppetresources -p . -o deadcode +RTS -N4
</figure>

Also of interest for those writing automated integration test, puppetresources now exits with an error code when something went wrong.

# The perfect machine

You sometimes hear people claim that there is no perfectly efficient machine, that every machine wastes some of its input energy in noise or friction.

However, there is a counterexample. An electric space heater is perfectly efficient. Its purpose is to heat the space around it, and 100% of the input energy is applied to this purpose. Even the electrical energy lost to resistance in the cord you use to plug it into the wall is converted to heat.

Wait, you say, the space heater does waste some of its energy. The coils heat up, and they emit not only heat, but also light, which is useless, being a dull orange color. Ah! But what happens when that light hits the wall? Most of it is absorbed, and heats up the wall. Some is reflected, and heats up a different wall instead.

Similarly, a small fraction of the energy is wasted in making a quiet humming noise—until the sound waves are absorbed by the objects in the room, heating them slightly.

Now it's true that some heat is lost when it's radiated from the outside of the walls and ceiling. But some is also lost whenever you open a window or a door, and you can't blame the space heater for your lousy insulation. It heated the room as much as possible under the circumstances.

So remember this when you hear someone complain that incandescent light bulbs are wasteful of energy. They're only wasteful in warm weather. In cold weather, they're free.

# Everything needs an ID

I wrote some time ago about Moonpig's use of GUIDs: every significant object was given a unique ID. I said that this was a useful strategy I had only learned from Rik, and I was surprised to see how many previously tricky programming problems became simpler once the GUIDs were available. Some of these tricky problems are artifacts of Perl's somewhat limited implementation of hashes; hash keys must be strings, and the GUID gives you an instantaneous answer to any question about what the keys should be.

But it reminds me of a similar maxim which I was thinking about just yesterday: Every table in a relational database should have a record ID field. It often happens that I am designing some table and there is no obvious need for such a field. I now always put one in anyway, having long ago learned that I will inevitably want it for something.

Most recently I was building a table to record which web pages were being currently visited by which users. A record in the table is naturally identified by the pair of user ID and page URL; it is not clear that it needs any further keys.

But I put in a record ID anyway, because my practice is to always put in a record ID, and sure enough, within a few hours I was glad it was there. The program I was writing has not yet needed to use the record IDs. But to test the program I needed to insert and manipulate some test records, and it was much easier to write this:

update table set ... where record_id = 113;


than this:

update table set ... where user_id = 97531 and url = 'http://hostname:port/long/path/that/is/hard/to/type';


If you ever end up with two objects in the program that represesent record sets and you need to merge or intersect them synthetically, having the record ID numbers automatically attached to the records makes this quite trivial, whereas if you don't have them it is a pain in the butt. You should never be in such a situation, perhaps, but stranger things have happened. Just yesterday I found myself writing

    function relativize (pathPat) {
var dummyA = document.createElement('a');
dummyA.href = document.URL;
return "http://" + dummyA.host + pathPat;
}


which nobody should have to do either, and yet there I was. Sometimes programming can be a dirty business.

During the bootstrapping of the user-url table project some records with bad URLs were inserted by buggy code, and I needed to remove them. The URLs all ended in % signs, and there's probably some easy way to delete all the records where the URL ends in a % sign. But I couldn't remember the syntax offhand, and looking up the escape sequence for LIKE clauses would have taken a lot longer than what I did do, which was:

delete from table where record_id in (43, 47, 49)


So the rule is: giving things ID numbers should be the default, because they are generally useful, like handles you can use to pick things up with. You need a good reason to omit them.

# 7.8.1-rc1 Gentoo experience

A week ago Austin Seipp and GHC team announced first release candidate from 7.8 branch.

As a packager I was especially interested in following features:

1. GHCi (and dynamic linking) on unregisterised arches, like ia64 and powerpc64
2. jobs argument for ghc make. Parallel builds for free.
3. what did seriously break, what was fixed?

First off, -rc1 is packaged in gentoo-haskell overlay (not keyworded as quite a bit of packages fail to build against ghc-7.8).

# GHCi (and dynamic linking)

Dynamic linking works like a charm! GHCi loads binaries noticeaby faster. Let’s test it! Simplest synthetic test: how fast do you get prompt from interpreter?

# ghc-7.6:
$time { echo '1+1' | ghci -package yesod-core >/dev/null; } real 0m0.626s user 0m0.550s sys 0m0.074s # ghc-7.8:$ time { echo '1+1' | ghci -package yesod-core >/dev/null; }
real    0m0.209s
user    0m0.172s
sys     0m0.034s

It’s a case, when files are cached in RAM. 3-4 times faster. The same boost should apply every time when you compile something template-haskell related.

# jobs argument for ghc make

I’ve went ahead and tried to enable it for all ebuilds.

For some reason ghc eats a lot of system time in that mode. Likely jobs without arguments is not very good idea and i’ll need to limit it by minimum of MAKEOPTS value and some N (Cabal picked 64).

Even in this mode 2-time speedup is visible on large packages.

# So what did break?

Not _that_ much, actually.

## alex and happy generated parsers

All package maintainers who ship lexers generated by alex and parsers generated by happy are strongly advised to update those tools locally and reissue hackage update, as old parsers do not compile against ghc-7.8.

If you have happened to use low-level

(==#) :: Int# -> Int# -> Bool

primitives, you might need to port your code a bit, as how their type is a bit different:

(==#) :: Int# -> Int# -> Int#

Here is our example fix for arithmoi.

## Type inference changed a bit.

Traditionally darcs needed a patch :] In that big mostly dumb patch most interesting bit is explicit assignment:

- where copyRepo =
+ where copyRepo :: IO ()
+ copyRepo =

Even more amusing breakage was in shake, where error was in inability to infer Addr# argument. No idea was it a bug or feature.

As we’ve seen in darcs patch many unsafe${something} functions went away from Foreign modules down to their Unsafe counterparts. ## Typeable Typeable representation did change in a substantial way, thus advanced generic stuff will break. I have no example fix, but have a few of broken packages, like dependent-sum. ## Hashtable gone from base Example of fix for frag package. By the way, ghc-7.6 used to eat 8GBs of RAM compiling frag. For ghc-7.8 it was enough 700MBs even for 8 building threads. ## Compiler itself The thing I expected to try didn’t compile: unregisterised arches and GHCi on them. I’ve hacked-up a workaround to make them build, but in threaded RTS mode it still SIGSEGVs. STG gurus are welcome to help me :] I have fundamental questions like: • can unregisterised builds support SMP in theory? (via __thread attribute for example) • did UNREG ever produce working threaded runtime? $ cat __foo/foo.hs
main = print 1
# non-threaded works, as always been
$inplace/bin/ghc-stage1 --make __foo/foo.hs -threaded -debug -fforce-recomp #$ gdb --args ./__foo/foo +RTS -D{s,i,w,g,G,b,S,t,p,a,l,m,z,c,r}
...
(gdb) run
...
7ffff7fb9700: resuming capability 0
7ffff7fb9700: cap 0: created thread 1
7ffff7fb9700: new bound thread (1)
7ffff7fb9700: cap 0: schedule()
7ffff7fb9700: cap 0: running thread 1 (ThreadRunGHC)
Jumping to 0x7ec17f
#
Program received signal SIGSEGV, Segmentation fault.
0x00000000007ec1a2 in stg_returnToStackTop ()
(gdb) bt
#0  0x00000000007ec1a2 in stg_returnToStackTop ()
#1  0x00000000007d26d9 in StgRun (f=0x7ec17f , basereg=0xca0648) at rts/StgCRun.c:81
#2  0x00000000007c7a30 in schedule (initialCapability=0xca0630, task=0xcc3b30) at rts/Schedule.c:463
#3  0x00000000007ca2c4 in scheduleWaitThread (tso=0x7ffff6b05390, ret=0x0, pcap=0x7fffffffd218) at rts/Schedule.c:2346
#4  0x00000000007c0162 in rts_evalIO (cap=0x7fffffffd218, p=0xb61450 , ret=0x0) at rts/RtsAPI.c:459
#5  0x00000000007e04c3 in ioManagerStartCap (cap=0x7fffffffd218) at rts/posix/Signals.c:184
#6  0x00000000007e04f6 in ioManagerStart () at rts/posix/Signals.c:194
#7  0x00000000007d1d5d in hs_init_ghc (argc=0xc96570 , argv=0xc96578 , rts_config=...) at rts/RtsStartup.c:262
#8  0x00000000007d000b in real_main () at rts/RtsMain.c:47
#9  0x00000000007d0122 in hs_main (argc=17, argv=0x7fffffffd418, main_closure=0xb527a0 , rts_config=...) at rts/RtsMain.c:114
#10 0x0000000000404df1 in main ()

Looks like CurrentTSO is complete garbage. Should not happen :]

# Conclusion

The experience is positive. I already get bored, when see single-threaded make of ghc-7.6 and want to update a compiler.

Things like yesod, darcs, hoogle, pandoc and xmonad build fine, thus you can get working environment very fast.

Package authors are more eager to fix stuff for this release: it turns bug lookup and benchmarking into very interactive process.

I want to thank All Of You to make push haskell forward!

Thank you!