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

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_cmd = cc_parser.parse_known_args(sys.argv)[1][1:]

subprocess.call(cc_cmd)

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.

# (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?

Nope.

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

Nope.

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.

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.

## Throughput

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.

## Maintenance

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.

## Vendors

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.

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

Stupid.

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

Stupider.

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!

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?

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

# 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 https://github.com/elm-lang/elm-compiler.git"
"git clone -b 0.16 https://github.com/elm-lang/elm-package.git"
"git clone -b 0.16 https://github.com/elm-lang/elm-make.git"
"git clone -b 0.16 https://github.com/elm-lang/elm-reactor.git"
"git clone -b 0.16 https://github.com/elm-lang/elm-repl.git"
)

for r in ${repos[@]}; do eval${r}
done

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!

# 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
where
funcName = "System.Linux.Inotify.getEvent"
loop = join $withLock bufferLock$ do
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: (do 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. ## November 19, 2015 ### FP Complete # Kubernetes for Haskell Services # Kubernetes (AKA "k8s") From kubernetes.io: 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: • AWS_ACCESS_KEY_ID • AWS_SECRET_ACCESS_KEY • AWS_DEFAULT_REGION ## 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 externalDNSName: kube.mydomain.com # 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. kube.mydomain.com. IN A <<IPADDRESS>> If you don't have control of DNS for a domain, you can put an entry into your /etc/hosts file. kube.mydomain.com <<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: [.] image: container: 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 [("Content-Type","text/plain")] "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 dockerhub.com. 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 metadata: name: hello spec: replicas: 2 template: metadata: labels: app: hello spec: containers: - name: hello image: dysinger/hello:0.1.0 command: - hello ports: - 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 metadata: name: hello labels: app: hello spec: ports: - name: http port: 80 targetPort: http selector: 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. hello.mydomain.com. CNAME <<ELB-HOSTNAME>>. ### 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.Preludeimport Typed.Spreadsheetdata AColor = Red | Orange | Yellow | Green | Blue | Purple deriving (Enum, Bounded, Show)toColor :: AColor -> Colour DoubletoColor Red = redtoColor Orange = orangetoColor Yellow = yellowtoColor Green = greentoColor Blue = bluetoColor Purple = purplemain :: IO ()main = graphicalUI "Example program" logic where 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="https://www.youtube.com/embed/xPWuzZHGnHk" width="420"></iframe>

#### Applicatives

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 AColorspinButtonAt 100 "Radius"       1                      :: Updatable DoublespinButton       "X Coordinate" 1                      :: Updatable DoublespinButton       "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:

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

#### Charts

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.Preludeimport Typed.Spreadsheetimport qualified Data.Text as Textbar :: Int -> Updatable (Diagram Cairo)bar i = fmap buildRect (spinButtonAt 100 label 1)  where    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="https://www.youtube.com/embed/lZoMwxgULB0" 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.Preludeimport Typed.Spreadsheetimport qualified Data.Text as Textbar :: Int -> Updatable (Diagram Cairo)bar i = fmap buildRect (spinButtonAt 100 label 1)  where    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])  where    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="https://www.youtube.com/embed/JybjVmrAw9I" 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.Preludeimport Typed.Spreadsheetimport qualified Data.Text as Textbar :: Int -> Updatable (Diagram Cairo)bar i = fmap buildBar (spinButtonAt 100 label 0.2)  where    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                  )        )      where        stepSize = 15        vine = strokeP (fromVertices (map toPoint [0..height]))          where            toPoint n = p2 (5 * cos (pi * n / stepSize), n)        bubble n =            circle radius                # translate (r2 (0, n * stepSize))                # fc lightblue          where            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])  where    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="https://www.youtube.com/embed/UWLY-zmDe7Y" 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.

#### Conclusion

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.

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

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

ABSTRACT

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

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

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

### Example

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

# 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 &) ;
} ;



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

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

# 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

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

## November 14, 2015

### Gabriel Gonzalez

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 todosinterpret :: 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 todosdelete :: Int -> [a] -> Maybe [a]delete 0 (_:as) = Just asdelete n (a:as) = do    as' <- delete (n - 1) as    return (a:as')delete _  []    = Nothingmain = do    putStrLn "Commands:"    putStrLn "+ <String> - Add a TODO entry"    putStrLn "- <Int>    - Delete the numbered entry"    putStrLn "q          - Quit"    prompt []

Example usage:

#### 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 = Phedecode U U C = Phedecode U U A = Leudecode U U G = Leudecode U C _ = Serdecode U A U = Tyrdecode U A C = Tyrdecode U A A = Stopdecode U A G = Stopdecode U G U = Cysdecode U G C = Cysdecode U G A = Stopdecode U G G = Trpdecode C U _ = Leudecode C C _ = Prodecode C A U = Hisdecode C A C = Hisdecode C A A = Glndecode C A G = Glndecode C G _ = Argdecode A U U = Iledecode A U C = Iledecode A U A = Iledecode A U G = Metdecode A C _ = Thrdecode A A U = Asndecode A A C = Asndecode A A A = Lysdecode A A G = Lysdecode A G U = Serdecode A G C = Serdecode A G A = Argdecode A G G = Argdecode G U _ = Valdecode G C _ = Aladecode G A U = Aspdecode G A C = Aspdecode G A A = Gludecode G A G = Gludecode G G _ = GlydecodeAll :: [RNA] -> [AminoAcid]decodeAll (a:b:c:ds) = decode a b c : decodeAll dsdecodeAll  _         = []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:

#### Conclusion

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

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

## HTML

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 setup.py MANIFEST.in file

Moving up towards ‘proper’ programming language, I came across this example — the MANIFEST.in 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 MANIFEST.in 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 MANIFEST.in 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 MANIFEST.in 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 MANIFEST.in 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 MANFIEST.in 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 setup.py 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 setup.py) 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 MANIFEST.in altogether and optimise only the case when it is completely empty.

2. The power has a second cost — MANIFEST.in 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 MANIFEST.in 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 MANIFEST.in 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 MANIFEST.in 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% MANIFEST.in 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/urls.py 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 views.py 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 cuteness.com, a URL like http://www.cuteness.com/kittens/23/ 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 urls.py 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]
try:
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...

## 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():
pass

def bar(a, callback=foo):
pass


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

Using a decorator:

@decorateit
def foo():
pass

@decorateit
def bar():
pass


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()):
pass

def bar(x=Something()):
pass


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 :-(

## Summary

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.

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

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

# luminance-0.7

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!

## Overview

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.

### usampler2D

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! :)

# 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?

# 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)
33308


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
-0.5
-0.3368421052631579
-0.31572844839628944
-0.31530116270327685
-0.31530098645936266
-0.3153009864593327
-0.3153009864593327


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 0.0  ## 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. ### 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.Applicativeimport Typed.Spreadsheetmain :: IO ()main = textUI "Example program" logic where -- 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.

#### Distribution

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.Applicativeimport Data.Monoidimport Data.Text (Text)import Typed.Spreadsheetpayment :: Double -> Double -> Double -> Textpayment mortgageAmount numberOfYears yearlyInterestRate    =  "Monthly payment: $" <> display (mortgageAmount * (i * (1 + i) ^ n) / ((1 + i) ^ n - 1)) where n = truncate (numberOfYears * 12) i = yearlyInterestRate / 12 / 100logic :: Updatable Textlogic = payment <$> spinButton "Mortgage Amount"          1000                <*> spinButton "Number of years"             1                <*> spinButton "Yearly interest rate (%)"    0.01main :: 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.Monoidimport Typed.Spreadsheetnoun = entry "Noun"verb = entry "Verb"adjective = entry "Adjective"example =    "I want to " <> verb <> " every " <> noun <> " because they are so " <> adjectivemain :: 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.

#### Applicatives

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 Boolz = (&&) <$> 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 Boolz = 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.Spreadsheetmain :: 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. #### Conclusion 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. ### 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. ## 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 OSDev.org 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. #![feature(asm)] unsafe fn outb(value: u8, port: u16) { asm!("outb %al, %dx" :: "{dx}"(port), "{al}"(value) :: "volatile"); }  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. ## 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 04, 2015 ### Well-Typed.Com # 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. ## Preparations 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 and 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
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"]
"2015-11-01"
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.

# 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

## 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 grademiners.com/dissertation-help who seasoned and is qualified.

# 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 192.168.1.199/24 dev eth0 label eth0:0

The configuration in Debian is

auto eth0:0
iface eth0:0 inet static
netmask 255.255.255.0

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

[Match]
Name=eth0

[Network]
Gateway=192.168.1.1

## 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=192.168.1.199:2048:2048 nw /home/myusre/echosrv

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

# Introduction

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 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 0  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} Thus \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' 2.85776225450217e-7  ## 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 0.31731050786291415 ghci> p 2.0 1.0 4.550026389635842e-2 ghci> p 3.0 1.0 2.699796063260207e-3  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
0.326

ghci> supAbove 2.0
7.0e-2

ghci> supAbove 3.0
0.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
0.31592655955519156

ghci> supAbove' 2.0
4.999395029856741e-2

ghci> supAbove' 3.0
2.3859203473651654e-3


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.

## Proof

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.

$\blacksquare$

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

Proof

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.

$\blacksquare$

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

Proof

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

$\blacksquare$

## 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}$

then

\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

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

# Notes

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

# Bibliography

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. https://books.google.co.uk/books?id=fsgkBAAAQBAJ.

# 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)
orElse
(RegionChange <$> regionListWaiter origsnapshot) orElse (BufferChange <$> outputBufferWaiterSTM waitCompleteLines)
orElse
(TerminalResize <$> waitwidthchange) orElse (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 2015

• October 29th, 2015: This is a perfect introduction to today's #haskell problem: dynamic predictions http://lpaste.net/6734184072140029952 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 http://lpaste.net/8373695753289203712
• October 28th, 2015: Today's #haskell problem, we DEFINE WHAT 'AVERAGE' IS! Nope. But we do take on predictive analytics! http://lpaste.net/6882676007984168960 So there's that. And here's the predictions-distributions. One day we'll even do ROC-analysis. Or not. http://lpaste.net/4234314648314183680
• October 27th, 2015: For today's #haskell problem we say "HEY! YOU! GET YOU SOME RANDOM, YO!" and then define a random number generator http://lpaste.net/5973373084290252800 A (random) solution (not really) to yesterday's random (really) #haskell problem http://lpaste.net/3547465428253016064
• October 26th, 2015: Well, bleh! It only took all day to compose, but here's today's #haskell problem! "Learning R...in Haskell!"http://lpaste.net/2843567468654362624 Okay, that (randomly) hurt! -- one possible solution to this problem is posted at http://lpaste.net/4854130028864077824
• October 23rd, 2015: Today's #haskell problem is thanks to Jim Webber's keynote at @GraphConnect is about triadic closurehttp://lpaste.net/2004709237044805632
• October 22nd, 2015: Today's #haskell problem is thanks to Jim Webber's keynoteat the @neo4j @GraphConnect: WWI Alliances http://lpaste.net/4042786156616613888  WWI-Allianceshttp://lpaste.net/4413387094903226368 … 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) http://lpaste.net/4391386661800378368
• October 15th, 2015: Today's #haskell problem is a real (silly) problem: 'efficientize' row and col definitions for Data.Matrix http://lpaste.net/7329174284021006336 Zippidy Doo-Dah! Zippidy day! My, oh, my we've 'efficientized' Matrix RowCol (that scans. Kinda) http://lpaste.net/4076800205951860736
• October 14th, 2015: For today's #haskell problem we look at multiplying matrices, because SCIENCE! http://lpaste.net/2775082411233378304 Today criss-cross is gonna JUMP-JUMP! ... and sauce the apples http://lpaste.net/6379071958448865280 (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 http://lpaste.net/7639242339784851456 Today we transpose matrices ... LIKE A GANGSTA! http://lpaste.net/4495861517937278976
• October 12th, 2015: We go from eh-matrices to ÜBERMATRICES for today's #haskell problem http://lpaste.net/3386266226073272320 And we übered those matrices at http://lpaste.net/4104557754952187904
• 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 http://lpaste.net/4256620462181711872 Matrices, REBORN! http://lpaste.net/5942967859750633472 (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 http://lpaste.net/2435920706567929856 That MultiMap is now hella-relaxed, yo! http://lpaste.net/8471070633348825088
• October 6th, 2015: So YESTERDAY we looked at Foldable. @argumatronic said "Step it up: do Traversable!" So for TODAY'S #haskell problem http://lpaste.net/4868288594713772032 So we WuTang Traversible CLANNEDthat solution! http://lpaste.net/4953464088320540672
• October 5th, 2015: For today's #haskell problem we go from Monadical to Foldable, thanks to @argumatronic http://lpaste.net/2602721740102565888 Wait. Is 'monadical' a word? DList. Foldable instance. Done. http://lpaste.net/8044707151110733824
• October 2nd, 2015: For today's #haskell problem we make multimaps fast with difference lists ... OR. DO. WE! http://lpaste.net/8174150842572603392 And today we find out HOW FAST MULTIMAPS ARE WITH DLISTS! (in all caps, no less) http://lpaste.net/341094126416035840
• October 1st, 2015: Yesterday we made Difference Lists Applicative, for today's #haskell problem we make them monadichttp://lpaste.net/1062399498271064064 So, difference lists are monadic now ... so there's that ... http://lpaste.net/4828960021565931520

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

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

# Introduction

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.

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-0.2.5.1:Data.HashMap.Base.empty. 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.

# Tries

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.

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

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

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: # 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 + Pie.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
> 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] # Conclusion 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. # Appendix 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.

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

# 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')
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA
...


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
ar


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" concurrently createProcessConcurrent (proc "ls" []) concurrently 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!

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

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!

# 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. ### 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 = 1f _ = 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 = xtest _ x = negate x Could be changed to: test [1,2,3,4,5,6,7,8,9,10] = \x -> xtest _ = 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.

# 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/bob   [LINK] home -> /tony/home   [FILE] cookies /tony   [DIR]  home/tony/home   [FILE] cookies

### Roman Cheplyaka

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

linux-vdso.so.1 (0x00007ffcb20c2000)
librt.so.1 => /lib64/librt.so.1 (0x00007fa435dc6000)
libutil.so.1 => /lib64/libutil.so.1 (0x00007fa435bc3000)
libdl.so.2 => /lib64/libdl.so.2 (0x00007fa4359be000)
libpcre.so.1 => /lib64/libpcre.so.1 (0x00007fa43574e000)
libgmp.so.10 => /lib64/libgmp.so.10 (0x00007fa4354d6000)
libm.so.6 => /lib64/libm.so.6 (0x00007fa4351cd000)
libgcc_s.so.1 => /lib64/libgcc_s.so.1 (0x00007fa434fb6000)
libc.so.6 => /lib64/libc.so.6 (0x00007fa434bf6000)
/lib64/ld-linux-x86-64.so.2 (0x000055571e53e000)

To satisfy them statically, I had to install only three Fedora packages:

pcre-static.x86_64
gmp-static.x86_64
glibc-static.x86_64

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

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.

### FP Complete

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.

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

# 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!

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

# Docker container with ip address on local network

Shortly after I started my new job in August I put an instance of gitlab on a server and started promoting using it over the git-repos-on-an-NFS-share that had been used thus far. Thanks to the Docker image of Gitlab CE it only took about 5 minutes to have a running instance – setting up authentication via LDAP only took slightly longer. So far I’ve been running it on non-standard ports, just like the guide suggests, but I’ve gotten to the point where I’d like to make it a bit more official. That means I’d like to get it off non-standard ports, but I do really like running it in Docker. In short, I need to give the Docker image an ip address on the local network.

Unfortunately Docker doesn’t make it easy to do that, but I found an article on four ways to connect a docker container to a local network. What follows is my take on the instruction for how to use a macvlan device to achieve it.

## An image for testing

First I looked around for a simple echo server to run in my testing image:

module Main
where

import Control.Concurrent
import Network.Socket
import System.IO

srvPort :: PortNumber
srvPort = 2048

main :: IO ()
main = withSocketsDo $do newSocket <- socket AF_INET Stream defaultProtocol setSocketOption newSocket ReuseAddr 1 bindSocket newSocket$ SockAddrInet srvPort iNADDR_ANY
listen newSocket 2
runServer echo newSocket

runServer :: (String -> String) -> Socket -> IO()
runServer f s = forever $do (usableSocket,_) <- accept s forkIO$ interactWithSocket f usableSocket

interactWithSocket :: (String -> String) -> Socket -> IO()
interactWithSocket f s = do
forever $f <$> hGetLine handle >>= hPutStrLn handle

echo :: String -> String
echo = ("R: " ++)

Run it and test it by pointing netcat to port 2048.

Once that was built I put together a Dockerfile that uses Debian Jessie as a base and copies in the echo server (I based it on another image):

FROM debian:8.2
MAINTAINER Magnus Therning <magnus@therning.org>

RUN TERM=vt220 apt-get update && \
TERM=vt220 DEBIAN_FRONTEND=noninteractive apt-get -y install \
apt-utils \
dialog \
libgmp10 \
&& true

RUN useradd -G users -m -s /bin/bash myuser && \
echo "root:root" | chpasswd

USER myuser
COPY echosrv /home/myuser/
CMD bash --login

I popped the Dockerfile and the binary into a folder srv/ so I can build the image using

$docker build --rm --tag=nw srv and then started using $ docker run --rm --interactive --tty --name=echo nw /home/myuser/echosrv

## A handy alias

The following alias will turn out to be very handy indeed

$alias docker-pid="docker inspect --format '{{ .State.Pid }}'" ## The network setup The local network is 192.168.1.0/24 and I found an unused address, 192.168.1.199 that I decided to use for my experiment. The gateway is on 192.168.1.1. First create the macvlan device: $ sudo ip link add mybridge link enp0s25 type macvlan mode bridge

Then put it into the network namespace of the running container, and bring it up:

$sudo ip link set netns$(docker-pid echo) mybridge
$sudo nsenter -t$(docker-pid echo) -n ip link set mybridge up

Now the device need its address and the routing has to be set up:

$sudo nsenter -t$(docker-pid echo) -n ip route del default
$sudo nsenter -t$(docker-pid echo) -n ip addr add 192.168.1.199/24 dev mybridge
$sudo nsenter -t$(docker-pid echo) -n ip route add default via 192.168.1.1 dev mybridge

That’s it, now the docker container is reachable on 192.168.1.199. Well, it’s reachable on that ip from any computer on the network except for the host. In order for the host to be able to reach it add another route:

## Example 3: safe key generation, Yesod application

Adding this same approach to a Yesod application is fairly straight-forward, the only two tricks are:

• Put the generated key into the foundation data type
• Use the waiRequest function to get access to the raw request value

A simple working exactly:

#!/usr/bin/env stack
-- stack --resolver lts-3.9 runghc --package yesod-core

{-# LANGUAGE QuasiQuotes           #-}
{-# LANGUAGE TypeFamilies          #-}

import qualified Data.Vault.Lazy as V
import Network.Wai
import Network.Wai.Handler.Warp
import Network.HTTP.Types
import System.Random
import qualified Data.ByteString.Lazy.Char8 as L8
import Yesod.Core

middleware :: V.Key Int -> Middleware
middleware key app req respond = do
-- Generate a random number
value <- randomIO
let vault' = V.insert key value (vault req)
req' = req { vault = vault' }
app req' respond

app :: V.Key Int -> Application
app key req respond =
respond $responseLBS status200 []$ L8.pack str
where
str =
case V.lookup key (vault req) of
Just value -> "Random number is: " ++ show value

data App = App
{ randomKey :: V.Key Int
}

mkYesod "App" [parseRoutes|
/ HomeR GET
|]

instance Yesod App

getHomeR :: Handler Html
getHomeR = do
App key <- getYesod
req <- waiRequest
defaultLayout [whamlet|#{show $V.lookup key (vault req)}|] main :: IO () main = do key <- V.newKey app <- toWaiApp$ App key
run 3000 \$ middleware key app

## Exercise: unsafe key generation, Yesod application

The last example in our matrix would be using unsafePerformIO for generating the key, and using it in a Yesod application. That should be a straightforward modification of what we've already seen, and is left as an exercise to the reader.

## October 19, 2015

### FP Complete

This is a guest blog from Konstantin Zudov, who has been making a number of wonderful enhancements to the Stackage Server website.

# Snapshot badges for packages on Stackage

Stackage Server just got a new feature: snapshot badges. Take a look:

• stack/lts-2:
• stack/lts-3:
• stack/lts (the latest):
• stack/nightly:

Package authors can add the badges to their README.md to tell users in which snapshots the package is present and provide a link to the package page.

Here is an example of how that can be done:

# PackageName

[![packagename on Stackage Nightly](http://stackage.org/package/packagename/badge/nightly)](http://stackage.org/nightly/package/packagename)

In case of stack it would look like:

# Either and (,) in Haskell are not arbitrary

Alternate title: Unnecessary particularity considered harmful

Since I’d rather explain this in O(1) rather than O(twitter) time, this is a brief rundown of why the way type constructors and constructor classes work in Haskell is not arbitrary. The post is not a tutorial on higher-kinded types, constructor classes, or functor. Don’t know these things? I write stuff so you can learn ’em.

First, the data types we’re dealing with:

data Either a b =
Left a
| Right b

-- sorta fake
data (,) a b =
(a, b)

We’ll use Functor to make the point, and Functor looks like this:

class Functor f where
fmap :: (a -> b) -> f a -> f b

Some of the post-FTP drama has included people asserting that the way the Foldable instances for Either and (,) work is arbitrary. Not so. They work on the same principle as the Functor instances:

Prelude> fmap (+1) (Right 1)
Right 2
Prelude> fmap (+1) (Left "blah")
Left "blah"

Prelude> fmap (+1) (0, 0)
(0,1)

The first thing to recognize is that Left and Right in Either mean nothing to your program and similarly the first and second positions in (,) mean nothing in and of themselves. Because type constructors in Haskell work the same way as data constructors and functions in general do, the way their instances work is the only way they could work. Either and (,) will always have one type argument that gets mapped and one that does not. It doesn’t really matter which data constructor that is; we can only benefit by letting the consistent semantics of Haskell pick the type argument for us.

The only useful purpose a Functor for Either can ever have is to have one type which is transformed by the lifted functions and one which is not. If you want to be able to pick arbitrary targets, then you want lenses rather than a typeclass. If you want to able to transform both, then you want Bifunctor.

Note that with bimap in the Bifunctor class you have to provide two functions you’re mapping rather than one because the types a and b could vary and be different types. Even if they are the same type, you can’t write the Functor instance as if they were because the Either and (,) are defined with two distinct type arguments.

If you want a “tuple” of values that were all of the same type…well, go ahead. You can write it yourself:

-- We use this in the book to demonstrate how
-- type constructors and constructor classes
-- work in Haskell, as it happens.
data Pair a =
Pair a a
deriving (Eq, Show)

instance Functor Pair where
fmap f (Pair a a') = Pair (f a) (f a')

Then to see how the Functor for this behaves:

Prelude> fmap (+1) (Pair 1 1)
Pair 2 2
Prelude> fmap show (Pair 1 1)
Pair "1" "1"
Prelude> fmap show (Pair 1 9001)
Pair "1" "9001"

A Functor for (,) can only ever map over one of the fields of the type. It might as well be the one that occurs naturally from the order of arguments to the type constructor (read: functions). length written in terms of Foldable has nothing to do with the contents of the Foldable structure; it has to do with the structure itself. You wouldn’t expect length of a list of lists to measure the length of one or more of the sublists:

Prelude> length [[], []]
2

You would expect it to measure how many cons cells were in the outermost list. Unless you lifted it. If you lifted it, then you could get the measure of all the list values contained within! (this is why we have fmap)

Prelude> fmap length [[], ["lol"]]
[0,1]

Prelude> (fmap . fmap) length [[], ["lol"]]
[[],[3]]

-- Doesn't change for Maybe
Prelude> length (Just "blah")
1
Prelude> fmap length (Just "blah")
Just 4
Prelude> fmap length (Nothing :: Maybe String)
Nothing

Similarly, no matter what food you move around on your plate, length for (,) is never going to do anything but return 1 because there’s always one value of the type you’re folding over with (,). Even if you add type lambdas.

Prelude> length ("blah", "")
1
-- unless we lift it over the tuple structure.
Prelude> fmap length ("blah", "")
("blah",0)
Prelude> fmap length ("blah", "Papuchon")
("blah",8)

Want to map over the left-hand side? Use Bifunctor:

Prelude> import Data.Bifunctor
Prelude> :t first
first :: Bifunctor p => (a -> b) -> p a c -> p b c
Prelude> :t second
second :: Bifunctor p => (b -> c) -> p a b -> p a c

Prelude> first length ("blah", "Papuchon")
(4,"Papuchon")
Prelude> second length ("blah", "Papuchon")
("blah",8)

Or lenses! Whatever you like!

The Functor and Foldable for Either and (,) can only ever do one useful thing. We may as well make it so we know exactly which type is being mapped over by looking at the type. What Functor and Foldable do, how they work, is essentially what the combination of higher kinded types and typeclasses into constructor classes is for. This is their purpose for existing. If you want to address more structure than what Functor/Foldable let you talk about, then use Bifunctor or Bifoldable. If you want to choose arbitrary targets, then use lenses and prisms. There’s no reason to break the consistent and predictable semantics of the language because the (necessary by construction!) Functor instance for Either or (,) appears arbitrary to you. In fact, they’re the complete opposite of arbitrary or contingent because their instances follow directly from how the datatypes are defined. This uniqueness and necessity is why we can have the DeriveFunctor and DeriveFoldable extensions which will generate Functor and Foldable instances knowing only the definition of a datatype.

It doesn’t matter if the definition of Either was:

data Either a b = Left b | Right a

It matters that a default exists and is chosen for the Functor because that’s the only reason to make something Left or Right. Contrary to developer intuitions, Right doesn’t mean “success”. The data constructors of Either are defined by what the Functor/Applicative/etc. instances do.

I’ve used Left to indicate “success” in situations where I want to stop fmap’ing a computation that might fail. It is the picking-of-a-winner that Haskell’s semantics induce that is valuable and not arbitrary. What is arbitrary is what we call left and right and the syntactic position of their type arguments in the type constructor. There’s much less utility in an Either that doesn’t have a Functor with a default target.

Further, they aren’t arbitrary. Following from the definition of arbitrary that Google provided:

based on random choice or personal whim, rather than any reason or system.

We can break it down as follows:

1. Is there a reason the Either Functor works the way it does? Yes, it makes the datatype more useful in that it gives us a biased-choice Functor which is frequently useful regardless of whether the biased-target represents success or not. The way Functor behaves is useful insofar as its only reason for existing is to pick one of the two exclusive choices. There is no reason for programmers to favor the target being Left or Right. Those words mean nothing and word/name-fetishism kills software reuse and modularity.

2. Is there a systematic cause for why the Either Functor works the way it does? Yes, cf. Jones’ work on Gofer dating to 1993/1994. The way the Functor behaves is necessary and follows from how the language works in a natural way. You can make a learner predict what the Either Functor does if you teach them how HKTs and constructor classes work. I’ve done this with learners before. This isn’t surprising if you know Haskell.

### Summary

It does not matter whether one of your types is going to be in the Left or Right data constructor, all that matters is what you want your Functor-target to be. Not having a universal winner for Left or Right being the Functor target is bizarre and counter-productive. You can not and will not ever have a single Functor that lets you pick either/or of Left or Right because a != b.

If you want to map over your “error” value, I have news for you! Right` just became your error value. The names Left and Right mean nothing. The code is what it does. If you want to be able to arbitrarily pick Left, Right or both as a target, what you want is Bifunctor or a prism. It is madness to give programmers an avenue to introduce useless arbitrariness to their code. Preventing the proliferation of meaningless difference is an excellent way for people doing PL to improve a language.

We’ve covered both ways in which the Functor instance is not arbitrary, due to being both necessary and useful. We can also see that the way the Either Functor works is neither random nor based on whim.

I know this site is a bit of a disaster zone, but if you like my writing or think you could learn something useful from me, please take a look at the book I've been writing with my coauthor Julie. There's a free sample available too!