{"id":671,"date":"2018-03-26T15:27:19","date_gmt":"2018-03-26T14:27:19","guid":{"rendered":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/?p=671"},"modified":"2019-05-02T20:37:23","modified_gmt":"2019-05-02T19:37:23","slug":"the-task-abstraction","status":"publish","type":"post","link":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/the-task-abstraction\/","title":{"rendered":"The Task abstraction"},"content":{"rendered":"

Neil Mitchell, Simon Peyton Jones and I have just finished a paper describing a systematic and executable framework for developing and comparing build systems. The paper and associated code are available here: https:\/\/github.com\/snowleopard\/build<\/a>. The code is not yet well documented and polished, but I’ll bring it in a good shape in April. You can learn more about the motivation behind the project here<\/a>.<\/p>\n

(Update: the paper got accepted to ICFP! Read the PDF<\/a>, watch the talk<\/a>.)<\/p>\n

In this blog post I would like to share one interesting abstraction that we came up with to describe build tasks:<\/p>\n

type<\/span> Task<\/span> c k v =<\/span> forall f.<\/span> c f =><\/span> (k -><\/span> f v) -><\/span> k -><\/span> Maybe<\/span> (f v)<\/pre>\n
A Task<\/span> is completely isolated from the world of compilers, file systems, dependency graphs, caches, and all other complexities of real build systems. It just computes the value of a key k<\/span>, in a side-effect-free way, using a callback of type\u00a0k \u2192 f v<\/span> to find the values of its dependencies. One simple example of a callback is Haskell’s readFile function<\/a>: as one can see from its type FilePath \u2192 IO String<\/span>, given a key (a file path k =\u00a0FilePath<\/span>) it can find its value (the file contents of type v = String<\/span>) by performing arbitrary IO effects (hence,\u00a0f = IO<\/span>). We require task descriptions to be polymorhic in f<\/span>, so that we can reuse them in different computational contexts f<\/span> without rewriting from scratch.<\/p>\n
<\/p>\n
This highly-abstracted type is best introduced by an example. Consider the following Excel spreadsheet (yes, Excel is a build system in disguise):<\/p>\n
A1: 10     B1: A1 + A2\r\nA2: 20     B2: B1 * 2<\/pre>\n
Here cell A1<\/span> contains the value 10<\/span>, cell B1<\/span> contains the formula A1 + A2<\/span>, etc. We can represent the formulae (i.e. build tasks<\/em>) of this spreadsheet with the following task description:<\/p>\n
sprsh1<\/span> ::<\/span> Task<\/span> Applicative<\/span> String<\/span> Integer<\/span>\r\nsprsh1 fetch \"B1\"<\/span> =<\/span> Just<\/span> ((+)<\/span>  <$><\/span> fetch \"A1\"<\/span> <<\/span>*><\/span> fetch \"A2\"<\/span>)\r\nsprsh1 fetch \"B2\"<\/span> =<\/span> Just<\/span> ((*2<\/span>) <$><\/span> fetch \"B1\"<\/span>)\r\nsprsh1 _     _    =<\/span> Nothing<\/span>\r\n<\/pre>\n
We instantiate the type of keys<\/em> k<\/span> with String<\/span> (cell names), and the type of values<\/em> v<\/span> with Integer<\/span> (real spreadsheets contain a wider range of values, of course). The task description sprsh1<\/span> embodies all the formulae of the spreadsheet, but not the input values. Like every Task<\/span>, sprsh1<\/span> is given a callback<\/em> fetch<\/span> and a key. It pattern-matches on the key to see if it has a task description (a formula) for it. If not, it returns Nothing<\/span>, indicating that the key is an input<\/em>. If there is a formula in the cell, it computes the value of the formula, using fetch<\/span> to find the value of any keys on which it depends.<\/p>\n
The definition of Task<\/span> and the above example look a bit mysterious. Why do we require Task<\/span> to be polymorphic in the type constructor f<\/span>? Why do we choose the c = Applicative<\/span> constraint? The answer is that given one task description, we would like to explore many different build systems that can build it and it turns out that each of them will use a different f<\/span>. Furthermore, we found that constraints c<\/span> classify build tasks in a very interesting way:<\/p>\n