There Is Such A Thing As A Declarative Language, and It’s The World’s Best DSL

In a recent post I asked whether there is any such thing as a declarative language. The main point was to argue that the standard “definitions” are, at best, not very precise, and to see whether anyone might offer a better definition. What I’m after is an explanation of why people seem to think that the phrase has meaning, even though they can’t say very clearly what they mean by it.  (One commenter analogized with “love” and “happiness”, but I would counter by saying that we’re trying to do science here, and we ought to be able to define our terms with some precision.)

As I mentioned, perhaps the best “definition” that is usually offered is to say that “declarative” is synonymous with “functional-and-logic-programming”.  This is pretty unsatisfactory, since it is not so easy to define these terms either, and because, contrary to conventional classifications, the two concepts have pretty much nothing in common with each other (but for one thing to be mentioned shortly). The propositions-as-types principle helps set them clearly apart: whereas functional programming is about executing proofs, logic programming is about the search for proofs. Functional programming is based on the dynamics of proof given by Gentzen’s inversion principle. Logic programming is based on the dynamics of provability given by cut elimination and focusing.  The two concepts of computation could not be further apart.

Yet they do have one thing in common that is usefully isolated as fundamental to what we mean by “declarative”, namely the concept of a variable.  Introduced by the ancient Hindu and Muslim mathematicians, Brahmagupta and al Kwharizmi, the variable is one of the most remarkable achievements of the human intellect.  In my previous post I had secretly hoped that someone would propose variables as being central to what we mean by “declarative”, but no one did, at least not in the comments section.  My unstated motive for writing that post was not so much to argue that the term “declarative” is empty, but to test the hypothesis that few seem to have grasp the importance of  this concept for designing a civilized, and broadly applicable, programming language.

My contention is that variables, properly so-called, are what distinguish “declarative” languages from “imperative” languages. Although the imperative languages, including all popular object-oriented languages, are based on a concept that is called a variable, they lack anything that actually is a variable.   And this is where the trouble begins, and the need for the problematic distinction arises.  The declarative concept of a variable is the mathematical concept of an unknown that is given meaning by substitution. The imperative concept of a variable, arising from low-level machine models, is instead given meaning by assignment (mutation), and, by a kind of a notational pun, allowed to appear in expressions in a way that resembles that of a proper variable.  But the concepts are so fundamentally different, that I argue in PFPL that the imperative concept be called an “assignable”, which is more descriptive, rather than “variable”, whose privileged status should be emphasized, not obscured.

The problem with purely imperative programming languages is that they have only the concept of an assignable, and attempt to make it serve also as a concept of variable. The results are a miserable mess of semantic and practical complications. Decades of work has gone into rescuing us from the colossal mistake of identifying variables with assignables. And what is the outcome? If you want to reason about assignables, what you do is (a) write a mathematical formulation of your algorithm (using variables, of course) and (b) show that the imperative code simulates the functional behavior so specified.   Under this methodology the mathematical formulation is taken as self-evidently correct, the standard against which the imperative program is judged, and is not itself in need of further verification, whereas the imperative formulation is, invariably, in need of verification.

What an odd state of affairs!  The functional “specification” is itself a perfectly good, and apparently self-evidently correct, program.  So why not just write the functional (i.e., mathematical) formulation, and call it a day?  Why indeed!  Declarative languages, being grounded in the language of mathematics, allow for the identification of the “desired behavior” with the “executable code”.  Indeed, the propositions-as-types principle elevates this identification to a fundamental organizing principle: propositions are types, and proofs are programs.  Who needs verification?  Once you have a mathematical specification of the behavior of a queue, say, you already have a running program; there is no need to relegate it to a stepping stone towards writing an awkward, and invariably intricate, imperative formulation that then requires verification to ensure that it works properly.

Functional programming languages are written in the universally applicable language of mathematics as expressed by the theory of types.  Such languages are therefore an integral part of science itself, inseparable from our efforts to understand and master the workings of the world.  Imperative programming has no role to play in this effort, and is, in my view, doomed in the long run to obsolescence, an artifact of engineering, rather than a fundamental discovery on a par with those of mathematics and science.

This brings me to my main point, the popular concept of a domain-specific language. Very much in vogue, DSL’s are offered as the solution to many of our programming woes. And yet, to borrow a phrase from my colleague Guy Blelloch, the elephant in the room is the question “what is a domain?”. I’ve yet to hear anyone explain how you decide what are the boundaries of a “domain-specific” language. Isn’t the “domain” mathematics and science itself? And does it not follow that the right language must be the language of mathematics and science? How can one rule out anything as being irrelevant to a “domain”?  I think it is impossible, or at any rate inadvisable, to make such restrictions a priori.  Indeed, full-spectrum functional languages are already the world’s best DSL’s, precisely because they are (or come closest to being) the very language of science, the ultimate “domain”.

Filed under: Research Tagged: assignables, declarative language, domain-specific language, variables

by Robert Harper at March 10, 2014 05:12 AM

Tariq Ali says independence would open a new politics throughout UK

I have a colleague who opposes independence, on the grounds that though it might be good for Scotland, it would be bad for the UK as a whole. Tariq Ali disagrees, as reported in Herald Scotland.

[Ali] believes the referendum could trigger the process of dismantling the British state. "At present UK politics are dominated by the extreme centre." A vote for Scottish independence would amount to a rejection of the extreme centre, and would open up the path for a "new politics" throughout the UK.
"England has been politically petrified since the Thatcher era." Although the Tories were soundly beaten by New Labour in 1997, Blair was the heir to Thatcher, he says. "An independent Scotland could also lead to something quite new in England; but not something nutty like UKIP."
He will tell his Scottish audiences that a vote for independence would " enable the rediscovery of hope of a better future, provide a much greater say for people over what their country looks like, and would finish off the decrepit, corrupt, tribal Labourist stranglehold on some parts of Scotland forever".
Ali is not much exercised by suggestions by businesses that would leave Scotland after a yes vote. "Large corporations are trying to frighten people,'' he said. ''But there are opportunities for investment from Scandinavia and the far east."
Ali's visit will not be welcomed by the SNP leadership. He will argue that an independent Scotland would need its own currency, and would require a state Bank of Scotland to be established. He says the new currency could be informally tied to sterling, but that all economic decisions would be taken in Scotland by a sovereign Scottish parliament.

Ali will be speaking in Appleton Tower, opposite my office, 3:30 Fri 14 March. Alas, I'll be in London that day, speaking at Functional Programming eXchange.

 

by Philip Wadler (noreply@blogger.com) at March 09, 2014 11:06 PM

An Unpleasant Interruption, Some Good News, and A Plea

It’s been a while since my last blog post (early last December, in fact), and I’ve even neglected to process comments during the same period.  Why the interruption?  Have I finally run out of things to complain about?  Not a chance!  Actually, what’s happened is that on December 18 I underwent a kidney transplant from a kind living donor who I scarcely even knew before the surgery occurred.  (If you are interested in the back story, you might like to read the newspaper article about it that appeared in the Pittsburgh Post-Gazette last Christmas.)  My condition, primary FSGS, is idiopathic, and has been worsening for about 20 years (an unusually long time before transplant is indicated).  Things finally became acute last year when I was reduced to approximately 10% kidney function, close to the lower bound for survival without renal replacement therapy.  I was deeply humbled by the generosity of numerous people who stepped forward to volunteer to donate an organ to me, some of whom are readers of this blog and are in any case well-known to all of you.  To them I am unable to adequately express my gratitude, but I can try to pay it forward over time.  The donor selection process is largely opaque to the donee (so as to ensure that the donor not being is coerced or bribed), but as it turned out Tony Balko, the fiancé of my “niece”, Marina Pfenning, daughter of my colleague Frank Pfenning, became my donor, and thereby saved my life.

I have spent the last couple of months recovering from the surgery itself, which involved a substantial incision, monitoring my progress and the health of the organ, and adjusting the immune suppressants to achieve a balance between avoiding rejection and inviting infection.  As a pay-it-forward gesture I volunteered to be a subject in a study of a new immune suppressant, ASKP1240, that is being developed specifically for kidney transplant patients.  All this means frequent visits to the transplant center and frequent blood draws to measure my kidney function and medication levels.  The recovery and monitoring has kept me operating at a reduced level, including neglecting my blog.

The good news is that Tony and I have fully recovered from surgery, and I am happy to say that I am enjoying an optimal outcome so far.  The transplanted organ began working immediately (this is not always the case), and within two days I had gotten back ten years of kidney function.  By now I am at completely normal blood levels, with no signs of kidney disease, and no signs of rejection or other complications.  Tony gave me a really good organ, and my body seems to be accepting it so far.  I’m told that the first six months are determinative, so I expect to have a pretty solid sense of things by the summer.

I would like to say that among the many things I’ve learned and experienced these last few months, one is an appreciation for the importance of organ donation.  Every year hundreds of people die from kidney disease for lack of a suitable organ.  If someone is limited to the national cadaverous donors list, it can take more than two years to find an acceptable organ, during which time people often die waiting.  Another complication is that someone may have a willing donor, perhaps a family member, with whom they are incompatible.  There are now several living donor exchange networks that arrange chains of organ swaps (as many as 55 simultaneously, I’m told!) so that everyone gets a compatible organ.  But to be part of such an exchange, you must have a living donor.

Living donation is a daunting prospect for many.  It does, after all, involve major surgery, and therefore presents a health risk to the donor.  On the other hand nature has  provided that we can survive perfectly well on one kidney, and a donation is literally the difference between life and death for the recipient.  The trade-off is, in objective terms, clearly in favor of donation, but the scarcity of organs makes clear that not everyone, subjectively, reaches the same conclusion.  As an organ recipient, allow me to plead with you to consider becoming an organ donor, at least upon your death, and perhaps even as a living donor for those cases, such as kidney donation, where it is feasible.  Should you donate, and find yourself in need of an organ later in life, you will receive top priority among all recipients for a donated organ.  The donation process is entirely cost-free to the donor in monetary terms, but pays off big-time in terms of one’s personal satisfaction at having saved someone’s life.

Filed under: Uncategorized Tagged: kidney transplant, organ donation

by Robert Harper at March 09, 2014 07:07 PM

WAI 2.1 and yesod-websockets

I'm happy to announce a new 2.1 release of WAI and Warp, version 0.3.1 of http-reverse-proxy, and the release of a brand new package: yesod-websockets. These releases are all connected, so let's start off by describing the major addition to WAI 2.1.

Primary change: responseRaw

HTTP is built around a request/response pair, and WAI has until now followed that strictly. The three response types allowed (builder, file, and source) all worked around the idea of first consuming a request, then returning a response. For normal HTTP requests, this is adequate. But there are two areas (that I'm aware of at least) where this falls short:

• Implementing proxy servers, where the CONNECT request method requires upgrading to full-duplex communication.
• Using WebSockets, which again use full duplex communication.

To work around this limitation, Warp provides a settingsIntercept, which allows a special handler to intercept some requests and take control away from the normal WAI request/response pairs. I took this approach initially because many WAI handlers have no means of properly supporting full duplex communications (e.g., CGI). However, this split between normal and non-normal handling makes it very awkward to actually use WebSockets.

So starting with WAI 2.1, we have a fourth response type: responseRaw. Its type is:

responseRaw
    :: (C.Source IO B.ByteString -> C.Sink B.ByteString IO () -> IO ())
    -> Response
    -> Response

The first parameter is a "raw application:" it takes a Source of all data coming from the client, a Sink for sending data to the client, and performs an action with them. The second parameter is a backup response for WAI handlers which do not support responseRaw; usually this will just be a message like "Your server doesn't support WebSockets."

With this change the old settingsIntercept from Warp is no longer necessary, and the behavior can be achieved from inside normal WAI applications. This has resulted in a number of changes.

wai-websockets 2.1

The wai-websockets package has been available for over two years now, thanks to Jasper Van der Jeugt's websockets library. However, until now, it's provided a slightly strange API to work with settingsIntercept:

intercept :: ConnectionOptions -> ServerApp -> Request -> Maybe (Source IO ByteString -> Connection -> IO ())

ConnectionOptions and ServerApp are both part of the websockets library itself. Request is a WAI request, and it returns a Just value if the request represents a proper WebSockets request. Starting with version 2.1, there's a much simpler API:

websocketsApp :: ConnectionOptions -> ServerApp -> Request -> Maybe Response

Now, instead of getting back something to tie into Warp's intercept handler, we get back a Response. If there was no WebSockets request, we get Nothing, which allows us to write normal, non-WebSockets responses.

yesod-websockets

This is also the first release of the yesod-websockets package. Previously, there was no good story for how to tie WebSockets into an existing Yesod application. Now, integration is trivial. Let's say we want to write a very basic chat server. We can describe this as a WebSockets application with the following:

chatApp :: WebSocketsT Handler ()
chatApp = do
    sendTextData ("Welcome to the chat server, please enter your name." :: Text)
    name <- receiveData
    sendTextData $ "Welcome, " <> name
    App writeChan <- getYesod
    readChan <- atomically $ do
        writeTChan writeChan $ name <> " has joined the chat"
        dupTChan writeChan
    race_
        (forever $ atomically (readTChan readChan) >>= sendTextData)
        (sourceWS $$ mapM_C (\msg ->
            atomically $ writeTChan writeChan $ name <> ": " <> msg))

sendTextData and receiveData are the core functions. There's also a conduit-based API using sourceWS and sinkWSText, as well as some convenience asynchronous helpers (race and concurrently). But more interesting is the integration with the existing handler infrastructure:

getHomeR :: Handler Html
getHomeR = do
    webSockets chatApp
    defaultLayout ...

The webSockets function takes a WebSockets application and tries to run it. If the client sent a WebSockets request, then the app will be run, and no further Handler actions will be taken. Otherwise, normal operations will continue. (You can see the full chat example in the Github repo.)

As this is a first release, things are still evolving, so it's not a good idea to base your entire app off of this yet. But if you've been interested in playing with WebSockets, now's a good time to get started. If you end up working on anything, please let me know!

http-reverse-proxy

This is actually the project that kicked off my endeavors into responseRaw in the first place. I wanted to add support for reverse proxying WebSockets requests, and initially did so without WAI support using settingsIntercept. But the entire approach felt like a hack. Now with responseRaw support, all users of http-reverse-proxy automatically get WebSockets support. (This includes yesod devel and keter, by the way.)

I also put together an experimental forward proxy server a few weeks ago, and responseRaw made that nicer too.

Additional change: settings

Kazu and I changed a few settings since Warp 2.0, which required a major version bump. We didn't like that the 2.0 settings infrastructure required a major version bump for minor tweaks to settings, so we've introduced a new system for modifying Warp settings. You still start with the defaultSettings value, but to modify, for example, the port, you use the new setter function:

setPort 8080 defaultSettings

The old record-based accessors have been deprecated. In a future release, we'll be moving them entirely to an internal module.

The concrete settings change was providing the socket address to the onOpen and onClose settings. This allows you to write logging functions when connections are opened and closed, and indicate where the connections come from. In addition, you can inspect the SockAddr in onOpen and reject a connection immediately. Previously, this needed to be done from the application itself, which meant that more processing was performed before terminating the connection. onOpen/onClose.

March 09, 2014 11:32 AM

Lady Alba — Bad Romance

<object class="BLOGGER-youtube-video" classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=6,0,40,0" data-thumbnail-src="https://ytimg.googleusercontent.com/vi/5SvdecwnYJ4/0.jpg" height="266" width="320"><param name="movie" value="https://youtube.googleapis.com/v/5SvdecwnYJ4&amp;source=uds"/><param name="bgcolor" value="#FFFFFF"/><param name="allowFullScreen" value="true"/><embed allowfullscreen="true" height="266" src="https://youtube.googleapis.com/v/5SvdecwnYJ4&amp;source=uds" type="application/x-shockwave-flash" width="320"></embed></object>

Dead on and hilarious.

by Philip Wadler (noreply@blogger.com) at March 08, 2014 02:53 PM

Bayesian Football Picker: an implementation

Some time ago I wrote an article about applying Bayes to pick winners for the weekly football pool we had at our office. So, that pool went on for seventeen weeks, and I came out as one of the winners. Success!

So, how did that all work? 

I'll give you the business process of it and provide a high level overview of my Bayesian system. After that, I'll get down into the guts of the implementation.

I wrote this entire system in Haskell. It was something less than a day's effort.

Business Process/Big Picture

Each week, our boss, Dharni, provided the USA Today's predictions for the teams as a spreadsheet, which I saved in CSV format ('comma-separated values'). The weekly input spreadsheet (as CSV) looked like this:

,Wed Sep 5,

NYG GIANTS,3½ ,Dallas

,Sun Sep 9,

CHICAGO,10 ,Indianapolis

Philadelphia,7½ ,CLEVELAND

NYJ JETS,2½ ,Buffalo

NEW ORLEANS,7 ,Washington

New England,5 ,TENNESSEE

MINNESOTA,3½ ,Jacksonville

HOUSTON,11 ,Miami

DETROIT,6½ ,St. Louis Rams

Atlanta,2½ ,KANSAS CITY

GREEN BAY,5 ,San Francisco

Carolina,2½ ,TAMPA BAY

Seattle,2½ ,ARIZONA

DENVER,2½ ,Pittsburgh

,Mon Sep 10,,,,,,,

BALTIMORE,6 ,Cincinnati,TS,35-20,,,,

OAKLAND,2½ ,San Diego,,,,,,

where the number (e.g.: '2½') was the predicted point-spread, the team on the left was  the team predicted to win by the point-spread, and the capitalized team was the home team. The 'TS' indicator was if there were ties of people in the pool who guess the same number of picks correctly, then the TS was a tie-breaker: you had to guess the 'Total Score' for that game and the person who got the closest total score won the tie-breaker. I didn't worry my head over this particular aspect, so I just had my system predict the winner for that game and threw out a random total score.

I fed these data to my system which took each data point as a class-value for the Bayesian classifier, and my system spit out ('spit out' is a technical term, just like: 'run off') its own predictions which I turned right around back to Dharni: "I've highlighted the teams my system picked to win, Dharni."

The output result from the system was something like this:

Thursday,NYGGIANTS,Home,3.5,DALLAS,RIGHT

Saturday,CHICAGO,Home,10.5,INDIANAPOLIS,LEFT

Saturday,PHILADELPHIA,Away,7.5,CLEVELAND,LEFT

Saturday,NYJJETS,Home,2.5,BUFFALO,LEFT

Saturday,NEWORLEANS,Home,7.5,WASHINGTON,RIGHT

....

Just as before, right? Well, sort of. In this case my system output teams as (discriminated type) values, the spreads were floats, and the Home/Away indicator told me where the left team played. 'LEFT' or 'RIGHT' indicated which team the system predicted would win that game.

My coworkers were enchanted that I wrote myself a little football-picker. They'd exclaim in mock-dismay: "Something only geophf would come up with!"

Then my system won, and won, and won again. Not consistently, nor convincingly, but, to my satisfaction (that it even ever won at all): profitably. Pretty good. Pretty darn good enough!

Then, with what really happened that week (you know: that pesky ITRW result-set messing with my conceptual-frameworks!), I'd feed the results back into my system (the feedback look), training it with what were good and bad guesses on its part. Week after week my system accumulated the historical data and results into a data-set I named basis/training-set.csv. 

As the season progressed, my historical training data set grew, and I did, indeed, win pools more often later in the season rather than earlier. Which was nice: my predictive system was predicable.

The Guts/Little Picture

It's actually embarrassing how small my baby classifier is, and really, it'd be a lot smaller if Haskell natively read football spread predictions: it'd just be the Bayesian classifier.

But since Haskell doesn't natively read CSV files nor football spreads, I wrote those modules, too.

Here's the system.

The football picker is in the Football (parent) module and contains the module named Go:

> module Football.Go where

> import Football.Data.Week

> import Football.Analytics.Bayes

> import Football.Trainer

> go picks training = snarf training >>= \basis ->

>                     slurp picks >>= readWrite pick Thursday basis writeln

> choose picks = putStrLn "<table border='1'>" >>

>              slurp picks >>= readWrite justShow Thursday () writeRow >>

>              putStrLn "</table>"

> writeRow (match, _) = writeWeek HTML match >> putStrLn ""

What you do is load the Go module and say "go" to Haskell with the teams to be picked for this week with their data (the 'picks') and the training data set, both in CSV-format.

The system then 'snarfs' the training data, training the Bayesian classifier, yielding a training 'basis,' then 'slurps' in the teams for this week to give the picks.

As to the names of the functions: don't look at me. I don't know. The dude who wrote system had an oddball sense of humor.

And the 'choose' and 'writeRow' functions. Eh. I had made my system both CSV and HTML (output) friendly. I had this grandiose plan to have everything printed out all prettily in HTML and have an HTML input interface, setting this up as a web service with micro-transactions and everything so I could eventually sell the system off to Microsoft for 1.21 gigabucks, but in practice I just 'go'ed with the console-output results and highlighted the winning teams on the spreadsheet Dharni provided, and never really used the HTML functionality beyond some initial prototyping. Idle hands, lesson learned, simplicity, ... you know: all that.

So, the 'Go' module is just an entry-point to the 'readWrite' function which reads the input UTF-8 data, converts it to Haskell types and then writes the results out as CSV. Let's look at that function, then, and keep digging down until we're all dig-dugged out.

readWrite

The 'readWrite' function is in module Football.Trainer, its definition is as follows:

> readWrite _ _ _ _ [] = return ()

> readWrite fn day basis w (row:rows) = if   length (csv row) == 1

>                                       then readWrite fn (succ day) basis w rows 

>                                       else w (fn day row basis) >>

>                                            readWrite fn day basis w rows

... the whole if-clause is to handle whether this row is a football match row or a row declaring the day of the week.

If we query the type of readWrite from the Haskell system we get this 'interesting' type-value:

readWrite

  :: (Monad m, Enum a) =>

     (a -> String -> t -> t1)

     -> a

     -> t

     -> (t1 -> m a1)

     -> [String]

     -> m ()

which is my lovely way of making this generalized function that reads an enumerable type and puts it out to some monadic domain.

Bleh!

But, since I'm not working with HTML any more, readWrite is always called with the higher-order function arguments of

readWrite pick day basis writeln

where the functions pick and writeln are declared as:

> pick :: DayOfWeek -> String -> ([Match], [Match]) -> (Match, Call)

and

> writeln :: (Show t) => (Match, t) -> IO ()

> writeln (match, winner) = writeWeek CS match >> putStrLn (show winner)

which reduces readWrite, once the higher-order function arguments are applied, to a more compact type of:

> justDoIt :: DayOfWeek -> ([Match], [Match]) -> [String] -> IO ()

> justDoIt day basis rows = readWrite pick day basis writeln rows

which, of course, means we need to explain the function pick now, with its calls, but let's first clarify the types used, now that the function readWrite has been reduced to its used form.

Types

DayOfWeek is an example right out of the book for a disjoint type:

> data DayOfWeek = Thursday | Sunday | Monday

>      deriving (Show, Read, Eq, Ord, Enum)

(apparently there are only three days of the week ... in football, anyway, and that's all that matters, right?)

And the Match-type is the representation of a row of data (a football match):

> data Match = Match DayOfWeek Team Field Float Team deriving Show

Team is just simply the teams as disjoint enumerated values (e.g.: GREENBAY, STLOUISRAMS, etc.), The Field-type is Home or Away, and there you go!

There is a bit of a hex reading in the floating point value from, e.g.  '2½' and for that particular hack I created a separate type in a separate module:

> module Football.Data.Spread where

eh.

So, the spread is a number but represented in unicode ... do we wish to

capture the original datum as it was represented in the picks sheet for any

reason? Mucking with data always leads to sorrow, but ... well, this module

provides a Num interface to Spread, so you can swing either way with it.

> import Data.Char

> data Spread = Spread String

>      deriving Show

> toNum :: Spread -> Float

> toNum (Spread x) = toNum' x 0.0

> toNum' [] x = x

> toNum' (c:rest) x | c == ' ' = x

>                   | c > '9' = x + 0.5

>                   | otherwise = toNum' rest (10 * x

>                                              + fromIntegral (ord c - ord '0'))

> instance Read Spread where

>    readsPrec _ datum = [(Spread datum, "")]

> instance Eq Spread where

>    x == y = toNum x == toNum y

You'll note that the Spread-type isn't actually a Num instance, as the spread is a typed class value, I don't care, in my Bayesian system, whether the spread is lesser or greater; I just care if it's different from another spread.

Algorithm

Okay, back to the program!

So readWrite slurps in training data and the matches for this week and sends it to the 'pick' function which we've declared above, and we now define as:

> pick day row basis = let (match, _) = mkWeek day row

>                          winner = classify match basis

>                      in (match, winner)

The mkWeek function just slurps in the row as a string and converts it to a Match-type and with that reified typed value we ask the Bayesian system to classify this n-tuple as a Left or Right (predicted-to-)win.

So, let's look at the classify-function.

> classify :: Match -> ([Match], [Match]) -> Call

> classify query basis@(l, r) = let ll  = fromIntegral $ length l

>                             lr  = fromIntegral $ length r

>                             tot = ll + lr

>                         in  if (bayes query l + log (ll / tot)) >

>                                (bayes query r + log (lr / tot))

>                             then LEFT

>                             else RIGHT

The classify-function is your classic Bayes algorithm: classify the n-tuple as the type with the greatest probabilistic outcome. In our case we have two possible results, LEFT and RIGHT, so if the probablistic (logarithmic) sum for LEFT is greater, then it's LEFT, otherwise it's RIGHT.

Very 'Either'escque ... without the packaged data. So, actually, not very 'Either'escque at all but more 'Boolean'escque. Kinda. Sorta.

Our bayes-function is just summing the logarithms of the probabilities:

> bayes :: Match -> [Match] -> Float

> bayes (Match dow fav field spred dis) side = 

>       let pdow =   logp (\(Match d _ _ _ _) -> d == dow) side

>           pfav =   logp (\(Match _ f _ _ _) -> f == fav) side

>           pfield = logp (\(Match _ _ f _ _) -> f == field) side

>           psprd =  logp (\(Match _ _ _ s _) -> s == spred) side

>           pdis   = logp (\(Match _ _ _ _ d) -> d == dis) side

>       in sum [pdow, pfav, pfield, psprd, pdis]

We need a fix here for 0% match ... the log return -infinite, skewing the results, so let's just return 0 for 0, okay?[1]

> logp :: (Match -> Bool) -> [Match] -> Float

> logp fn matches = let num = fromIntegral (length $ filter fn matches)

>                       dem = fromIntegral (length matches)

>                   in  if (num == 0.0 || dem == 0.0)

>                       then 0.0

>                       else log (num / dem) 

That's basically everything, just some window-dressing functions of reading in the training set, which requires us to read in CSV files, so I present these functions here for completeness.

To read a CSV file, we simply rewrite the words-function from the Prelude to allow separators other than spaces:

> module CSV where

> import Char

-- I modified Prelude.words to accept a set of alternative delimiters to space

> wordsBy :: String -> String -> [String]

> wordsBy delims line

>        = let isDelim = flip elem delims

>          in  case dropWhile isDelim line of

>                           "" -> []

>                           s' -> w : wordsBy delims s''

>                                 where (w, s'') =

>                                        break isDelim s'

> csv = wordsBy ","

The CSV module is useful not only here for picking football teams, but also for anywhere you need to parse in CSV data as linearized Haskell-types.

and then readResults (the results of the training data, that is) is as follows:

> readResults :: ([Match], [Match]) -> [String] -> ([Match], [Match])

> readResults map [] = map

> readResults map (row:rows) = let [dow, fav, field, spred, dis, call] = csv row

>                                  day = read dow

>                                  match = Match day (read fav) (read field)

>                                                (read spred) (read dis)

>                                  winner = read call

>                                  res = Result match winner

>                              in  readResults (addmap winner map match) rows

where addmap is the obvious add-to-left-or-right-branch-of-the-training-data-function:

> addmap :: Call -> ([a], [a]) -> a -> ([a], [a])

> addmap LEFT (l, r) m = (m:l, r)

> addmap RIGHT (l, r) m = (l, m:r)

The 'a'-type here is invariably a Match-(Row)-type that I use as my training-set basis, but the addmap-function works with any set of paired-lists.

The readResults-function is used by the snarf-function:

> snarf :: FilePath -> IO ([Match], [Match])

> snarf file = readFile file >>=

>              return . lines >>=

>              return . readResults ([], [])

So that just leaves the slurp-function for reading in this week's matches:

> slurp :: FilePath -> IO [String]

> slurp file = readFile file >>= return . tail . lines

(we skip, or 'tail', by the first line, because that's the day of the first football games, which we invariably call Thursday)

Conclusion, or: please send your 1.21 gigabuck checks to geophf

And there you have it, folks: a little Bayesian system that picks (we hope) winning football teams from a set of accumulating historical data. The 'we hope'-caveat is the usual standard disclaimer when using Bayesian systems: as one of my colleagues pointed out, using such a system for classification is like driving your car with the only guidance being the view in the rear-mirror, but, for me, such guidance paid off. I walked away from this experience building yet another (naïve) Bayesian classifier, and my little pet project helped me walk away from this pool with a few dollars more than I invested into it. Yay!

('Yay!' is a technical term, c.f. Despicable Me 2)

-----

Endnotes:

[1] There was a comment on my original blog entry about normalizing the absent probability instead of what I do here, which is to zero it out. My system worked okay without linearization, so it would be an area of further research to see how the results are improved from linearization.

by geophf (noreply@blogger.com) at March 08, 2014 02:48 AM

Happy, Alex, and GHC 7.8

As we approach the 7.8 release of GHC, more and more people are running into problems with packages that use Alex and/or Happy for parsing.

The errors look like

templates/GenericTemplate.hs:104:22:
    Couldn't match expected type ‛Bool’
                with actual type ‛Happy_GHC_Exts.Int#’
    In the expression:
      (n Happy_GHC_Exts.<# (0# :: Happy_GHC_Exts.Int#))
    In a stmt of a pattern guard for
                   a case alternative:
      (n Happy_GHC_Exts.<# (0# :: Happy_GHC_Exts.Int#))
    In a case alternative:
        n | (n Happy_GHC_Exts.<# (0# :: Happy_GHC_Exts.Int#))
          -> (happyReduceArr Happy_Data_Array.! rule) i tk st
          where
              rule
                = (Happy_GHC_Exts.I#
                     ((Happy_GHC_Exts.negateInt#
                         ((n Happy_GHC_Exts.+# (1# :: Happy_GHC_Exts.Int#))))))

for Happy and

    Pattern bindings containing unlifted types should use an outermost bang pattern:
      ((I# (ord_c))) = ord c
    In the expression:
      let
        (base) = alexIndexInt32OffAddr alex_base s
        ((I# (ord_c))) = ord c
        (offset) = (base +# ord_c)
        ....
      in
        case new_s of {
          -1# -> (new_acc, input)
          _ -> alex_scan_tkn
                 user orig_input (len +# 1#) new_input new_s new_acc }
    In a case alternative:
        Just (c, new_input)
          -> let
               (base) = alexIndexInt32OffAddr alex_base s
               ((I# (ord_c))) = ord c
               ....
             in
               case new_s of {
                 -1# -> (new_acc, input)
                 _ -> alex_scan_tkn
                        user orig_input (len +# 1#) new_input new_s new_acc }
    In the second argument of ‘seq’, namely
      ‘case alexGetChar input of {
         Nothing -> (new_acc, input)
         Just (c, new_input)
           -> let
                (base) = ...
                ....
              in
                case new_s of {
                  -1# -> ...
                  _ -> alex_scan_tkn
                         user orig_input (len +# 1#) new_input new_s new_acc } }’

for Alex. (These are not all the error messages that are produced by GHC, but hopefully enough that this article is googlable.)

First I give instructions on how to fix these problems, and then explain why they arise in the first place.

TL;DR: how do I fix the package?

As a maintainer

1. Install the latest versions of alex and happy. GHC 7.8 support was added in alex-3.1.0 and happy-1.19.0, but later versions contain additional bugfixes.

2. Double-check that cabal picks the latest versions of these tools: in your package’s source tree run

   cabal configure -v | grep -e alex -e happy

   The output should look like

   Using alex version 3.1.3 found on system at: /home/feuerbach/bin/alex
   Using happy version 1.19.3 found on system at: /home/feuerbach/bin/happy

3. Bump the package’s version (the fourth component is enough: e.g. 1.2.3 -> 1.2.3.1) and upload:

   cabal sdist
   cabal upload dist/$pkg-$version.tar.gz

That’s it; no actual source code modification to your package is necessary. If you’re curious as to why this works, read on.

As a user

First of all, notify the package maintainer(s) about this problem and send them a link to this article. Only they are in a position to fix the problem properly.

Until the maintainer(s) react, you can fix the problem locally as follows:

1. Get into the source tree:

   cabal get $pkg
   cd $pkg-$version

   (If cabal says it doesn’t know about the get command, you have to update it with

   cabal install cabal-install

   The command was called unpack before, but since you are using GHC 7.8 now, the older versions of cabal will get you in trouble anyway.)

2. Now that you’re in the source tree, run

   cabal clean

   You may think «but I’ve just downloaded a fresh copy of the package’s source — surely it is clean!» Not really; read on for the details.

3. Finally,

   cabal install

   should run without any alex- or happy-related errors.

What’s going on here?

Code produced by old Happy and Alex no longer builds

Because Alex and Happy strive to produce the most efficient code, they make use of unboxed types and primitives. And those are affected by certain changes in GHC 7.8:

• PrimOps for comparing unboxed values now return Int# instead of Bool
• Lazy unlifted bindings are an error now. For background on this one, see #2806, #3278 and #8022.

Happy and Alex were then updated to generate code that builds with the new GHC. So, it seems, just updating happy/alex should do the trick. Not so fast!

cabal includes generated code in the source distribution

When cabal creates a source distribution for uploading to hackage (cabal sdist), it runs happy/alex on all included .x and .y modules and includes their output in the tarball. So even when you have the new alex and happy installed, cabal install will not see the need to regenerate .hs files from .x and .y sources, and will run into the errors described above.

That’s why maintainers have to re-upload their tarballs generated with new alex and happy; and until they do, users have to run cabal get and cabal clean.

The rationale behind this cabal behavior is not to force users install alex or happy. Alas, it doesn’t work so well in practice:

Dec 09 19:37:21 dcoutts refold: there's a few problems with our shipped pre-processed sources system
Dec 09 19:37:41 dcoutts it doesn't interact well with using  build-tools: happy
Dec 09 19:38:03 dcoutts if there are shipped sources then obviously we do not need happy
Dec 09 19:38:14 dcoutts the shipped sources currently go in dist
Dec 09 19:38:18 dcoutts that then fails if you clean
Dec 09 19:38:33 dcoutts it only allows one instance of shipped sources
Dec 09 19:38:52 dcoutts e.g. for happy & alex, they can produce ghc-specific output or generic output
Dec 09 19:39:20 dcoutts this is less of a problem these days since in practice there are not other compilers
Dec 09 19:40:19 dcoutts and then this new problem, if we do ship sources, we don't know what version of the
                pre-processor generated them, so we cannot easily hack around version incompatibilities
Dec 09 19:40:21 refold  yes, using dist is hack
Dec 09 19:40:30 dcoutts the plan was to use a different dir
Dec 09 19:40:31 refold  also fails with a different --builddir
Dec 09 19:40:34 dcoutts right

See also #130 and #1685.

March 07, 2014 10:00 PM

[yheyrtgq] Factorial via GMP?

Amongst the many ways of implementing the factorial function in Haskell (Evolution of a Haskell programmer), I have yet to see one that calls the GNU MP function mpz_fac_ui on the internal implementation of Integer. (Of course, such an implementation would not be portable.)  That implementation is quite heavily algorithmically optimized, most notably by organizing the computation (binary splitting) to take advantage of subquadratic multiplication of two large multiplicands, which the tenured professor's method product [1..n] does not do.

Previously, benchmarking mpz_fac_ui on very large inputs from C++.

In the vein of wanting bindings to GMP, we would also like access to mpz_export and mpz_import for fast conversion to ByteStrings.

Someday, I may write these.

by Ken (noreply@blogger.com) at March 07, 2014 06:17 PM

Propositions as Types

Propositions as Types
Philip Wadler
Draft, March 2014

The principle of Propositions as Types links logic to computation. At first sight it appears to be a simple coincidence---almost a pun---but it turns out to be remarkably robust, inspiring the design of theorem provers and programming languages, and continuing to influence the forefronts of computing. Propositions as Types has many names and many origins, and is a notion with depth, breadth, and mystery.

Comments solicited!

by Philip Wadler (noreply@blogger.com) at March 07, 2014 04:02 PM

Jammed, the simple traffic simulator

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.

by sinelaw at March 06, 2014 04:15 AM

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.

March 05, 2014 07:12 PM

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           Control.Monad            (void)
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.

March 05, 2014 06:44 PM

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.

by nomeata (mail@joachim-breitner.de) at March 05, 2014 03:43 PM

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).

Comments welcome!

by Philip Wadler (noreply@blogger.com) at March 05, 2014 02:02 PM

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?

by Luke at March 05, 2014 12:40 AM

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.

by Mark Dominus (mjd@plover.com) at March 05, 2014 12:00 AM

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 04, 2014 10:00 PM

GHC 7.8.1 RC2

Today, GHC 7.8.1 RC2 has been released.

• Binaries and sources
• Documentation (user guide and API)

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!

by austin at March 03, 2014 06:24 PM

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:

• Danny Navarro and Chris Catalfo are working on tasty-html;
• Tyler Huffman is going to improve the HSpec test provider.

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,

operation-dependency-streamline. roll your own copies of code and types instead of depending on different packages.

— Vincent Hanquez (@vincenthz) February 27, 2014

<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.

March 02, 2014 10:00 PM

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 a
with 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 a

with 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.

by Ben Lippmeier (noreply@blogger.com) at March 02, 2014 11:26 AM

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.

by Mark Dominus (mjd@plover.com) at March 01, 2014 09:55 PM

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.

March 01, 2014 12:57 PM

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

by Johan Tibell (noreply@blogger.com) at March 01, 2014 10:09 AM

'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?)

by geophf (noreply@blogger.com) at February 28, 2014 06:39 PM

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

February 27, 2014 10:09 PM

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

February 27, 2014 01:20 PM

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.)

by Mark Dominus (mjd@plover.com) at February 27, 2014 04:56 AM

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.

February 26, 2014 09:36 PM

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.

February 26, 2014 05:34 PM

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

February 26, 2014 01:54 PM

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.

by alson at February 26, 2014 02:25 AM

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

by Wolfgang Jeltsch at February 25, 2014 10:24 PM

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!

by Jon Kristensen at February 25, 2014 07:14 PM

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.)

by Kevin Reid (kpreid) (kpreid@switchb.org) at February 25, 2014 04:23 PM

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])

February 25, 2014 12:00 AM

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.

Screenshot of profiteur

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 25, 2014 12:00 AM

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.

by Neil Mitchell (noreply@blogger.com) at February 24, 2014 10:02 PM

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.

February 24, 2014 05:16 PM

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.

February 24, 2014 03:03 PM

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 purposes¹, 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 24, 2014 12:00 AM

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

by Marcos (noreply@blogger.com) at February 23, 2014 03:24 AM

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.

by Paul Johnson (noreply@blogger.com) at February 22, 2014 02:46 PM

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".

by Philip Wadler (noreply@blogger.com) at February 22, 2014 12:07 PM

[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.

by Ken (noreply@blogger.com) at February 22, 2014 12:50 AM

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

lim_n (1 - 1 / 2ⁿ) 

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?

by geophf (noreply@blogger.com) at February 21, 2014 06:31 PM

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)

by geophf (noreply@blogger.com) at February 21, 2014 04:02 PM

Using Images in Haddock Documentation on Hackage

Using Images in Haddock Documentation on Hackage

February 21, 2014

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.

haskell

<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 21, 2014 03:53 PM

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 18, 2014 07:10 AM

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 17, 2014 10:56 AM

Announcing mono-traversable, chunked-data, and conduit-combinators

I'm happy to announce the release of a number of packages today, in particular:

• mono-traversable 0.3
• chunked-data 0.1 (first release)
• conduit-combinators 0.1 (first release)
• classy-prelude, classy-prelude-conduit, and classy-prelude-yesod 0.8

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!

February 16, 2014 09:44 AM

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!

by magnusth at February 16, 2014 08:47 AM

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!

by JP Moresmau (noreply@blogger.com) at February 14, 2014 12:54 PM

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,

February 14, 2014 12:00 AM

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!

Just add the following and start the download:

[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

by magnusth at February 12, 2014 08:58 PM

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)
import GHC.Conc (labelThread)

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"
  threadDelay 5000000
  putStrLn "BLIP"

main :: IO ()
main = do
  a1 <- async' "evens" $ mapM_ printFib [30, 32 .. 38]
  a2 <- async' "odds"  $ mapM_ printFib [31, 33 .. 39]
  threadDelay 5000000
  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 A–X. 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.

by edsko, duncan at February 12, 2014 08:25 PM

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], 0xba
66c7042500004000dbba      mov word  [0x400000], 0xbadb
c7042500004000efbead0b    mov dword [0x400000], 0xbadbeef
48c7042500004000efbead0b  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 30000

tape_start:
    times TAPE_SIZE dq cell0

head 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 0
cont_nonzero:  dq 0
out_byte:      db 0

align 16
cell_underflow:
    jmp inc_cell

align 16
cell0:
    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
%endrep

align 16
cell_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_cell

dec_cell:
    sub qword [head], 16
    jmp test_cell

move_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, k00000001
k00000001: do_inc    k00000002
k00000002: do_branch k00000003, k00000001
k00000003: jmp exit

which blows up into something like

401205:  48c70425611240005c124000  mov qword ptr [0x401261], 0x40125c
401211:  48c704256912400022124000  mov qword ptr [0x401269], 0x401222
40121d:  e90cefffff                jmp 40012e <test_cell>

401222:  48c70425611240003f124000  mov qword ptr [0x401261], 0x40123f
40122e:  48c70425691240003f124000  mov qword ptr [0x401269], 0x40123f
40123a:  e9f6eeffff                jmp 400135 <inc_cell>

40123f:  48c70425611240005c124000  mov qword ptr [0x401261], 0x40125c
40124b:  48c704256912400022124000  mov qword ptr [0x401269], 0x401222
401257:  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!' | ./rip
Hello, world!

$ curl -s http://www.hevanet.com/cristofd/brainfuck/fib.b | ./compiler
$ ./rip
0
1
1
2
3
5
8
13
…

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!') | ./rip
Hello, 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 ./rip
Hello, 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).

by keegan (noreply@blogger.com) at February 12, 2014 05:50 AM

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 }

instance Monad (VLMonad ops) where
  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.

February 12, 2014 02:20 AM

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.

by Björn Buckwalter (noreply@blogger.com) at February 11, 2014 01:04 PM

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.

by Björn Buckwalter (noreply@blogger.com) at February 11, 2014 01:03 PM

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.

February 11, 2014 09:55 AM