Planet Haskell

December 01, 2015

Philip Wadler

Cycle path resources

<iframe allowfullscreen="" frameborder="0" height="281" mozallowfullscreen="" src="" webkitallowfullscreen="" width="500"></iframe>
A list of cycling resources, suggested by Iain Longstaff. I expect these to be a huge help in lobbying Edinburgh to build more segregated cycle paths. The video is well worth the short time it takes to view.

Protected Intersections for Bicyclists
A six-minute video on dutch style protected junctions.

A View from the Cycle Path
A dutch blog detailing the advantages of cycle paths.

Bicycle Dutch
About new infrastructure being built in the Netherlands.

Good Cycling Facility of the Week
Examples of cycling facilities drawn from the UK and the Netherlands.

by Philip Wadler ( at December 01, 2015 10:51 PM

Static vs. Dynamic Languages: A Literature Review

A thorough study by Dan Luu. From the introduction:
The summary of the summary is that most studies find very small effects, if any. However, the studies probably don’t cover contexts you’re actually interested in. If you want the gory details, here’s each study, with its abstract, and a short blurb about the study.
And from the conclusion:
Other than cherry picking studies to confirm a long-held position, the most common response I’ve heard to these sorts of studies is that the effect isn’t quantifiable by a controlled experiment. However, I’ve yet to hear a specific reason that doesn’t also apply to any other field that empirically measures human behavior. Compared to a lot of those fields, it’s easy to run controlled experiments or do empirical studies. It’s true that controlled studies only tell you something about a very limited set of circumstances, but the fix to that isn’t to dismiss them, but to fund more studies. It’s also true that it’s tough to determine causation from ex-post empirical studies, but the solution isn’t to ignore the data, but to do more sophisticated analysis. For example, econometric methods are often able to make a case for causation with data that’s messier than the data we’ve looked at here.

The next most common response is that their viewpoint is still valid because their specific language or use case isn’t covered. Maybe, but if the strongest statement you can make for your position is that there’s no empirical evidence against the position, that’s not much of a position.
Thanks for the effort you put into this epic study, Dan! Spotted via Lambda the Ultimate.

by Philip Wadler ( at December 01, 2015 08:06 PM

Castagna: A Handbook for PC Chairs

Giuseppe Castagna published a 12-page guide based on his experience chairing ECOOP 2013. It includes pithy advice such as the following.
As a side note, I suggest to send to PC members as few emails as possible and to repeat all important information in every mail: never assume that if you wrote something in a mail, then every member of the PC knows it (my personal experience was that many of the important pieces of information I wrote in my mails were missed by one ortwo members, not always the same ones).
Beppe's handbook is a useful addition to the literature on how to run a conference, including several written by members of SIGPLAN.

by Philip Wadler ( at December 01, 2015 06:43 PM

Douglas M. Auclair (geophf)

November 2015 1HaskellADay One-liners

  • November 3rd, 2015:
Why is 'a' the standard label for type-variables? If you don't care what the type is, shouldn't the type be 'eh'? #imponderables
  • November 3rd, 2015:
{-# LANGUAGE OverloadedStrings #-}import Network.HTTPtype URL = StringrespBodyAsText :: URL -> IO Stringdefine respBodyAsTextrespBodyAsText url = simpleHTTP (getRequest url) >>= getResponseBody
    • November 2nd, 2015: 
    You have f :: a -> IO b, g :: b -> IO (), h :: b -> IO AnsYou wish to sequence f, g, h as j :: a -> IO AnsDefine j points-freeDimitri Sabadie @phaazon_fmap snd . runKleisli (Kleisli g &&& Kleisli h) . f

      by geophf ( at December 01, 2015 03:12 PM

      November 2015 1HaskellADay Problems and Solutions

      November 2015

      • November 30th, 2015: Pride and Prejudice on the command-line? No. Today's #haskell problem: read in a stream The solution defines a new Kleisli arrow. ... AND Jane Austen prefers the pronouns SHE and HER. So there's that.
      • November 27th, 2015: Simply getting the command-line arguments for #BlackFriday #haskell problem ...and then there's that bonus. OH NOES! 'Simple' solution, am I right?
      • November 26th, 2015: A little worker-pool in #haskell wishes you Happy Thanksgiving from the #USA or today's problem: Erlangesque-Haskell And today, a #haskell solution says ('sez') "Go get'm Black Friday dealz, yo!" (but: caveat emptor!)
      • November 25th, 2015: Today's #haskell problem has a Secret Decoder Ring! ... as long as you use the HaHaJK-type. BREAKING: SHA1-HASH DECODED using #haskell! Reported here first show my bonnie lies over BOTH the ocean AND the sea!
      • November 24th, 2015: For today's #haskell problem we look at parsing URI ... not Andropov ... not today. Today's #haskell URI-parsing exercise makes Yuri (Andropov) SAD and MAD ... Don't worry, Yuri: URIs are just a FAD
      • November 23rd, 2015: For today's #haskell problem we ride West on ol' Silver declaiming: "JSON! Ho!" And the solution allows us to look at JSON and declaim: HA!
      • November 20th, 2015: Today's #haskell problem comes with honorable mentions and stuff! ♫ My!
        <iframe allowfullscreen="" class="YOUTUBE-iframe-video" data-thumbnail-src="" frameborder="0" height="266" src="" width="320"></iframe> 
        ... AAANNNNNDDDDD our solution, down to 4.6 seconds from 151 seconds. Not a bad start!
      • November 19th, 2015: In today's #haskell problem we say: '@geophf your RID-analyzer is SO efficient!' ... NOT! Update: today geophf cries Efficienc-me? No! Efficienc-you!
      • November 18th, 2015: Today JSON and the Argonauts sail off into the high seas of the RID to adventures beyond the Thunderdome! No...wait.
      • November 17th, 2015: Today's #haskell problem generates a report with no title... o! the irony! The solution shows Jane Austen getting her Aggro on ... even if just a little bit 
      • November 16th, 2015: New Regressive Imagery Dictionary/RID(-structure)? That means New-NEW JSON for today's #Haskell problem And there is the RID, in all its JSON-iferific glory!
      • November 13th, 2015: Today's #haskell problem–Project RIDenberg–classifies a big-ole document with FULL! ON! RID! (exclamation mandatory) Today's solution shows us that the RID is as fascinating as ... well: Mr. Wickham. (There. I said it.)
      • November 11th, 2015: Today's #haskell problem goes the Full Monty... NO! WAIT! NOT 'MONTY'! WE GO FULL RID! (Regressive Imagery Dictionary) ... annnnnndddd this #haskell solution gives us the full RID as a graph 
      • November 10th, 2015: For today's #haskell problem we look at parsing a (small) document and matching it to a (small) RID QWERTY-style! Our solution (also) answers that age-old nagging question: "What DOES the fox say?" … No, really: I need to know this.
      • November 9th, 2015: LAST week we looked at cataloguing the RID/Regressive Imagery Dictionary. Today's #haskell problem completes that. Not that every problem and every solution can be modeled as a Graph, but ... the solution-as-Graph is here: *blush
      • November 6th, 2015: Today's #haskell problem looks at the RID as Friends and Relations ... actually: it just looks at RID-as-relations Ooh! Pritty Bubblés for a solution to the RID-as-relations problem 
      • November 5th, 2015: Today's #haskell problem is to JSONify the RID because JSON, and because indentation as semantic-delimiters is weird A solution shows PRIMARY-RID-JSON in 420 lines, as opposed to the raw text at over 1800 lines. Cool story, bro!
      • November 4th, 2015: For today's #Haskell problem please Graph that RID! YEAH! I WANT YOUR SEX(y graph of the RID) poses a solution at
      • November 3rd, 2015: YESTERDAY we used a Python program to map a document to the RID in #Haskell TODAY we map part of the RID to #Haskell A solution gives us a Pathway to BACON, ... because priorities.
      • November 2nd, 2015: We look at EQ for today's #Haskell problem; not the Class Eq, but the Emotional Quotient of a document. Fun! runKleisli (from @phaazon_) and (>=>) to the rescue for the solution today

      by geophf ( at December 01, 2015 01:15 PM

      November 28, 2015

      Mark Jason Dominus

      A message to the aliens, part 19/23 (map of the Earth)

      Earlier articles: Introduction Common features Page 1 (numerals) Page 2 (arithmetic) Page 3 (exponents) Page 4 (algebra) Page 5 (geometry) Page 6 (chemistry) Page 7 (mass) Page 8 (time and space) Page 9 (physical units) Page 10 (temperature) Page 11 (solar system) Page 12 (Earth-Moon system) Page 13 (days, months, and years) Page 14 (terrain) Page 15 (human anatomy) Page 16 (vital statistics) Page 17 (DNA chemistry) Page 18 (cell respiration and division)

      These are pages 19–20 of the Cosmic Call message. An explanation follows.

      These two pages are a map of the surface of the Earth. Every other page in the document is surrounded by a one-pixel-wide frame, to separate the page from its neighbors, but the two pages that comprise the map are missing part of their borders to show that the the two pages are part of a whole. Assembled correctly, the two pages are surrounded by a single border. The matching sides of the map pages have diamond-shaped registration marks to show how to align the two pages.

      The map projection used here is R. Buckminster Fuller's Dymaxion projection, in which the spherical surface of the Earth is first projected onto a regular icosahedron, which is then unfolded into a flat net. This offers a good compromise between directional distortion and size distortion. Each twentieth of the map is distoried only enough to turn it into a triangle, and the interruptions between the triangles can be arranged to occur at uninteresting parts of the map.

      Both pages are labeled with the glyph for “Earth”. On each page, the land parts of the map are labeled with and the water parts with , as on page 14, since the recipients wouldn't otherwise be able to tell which was which.

      The next article will discuss page 21, shown at right. (Click to enlarge.) Try to figure it out before then.

      by Mark Dominus ( at November 28, 2015 12:00 AM

      November 27, 2015

      Edward Z. Yang

      What is Stateless User Interface?

      The essence of stateless user interface is that actions you take with a program should not depend on implicit state. Stateless interfaces are easier to understand, because an invocation of a command with some arguments will always do the same thing, whereas in a stateful interface, the command may do some different than it did yesterday, because that implicit state has changed and is influencing the meaning of your program.

      This philosophy is something any Haskeller should intuitively grasp... but Cabal and cabal-install today fail this ideal. Here are some examples of statefulness in Cabal today:

      1. Running cabal install, the built packages are installed into a "package database", which makes them available for use by GHC.
      2. Running cabal install, the choice of what packages and versions to install depends on the state of the local package database (the current solver attempts to reuse already installed software) and the state of the remote package repository (which says what packages and versions are available.)
      3. Running ./Setup configure saves a LocalBuildInfo to dist/setup-config, which influences further Setup commands (build, register, etc.)

      Each of these instances of state imposes complexity on users: how many times do you think you have (1) blown away your local package database because it was irreversibly wedged, (2) had your project stop building because the dependency solver started picking too new version of packages, or (3) had Cabal ask you to reconfigure because some feature wasn't enabled?

      State has cost, but it is not here for no reason:

      1. The package database exists because we don't want to have to rebuild all of our packages from scratch every time we want to build something (indeed, this is the whole point of a package manager);
      2. The solver depends on the local package database because users are impatient and want to avoid building new versions packages before they can build their software;
      3. The solver depends on the remote package repository because developers and users are impatient and want to get new releases to users as quickly possible;
      4. The configure caches its information because a user doesn't want to wait to reconfigure the package every time they try to build a package they're working on.

      In the face of what is seemingly an inherently stateful problem domain, can stateless user interface prevail? Of course it can.

      Sometimes the state is merely being used as a cache. If a cache is blown away, everything should still work, just more slowly. The package database (reason 1) and configuration cache (reason 4) both fall under this banner, but the critical mistake today's Cabal makes is that if you delete this information, things do not "just work". There must be sufficient information to rebuild the cache; e.g., the configuration cache should be supplemented with the actual input to the configure step. (Sometimes, separation of concerns means you simply cannot achieve this. What is ghc to do if you ask it to use the not-in-cache lens package?) Furthermore, the behavior of a system should not vary depending on whether or not the cached data is present or not; e.g., the solver (reason 2) should not make different (semantically meaningful) decisions based on what is cached or not.

      Otherwise, it must be possible to explicitly manage the state in question: if the state is a remote package repository (reason 3), there must be a way to pin against some state. (There's a tool that does this and it's called Stack.) While sometimes necessary, explicit state complicates interface and makes it harder to describe what the system can do. Preferably, this state should be kept as small and as centralized as possible.

      I don't think anything I've said here is particularly subtle. But it is something that you need to specifically think about; otherwise, you will be seduced by the snare of stateful interface. But if you refuse the siren call and put on the hair shirt, your users will thank you much more for it.

      Acknowledgments. These thoughts are not my own: I have to give thanks to Johan Tibell, Duncan Coutts, and Simon Marlow, for discussions which communicated this understanding to me. Any mistakes in this article are my own. This is not a call to action: the Cabal developers recognize and are trying to fix this, see this hackathon wiki page for some mutterings on the subject. But I've not seen this philosophy written out explicitly anywhere on the Internet, and so I write it here for you.

      by Edward Z. Yang at November 27, 2015 06:53 AM

      November 26, 2015

      Magnus Therning

      Trick for pre-processing source in CMake

      When using <LANG>_COMPILER_LAUCHER or RULE_LAUNCH_COMPILER the following is a nice little pattern to deal with the arguments.

      #! /usr/bin/python3
      import argparse
      import subprocess
      import sys
      # create an argumentparser for the stuff the launcher script needs, some
      # specific to it and some of the compiler arguments
      parser = argparse.ArgumentParser(description='Compiler launcher for C.')
      parser.add_argument('--flag-for-wrapper', type=str)
      parser.add_argument('-I', dest='includes', action='append', type=str, default=[])
      parser.add_argument('-D', dest='defines', action='append', type=str, default=[])
      parser.add_argument('-o', dest='output', type=str)
      parser.add_argument('-c', dest='input', type=str)
      args, rest = parser.parse_known_args(sys.argv)
      # do stuff with the source, e.g. pass it through the C pre-processor (using the
      # arguments picked out above) and then process the output
      # build another argument parser to prepare the call to the compiler
      cc_parser = argparse.ArgumentParser(description='Parser for removing launcher-specific arguments.')
      cc_parser.add_argument('--flag-for-wrapper', type=str)
      cc_cmd = cc_parser.parse_known_args(sys.argv)[1][1:]

      That is, first create a parser for launcher-specific arguments and the compiler arguments1 that are of interest to the launcher. Then perform the magic of the launcher. Finally, create another parser and use it to remove the launcher-specific arguments and use the remainder to perform the compilation.

      1. Here I’m relying on CMake always putting -c just before the source file, which seems to hold most of the time.

      November 26, 2015 12:00 AM

      November 25, 2015

      Douglas M. Auclair (geophf)

      (Really) Big Data: from the trenches

      Okay, people throw around 'big data' experience, but what is it really like? What does it feel like to manage a Petabyte of data. How do you get your hands around it? What is the magic formula that makes it all work seamlessly without Bridge Lines opened on Easter Sunday with three Vice Presidents on the line asking for status updates by the minute during an application outage?

      Are you getting the feel for big data yet?


      Big data is not terabytes, 'normal'/SQL databases like Oracle or DB2 or GreenPlum or whatever can manage those, and big data vendors don't have a qualm about handling your 'big data' of two terabytes even though they are scoffing into your purchase order.

      "I've got a huge data problem of x terabytes."

      No, you don't. You think you do, but you can manage your data just fine and not even make Hadoop hiccough.

      Now let's talk about big data.

      1.7 petabytes
      2.5 billion transactions per day.
      Oh, and growing to SIX BILLION transactions per day.

      This is my experience. When the vendor has to write a new version of HBase because their version that could handle 'any size of data, no matter how big' crashed when we hit 600 TB?

      Yeah. Big data.

      So, what's it like?

      Storage Requirements/Cluster Sizing

      1. Your data is bigger than you think it is/bigger than the server farm you planned for it.

      Oh, and 0. first.

      0. You have a USD million budget ... per month.

      Are you still here? Because that's the kind of money you have to lay out for the transactional requirements and storage requirements you're going to need.

      Get that lettuce out.

      So, back to 1.

      You have this formula, right? from the vendor that says: elastic replication is at 2.4 so for 600 TB you need 1.2 Petabytes of space.


      Wrong. Wrong. WRONG.

      First: throw out the vendors' formulae. They work GREAT for small data in the lab. They suck for big data IRL.

      Here's what happens in industry.

      You need a backup. You make a backup. A backup is the exact same size as your active HTables, because the HTables are in bz2-format already compressed.

      Double the size of your cluster for that backup-operation.

      Not a problem. You shunt that TWO PETABYTE BACKUP TO AWS S3?!?!?

      Do you know how long that takes?

      26 hours.

      Do you know how long it takes to do a restore from backup?

      Well, boss, we have to load the backup from S3. That will take 26 hours, then we ...

      Boss: No.

      me: What?

      Boss: No. DR ('disaster recovery') requires an immediate switch-over.

      Me: well, the only way to do that is to keep the backup local.

      Boss: Okay.

      Double the size of your cluster, right?


      What happens if the most recent backup is corrupted, that is, today's backup, because you're backing up every day just before the ETL-run, then right after the ETL-run, because you CANNOT have data corruption here, people, you just can't.

      You have to go to the previous backup.

      So now you have two FULL HTable backups locally on your 60-node cluster!

      And all the other backups are shunted, month-by-month, to AWS S3.

      Do you know how much 2 petabytes, then 4 petabytes, then 6 petabytes in AWS S3 costs ... per month?

      So, what to do then?

      You shunt the 'old' backups, older than x years old, every month, to Glacier.

      Yeah, baby.

      That's the first thing: your cluster is 3 times the size of what it needs to be, or else you're dead, in one month. Personal experience bears this out: first you need the wiggle room or else you stress out your poor nodes of your poor cluster, and you start getting HBase warnings and then critical error messages about space utilization, second, you need that extra space when the ETL job loads in a billion row transaction of the 2.5 billion transactions you're loading in that day.

      Been there. Done that.

      Disaster Recovery

      Okay, what about that DR, that Disaster Recovery?

      Your 60 node cluster goes down, because, first, you're not an idiot and didn't build a data center and put all those computers in there yourself, but shunted all that to Amazon and let them handle that maintenance nightmare.

      Then the VP of AWS Oregon region contacts you and tells you everything's going down in that region: security patch. No exceptions.

      You had a 24/7 contract with 99.999% availability with them.

      Sorry, Charlie: you're going down. A hard shutdown. On Thursday.

      What are you going to do?

      First, you're lucky if Amazon tells you: they usually just do it and let you figure that out on your own. So that means you have to be ready at any time for the cluster to go down with no reason.

      We had two separate teams monitoring our cluster: 24/7. And they opened that Bridge Line the second a critical warning fired.

      And if a user called in and said the application was non-responsive?

      Ooh, ouch. God help you. You have not seen panic in ops until you see it when one user calls and come to find it's because the cluster is down with no warning catching that.

      Set up monitoring systems on your cluster. No joke.

      With big data, your life? Over.


      Not an issue. Or, it becomes an issue when you're shunting your backup to S3 and the cluster gets really slow. We had 1600 users that we rolled out to, we stress-tested it, you know. Nobody had problems during normal operations, it's just that when you ask the cluster to do something, like ETL or backup-transfer, that engages all disks of all nodes in reads and writes.

      A user request hits all your region servers, too.

      Do your backups at 2 am or on the weekends. Do your ETL after 10 pm. We learned to do that.


      Amazon is perfect; Amazon is wonderful; you'll never have to maintain nor monitor your cluster again! It's all push-of-the-button.

      I will give Amazon this: we had in-house clusters with in-house teams monitoring our clusters, 'round the clock. Amazon made maintenance this: "Please replace this node."

      Amazon: "Done."

      But you can't ask anything other than that. Your data on that node? Gone. That's it, no negotiations. But Hadoop/HBase takes care of that for you, right? So you're good, right?

      Just make sure you have your backup/backout/DR plans in place and tested with real, honest-to-God we're-restarting-the-cluster-from-this-backup data or else you'll never know until you're in hot water.


      Every vendor will promise you the Moon ... and 'we can do that.' Every vendor believes it.

      Then you find out what's what. We did. Multiple times, multiple vendors. Most can't handle our big data when push came to shove, even though they promised they can handle data of any size. They couldn't. Or they couldn't handle it in a manageable way: if the ETL process takes 26 hours and it's daily, you're screwed. Our ETL process got down to 1.5 hours, but that was after some tuning our their part and on ours: we had four consultants from the vendor in-house every day for a year running. Part of our contract-agreement. If you are blazing the big data trail, your vendor is, too: we were inventing stuff on the fly just to manage the data coming in, and to ensure the data came out in quick, responsive ways.

      You're going to have to do that, too, with real big data, and that costs money. Lots.

      And, ... but it also costs cutting through what vendors are saying to you, and what their product can actually handle. Their sales people have their sales-pitch, but what really happened is we had to go through three revisions of their product just so it could be an Hadoop HBase-compilant database that could handle 1.7 petabytes of data.

      That's all.

      Oh, and grow by 2.5 billion rows per day.

      Which leads to ...

      Backout/Aging Data

      Look, you have big data. Some of it's relevant today, some of it isn't. You have to separate the two, clearly and daily, if you're not, then a month, two months, two years down the road you're screwed, because you're now dealing with a full-to-the-gills cluster AND having to disambiguate data you've entangled, haven't you? with the promise of looking at aging data gracefully ... 'later.'

      Well, later is right now, and your cluster is full and in one month it's going critical.

      What are you going to do?

      Have a plan to age data. Have a plan to version data. Have a data-correction plan.

      These things can't keep being pushed off to be considered 'later' because 'later' will be far too late, and you'll end up crashing your cluster (bad) or corrupting your data when you slice and dice it the wrong way, come to find (much, much worse). Oh, and version your backups, tying them to the application version, because when you upgrade your application, your data gets all screwy, being old, or your new data format on your old application when somebody pulls up a special request to view three-year-old data is all screwy.

      Have a very clear picture of what your users need, the vast majority of the time, and deliver that and no more.

      We turned a 4+hour query that terminated when it couldn't deliver a 200k+ row query on GreenPlum...

      Get that? 4+hours to learn your query failed.

      No soup for you.

      To a 10 second query against Hadoop HBase that returns 1M+ rows.

      Got that?

      We changed peoples' lives. What was impossible before for our 1600 users was now in hand in 10 seconds.

      But why?

      Because we studied all their queries.

      One particular query was issued 85% of the time.

      We built our Hadoop/HBase application around that, and shunted the other 15% of the queries other tools that could manage that load.

      Also, we studied our users: all their queries were in transactions of within the last month.

      We kept two years of data on-hand.


      And that two years grew to more, month by month.


      We had no graceful data aging/versioning/correcting plans, so, 18 months into production we were faced with a growing problem.

      Growing daily.

      The users do queries up to a month? No problem: here's your data in less than 10 seconds, guaranteed. You want to do research, you put in a request.

      Your management has to put their foot down. They have to be very clear what this new-fangled application is delivering and the boundaries on what data they get.

      Our management did, for the queries, and our users loved us. You put in a query and it takes four hours, and only 16 queries are allowed against the system to run at any one time to: anyone, anywhere can submit a query and it returns right away?

      Life-changing, and we did psychological studies as well as user-experience studies, too, so I'm not exaggerating.

      What our management did not do is put bounds on how far back you could go into the data set. The old application had a 5 year history, so we thought two years was good. It wasn't. Everybody only queried on today, or yesterday, or, rarely: last week or two weeks ago. We should have said: one month of data. You want more, submit a request to defrost that old stuff. We didn't and we paid for it in long, long meetings around the problem of how to separate old data from new and what to do to restore old data, if, ever (never?) a request for old data came. If we had a monthly shunt to S3 then to Glacier, that would have been a well-understood and automatic right-sizing from the get-go.

      You do that for your big data set.

      Last Words

      Look. There's no cookbook or "Big Data for Dummies" that is going to give you all the right answers. We had to crawl through three vendors to get to one who didn't work out of the box but who could at least work with us, night and day, to get to a solution that could eventually work with our data set. So you don't have to do that. We did that for you.

      You're welcome.

      But you may have to do that because you're using Brand Y not our Brand X or you're using Graph databases, not Hadoop, or you're using HIVE or you're using ... whatever. Vendors think they've seen it all, and then they encounter your data-set with its own particular quirks.

      Maybe, or maybe it all will magically just work for you.

      And let's say it does all magically work, and let's say you've got your ETL tuned, and your HTables properly structured for fast in-and-out operations.

      Then there's the day-to-day daily grind of keeping a cluster up and running. If your cluster is in-house ... good luck with that. Have your will made out and ready for when you die from stress and lack of sleep. If your cluster is from an external vendor, just be ready for the ... eh ... quarterly, at least, ... times they pull the rug out from under you, sometimes without telling you and sometimes without reasonably fair warning time, so it's nights and weekends for you to prep with all hands on deck and everybody looking at you for answers.

      Then, ... what next?

      Well: you have big data? It's because you have Big Bureaucracy. The two go together, invariably. That means your Big Data team is telling you they're upgrading from HBase 0.94 to HBase whatever, and that means all your data can go bye-bye. What's your transition plan? We're phasing in that change next month.

      And then somebody inserts a row in the transaction, and it's ... wrong.

      How do you tease a transaction out of an HTable and correct it?

      An UPDATE SQL statement?

      Hahaha! Good joke! You so funny!

      Tweep: "I wish twitter had an edit function."

      Me: Hahaha! You so funny!

      And, ooh! Parallelism! We had, count'm, three thousand region servers for our MapReduce jobs. You got your hands around parallelism? Optimizing MapReduce? Monitoring the cluster as the next 2.5 billion rows are processed by your ETL-job?

      And then a disk goes bad, at least once a week? Stop the job? Of course not. Replace the disk (which means replacing the entire node because it's AWS) during the op? What are the impacts of that? Do you know? What if two disks go down during an op?

      Do you know what that means?

      At replication of 2.4, two bad disks means one more disk going bad will get you a real possibility of data corruption.

      How's your backups doing? Are they doing okay? Because if they're on the cluster now your backups are corrupted. Have you thought of that?

      Think about that.

      And, I think I've given enough experience-from-the-trenches for you to think on when spec'ing out your own big data cluster. Go do that and (re)discover these problems and come up with a whole host of fires you have to put out on your own, too.

      Hope this helped. Share and enjoy.

      cheers, geophf

      by geophf ( at November 25, 2015 01:23 AM

      November 23, 2015

      Magnus Therning

      Elm 0.16 with stack

      I just noticed that there’s been a new release of the elm tools. The previous release was fairly easy to build using stack, but this release made it a little bit easier still.

      The script for cloning should be modified to look like this:

      #! /usr/bin/zsh
      repos=("git clone -b 0.16"
             "git clone -b 0.16"
             "git clone -b 0.16"
             "git clone -b 0.16"
             "git clone -b 0.16"
      for r in ${repos[@]}; do
          eval ${r}

      When creating the inital stack.yaml tell stack to use release 7.10.2 of ghc:

      % stack init --resolver ghc-7.10.2

      That makes it possible to use the installed version of ghc. It’s also unecessary to provide any flag for aeson, which means there’s no need for any manual changed to stack.yaml prior to running (add --install-ghc if you don’t have it on your system already)

      % stack solver --modify-stack-yaml

      Now just build and install as before:

      % stack install elm-{compiler,make,package,repl}
      % stack install elm-reactor

      That’s it!

      November 23, 2015 12:00 AM

      November 21, 2015

      Leon P Smith

      Announcing linux-inotify 0.3

      linux-inotify is a thin binding to the Linux kernel’s file system notification functionality for the Glasgow Haskell Compiler. The latest version does not break the interface in any way, but the implementation eliminates use-after-close file descriptor faults, which are now manifested as IOExceptions instead. It also adds thread safety, and is much safer in the presence of asynchronous exceptions.

      In short, the latest version is far more industrial grade. It is the first version I would not hesitate to recommend to others, and the first version I have talked much about publicly. The only downside is that it does require GHC 7.8 or later, due to the use of threadWaitReadSTM to implement blocking reads.

      File Descriptor Allocation

      These changes were motivated by lpsmith/postgresql-simple#117, one of the more interesting bugs I’ve been peripherally involved with. The upshot is that it’s very probably a use-after-close descriptor fault: a descriptor associated with a websocket would close, that descriptor would be associated with a new description that would be a database connection, and then a still-active websocket thread would ping the database connection, causing the database server to hang up due to a protocol error. Thus, a bug in snap and/or websockets-snap manifested itself in the logs of a database server.

      This issue did end up exposing a significant deficiency in my understanding of the allocation of file descriptors: for historical reasons, the POSIX standard specifies that a new description must be indexed by the smallest unused descriptor.

      This is an unfortunate design from several standpoints, as it necessitates more serialization than would otherwise be required, and a scheme that seeks to delay reusing descriptors as long as practical would greatly mitigate use-after-close faults, as they would almost certainly manifest as an EBADF errno instead of a potentially catastrophic interaction with an unintended description.

      In any case, one of the consequences of the POSIX standard is that a use-after-close descriptor fault is a pretty big deal, especially in a server with a high descriptor churn rate. In this case, the chances of an inappropriate interaction with the wrong descriptor is actually pretty likely.

      Thus, in the face of new evidence, I revised my opinion regarding what the linux-inotify binding should provide; in particular protection against use-after-close. And in the process I made the binding safer in the presence of concurrency and asynchronous exceptions.

      The Implementation

      Due to the delivery of multiple inotify messages in a single system call, linux-inotify provides a buffer behind the scenes. The new implementation has two MVar locks: one associated with the buffer, and another associated with the inotify descriptor itself.

      Four functions take only the descriptor lock: addWatch, rmWatch, close, and isClosed. Four functions take the buffer lock, and may or may not take the descriptor lock: getEvent, peekEvent, getEventNonBlocking, and peekEventNonBlocking. Two functions only ever take the buffer lock: getEventFromBuffer and peekEventFromBuffer.

      The buffer is implemented in an imperative fashion, and the lock protects all the buffer manipulations. The existence of the descriptor lock is slightly frustrating, as the only reason it’s there is to correctly support the use-after-close protection; the kernel would otherwise be able to deal with concurrent calls itself.

      In this particular design, it’s important that neither of these locks are held for any significant length of time; in particular we don’t want to block while holding either one. This is so that the nonblocking functions are actually nonblocking: otherwise it would be difficult for getEventNonBlocking to not block while another call to getEvent is blocked on the descriptor.

      So looking at the source of getEvent, the first thing it does is to take the buffer lock, then checks if the buffer is empty. If the buffer not empty, it returns the first message without ever taking the descriptor lock. If the buffer is empty, it then also takes the descriptor lock (via fillBuffer) and attempts to read from the descriptor. If the descriptor has been closed, then it throws an exception. If the read would block, then it drops both locks and then waits for the descriptor to become readable before it tries again. And of course if the read succeeds, then we grab the first message, then drop the locks, and return the message.

      getEvent :: Inotify -> IO Event
      getEvent inotify@Inotify{..} = loop
          funcName = "System.Linux.Inotify.getEvent"
          loop = join $ withLock bufferLock $ do
                     start <- readIORef startRef
                     end   <- readIORef endRef
                     if start < end
                     then (do
                              evt <- getMessage inotify start True
                              return (return evt)                  )
                     else fillBuffer funcName inotify
                          -- file descriptor closed:
                             (throwIO $! fdClosed funcName)
                          -- reading the descriptor would block:
                             (\fd -> do
                                  (waitRead,_) <- threadWaitReadSTM fd
                                  return (atomically waitRead >> loop) )
                          -- read succeeded:
                                  evt <- getMessage inotify 0 True
                                  return (return evt)                  )

      So there are two points of subtlety worth pointing out in this implementation. First is the idiom used in loop: the main body returns an IO (IO Event), which is turned into IO Event via join. The outer IO is done inside a lock, which computes an (IO Event) to perform after the lock(s) are dropped.

      The second point of subtlety is the case where the read would block. You may want to think for a minute why I didn’t write this instead:

      \fd -> do
         return (threadWaitRead fd >> loop)

      Because we don’t want to block other operations that need the buffer and/or file descriptor locks, we need to drop those locks before we wait on the descriptor. But because we are dropping those locks, anything could happen before we actually start waiting on the descriptor.

      In particular, another thread could close the descriptor, and the descriptor could be reused to refer to an entirely new description, all before we start waiting. Essentially, that file descriptor is truly valid only while we hold the descriptor lock; thus we need to go through the process of registering our interest in the file descriptor while we have the lock, and then actually blocking on the descriptor after we have released the lock.

      Now, this race condition is a relatively benign one as long as the new description either becomes readable relatively quickly, or that the descriptor is closed and GHC’s IO manager is aware the fact. In the first case, the threadWaitRead fd will unblock, and the thread will loop and realize that the descriptor has been closed, and throw an exception. In the second case, GHC’s IO manager will cause threadWaitRead fd to throw an exception directly.

      But if you get very unlucky, this might not happen for a very long time, if ever, causing deadlock. This might be the case if say, the new descriptor is a unix socket to /dev/log. Or, if the reallocated descriptor is managed by foreign code, and is closed without GHC’s IO manager being made aware, it is quite possible that this could deadlock.

      by lpsmith at November 21, 2015 09:13 AM

      November 19, 2015

      FP Complete

      Kubernetes for Haskell Services

      Kubernetes (AKA "k8s")

      From Kubernetes is an open source orchestration system for Docker containers. It handles scheduling onto nodes in a compute cluster and actively manages workloads to ensure that their state matches the users declared intentions. Using the concepts of "labels" and "pods", it groups the containers which make up an application into logical units for easy management and discovery.

      We use it to host some of our web applications at FP Complete. In this article we will show you how to deploy a Kubernetes cluster to Amazon's AWS cloud, create a Haskell web application, build the application with Stack and finally deploy the application with Docker & Kubernetes. The whole process should take about 10 minutes.

      Download the command line interface kubectl here (the binary CLI for your OS will be found in the tarball). You'll need this executable in order to interact with your deployed Kubernetes cluster. Download it now & make sure it's in your PATH.

      If you are curious about all the things you can do with Kubernetes, you can find the documentation online. There's also an active mail-list and IRC channel.

      kube-aws Deployment Tool

      The CoreOS team has created a nice AWS CloudFormation tool for deploying working clusters of Kubernetes on AWS with ease. This is much simpler than my blog post from last winter (shows the guts of a CloudFormation deployment with CoreOS & Kubernetes.) These days all we need is one command line tool & a tiny yaml manifest file.

      Download the command line tool here and put it in your PATH.

      Deploy Kubernetes

      Setup your AWS environment variables

      Make sure you have at least the following environment variables set:


      Create a folder for the new cluster

      This will house the TLS certificates & configuration for communicating with Kubernetes after launch.

      mkdir -p ~/.kube/clusters/kube/
      cd ~/.kube/

      Create a ~/.kube/clusters/kube/cluster.yaml manifest file

      This file will be used by kube-aws when launching a cluster (or destroying a cluster. See kube-aws --help for more options.)

      # cluster name is whatever you want it to be
      clusterName: kube
      # the key name is, of course, the aws key-pair name
      keyName: kubernetes
      # pick a region and availability zone
      region: us-west-2
      availabilityZone: us-west-2a
      # pick a domain name for your cluster
      # pick the size of your cluster
      workerCount: 3

      Launch with kube-aws

      Once our manifest is ready we can launch our cluster.

      kube-aws up --config=~/.kube/clusters/kube/cluster.yaml

      This will output the IP address of the master node. Take note of the IP address for the next step.

      Set a DNS A record for the Kubernetes IP address

      Set an external DNS 'A' record with master node's IP address. IN A <<IPADDRESS>>

      If you don't have control of DNS for a domain, you can put an entry into your /etc/hosts file. <<IPADDRESS>>

      Configure kubectl

      Then we'll want to link the kubectl configuration file that kube-aws produced into the right spot (~/.kube/config) so we can talk to our cluster.

      ln -sf ~/.kube/clusters/kube/kubeconfig ~/.kube/config

      Interact with the Kubernetes cluster

      Everything should be ready to interact with our new cluster. Let's list the (worker) nodes. You should see 3 based on our manifest file above.

      kubectl get nodes

      Haskell Web Service

      Start a new haskell package

      Let's create a new directory for our example haskell web service. (We could have used stack new hello to create an application stub but our needs are as simple as they get. We'll just create a couple of files & our project will be complete.)

      mkdir hello
      cd hello

      Create a hello.cabal

      As with any Haskell application we need a cabal file describing the project.

      name:                hello
      version:             0.1.0
      license:             BSD3
      build-type:          Simple
      cabal-version:       >=1.10
      executable hello
        default-language:    Haskell2010
        ghc-options:         -threaded -rtsopts -with-rtsopts=-N
        main-is:             Main.hs
        build-depends:       base
                           , http-types
                           , wai
                           , warp

      Create a stack.yaml

      We also need a stack.yaml file. This sets the resolver (and the GHC version. In this case it's 7.10.2). The stack.yaml file also describes what packages we are building and it has container image settings.

      resolver: lts-3.14
      packages: [.]
          base: hello:base

      Create a Dockerfile

      In order for Stack to build our application & package a docker container, we need to setup a base image with all our application dependencies. Put anything in your base image that your application will need. In our case today, we only need libgmp which is used by most haskell applications.

      FROM ubuntu:14.04
      RUN apt-get update && apt-get install -y libgmp10

      Now we need to build & tag the base image. You most likely only need to do this once. You can optionally tag this base image & share it on DockerHub with your co-workers.

      docker build -t hello:base .

      Create a Main.hs

      Every haskell application needs it's Main module. This one simply fires up a Warp web-server on port 8080 and always serves "hello world" as plain text.

      {-# LANGUAGE OverloadedStrings #-}
      import Network.HTTP.Types (status200)
      import Network.Wai (responseLBS)
      import Network.Wai.Handler.Warp (run)
      main :: IO ()
      main =
        run 8080
            (\rq rs ->
               rs (responseLBS status200
                               "hello world"))

      Build with Stack

      This will compile your haskell executable and layer it on top of your 'base' image.

      stack image container

      You should now see a hello docker image if you list your images.

      Test the image locally

      We should now be able to run the docker image locally & see it work. Try it.

      docker run -i -t --rm -p 8080:8080 hello hello

      In another window use curl or your web-browser to access port 8080.

      curl -v http://localhost:8080

      Press ctrl-c when you are done with the local docker web-server.

      Push the image to dockerhub

      Next we'll tag the hello image with our dockerhub user prefix and a version. Then we'll push the image up to

      docker tag hello dysinger/hello:0.1.0
      docker push dysinger/hello:0.1.0

      Deploy to Kubernetes

      Now that we have our application written & published we can deploy it to our new Kubernetes cluster. In order to deploy any cluster of web-servers to Kubernetes you need two basic yaml files. One is the Replication Controller file & the other is the Service file.

      Create a hello-rc.yaml

      The Replication Controller file describes our docker container's needs (ports, volumes, number of replicas, etc). Kubernetes will use this information to maintain a number of docker containers on the cluster running your application.

      apiVersion: v1
      kind: ReplicationController
        name: hello
        replicas: 2
              app: hello
            - name: hello
              image: dysinger/hello:0.1.0
              - hello
              - name: http
                containerPort: 8080

      Create a hello-svc.yaml

      The Service file describes the external interface for your replicated application. It can optionally create a load-balancer and map ports into your replicated application. If you need your application to be exposed to the internet, then you need a Service file.

      apiVersion: v1
      kind: Service
        name: hello
          app: hello
        - name: http
          port: 80
          targetPort: http
          app: hello
        type: LoadBalancer

      Deploy the Controller & Service to Kubernetes

      Next we use the kubectl command line tool to tell Kubernetes to deploy this application. We can do it with one command.

      kubectl create -f hello-rc.yaml -f hello-svc.yaml

      Describe the running Service

      We can ask Kubernetes how the deployment went with the get subcommand.

      kubectl get pods

      You should see your new hello application being deployed (possibly not ready yet.)

      You should see 2 of our hello applications deployed on 2 of our 3 worker nodes.

      After a few minutes you should be able to get information about the applications external interface.

      kubectl describe svc hello

      This will show you the Amazon ELB DNS name. You can stick this hostname in your browser & your should see 'hello world'. You can update DNS with a CNAME from your domain to the Amazon ELB DNS name if you would like a shorter URL. CNAME <<ELB-HOSTNAME>>.

      November 19, 2015 07:00 PM

      Gabriel Gonzalez

      Interactive and composable charts

      I've added a diagrams backend to my typed-spreadsheet library which you can use to build composable graphical programs that update in response to user input.

      Here's an example program that displays a circle that changes in response to various user inputs:

      {-# LANGUAGE OverloadedStrings #-}

      import Diagrams.Backend.Cairo (Cairo)
      import Diagrams.Prelude
      import Typed.Spreadsheet

      data AColor = Red | Orange | Yellow | Green | Blue | Purple
      deriving (Enum, Bounded, Show)

      toColor :: AColor -> Colour Double
      toColor Red = red
      toColor Orange = orange
      toColor Yellow = yellow
      toColor Green = green
      toColor Blue = blue
      toColor Purple = purple

      main :: IO ()
      main = graphicalUI "Example program" logic
      logic = combine <$> radioButton "Color" Red [Orange .. Purple]
      <*> spinButtonAt 100 "Radius" 1
      <*> spinButton "X Coordinate" 1
      <*> spinButton "Y Coordinate" 1

      combine :: AColor -> Double -> Double -> Double -> Diagram Cairo
      combine color r x y =
      circle r # fc (toColor color) # translate (r2 (x, -y))

      Here is a video showing the example program in action:

      <iframe allowfullscreen="allowfullscreen" frameborder="0" height="315" src="" width="420"></iframe>


      The first half of the main function (named logic) requests four users inputs to parametrize the displayed circle:

      • A radio button for selecting the circle's color
      • A spin button for controlling radius which defaults to 100 (pixels)
      • A spin button for controlling the x coordinate for the center of the circle
      • A spin button for controlling the y coordinate for the center of the circle

      Each of these inputs is an Updatable value and we can express that using Haskell's type system:

      radioButton      "Color"        Red [Orange .. Purple] :: Updatable AColor
      spinButtonAt 100 "Radius" 1 :: Updatable Double
      spinButton "X Coordinate" 1 :: Updatable Double
      spinButton "Y Coordinate" 1 :: Updatable Double

      The Updatable type implements Haskell's Applicative interface, meaning that you can combine smaller Updatable values into larger Updatable values using Applicative operations.

      For example, consider this pure function that consumes four pure inputs and produces a pure diagram:

      :: AColor
      -> Double
      -> Double
      -> Double
      -> Diagram Cairo

      Normally if we compute a pure function we would write something like this:

      combine Green 40 10 20
      :: Diagram Cairo

      However, this result is static and unchanging. I would like to transform this function into one that accepts Updatable arguments and produces an Updatable result.

      Fortunately, Haskell's Applicative interface lets us do just that. We can lift any pure function to operate on any type that implements the Applicative interface like the Updatable type. All we have to do is separate the function from the first argument using the (<$>) operator and separate each subsequent argument using the (<*>) operator:

      combine <$> radioButton      "Color"        Red [Orange .. Purple]
      <*> spinButtonAt 100 "Radius" 1
      <*> spinButton "X Coordinate" 1
      <*> spinButton "Y Coordinate" 1
      :: Updatable (Diagram Cairo)

      Now the combine function accepts four Updatable arguments and produces an Updatable result! I can then pass this result to the graphicalUI function which builds a user interface from any Updatable Diagram:

      graphicalUI :: Text -> Updatable Diagram -> IO ()

      main = graphicalUI "Example program" logic

      The Applicative operations ensure that every time one of our primitive Updatable inputs change, the composite Updatable Diagram immediately reflects that change.


      One reason I wanted diagrams integration was to begin building interactive charts for typed spreadsheets. I'll illustrate this using a running example where I building up a successively more complex chart piece-by-piece.

      Let's begin with a simple rectangle with an adjustable height (starting at 100 pixels):

      {-# LANGUAGE OverloadedStrings #-}

      import Diagrams.Backend.Cairo (Cairo)
      import Diagrams.Prelude
      import Typed.Spreadsheet

      import qualified Data.Text as Text

      bar :: Int -> Updatable (Diagram Cairo)
      bar i = fmap buildRect (spinButtonAt 100 label 1)
      buildRect height = alignB (rect 30 height)

      label = "Bar #" <> Text.pack (show i)

      main :: IO ()
      main = graphicalUI "Example program" (bar 1)

      When we run this example we get a boring chart with a single bar:

      <iframe allowfullscreen="allowfullscreen" frameborder="0" height="315" src="" width="420"></iframe>

      However, the beauty of Haskell is composable abstractions like Applicative. We can take smaller pieces and very easily combine them into larger pieces. Each piece does one thing and does it well, and we compose them to build larger functionality from sound building blocks.

      For example, if I want to create a bar chart with five individually updatable bars, I only need to add a few lines of code to create five bars and connect them:

      {-# LANGUAGE OverloadedStrings #-}

      import Diagrams.Backend.Cairo (Cairo)
      import Diagrams.Prelude
      import Typed.Spreadsheet

      import qualified Data.Text as Text

      bar :: Int -> Updatable (Diagram Cairo)
      bar i = fmap buildRect (spinButtonAt 100 label 1)
      buildRect height = alignB (rect 30 height)

      label = "Bar #" <> Text.pack (show i)

      bars :: Int -> Updatable (Diagram Cairo)
      bars n = fmap combine (traverse bar [1..n])
      combine bars = alignX 0 (hcat bars)

      main :: IO ()
      main = graphicalUI "Example program" (bars 5)

      This not only creates a bar chart with five bars, but also auto-generates a corresponding input cell for each bar:

      <iframe allowfullscreen="allowfullscreen" frameborder="0" height="315" src="" width="420"></iframe>

      Even better, all the inputs are strongly typed! The program enforces that all inputs are well-formed and won't let us input non-numeric values.

      We also benefit from all the features of Haskell's diagrams library, which is an powerful Haskell library for building diagrams. Let's spruce up the diagram a little bit by adding color, spacing, and other embellishments:

      {-# LANGUAGE FlexibleContexts  #-}
      {-# LANGUAGE TypeFamilies #-}
      {-# LANGUAGE OverloadedStrings #-}

      import Diagrams.Backend.Cairo (Cairo)
      import Diagrams.Prelude
      import Typed.Spreadsheet

      import qualified Data.Text as Text

      bar :: Int -> Updatable (Diagram Cairo)
      bar i = fmap buildBar (spinButtonAt 100 label 0.2)
      color = case i `mod` 3 of
      0 -> red
      1 -> green
      2 -> yellow

      buildBar height =
      ( alignB ( vine
      <> bubbles
      <> alignB ( roundedRect 25 (height - 5) 5 # fc white
      <> roundedRect 30 height 5 # fc color
      stepSize = 15

      vine = strokeP (fromVertices (map toPoint [0..height]))
      toPoint n = p2 (5 * cos (pi * n / stepSize), n)

      bubble n =
      circle radius
      # translate (r2 (0, n * stepSize))
      # fc lightblue
      radius = max 1 (min stepSize (height - n * stepSize)) / 5

      bubbles = foldMap bubble [1 .. (height / stepSize) - 1]

      label = "Bar #" <> Text.pack (show i)

      bars :: Int -> Updatable (Diagram Cairo)
      bars n = fmap combine (traverse bar [1..n])
      combine bars = alignX 0 (hsep 5 [alignL yAxis, alignL (hsep 5 bars)])

      yAxis = arrowV (r2 (0, 150))

      main :: IO ()
      main = graphicalUI "Example program" (bars 5)

      One embellishment is a little animation where bubbles fade in and out near the top of the bar:

      <iframe allowfullscreen="allowfullscreen" frameborder="0" height="315" src="" width="420"></iframe>

      We can customize the visuals to our heart's content becuse the spreadsheet and diagram logic are both embedded within a fully featured programming language.


      The typed-spreadsheet library illustrates how you can use the Haskell language to build high-level APIs that abstract way low-level details such as form building or reactive updates in this case.

      In many languages high-level abstractions come at a price: you typically have to learn a domain-specific language in order to take advantage of high-level features. However, Haskell provides reusable interfaces like Applicatives that you learn once and apply over and over and over to each new library that you learn. This makes the Haskell learning curve very much like a "plateau": initially steep as you learn the reusable interfaces but then very flat as you repeatedly apply those interfaces in many diverse domains.

      If you would like contribute to the typed-spreadsheet library you can contribute out-of-the-box charting functionality to help the library achieve feature parity with real spreadsheet software.

      You can learn more about the library by checking out:

      by Gabriel Gonzalez ( at November 19, 2015 07:03 AM

      November 18, 2015

      Philip Wadler

      Snooper's Charter could impede computer security workers in UK

      As Glyn Moody and George Danezis point out, the draft bill effectively makes it a crime to reveal the existence of government hacking. Along the way, the new law would also make it illegal to discuss the existence or nature of warrants with anyone under any circumstances, including in court or with your MP, no matter what’s been happening. The powers are sweeping, absolute, and carefully put beyond public scrutiny, effectively for ever. There’s no limitation of time.
      Let’s say I’m a security researcher, digging into some unusual behaviour in a router on behalf of a major telecoms client. I discover a security hole into which somebody has installed a backdoor. Whoever it was didn’t leave a calling card: they rarely do.
      What would I do if I found that backdoor today? The ethical thing is to check my results with trusted colleagues, tell my client, determine what the best remedial action is, tell whoever is in charge of that aspect of the router software, allow time for a patch to propagate out, then tell the world what happened. It’s interesting, but not immediately important, to work out who did the attack. Fix first, ask questions later.
      Let’s look at that in a world where the Snooper's Charter has become law. I find the backdoor and tell a colleague. She doesn’t answer my e-mail, but I get a knock at the door—turns out that GCHQ was behind the attack. I am now banned forever from mentioning to anyone what I found—or that I found anything. The backdoor is later exploited by the bad guys and my client is hit. Why didn’t you find it, they ask? I can only shrug. Soon, my consultancy is in disarray. If I’m sued for incompetence, I cannot defend myself. I can write no papers, warn no people.What would I do if I found that backdoor today? The ethical thing is to check my results with trusted colleagues, tell my client, determine what the best remedial action is, tell whoever is in charge of that aspect of the router software, allow time for a patch to propagate out, then tell the world what happened. It’s interesting, but not immediately important, to work out who did the attack. Fix first, ask questions later.

      by Philip Wadler ( at November 18, 2015 03:40 PM

      Antti-Juhani Kaijanaho (ibid)

      Doctoral defense approaching, dissertation publicly available

      I will be defending my doctoral dissertation “Evidence-based programming language design: a philosophical and methodological exploration” on December 4, 2015 at noon, in the Seminarium building, auditorium S212, of the University of Jyväskylä. My opponent will be Professor Lutz Prechelt (Freie Universität Berlin, Germany), and the custos is Professor Tommi Kärkkäinen (University of Jyväskylä).

      The defense is public; anyone may come. Dress code for the audience is whatever one would wear to any lecture or regular academic activity at the university (no formal dress required). There is a Facebook event page.

      The dissertation manuscript was reviewed (for a permission to publish and defend) by Professor Matthias Felleisen (Northeastern University, USA) and Professor Andreas Stefik (University of Nevada, Las Vegas, USA). The dissertation incorporates most of my licentiate thesis, which was examined last year by Doctor Stefan Hanenberg (University of Duisburg-Essen, Germany) and Professor Stein Krogdahl (University of Oslo, Norway).

      The dissertation is now publicly available as a PDF.

      The dissertation mentions Haskell in several places, although that is not its main focus.


      Kaijanaho, Antti-Juhani
      Evidence-Based Programming Language Design. A Philosophical and Methodological Exploration.
      Jyväskylä: University of Jyväskylä, 2015, 256 p.
      (Jyväskylä Studies in Computing
      ISSN 1456-5390; 222)
      ISBN 978-951-39-6387-3 (nid.)
      ISBN 978-951-39-6388-0 (PDF)
      Finnish summary

      Background: Programming language design is not usually informed by empirical studies. In other fields similar problems have inspired an evidence-based paradigm of practice. Such a paradigm is practically inevitable in language design, as well. Aims: The content of evidence-based programming design (EB-PLD) is explored, as is the concept of evidence in general. Additionally, the extent of evidence potentially useful for EB-PLD is mapped, and the appropriateness of Cohen’s kappa for evaluating coder agreement in a secondary study is evaluated. Method: Philosophical analysis and explication are used to clarify the unclear. A systematic mapping study was conducted to map out the existing body of evidence. Results: Evidence is a report of observations that affects the strength of an argument. There is some but not much evidence. EB-PLD is a five-step process for resolving uncertainty about design problems. Cohen’s kappa is inappropriate for coder agreement evaluation in systematic secondary studies. Conclusions: Coder agreement evaluation should use Scott’s pi, Fleiss’ kappa, or Krippendorff’s alpha. EB-PLD is worthy of further research, although its usefulness was out of scope here.

      Keywords: programming languages, programming language design, evidence-based paradigm, philosophical analysis, evidence, systematic mapping study, coder agreement analysis

      by Antti-Juhani Kaijanaho at November 18, 2015 08:16 AM

      November 17, 2015

      Derek Elkins

      Behavioral Reflection

      Behavioral Reflection

      The ultimate goal of behavioral reflection (aka procedural reflection and no doubt other things) is to make a language where programs within the language are able to completely redefine the language as it executes. This is arguably the pinnacle of expressive power. This also means, though, local reasoning about code is utterly impossible, essentially by design.

      Smalltalk is probably the language closest to this that is widely used. The Common Lisp MOP (Meta-Object Protocol) is also inspired by research in this vein. The ability to mutate classes and handle calls to missing methods as present in, e.g. Ruby, are also examples of very limited forms of behavioral reflection. (Though, for the latter, often the term “structural reflection” is used instead, reserving “behavioral reflection” for things beyond mere structural reflection.)

      Very Brief History

      The seminal reference for behavioral reflection is Brian Smith’s 1982 thesis on 3-LISP. This was followed by the languages Brown, Blond, Refci, and Black in chronological order. This is not a comprehensive list, and the last time I was in to this was about a decade ago. (Sure enough, there is some new work on Black and some very new citations of Black.)

      Core Idea

      The core idea is simply to expose the state of the (potentially conceptual) interpreter and allow it to be manipulated.

      From this perspective Scheme’s call/cc is a basic, limited example of behavioral reflection. It exposes one part of the state of the interpreter and allows it to be replaced. Delimited continuations (i.e. shift and reset) are a bit more powerful. They expose the same part of the state as call/cc, but they expose it in a more structured manner that allows more manipulations beyond merely replacing it. We could imagine representing the continuation with a less opaque object than a function which would lead to Smalltalk’s MethodContext.

      Early Lisps’ fexpr was another example of exposing a different part of the interpreter state, namely the expression under evaluation. The Kernel language explores this in more depth (among other things which can likely also be classified as forms of behavior reflection.)

      For a language with mutation the heap would also be exposed. For a language without mutation, mutation can be added using the techniques from Representing Monads since something at least as powerful as delimited continuations will almost certainly be available. At that point, the heap would be first-class.

      As an aside, I like to use the word “introspection” for purely read-only access to interpreter state, and reserve the word “reflection” for when manipulations are possible. Terminologically, “reflection” is also often broken down into “structural reflection” for the widely available ability to add and remove methods to classes and similar such operations; and “behavioral” or “procedural” reflection, the ability to manipulate the language itself. To control introspection and, at least, structural reflection, mirrors can be used.


      Making a simple behaviorally reflective language is actually pretty straightforward. If you have an abstract machine for your language, all you need to do is provide one additional primitive operation which gets passed the interpreter state and returns a new interpreter state. It may be clearer and cleaner, perhaps, to split this into two operations: one, often called reify, that provides the interpreter state as a value, and another, often called reflect, that sets the interpreter state to the state represented by the given value. Note that both reify and reflect are (very) impure operations. The more tedious part is marshalling the state of the interpreter into a language level object and vice versa. In the special case of a meta-circular interpreter, this part turns out to be trivial. The following interpreter is NOT meta-circular though.

      The approach taken in this example, while simple, is very unstructured. For example, it is possible to write a procedure that when evaluated transforms the language from call-by-value (the CEK machine is an implementation of the CbV lambda calculus), to call-by name. However, to do this requires walking all the code in the environment and continuation and rewriting applications to force their first argument and delay their second argument. Primitives also need to be dealt with. It would be far nicer and cleaner to simply be able to say, “when you do an application, do this instead.” The newer behaviorally reflective languages work more like this.

      Note, despite the fact that we do a global transformation, this is not an example of lack of expressiveness. We can define this transformation locally and execute it at run-time without coordination with the rest of the code. In this sense, everything is macro expressible (a la Felleisen) because arbitrary global transformations are macro expressible.

      The Code

      You can get a copy of the full version of the code from here.

      I arbitrarily decided to start from the CEK machine: an abstract machine for the untyped call-by-value lambda calculus. (CEK stands for Control-Environment-Kontinuation, these being the three pieces of interpreter state with control being the expression driving evaluation.) While a call-by-value language is probably the way to go because both reify and reflect are very impure operations (particularly reflect), the main motivation for choosing this machine was that the state components correspond in a direct way to concepts that are natural to the programmer. Compare this to the SECD machine which stands for Stack-Environment-Control-Dump.

      The AST uses deBruijn indices.

      data Expr 
          = EVar !Int 
          | ELam Expr 
          | Expr :@: Expr

      The only types of values we have are closures. The two additional pieces of interpreter state are the environment and the continuation (the call stack).

      data Value = Closure Expr Env
      type Env = [Value]
      data Kont = Done | Arg Expr Env Kont | Fun Value Kont

      Finally the evaluator is fairly straightforward, and is a straightforward transcription of the operational semantics. Evaluation starts off with the final contination and an empty environment. With a bit of inspection you can see that evaluation is call-by-value and proceeds left-to-right. Derive Show for Expr and Value and these 15 lines of code are a complete interpreter.

      evaluate :: Expr -> Value
      evaluate e = cek e [] Done
      cek :: Expr -> Env -> Kont -> Value
      cek (EVar i)  env                         k = cek e env' k where Closure e env' = env !! i
      cek (f :@: x) env                         k = cek f env (Arg x env k)
      cek (ELam b)  env                      Done = Closure b env
      cek (ELam b)  env            (Arg x env' k) = cek x env' (Fun (Closure b env) k)
      cek (ELam b)  env (Fun (Closure b' env') k) = cek b' (Closure b env:env') k

      The first stab at adding reflective features looks like this. We add the primitive operation to reify and reflect. We’ll require them to be wrapped in lambdas so the interpreter doesn’t have to deal with unevaluated arguments when interpreting them. Note that reify doesn’t pass the Expr part to its argument. This is because the Expr part would just be EReify. The arguments of this particular application are stored, unevaluated, in the continuation as arguments needing to be evaluated. So, if we want to define quote which simply returns the expression representing it’s argument, we’ll have to dig into the continuation to get that argument.

      data Expr
          = ...
          | EReify
          | EReflect
      -- reify f = f e k
      reify = ELam EReify
      -- reflect c e k
      reflect = ELam (ELam (ELam EReflect))

      And here’s what we’d like to write in the interpreter (and is very close to what we ultimately will write.)

      cek :: Expr -> Env -> Kont -> Value
      cek EReify   (Closure b env':env) k = cek b (k:env:env') k
      cek EReflect (k:e:c:_)            _ = cek c            e k

      There are two problems with this code: one minor and one major. The minor problem is that the argument to reify takes two arguments but we can’t just pass them directly to it. We need to follow our calling convention which expects to evaluate arguments one at a time. This problem is easily fixed by pushing an Arg call stack frame onto the continuation to (trivially) evaluate the continuation.

      The major problem is that this doesn’t type check. c, e, env, and k can’t simultaneously be Values and Exprs, Envs, and Konts. We need a way to embed and project Expr, Env, and Kont value into and out of Value. The embedding is easy; you just fold over the data structure and build up a lambda term representing the Church encoding. The projection from Values is… non-obvious, to say the least.

      Instead of figuring that out, we can simply add Expr, Env, and Kont to our language as primitive types. This is also, almost certainly, dramatically more efficient.

      We extend our AST and Value.

      data Expr
          = ...
          | EInject Value
      -- Int so we can manipulate the EVar case.
      data Value = Closure Expr Env | Int !Int | Expr Expr | Env Env | Kont Kont

      The changes to the interpreter are minimal. We need to change the EVar case to handle the new kinds of values that can be returned and add a trivial EInject case. Some cases can be omitted because they would only come up in programs that would “get stuck” anyway. (In our case, “getting stuck” means pattern match failure or index out of bounds.)

      inject :: Value -> (Expr, Env)
      inject (Closure b env) = (ELam b, env)
      inject v = (EInject v, [])
      cek :: Expr -> Env -> Kont -> Value
      cek (EVar i) env k = cek e env' k where (e, env') = inject (env !! i)
      cek EReify (Closure b env':env) k = cek b (Env env:env') (Arg (EInject (Kont k)) [] k)
      cek EReflect (Kont k:Env e:Expr c:_) _ = cek c e k
      cek (EInject v) _ Done = v
      cek (EInject v) _ (Fun (Closure b' env') k) = cek b' (v:env') k

      While this interpreter achieves the goal, it is somewhat limited. We don’t have any means to manipulate the values of these new primitive types, so our manipulation of the interpreter state is limited to replacing a component, e.g. the environment, with some version of it that we got before via reify. Though it may be limited, it is not trivial. You can implement something close to call/cc if not call/cc itself.

      Still, the scenario above of turning the language into a call-by-name language doesn’t seem possible. Modifying the interpreter to support primitive operations defined in Haskell is a simple matter of programming: you add a constructor for primitive operations to the AST, you make a very slight variant of the EInject case in cek, and then you tediously make primitives corresponding to each constructor for each type and a fold for each type. See the linked source file for the details.

      The file additionally defines a pretty printer and a layer using parametric higher-order abstract syntax because humans are terrible with deBruijn indices. The end result is code that looks like this:

      one = _Suc :@ _Zero
      identity = lam (\x -> x)
      loop = lam (\x -> x :@ x) :@ lam (\x -> x :@ x)
      tailEnv = lam (\e -> paraEnv :@ e :@ _Nil 
                                        :@ lam (\_ -> lam (\x -> lam (\_ -> x))))
      tailKont = lam (\k -> paraKont :@ k :@ _Done
                                          :@ lam (\_ -> lam (\_ -> lam (\x -> lam (\_ -> x))))
                                          :@ lam (\_ -> lam (\x -> lam (\_ -> x))))
      eval = lam (\c -> reify :@ lam (\e -> lam (\k -> reflect :@ c :@ (tailEnv :@ e) :@ k)))
      quote = reify :@ lam (\e -> lam (\k -> reflect :@ (_Inject :@ c k) :@ e :@ (tailKont :@ k)))
          where c k = paraKont :@ k :@ garbage 
                                    :@ lam (\x -> (lam (\_ -> lam (\_ -> lam (\_ -> x))))) 
                                    :@ lam (\_ -> lam (\_ -> lam (\_ -> garbage)))
                garbage = _Inject :@ _Zero
      callCC = lam (\f -> reify :@ lam (\e -> lam (\k -> 
                  f :@ lam (\a -> reflect :@ (_Inject :@ a) :@ (tailEnv :@ e) :@ k))))
      example1 = evaluate $ quote :@ loop -- output looks like: Expr ((\a -> a a) (\a -> a a))
      example2 = evaluate $ eval :@ (quote :@ loop) -- loops forever
      example3 = evaluate $ callCC :@ lam (\k -> k :@ one :@ loop) -- escape before evaluating the loop
      example4 = evaluate $ callCC :@ lam (\k -> lam (\_ -> loop) :@ (k :@ one)) -- also escape before the loop

      November 17, 2015 12:54 AM

      November 16, 2015

      Erik de Castro Lopo

      Forgive me Curry and Howard for I have Sinned.

      Forgive me Curry and Howard for I have sinned.

      For the last several weeks, I have been writing C++ code. I've been doing some experimentation in the area of real-time audio Digital Signal Processing experiments, C++ actually is better than Haskell.

      Haskell is simply not a good fit here because I need:

      • To be able to guarantee (by inspection) that there is zero memory allocation/de-allocation in the real-time inner processing loop.
      • Things like IIR filters are inherently stateful, with their internal state being updated on every input sample.

      There is however one good thing about coding C++; I am constantly reminded of all the sage advice about C++ I got from my friend Peter Miller who passed away a bit over a year ago.

      Here is an example of the code I'm writing:

        class iir2_base
            public :
                // An abstract base class for 2nd order IIR filters.
                iir2_base () ;
                // Virtual destructor does nothing.
                virtual ~iir2_base () { }
                inline double process (double in)
                    unsigned minus2 = (minus1 + 1) & 1 ;
                    double out = b0 * in + b1 * x [minus1] + b2 * x [minus2]
                                    - a1 * y [minus1] - a2 * y [minus2] ;
                    minus1 = minus2 ;
                    x [minus1] = in ;
                    y [minus1] = out ;
                    return out ;
            protected :
                // iir2_base internal state (all statically allocated).
                double b0, b1, b2 ;
                double a1, a2 ;
                double x [2], y [2] ;
                unsigned minus1 ;
            private :
                // Disable copy constructor etc.
                iir2_base (const iir2_base &) ;
                iir2_base & operator = (const iir2_base &) ;
        } ;

      November 16, 2015 11:22 AM

      Eric Kidd

      Bare Metal Rust 3: Configure your PIC to handle interrupts correctly

      Want to build your own kernel in Rust? See Bare Metal Rust to get started.

      We're almost ready to write a keyboard driver in Rust! But first, we need to deal with two obstacles: setting up the PIC, and handling interrupts without crashing. This is one of the most frustrating steps, as Julia Evans explains in her hilarious and very helpful post After 5 days, my OS doesn't crash when I press a key:

      1. Turn interrupts on (sti).
      2. The OS AGAIN crashes every time i press a key. Read “I Can’t Get Interrupts Working” again. This is called “I’m receiving EXC9 instead of IRQ1 when striking a key?!” Feel on top of this.
      3. Remap the PIC so that interrupt i gets mapped to i + 32, because of an Intel design bug. This basically looks like just typing in a bunch of random numbers, but it works.
      4. 12. THE OS IS STILL CRASHING WHEN I PRESS A KEY. This continues for 2 days.

      We're going to follow Julia Evans' roadmap. (She saved me several days of suffering.) And once we're past these next few obstacles, things will get easier. Let's talk to the PIC first.

      The 8295/8295A Programmable Interrupt Controller

      We're going to with the retro approach here, and handle interrupts using the 8295 PIC. You can read all about it on the OSDev wiki, as usual. The PIC works fine in 64-bit mode, but someday, if we want to support multiple processors and I/O, we'll eventually need to support the newer APIC and IOAPIC. But for now, let's keep it simple.

      Technically, the x86 architecture has two PIC chips, usually known as PIC1 and PIC2. PIC1 handles external interrupts 0–7, and PIC2 handles 8–15. PIC2 is actually chained into interrupt 2 on PIC1, which means that we'll frequently need to talk to them as a pair.

      Unfortunately, the modern x86 architecture reserves CPU interrupts 0-31 for processor exceptions. This means that when we press a key, the CPU will think it just received the "EXC9" mentioned by Julia Evans, which the Intel manual tells me is "Coprocessor-Segment-Overrun Exception." So we need to tell our PIC that, no, McGyver and Miami Vice are no longer cutting-edge television, that there's this new-fangled thing called 386 Protected Mode, and that it needs to start mapping interrupts at offset 32.

      Read more…

      November 16, 2015 11:16 AM

      Johan Tibell

      The design of the Strict Haskell pragma

      Since the Strict Haskell pragma just landed in HEAD, thanks to the hard work of my GSoC student Adam Sandberg Ericsson, I thought I'd share my thoughts behind the design.

      First, is this making Haskell a strict language? No. This pragma lets you reverse the default on a per-module basis. Since the pragma will never be used in every module (most notably those in base) this doesn't make Haskell a strict language. Making Haskell strict is not possible at this point.

      This pragma (and its companion StrictData)

      • lets us get rid of some of the syntatic noise and error-proneness in code that needs to be (mostly) strict and

      • lets us experiment with how switching the default might affect code, in particular code with performance problems.

      The first is a quite practical "might be useful in real code soon" kind of thing and the second is a "lets do some sciene and see what happens" kind of thing.

      What's actually in GHC 8.0?

      There are two new pragmas, Strict and StrictData, where the second is a subset of the former.

      Strict makes all constructor fields and bindings (i.e. let/where/case/function arguments) strict, as if you had put a bang pattern on all of them.

      StrictData does the same, but only to constructor fields.

      Both affect only definitions in the current module. For example, using StrictData doesn't mean that the tuple types defined in base have strict fields and using Strict doesn't mean that existing fmap instances are strict, etc. Having a Strict pragma affecting other modules wouldn't make much sense, because those other modules might rely on laziness for correctness.

      See the wiki page for more details on the actual semantics and implementation.

      Practical reasons for this pragma

      Writing production quality [1] Haskell code often detracts from the beauty of Haskell. For example, instead of writing

      data Vector2 = V2 Double Double

      you need to write

      data Vector2 = V2 {-# UNPACK #-} !Double {-# UNPACK #-} !Double

      when you define a data type with small (e.g. Int or Double) fields. Even for larger fields you often want to make the field strict (and often unpacked). This syntactic noise hurts readability.

      The same applies to functions. Here's an example from unordered-containers (slightly modified for pedagogical purposes):

      insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v
      insert k v m = go h k v 0 m
          h = hash k
          go !h !k !x !_ Empty = Leaf h (L k x)

      This function is entirely strict, so all those bangs are just noise. In addition, knowing why they need to be there is not entirely obvious.

      The new Strict pragma, together with a previous change I made to unpacking, lets us write the code we want to write because

      • the Strict pragma lets us leave out the bangs but still get strict fields [2] and

      • default unpacking of small fields (see -funbox-small-strict-fields) gets us the unpacking without the pragmas.

      So with GHC 8.0 you can write e.g. the definition of Vector2 you want to write, but get the representation you need.

      When can I use this in my code?

      The first thing you should consider is whether you want to only try StrictData or also Strict. The former is a quite modest change; you're probably (mostly) using strict constructor fields anyway so using StrictData will just remove some noise and force you to be explicit about when you actually want lazy fields. I'm hoping some application developers will start using StrictData.

      Using the the Strict pragma would be a bigger change for your code base (I expect), so that should be approached with more caution. If nothing else it could be interesting to compile your own code with it and see what effect that has, both in terms of correctness (i.e. how often do you actually rely on laziness) and performance.

      So when can you actually use this stuff?

      If you're maintaing libraries that have lots of users and you need to support the three latest major GHC releases: when GHC 8.4 is out. Doing it before is probably not worth it as you'd need to use CPP. Just use bang patterns until then.

      If you're writing an application where you can pick just a single GHC version and stick with it, you can try to use Strict/StrictData as soon as GHC 8.0 is out.

      Scientific reasons for this pragma

      For quite some time I've wanted to do an emperical analysis of lazy-by-default languages, in particular on performance correctness.

      While we could compare e.g. OCaml with Haskell that's not a great comparison as the two languages differ in quite a few aspects (e.g. one uses monads as a way to control side effects, the GC implementations are different, etc).

      What I plan to do is to take a number of sample programs e.g.

      • all programs on StackOverflow tagged with "haskell" and "performance", for a selection of programs with performance problems,
      • all of nofib, or
      • all of nofib but with base compiled with Strict (or StrictData),
      • some more realistic programs,
      • etc.

      and see what happens if we compile them with Strict or StrictData.

      I'd like to look at the results along two axes: does the program produce the same result under both defaults and if it does, does the strict default change the performance? Of course, doing some analysis on the causes e.g. where do programmers rely on laziness and what's the main reason strictness affects performance would be interesting as well.

      [1] Defining "production quality code" probably deserves a whole post on its own. For the purpose of this post think of it as meaning code without surprised, in the sense that it produces the expected result using the expect computational resources. For example of of non-production quality code, consider a CSV library that needs 1.4GB of RAM to parse a 100MB CSV file.

      [2] Here's it's actually enough to use the StrictData pragma, which is a subset of the Strict pragma.

      by Johan Tibell ( at November 16, 2015 10:47 AM

      Russell O'Connor

      Stochastic Elections Canada 2015 Results

      It is time to announce the results from Stochastic Elections Canada for the 42st General Election.

      Every vote counts with the stochastic election process, so we had to wait until all election results were validated and certified before we could announce our results. However, stochastic election results are not very sensitive to small changes to the number of votes counted. The distributions for each candidate are typically only slightly adjusted.

      Now that the last judicial recount has been completed, we can announce our MP selection.

      2015 Stochastic Election Simulation Results
      Party Seats Seat Percentage Vote Percentage
      Liberal 139 41.1% 39.5%
      Conservative 105 31.1% 31.9%
      NDP-New Democratic Party 63 18.6% 19.7%
      Bloc Québécois 19 5.62% 4.66%
      Green Party 11 3.25% 3.45%
      Christian Heritage Party 1 0.296% 0.0870%

      Results by province and by riding are available (electoral districts on page 2).

      The results were generated from Elections Canada data. One hundred and seventy-four elected candidates differ from the actual 2015 election outcome.

      The Christian Heritage Party holds the balance of power in this parliament. Assuming a Liberal party member becomes speaker of the house, that means the Liberals together with the Bloc Québécois and Green Party have 168 votes and the Conservative and NDP together have 168 votes. In this case, it is the Christian Heritage Party vote that would break the tie.

      Unfortunately, Liberal leader Justin Trudeau with 52.0% of the vote in the riding of Papineau, still lost to Maxime Claveau of the Bloc Québécois with 12.2% of the vote. Apparently it is now the Bloc Québécois’s turn to represent their support in Papineau. If Justin Trudeau wants to be prime minister, his best bet is to try to be appointed to the Senate and rule from there. Similarly NDP leader Tom Mulcair lost to Liberal candidate Rachel Bendayan in the riding of Outremont. Perhaps there is a deal to be struck between the Liberal and NDP to get their leaders appointed to the Senate.

      This is only one example of the results of a stochastic election. Because of the stochastic nature of the election process, actual results may differ.

      In Canada’s election process, it is sometimes advantageous to not vote for one’s preferred candidate. The stochastic election system is the only system in which it always best to vote for your preferred candidate. Therefore, if the 2015 election were actually using a stochastic election system, people would be allowed to vote for their true preferences. The outcome could be somewhat different than what this simulation illustrates.

      Related info

      November 16, 2015 04:20 AM

      November 15, 2015

      Brent Yorgey

      A strange representation of Z6

      On my other blog I am writing about a proof of the Lucas-Lehmer test, and today in the course of working up some examples I stumbled across this little gem.

      Let M be a monoid, and let M^* denote the subset of elements of M which actually have an inverse. Then it is not hard to show that M^* is a group: the identity is its own inverse and hence is in M^*; it is closed under the monoid operation since if a and b have inverses then so does ab (namely, b^{-1}a^{-1}); and clearly the inverse of every element in M^* is also in M^*, because being an inverse also implies having one.

      Now let M = \{a + b\sqrt{3} \mid 0 \leq a,b < 3\}, where the operation is multiplication, but the coefficients a and b are reduced modulo 3. For example, (2 + \sqrt 3)(2 + 2 \sqrt 3) = (4 + 6) + (4 + 2) \sqrt 3 = 1 + 0 \sqrt 3. This does turn out to be associative, and is clearly commutative; and 1 = 1 + 0\sqrt 3 is the identity. I wrote a little program to see which elements have inverses, and it turns out that the three elements with a = 0 do not, but the other six do. So this is an Abelian group of order 6; but there’s only one such group, namely, the cyclic group \mathbb{Z}_6. And, sure enough, M^* turns out to be generated by 2 + \sqrt 3 and 2 + 2 \sqrt 3.

      by Brent at November 15, 2015 05:34 AM

      November 14, 2015

      Gabriel Gonzalez

      Basic Haskell Examples

      The Haskell community self-selects for people interested in unique things that Haskell can do that other languages cannot do. Consequently, a large chunk of Haskell example code in the wild uses advanced idioms (and I'm guilty of that, too).

      So I would like to swing the pendulum in the other direction by just writing five small but useful programs without any imports, language extensions, or advanced features. These are programs that you could write in any other language and that's the point: you can use Haskell in the same way that you use other languages.

      They won't be the prettiest or most type-safe programs, but that's okay.

      Example #1: TODO program

      This program is an interactive TODO list:

      putTodo :: (Int, String) -> IO ()
      putTodo (n, todo) = putStrLn (show n ++ ": " ++ todo)

      prompt :: [String] -> IO ()
      prompt todos = do
      putStrLn ""
      putStrLn "Current TODO list:"
      mapM_ putTodo (zip [0..] todos)
      command <- getLine
      interpret command todos

      interpret :: String -> [String] -> IO ()
      interpret ('+':' ':todo) todos = prompt (todo:todos)
      interpret ('-':' ':num ) todos =
      case delete (read num) todos of
      Nothing -> do
      putStrLn "No TODO entry matches the given number"
      prompt todos
      Just todos' -> prompt todos'
      interpret "q" todos = return ()
      interpret command todos = do
      putStrLn ("Invalid command: `" ++ command ++ "`")
      prompt todos

      delete :: Int -> [a] -> Maybe [a]
      delete 0 (_:as) = Just as
      delete n (a:as) = do
      as' <- delete (n - 1) as
      return (a:as')
      delete _ [] = Nothing

      main = do
      putStrLn "Commands:"
      putStrLn "+ <String> - Add a TODO entry"
      putStrLn "- <Int> - Delete the numbered entry"
      putStrLn "q - Quit"
      prompt []

      Example usage:

      $ runghc todo.hs
      + <String> - Add a TODO entry
      - <Int> - Delete the numbered entry
      q - Quit

      Current TODO list:
      + Go to bed

      Current TODO list:
      0: Go to bed
      + Buy some milk

      Current TODO list:
      0: Buy some milk
      1: Go to bed
      + Shampoo the hamster

      Current TODO list:
      0: Shampoo the hamster
      1: Buy some milk
      2: Go to bed
      - 1

      Current TODO list:
      0: Shampoo the hamster
      1: Go to bed

      Example #2 - Rudimentary TSV to CSV

      The following program transforms tab-separated standard input into comma-separated standard output. The program does not handle more complex cases like quoting and is not standards-compliant:

      tabToComma :: Char -> Char
      tabToComma '\t' = ','
      tabToComma c = c

      main = interact (map tabToComma)

      Example usage:

      $ cat file.tsv
      1 2 3
      4 5 6
      $ cat file.tsv | runghc tsv2csv.hs

      Example #3 - Calendar

      This program prints a calendar for 2015

      data DayOfWeek
      = Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday
      deriving (Eq, Enum, Bounded)

      data Month
      = January | February | March | April | May | June
      | July | August | September | October | November | December
      deriving (Enum, Bounded, Show)

      next :: (Eq a, Enum a, Bounded a) => a -> a
      next x | x == maxBound = minBound
      | otherwise = succ x

      pad :: Int -> String
      pad day = case show day of
      [c] -> [' ', c]
      cs -> cs

      month :: Month -> DayOfWeek -> Int -> String
      month m startDay maxDay = show m ++ " 2015\n" ++ week ++ spaces Sunday
      week = "Su Mo Tu We Th Fr Sa\n"

      spaces currDay | startDay == currDay = days startDay 1
      | otherwise = " " ++ spaces (next currDay)

      days Sunday n | n > maxDay = "\n"
      days _ n | n > maxDay = "\n\n"
      days Saturday n = pad n ++ "\n" ++ days Sunday (succ n)
      days day n = pad n ++ " " ++ days (next day) (succ n)

      year = month January Thursday 31
      ++ month February Sunday 28
      ++ month March Sunday 31
      ++ month April Wednesday 30
      ++ month May Friday 31
      ++ month June Monday 30
      ++ month July Wednesday 31
      ++ month August Saturday 31
      ++ month September Tuesday 30
      ++ month October Thursday 31
      ++ month November Sunday 30
      ++ month December Tuesday 31

      main = putStr year

      Example usage:

      $ runghc calendar.hs
      January 2015
      Su Mo Tu We Th Fr Sa
      1 2 3
      4 5 6 7 8 9 10
      11 12 13 14 15 16 17
      18 19 20 21 22 23 24
      25 26 27 28 29 30 31

      February 2015
      Su Mo Tu We Th Fr Sa
      1 2 3 4 5 6 7
      8 9 10 11 12 13 14
      15 16 17 18 19 20 21
      22 23 24 25 26 27 28

      March 2015
      Su Mo Tu We Th Fr Sa
      1 2 3 4 5 6 7
      8 9 10 11 12 13 14
      15 16 17 18 19 20 21
      22 23 24 25 26 27 28
      29 30 31

      April 2015
      Su Mo Tu We Th Fr Sa
      1 2 3 4
      5 6 7 8 9 10 11
      12 13 14 15 16 17 18
      19 20 21 22 23 24 25
      26 27 28 29 30

      May 2015
      Su Mo Tu We Th Fr Sa
      1 2
      3 4 5 6 7 8 9
      10 11 12 13 14 15 16
      17 18 19 20 21 22 23
      24 25 26 27 28 29 30

      June 2015
      Su Mo Tu We Th Fr Sa
      1 2 3 4 5 6
      7 8 9 10 11 12 13
      14 15 16 17 18 19 20
      21 22 23 24 25 26 27
      28 29 30

      July 2015
      Su Mo Tu We Th Fr Sa
      1 2 3 4
      5 6 7 8 9 10 11
      12 13 14 15 16 17 18
      19 20 21 22 23 24 25
      26 27 28 29 30 31

      August 2015
      Su Mo Tu We Th Fr Sa
      2 3 4 5 6 7 8
      9 10 11 12 13 14 15
      16 17 18 19 20 21 22
      23 24 25 26 27 28 29
      30 31

      September 2015
      Su Mo Tu We Th Fr Sa
      1 2 3 4 5
      6 7 8 9 10 11 12
      13 14 15 16 17 18 19
      20 21 22 23 24 25 26
      27 28 29 30

      October 2015
      Su Mo Tu We Th Fr Sa
      1 2 3
      4 5 6 7 8 9 10
      11 12 13 14 15 16 17
      18 19 20 21 22 23 24
      25 26 27 28 29 30 31

      November 2015
      Su Mo Tu We Th Fr Sa
      1 2 3 4 5 6 7
      8 9 10 11 12 13 14
      15 16 17 18 19 20 21
      22 23 24 25 26 27 28
      29 30

      December 2015
      Su Mo Tu We Th Fr Sa
      1 2 3 4 5
      6 7 8 9 10 11 12
      13 14 15 16 17 18 19
      20 21 22 23 24 25 26
      27 28 29 30 31

      Example #4 - Decode RNA

      This program converts an RNA sequence read from standard input into the equivalent sequence of amino acids written to standard output, using the genetic code:

      data RNA = A | U | C | G
      deriving (Read)

      data AminoAcid
      = Ala | Cys | Asp | Glu | Phe | Gly | His | Ile | Lys | Leu
      | Met | Asn | Pro | Gln | Arg | Ser | Thr | Val | Trp | Tyr
      | Stop
      deriving (Show)

      decode :: RNA -> RNA -> RNA -> AminoAcid
      decode U U U = Phe
      decode U U C = Phe
      decode U U A = Leu
      decode U U G = Leu
      decode U C _ = Ser
      decode U A U = Tyr
      decode U A C = Tyr
      decode U A A = Stop
      decode U A G = Stop
      decode U G U = Cys
      decode U G C = Cys
      decode U G A = Stop
      decode U G G = Trp
      decode C U _ = Leu
      decode C C _ = Pro
      decode C A U = His
      decode C A C = His
      decode C A A = Gln
      decode C A G = Gln
      decode C G _ = Arg
      decode A U U = Ile
      decode A U C = Ile
      decode A U A = Ile
      decode A U G = Met
      decode A C _ = Thr
      decode A A U = Asn
      decode A A C = Asn
      decode A A A = Lys
      decode A A G = Lys
      decode A G U = Ser
      decode A G C = Ser
      decode A G A = Arg
      decode A G G = Arg
      decode G U _ = Val
      decode G C _ = Ala
      decode G A U = Asp
      decode G A C = Asp
      decode G A A = Glu
      decode G A G = Glu
      decode G G _ = Gly

      decodeAll :: [RNA] -> [AminoAcid]
      decodeAll (a:b:c:ds) = decode a b c : decodeAll ds
      decodeAll _ = []

      main = do
      str <- getContents
      let rna :: [RNA]
      rna = map (\c -> read [c]) str

      let aminoAcids :: [AminoAcid]
      aminoAcids = decodeAll rna

      putStrLn (concatMap show aminoAcids)

      Example usage:

      $ echo "ACAUGUCAGUACGUAGCUAC" | runghc decode.hs

      Example #5 - Bedtime story generator

      This generates a "random" bedtime story:

      stories :: [String]
      stories = do
      let str0 = "There once was "

      str1 <- ["a princess ", "a cat ", "a little boy "]

      let str2 = "who lived in "

      str3 <- ["a shoe.", "a castle.", "an enchanted forest."]

      let str4 = " They found a "

      str5 <- ["giant ", "frog ", "treasure chest " ]

      let str6 = "while "

      str7 <- ["when they got lost ", "while strolling along "]

      let str8 = "and immediately regretted it. Then a "

      str9 <- ["lumberjack ", "wolf ", "magical pony "]

      let str10 = "named "

      str11 <- ["Pinkie Pie ", "Little John ", "Boris "]

      let str12 = "found them and "

      str13 <- ["saved the day.", "granted them three wishes."]

      let str14 = " The end."

      return ( str0
      ++ str1
      ++ str2
      ++ str3
      ++ str4
      ++ str5
      ++ str6
      ++ str7
      ++ str8
      ++ str9
      ++ str10
      ++ str11
      ++ str12
      ++ str13
      ++ str14

      main = do
      let len = length stories
      putStrLn ("Enter a number from 0 to " ++ show (len - 1))
      n <- readLn
      putStrLn ""
      putStrLn (stories !! n)

      Example usage:

      $ runghc story.hs
      Enter a number from 0 to 971

      There once was a princess who lived in an enchanted forest. They found a giant
      while while strolling along and immediately regretted it. Then a lumberjack
      named Boris found them and saved the day. The end.


      If you would like to contribute a simple example of your own, try sharing a paste of your program under the #Haskell #BackToBasics hashtags.

      by Gabriel Gonzalez ( at November 14, 2015 06:40 PM

      Luke Plant

      We need less powerful languages

      Many systems boast of being ‘powerful’, and it sounds difficult to argue that this is a bad thing. Almost everyone who uses the word assumes that it is always a good thing.

      The thesis of this post is that in many cases we need less powerful languages and systems.

      Before I get going, I should say first of all that there is very little in this post by way of original insight. The train of thought behind it was set off by reading Hofstadter’s book Gödel, Escher, Bach — an Eternal Golden Braid which helped me pull together various things in my own thinking where I’ve seen the principle in action. Philip Wadler’s post on the rule of least power was also formative, and most of all I’ve also taken a lot from the content of this video from a Scala conference about everything that is wrong with Scala, which makes the following fairly central point:

      Every increase in expressiveness brings an increased burden on all who care to understand the message.

      My aim is simply to illustrate this point using examples that might be more accessible to the Python community than the internals of a Scala compiler.

      I also need a word about definitions. What do we mean by “more powerful” or “less powerful” languages? In this article, I mean something roughly like this: “the freedom and ability to do whatever you want to do”, seen mainly from the perspective of the human author entering data or code into the system. This roughly aligns with the concept of “expressiveness”, though not perhaps with a formal definition. (More formally, many languages have equivalent expressiveness in that they are all Turing complete, but we still recognise that some are more powerful in that they allow a certain outcome to be produced with fewer words or in multiple ways, with greater freedoms for the author).

      The problem with this kind of freedom is that every bit of power you insist on have when writing in the language corresponds to power you must give up at other points of the process — when ‘consuming’ what you have written. I’ll illustrate this with various examples which range beyond what might be described as programming, but have the same principle at heart.

      We’ll also need to ask “Does this matter?” It matters, of course, to the extent that you need to be able to ‘consume’ the output of your system. Different players who might ‘consume’ the message are software maintainers, compilers and other development tools, which means you almost always care — this has implications both for performance and correctness as well as human concerns.

      Databases and schema

      Starting at the low end of the scale in terms of expressiveness, there is what you might call data rather than language. But both “data” and “language” can be thought of as “messages to be received by someone”, and the principle applies here.

      In my years of software development, I’ve found that clients and users often ask for “free text” fields. A free text field is maximally powerfully as far as the end user is concerned — they can put whatever they like in. In this sense, this is the “most useful” field — you can use it for anything.

      But precisely because of this, it is also the least useful, because it is the least structured. Even search doesn’t work reliably because of typos and alternative ways of expressing the same thing. The longer I do software development involving databases, the more I want to tightly constrain everything as much as possible. When I do so, the data I end up with is massively more useful. I can do powerful things when consuming the data only when I severely limit the power (i.e. the freedom) of the agents putting data into the system.

      In terms of database technologies, the same point can be made. Databases that are “schema-less” give you great flexibility and power when putting data in, and are extremely unhelpful when getting it out. A key-value store is a more technical version of “free text”, with the same drawbacks — it is pretty unhelpful when you want to extract info or do anything with the data, since you cannot guarantee that any specific keys will be there.


      The success of the web has been partly due to the fact that some of the core technologies, HTML and CSS, have been deliberately limited in power. Indeed, you probably wouldn’t call them programming languages, but markup languages. This, however, was not an accident, but a deliberate design principle on the part of Tim Berners Lee. I can’t do better than to quote that page at length:

      Computer Science in the 1960s to 80s spent a lot of effort making languages which were as powerful as possible. Nowadays we have to appreciate the reasons for picking not the most powerful solution but the least powerful. The reason for this is that the less powerful the language, the more you can do with the data stored in that language. If you write it in a simple declarative form, anyone can write a program to analyze it in many ways. The Semantic Web is an attempt, largely, to map large quantities of existing data onto a common language so that the data can be analyzed in ways never dreamed of by its creators. If, for example, a web page with weather data has RDF describing that data, a user can retrieve it as a table, perhaps average it, plot it, deduce things from it in combination with other information. At the other end of the scale is the weather information portrayed by the cunning Java applet. While this might allow a very cool user interface, it cannot be analyzed at all. The search engine finding the page will have no idea of what the data is or what it is about. This the only way to find out what a Java applet means is to set it running in front of a person.

      This is has become a W3C principle:

      Good Practice: Use the least powerful language suitable for expressing information, constraints or programs on the World Wide Web.

      Note that this is almost exactly the opposite of Paul Graham’s advice (with the caveat that 'power' is often too informally defined to compare):

      if you have a choice of several languages, it is, all other things being equal, a mistake to program in anything but the most powerful one.

      Python file

      Moving up towards ‘proper’ programming language, I came across this example — the file format used by distutils/setuptools. If you have had to create a package for a Python library, you may well have used it.

      The file format is essentially a very small language for defining what files should be included in your Python package (relative to the file, which we’ll call the working directory from now on). It might look something like this:

      include README.rst
      recursive-include foo *.py
      recursive-include tests *
      global-exclude *~
      global-exclude *.pyc
      prune .DS_Store

      There are two types of directive: include type directives (include, recursive-include, global-include and graft), and exclude type directives (exclude, recursive-exclude, global-exclude and prune).

      There comes a question — how are these directives to be interpreted (i.e. what are the semantics)?

      You could interpret them in this way:

      A file from the working directory (or sub-directories) should be included in the package if it matches at least one include type directive, and does not match any exclude type directive.

      This would make it a declarative language.

      Unfortunately, that is not how the language is defined. The distutils docs for are specific about this — the directives are to be understood as follows (my paraphrase):

      1. Start with an empty list of files to include in the package (or technically, a default list of files).
      2. Go down the directives in the in order.
      3. For every include type directive, copy any matching files from the working directory to the list for the package.
      4. For every exclude type directive, remove any matching files from the list for the package.

      As you can see, this interpretation defines a language that is imperative in nature — each line of is a command that implies an action with side effects.

      The point to note is that this makes the language more powerful than my speculative declarative version above. For example, consider the following:

      recursive-include foo *
      recursive-exclude foo/bar *
      recursive-include foo *.png

      The end result of the above commands is that .png files that are below foo/bar are included, but all other files below foo/bar are not. If I’m thinking straight, to replicate the same result using the declarative language is harder — you would have to do something like the following, which is obviously sub-optimal:

      recursive-include foo *
      recursive-exclude foo/bar *.txt *.rst *.gif *.jpeg *.py ...

      So, because the imperative language is more powerful, there is a temptation to prefer that one. However, the imperative version comes with significant drawbacks:

      1. It is much harder to optimise.

        When it comes to interpreting the and building a list of files to include in the package, one fairly efficient solution for a typical case is to first build an immutable list of all files in the directory and its sub-directories, and then apply the rules: addition rules involve copying from the full list to an output list, and subtraction rules involve removing from the output list. This is how the Python implementation currently does it.

        This works OK, unless you have many thousands of files in the full list, most of which are going to get pruned or not included, in which case you can spend a lot of time building up the full list, only to ignore most of it.

        An obvious shortcut is to not recurse into directories that would be excluded by some exclude directive. However, you can only do that if the exclude directives come after all include directives.

        This is not a theoretical problem — I’ve found that doing sdist and other commands can take 10 minutes to run, due to a large number of files in the working directory if you use the tool tox for instance. This means that runs of tox itself (which uses become very slow. I am currently attempting to fix this issue, but it is looking like it will be really hard.

        Adding the optimised case might not look that hard (you can shortcut the file system traversal using any exclude directives that come after all include directives), but it adds sufficiently to the complexity that a patch is unlikely to be accepted — it increases the number of code paths and the chances of mistakes, to the point of it not being worth it.

        It might be that the only practical solution is to avoid altogether and optimise only the case when it is completely empty.

      2. The power has a second cost — files are harder to understand.

        First, in understanding how the language works — the docs for this are considerably longer than for the declarative version I imagined.

        Second, in analysing a specific file — you have to execute the commands in your head in order to work out what the result will be, rather than being able to take each line on its own, or in any order that makes sense to you.

        This actually results in packaging bugs. For instance, it would be easy to believe that a directive like:

        global-exclude *~

        at the top of a file would result in any file name ending in ~ (temporary files created by some editors) being excluded from the package. In reality it does nothing at all, and the files will be erroneously included if other commands include them.

        Examples I’ve found of this mistake (exclude directives that don’t function as intended or are useless) include:

        • hgview (exclude directives at the top do nothing)
        • django-mailer (global-exclude at the top does nothing)
      3. Another result is that you cannot groups lines in the file in any way you please, for clarity, since re-ordering changes the meaning of the file.

      In addition, virtually no-one will actually use the additional power. I’m willing to bet that 99.99% files do not make use of the additional power of the imperative language (I downloaded 250 and haven’t found any that do). So we could have been served much better by a declarative language here instead of an imperative one. But backwards compatibility forces us to stick with this. That highlights another point — it is often possible to add features to a language to make it more powerful, but compatibility concerns usually don’t allow you to make it less powerful, for example by removing features or adding constraints.

      URL reversing

      One core piece of the Django web framework is URL routing. This is the component that parses URLs and dispatches them to the handler for that URL, possibly passing some components extracted from the URL.

      In Django, this is done using regular expressions. For an app that displays information about kittens, you might have a kittens/ with the following:

      from django.conf.urls import url
      from kittens import views
      urlpatterns = [
          url(r'^kittens/$', views.list_kittens, name="kittens_list_kittens"),
          url(r'^kittens/(?P<id>\d+)/$', views.show_kitten, name="kittens_show_kitten"),

      The corresponding file looks like:

      def list_kittens(request):
          # ...
      def show_kitten(request, id=None):
          # ...

      Regular expressions have a capture facility built in, which is used to capture parameters that are passed to the view functions. So, for example, if this app were running on, a URL like results in calling the Python code show_kitten(request, id="23").

      Now, as well as being able to route URLs to specific functions, web apps almost always need to generate URLs. For example, the kitten list page will need to include links to the individual kitten page i.e. show_kitten. Obviously we would like to do this in a DRY way, re-using the URL routing configuration.

      However, we would be using the URL routing configuration in the opposite direction. When doing URL routing, we are doing:

      URL path -> (handler function, arguments)

      In URL generation, we know the handler function and arguments we want the user to arrive at, and want to generate a URL that will take the user there, after going through the URL routing:

      (handler function, arguments) -> URL path

      In order to do this, we essentially have to predict the behaviour of the URL routing mechanism. We are asking “given a certain output, what is the input?”

      In the very early days Django did not include this facility, but it was found that with most URLs, it was possible to 'reverse' the URL pattern. The regex can be parsed looking for the static elements and the capture elements.

      Note, first of all, that this is only possible at all because the language being used to define URL routes is a limited one — regular expressions. We could easily have defined URL routes using a more powerful language. For example, we could have defined them using functions that:

      • take a URL path as input
      • raise NoMatch if they do not match
      • return a truncated URL and an optional set of captures if they do match.

      Our kittens would look like something like this:

      from django.conf.urls import url, NoMatch
      def match_kitten(path):
          KITTEN = 'kitten/'
          if path.startswith(KITTEN):
              return path[len(KITTEN):], {}
          raise NoMatch()
      def capture_id(path):
          part = path.split('/')[0]
              id = int(part)
          except ValueError:
              raise NoMatch()
          return path[len(part)+1:], {'id': id}
      urlpatterns = [
          url([match_kitten], views.list_kittens, name='kittens_list_kittens'),
          url([match_kitten, capture_id], views.show_kitten, name="kittens_show_kitten"),

      Of course, we could provide helpers that make things like match_kitten and capture_id much more concise:

      from django.conf.urls import url, m, c
      urlpatterns = [
          url([m('kitten/'), views.list_kittens, name='kittens_list_kittens'),
          url([m('kitten/'), c(int)], views.show_kitten, name="kittens_show_kitten"),

      Now, this language for URL routing is actually a lot more powerful than our regex based one, assuming that m and c are returning functions as above. The interface for matching and capturing is not limited to the capabilities of regexes — for instance, we could do database lookups for the IDs, or many other things.

      The downside, however, is that URL reversing would be entirely impossible. For general, Turing complete languages, you cannot ask “given this output, what is the input?”. We could potentially inspect the source code of the function and look for known patterns, but it quickly becomes totally impractical.

      With regular expressions, however, the limited nature of the language gives us more options. In general, URL configuration based on regexes is not reversible — a regex as simple as . cannot be reversed uniquely. (Since we want to generate canonical URLs normally, a unique solution is important. As it happens, for this wild card, Django currently picks an arbitrary character, but other wild cards are not supported). But as long as wild cards of any sort are only found within capture groups (and possibly some other constraints), the regex can be reversed.

      So, if we want to be able to reliably reverse the URL routes, we actually want a language less powerful than regular expressions. Regular expressions were presumably chosen because they were powerful enough, without realising that they were too powerful.

      Additionally, in Python defining mini-languages for this kind of thing is quite hard, and requires a fair amount of boilerplate and verbosity both for implementation and usage — much more than when using a string based language like regexes. In languages like Haskell, relatively simple features like easy definitions of algebraic data types and pattern matching make these things much easier.

      Regular expressions

      The mention of regexes as used in Django’s URL routing reminds me of another problem:

      Many usages of regexes are relatively simple, but whenever you invoke a regex, you get the full power whether you need it or not. One consequence is that for some regular expressions, the need to do backtracking to find all possible matches means that it is possible to construct malicious input that takes a huge amount of time to be processed by the regex implementation.

      This has been the cause of a whole class of Denial Of Service vulnerabilities in many web sites and services, including one in Django due to an accidentally 'evil' regex in the URL validator — CVE-2015-5145.

      Django templates vs Jinja templates

      The Jinja template engine was inspired by the Django template language, but with some differences in philosophy and syntax.

      One major advantage of Jinja2 over Django is that of performance. Jinja2 has an implementation strategy which is to compile to Python code, rather than run an interpreter written in Python, which is how Django works, and this results in a big performance increase — often 5 to 20 times. (YMMV etc.)

      Armin Ronacher, the author of Jinja, attempted to use the same strategy to speed up Django template rendering. There were problems, however.

      The first he knew about when he proposed the project — namely that the extension API in Django makes the approach taken in Jinja very difficult. Django allows custom template tags that have almost complete control over the compilation and rendering steps. This allows some powerful custom template tags like addtoblock in django-sekizai that seems impossible at first glance. However, if a slower fallback was provided for these less common situations, a fast implementation might still have been useful.

      However, there is another key difference that affects a lot of templates, which is that the context object that is passed in (which holds the data needed by the template) is writable within the template rendering process in Django. Template tags are able to assign to the context, and in fact some built-in template tags like url do just that.

      The result of this is a key part of the compilation to Python that happens in Jinja is impossible in Django.

      Notice that in both of these, it is the power of Django’s template engine that is the problem — it allows code authors to do things that are not possible in Jinja2. However, the result is that a very large obstacle is placed in the way of attempts to compile to fast code.

      This is not a theoretical consideration. At some point, performance of template rendering becomes an issue for many projects, and a number have been forced to switch to Jinja because of that. This is far from an optimal situation!

      Often the issues that make optimisation difficult are only clear with the benefit of hindsight, and it isn’t true to say that simply adding restrictions to a language is necessarily going to make it easier to optimise. There are certainly languages which somehow manage to hit a “sour spot” of providing little to power to either the authors or the consumers!

      You might also say that for the Django template designers, allowing the context object to be writable was the obvious choice because Python data structures are typically mutable by default. Which brings us to Python...


      There are many ways that we could think about the power of the Python language, and how it makes life hard for every person and program that wants to make sense of Python code.

      Compilation and performance of Python is an obvious one. The unrestricted effects that are possible at any point, including writable classes and modules etc., not only allow authors to do some very useful things, they make it extremely difficult to execute Python code quickly. PyPy has made some impressive progress, but looking at the curve from PyPy 1.3 onward, which shows diminishing returns, makes it clear that they are unlikely to make much bigger gains in the future. And the gains that have been made in terms of run time have often been at the expense of memory usage. There is simply a limit to how well you can optimise Python code.

      (Please note, to all who continue reading this — I’m not a Python basher, or a Django basher for that matter. I’m a core developer of Django, and I use Python and Django in almost all my professional programming work. The point of this post is illustrate the problems caused by powerful languages).

      However, rather than focus on the performance problems of Python, I’m going to talk about refactoring and maintenance. If you do any serious work in a language, you find yourself doing a lot of maintenance, and being able to do it quickly and correctly often becomes very important.

      So, for example, in Python, and with typical VCS tools (Git or Mercurial, for instance), if you re-order functions in a module e.g. move a 10 line function to a different place, you get a 20 line diff, despite the fact that nothing changed in terms of the meaning of the program. And if something did change (the function was both moved and modified), it’s going to be very difficult to spot.

      This happened to me recently, and set me off thinking just how ridiculously bad our toolsets are. Why on earth are we treating our highly structured code as a bunch of lines of text? I can’t believe that we are still programming like this, it is insane!

      At first, you might think that this could be solved with a more intelligent diff tool. But the problem is that in Python, the order in which functions are defined can in fact change the meaning of a program (i.e. change what happens when you execute it).

      Here are a few examples:

      Using a previously defined function as a default argument:

      def foo():
      def bar(a, callback=foo):

      These functions can’t be re-ordered or you’ll get a NameError for foo in the definition of bar.

      Using a decorator:

      def foo():
      def bar():

      Due to unrestricted effects that are possible in @decorateit, you can’t safely re-order these functions and be sure the program will do the same thing afterwards. Similarly, calling some code in the function argument list:

      def foo(x=Something()):
      def bar(x=Something()):

      Similarly, class level attributes can’t be re-ordered safely:

      class Foo():
          a = Bar()
          b = Bar()

      Due to unrestricted effects possible inside the Bar constructor, the definitions of a and b cannot be re-ordered safely. (This might seem theoretical, but Django, for instance, actually uses this ability inside Model and Form definitions to provide a default order for the fields, using a cunning class level counter inside the base Field constructor).

      Ultimately, you have to accept that a sequence of function statements in Python is a sequence of actions in which objects (functions and default arguments) are created, possibly manipulated, etc. It is not a re-orderable set of function declarations as it might be in other languages.

      This gives Python an amazing power when it comes to writing it, but imposes massive restrictions on what you can do in any automated way to manipulate Python source code.

      Above I used the simple example of re-ordering two functions or class attributes. But every single type of refactoring that you might do in Python becomes virtually impossible to do safely because of the power of the language e.g. duck typing means you can’t do method renames, the possibility of reflection/dynamic attribute access (getattr and friends) means you can’t in fact do any kind of automated renames (safely).

      So, if we are tempted to blame our crude VCS or refactoring tools, we actually have to blame the power of Python — despite the huge amount of structure in correct Python source code, there is very little that any software tool can do with it when it comes to manipulating it, and the line-based diffing that got me so mad is actually a reasonable approach.

      Now, 99% of the time, we don’t write Python decorators which mean that the order of function definitions makes a difference, or silly things like that — we are responsible “adults”, as Guido put it, and this makes life easier for human consumers. But the fact remains that our tools are limited by what we do in the 0.01% of cases. For some consumers, we can optimise on the basis of the common case, and detect when that fails e.g. a JIT compiler using guards. But with others e.g. VCS or refactoring tools, the “runtime” information that you hit the unlucky case comes far too late — you might have released your subtly-broken code by the time you find out, so you have to be safe rather than sorry.

      In an ideal world, with my dream language, when you rename a function, the entire “diff” in your VCS should simply be “Function foo renamed to bar”. (And, this should be exportable/importable, so that when you upgrade a dependency to a version in which foo is renamed to bar, it should be exactly zero work to deal with this). In a “less powerful” language, this would be possible, but the power given to the program author in Python has taken power from all the other tools in the environment.

      Does this matter? It depends on how much time you spend manipulating your code, compared to using code to manipulate data.

      At the beginning of a project, you may be tempted to desire the most powerful language possible, because it gives you the most help and freedom in terms of manipulating data. But later on, you spend a huge amount of time manipulating code, and often using an extremely basic tool to do so — a text editor. This treats your highly structured code as one of the least structured forms of data — a string of text — exactly the kind of manipulation you would avoid at all costs inside your code. But all the practices you would choose and rely on inside your program (manipulating all data inside appropriate containers) are no longer available to you when it comes to manipulating the program itself.

      Some popular languages make automated refactoring easier, but more is needed: to actually make use of the structure of your code, you need an editor and VCS that understand your code properly. Projects like Lamdu are in the right direction, but still in their infancy, and unfortunately involving re-thinking the entire software development stack :-(


      When you consider the total system and all the players (whether software or human), including the need to produce efficient code, and long term maintainability, less powerful languages are actually more powerful — “slavery is freedom”. There is a balance between expressiveness and reasonability.

      The more powerful a language, the greater the burden on software tools, which either are need to be more complicated in order to work, or are forced to do less than they could. This includes:

      • compilers — with big implications for performance
      • automated refactoring and VCS tools — with big implications for maintenance.

      Similarly, the burden also increases for humans — for anyone attempting to understand the code or modify it.

      A natural instinct is to go for the most powerful solution, or a solution that is much more powerful than is actually needed. We should try to do the opposite — find the least powerful solution that will do the job.

      This won’t happen if creating new languages (which might involve parsers etc.) is hard work. We should prefer software ecosystems that make it easy to create very small and weak languages.

      by Luke Plant at November 14, 2015 11:46 AM

      November 13, 2015

      Functional Jobs

      Haskell Developer (ON SITE) at CJ Affiliate by Conversant (Full-time)

      Join our newly formed team of crack commandos (there are only two of us at this point) tasked with replatforming a flaky data import / export system to Haskell (from Java). This is the first Haskell project at the company and we plan (pray?) to knock it out of the park.

      The right candidate is either: A senior developer (JVM experience preferred) with a hobbyist's level of Haskell foo and a keen interest in Haskell's particular flavor of functional programming - or a junior/mid-career developer with strong Haskell skills.

      Get information on how to apply for this position.

      November 13, 2015 11:45 PM

      Haskell Developer at CJ Affiliate by Conversant (Full-time)

      Join our newly formed team of crack commandos (there are only two of us at this point) tasked with replatforming a flaky data import / export system to Haskell (from Java). This is the first Haskell project at the company and we plan (pray?) to knock it out of the park.

      The right candidate is either: A senior developer (JVM experience preferred) with a hobbyist's level of Haskell foo and a keen interest in Haskell's particular flavor of functional programming - or a junior/mid-career developer with strong Haskell skills.

      Get information on how to apply for this position.

      November 13, 2015 11:45 PM

      Dimitri Sabadie

      OpenGL 3.2 support for luminance!


      You can’t even imagine how hard it was to release luminance-0.7. I came accross several difficulties I had to spend a lot of time on but finally, here it is. I made a lot of changes for that very special release, and I have a lot to say about it!


      As for all my projects, I always provide people with a changelog. The 0.7 release is a major release (read as: it was a major increment). I think it’s good to tell people what’s new, but it should be mandatory to warn them about what has changed so that they can directly jump to their code and spot the uses of the deprecated / changed interface.

      Anyway, you’ll find patch, minor and major changes in luminance-0.7. I’ll describe them in order.

      Patch changes

      Internal architecture and debugging

      A lot of code was reviewed internally. You don’t have to worry about that. However, there’s a new cool thing that was added internally. It could have been marked as a minor change but it’s not supposed to be used by common people – you can use it via a flag if you use cabal or stack though. It’s about debugging the OpenGL part used in luminance. You shouldn’t have to use it but it could be interesting if you spot a bug someday. Anyway, you can enable it with the flag debug-gl.

      Uniform Block / Uniform Buffer Objects

      The UBO system was buggy and was fixed. You might experience issue with them though. I spotted a bug and reported it – you can find the bug report here. That bug is not Haskell related and is related to the i915 Intel driver.

      Minor changes

      The minor changes were the most important part of luminance-0.7. luminance now officially supports OpenGL 3.2! When installing luminance, you default to the gl32 backend. You can select the backend you want with flags – gl45 and gl45-bindless-textures – but keep in mind you need the appropriate hardware to be able to use it. Because you need to use flags, you won’t be able to switch to the backend you want at runtime – that’s not the purpose of such a change though.

      The performance gap should be minor between gl32 and gl45 but still. Basically, OpenGL 4.5 adds the support for DSA, which is very handy and less ill-designed that previous iterations of OpenGL. So a lot of code had to be rewritten to implement luminance’s stateless interface without breaking performance nor bring them down.

      I might add support for other backends later on – like an OpenGL ES backend and WebGL one – but that won’t ship that soon though because I have a ton of work to do, and yet need to provide you with a concrete, beautiful, fast, appealing and eye-blowing demo with luminance! ;)

      Feel free to test the gl32 backend and give me back feedback!

      However, if I spent so much time on that 0.7 version, it’s because I had issue whilst writing the gl32 backend. Indeed, I spotted several bugs on my Intel HD card. This is my OpenGL version string for my Intel IGP card:

      OpenGL core profile version string: 3.3 (Core Profile) Mesa 11.0.4

      The architecture is Haswell. And on such a card (i915 linux driver) I’ve found two bugs while trying the gl32 backend with luminance-samples-0.7.


      For unknown reason, the Texture sample failed on my Intel IGP but ran smoothly and flawlessly on my nVidia GPU. I spent a lot of time trying to figure out what I was missing, but eventually changed the sampler type – it’s now a sampler2D – and… it worked. I reported the issue to the intel dev team. So if you hit that error too, please leave a message here so that I can have more hindsight about that error and see what I can do.

      Uniform block and vec3

      This is a very nasty issue that kept me awoken for days trying to fix my code while it was a driver bug. It’s a big technical, so I’ll just leave a link to the bug tracker so that you can read it if you want to.

      Breaking changes

      Ok, let’s talk.

      When creating a new shader stage, you now have to use the function createStage – instead of several functions like createVertexShader. That change is important so that I can add new shader types without changing the interface, and because some shader can fail to be created. For instance, on the gl32 backend, trying to build a tessellation shader will raise an error.

      When a shader stage creation fails, the UnsupportedStage error is raised and holds the type of the stage that failed.

      Finally, the interface for the cubemaps changed a bit – you don’t have access to width and height anymore, that was error-prone and useless; you’re stick to a size parameter.

      I’d like to thank all people supporting me and luminance. I’ll be watching reactions to that major and important release as it will cover more people with cheaper and well-spread GPUs.

      Happy hacking! :)

      by Dimitri Sabadie ( at November 13, 2015 06:31 PM

      Magnus Therning

      How can I unit test failure cases?

      When writing unit tests, especially when using mock objects, there’s always a risk of falling into the trap of writing tests for the implementation rather than for the API. In my experience the most obvious indication of that is that any refactoring of the code requires major rework of the tests.

      Right now I’m sitting with the task of writing tests for a function that promises to return NULL on failure. The function in question allocates memory up to three times, opens two message queues, sends a message on one and expects a reponse on the other. If all goes well it returns the pointer to one of the memory areas allocated. And if it fails, for whatever reason, it returns NULL.

      Is it even possible to write a set of tests for it without testing the specific implementation?

      I know some of the calls can be re-arranged, e.g. moving all memory allocation to the start of the function, without affecting the caller of the function. However, if I use mock objects to simulate failure in the external libraries and system calls I’d be forced to modify the tests on each such re-arranging of calls. In other words I’m testing the implementation!

      Should I think differently about testing failure cases?

      Should the API be changed in some way to make unit tests a better fit for testing failures?

      November 13, 2015 12:00 AM

      November 12, 2015

      Dominic Steinitz

      Floating Point: A Faustian Bargain?

      Every so often, someone bitten by floating point arithmetic behaving in an unexpected way is tempted to suggest that a calculation should be done be precisely and rounding done at the end. With floating point rounding is done at every step.

      Here’s an example of why floating point might really be the best option for numerical calculations.

      Suppose you wish to find the roots of a quintic equation.

      > import Numeric.AD
      > import Data.List
      > import Data.Ratio
      > p :: Num a => a -> a
      > p x = x^5 - 2*x^4 - 3*x^3 + 3*x^2 - 2*x - 1

      We can do so using Newton-Raphson using automatic differentiation to calculate the derivative (even though for polynomials this is trivial).

      > nr :: Fractional a => [a]
      > nr = unfoldr g 0
      >   where
      >     g z = let u = z - (p z) / (h z) in Just (u, u)
      >     h z = let [y] = grad (\[x] -> p x) [z] in y

      After 7 iterations we see the size of the denominator is quite large (33308 digits) and the calculation takes many seconds.

      ghci> length $ show $ denominator (nr!!7)

      On the other hand if we use floating point we get an answer accurate to 1 in 2^{53} after 7 iterations very quickly.

      ghci> mapM_ putStrLn $ map show $ take 7 nr

      The example is taken from here who refers the reader to Nick Higham’s book: Accuracy and Stability of Numerical Algorithms.

      Of course we should check we found a right answer.

      ghci> p $ nr!!6

      by Dominic Steinitz at November 12, 2015 08:46 PM

      November 11, 2015

      Functional Jobs

      Software Engineer - Functional Programmer - Erlang at Change Healthcare (Full-time)

      Job Description

      Change Healthcare is a leading provider of United States healthcare solutions. Our division is responsible for consumer engagement and transparency. We have a very lean, Agile team with a rapid deployment schedule for processing X12 in Erlang doing insurance calculations. Functional programming in Erlang has created a robust, scalable foundation for our organization.

      What You Could Be Working On:

      Full product life-cycle development, working with product management to production delivery for multiple clients. Team environment is a product manager, a QA, 2 developers and 1 architect. Cross team cooperation with Ops and Data is required. X12 transaction processing applies across the US for electronic data interchange, and is used extensively in healthcare. JIRA and git are key tools in the daily workflow.

      Where You Will Work:

      Our office in Nashville, TN is a casual open cube plan with a motto of work hard, play hard. Foosball play is competitive, and individual creativity is valued here at Change Healthcare. Nashville is a great place to live, and is growing rapidly like Change Healthcare

      What We Commit to YOU:

      • You will get to work with one of the most innovative teams in the IT marketplace and solve real strategic problems in a 99.99% uptime production environment.
      • We will invest in things that are important to you both professionally and personally.
      • We will provide you with a team environment like no other – we are listed in the "100 Best Places to Work in Healthcare".
      • We will build a relationship with you to accelerate your Career.
      • We provide some of the best benefits around.

      What Is Required:

      • Have 3+ years experience with a functional language (e.g. Lisp, Scheme, F#, OCAML, Erlang, Haskell).
      • Ability to identify, communicate and push toward resolution of requirement gaps.
      • A Bachelors degree in computer science is a major plus.
      • Passion and pride in your personal work product.
      • Ability to work with a team, and hand off work as needed to drive towards hard delivery dates.
      • Worked with Restful API design.
      • Experience with scalable parallel solution design.
      • Experience with writing test cases

      Get information on how to apply for this position.

      November 11, 2015 04:07 PM

      Gabriel Gonzalez

      Haskell-native spreadsheets

      I'm releasing the typed-spreadsheet library, which lets you build spreadsheets integrated with Haskell. I use the term "spreadsheet" a bit loosely, so I'll clarify what I mean by comparing and contrasting this library with traditional spreadsheets.

      The best way to explain how this works is to begin with a small example:

      {-# LANGUAGE OverloadedStrings #-}

      import Control.Applicative
      import Typed.Spreadsheet

      main :: IO ()
      main = textUI "Example program" logic
      -- Hate weird operators? Read on!
      logic = combine <$> checkBox "a" -- Input #1
      <*> spinButton "b" 1 -- Input #2
      <*> spinButton "c" 0.1 -- Input #3
      <*> entry "d" -- Input #4

      combine a b c d = display (a, b + c, d) -- The output is a
      -- function of all
      -- four inputs

      The above program builds a graphical user interface with four user inputs in the left panel and one output in the right panel:

      The output is a text representation of a 3-tuple whose:

      • 1st element is the checkbox state (False for unchecked, True for checked)
      • 2nd element is the sum of the two numeric fields (labeled "b" and "c")
      • 3rd element is the text entry field

      The right panel immediately updates in response to any user input from the left panel. For example, every time we toggle the checkbox or enter numbers/text the right panel changes:

      So in one sense this resembles a spreadsheet in that the output "cell" on the right (the text panel) updates immediately in response to the input "cell"s on the left (the checkbox, and numeric/text entry fields).

      However, this also departs significantly from the traditional spreadsheet model: input controls reflect the type of input in order to make invalid inputs unrepresentable. For example, a Bool input corresponds to a checkbox.


      The generated executable is an ordinary binary so you can distribute the program to other users without needing to supply the Haskell compiler or toolchain. You can even fully statically link the executable for extra portability.

      For example, say that I want to create a mortage calculator for somebody else to use. I can just write the following program:

      {-# LANGUAGE OverloadedStrings #-}

      import Control.Applicative
      import Data.Monoid
      import Data.Text (Text)
      import Typed.Spreadsheet

      payment :: Double -> Double -> Double -> Text
      payment mortgageAmount numberOfYears yearlyInterestRate
      = "Monthly payment: $"
      <> display (mortgageAmount * (i * (1 + i) ^ n) / ((1 + i) ^ n - 1))
      n = truncate (numberOfYears * 12)
      i = yearlyInterestRate / 12 / 100

      logic :: Updatable Text
      logic = payment <$> spinButton "Mortgage Amount" 1000
      <*> spinButton "Number of years" 1
      <*> spinButton "Yearly interest rate (%)" 0.01

      main :: IO ()
      main = textUI "Mortgage payment" logic

      ... and compile that into an executable which I can give them. When they run the program they will get the following simple user interface:

      Or maybe I want to write a simple "mad libs" program for my son to play:

      {-# LANGUAGE OverloadedStrings #-}

      import Data.Monoid
      import Typed.Spreadsheet

      noun = entry "Noun"

      verb = entry "Verb"

      adjective = entry "Adjective"

      example =
      "I want to " <> verb <> " every " <> noun <> " because they are so " <> adjective

      main :: IO ()
      main = textUI "Mad libs" example

      This generates the following interface:

      All the above examples have one thing in common: they only generate a single Text output. The typed-spreadsheet library does not permit multiple outputs or outputs other than Text. If we want to display multiple outputs then we need to somehow format and render all of them within a single Text value.

      In the future the library may provide support for diagrams output instead of Text but for now I only provide Text outputs for simplicity.


      The central type of this library is the Updatable type, which implements the Applicative interface. This interface lets us combine smaller Updatable values into larger Updatable values. For example, a checkBox takes a single Text argument (the label) and returns an Updatable Bool:

      checkBox :: Text -> Updatable Bool

      Using Applicative operators, (<$>) and (<*>), we can lift any function over an arbitrary number of Updatable values. For example, here is how I would lift the binary (&&) operator over two check boxes:

      z :: Updatable Bool
      z = (&&) <$> checkBox "x" <*> checkBox "y"

      ... or combine their output into a tuple:

      both :: Updatable (Bool, Bool)
      both = (,) <$> checkBox "x" <*> checkBox "y"

      However, to the untrained eye these will look like operator soup. Heck, even to the trained eye they aren't that pretty (in my opinion).

      Fortunately, ghc-8.0 will come with a new ApplicativeDo which will greatly simplify programs that use the Applicative interface. For example, the above two examples would become much more readable:

      z :: Updatable Bool
      z = do
      x <- checkBox "x"
      y <- checkBox "y"
      return (x && y)

      both :: Updatable (Bool, Bool)
      both = do
      x <- checkBox "x"
      y <- checkBox "y"
      return (x, y)

      Similarly, the very first example simplifies to:

      {-# LANGUAGE ApplicativeDo     #-}
      {-# LANGUAGE OverloadedStrings #-}

      import Typed.Spreadsheet

      main :: IO ()
      main = textUI "Example program" (do
      a <- checkBox "a"
      b <- spinButton "b" 1
      c <- spinButton "c" 0.1
      d <- entry "d"
      return (display (a, b + c, d)) )

      That's much easier on the eyes. ApplicativeDo helps the code look much less like operator soup and presents a comfortable syntax for people used to imperative programming.


      Spreadsheet integration with Haskell comes with advantages and disadvantages.

      The obvious advantage is that you get the full power of the Haskell ecosystem. You can transform input to output using arbitrary Haskell code. You also get the benefit of the strong type system, so if you need extra assurance for critical calculations you can build that into your program.

      The big disadvantage is that you have to relaunch the application in order to change the code. The library does not support live code reloading. This is technically feasible but requires substantially more work and would make the application much less portable.

      If you follow my previous work this is very similar to a previous post of mine on spreadsheet-like programming in Haskell. This library simplifies many of the types and ideas from that previous post and packages them in a polished library.

      If you would like to contribute to this library there are two main ways that you can help:

      • Adding new types of input controls
      • Adding new backends for output (like diagrams)

      If you would like to use this code you can find the library on Github or Hackage.

      by Gabriel Gonzalez ( at November 11, 2015 03:12 PM

      Eric Kidd

      Bare Metal Rust 2: Retarget your compiler so interrupts are not evil

      Want to build your own kernel in Rust? See the Bare Metal Rust page for more resources and more posts in this series. There's just a few more posts to go until we have keyboard I/O!

      Hacking on kernels in Rust is a lot of fun, but it can also result in massive frustration when QEMU starts rebooting continuously because of a triple fault. One good way to minimize frustration is to wander on over to the ever-helpful OSDev wiki. It's sort of like having an experienced kernel developer on hand to give grouchy but sanity-saving advice.

      The OSDev Beginner Mistakes page, in particular, has saved me a couple times already. But there's one bit of advice that I want to focus on today, which I've marked in boldface below:

      Beginners often ask "What is the easiest way to do X?" rather than "What is the best, proper, correct way to do X?". This is dangerous as the newcomer doesn't invest time into understanding the superior way to implement something, but instead picks a conceptually simpler method copied from a tutorial. Indeed, the simpler route is often too simple and ends up causing more problems in the long run, because the beginner is ignorant of the superior alternative and doesn't know when it is better to switch. What's so bad about taking the hard route instead?

      Common examples include being too lazy to use a Cross-Compiler, developing in Real Mode instead of Protected Mode or Long Mode, relying on BIOS calls rather than writing real hardware drivers, using flat binaries instead of ELF, and so on. Experienced developers use the superior alternatives for a reason…

      So what does that mean, "being too lazy to use a cross-compiler"? It means cheating, and using our regular rustc setup to build ordinary user-space code, and then trying to run it in kernel space. This will actually work, at least for a while. But eventually, we may find ourselves engaged in multiweek debugging nightmares.

      So today, I'm going to talk about the sanity-saving difference between --target x86_64-unknown-linux-gnu and --target x86_64-unknown-none-gnu, and how to get your Rust compiler ready for the kernel world.

      Read more…

      November 11, 2015 10:43 AM

      November 09, 2015

      Eric Kidd

      Bare Metal Rust: Low-level CPU I/O ports

      Want to build your own kernel in Rust? See the Bare Metal Rust page for more resources and more posts in this series.

      Rust is a really fun language: It allows me to work on low-level kernel code, but it also allows me to wrap my code up in clean, high-level APIs. If you this sounds interesting, you should really check out Philipp Oppermann's blog posts about writing a basic x86_64 operating system kernel in Rust. He walks you through booting the kernel, entering long mode, getting Rust running, and printing text to the screen.

      Once you get a basic kernel running, you'll probably want to start working on basic I/O, which requires interrupts. And this point, you'll find that pretty much every tutorial dives right into the in and out instructions. For example, if you look at the introduction to interrupts, the very first code you'll see is (comments added):

      mov al,20h  ; Move interrupt acknowledgment code into al.
      out 20h,al  ; Write al to PIC on port 0x20.

      Here, we're talking to the PIC ("Programmable Interrupt Controller"), and we're telling it that we've finished handling a processor interrupt. To do this, we need to write an 8-bit status code to the I/O port at address 0x20.

      Traditionally, we would wrap this up in an outb ("out byte") function, which might look something like this in Rust:

      // The asm! macro requires a nightly build of Rust, and
      // we need to opt-in explicitly.
      unsafe fn outb(value: u8, port: u16) {
          asm!("outb %al, %dx" ::
               "{dx}"(port), "{al}"(value) ::

      This writes an 8-byte value to the specified port. It uses the unstable Rust extension asm!, which allows us to use GCC/LLVM-style inline assembly. We'd invoke it like this:

      outb(0x20, 0x20);

      But let's see if we can wrap a higher-level API around an I/O port.

      Read more…

      November 09, 2015 12:33 PM

      November 07, 2015

      FP Complete

      Stack entering stabilization phase

      Since we created the stack repo at the end of April, a tremendous amount of work has been done very rapidly. Now that Stack has a suite of features that make it excellent for most common use cases, it's a good time to step back and work on improving the code-base to make future enhancements easier and more reliable. We'll do one or two new releases, and then enter a stabilization phase. In particular, this will include:

      • Refactoring build plan construction and execution
      • Eliminating code duplication
      • Properly integrate code that was copied/pasted from other projects
      • Spinning off non-Stack-specific helper modules into separate packages
      • More integration tests
      • Bug fixes
      • Performance optimization

      During this period, minor pull requests with code cleanup, optimization, and additional tests will be gladly accepted, but please hold off on new features.

      Some ways you can help:

      • File issues identifying duplicate and sub-optimal code, and other quality issues
      • Submit pull requests with code cleanup, optimization, and additional integration tests (stack test --flag stack:integration-tests enables them). Best to check first to avoid conflicts in code that is being overhauled.
      • Github issue triage

      During this period, pull requests with new features are unlikely to be merged, so probably best to hold off to avoid a bunch of bitrotted PRs.

      Some things we're working on before beginning the stabilization phase:

      • All-in-one package builds when there are no cyclic dependencies #1166
      • Docker integration: Remove need for custom entrypoint and phusion init in Docker images #531 #547
      • Allow global options both before and after command #519

      November 07, 2015 05:00 AM

      November 04, 2015


      Implementing a minimal version of haskell-servant

      Recently, there was a question on Stack Overflow on how Servant actually works. Others were quick to suggest the Servant paper as a thorough explanation of the approach and the implementation.

      As a co-author, I’m obviously happy if the paper is being read, but it’s also 12 pages long in two-column ACM style. And while it explains the implementation, it does not necessarily make it easier to start playing with the code yourself, because it only shows excerpts, and code snippets in a paper are not easily runnable.

      At the same time, whenever I want to demonstrate a new concept in the Servant context, or play with new ideas, I find myself not impementing it in the main Servant code base, but rather to create a small library that is “like Servant”, built on the same principles, but much simpler, so that I have less work to do and can evaluate the ideas more quickly. I’ve talked to some other contributors, and at least some of them are doing the same. So I thought it might be useful to develop and present the code of “TinyServant”, which is not exactly tiny, but still small compared to the full Servant code base, strips away a lot of duplication and unessential extras, but is still complete enough so that we can observe how Servant works. Obviously, this still won’t explain everything that one might want to know about the implementation of Servant, but I hope that it will serve as a useful ingredient in that process.

      This blog post is a somewhat revised and expanded version of my Stack Overflow answer.

      This is not a general tutorial on Servant and using Servant. For learning how to use Servant, the official Servant tutorial or the general documentation section of the Servant home page are better starting points.

      The code

      The full code that is discussed in this post is 81 lines of Haskell and available separately.

      An overview

      I’m going to show the following things:

      1. How to define the web API specification language that Servant offers. We are going to define as few constructs as possible: we are not going to worry about content types (just plain text), we are not going to worry about different HTTP methods (just GET), and the only special thing we can do in routes will be that we can capture components of the path. Still, this is enough to show all relevant ideas of the Servant implementation.

      2. How to define an interpretation of the specification language. The point of Servant is that we can define many of these: an API can be interpreted as a web server (for various web backends), a web client (for various frontend languages, such as Haskell or JavaScript), a mock server, as documentation (in various formats) and more. Here, I’m going to implement an interpretation as a simplified Haskell function that can be seen as simulating a primitive web server, but without incurring any actual web dependencies.

      3. How to use TinyServant on an example. We are going to take the very first example of the Servant homepage and adapt it for our examples.


      To start, here are the language extensions we’ll need:

      {-# LANGUAGE DataKinds, PolyKinds, TypeOperators #-}
      {-# LANGUAGE TypeFamilies, FlexibleInstances, ScopedTypeVariables #-}
      {-# LANGUAGE InstanceSigs #-}

      The first three are needed for the definition of the type-level DSL itself. The DSL makes use of type-level strings (DataKinds) and also uses kind polymorphism (PolyKinds). The use of the type-level infix operators such as :<|> and :> requires the TypeOperators extension.

      The second three are needed for the definition of the interpretation. For this, we need type-level functions (TypeFamilies), some type class programming which will require FlexibleInstances, and some type annotations to guide the type checker which require ScopedTypeVariables.

      Purely for documentation purposes, we also use InstanceSigs.

      Here’s our module header:

      module TinyServant where
      import Control.Applicative
      import GHC.TypeLits
      import Text.Read
      import Data.Time

      The import of Data.Time is just for our example.

      API specifications

      The first ingredient is to define the datatypes that are being used for the API specifications.

      data Get (a :: *)
      data a :<|> b = a :<|> b
      infixr 8 :<|>
      data (a :: k) :> (b :: *)
      infixr 9 :>
      data Capture (a :: *)

      As I’ve said before, we define only four constructs in our simplified language:

      1. A Get a represents an endpoint of type a (of kind *). In comparison with full Servant, we ignore content types here. We need the datatype only for the API specifications. There are no directly corresponding values, and hence there is no constructor for Get.

      2. With a :<|> b, we represent the choice between two routes. Again, we wouldn’t need a constructor, but it will turn out to be useful later when we define handlers.

      3. With item :> rest, we represent nested routes, where item is the first path component and rest are the remaining components. In our simplified DSL, there are just two possibilities for item: a type-level string, or a Capture. Because type-level strings are of kind Symbol, but a Capture, defined below is of kind *, we make the first argument of :> kind-polymorphic, so that both options are accepted by the Haskell kind system. So in particular, we will be able to write both

        "person" :> Get Person


        Capture Currency :> Get Amount

        and it will be well-kinded.

      4. A Capture a represents a route component that is captured, parsed and then exposed to the handler as a parameter of type a. In full Servant, Capture has an additional string as a parameter that is used for documentation generation. We omit the string here.

      Example API

      We can now write down a version of the API specification from the Servant home page, adapted to our simplified DSL, and replacing the datatypes used there by actual datatypes that occur in the Data.Time library:

      type MyAPI = "date" :> Get Day
              :<|> "time" :> Capture TimeZone :> Get ZonedTime

      Interpretation as server

      The most interesting aspect is of course what we can do with the API. Servant defines several interpretations, but they all follow a similar pattern. We’ll define only one here, which is inspired by the interpretation as a web server.

      In Servant, the serve function has the following type:

      serve :: HasServer layout
            => Proxy layout -> Server layout -> Application

      It takes a proxy for the API type (we’ll get back to that in a moment), and a handler matching the API type (of type Server layout) to an Application. The Application type comes from the excellent WAI library that Servant uses as its default backend.

      Even though WAI is very simple, it is too complicated for the purposes of this post, so we’ll assume a “simulated server” of type

      [String] -> IO String

      This server is supposed to receive a request that is just a sequence of path components ([String]). We do not care about request methods or the request body or anything like that. And the response it just a message of type String. We ignore status codes, headers and anything else. The underlying idea is still the same though than that of the Application type used in the actual Servant implementation.

      So our serve function has type

      serve :: HasServer layout
            => Proxy layout -> Server layout -> [String] -> IO String

      The HasServer class, which we’ll define below, has instances for all the different constructs of the type-level DSL and therefore encodes what it means for a Haskell type layout to be interpretable as an API type of a server.

      The Proxy type is defined as follows: It’s defined as

          data Proxy a = Proxy

      Its only purpose is to help the GHC type checker. By passing an explicitly typed proxy such as Proxy :: Proxy MyAPI to serve, we can explicitly instantiate the serve function to a particular API type. Without the Proxy, the only occurrences of the layout parameter would be in the HasServer class constraint and as an argument of Server, which is a type family. GHC is not clever enough to infer the desired value of layout from these occurrences.

      The Server argument is the handler for the API. As just stated, Server itself is a type family (i.e., a type-level function), and computes from the API type the type that the handler(s) must have. This is one core ingredient of what makes Servant work correctly.

      From these inputs, we then compute the output function of type [String] -> IO String as explained above.

      The Server type family

      We define Server as a type family first. (Again, this is somewhat simplified compared to Servant, which defines a monad transformer type family called ServerT as part of the HasServer class and then a top-level type synonym Server in terms of ServerT.)

      type family Server layout :: *

      The handler for a Get a endpoint is simply an IO action producing an a. (Once again, in the full Servant code, we have slightly more options, such as producing an error with a choice of status codes.)

      type instance Server (Get a) = IO a

      The handler for a :<|> b is a pair of handlers, so we could just define

      type instance Server (a :<|> b) = (Server a, Server b) -- preliminary

      But with this definition, nested occurrences of :<|> in the API would lead to nested pairs of handlers, so we’d have to write code like

      (handler1, (handler2, handler3))

      which looks a bit ugly. Instead, we’re going to make :<|> equivalent to Haskell’s pair type, but with an infix constructor called :<|>, so that we can write

      handler1 :<|> handler2 :<|> handler3

      for a nested pair. The actual definition of Server for :<|> is then

      type instance Server (a :<|> b) = Server a :<|> Server b

      It remains to explain how each of the path components is handled.

      Literal strings in the routes do not affect the type of the handler:

      type instance Server ((s :: Symbol) :> r) = Server r

      A capture, however, means that the handler expects an additional argument of the type being captured:

      type instance Server (Capture a :> r) = a -> Server r

      Computing the handler type of the example API

      If we expand Server MyAPI, we obtain

         Server MyAPI
      ~  Server (     "date" :> Get Day
                 :<|> "time" :> Capture TimeZone :> Get ZonedTime
      ~       Server ("date" :> Get Day)
         :<|> Server ("time" :> Capture TimeZone :> Get ZonedTime)
      ~       Server (Get Day)
         :<|> Server ("time" :> Capture TimeZone :> Get ZonedTime)
      ~       IO Day
         :<|> Server ("time" :> Capture TimeZone :> Get ZonedTime)
      ~       IO Day
         :<|> Server (Capture TimeZone :> Get ZonedTime)
      ~       IO Day
         :<|> TimeZone -> Server (Get ZonedTime)
      ~       IO Day
         :<|> TimeZone -> IO ZonedTime

      where ~ is GHC’s syntax for type equality.

      Recall that :<|> as defined is equivalent to a pair. So as intended, the server for our API requires a pair of handlers, one that provides a date of type Day, and one that, given a time zone, provides a time (of type ZonedTime). We can define the handler(s) right now:

      handleDate :: IO Day
      handleDate = utctDay <$> getCurrentTime
      handleTime :: TimeZone -> IO ZonedTime
      handleTime tz = utcToZonedTime tz <$> getCurrentTime
      handleMyAPI :: Server MyAPI
      handleMyAPI = handleDate :<|> handleTime

      The HasServer class

      We still have to implement the HasServer class, which looks as follows:

      class HasServer layout where
        route :: Proxy layout -> Server layout -> [String] -> Maybe (IO String)

      The task of the function route is almost like serve. Internally, we have to dispatch an incoming request to the right router. In the case of :<|>, this means we have to make a choice between two handlers. How do we make this choice? A simple option is to allow route to fail, by returning a Maybe. Then in a choice we can just try the first option, and if it returns Nothing, try the second. (Again, full Servant is somewhat more sophisticated here, and version 0.5 will have a much improved routing strategy, which probably at some point in the future deserves to be the topic of its own blog post.)

      Once we have route defined, we can easily define serve in terms of route:

      serve :: HasServer layout
            => Proxy layout -> Server layout -> [String] -> IO String
      serve p h xs = case route p h xs of
        Nothing -> ioError (userError "404")
        Just m  -> m

      If none of the routes match, we fail with a (simulated) 404. Otherwise, we return the result.

      The HasServer instances

      For a Get endpoint, we defined

      type instance Server (Get a) = IO a

      so the handler is an IO action producing an a, which we have to turn into a String. We use show for this purpose. In the actual Servant implementation, this conversion is handled by the content types machinery, and will typically involve encoding to JSON or HTML.

      instance Show a => HasServer (Get a) where
        route :: Proxy (Get a)
              -> IO a -> [String] -> Maybe (IO String)
        route _ handler [] = Just (show <$> handler)
        route _ _       _  = Nothing

      Since we’re matching an endpoint only, the require the request to be empty at this point. If it isn’t, this route does not match and we return Nothing.

      Let’s look at choice next:

      instance (HasServer a, HasServer b) => HasServer (a :<|> b) where
        route :: Proxy (a :<|> b)
              -> (Server a :<|> Server b) -> [String] -> Maybe (IO String)
        route _ (handlera :<|> handlerb) xs =
              route (Proxy :: Proxy a) handlera xs
          <|> route (Proxy :: Proxy b) handlerb xs

      Here, we get a pair of handlers, and we use <|> for Maybe to try both, preferring the first if it matches.

      What happens for a literal string?

      instance (KnownSymbol s, HasServer r) => HasServer ((s :: Symbol) :> r) where
        route :: Proxy (s :> r)
              -> Server r -> [String] -> Maybe (IO String)
        route _ handler (x : xs)
          | symbolVal (Proxy :: Proxy s) == x = route (Proxy :: Proxy r) handler xs
        route _ _       _                     = Nothing

      The handler for s :> r is of the same type as the handler for r. We require the request to be non-empty and the first component to match the value-level counterpart of the type-level string. We obtain the value-level string corresponding to the type-level string literal by applying symbolVal. For this, we need a KnownSymbol constraint on the type-level string literal, but all concrete literals in GHC are automatically an instance of KnownSymbol.

      The final case is for captures:

      instance (Read a, HasServer r) => HasServer (Capture a :> r) where
        route :: Proxy (Capture a :> r)
              -> (a -> Server r) -> [String] -> Maybe (IO String)
        route _ handler (x : xs) = do
          a <- readMaybe x
          route (Proxy :: Proxy r) (handler a) xs
        route _ _       _        = Nothing

      In this case, we can assume that our handler is actually a function that expects an a. We require the first component of the request to be parseable as an a. Here, we use the Read class, whereas in Servant, we use a special-purpose class called FromText (or FromHttpApiData in version 0.5). If reading fails, we consider the request not to match. Otherwise, we can feed it to the handler and continue.

      Testing everything

      Now we’re done.

      We can confirm that everything works in GHCi:

      GHCi> serve (Proxy :: Proxy MyAPI) handleMyAPI ["time", "CET"]
      "2015-11-01 20:25:04.594003 CET"
      GHCi> serve (Proxy :: Proxy MyAPI) handleMyAPI ["time", "12"]
      *** Exception: user error (404)
      GHCi> serve (Proxy :: Proxy MyAPI) handleMyAPI ["date"]
      GHCi> serve (Proxy :: Proxy MyAPI) handleMyAPI []
      *** Exception: user error (404)

      We now have a system that we can play with an extend and modify easily. We can for example extend the specification language by a new construct and see what we have to change. We can also make the simulation more faithful (e.g. include request bodies or query parameters). Or we can define a completely different interpretation (e.g. as a client) by following the same scheme.

      by andres at November 04, 2015 11:38 AM

      November 03, 2015

      Joey Hess

      STM Region contents

      concurrent-output released yesterday got a lot of fun features. It now does full curses-style minimization of the output, to redraw updated lines with optimal efficiency. And supports multiline regions/wrapping too long lines. And allows the user to embed ANSI colors in a region. 3 features that are in some tension and were fun to implement all together.

      But I have a more interesting feature to blog about... I've added the ability for the content of a Region to be determined by a (STM transaction).

      Here, for example, is a region that's a clock:

      timeDisplay :: TVar UTCTime -> STM Text
      timeDisplay tv = T.pack . show <$> readTVar tv
      clockRegion :: IO ConsoleRegionHandle
      clockRegion = do
          tv <- atomically . newTVar =<< getCurrentTime
          r <- openConsoleRegion Linear
          setConsoleRegion r (timeDisplay tv)
          async $ forever $ do
              threadDelay 1000000 -- 1 sec
              atomically . (writeTVar tv) =<< getCurrentTime
          return r

      There's something magical about this. Whenever a new value is written into the TVar, concurrent-output automatically knows that this region needs to be updated. How does it know how to do that?

      Magic of STM. Basically, concurrent-output composes all the STM transactions of Regions, and asks STM to wait until there's something new to display. STM keeps track of whatever TVars might be looked at, and so can put the display thread to sleep until there's a change to display.

      Using STM I've gotten extensability for free, due to the nice ways that STM transactions compose.

      A few other obvious things to do with this: Compose 2 regions with padding so they display on the same line, left and right aligned. Trim a region's content to the display width. (Handily exported by concurrent-output in a TVar for this kind of thing.)

      I'm tempted to write a console spreadsheet using this. Each visible cell of the spreadsheet would have its own region, that uses a STM transaction to display. Plain data Cells would just display their current value. Cells that contain a function would read the current values of other Cells, and use that to calculate what to display. Which means that a Cell containing a function would automatically update whenever any of the Cells that it depends on were updated!

      Do you think that a simple interactive spreadsheet built this way would be more than 100 lines of code?

      November 03, 2015 08:03 PM

      November 02, 2015

      Douglas M. Auclair (geophf)

      October 2015 1HaskellADay 1-Liners

      • October 15th, 2015: Matrix-themed problem
        dotProduct :: Num a => [a] -> [a] -> a
        dotProduct a b = sum (zipWith (*) a b)
        point-free-itize the definition
        • Freddy Román @frcepeda dotProduct = sum `dot` zipWith (*) where dot = (.).(.)
      • October 13th, 2015: You're given either fst or snd, but don't know which. Define a function that returns its dual:
        dual :: ((a,a) -> a) -> ((a,a) -> a)
        n.b.: The tuples here have BOTH fst and snd as the same type: a
        Also, a-values have NO typeclass constraints. You CAN NOT use (==) nor (>)
        • Michael Thomas @mjtjunior dual f = f (snd,fst)
        • Francisco Soares Nt @frsoares dual = uncurry . flip . curry
        • Fernando Castor @fernandocastor dual f = \(x,y) -> f (y, x)
          (I hadn't seen @mjtjunior's answer beforehand)
        • Андреев Кирилл @nonaem00 (. Data.Tuple.swap)

      by geophf ( at November 02, 2015 09:39 PM

      Mark Jason Dominus

      A message to the aliens, part 18/23 (cell respiration and division)

      Earlier articles: Introduction Common features Page 1 (numerals) Page 2 (arithmetic) Page 3 (exponents) Page 4 (algebra) Page 5 (geometry) Page 6 (chemistry) Page 7 (mass) Page 8 (time and space) Page 9 (physical units) Page 10 (temperature) Page 11 (solar system) Page 12 (Earth-Moon system) Page 13 (days, months, and years) Page 14 (terrain) Page 15 (human anatomy) Page 16 (vital statistics) Page 17 (DNA chemistry)

      This is page 18 of the Cosmic Call message. An explanation follows.

      The 10 digits are:











      This page depicts the best way to fry eggs. The optimal fried egg is shown at left. Ha ha, just kidding. The left half of the page explains cellular respiration. The fried egg is actually a cell, with a DNA molecule in its nucleus. Will the aliens be familiar enough with the structure of DNA to recognize that the highly abbreviated picture of the DNA molecule is related to the nucleobases on the previous page? Perhaps, if their genetic biochemistry is similar to ours, but we really have no reason to think that it is.

      The top formula says that C6H12O6 and O2 go in; the bottom formula says that CO2 comes out. (Energy comes out also; I wonder why this wasn't mentioned.) The notation for chemical compounds here is different from that used on page 14: there, O2 was written as ; here it is written as (“2×O”).

      The glyph near the left margin does not appear elsewhere, but I think it is supposed to mean “cell”. Supposing that is correct, the text at the bottom says that the number of cells in a man or woman is . The number of cells in a human is not known, except very approximately, but is probably the right order of magnitude. (A 2013 paper from Annals of Human Biology estimates .)

      Next to the cell is a ruler labeled meters, which is a typical size for a eukaryotic cell.

      The illustration on the right of the page, annotated with the glyphs for the four nucleobases from the previous page , depicts the duplication of genetic material during cellular division. The DNA molecule splits down the middle like a zipper. The cell then constructs a new mate for each half of the zipper, and when it divides, each daughter cell gets one complete zipper.

      The next article will discuss pages 19 and 20, shown at right. (Click to enlarge.) Try to figure it out before then.

      by Mark Dominus ( at November 02, 2015 03:04 PM

      Derek Elkins

      You know more about presheaves than you think

      The category of graphs as a presheaf

      Here’s a small example of why people find category theory interesting. Consider the category, call it |ccC|, consisting of two objects, which we’ll imaginatively name |0| and |1|, and two non-identity arrows |s,t : 0 -> 1|. The category of graphs (specifically directed multigraphs with loops) is the category of presheaves over |ccC|, which is to say, it’s the category of contravariant functors from |ccC| to |cc"Set"|. I’ll spell out what that means momentarily, but first think about what has been done. We’ve provided a complete definition of not only graphs but the entire category of graphs and graph homomorphisms given you’re familiar with very basic category theory1. This is somewhat magical.

      Spelling things out, |G| is a contravariant functor from |ccC| to |cc"Set"|. This means that |G| takes each object of |ccC| to a set, i.e. |G(0) = V| and |G(1) = E| for arbitrary sets |V| and |E|, but which will represent the vertices and edges of our graph. In addition, |G| takes the arrows in |ccC| to a (set) function, but, because it’s contravariant, it flips the arrows around. So we have, for example, |G(s) : G(1) -> G(0)| or |G(s) : E -> V|, and similarly for |t|. |G(s)| is a function that takes an edge and gives its source vertex, and |G(t)| gives the target. The arrows in the category of graphs are just natural transformations between the functors. In this case, that means if we have two graphs |G| and |H|, a graph homomorphism |f : G -> H| is a pair of functions |f_0 : G(0) -> H(0)| and |f_1 : G(1) -> H(1)| that satisfy |H(s) @ f_1 = f_0 @ G(s)| and |H(t) @ f_1 = f_0 @ G(t)|. With a bit of thought you can see that all this says is that we must map the source and target of an edge |e| to the source and target of the edge |f_1(e)|. You may also have noticed that any pair of sets and pair of functions between them is a graph. In other words, graphs are very simple things. This takes out a lot of the magic, though it is nice that we get the right notion of graph homomorphism for free. Let me turn the magic up to 11.

      Presheaves are extremely important in category theory, so categorists know a lot about them. It turns out that they have a lot of structure (mostly because |cc"Set"| has a lot of structure). In particular, in the categorical jargon, if |ccC| is small (and finite is definitely small), then the category of presheaves over |ccC| is a complete and cocomplete elementary topos with a natural number object. For those of you learning category theory who’ve gotten beyond the basics, proving this is a very good and important exercise. In programmer-speak, that says we can do dependently typed lambda calculus with algebraic data and codata types in that category. To be clear, this is not saying we have a lambda calculus with a graph type. It’s saying we have a lambda calculus where all our types have graph structure.

      Beyond graphs

      But set that aside for now. This isn’t an article about graphs so let’s start generalizing away from them. We’ll start with a baby step. You can probably guess how we’d go about making edge labeled graphs. We’d add another object to |ccC|, say |2|, and an arrow from |2| to |1|, call it |l_e| — remember that the arrows are “backwards” because presheaves are contravariant. You may start seeing a pattern already. One way to start formalizing that pattern is to say for every object of |ccC| we have an abstract data type with a field for each arrow into that object. In our example, |1| has three arrows into it, namely |s|, |t|, and |l_e|. We can view an element |e in F(1)| for a presheaf |F| as having fields e.s, e.t and e.l_e. Since |cc"Set"| has (non-constructive, non-computable) decidable equality for everything, we can tell |e| from |e’| even if e.s = e'.s and e.t = e'.t and e.l_e = e'.l_e. This is different from a normal abstract data type (in a purely functional language) where an abstract data type with three fields would be isomorphic to a 3-tuple. The extra ability to differentiate them could be modeled by having a fourth field that returned something that could only be compared for equality, kind of like Data.Unique (ignoring the Ord instance…) It may look like:

      data Vertex -- abstract
      vertexId :: Vertex -> Unique
      data Label -- abstract
      labelId :: Label -> Unique
      data Edge -- abstract
      edgeId :: Edge -> Unique
      src :: Edge -> Vertex
      tgt :: Edge -> Vertex
      label :: Edge -> Label

      Of course, if these are literally all the functions we have for these types (plus some constants otherwise we can’t make anything), then these abstract types might as well be records. Anything else they have is unobservable and thus superfluous.

      data Vertex = Vertex { vertexId :: Unique }
      data EdgeLabel = EdgeLabel { edgeLabelId :: Unique }
      data Edge = Edge { 
          edgeId :: Unique, 
          src :: Vertex, 
          tgt :: Vertex,
          edgeLabel :: EdgeLabel

      This starts to suggest that we can just turn each object in our category |ccC| into a record with an ID field. Each arrow in to that object becomes an additional field. This almost works. We’ll come back to this, but let’s take another baby step.

      Something a bit more interesting happens if we want to label the vertices. We proceed as before: add another object, call it |3|, and another arrow |l_v : 3 -> 0|. This time, though, we’re not finished. |ccC| is supposed to be a category, so we can compose arrows and thus we have two composites but no arrow for the composites to be, namely: |s @ l_v| and |t @ l_v|. The abstract data type intuition suggests that whenever we run into this situation, we should add a distinct arrow for each composite. For the purpose of labeling vertices, this is the right way to go: we want to think of each vertex as having a vertex label field with no constraints. There is, however, another choice. We could add one new arrow and have both composites be equal to it. What that would say is that for every edge, the source and the target vertices must have the same label. It’s easy to see that that would lead to every vertex in a connected component having the same label. In code, the former choice would look like:

      data VertexLabel = VertexLabel { vertexLabelId :: Unique }
      data Vertex = Vertex { 
          vertexId :: Unique,
          vertexLabel :: VertexLabel
      data EdgeLabel = EdgeLabel { edgeLabelId :: Unique }
      data Edge = Edge { 
          edgeId :: Unique, 
          src :: Vertex, 
          tgt :: Vertex,
          edgeLabel :: EdgeLabel
          -- With our earlier "rule" to add a field for each arrow
          -- we should also have:
          --    srcVertexLabel :: VertexLabel
          --    tgtVertexLabel :: VertexLabel
          -- but, by definition, these are:
          --    vertexLabel . src and
          --    vertexLabel . tgt respectively.
          -- So we don't explicitly add a field for composite arrows.

      The latter choice would look the same, except there would be an extra constraint that we can’t capture in Haskell, namely vertexLabel . src == vertexLabel . tgt.

      If we stick to the abstract data type intuition and we have a cycle in the arrows in |ccC|, then the requirement to add a distinct arrow for each composite means we need to add a countably infinite number of arrows, so |ccC| is no longer finite. It is still “small” though, so that’s no problem. We could say we have a finite graph of the non-composite arrows and possibly some equations like |s @ l_v = t @ l_v| and we generate a category from that graph subject to those equations by adding in all composites as necessary. We will use the arrows in this graph to decide on the fields for our abstract data types, rather than the arrows in the category so we don’t end up with an infinity of fields in our data types. Even when there aren’t an infinite number of arrows in our category, this is still useful since we aren’t going to add a field to our edges to hold each vertex’s label, since we can just get the vertex and then get the label.

      Some of you have probably thought of another more appropriate intuition. A presheaf is a database. The category which our presheaf is over, what we’ve been calling |ccC| 2 is sort of like a schema. You don’t specify types, but you do specify foreign key relationships plus some additional integrity constraints that don’t fit in to the typical ones supported by databases.

      Presheaves as databases

      For our earlier example:

      CREATE VertexLabel (Id uniqueidentifier PRIMARY KEY);
      CREATE Vertex (
          Id uniqueidentifier PRIMARY KEY,
          Label uniqueidentifier REFERENCES VertexLabel(Id)
      CREATE EdgeLabel (Id uniqueidentifier PRIMARY KEY);
      CREATE Edge (
          Id uniqueidentifier PRIMARY KEY,
          Src uniqueidentifier REFERENCES VertexLabel(Id),
          Tgt uniqueidentifier REFERENCES VertexLabel(Id),
          Label uniqueidentifier REFERENCES EdgeLabel(Id)
          -- Nothing stops us from having additional columns here and elsewhere
          -- corresponding to the fact that our types were really abstract data
          -- types in the Haskell, and to the fact that we can choose an arbitrary
          -- set as long as it has at least this much structure.  They won't be
          -- preserved by "homomorphisms" though.

      To be clear, each presheaf corresponds to a database with data. Inserting a row into a table is a homomorphism of presheaves, but so is adding a (not preserved by homomorphism) column. The schema above corresponds to the |ccC| part of the presheaf.

      If we had made that second choice before where we had only one arrow back that would lead to the following integrity constraint:

                 FROM Edge e
                 JOIN Vertex src ON e.Src = src.Id
                 JOIN Vertex tgt ON e.Tgt = tgt.Id
                 WHERE src.Label <> tgt.Label)

      It turns out this intuition is completely general. You can actually think of all of presheaf theory as a (slightly unusual) database theory. More objects just means more tables. More arrows means more foreign keys and potentially additional integrity constraints. It’s not exactly relational though. In fact, in some ways it’s a bit closer to SQL3 or object databases. You can turn this around too going back to the point at the beginning. Whether or not we can think of all presheaves like databases or all databases like presheaves, we can certainly think of this example, and many like it, as presheaves. This means for many “databases”, we can talk about doing dependently typed programming where our types are databases of the given shape. This also dramatically shifts the focus in database theory from databases to database migrations, i.e. homomorphisms of databases.

      David Spivak is the one who has done the most on this, so I’ll refer you to his work. He also has a better story for schemas that are much closer to normal schemas. I’ll end as I began:

      Here’s a small example of why people find category theory interesting.

      1. “very basic category theory” means knowing the definitions of categories, isomorphisms, functors, and natural transformations

      2. remember the presheaf is the functor from |ccC^(op) -> cc“Set”|

      3. SQL is hardly the relational ideal

      November 02, 2015 12:04 PM

      FP Lunch

      How to Distribute a Study Report

      Your pit bull could be the lighting of one’s life, but you will need the correct reports when you wish his renowned background to be appreciated by others. His lineage is traced by a pitbull’s forms and present how superior his breeding in fact is. Then there is no solution to get paperwork, in the event one’s pitbull werent’s parents registered. A pitbull with paperwork could be able to contend in puppy exhibits, and his pups can demand a greater value from owners that are prospective. Recommendations Examine the paperwork whenever you ordered your pitbull that you obtained. You could possess a Puppy Registration App from the Kennel Club and should have a subscription certificate. Contact your breeder in the event you didn’t get paperwork.

      Error you cannot process articles longer than 5,000 words.

      Ask for a registration certificate. Request if your pet is not ineligible for the American Kennel Team based on his reputation. If he is, request an Registration Program. Enroll your dog using the American Kennel Team utilizing the documents you received from your own breeder. You are able to do this online at with the AKC site,, and clicking on “Subscription.” Input information regarding yourself and your dog to get him documented and acquire paperwork. A charge is for joining your dog. Enroll your pet with other teams for additional paperwork. Corporations like the American Pitbull Registry and the United Club can register your dog and provide you with paperwork demonstrating that enrollment.

      by Administrator at November 02, 2015 09:25 AM

      Brent Yorgey

      ICFP roundup

      Well, ICFP 2015 in Vancouver is already two months in the past… I’ve been meaning for a while to write a post reflecting on the experience. Better late than never!

      The Place

      I had never been to Vancouver before; it seems like a beautiful and fun city. One afternoon I skipped all the talks and went for a long hike—I ended up walking around the entire perimeter of the Stanley Park seawall, which was gorgeous. The banquet was at the (really cool) aquarium—definitely the first time I have eaten dinner while being watched by an octopus.

      The People

      Instead of staying in the conference hotel, four of us (me, Ryan Yates, Ryan Trinkle, and Michael Sloan) rented an apartment through AirBnB.1 The apartment was really great, it ended up being cheaper per person than sharing two hotel rooms, and it was a lot of fun to have a comfortable place to hang out in the evenings—where we could sit around in our pajamas, and talk, or write code, or whatever, without having to be “on”.

      I met some new people, including Aahlad Gogineni from Tufts (along with another Tufts student whose name I unfortunately forget); Zac Slade and Boyd Smith from my new home state of Arkansas; and some folks from Vancouver whose names I am also blanking on at the moment. I also met a few people in person for the first time I had previously only communicated with electronically, like Rein Heinrich and Chris Smith.

      I also saw lots of old friends—way too many to list. It once again reminded me how thankful I am to be part of such a great community. Of course, the community is also far from perfect; towards that end I really enjoyed and appreciated the ally skills tutorial taught by Valerie Aurora (which probably deserves its own post).

      The Content

      Here are just a few of my favorite talks:

      I had a lot of great discussions relating to diagrams. For example:

      • I talked with Alan Zimmerman about using his and Matthew Pickering’s great work on ghc-exactprint with an eye towards shipping future diagrams releases along with an automated refactoring tool for updating users’ diagrams code.

      • After talking a bit with Michael Sloan I got a much better sense for the ways stack can support our development and CI testing process.

      • I had a lot of fun talking with Ryan Yates about various things, including projecting diagrams from 3D into 2D, and reworking the semantics and API for diagrams’ paths and trails to be more elegant and consistent. We gave a presentation at FARM which seemed to be well-received.

      I got another peek at how well Idris is coming along, including a few personal demonstrations from David Christiansen (thanks David!). I am quite impressed, and plan to look into using it during the last few weeks of my functional programming course this spring (in the past I have used Agda).

      If I had written this as soon as I got back, I probably could have remembered a lot more; oh well. All in all, a wonderful week, and I’m looking forward to Japan next year!

      1. Yes, I know that hotel bookings help pay for the conference, and I admit to feeling somewhat conflicted about this.

      2. I asked him afterwards how he made the great animations in his slides, and sadly it seems he tediously constructed them using PowerPoint. Someday, it will be possible to do this with diagrams!

      by Brent at November 02, 2015 02:47 AM

      November 01, 2015

      FP Lunch

      Scholarships with February 2015 deadlines

      Buying a vehicle from a private retailer who still owes cash about the car can be complex. Owner won’t manage to exchange the title of the vehicle for you before loan is paid down. Before the mortgage is paid down, a lien may stick to the car, and as a shopper, you may not wish to be held responsible for that mortgage along with everything you pay for the car. You are able to make sure that you will not find yourself using an unforeseen fiscal pressure, by using certain precautions. Ad Measures Part 1 of 2: If Income Is Owed Discovering Talk with the DMV. Should you live in the United States, you’re able to verify the reputation of a caris lien by visiting a state’s DMV website. You’ll have to know the vehicle’s produce, design, and vehicle identification number (VIN), that may all be on the vehicleis registration paperwork. Generally an inquiry can follow exactly the same procedure, although approach may vary somewhat by condition. The DMV will have the ability to inform you the final day that a concept was processed because express, how many liens (if any) occur to the vehicle, along with the title and tackle of each mortgage holder.

      Figure out how to deliver and demand cash.

      Give your contact information inside the online type through the DMV’s website. Fill out all of the vital information for the DMV to recognize the car. This can usually include the produce, design of the automobile, in addition to the VIN. Save the shape using Adobe. Connect in an email and send it for the email listed about the DMV site. Advertising Search on the internet. Several sites, including Carfax and, let you search for mortgage information, utilizing the VIN and also the make and style of the vehicle.

      And tea tree gas has agents in-it which might be drying agents.

      Many of these websites are free, while a payment charges. Talk with the Private Property Securities Register. Some places have a government-manage Individual Home Investments Register, or possibly a similar registry in position, in which safety interests held in private property (in this instance, vehicles) are cataloged online and may be sought out by interested parties. You can search online to learn if the car you are buying has money owed about it if you live-in a location that’s such a registry. Consumers in Australia and New Zealand may go to and click “research.” Customers may also have search engine results texted to your cellular phone for a $3 service fee. Work an HPI Check. HPI Inspections could inform potential buyers perhaps the car is compromised or has improved distance, along with in case a car has excellent fund owed about it.

      So that the left edge sets contrary to the report manual heap the paper.

      HPI Inspections are blame, but can offer peace of mind in regards to purchasing a used-vehicle. Ask to view document or the concept of registration. In a few places, a car seller must exhibit a replica of the state document of enrollment, which may only be had if there are no debts owed around the automobile to audience. In other countries, the autois title may echo the bank has liens on the car, suggesting that the supplier has outstanding loans having a standard bank. Advertising Part 2 of 2: Obtaining The Debt Settled Consult the vendor to cover. If you’re thinking about buying a car or truck with funds you may want to demand that the seller takes care of his debt before you supply him any money. You might want to claim that owner take an individual mortgage out to protect the expenses, before you get it as a way to secure the concept. Should you insist the seller takes care of his loans before you buy the automobile, be sure you get a signed, written proof of payment from capital company or the selleris lender. If you can, accompany the seller to standard bank or the lender so that you can supervise the method and realize for certain that the automobile’s loans have already been settled in full.

      Since it moves to another from era, training is just the heart of a community.

      If those possibilities are available where you will purchase the vehicle you might want to run another search through PPSR or HPI if you fail to get anything written down from the bank confirming the loans were compensated entirely. This can permit you to validate that the loans have now been satisfied. Renegotiate the purchase price. If you’re still considering buying the vehicle, make an effort to renegotiate the purchase price you’d pay for the retailer, after factoring in just how much he nevertheless owes around the vehicleis loans. Deduct the amount that the supplier owes for the bank in the price you originally assumed was a reasonable income cost for that car. Supply to cover the seller that quantity, after you’ve paid the rest of owneris loan towards lender that has a mortgage about the automobile or the bank. Possess the owner send you an old commission quote.

      Understand somebody you rely register your manager that is investigate.

      Once you have paid the mortgage, and presented the seller any leftover money after agreeing over a price, you may have the concept used in your title. Set up. If you worry about owner not holding his end-of the settlement to pay his auto loans off, you are able to always put up an escrow account. Your money would be held by this for a predetermined period of time, during which the vendor must pay-off his loans and exchange you the title to be able to get your money. Within the United States, the Department of Motor Vehicles advises using Escrow. Set a merchant account up at. Produce a deal, and also have the seller consent to conditions and the terms. Deposit your cash. Until the loans have already been settled PaySAFE will not release the amount of money to the supplier and the title is ready to change hands.

      You have to grieve these overlooked requirements and to know and confirm what happened.

      Ask a seller to agent the selling. By finding a dealership included, you make certain that title is legitimate and that you will have a document trail that proves all obligations were manufactured. You may have to pay more, since the dealer will want to make a gain buying the auto from the supplier and in convert promoting you it, but you’ll have peaceofmind with your purchase. Anticipate this to be a costlier alternative, while the seller will want to produce some cash from your sale. You could ask the vendor so you don’t wind up paying out more for the vehicle to cover the vendor out of her or his earnings. Ad We could truly utilize your support! Can you inform US about Locks? Yes No Can you reveal about Pokemon? Yes No Can you inform US about Cold candy?

      Do not only quit at building a checklist while producing the proposal.

      Yes No Can you tell us about Taking care of legs? Yes No For aiding cheers! Please reveal everything you find out about… Tell us whatever you know below. Remember detail is much better. Ideas Present specifics. Please be detailed as you can in your reason. We revise it for accuracy and understanding will get your comprehensive data, and incorporate it into articles that will assist a large number of people. Do not state: Eat fats.

      This will assist us acknowledge and take care of several types of problems.

      Do claim: Incorporate fats with a few vitamins and minerals to the ingredients you previously eat. Attempt butter, olive oil, grape. Ideas Contemplate obtaining legitimate help in this subject. After you pay owner, you want to make sure you own the car clear and free of any lender mortgage. Legal counselor or legal counsel can help you ensure you are secured. Alerts Be sure in case you pick that option, to make use of a reliable escrow service. Look for a lender or additional brokerage who seasoned and is qualified.

      by Administrator at November 01, 2015 03:09 PM

      Magnus Therning

      Docker container with ip address on local network, p2

      In my latest post I described described a way to give a docker container an address on the local network. That’s a general way of achieving it, but it’s also rather complicated. If you know exactly what ports need to be exposed there is a simpler way.

      Add a second IP to the system interface

      There’s a good description on how to give an interface multiple in Debian at the Debian Wiki. The completely manual way is

      ip addr add dev eth0 label eth0:0

      The configuration in Debian is

      auto eth0:0
      iface eth0:0 inet static

      If you’re using Systemd it seems to be enough to just add extra Address=... statements to the .network file:


      Bind ports of the container to a specific IP

      Using the image from my latest post it’s just to run it using the --publish option:

      docker --rm --interactive --tty --name=echo --publish= nw /home/myusre/echosrv

      Just like the last time it’s easy to verify everything’s working using netcat.

      November 01, 2015 12:00 AM

      October 31, 2015

      Dominic Steinitz

      Girsanov’s Theorem


      We previously used importance sampling in the case where we did not have a sampler available for the distribution from which we wished to sample. There is an even more compelling case for using importance sampling.

      Suppose we wish to estimate the probability of a rare event. For example, suppose we wish to estimate \mathbb{P}(X > 5) where X \sim {\mathcal{N}}(0,1). In this case, we can look up the answer \mathbb{P}(X > 5) \approx 2.86710^{-7}. But suppose we couldn’t look up the answer. One strategy that might occur to us is to sample and then estimate the probability by counting the number of times out of the total that the sample was bigger than 5. The flaw in this is obvious but let’s try it anyway.

      > module Girsanov where
      > import qualified Data.Vector as V
      > import Data.Random.Source.PureMT
      > import Data.Random
      > import Control.Monad.State
      > import Data.Histogram.Fill
      > import Data.Histogram.Generic ( Histogram )
      > import Data.Number.Erf
      > import Data.List ( transpose )
      > samples :: (Foldable f, MonadRandom m) =>
      >                     (Int -> RVar Double -> RVar (f Double)) ->
      >                     Int ->
      >                     m (f Double)
      > samples repM n = sample $ repM n $ stdNormal
      > biggerThan5 :: Int
      > biggerThan5 = length (evalState xs (pureMT 42))
      >   where
      >     xs :: MonadRandom m => m [Double]
      >     xs = liftM (filter (>= 5.0)) $ samples replicateM 100000

      As we might have expected, even if we draw 100,000 samples, we estimate this probability quite poorly.

      ghci> biggerThan5

      Using importance sampling we can do a lot better.

      Let \xi be a normally distributed random variable with zero mean and unit variance under the Lebesgue measure \mathbb{P}. As usual we can then define a new probability measure, the law of \xi, by

      \displaystyle   \begin{aligned}  \mathbb{P}_\xi((-\infty, b])  &= \frac{1}{\sqrt{2\pi}}\int_{-\infty}^b e^{-x^2/2}\,\mathrm{d}x  \end{aligned}


      \displaystyle   \begin{aligned}  \mathbb{E}_\xi(f) &= \frac{1}{\sqrt{2\pi}}\int_{-\infty}^\infty f(x) e^{-x^2/2}\,\mathrm{d}x \\  &= \frac{1}{\sqrt{2\pi}}\int_{-\infty}^\infty f(x) e^{a^2/2}e^{-a x}e^{-(x-a)^2/2}\,\mathrm{d}x \\  &= \mathbb{E}_{\xi + a}(fg) \\  &= \mathbb{\tilde{E}}_{\xi + a}(f)  \end{aligned}

      where we have defined

      \displaystyle   g(x) \triangleq e^{a^2/2}e^{-a x}  \quad \mathrm{and} \quad  \mathbb{\tilde{P}}((-\infty, b]) \triangleq \int_{-\infty}^b g(x)\,\mathrm{d}x

      Thus we can estimate \mathbb{P}(X > 5) either by sampling from a normal distribution with mean 0 and counting the number of samples that are above 5 or we can sample from a normal distribution with mean 5 and calculating the appropriately weighted mean

      \displaystyle   \frac{1}{n}\sum_{i=1}^n \mathbb{I}_{\{x > 5\}}g(y)

      Let’s try this out.

      > biggerThan5' :: Double
      > biggerThan5' = sum (evalState xs (pureMT 42)) / (fromIntegral n)
      >   where
      >     xs :: MonadRandom m => m [Double]
      >     xs = liftM (map g) $
      >          liftM (filter (>= 5.0)) $
      >          liftM (map (+5)) $
      >          samples replicateM n
      >     g x = exp $ (5^2 / 2) - 5 * x
      >     n = 100000

      And now we get quite a good estimate.

      ghci> biggerThan5'

      Random Paths

      The probability of another rare event we might wish to estimate is that of Brownian Motion crossing a boundary. For example, what is the probability of Browian Motion crossing the line y = 3.5? Let’s try sampling 100 paths (we restrict the number so the chart is still readable).

      > epsilons :: (Foldable f, MonadRandom m) =>
      >                     (Int -> RVar Double -> RVar (f Double)) ->
      >                     Double ->
      >                     Int ->
      >                     m (f Double)
      > epsilons repM deltaT n = sample $ repM n $ rvar (Normal 0.0 (sqrt deltaT))
      > bM0to1 :: Foldable f =>
      >           ((Double -> Double -> Double) -> Double -> f Double -> f Double)
      >           -> (Int -> RVar Double -> RVar (f Double))
      >           -> Int
      >           -> Int
      >           -> f Double
      > bM0to1 scan repM seed n =
      >   scan (+) 0.0 $
      >   evalState (epsilons repM (recip $ fromIntegral n) n) (pureMT (fromIntegral seed))

      We can see by eye in the chart below that again we do quite poorly.

      We know that \mathbb{P}(T_a \leq t) = 2(1 - \Phi (a / \sqrt{t})) where T_a = \inf \{t : W_t = a\}.

      > p :: Double -> Double -> Double
      > p a t = 2 * (1 - normcdf (a / sqrt t))
      ghci> p 1.0 1.0
      ghci> p 2.0 1.0
      ghci> p 3.0 1.0

      But what if we didn’t know this formula? Define

      \displaystyle   N(\omega) \triangleq  \begin{cases}  1 & \text{if } \sup_{0 \leq t \leq 1}\tilde W_t \geq a \\  0 & \text{if } \sup_{0 \leq t \leq 1}\tilde W_t < a \\  \end{cases}

      where \mathbb{Q} is the measure which makes \tilde W_t Brownian Motion.

      We can estimate the expectation of N

      \displaystyle   \hat p_{\mathbb{Q}} = \frac{1}{M}\sum_{i=1}^H n_i

      where n_i is 1 if Brownian Motion hits the barrier and 0 otherwise and M is the total number of simulations. We know from visual inspection that this gives poor results but let us try some calculations anyway.

      > n = 500
      > m = 10000
      > supAbove :: Double -> Double
      > supAbove a = fromIntegral count / fromIntegral n
      >   where
      >     count = length $
      >             filter (>= a) $
      >             map (\seed -> maximum $ bM0to1 scanl replicateM seed m) [0..n - 1]
      > bM0to1WithDrift seed mu n =
      >   zipWith (\m x -> x + mu * m * deltaT) [0..] $
      >   bM0to1 scanl replicateM seed n
      >     where
      >       deltaT = recip $ fromIntegral n
      ghci> supAbove 1.0
      ghci> supAbove 2.0
      ghci> supAbove 3.0

      As expected for a rare event we get an estimate of 0.

      Fortunately we can use importance sampling for paths. If we take \mu(\omega, t) = a where a is a constant in Girsanov’s Theorem below then we know that \tilde W_t = W_t + \int_0^t a \,\mathrm{d}s = W_t + at is \mathbb{Q}-Brownian Motion.

      We observe that

      \displaystyle   \begin{aligned}  \mathbb{Q}N &= \mathbb{P}\bigg(N\frac{\mathrm{d} \mathbb{Q}}{\mathrm{d} \mathbb{P}}\bigg) \\  &=  \mathbb{P}\Bigg[N  \exp \Bigg(-\int_0^1  \mu(\omega,t) \,\mathrm{d}W_t - \frac{1}{2} \int_0^1 \mu^2(\omega, t) \,\mathrm{d} t\Bigg)  \Bigg] \\  &=  \mathbb{P}\Bigg[N  \exp \Bigg(-aW_1 - \frac{1}{2} a^2\Bigg)  \Bigg]  \end{aligned}

      So we can also estimate the expectation of N under \mathbb{P} as

      \displaystyle   \hat p_{\mathbb{P}} = \frac{1}{M}\sum_{i=1}^H n_i\exp{\bigg(-aw^{(1)}_i - \frac{a^2}{2}\bigg)}

      where n_i is now 1 if Brownian Motion with the specified drift hits the barrier and 0 otherwise, and w^{(1)}_i is Brownian Motion sampled at t=1.

      We can see from the chart below that this is going to be better at hitting the required barrier.

      Let’s do some calculations.

      > supAbove' a = (sum $ zipWith (*) ns ws) / fromIntegral n
      >   where
      >     deltaT = recip $ fromIntegral m
      >     uss = map (\seed -> bM0to1 scanl replicateM seed m) [0..n - 1]
      >     ys = map last uss
      >     ws = map (\x -> exp (-a * x - 0.5 * a^2)) ys
      >     vss = map (zipWith (\m x -> x + a * m * deltaT) [0..]) uss
      >     sups = map maximum vss
      >     ns = map fromIntegral $ map fromEnum $ map (>=a) sups
      ghci> supAbove' 1.0
      ghci> supAbove' 2.0
      ghci> supAbove' 3.0

      The reader is invited to try the above estimates with 1,000 samples per path to see that even with this respectable number, the calculation goes awry.

      In General

      If we have a probability space (\Omega, {\mathcal{F}}, \mathbb{P}) and a non-negative random variable Z with \mathbb{E}Z = 1 then we can define a new probability measure \mathbb{Q} on the same \sigma-algebra by

      \displaystyle   \mathbb{Q} A \triangleq \int_A Z \,\mathrm{d} \mathbb{P}

      For any two probability measures when such a Z exists, it is called the Radon-Nikodym derivative of \mathbb{Q} with respect to \mathbb{P} and denoted \frac{\mathrm{d} \mathbb{Q}}{\mathrm{d} \mathbb{P}}

      Given that we managed to shift a Normal Distribution with non-zero mean in one measure to a Normal Distribution with another mean in another measure by producing the Radon-Nikodym derivative, might it be possible to shift, Brownian Motion with a drift under a one probability measure to be pure Brownian Motion under another probability measure by producing the Radon-Nikodym derivative? The answer is yes as Girsanov’s theorem below shows.

      Girsanov’s Theorem

      Let W_t be Brownian Motion on a probability space (\Omega, {\mathcal{F}}, \mathbb{P}) and let \{{\mathcal{F}}_t\}_{t \in [0,T]} be a filtration for this Brownian Motion and let \mu(\omega, t) be an adapted process such that the Novikov Sufficiency Condition holds

      \displaystyle   \mathbb{E}\bigg[\exp{\bigg(\frac{1}{2}\int_0^T \mu^2(s, \omega) \,\mathrm{d}s\bigg)}\bigg] = K < \infty

      then there exists a probability measure \mathbb{Q} such that

      • \mathbb{Q} is equivalent to \mathbb{P}, that is, \mathbb{Q}(A) = 0 \iff \mathbb{P}(A) = 0.

      • \displaystyle {\frac{\mathrm{d}\mathbb{Q}}{\mathrm{d}\mathbb{P}} = \exp \Bigg(-\int_0^T \mu(\omega,t) \,\mathrm{d}W_t - \frac{1}{2} \int_0^T \mu^2(\omega, t) \,\mathrm{d} t\Bigg)}.

      • \tilde W_t = W_t + \int_0^t \mu(\omega, t) \,\mathrm{d}s is Brownian Motion on the probabiity space (\Omega, {\mathcal{F}}, \mathbb{Q}) also with the filtration \{\mathcal{F}_t\}_{t \in [0,T]}.

      In order to prove Girsanov’s Theorem, we need a condition which allows to infer that M_t(\mu) is a strict martingale. One such useful condition to which we have already alluded is the Novikov Sufficiency Condition.


      Define \mathbb{Q} by

      \displaystyle   \mathbb{Q}(A) = \mathbb{P}(1_A M_T) \quad \mathrm{where} \quad  M_t(\mu) = \exp{\bigg(\int_0^t - \mu(t, \omega) \,\mathrm{d}W_s  -                        \frac{1}{2}\int_0^t \mu^2(t, \omega) \,\mathrm{d}s\bigg)}

      Then, temporarily overloading the notation and writing \mathbb{P} for expectation under \mathbb{P}, and applying the Novikov Sufficiency Condition to f(s) - \mu(\omega ,s), we have

      \displaystyle   \begin{aligned}  \mathbb{Q}\bigg[\exp{\int_0^T f(s) \,\mathrm{d}X_s}\bigg] &=  \mathbb{Q}\bigg[\exp{\int_0^T f(s) \,\mathrm{d}W_s + \int_0^T \mu(\omega, s) \,\mathrm{d}s}\bigg] \\  &=  \mathbb{P}\bigg[\exp{\bigg(  \int_0^T \big(f(s) - \mu(\omega, s)\big)\,\mathrm{d}W_s +  \int_0^T f(s)\mu(\omega, s)\,\mathrm{d}s -  \frac{1}{2}\int_0^T \mu^2(\omega ,s) \,\mathrm{d}s  \bigg)}\bigg] \\  &=  \mathbb{P}\bigg[\exp{\bigg(  \int_0^T \big(f(s) - \mu(\omega, s)\big)\,\mathrm{d}W_s -  \frac{1}{2}\int_0^T \big(f(s) - \mu(\omega ,s)\big)^2 \,\mathrm{d}s +  \frac{1}{2}\int_0^T f^2(s) \,\mathrm{d}s  \bigg)}\bigg] \\  &=  \frac{1}{2}\int_0^T f^2(s) \,\mathrm{d}s  \,  \mathbb{P}\bigg[\exp{\bigg(  \int_0^T \big(f(s) - \mu(\omega, s)\big)\,\mathrm{d}W_s -  \frac{1}{2}\int_0^T \big(f(s) - \mu(\omega ,s)\big)^2 \,\mathrm{d}s  \bigg)}\bigg] \\  &=  \frac{1}{2}\int_0^T f^2(s) \,\mathrm{d}s  \end{aligned}

      From whence we see that

      \displaystyle   \mathbb{Q}\big(e^{i \zeta (X_t - X_s)}\big) = e^{-\frac{1}{2} \zeta^2 (t - s)}

      And since this characterizes Brownian Motion, we are done.


      The Novikov Sufficiency Condition

      The Novikov Sufficiency Condition Statement

      Let \mu \in {\cal{L}}^2_{\mathrm{LOC}}[0,T] and further let it satisfy the Novikov condition

      \displaystyle   \mathbb{E}\bigg[\exp{\bigg(\frac{1}{2}\int_0^T \mu^2(s, \omega) \,\mathrm{d}s\bigg)}\bigg] = K < \infty

      then the process defined by

      \displaystyle   M_t(\mu) = \exp{\bigg(\int_0^t \mu(t, \omega) \,\mathrm{d}W_s  -                        \frac{1}{2}\int_0^t \mu^2(t, \omega) \,\mathrm{d}s\bigg)}

      is a strict martingale.

      Before we prove this, we need two lemmas.

      Lemma 1

      Let M_t for t \in [0,t] be a non-negative local martingale then M_t is a super-martingale and if further \mathbb{E}M_T = \mathbb{E}M_0 then M_t is a strict martingale.


      Let \{\tau_n\}_{n \in \mathbb{N}} be a localizing sequence for M_t then for 0 < s < t < T and using Fatou’s lemma and the fact that the stopped process is a strict martingale

      \displaystyle   \mathbb{E}(M_t \,|\, {\mathcal{F}_s}) =  \mathbb{E}(\liminf_{n \rightarrow \infty} M_{t \land \tau_m} \,|\, {\mathcal{F}_s}) \leq  \liminf_{n \rightarrow \infty} \mathbb{E}(M_{t \land \tau_m} \,|\, {\mathcal{F}_s}) =  \liminf_{n \rightarrow \infty} M_{s \land \tau_m} = M_s

      Thus M_t is a super-martingale and therefore

      \displaystyle   \mathbb{E}M_T \leq \mathbb{E}M_t \leq \mathbb{E}M_s \leq \mathbb{E}M_0

      By assumption we have \mathbb{E}M_T \leq \mathbb{E}M_0 thus M_t is a strict martingale.


      Lemma 2

      Let M_t be a non-negative local martingale. If \{\tau_n\}_{n \in \mathbb{N}} is a localizing sequence such that \sup_n \|M_{T \land \tau_n}\|_p < \infty for some p > 1 then M_t is a strict martingale.


      \displaystyle   \mathbb{E}(|M_T - M_{T \land \tau_n}|) \leq  \mathbb{E}(|M_T - r \land M_T) +  \mathbb{E}(|r \land M_T - r \land M_{T \land \tau_n}|) +  \mathbb{E}(M_{T \land \tau_n} - r \land M_{T \land \tau_n})

      By the super-martingale property \mathbb{E}(M_T) \leq \mathbb{E}(M_0) < \infty and thus by dominated convergence we have that

      \displaystyle   \lim_{r \rightarrow \infty} \mathbb{E}(r \land M_T) = \mathbb{E}(M_T) \quad \mathrm{and} \quad  \lim_{r \rightarrow \infty}\lim_{n \rightarrow \infty}\mathbb{E}(|r \land M_T - r \land M_{T \land \tau_n}|) = 0

      We also have that

      \displaystyle   \begin{aligned}  \mathbb{E}(M_{T \land \tau_n} - r \land M_{T \land \tau_n}) &=  \mathbb{E}((M_{T \land \tau_n} - r \land M_{T \land \tau_n}){I}_{(M_{T \land \tau_n} > r)}) +  \mathbb{E}((M_{T \land \tau_n} - r \land M_{T \land \tau_n}){I}_{(M_{T \land \tau_n} \leq r)}) \\  &= \mathbb{E}((M_{T \land \tau_n} - r \land M_{T \land \tau_n}){I}_{(M_{T \land \tau_n} > r)}) \\  &= \mathbb{E}(M_{T \land \tau_n}{I}_{(M_{T \land \tau_n} > r)}) - r\mathbb{P}({M_{T \land \tau_n} > r})  \end{aligned}

      By Chebyshev’s inequality (see note (2) below), we have

      \displaystyle   r\mathbb{P}({M_{T \land \tau_n} > r}) \leq \frac{r\mathbb{E}|X|^p}{r^p} \leq  \frac{\sup_n{\mathbb{E}(M_{T \land \tau_n})^p}}{r^{p-1}}

      Taking limits first over n \rightarrow \infty and then over r \rightarrow \infty we see that

      \displaystyle   \lim_{r \rightarrow \infty}\lim_{n \rightarrow \infty} r\mathbb{P}({M_{T \land \tau_n} > r}) \rightarrow 0

      For 0 \leq r \leq x and p > 1 we have x \leq r^{1-p}x^p. Thus

      \displaystyle   \mathbb{E}(M_{T \land \tau_n}{I}_{(M_{T \land \tau_n} > r)}) \leq  r^{1-p}\mathbb{E}(M_{T \land \tau_n}^p{I}_{(M_{T \land \tau_n} > r)}) \leq  r^{1-p}\sup_n(M_{T \land \tau_n}^p)

      Again taking limits over n \rightarrow \infty and then over r \rightarrow \infty we have

      \displaystyle   \lim_{r \rightarrow \infty}\lim_{n \rightarrow \infty} \mathbb{E}(M_{T \land \tau_n}{I}_{(M_{T \land \tau_n} > r)}) \rightarrow 0

      These two conclusions imply

      \displaystyle   \lim_{r \rightarrow \infty}\lim_{n \rightarrow \infty} \mathbb{E}(M_{T \land \tau_n} - r \land M_{T \land \tau_n}) \rightarrow 0

      We can therefore conclude (since M_{T \land \tau_n} is a martingale)

      \displaystyle   \mathbb{E}(M_T) = \lim_{n \rightarrow \infty}\mathbb{E}(M_{T \land \tau_n}) =  \mathbb{E}(M_0)

      Thus by the preceeding lemma M_t is a strict as well as a local martingale.


      The Novikov Sufficiency Condition Proof

      Step 1

      First we note that M_t(\lambda\mu) is a local martingale for 0 < \lambda < 1. Let us show that it is a strict martingale. We can do this if for any localizing sequence \{\tau_n\}_{n \in \mathbb{N}} we can show

      \displaystyle   \sup_n\mathbb{E}(M_{T \land \tau_n}(\lambda\mu))^p < \infty

      using the preceeding lemma where p > 1.

      We note that

      \displaystyle   \begin{aligned}  M_t(\lambda\mu) &=  \exp{\bigg(\int^t_0 \lambda\mu(\omega, s)\,\mathrm{d}W_s -  \frac{1}{2}\int^t_0 \lambda^2\mu^2(\omega, s)\,\mathrm{d}s\bigg)} \\  &= {(M_t(\mu))}^{\lambda^2}\exp{\bigg((\lambda - \lambda^2)\int^t_0 \mu(\omega, s)\,\mathrm{d}W_s\bigg)}  \end{aligned}

      Now apply Hölder’s inequality with conjugates ({p\lambda^2})^{-1} and ({1 - p\lambda^2})^{-1} where p is chosen to ensure that the conjugates are both strictly greater than 1 (otherwise we cannot apply the inequality).

      \displaystyle   \begin{aligned}  \mathbb{E}((M_t(\lambda\mu))^p)  &=  \mathbb{E}\bigg[{(M_t(\mu))}^{p\lambda^2}\exp{\bigg(p(\lambda - \lambda^2)\int^t_0 \mu(\omega, s)\,\mathrm{d}W_s\bigg)}\bigg] \\  &\le  \bigg|\bigg|{M_t(\mu)}^{p\lambda^2}\bigg|\bigg|_{p\lambda^2}  \bigg|\bigg|\exp{\bigg(p(\lambda - \lambda^2)\int^t_0 \mu(\omega, s)\,\mathrm{d}W_s\bigg)}\bigg|\bigg|_{1 - p\lambda^2} \\  &=  \mathbb{E}{\bigg[M_t(\mu)}\bigg]^{p\lambda^2}  \mathbb{E}\bigg[\exp{\bigg(p\frac{\lambda - \lambda^2}{1 - p\lambda^2}\int^t_0 \mu(\omega, s)\,\mathrm{d}W_s\bigg)}\bigg]^{1 - p\lambda^2}  \end{aligned}

      Now let us choose

      \displaystyle   p\frac{\lambda - \lambda^2}{1 - p\lambda^2} = \frac{1}{2}


      \displaystyle   \begin{aligned}  2p(\lambda - \lambda^2) &= 1 - p\lambda^2 \\  p & = \frac{1}{2(\lambda - \lambda^2) + \lambda^2} \\  p &= \frac{1}{(2 - \lambda)\lambda}  \end{aligned}

      In order to apply Hölder’s inequality we need to check that (p\lambda^2)^{-1} > 1 and that (1 - p\lambda^2)^{-1} > 1 but this amounts to checking that p\lambda^2 > 0 and that 1 > \lambda. We also need to check that p > 0 but this amounts to checking that (2 - \lambda)\lambda < 1 for 0 < \lambda < 1 and this is easily checked to be true.

      Re-writing the above inequality with this value of p we have

      \displaystyle   \begin{aligned}  \mathbb{E}((M_t(\lambda\mu))^p)  &\le  \mathbb{E}{\bigg[M_t(\mu)}\bigg]^{p\lambda^2}  \mathbb{E}\bigg[\exp{\bigg(\frac{1}{2}\int^t_0 \mu(\omega, s)\,\mathrm{d}W_s\bigg)}\bigg]^{1 - p\lambda^2}  \end{aligned}

      By the first lemma, since M_t(\mu) is a non-negative local martingale, it is also a supermartingale. Furthermore \mathbb{E}(M_0(\mu)) = 1. Thus

      \displaystyle   \mathbb{E}{\bigg[M_t(\mu)}\bigg]^{p\lambda^2} \leq 1

      and therefore

      \displaystyle   \begin{aligned}  \mathbb{E}((M_t(\lambda\mu))^p)  &\le  \mathbb{E}\bigg[\exp{\bigg(\frac{1}{2}\int^t_0 \mu(\omega, s)\,\mathrm{d}W_s\bigg)}\bigg]^{1 - p\lambda^2}  \end{aligned}

      Step 2

      Recall we have

      \displaystyle   {M_t} =  \exp\bigg(  \int_0^t \mu(\omega ,s)\,\mathrm{d}W_s - \frac{1}{2}\int_0^t \mu(\omega ,s)\,\mathrm{d}s  \bigg)

      Taking logs gives

      \displaystyle   \log{M_t} =  \int_0^t \mu(\omega ,s)\,\mathrm{d}W_s - \frac{1}{2}\int_0^t \mu(\omega ,s)^2\,\mathrm{d}s

      or in diferential form

      \displaystyle   \mathrm{d}(\log{M_t}) =  \mu(\omega ,t)\,\mathrm{d}W_t - \frac{1}{2}\mu(\omega ,t)^2\,\mathrm{d}t

      We can also apply Itô’s rule to \log{M_t}

      \displaystyle   \begin{aligned}  \mathrm{d}(\log{M_t})  &= \frac{1}{M_t}\,\mathrm{d}M_t   - \frac{1}{2}\frac{1}{M_t^2}\,\mathrm{d}[M]_t \\  \end{aligned}

      where [\ldots] denotes the quadratic variation of a stochastic process.

      Comparing terms gives the stochastic differential equation

      \displaystyle   \mathrm{d}M_t = M_t\mu(\omega,t)\,\mathrm{d}W_t

      In integral form this can also be written as

      \displaystyle   M_t = 1 + \int_0^t M_s\mu(\omega, s)\,\mathrm{d}W_s

      Thus M_t is a local martingale (it is defined by a stochastic differential equation) and by the first lemma it is a supermaringale. Hence \mathbb{E}M_t \leq 1.

      Next we note that

      \displaystyle   \exp{\bigg(\frac{1}{2}\int_0^t \mu(\omega, t)\bigg)} =  \exp{\bigg(\frac{1}{2}\int_0^t \mu(\omega, t) -       \frac{1}{4}\int_0^t \mu^2(\omega, t) \,\mathrm{d}s\bigg)}  \exp{\bigg(\frac{1}{4}\int_0^t \mu^2(\omega, t) \,\mathrm{d}s\bigg)}

      to which we can apply Hölder’s inequality with conjugates p = q = 2 to obtain

      \displaystyle   \begin{aligned}  \mathbb{E}\bigg[\exp{\bigg(\frac{1}{2}\int_0^t \mu(\omega, t)\bigg)}\bigg] &=  \mathbb{E}\bigg[\exp{\bigg(\frac{1}{2}\int_0^t \mu(\omega, t) -                             \frac{1}{4}\int_0^t \mu^2(\omega, t) \,\mathrm{d}s                       \bigg)}                  \exp{\bigg(\frac{1}{4}\int_0^t \mu^2(\omega, t) \,\mathrm{d}s                       \bigg)}\bigg] \\  & \leq  \sqrt{\mathbb{E}\bigg[\exp{\bigg(\int_0^t \mu(\omega, t) -                             \frac{1}{2}\int_0^t \mu^2(\omega, t) \,\mathrm{d}s                       \bigg)}\bigg]}  \sqrt{\mathbb{E}\exp{\bigg(\frac{1}{2}\int_0^t \mu^2(\omega, t) \,\mathrm{d}s                       \bigg)}\bigg]}  \end{aligned}

      Applying the supermartingale inequality then gives

      \displaystyle   \begin{aligned}  \mathbb{E}\bigg[\exp{\bigg(\frac{1}{2}\int_0^t \mu(\omega, t)\bigg)}\bigg]  & \leq  \sqrt{\mathbb{E}\exp{\bigg(\frac{1}{2}\int_0^t \mu^2(\omega, t) \,\mathrm{d}s                       \bigg)}\bigg]}  \end{aligned}

      Step 3

      Now we can apply the result in Step 2 to the result in Step 1.

      \displaystyle   \begin{aligned}  \mathbb{E}((M_t(\lambda\mu))^p)  &\le  \mathbb{E}\bigg[\exp{\bigg(\frac{1}{2}\int^t_0 \mu(\omega, s)\,\mathrm{d}W_s\bigg)}\bigg]^{1 - p\lambda^2} \\  &\le  {\mathbb{E}\bigg[\exp{\bigg(\frac{1}{2}\int_0^t \mu^2(\omega, t) \,\mathrm{d}s                        \bigg)}\bigg]}^{(1 - p\lambda^2)/2} \\  &\le  K^{(1 - p\lambda^2)/2}  \end{aligned}

      We can replace M_t by M_t {\mathcal{I}}_{t < \tau} for any stopping time \tau. Thus for a localizing sequence we have

      \displaystyle   \begin{aligned}  \mathbb{E}((M_{t \land \tau_n}(\lambda\mu))^p)  &\le  K^{(1 - p\lambda^2)/2}  \end{aligned}

      From which we can conclude

      \displaystyle   \sup_n \|M_{T \land \tau_n}(\lambda\mu)\|_p < \infty

      Now we can apply the second lemma to conclude that M_{T \land \tau_n}(\lambda\mu) is a strict martingale.

      Final Step

      We have already calculated that

      \displaystyle   \begin{aligned}  M_t(\lambda\mu) &=  \exp{\bigg(\int^t_0 \lambda\mu(\omega, s)\,\mathrm{d}W_s -  \frac{1}{2}\int^t_0 \lambda^2\mu^2(\omega, s)\,\mathrm{d}s\bigg)} \\  &= {(M_t(\mu))}^{\lambda^2}\exp{\bigg((\lambda - \lambda^2)\int^t_0 \mu(\omega, s)\,\mathrm{d}W_s\bigg)}  \end{aligned}

      Now apply Hölder’s inequality with conjugates p = \lambda^{-2} and q = (1 - \lambda^2)^{-1}.

      \displaystyle   1 = \mathbb{E}(M_t(\lambda\mu) \le  \mathbb{E}(M_t(\mu))^{\lambda^2}\mathbb{E}{\bigg(}\exp{\bigg(\frac{\lambda}{1 + \lambda}\int^t_0 \mu(\omega, s)\,\mathrm{d}W_s\bigg)}\bigg)^{1 - \lambda^2}

      And then we can apply Jensen’s inequality to the last term on the right hand side with the convex function x^{(1 + \lambda)/2\lambda}.

      \displaystyle   1 \le  \mathbb{E}(M_t(\mu))^{\lambda^2}  \mathbb{E}{\bigg(}\exp{\bigg(\frac{1}{2}\int^t_0 \mu(\omega, s)\,\mathrm{d}W_s\bigg)}\bigg)^{2\lambda(1- \lambda)}

      Using the inequality we established in Step 2 and the Novikov condition then gives

      \displaystyle   1 \le  \mathbb{E}(M_t(\mu))^{\lambda^2}  K^{\lambda(1 - \lambda)}

      If we now let \lambda \nearrow 1 we see that we must have 1 \le \mathbb{E}(M_t(\mu)). We already now that 1 \ge \mathbb{E}(M_t(\mu)) by the first lemma and so we have finally proved that M_t(\mu) is a martingale.


      1. We have already used importance sampling and also touched on changes of measure.

      2. Chebyshev’s inequality is usually stated for the second moment but the proof is easily adapted:

      \displaystyle   \mathbb P( |X| > u ) = \int 1_{|X| > u} ~d\mathbb P = \frac 1 {u^p} \int u^p 1_{|X| > u} ~d\mathbb P < \frac 1 {u^p} \int |X|^p 1_{|X| > u} ~ d\mathbb P \le \frac 1 {u^p} \mathbb E|X|^p.

      1. We follow Handel (2007); a similar approach is given in Steele (2001).


      Handel, Ramon von. 2007. “Stochastic Calculus, Filtering, and Stochastic Control (Lecture Notes).”

      Steele, J.M. 2001. Stochastic Calculus and Financial Applications. Applications of Mathematics. Springer New York.

      by Dominic Steinitz at October 31, 2015 05:23 PM

      Joey Hess

      a tiling region manager for the console

      Building on top of concurrent-output, and some related work Joachim Breitner did earlier, I now have a kind of equivilant to a tiling window manager, except it's managing regions of the console for different parts of a single program.

      Here's a really silly demo, in an animated gif:


      Not bad for 23 lines of code, is that? Seems much less tedious to do things this way than using ncurses. Even with its panels, ncurses requires you to think about layout of various things on the screen, and many low-level details. This, by contrast, is compositional, just add another region and a thread to update it, and away it goes.

      So, here's an apt-like download progress display, in 30 lines of code.


      Not only does it have regions which are individual lines of the screen, but those can have sub-regions within them as seen here (and so on).

      And, log-type messages automatically scroll up above the regions. External programs run by createProcessConcurrent will automatically get their output/errors displayed there, too.

      What I'm working on now is support for multiline regions, which automatically grow/shrink to fit what's placed in them. The hard part, which I'm putting the finishing touches on, is to accurately work out how large a region is before displaying it, in order to lay it out. Requires parsing ANSI codes amoung other things.

      STM rules

      There's so much concurrency, with complicated interrelated data being updated by different threads, that I couldn't have possibly built this without Software Transactional Memory.

      Rather than a nightmare of locks behind locks behind locks, the result is so well behaved that I'm confident that anyone who needs more control over the region layout, or wants to do funky things can dive into to the STM interface and update the data structures, and nothing will ever deadlock or be inconsistent, and as soon as an update completes, it'll display on-screen.

      An example of how powerful and beuatiful STM is, here's how the main display thread determines when it needs to refresh the display:

      data DisplayChange
              = BufferChange [(StdHandle, OutputBuffer)]
              | RegionChange RegionSnapshot
              | TerminalResize (Maybe Width)
              | EndSignal ()
                      change <- atomically $
                              (RegionChange <$> regionWaiter origsnapshot)
                              (RegionChange <$> regionListWaiter origsnapshot)
                              (BufferChange <$> outputBufferWaiterSTM waitCompleteLines)
                              (TerminalResize <$> waitwidthchange)
                              (EndSignal <$> waitTSem endsignal)
                      case change of
                              RegionChange snapshot -> do
                              BufferChange buffers -> do
                              TerminalResize width -> do

      So, it composes all these STM actions that can wait on various kinds of changes, to get one big action, that waits for all of the above, and builds up a nice sum type to represent what's changed.

      Another example is that the whole support for sub-regions only involved adding 30 lines of code, all of it using STM, and it worked 100% the first time.

      Available in concurrent-output 1.1.0.

      October 31, 2015 01:44 AM

      Douglas M. Auclair (geophf)

      October 2015 1HaskellADay Problems and Solutions

      October 2015

      • October 29th, 2015: This is a perfect introduction to today's #haskell problem: dynamic predictions because cats. And today's #haskell problem has the added benefit of containing the longest epic mid-type-declaration-comment of epic epicness. Epically. ... but what you didn't see for today's #haskell problem is the preparation #fallingasleepoverthekeyboard #again And the 'S' in the anSwer is not for 'S'tatistician, but for geophf waiting for a 'S'uper heroine to give the anSwer
      • October 28th, 2015: Today's #haskell problem, we DEFINE WHAT 'AVERAGE' IS! Nope. But we do take on predictive analytics! So there's that. And here's the predictions-distributions. One day we'll even do ROC-analysis. Or not.
      • October 27th, 2015: For today's #haskell problem we say "HEY! YOU! GET YOU SOME RANDOM, YO!" and then define a random number generator A (random) solution (not really) to yesterday's random (really) #haskell problem
      • October 26th, 2015: Well, bleh! It only took all day to compose, but here's today's #haskell problem! "Learning Haskell!" Okay, that (randomly) hurt! -- one possible solution to this problem is posted at
      • October 23rd, 2015: Today's #haskell problem is thanks to Jim Webber's keynote at @GraphConnect is about triadic closure
      • October 22nd, 2015: Today's #haskell problem is thanks to Jim Webber's keynoteat the @neo4j @GraphConnect: WWI Alliances  WWI-Alliances … and as a @neo4j-graph 
      • October 16th, 2015: Today's #haskell problem asks you to create MAJYCK! with LENSES over MATRICES using SCIENCE! (lens = magic ICYMI)
      • October 15th, 2015: Today's #haskell problem is a real (silly) problem: 'efficientize' row and col definitions for Data.Matrix Zippidy Doo-Dah! Zippidy day! My, oh, my we've 'efficientized' Matrix RowCol (that scans. Kinda)
      • October 14th, 2015: For today's #haskell problem we look at multiplying matrices, because SCIENCE! Today criss-cross is gonna JUMP-JUMP! ... and sauce the apples (What this has to do with matrix-multiplication, I do not know)
      • October 13th, 2015: A rose by any other name would smell as sweet. A matrix-transpose by any other name is still today's #haskell problem Today we transpose matrices ... LIKE A GANGSTA!
      • October 12th, 2015: We go from eh-matrices to ÜBERMATRICES for today's #haskell problem And we übered those matrices at
      • October 8th, 2015: We haven't touched Data.Matrix in a while, and it didn't age well. Let's fix this for today's #haskell problem Matrices, REBORN! (or at least, prenatal, but we'll get there)
      • October 7th, 2015: So, after all that work making DList Foldable/Traversable/Monadible (eh?) TODAY's #haskell problem relaxes MultiMap That MultiMap is now hella-relaxed, yo!
      • October 6th, 2015: So YESTERDAY we looked at Foldable. @argumatronic said "Step it up: do Traversable!" So for TODAY'S #haskell problem So we WuTang Traversible CLANNEDthat solution!
      • October 5th, 2015: For today's #haskell problem we go from Monadical to Foldable, thanks to @argumatronic Wait. Is 'monadical' a word? DList. Foldable instance. Done.
      • October 2nd, 2015: For today's #haskell problem we make multimaps fast with difference lists ... OR. DO. WE! And today we find out HOW FAST MULTIMAPS ARE WITH DLISTS! (in all caps, no less)
      • October 1st, 2015: Yesterday we made Difference Lists Applicative, for today's #haskell problem we make them monadic So, difference lists are monadic now ... so there's that ...

      by geophf ( at October 31, 2015 12:53 AM

      October 30, 2015

      Yesod Web Framework

      Beginner friendly code and APIs

      I just flew from Tel Aviv to Los Angeles. It's a long flight, and includes significant travel time outside of the flight itself. There are two results of that: (1) I've slept something like 8 hours in the past 72, and (2) I've had a lot of time to play with random code sitting on my laptop and think about it from different perspectives. I'm going to talk about (2), and use (1) as an excuse for anything ridiculous I say. Note that this blog post is just exploring ideas, not giving any real statements.

      The following two pieces of code are identical in functionality:

      someFunc1 key =
          case lookup key someMap of
              Nothing -> getDefaultValue
              Just value -> otherFunc value
      someFunc2 = maybe getDefaultValue otherFunc . flip lookup someMap

      Which is better? I'll start with objective facts from my own experience:

      1. When I was a beginner Haskeller, I would have been able to write something like someFunc1
      2. When I was a beginner Haskeller, I would have had to try and puzzle out someFunc2` for a long time if I read it, and almost certainly couldn't have written it
      3. Past the beginner phase, reading code like someFunc2 taught me new ways to compose Haskell code easily
      4. As an intermediate Haskeller, I definitely got the feeling that I should be writing my code in someFunc2 style (point-free, avoid pattern matching, use function composition)
      5. I seem to receive pull requests on a regular (though not frequent) basis rewriting code in the style of someFunc1 to look like someFunc2
      6. I have a gut reaction that someFunc2 is better
      7. someFunc2 is shorter
      8. And yet, to this date, I think I can still parse and understand someFunc1 more easily, and also believe I will more quickly spot a bug in that style

      There's quite a few "I got the feeling" statements above. Those are objective statements about my subjective observations; I'd be really intersted in whether other people have had the same kinds of observations over time, or if my experience is unique. But now, the truly subjective/exploratory part:

      It seems like my progression as a Haskeller results in forcing myself to write in a harder-to-parse style to make my code shorter, to satisfy some base need for "better" code, even though by most measurements I just made, the longer/explicit/pattern matching code is in fact better.

      There are certainly advantages to point-free style though, right? Some more complicated combinators - like foldr - result in clearer code, plus code that generalizes to more data types than just a list (thanks to Foldable). In some cases (like stream fusion and other rewrite rules) point-free style may be more efficient; I know that in conduit await >>= maybe f g is more efficient than pattern matching.

      To try and generalize my point beyond point-free style: we've been having some discussions about more code sharing in the web framework space recently. One point that's come up is a difference between Servant and Yesod regarding explicitness of parameters. For example, in Yesod (and I think other WAI frameworks), there's a function available inside your handler code to lookup request headers. In Servant, a dependency on such a piece of data is explicit at the type level. (There are similar issues around short-circuiting requests, and explicitness of different content representations.)

      My 5-year-more-Haskell-experienced self is very much intrigued by the Servant approach. It seems more sound. And yet, I still interact regularly with less experienced Haskellers. And just this past week, this kind of need for explicit declaration of all data came up in practice for a customer, and resulted in Haskell being a harder adoption for them.

      I'm feeling the same tension again. The Yesod API seems to appeal to what the beginner would expect at a straightforward level: if you want to send a redirect, you just call the redirect function, and don't need to worry about changing type signatures around. Need a request header? Ask for it. However, I know that being explicit about these things gives great benefit (in Servant's case, it has the ability to generate API bindings that Yesod doesn't have). But even so, today when I write a web app in Haskell, I still like the ability to use the "beginner-friendly" API without the explicitness.

      This is where I'm stuck. There are clearly benefits to each kind of approach in these dichotomies. And I'm sure there are more dichotomies than I've listed. The kind of questions I've been pondering are:

      1. If I would design an API differently today than in the past, based on my larger Haskell experience, what does that mean? Is the new API better? Or have I lost touch with what's most useful, and am instead chasing an less important ideal?
      2. Is there an inherent tension between beginner-friendly and expert-friendly APIs for some of these things, and are the two groups best served by separating out the APIs?
      3. When do I give in to the voice that says "you could rewrite that to be cleaner" and when do I say "no, the simple code is better, don't complicate it in the name of cleanliness."

      Sorry for the mostly unintelligible rambling. In the interest of sometimes listening to the less experienced person inside of me, I'm posting this without much review, in case I'm actually hitting on an important topic. If not, please ignore me.

      And in case anyone's curious, a lot of this came up when working on wai-frontend-monad, which attempts to extract the HandlerT transformer from Yesod into something more generally useful, and in a more modern coding style. That work (combined with lack of sleep on a plane) seems to have opened up some existential dilemmas ;).

      October 30, 2015 07:30 AM

      wren gayle romano

      Limitations of strongly-typed ABTs

      Last time I talked a bit about ABTs; in particular, I introduced the notion of strongly-typed ABTs (or "GABTs" if you prefer) and showed how we can extend the basic idea of ABTs to guarantee well-typedness in addition to well-aritiedness. However, I also made a note that ensuring this sort of well-typedness runs counter to what Neel and other CMUers often do. One of my colleagues here at IU noticed the reason, so I thought I'd write a bit more about it.

      The issue at stake here is how general we can make our ABT library, to minimize the amount of boilerplate needed whenever inventing a new language. By encoding object-language type systems into the kinding of the ABT, we restrict the the possible object languages we can use the ABT implementation for (namely those object languages with type systems that can be embedded into whatever kinding the ABT has). To put a finer point on it, using the kinds presented in the previous post you cannot have binders in your type system. This means no System F, and no dependent types. This is unfortunate as the whole point of ABTs is to capture binding structure once and for all!

      However, I'd like to reiterate that, for our purposes in Hakaru this limitation is no restriction. Hakaru is simply-typed, so there are no type-level binders in sight. Moreover, we do a lot of program transformations in Hakaru. By using GABTs we can have GHC verify that our program transformations will never produce Hakaru code which is ill-typed, and that our program transformations will always produce Hakaru code of an appropriate type (e.g., the same type as the input term, for things like partial evaluation; but we have a number of type-changing transformations too). Thus, even though our GABT library could not be reused for implementing languages with type-level binders, it still provides a substantial benefit for those languages without type-level binders.

      Although our GABTs cannot handle type-level binders, that does not mean we're restricted to only working with simply typed languages. For example, intersection types are not usually thought of as "simple types"; but they do not require binders and so they're fine. More generally, Larry Moss is engaged in a research project where he asks, "given infinite time, how far could Aristotle have gotten in logic?" By which he means, given the Aristotelian restriction to syllogistic logics (i.e., ones without the quantifiers introduced by Frege), what are the limits in what we can cover? It turns out that we can cover quite a lot. Some syllogistic logics go beyond the power of the "Peano–Frege" boundary: they can handle comparing cardinality of sets! A good pictorial summary of this line of research is on slide 2 of this talk; and a bit more about the complexity results is given in this talk (the requisite picture is on slide 39).

      comment count unavailable comments

      October 30, 2015 05:17 AM

      Jasper Van der Jeugt

      Tries and elegant Scope Checking


      This blogpost is mostly based upon a part of the talk I recently gave at the Haskell eXchange. I discussed scope checking – also referred to as scope analysis or renaming. While the talk focussed on Ludwig, a DSL used to program Fugue, the ideas around scope checking are broadly applicable, so in this blogpost we use a simple toy language.

      > {-# LANGUAGE DeriveFoldable    #-}
      > {-# LANGUAGE DeriveFunctor     #-}
      > {-# LANGUAGE DeriveTraversable #-}
      > import qualified Data.HashMap.Strict    as HMS
      > import           Data.Hashable          (Hashable)
      > import           Data.List              (foldl')
      > import           Data.Either.Validation (Validation (..),
      >                                          validationToEither)
      > import           Prelude                hiding (lookup)

      This part of a Compiler/Interpreter is concerned with resolving occurence names to full names. Occurrence names are just what the programmer uses in the source file, and full names contain more information.

      I think this is an interesting area to explore. The vast majority of articles about creating parsers and interpreters just use Strings as names, in order to keep things simple (which is of course fully justified). This blogpost, on the other hand, explains what you can do if things become a bit more complicated.

      Consider the following Haskell snippet:

      import qualified Data.HashMap.Strict as HMS
      emptyThing = HMS.empty

      HMS.empty is an occurrence name. The full name, on the other hand, is something like unordered-containers- Let’s get started by representing these types in Haskell:

      > -- E.g. ["HMS", "empty"].
      > type OccName = [String]
      > -- E.g. ["Data", "HashMap", "Strict"]
      > type ModuleName = [String]
      > -- Just an example of what sort of things can be in 'FullName'.
      > data BindingScope = ToplevelScope | LocalScope
      >     deriving (Show)
      > data FullName = FullName
      >     { fnOccName      :: !OccName
      >     , fnModuleName   :: !ModuleName
      >     , fnBindingScope :: !BindingScope
      >     } deriving (Show)

      Note that this is just a toy example. Firstly, we can use more efficient representations for the above, and we might want to add newtype safety. Secondly, we might also want to store other things in FullName, for example the package where the name originated. The FullName record can really get quite big.

      Now that we have two name types – OccName and FullName, we can parametrise our abstract syntax tree over a name type.

      > data Expr n
      >     = Literal Int
      >     | Add (Expr n) (Expr n)
      >     | Var n
      >     deriving (Show)

      Now, we can formalise the problem of scope checking a bit more: it is a function which turns an Expr OccName into an Expr FullName.


      In order to implement this, it is clear that we need some sort of “Map” to store the FullName information. The specific data structure we will use is a Trie. Tries are somewhat similar to Radix trees, but significantly more simple. We will implement one here for educational purposes.

      A Trie k v can be seen as a mapping from lists of keys to values, so it could be defined as:

      type Trie k v = HMS.HashMap [k] v

      However, there is a nicer representation which we will need in order to support some fast operations.

      First, we need a quick-and-dirty strict Maybe type.

      > data M a = J !a | N
      >     deriving (Foldable, Functor, Show, Traversable)

      Note how we automically added Foldable, Functor and Traversable instances for this type. Thanks GHC!

      Then, we can define Trie in a recursive way:

      > data Trie k v = Trie
      >     { tValue    :: !(M v)
      >     , tChildren :: !(HMS.HashMap k (Trie k v))
      >     } deriving (Foldable, Functor, Show, Traversable)

      We can have a value at the root (tValue), and then the other elements in the Trie are stored under the first key of their key list (in tChildren).

      Now it is time to construct some machinery to create Tries. The 1 empty Trie is really easy:

      > empty :: Trie k v
      > empty = Trie N HMS.empty

      Let’s draw the empty Trie as a simple box with an N value, since it has no value and no children.

      The empty trie

      The empty trie

      We can also define a function to create a Trie with a single element. If the list of keys is empty, we simply have a J value at the root. Otherwise, we define the function recursively.

      > singleton :: (Eq k, Hashable k) => [k] -> v -> Trie k v
      > singleton []       x = Trie (J x) HMS.empty
      > singleton (k : ks) x = Trie N (HMS.singleton k (singleton ks x))

      As an example, this is the result of the call singleton ["foo", "bar"] "Hello World".

      A singleton trie

      A singleton trie

      We can skip insert and simply create a unionWith function instead. This function unifies two Tries, while allowing you to pass in a function that decides how to merge the two values if there is a key collision.

      > unionWith
      >     :: (Eq k, Hashable k)
      >     => (v -> v -> v) -> Trie k v -> Trie k v -> Trie k v
      > unionWith f (Trie v1 c1) (Trie v2 c2) =
      >     Trie v $ HMS.unionWith (unionWith f) c1 c2
      >   where
      >     v = case (v1, v2) of
      >         (N,   _)   -> v2
      >         (_,   N)   -> v1
      >         (J x, J y) -> J (f x y)

      The bulk of the work is of course done by HMS.unionWith. This is the result of calling unionWith (\x _ -> x) (singleton "foo" "Hello") (singleton "bar" "World"):

      unionWith example

      unionWith example

      For convenience, we can then extend unionWith to work on lists:

      > unionsWith
      >     :: (Eq k, Hashable k)
      >     => (v -> v -> v) -> [Trie k v] -> Trie k v
      > unionsWith f = foldl' (unionWith f) empty

      A last function we need to modify tries is prefix. This function prefixes a whole Trie by nesting it under a list of keys. Because of the way our Trie is represented, this can be done efficiently and we don’t need to change every key.

      > prefix :: (Eq k, Hashable k) => [k] -> Trie k v -> Trie k v
      > prefix []       trie = trie
      > prefix (k : ks) trie = Trie N $ HMS.singleton k (prefix ks trie)

      This is the result of prefixing the trie from the previous example with ["qux"]:

      prefix example

      prefix example

      In addition to creating Tries, we also need to be able to lookup stuff in the Trie. All we need for that is a simple lookup function:

      > lookup :: (Eq k, Hashable k) => [k] -> Trie k v -> Maybe v
      > lookup []       (Trie N     _)        = Nothing
      > lookup []       (Trie (J x) _)        = Just x
      > lookup (k : ks) (Trie _     children) = do
      >     trie <- HMS.lookup k children
      >     lookup ks trie

      These are all the Trie functions we need. A real implementation would, of course, offer more.

      The scope type

      Now, recall that we’re trying to resolve the occurrence names in a module into full names. We will tackle this from the opposite direction: we’ll gather up all the names which are in scope into one place. After this, actually, resolving an occurrence name is as simple as performing a lookup.

      In order to gather up all these names we need some datatype – which is, of course, the Trie we just implemented!

      > type Scope a = Trie String a

      We will differentiate between two different kinds of scopes (hence the a). An AmbiguousScope might contain duplicate names. In that case, we want to throw an error or show a warning to the user. In an UnambiguousScope, on the other hand, we know precisely what every name refers to.

      > type AmbiguousScope = Scope [FullName]
      > type UnambiguousScope = Scope FullName

      Let’s first focus on building AmbiguousScopes. We will later see how we can validate these and convert them into an UnambiguousScope.

      Building a scope for one module

      In order to build a scope, let’s start with a simple case. Let’s look at a sample module in our DSL and construct a scope just for that module.

      module Calories.Fruit where
      apple  = 52
      banana = 89

      We need to have some intuition for how such a module is represented in Haskell. Let’s try to keep things as simple as possible:

      > data Module n = Module
      >     { mName     :: !ModuleName
      >     , mBindings :: [Binding n]
      >     } deriving (Show)
      > data Binding n = Binding
      >     { bName :: !n
      >     , bBody :: !(Expr n)
      >     } deriving (Show)

      We can define a function to convert this module into a local Scope which contains all the bindings in the module. In order to keep things simple, we assume every binding in a module is always exported.

      > scopeFromModule :: Module OccName -> AmbiguousScope
      > scopeFromModule m =
      >     unionsWith (++) $ map scopeFromBinding (mBindings m)
      >   where
      >     scopeFromBinding :: Binding OccName -> AmbiguousScope
      >     scopeFromBinding b = singleton (bName b)
      >         [ FullName
      >             { fnOccName      = bName b
      >             , fnModuleName   = mName m
      >             , fnBindingScope = ToplevelScope
      >             }
      >         ]

      For our example module, we obtain something like:

      The fruit module scope

      The fruit module scope

      Multiple imports

      Of course, a realistic program will import multiple modules. Imagine a program with the following import list:

      import           Calories.Fruit
      import qualified Calories.Pie  as Pie
      -- An apple and an apple pie!
      combo = apple +

      In order to build the Scope for the program, we need three more things:

      1. Joining a bunch of Scopes, one for each import statement (plus the local scope, and maybe a builtin scope…);
      2. Qualifying a Scope, so that the qualified imports end up under the right name;
      3. Finally, converting the AmbiguousScope into an UnambiguousScope.

      The first one is easy, since we have our Trie machinery.

      > unionScopes :: [AmbiguousScope] -> AmbiguousScope
      > unionScopes = unionsWith (++)

      So is the second:

      > qualifyScope :: [String] -> AmbiguousScope -> AmbiguousScope
      > qualifyScope = prefix

      We can now build the scope for our little program. It is:

      > myScope :: AmbiguousScope
      > myScope = unionScopes
      >     [ scopeFromModule myModule  -- Defines 'combo'
      >     , scopeFromModule fruitModule
      >     , qualifyScope ["Pie"] $ scopeFromModule pieModule
      >     ]

      We get something like:



      Great! So now the problem is that we’re left with an AmbiguousScope instead of an UnambiguousScope. Fortunately we can convert between those fairly easily, because Trie (and by extension Scope) is Traversable:

      > toUnambiguousScope
      >     :: AmbiguousScope -> Validation [ScopeError] UnambiguousScope
      > toUnambiguousScope = traverse $ \fullNames -> case fullNames of
      >     [single] -> pure single
      >     []       -> Failure [InternalScopeError "empty list in scope"]
      >     multiple -> Failure [AmbiguousNames multiple]

      It is perhaps worth noting that this behaviour is different from GHC 2.

      By using the Validation Applicative, we ensure that we get as many error messages as we can. We have a nice datatype which describes our possible errors:

      > data ScopeError
      >     = AmbiguousNames [FullName]
      >     | NotInScope OccName
      >     | InternalScopeError String  -- For other failures
      >     deriving (Show)

      Scope checking an expression

      That entails everything we needed to build an UnambiguousScope, so we can now scope check a program. The actual scope checking itself is very straightforward:

      > scExpr
      >     :: UnambiguousScope -> Expr OccName
      >     -> Validation [ScopeError] (Expr FullName)
      > scExpr _ (Literal x) = pure (Literal x)
      > scExpr s (Add x y)   = Add <$> scExpr s x <*> scExpr s y
      > scExpr s (Var n)     = Var <$> scOccName s n
      > scOccName
      >     :: UnambiguousScope -> OccName
      >     -> Validation [ScopeError] FullName
      > scOccName s n = case lookup n s of
      >     Just fullName -> pure fullName
      >     Nothing       -> Failure [NotInScope n]


      I have described a simple and (in my opinion) elegant approach to scope checking. I hope this is inspiring if you ever are in the situation where modules would be a nice extension to some DSL (or full-fledged programming language) you are implementing.

      We’ve also seen how one can implement a Trie in a reasonably easy way. These often come in handy when you are modelling some sort of hierarchical Map.

      This entire blogpost is written in Literate Haskell, and works as a standalone example for scope checking. If you feel up to the challenge, try to add Let-bindings as an exercise! You can find the raw .lhs file here.


      This is the rest of the source code to this blogpost, in order to make it testable (and hackable!).

      > fruitModule :: Module OccName
      > fruitModule = Module
      >     { mName     = ["Calories.Fruit"]
      >     , mBindings =
      >         [ Binding ["apple"]  (Literal 52)
      >         , Binding ["banana"] (Literal 89)
      >         ]
      >     }
      > pieModule :: Module OccName
      > pieModule = Module
      >     { mName     = ["Calories.Pie"]
      >     , mBindings =
      >         [ Binding ["apple"]     (Literal 240)
      >         , Binding ["blueberry"] (Literal 371)
      >         ]
      >     }
      > myModule :: Module OccName
      > myModule = Module
      >     { mName     = ["Main"]
      >     , mBindings =
      >         [ Binding ["combo"] $ Add
      >               (Var ["apple"])
      >               (Var ["Pie", "apple"])
      >         ]
      >     }
      > scModule
      >     :: UnambiguousScope -> Module OccName
      >     -> Validation [ScopeError] (Module FullName)
      > scModule s (Module n bs) = Module n <$> traverse (scBinding s) bs
      > scBinding
      >     :: UnambiguousScope -> Binding OccName
      >     -> Validation [ScopeError] (Binding FullName)
      > scBinding s (Binding n e) = Binding <$> scOccName s n <*> scExpr s e
      > main :: IO ()
      > main = do
      >     let ambiguous = unionScopes
      >           [ scopeFromModule fruitModule
      >           , qualifyScope ["Pie"] $ scopeFromModule pieModule
      >           , scopeFromModule myModule
      >           ]
      >     print $ do
      >         unambiguous <- validationToEither $ toUnambiguousScope ambiguous
      >         validationToEither $ scModule unambiguous myModule

      1. Actually, in this representation, there is no “the” empty trie, since one can represent an empty trie in infinite ways.

      2. GHC only reports ambiguity errors for imported names when they are actually used, not when they are imported. We could also achieve this behaviour by continuing with the AmbiguousScope and throwing an error from scOccName when there is ambiguity.

      by Jasper Van der Jeugt at October 30, 2015 12:00 AM

      October 29, 2015

      Manuel M T Chakravarty

      Video of Functional Programming in a Stateful World

      Earlier this year, at YOW! Lambda Jam (in Brisbane), I gave a talk about developing a Mac app in Swift. More precisely, I described my take on how to best apply functional programming principles when writing Cocoa (Touch) apps in Swift. The video for the talk “Functional Programming in a Stateful World” is now online (and the slides are on Speaker Deck).

      October 29, 2015 12:36 PM

      Joey Hess

      concurrent output library

      concurrent-output is a Haskell library I've developed this week, to make it easier to write console programs that do a lot of different things concurrently, and want to serialize concurrent outputs sanely.

      It's increasingly easy to write concurrent programs, but all their status reporting has to feed back through the good old console, which is still obstinately serial.

      Haskell illustrates problem this well with this "Linus's first kernel" equivilant interleaving the output of 2 threads:

      > import System.IO
      > import Control.Concurrent.Async
      > putStrLn (repeat 'A') `concurrently` putStrLn (repeat 'B')

      That's fun, but also horrible if you wanted to display some messages to the user:

      > putStrLn "washed the car" `concurrently` putStrLn "walked the dog"
      walwkaesdh etdh et hdeo gc

      To add to the problem, we often want to run separate programs concurrently, which have output of their own to display. And, just to keep things interesting, sometimes a unix program will behave differently when stdout is not connected to a terminal (eg, ls | cat).

      To tame simple concurrent programs like these so they generate readable output involves a lot of plumbing. Something like, run the actions concurrently, taking care to capture the output of any commands, and then feed the output that the user should see though some sort of serializing channel to the display. Dealing with that when you just wanted a simple concurrent program risks ending up with a not-so-simple program.

      So, I wanted an library with basically 2 functions:

      outputConcurrent :: String -> IO ()
      createProcessConcurrent :: CreateProcess -> IO whatever

      The idea is, you make your program use outputConcurrent to display all its output, and each String you pass to that will be displayed serially, without getting mixed up with any other concurrent output.

      And, you make your program use createProcessConcurrent everywhere it starts a process that might output to stdout or stderr, and it'll likewise make sure its output is displayed serially.

      Oh, and createProcessConcurrent should avoid redirecting stdout and stderr away from the console, when no other concurrent output is happening. So, if programs are mostly run sequentially, they behave as they normally would at the console; any behavior changes should only occur when there is concurrency. (It might also be nice for it to allocate ttys and run programs there to avoid any behavior changes at all, although I have not tried to do that.)

      And that should be pretty much the whole API, although it's ok if it needs some function called by main to set it up:

      import Control.Concurrent.Async
      import System.Console.Concurrent
      import System.Process
      main = withConcurrentOutput $
          outputConcurrent "washed the car\n"
          createProcessConcurrent (proc "ls" [])
          outputConcurrent "walked the dog\n"
      $ ./demo
      washed the car
      walked the dog
      Maildir/  bin/  doc/  html/  lib/  mail/  mnt/  src/  tmp/

      I think that's a pretty good API to deal with this concurrent output problem. Anyone know of any other attempts at this I could learn from?

      I implemented this over the past 3 days and 320 lines of code. It got rather hairy:

      • It has to do buffering of the output.
      • There can be any quantity of output, but program memory use should be reasonably small. Solved by buffering up to 1 mb of output in RAM, and writing excess buffer to temp files.
      • Falling off the end of the program is complicated; there can be buffered output to flush and it may have to wait for some processes to finish running etc.
      • The locking was tough to get right! I could not have managed to write it correctly without STM.

      It seems to work pretty great though. I got Propellor using it, and Propellor can now run actions concurrently!

      October 29, 2015 02:07 AM

      October 28, 2015


      FRP — Release of reactive-banana version 1.0

      In the Haskell ecosystem, the version numbers of many libraries start with a zero. This is usually because the maintainer feels that the library is still incomplete and does not merit that magic first version number, 1.0. This is true even for some core libraries, like the bytestring library, which is currently at version

      Every now and then, however, a library author feels that his work has reached the level of completion that he originally envisioned before embarking on the unexpectedly long and perilous journey of actually building the library. Today is such a day. I am very pleased to announce the release of version 1.0 of my reactive-banana library on hackage!

      As of now, reactive-banana is a mature library for functional reactive programming (FRP) that supports first-class Events and Behaviors, continuous time, dynamic event switching, push-based performance characteristics and garbage collection.

      As planned, the API has changed significantly between the versions 0.9 and 1.0. The major changes are:

      • Dynamic event switching has become much easier to use. On the other hand, this means that all operations that depend on the previous history, like accumE or stepper are now required to be in the Moment monad.

      • Events may no longer contain occurrences that are simultaneous. This is mainly a stylistic choice, but I think it makes the API simpler and makes simultaneity more explicit.


      If you have been using the sodium FRP library, note that Stephen Blackheath has deprecated the Haskell variant of sodium so that he can focus on his upcoming FRP book and on the sodium ports for other languages. The APIs for sodium and reactive-banana 1.0 are very similar, porting should be straightforward.

      Thanks to Markus Barenhoff and Luite Stegeman, reactive-banana 1.0 now also works with GHCJS. If it doesn’t, in particular due to premature garbage collection, please report any offending programs.

      Of course, the library will continue to evolve in the future, but I think that it now has a proper foundation.

      Now, go forth and program functional reactively!

      October 28, 2015 11:20 PM

      Jan Stolarek

      Typed holes support in Template Haskell

      Back in April I found myself in a need for typed holes in Template Haskell. To my disappointment it turned out that typed holes are not implemented in TH. Sadly, this happens too often: a feature is added to GHC but no Template Haskell support is implemented for it. This was the time when I was working on injective type families and I already had some experience in extending TH implementation. I figured that adding support for typed holes should be a trivial task, no more than 30 minutes of coding. I created a feature request on Trac and started coding. I quickly realized that it won’t be that simple. Not that the amount of required work was that extensive. I simply tripped over the way GHC handles names internally. As a result the work got stalled for several months and I only finished it two weeks ago thanks to help from Richard Eisenberg.

      My patch allows you to do several interesting things. Firstly, it allows to quote typed holes, ie. expressions with name starting with an underscore:

      [d| i :: a -> a
          i x = _ |]

      This declaration quote will represent _ using an UnboundVarE constructor. Secondly, you can now splice unbound variables:

      i :: a -> a
      i x = $( return $ VarE (mkName "_") )
      j :: a -> a
      j x = $( return $ UnboundVarE (mkName "_") )

      Notice that in a splice you can use either VarE or UnboundVarE to represent an unbound variable – they are treated the same.

      A very important side-effect of my implementation is that you can actually quote unbound variables. This means that you can now use nested pattern splices, as demonstrated by one of the tests in GHC testsuite:

      baz = [| \ $( return $ VarP $ mkName "x" ) -> x |]

      Previously this code was rejected. The reason is that:

      1. nested pattern splice is not compiled immediately, because it is possible that it refers to local variables defined outside of the bracket;
      2. the bracket is renamed immediately at the declaration site and all the variables were required to be in scope at that time.

      The combination of the above means that the pattern splice does not bring anything into scope (because it is not compiled until the outer bracket is spliced in), which lead to x being out of scope. But now it is perfectly fine to have unbound variables in a bracket. So the above definition of baz is now accepted. When it is first renamed x is treated as an unbound variable, which is now fine, and when the bracket is spliced in, the inner splice is compiled and it correctly brings binding for x into scope. Getting nested pattern splices to work was not my intention when I started implementing this patch but it turned out we essentially got this feature for free.

      One stumbling block during my work was typed Template Haskell. With normal, untyped TH I can place a splice at top-level in a file:

      $$(return [
         SigD (mkName "m")
              (ForallT [PlainTV (mkName "a")]
                       (AppT (AppT ArrowT (VarT (mkName "a"))) (VarT (mkName "a"))))
       , FunD (mkName "m")
              [Clause [VarP (mkName "x")] (NormalB (VarE (mkName "x"))) [] ]

      and this will build a definition that will be spliced into the source code. But converting this into a typed splice, by saying $$(return ...., resulted in compiler panic. I reported this as #10945. The reason turned out to be quite tricky. When Template Haskell is enabled, top-level expressions are allowed. Each such expression is treated as an implicit splice. The problem with typed TH splice is that it doesn’t really make sense at the top-level and it should be treated as an implicit splice. Yet it was treated as an explicit splice, which resulted in a panic later in the compiler pipeline.

      Another issue that came up with typed TH was that typed holes cannot be quoted, again leading to panic. I reported this as #10946. This issue has not yet been solved.

      The above work is now merged with HEAD and will be available in GHC 8.0.

      by Jan Stolarek at October 28, 2015 06:05 PM

      Neil Mitchell

      ViewPatterns and lambda expansion

      Summary: One of HLint's rules reduced sharing in the presence of view patterns. Lambda desugaring and optimisation could be improved in GHC.

      HLint has the rule:

      function x = \y -> body
      function x y = body

      Given a function whose body is a lambda, you can use the function syntactic sugar to move the lambda arguments to the left of the = sign. One side condition is that you can't have a where binding, for example:

      function x = \y -> xx + y
      where xx = trace "hit" x

      This is equivalent to:

      function x = let xx = trace "hit" x in \y -> xx + y

      Moving a let under a lambda can cause arbitrary additional computation, as I previously described, so is not allowed (hint: think of map (function 1) [2..5]).

      View Patterns

      One side condition I hadn't anticipated is that if x is a view pattern, the transformation can still reduce sharing. Consider:

      function (trace "hit" -> xx) = \y -> xx + y

      This is equivalent to:

      function x = case trace "hit" x of xx -> \y -> xx + y

      And moving y to the right of the = causes trace "hit" to be recomputed for every value of y.

      I've now fixed HLint 1.9.22 to spot this case. Using Uniplate, I added the side condition:

      null (universeBi pats :: [Exp_])

      Specifically, there must be no expressions inside the pattern, which covers the PViewPat constructor, and any others that might harbour expressions (and thus computation) in future.

      The problem with function definitions also applies equally to \p1 -> \p2 -> e, which cannot be safely rewritten as \p1 p2 -> e if p1 contains a view pattern.

      The Problem Worsens (Pattern Synonyms)

      Pattern synonyms make this problem worse, as they can embody arbitrary computation in a pattern, which is lexically indistinguishable from a normal constructor. As an example:

      pattern Odd <- (odd -> True)
      f Odd = 1
      f _ = 2

      However, putting complex computation behind a pattern is probably not a good idea, since it makes it harder for the programmer to understand the performance characteristics. You could also argue that using view patterns and lambda expressions to capture computation after partial application on definitions then lambda expressions is also confusing, so I've refactored Shake to avoid that.

      Potential Fixes

      I think it should be possible to fix the problem by optimising the desugaring of functions, ensuring patterns are matched left-to-right where allowable, and that each match happens before the lambda requesting the next argument. The question is whether such a change would improve performance generally. Let's take an example:

      test [1,2,3,4,5,6,7,8,9,10] x = x
      test _ x = negate x

      Could be changed to:

      test [1,2,3,4,5,6,7,8,9,10] = \x -> x
      test _ = trace "" $ \x -> negate x

      Which goes 3-4x faster when running map (test [1..]) [1..n] at -O2 (thanks to Jorge Acereda Maciá for the benchmarks). The trace is required to avoid GHC deoptimising the second variant to the first, as per GHC bug #11029.

      There are two main downsides I can think of. Firstly, the desugaring becomes more complex. Secondly, these extra lambdas introduce overhead, as the STG machine GHC uses makes multiple argument lambdas cheaper. That overhead could be removed using call-site analysis and other optimisations, so those optimisations might need improving before this optimisation produces a general benefit.

      by Neil Mitchell ( at October 28, 2015 12:56 PM

      October 26, 2015

      Neil Mitchell

      FilePaths are subtle, symlinks are hard

      Summary: When thinking about the filepath .., remember symlinks, or you will trip yourself up.

      As the maintainer of the Haskell filepath package, one common path-related mistake I see is the assumption that filepaths have the invariant:

      /bob/home/../cookies == /bob/cookies

      I can see the conceptual appeal - go down one directory, go up one directory, end up where you started. Unfortunately, it's not true. Consider the case where home is a symlink to tony/home. Now, applying the symlink leaves us with the case:

      /tony/home/../cookies == /bob/cookies

      And, assuming /tony/home is itself not a symlink, that reduces to:

      /tony/cookies == /bob/cookies

      This is clearly incorrect (assuming no symlinks), so the original invariant was also incorrect, and cannot be relied upon in general. The subtle bit is that descending into a directory might move somewhere else, so it's not an operation that can be undone with ... Each step of the path is interpreted based on where it ends up, not based on the path it took to the current point.

      While this property isn't true in general, there are many special cases where it is reasonable to assume. For example, the shake package contains a normaliseEx function that normalises under this assumption, but nothing in the standard filepath package assumes it.

      The full example
      [DIR] bob
      [DIR] tony
      [LINK] home -> /tony/home
      [FILE] cookies
      [DIR] home
      [FILE] cookies

      by Neil Mitchell ( at October 26, 2015 09:03 PM

      Roman Cheplyaka

      Static linking with ghc

      Recently I needed to build a Haskell program that would run on my DigitalOcean box. The problem was that my laptop’s Linux distro (Fedora 22) was different from my server’s distro (Debian jessie), and they had different versions of shared libraries.

      I could build my app directly on the server, but I decided to go with static linking instead. I didn’t find a lot of information about static linking with ghc on the internet, hence this article.

      First, let’s clarify something. There are two kinds of libraries any Haskell program links against: Haskell libraries and non-Haskell (most often, C) libraries. Haskell libraries are linked statically by default; we don’t need to worry about them. ghc’s -static and -dynamic flag affect that kind of linking.

      On the other hand, non-Haskell libraries are linked dynamically by default. To change that, we need to pass the following options to ghc:

      -optl-static -optl-pthread

      If you are using stack (as I did), the whole command becomes

      stack build --ghc-options='-optl-static -optl-pthread' --force-dirty

      --force-dirty may be needed because stack may not recognize the options change as a sufficient reason to re-run ghc; this may get fixed in future versions of stack.

      The command may fail in case you don’t have some of the static libraries installed. In my case, the dynamic version of the executable had these dynamic dependencies (as reported by ldd): (0x00007ffcb20c2000) => /lib64/ (0x00007fa435dc6000) => /lib64/ (0x00007fa435bc3000) => /lib64/ (0x00007fa4359be000) => /lib64/ (0x00007fa43574e000) => /lib64/ (0x00007fa4354d6000) => /lib64/ (0x00007fa4351cd000) => /lib64/ (0x00007fa434fb6000) => /lib64/ (0x00007fa434bf6000) => /lib64/ (0x00007fa4349d9000)
      /lib64/ (0x000055571e53e000)

      To satisfy them statically, I had to install only three Fedora packages:


      October 26, 2015 08:00 PM

      FP Lunch

      Creating Personal Ambitions

      Most of us become paralyzed by concern when it comes to truly treading out and doing something about our aspiration. The life we wish is visualized by us, we find out about our people carrying it out and think that somehow they’re extra ordinary or involve some super-human power that makes them in a position to live our aspiration out. The fact remains which they simply began going. There are certainly a lot of individuals who like to compose and want notify to stimulate or educate their given industry on their unique attention. These folks actually cease themselves possibly dreaming about doing this for a living since they just cant work out how to get there using their existence. Their lifestyle meaning Oh Ive got youngsters to look after, oh I better get my doctorate degree first, oh Im not fairly enough, oh I dont learn the first in regards to the writing industry. These arent sensible explanations why you cant become a productive published author, these are simply reasons.

      Your sign your sign is also named your “rising indicator.” the 2 phrases are interchangeable.

      There are effective authors all over the world who arent any prettier, smarter, thicker, or maybe more exclusive than you’re, they are only doers and not just dreamers. Should you would consider oneself a dreamer then you definitely must become a doer! This is actually the self-published author’s evening. Becoming a home- printed writer will be the method you’ll be able to begin and develop a book publishing profession that is productive and lucrative. More and more people so are taking control in their future and are canning their ideas of pursuing traditional book publishing deals and getting self- released experts. You can study a lot of distinct companies that can help you receive your guide printed. I recommend choosing a company that has a simple deal, a simple writing offer which includes most of the thing you need to have a functional, world class book plus one that could give superior discussion on marketing your book to you.

      Melanoma guys are unbelievable lovers.

      There are various approaches to market your guide and a marketing plan that suits your lifestyle can be definitely developed by you. For example, if you’re a property mommy and you are an expert in health and you need to start to inform people through creating your own book, you are able to produce a book promotional approach that’s more web than basically traveling a lot doing workshops and book signings. My book would be published by me with a firm which was at least able to support me develop a marketing plan if I needed since 90% to become an effective writer of the work may be the marketing and marketing that aid. But dont permit this shock you. If you would like to achieve your dream of being a published publisher then consult with somebody who can provide you on publishing the top & most valuable guide feasible direction and do some investigation about the marketplace and maybe custom essays for sale you just need to consider step one.

      by Administrator at October 26, 2015 03:10 PM

      FP Complete

      The new haskell-ide repo

      Recently Alan Zimmerman announced on the haskell-cafe mailing list that there was a new haskell-ide project, with a new Github repository, a mailing list and an IRC channel. Some people have been concerned that this effort is fragmenting existing efforts, including with ide-backend (the open sourced library FP Complete announced earlier this year). I clarified this on Reddit, but wanted to take the opportunity to do so on this blog as well (and, additionally, throw some extra attention on the haskell-ide project).

      Alan's announcement did not come in a vacuum; about two weeks ago, he reached out to others for feedback on a potential project. There were some side channel discussions that I was involved in, all of which were very much in favor of (and excited about!) this project. To quote myself from Reddit, we reached the following conclusion:

      Both the ghc-mod and ide-backend maintainers have agreed to contribute code to this new repository and then rebase the old repos on this. The reason we're using a new repo instead of modifying one of the existing ones is so that the existing projects experience no disruption during this migration process. If this was a new set of people starting a new project without support from existing projects, I'd agree with you. But Alan's reached out to existing players already, which is an important distinction.

      Michael Sloan - the current maintainer of ide-backend and one of the primary developers of both School of Haskell and FP Haskell Center - is already getting involved in this project. It's too early to decide exactly what the future of ide-backend will be relative to haskell-ide, but we're not ruling anything out. Anything from rebasing ide-backend to use haskell-ide internally, all the way to deprecating ide-backend in favor of haskell-ide, is on the table. We'll do whatever makes the most sense to help the Haskell community create great tooling.

      Related to this project: a number of people have been following the development of stack-ide. We started that project not realizing how quickly existing tooling (like ghc-mod and hdevtools) would adopt support for Stack, and certainly not expecting this new haskell-ide project to offer a unifying force in the Haskell tooling space. To avoid fragmentation, we're currently holding off on further word on stack-ide, hoping instead that collaboration will help improve existing tooling not just for the Stack use case, but for cabal, cabal sandboxes, and other cases people have been targeting.

      Since I'm already discussing IDE stuff, let me publicly give an answer I've given privately to a few people. A number of individuals have asked about the future of the FP Haskell Center codebase, and the possibility of open sourcing it. The summary answer is:

      • Everything related to School of Haskell is being open sourced. Most of that is done already, the rest is just in the last few stages of code cleanup.
      • The current state of the FP Haskell Center code base is difficult to simply give out, since it's based on some superseded technologies. For example, we created it in a world where Docker didn't exist, and have quite a few LXC scripts to make it work. We also have some difficult-to-manage build scripts that could be replaced by Stack. We've cleaned all of this up for School of Haskell, but have not done the same to the FP Haskell Center codebase.
      • As a general policy, we don't like to just drop unsupported code on the community at FP Complete. If there are maintainers that are interested in taking over the current FPHC codebase, we can discuss transferring it over. But simply open sourcing without any support tends not to be a helpful move (instead, it distracts from other, active projects, which we don't want to do).
      • One possibility going forward is that, once the School of Haskell web service is up, running, and stable, a new IDE project could be started that targets that same API. We're not planning on running such a project at FP Complete, but we'd be happy to provide some feedback, and include necessary changes to the SoH service to make it work.

      I hope this excites others as much as it excites me: some concerted efforts on improving tooling can hopefully go a long way. A big thank you to Alan for coordinating this effort, and to Michael Sloan for leading the charge from the FP Complete side. I'm optimistic that we'll see some real strides forward in the near future.

      October 26, 2015 05:00 AM

      Christopher Done

      Idle thoughts: More open, more free software

      I’m a bit busy, these are just some idle thoughts.

      I just upgraded my Android OS to some other kind of dessert name and a bunch of stuff changed in a way I had no desire for.

      It made me think about the virtues of open source software. I can just go and change it! Free software means benefiting from the work of others without being shackled by them at the same time.

      And then about the problems of open source software, which is that only developers-skilled developers-with specific knowledge, are able to approach the codebase of an app they use, update it, and then use that new software in a continuous and smooth way. Everyone else’s hands are effectively tied behind their backs.

      So that got me thinking about how software could be more “open” than simply “open source”, if it was inherently more configurable. And also about better migration information from one piece of software to the next.

      So I imagined a world in which when I get an update for a piece of software I could see a smart diff, as a regular human, of what the new UI and behaviour looks like, how it changed. This button moved there, changed color. Pressing this button used to exhibit X behaviour, now that behaviour is more complicated, or more limited, to trigger this action, and so on.

      I believe that a properly declarative UI library with explicit state modeling, such as in Elm or whatnot, could actually handle a thing like that, but that it would have to be designed from the bottom up like that. And every component would need to have some “mock” meta-data about it, so that the migration tool could say “here’s what the old UI looks like with lorem ipsum data in it and here’s what that same data, migrated, looks like in the new UI” and you could interact with this fake UI on fake data, with no consequences. Or interact with the user’s data in a read-only “fake” way.

      You could say: actually, no, I want to configure that this button will stay where it is, that the theme will stay my current dark theme, etc.

      You could visualize state changes in the UI such as with the time traveling thing in Elm or React and make new decision trees, or perhaps pick between built-in behaviours.

      But one key idea could be that when you update software in a new way, unless you’re removing the ability to do a feature completely (e.g. the server won’t even respond to that RPC call), then you should indicate that, in the intelligent “software diff”: then the user can say, no I still want to use that and now they have a “patched” or “forked” version of the software locally but that the maintainers of the software don’t have to worry about.

      Normally configuring software is a thing developers manually hard code into the product. It seems obviously better to make software inherently configurable, from a free software perspective at least (not from a proprietary locked-in perspective).

      Of course, you could write code at any time; drop down to that. But if most of the code can be self-describing at least in a high-level “do the thing or that thing” way, this would be far more accessible to general users than code itself which at the moment is magic and certainly beyond my interest to go and patch for the most part.

      October 26, 2015 12:00 AM

      October 25, 2015

      Dimitri Sabadie

      luminance, episode 0.6: UBO, SSBO, Stackage.

      Up to now, luminance has been lacking two cool features: UBO and SSBO. Both are buffer-backed uniform techniques. That is, a way to pass uniforms to shader stages through buffers.

      The latest version of luminance has one of the two features. UBO were added and SSBO will follow for the next version, I guess.

      What is UBO?

      UBO stands for Uniform Bbuffer Object. Basically, it enables you to create uniform blocks in GLSL in feed them with buffers. Instead of passing values directly to the uniform interface, you just write whatever values you want to to buffers, and then pass the buffer as a source for the uniform block.

      Such a technique has a lot of advantages. Among them, you can pass a lot of values. It’s also cool when you want to pass values instances of a structure (in the GLSL source code). You can also use them to share uniforms between several shader programs as well as quickly change all the uniforms to use.

      In luminance, you need several things. First thing first, you need… a buffer! More specifically, you need a buffer Region to store values in. However, you cannot use any kind of region. You have to use a region that can hold values that will be fetched from shaders. This is done with a type called UB a. A buffer of UB a can be used as UBO.

      Let’s say you want to store colors in a buffer, so that you can use them in your fragment shader. We’ll want three colors to shade a triangle. We need to create the buffer and get the region:

      colorBuffer :: Region RW (UB (V3 Float)) <- createBuffer (newRegion 3)

      The explicit type is there so that GHC can infer the correct types for the Region. As you can see, nothing fancy, except that we just don’t want a Region RW (V3 Float but Region RW (UB (V3 Float)). Why RW?

      Then, we’ll want to store colors in the buffer. Easy peasy:

      writeWhole colorBuffer (map UB colors)

      colors :: [V3 Float]
      colors = [V3 1 0 0,V3 0 1 0,V3 0 0 1] -- red, green, blue

      At this point, colorBuffer represents a GPU buffer that holds three colors: red, green and blue. The next part is to get the uniform interface. That part is experimental in terms of exposed interface, but the core idea will remain the same. You’re given a function to build UBO uniforms as you also have a function to build simple and plain uniforms in createProgram:

      createProgram shaderList $ \uni uniBlock -> {- … -}

      Don’t spend too much time reading the signature of that function. You just have to know that uni is a function that takes Either String Natural – either a uniform’s name or its integral semantic – and gives you mapped U in return and that uniBlock does the same thing, but for uniform blocks instead.

      Here’s our vertex shader:

      in vec2 co;
      out vec4 vertexColor;

      // This is the uniform block, called "Colors" and storing three colors
      // as an array of three vec3 (RGB).
      uniform Colors {
      vec3 colors[3];

      void main() {
      gl_Position = vec4(co, 0., 1.);
      vertexColor = vec4(colors[gl_VertexID], 1.);

      So we want to get a U a mapped to that "Colors" uniform block. Easy!

      (program,colorsU) <- createProgram shaderStages $ \_ uniBlock -> uniBlock "Colors"

      And that’s all! The type of colorsU is U (Region rw (UB (V3 Float))). You can then gather colorBuffer and colorsU in a uniform interface to send colorBuffer to colorsU!

      You can find the complete sample here.

      Finally, you can augment the type you can use UB with by implementing the UniformBlock typeclass. You can derive the Generic typeclass and then use a default instance:

      data MyType = {- … -} deriving (Generic)

      instance UniformBlock MyTpe -- we’re good to go with buffer of MyType!

      luminance, luminance-samples and Stackage

      I added luminance and luminance-samples into Stackage. You can then find them in the nightly snapshots and the future LTS ones.

      What’s next?

      I plan to add stencil support for the framebuffer, because it’s missing and people might like it included. I will of course add support for *SSBO** as soon as I can. I also need to work on cheddar but that project is complex and I’m still stuck with design decisions.

      Thanks for reading my and for your feedback. Have you great week!

      by Dimitri Sabadie ( at October 25, 2015 10:29 PM

      Yesod Web Framework

      Resurrecting servius

      A while ago, I wrote a small package called servius, a simple executable that serves static files with Warp, and will additionally render Hamlet and Lucius templates. In some earlier package consolidation, the tool became part of shakespeare, and eventually was commented out (due to concerns around the dependency list on Hackage looking too big).

      Today, I just resurrected this package, and added support for rendering Markdown files as well. I often times end up working on Markdown files (such as for this blog, the Haskell Documentation project, and the FP Complete blog), and being able to easily view the files in a browser is useful.

      As it stands, the three specially-handled file types of Hamlet (.hamlet), Lucius (.lucius), and Markdown (.markdown and .md). If others wish to add more templating or markup languages to this list, I'm more than happy to access pull requests.

      Final note: this package is currently uploaded using the pvp-bounds feature of Stack, so don't be surprised when the version bounds on Hackage are more restrictive than those in the repo itself.

      October 25, 2015 08:00 AM