Switch to Tasks + Task

[snowleopard]

@ndmitchell @simonpj I have mixed feelings about this.

Here are the new types:

type Tasks c k v = k -> Maybe (Task c k v)
newtype Task c k v = Task { run :: forall f. c f => (k -> f v) -> f v }

Good:

• The refactoring wasn’t too hard.

• Some functions got simplified. For example:

  -- Before
  dependencies :: Task Applicative k v -> k -> [k]
  dependencies task = maybe [] getConst . task (\k -> Const [k])
  
  -- After
  dependencies :: Task Applicative k v -> [k]
  dependencies task = getConst $ run task (\k -> Const [k])

Bad:

• In many cases the simplification is somewhat misleading. For the above example, we still need to fiddle with Maybe, but just in a different place -- here is a snippet from topological:

  -- Before
  deps k = dependencies task k
  
  -- After
  deps k = maybe [] dependencies (tasks k)

• Task descriptions became noisier. One could introduce a combinator for Just . Task but still it seems harder to read/understand the resulting code because of lambdas with fetch:

  -- Before
  sprsh1 :: Task Applicative String Integer
  sprsh1 fetch "B1" = Just ((+)  <$> fetch "A1" <*> fetch "A2")
  sprsh1 fetch "B2" = Just ((*2) <$> fetch "B1")
  sprsh1 _     _    = Nothing
  
  -- After
  sprsh1 :: Tasks Applicative String Integer
  sprsh1 "B1" = Just $ Task $ \fetch -> ((+)  <$> fetch "A1" <*> fetch "A2")
  sprsh1 "B2" = Just $ Task $ \fetch -> ((*2) <$> fetch "B1")
  sprsh1 _    = Nothing

• Finally, and most unfortunately, I realised that we can't just pass a Task to Buck's process function and hope that it can extract transitive inputs (sources) from it: it really needs Tasks for this! A single Task only allows you to extract information about your immediate dependencies. So if we really want to be able to perform global analysis of the dependency graph inside process we need to pass Tasks to it. And maybe this is what we should do: see #2.

In summary, I'm leaning towards keeping the old abstraction. I don't think splitting into Tasks and Task brings us much, and -- on average -- it seems to lead to less elegant code.

[simonpj]

I’m not bothered by the task descriptions. To me it seems great to say

sprsh1 = mkTasks [ (“B1”, formulaB1)
                 , “B2”, formulaB2), …]

I don’t know what to make of the Buck thing though.

[ndmitchell]

I like it!

• It seems to move complexity around, neither adding nor removing it outside the task definition.
• The new formulation matches my operational intuition - the fact that you have a theorem-for-free that you won't use the dependencies is cute, but also harder to understand. The new formulation is more direct.
• This is step 1 - we haven't switched recursive etc. to pass a Task to the process function. That will bring further simplifications and generalisations (e.g. you can write cloud Excel, which currently reordering can't express). I think this is the big reason we're doing the refactor.
• The complication of tasks seems unimportant - we don't focus on defining concrete tasks in the paper - if we did focus on them I'm sure we'd combine the c Applicative/Monad with a ReaderT, and then you'd not need to care about fetch once more.

[simonpj]

What about the Buck business?

[ndmitchell]

There are two formulations of Buck:

1. The one that looks all the way to the transitive inputs on each node.
2. The one that only looks at direct dependencies, and uses a Merkle tree to get hash information from the transitive inputs.

Our current formulation can only do 2, and we had hoped Task would let us do 1 as well, but we now know it won't, it will be the same power as we currently have. In reality Buck does 2, so 1 is perhaps a more academic exercise anyway (it would have bad O complexity if implemented in real life).

I think Buck is a case of a hoped-for benefit not materialising, but not a big deal overall.

[snowleopard]

Thanks for the comments! I can see you're both in favour of going ahead with this change. I'm still not convinced -- for me, the Buck story was really convincing, but it's gone now.

To respond to some of your comments:

@simonpj:

To me it seems great to say sprsh1 = mkTasks ...

You can still say this with type Tasks c k v = forall f. c f => (k -> f v) -> k -> Maybe (f v). You just need to pick a different mkTasks :: [k, Task c k v] -> Tasks c k v. So, this doesn't seem to be a factor here: you can keep the current implementation (and the paper!), and define a SingleTask -- we might also call it Formula or Compute -- with mkTask :: [k, Compute c k v] -> Task c k v. This doesn't require changing any of the existing abstractions.

@ndmitchell:

The new formulation is more direct.

Yes, I agree with this.

This is step 1 - we haven't switched recursive etc. to pass a Task to the process function. That will bring further simplifications and generalisations

But there is an alternative: pass Tasks to process, which essentially turns it into another build system and our algorithms simply transform one build system into another, as in #2. This approach allows to handle both Buck formulations, so it is more general. It might also be simpler, since we don't need to introduce new types for process (but I haven't yet checked that this works for reordering).

if we did focus on them I'm sure we'd combine the c Applicative/Monad with a ReaderT, and then you'd not need to care about fetch once more.

I'm not sure I know exactly what you mean. Can you show how this would work with sprsh1?

Also, don't forget that if we go ahead with this switch, we'll probably have to translate it to the paper, which might just be a too large revision for reviewers to agree with it. This is hardly a good argument for a technical discussion, but is more of an 'engineering concern' :-)

[ndmitchell]

@snowleopard - shall we discuss over lunch? I'm free from now on.

[snowleopard]

@ndmitchell Good idea -- I'm ready!

[snowleopard]

OK, given the promise of glorious task transformers I'm merging this :)