"I just don't want to hear the word 'cunt' shouted repeatedly at 3am every night any more. I don't think that's unreasonable."

One infuriating KPI we're measured on is the final question a resident is asked once their case is closed: "Are you happy with the outcome of your case?" Because unless you evict the problem neighbor within a fortnight, erect a security wall around the complainant's house manned by armed guards, and bake them a cake, the answer will almost certainly be no.

Years of interacting with class A drug users has shown me that they really don't want to be out hustling to make enough money for their next score of diluted heroin. They want to sit at home, take drugs and when those drugs wear off, take some more. You may view this as a wasted life, and you may well be right, but here's the thing: they are going to do this anyway, whether we decide to criminalize them or not. If, after a lengthy period of honest, mature drug education across the country via schools, further education, government advertising and so on, class A drugs were made legally available on prescription to adults via pharmacies, the vast majority of users would pick up their prescriptions, go home, take their drugs and leave everyone else alone. They couldn't be arsed to break into your car if they didn't have to.

The best way to describe going to court is that it's like paying a visit to a run-down hospital where nobody gets better.

The old form for monthly one-to-ones used to have two questions "What did you do over the last month?" and "What do you plan to do in the next month?" and my line manager at the time seemed unimpressed when I answered "my job" to both.

The starting point Today, I ll take you on a another little walk through the land of program transformations. Let s begin with a simple binary tree, with value of unknown type in the leaves, as well as the canonical map function:

data T a = L a   B (T a) (T a)
map1 :: (a -> b) -> T a -> T b
map1 f (L x) = L (f x)
map1 f (B t1 t2) = B (map1 f t1) (map1 f t2)

As you can see, this map function is using the program stack as it traverses the tree. Our goal is now to come up with a map function that does not use the stack! Why? Good question! In Haskell, there wouldn t be a strong need for this, as the Haskell stack is allocated on the heap, just like your normal data, so there is plenty of stack space. But in other languages or environments, the stack space may have a hard limit, and it may be advised to not use unbounded stack space. That aside, it s a fun exercise, and that s sufficient reason for me. (In the following, I assume that tail-calls, i.e. those where a function end with another function call, but without modifying its result, do not actually use stack space. Once all recursive function calls are tail calls, the code is equivalent to an imperative loop, as we will see.)

Think? We could now just stare at the problem (rather the code), and try to come up with a solution directly. We d probably think ok, as I go through the tree, I have to remember all the nodes above me so I need a list of those nodes and for each of these nodes, I also need to remember whether I am currently processing the left child, and yet have to look at the right one, or whether I am done with the left child so what do I have to remember about the current node ? ah, my brain spins already. Maybe eventually I figure it out, but why think when we can derive the solution? So let s start with above map1, and rewrite it, in several, mechanical, steps into a stack-less, tail-recursive solution.

Go! Before we set out, let me rewrite the map function using a local go helper, as follows:

map2 :: forall a b. (a -> b) -> T a -> T b
map2 f t = go t
  where
    go :: T a -> T b
    go (L x) = L (f x)
    go (B t1 t2) = B (go t1) (go t2)

This transformation (effectively the static argument transformation ) has the nice advantage that we do not have to pass f around all the time, and that when we copy the function, I only have to change the top-level name, but not the names of the inner functions. Also, I find it more aesthetically pleasing.

CPS A blunt, effective tool to turn code that is not yet using tail-calls into code that only uses tail-calls is use continuation-passing style. If we have a function of type -> t, we turn it into a function of type -> (t -> r) -> r, where r is the type of the result we want at the very end. This means the function now receives an extra argument, often named k for continuation, and instead of returning some x, the function calls k x. We can apply this to our go function. Here, both t and r happen to be T b; the type of finished trees:

map3 :: forall a b. (a -> b) -> T a -> T b
map3 f t = go t (\r -> r)
  where
    go :: T a -> (T b -> T b) -> T b
    go (L x) k  = k (L (f x))
    go (B t1 t2) k  = go t1 (\r1 -> go t2 (\r2 -> k (B r1 r2)))

Note that when initially call go, we pass the identity function (\r -> r) as the initial continuation. Alas, suddenly all function calls are in tail position, and this codes does not use stack space! Technically, we are done, although it is not quite satisfying; all these lambdas floating around obscure the meaning of the code, are maybe a bit slow to execute, and also, we didn t really learn much yet. This is certainly not the code we would have writing after thinking hard .

Defunctionalization So let s continue rewriting the code to something prettier, simpler. Something that does not use lambdas like this. Again, there is a mechanical technique that can help it. It likely won't make the code prettier, but it will get rid of the lambdas, so let s do that an clean up later. The technique is called defunctionalization (because it replaces functional values by plain data values), and can be seen as a form of refinement. Note that we pass around vales of type (T b -> T b), but we certainly don t mean the full type (T b -> T b). Instead, only very specific values of that type occur in our program, So let us replace (T b -> T b) with a data type that contains representatives of just the values we actually use.

1. We find at all values of type (T b -> T b). These are:
   • (\r -> r)
   • (\r1 -> go t2 (\r2 -> k (B r1 r2)))
   • (\r2 -> k (B r1 r2))
2. We create a datatype with one constructor for each of these:

    data K = I   K1   K2

   (This is not complete yet.)
3. We introduce an interpretation function that turns a K back into a (T b -> T b):

   eval :: K -> (T b -> T b)
   eval = (* TBD *)

4. In the function go, instead of taking a parameter of type (T b -> T b), we take a K. And when we actually use the continuation, we have to turn the K back to the function using eval:

   go :: T a -> K a b -> T b
   go (L x) k  = eval k (L (f x))
   go (B t1 t2) k = go t1 K1

   We also do this to the code fragments identified in the first step; these become:
   • (\r -> r)
   • (\r1 -> go t2 K2)
   • (\r2 -> eval k (B r1 r2))
5. Now we complete the eval function: For each constructor, we simply map it to the corresponding lambda from step 1:

   eval :: K -> (T b -> T b)
   eval I = (\r -> r)
   eval K1 = (\r1 -> go t2 K2)
   eval K2 = (\r2 -> eval k (B r1 r2))

6. This doesn t quite work yet: We have variables on the right hand side that are not bound (t2, r1, k). So let s add them to the constructors K1 and K2 as needed. This also changes the type K itself; it now needs to take type parameters.

This leads us to the following code:

data K a b
  = I
    K1 (T a) (K a b)
    K2 (T b) (K a b)
map4 :: forall a b. (a -> b) -> T a -> T b
map4 f t = go t I
  where
    go :: T a -> K a b -> T b
    go (L x) k  = eval k (L (f x))
    go (B t1 t2) k  = go t1 (K1 t2 k)
    eval :: K a b -> (T b -> T b)
    eval I = (\r -> r)
    eval (K1 t2 k) = (\r1 -> go t2 (K2 r1 k))
    eval (K2 r1 k) = (\r2 -> eval k (B r1 r2))

Not really cleaner or prettier, but everything is still tail-recursive, and we are now working with plain data.

We like lists To clean it up a little bit, we can notice that the K data type really is just a list of values, where the values are either T a or T b. We do not need a custom data type for this! Instead of our K, we can just use the following, built from standard data types:

type K' a b = [Either (T a) (T b)]

Now I replace I with [], K1 t2 k with Left t2 : k and K2 r1 k with Right r1 : k. I also, very suggestively, rename go to down and eval to up:

map5 :: forall a b. (a -> b) -> T a -> T b
map5 f t = down t []
  where
    down :: T a -> K' a b -> T b
    down (L x) k  = up k (L (f x))
    down (B t1 t2) k  = down t1 (Left t2 : k)
    up :: K' a b -> T b -> T b
    up [] r = r
    up (Left  t2 : k) r1 = down t2 (Right r1 : k)
    up (Right r1 : k) r2 = up k (B r1 r2)

At this point, the code suddenly makes more sense again. In fact, I can try to verbalize it:

As we traverse the tree, we have to remember for all parent nodes, whether there is still something Left to do when we come back to it (so we remember a T a), or if we are done with that (so we have a T b). This is the list K' a b. We begin to go down the left of the tree (noting that the right siblings are still left to do), until we hit a leaf. We transform the leaf, and then go up. If we go up and hit the root, we are done. Else, if we go up and there is something Left to do, we remember the subtree that we just processed (as that is already in the Right form), and go down the other subtree. But if we go up and there is nothing Left to do, we put the two subtrees together and continue going up.

Quite neat!

The imperative loop At this point we could stop: the code is pretty, makes sense, and has the properties we want. But let s turn the dial a bit further and try to make it an imperative loop. We know that if we have a single tail-recursive function, then that s equivalent to a loop, with the function s parameter turning into mutable variables. But we have two functions! It turns out that if you have two functions a -> r and b -> r that have the same return type (which they necessarily have here, since we CPS-converted them further up), then those two functions are equivalent to a single function taking a or b , i.e. Either a b -> r. This really nothing else than the high-school level algebra rule of r^a r^b = r^{a + b}. So (after reordering the arguments of down to put T b first) we can rewrite the code as

map6 :: forall a b. (a -> b) -> T a -> T b
map6 f t = go (Left t) []
  where
    go :: Either (T a) (T b) -> K' a b -> T b
    go (Left (L x))     k        = go (Right (L (f x))) k
    go (Left (B t1 t2)) k        = go (Left t1) (Left t2 : k)
    go (Right r)  []             = r
    go (Right r1) (Left  t2 : k) = go (Left t2) (Right r1 : k)
    go (Right r2) (Right r1 : k) = go (Right (B r1 r2)) k

Do you see the loop yet? If not, maybe it helps to compare it with the following equivalent imperative looking pseudo-code:

mapLoop :: forall a b. (a -> b) -> T a -> T b
mapLoop f t  
  var node = Left t;
  var parents = [];
  while (true)  
    switch (node)  
      Left (L x) -> node := Right (L (f x))
      Left (B t1 t2) -> node := Left t1; parents.push(Left t2)
      Right r1 ->  
        if (parents.len() == 0)  
          return r1;
          else  
          switch (parents.pop())  
            Left t2  -> node := Left t2; parents.push(Right r1);
            Right r2 -> node := Right (B r1 r2)
           
         
       
     
   
 

Conclusion I find it enlightening to see how apparently very different approaches to a problem (recursive, lazy functions and imperative loops) are connected by a series of rather mechanical transformations. When refactoring code, it is helpful to see if one can conceptualize the refactoring as one of those mechanical steps (refinement, type equivalences, defunctionalization, cps conversion etc.) If you liked this post, you might enjoy my talk The many faces of isOrderedTree, which I have presented at MuniHac 2019 and Haskell Love 2020.

Laura, who lives in Chicago and works as a special ed teacher, never wants to see her friends, or date, or cook she's so tired, she just wants to melt into the couch. "But then I can't focus on what I'm watching, and end up unfocused again, and not completely relaxing," she explained. "Here I am telling you I don't even relax right! I feel bad about feeling bad! But by the time I have leisure time, I just want to be alone!"

Even after watching our parents get shut out, fall from, or simply struggle anxiously to maintain the American Dream, we didn't reject it. We tried to work harder, and better, more efficiently, with more credentials, to achieve it.

In writing that article, and this book, I haven't cured anyone's burnout, including my own. But one thing did become incredibly clear. This isn't a personal problem. It's a societal one and it will not be cured by productivity apps, or a bullet journal, or face mask skin treatments, or overnight fucking oats. We gravitate toward those personal cures because they seem tenable, and promise that our lives can be recentered, and regrounded, with just a bit more discipline, a new app, a better email organization strategy, or a new approach to meal planning. But these are all merely Band-Aids on an open wound. They might temporarily stop the bleeding, but when they fall off, and we fail at our new-found discipline, we just feel worse.

Millennials have been denigrated and mischaracterized, blamed for struggling in situations that set us up to fail. But if we have the endurance and aptitude and wherewithal to work ourselves this deeply into the ground, we also have the strength to fight. We have little savings and less stability. Our anger is barely contained. We're a pile of ashes smoldering, a bad memory of our best selves. Underestimate us at your peril: We have so little left to lose.

One additional and recent change was the accomodation of a recent CRAN Policy change to not allow gcc or clang to mess with diagnostic messages. A word of caution: this may make your compilation of packages using RcppEigen very noisy so consider adding -Wno-ignored-attributes to the compiler flags added in your ~/.R/Makevars.

-Wno-deprecated-declarations -Wno-parentheses -Wno-ignored-attributes -Wno-unused-function

Changes in RcppEigen version 0.3.3.9.1 (2020-12-17)

• Upgraded to Eigen 3.3.9 (Dirk in #92 fixing #91).
• Added GitHub Actions CI using run.sh from r-ci (Dirk)

This post by Dirk Eddelbuettel originated on his Thinking inside the box blog. Please report excessive re-aggregation in third-party for-profit settings.

1. First, the LTS work necessarily had an impact on other Debian teams that made the project possible (security team, DSA, buildd, ftpmasters, debian-www mainly) and we wanted to be able to give back to those teams by funding improvements to their infrastructure.
2. We have always allowed paid contributors to go beyond just preparing security updates for the LTS release. They can pick tasks that improve the LTS project at large (we try to collect such tasks here: https://salsa.debian.org/lts-team/lts-extra-tasks/-/issues) but they should not go over 25% of their allocated monthly hours so this limits their ability to tackle bigger projects and we would like to be able to tackle bigger projects that can have a meaningful impact on the LTS project and/or Debian in general.

No comment Liked this article? Click here. My blog is Flattr-enabled.

Issues with Farm Laws While I have written about the farm laws a bit sometime back. The issue is still in the nation s eye and that is due to the policies which have been done. I have been reading up on it quite a bit and also have been seeing what has been happening in here and now. The problems are with the three bills themselves which I have shared as below Click to access farmers-produce-trade-and-commerce-promotion-and-facilation-bill.pdf Click to access farmers-empowerment-and-protection-bill.pdf Click to access essential-commodities-bill-2020.pdf Biggest issue with the laws While there are many issues with the laws themselves but for me the biggest issue is that the fundamental right of the farmer to get justice via civil courts has been railroaded. From the laws itself. Standard disclaimer not a lawyer, please consult one for any issues per-se.

Farmers-produce-trade-and-commerce (promotion and facilitation-bill) 2020 Page 4 Chapter 3 Section 8 (1)8. (1) In case of any dispute arising out of a transaction between the farmer and a trader under section 4, the parties may seek a mutually acceptable solution through conciliation by filing an application to the Sub-Divisional Magistrate who shall refer such dispute to a Conciliation Board to be appointed by him for facilitating the binding settlement of the dispute. (2) Every Board of Conciliation appointed by the Sub-Divisional Magistrate under sub-section (1), shall consist of a chairperson and such members not less than two and not more than four, as the Sub-Divisional Magistrate may deem fit.10 (5) If the parties to the transaction under sub-section (1) are unable to resolve the dispute within thirty days in the manner set out under this section, they may approach the Sub-Divisional Magistrate concerned who shall be the Sub-Divisional Authority for settlement of such dispute. (8) Any party aggrieved by the order of the Sub-Divisional Authority may prefer an appeal before the Appellate Authority (Collector or Additional Collector nominated by the Collector) within thirty days of such order who shall dispose of the appeal within thirty days from the date of filing of such appeal. 10. (1) Any person aggrieved by an order under section 9 may, prefer an appeal within sixty days from the date of such order, to an officer not below the rank of Joint Secretary to the Government of India to be nominated by the Central Government for this purpose: Page 6 of the bill. 13. No suit, prosecution or other legal proceedings shall lie against the Central Government or the State Government, or any officer of the Central Government or the State Government or any other person in respect of anything which is in good faith done or intended to be done under this Act or of any rules or orders made thereunder. Page 7 of the bill, 15. No civil court shall have jurisdiction to entertain any suit or proceedings in respect of any matter, the cognizance of which can be taken and disposed of by any authority empowered by or under this Act or the rules made thereunder. Now the same laws have been reiterated for the farmers (Empowerment and Protection) Agreement on Price Assurance and Farm Services Bill, 2020. The problem is that too much power is being put into the hands of the executive. All the three, whether it is SDM (Sub-Divisional Magistrate) , the Appellate Authority or the Government Secretary directly are subservient to the whims and fancies of the Central Govt. They after all get their salaries from the Govt. itself. So there will be no independent oversight to any injustices done to the farmer. The third bill i.e. the Essential Commodities Bill, 2020 does away with stock limits on traders and big players like Adani and Ambani. This means that both these players can take and keep produce at their end thereby forcing consumers like you and me who at the retail end would have to pay higher prices for fruits and vegetables while from the producer they will take at the lowest price possible. While I have shared is just one of the points. That is the reason why even the Supreme Court bar association which almost never takes part in politics has been forced to take sides with the farmers. In many ways, one is forced to remember the Emergency Update 11/12/20 Came across this article on the wire which tells how everybody s rights, not just the farmer s rights are being shod over. I think it depicts correctly the signs of time to come. While arguing on SM, also came to know about Article 300 (1), thanks to Sachin Kumar which shows multiple instances where Government was sued because somebody was working in official capacity and did mistakes, malafide or otherwise and it was the state who was made to pay. FWIW, today farmers from Maharashtra, my state arrived at Delhi border where they were also kept at bay. I did come across an infographic which shows how the various states have fared. Most tellingly, is the state of Bihar. It was in 2006 (one of the most backward states) where APMC was taken off. While others have tried to paint a flattering picture of Bihar, they have failed to share that in the interim 15 odd years, there hasn t been any sort of infrastructure created for farmers which is the reason it is still the lowest earner. These are the last available figures we have about the farmer s income. From 2014 to 2020 there hasn t been any update.

Situation Assessment Survey of Agricultural Household 2013 Copyright GOI,

This concludes just one portion of the bill. I will take other parts of the bill. I may dwell on some other parts as and when I have the time. A cartoon which depicts the current issue

I stand with farmers Copyright Sanitary Panels

Too much democracy Amitabh Kant Yesterday, the Niti Aayog chief Amitabh Kant remarked that we are too much of a democracy at an event called for Atmanirbhar Bharat which is basically a coinage for import substitution. Whether this is desirable or not I have argued and if needed will re-argue the same later as well. What is and was interesting were the gentleman s context, the media reactions and our overall Democracy Index which has been going downhill for quite some years. Now the gentleman who is the Niti Aayog chief and who is supposed to have the ear of the Prime Minister had opined it in an event organized by Swarajya Magazine (a far-right magazine) known to be Islamophobic and all things undemocratic. It has been a target of defundthehate campaign and with good reason. But that s a different story altogether. His full statement was as below

Tough reforms are very difficult in the Indian context, as we are too much of a democracy but the government has shown courage and determination in pushing such reforms across sectors, including mining, coal, labour and agriculture. Niti Aayog chief. The upper quotation remarks and the statement has been from the article in Indian Express which I have linked to. I have archived it as a pdf just in case the link goes dead. Yesterday, after the statement became viraled, tweets of media houses which shared the tweet suddenly become unavailable. Seems too much democracy, became too little democracy all of a sudden. I think Mr. Amitabh Kant didn t visualize as the opposition as well as most people who are on Twitter to share their opinion on the same. Few examples

Too much Democracy copyright Satish Acharya

Too much democracy Illustration and Copyright Alok

Sterlite protest 13 dead, 100 injured Copyright Business Standard too much democracy

Erosion of Democracy V-dem institute Copyright The Hindu Web Team

The last one requires a bit more information. This comes from V-Dem Institute which is an independent research institute based out of Department of Political Science, University of Gothenburg, Sweden. I am gonna leave the methods they use for another day as the blog post itself has become rather big/large. Apart from that is the Economists own Democracy Index -2019 Click to access democracy-index-2019.pdf Now for many people, both the V-Dem report and the Economist Index are some sort of attack against India. Doesn t matter that in V-Dem 200+ countries have been taken a variety of indicators and data or the Economist which has data from 150+- countries. Somehow India is supposed to be bigger than all these countries, they do think that other countries data specifically our neighbor China or any other neighbor, those are all accurate. How the dissonance is, has to be gauged from statements of various people. Update 11/12/20 Sadly, the newest V-Dem report marks India as getting into authoritarianism. Gag on Press and Media owners I had shared about the gag on the press especially with respect to western media or reports or anything. This news made its way to straitstimes which normally covers a wide-range of stories covering East Asia vis-a-vis India/South-East Asia. What has also been a big worry that most of the media has been in the hands of a few people. Caravan ran a story on the same in 2016, it has been four years, god only knows what the current situation might be. Any wonder that there is dearth of investigative journalism in India.

India media ownership 2016 Copyright Caravan

Incidentally, a reporter called Akarshan Uppal, who is a reporter on a channel called IBN24 had showecased just few days back how Adani has got land which was shot down for land change use in 2017 to 2020 around 100 acres. There seem to be very less details as to how the land was acquired, whose land it was etc. etc. The reporter was supposedly following a story on drugs on which he was attacked and is now lying in hospital.

Akarshan Uppal Reporter, IBN24 Copyright IBN24

While it would take a whole article/blog post to talk about either Adani or Ambani, in the recent case, the land that has been taken over by Adani is 100 acres and there are private rail lines. And all of this was secret till few days back. The place where these massive godowns/silos have been made are Panipat s Jondhan Kalan and Naultha villages in Haryana. This is Adani AgiLogistics. Almost 7 odd companies have registered and come up in the last couple of years. As can be seen, almost all have come up within the last 2-3 years. Seems to be a lot of coincidence, isn t it?

Personal Anecdote on Data Collection and child marriages in India.

Around 1995 -96 when Internet had started to become a thing in India, there had been quite a few non-profits which were working on various issues. One of those which I initially came in contact with and which I found to be a bit absurd was non-profit which was working in the field of women against Violence. Now it is and was not the concept or the idea which was absurd to me, it was what these women were doing. Instead of the traditional ways in which you counsel women and try and figure out issues, these women were collecting data points from newspapers and magazines. This was way way before data science became a thing in India. They had their own structure where a story about violence against women which would be above the fold would be 5 points, the one below 2.5 points, in inner pages, it would be less and less. Patriarchy at that time was so strong, even today is but at that time it was such, that it felt a waste of time. I did consult them but never said that but did privately feel the above. In hindsight, they were doing the right thing and yet even today crimes against women goes unreported and is suppressed by both State and Central Governments as well as NCRB (National Crime Records Bureau). Interestingly, just few days back, the case against M.J. Akbar by Priya Ramani had taken a back seat and the defamation case by M.J. Akbar was taken forward. Even then, Priya Ramani s counsel s arguments were such that the court wound up in half an hour when they were expecting to do a whole day hearing. The next hearing would be happening today which I will look at in few hours from now. Why Priya Ramani was singled out rather than other tweets may probably be because she is an NRI and most NRI s usually do not want to be part of the bureaucratic Indian court system. This is also the reason that most companies from outside India especially those who are into startups prefer to change ownership, IPR etc. to their own or any country outside India which does make a loss to the exchequer. But this again is a story for another day. At the end, while I did not want to end on a negative note, it seems in many ways status-quo remains. For e.g. 2 years back, a BJP candidate (part of the ruling dispensation) had made a controversy saying that if they win the police won t interfere in child marriages. This is and was in Rajasthan where they have been trying to eradicate it forever. Till date, neither the NHRC (National Human Rights Commission) nor NCW (National Commission for Women) has taken cognizance of the statement. This is our state of democracy.

The need for case names Consider the following Coq proof, right out of the respected Software Foundations book, Chapter Inductively Defined Propositions (and slightly simplified):

Lemma star_app: forall T (s1 s2 : list T) (re : reg_exp T),
  s1 =~ Star re ->
  s2 =~ Star re ->
  s1 ++ s2 =~ Star re.
Proof.
  intros T s1 s2 re H1.
  remember (Star re) as re'.
   generalize dependent s2.
  induction H1.
  - (* MEmpty *) discriminate.
  - (* MChar *) discriminate.
  - (* MApp *) discriminate.
  - (* MUnionL *) discriminate.
  - (* MUnionR *) discriminate.
  - (* MStar0 *)
    injection Heqre' as Heqre''. intros s H. apply H.
  - (* MStarApp *)
    injection Heqre' as Heqre''.
    intros s3 H1. rewrite <- app_assoc.
    apply MStarApp.
    + apply H1_.
    + apply IHexp_match2.
      * rewrite Heqre''. reflexivity.
      * apply H1.
Qed.

This is a very typical example for a proof by induction over an inductively defined relation (in this case, the relations s =~ re which indicates that the string s matches the regular expression re): After some preparation, the invocation of a tactic like induction (could also be inversion or others) creates a number of new goals, one of for each rule of the relation. Then the modern(!) Coq user uses proof bullets to focus the goals, one after another, in order, to solve them. We can see from this example that proof bullets (which were a big improvement) are not quite satisfactory, and the author of this proof felt the need to annotate each subproof with the case it corresponds to. But these are mere comments! This is unsatisfactory, as there is nothing keeping them correct as my proof changes. And anyone who came to Coq from Isabelle is just flabbergasted that the state of art in Coq is still at that level So, wouldn t it be great if

• I could focus goals by their name (e.g. MEmpty)
• Focus them in any order (so that refactoring of my data types do not break my proofs)
• This even worked when simultaneously inducting over or inverting multiple relations?

Simulating named goals in Coq Well, with a few tricks we can! It just takes three simple steps:

1. I load a small file full of hacks (explained below):

   Require Import NamedCases.

2. This allows me to prefix the type of the constructors of the inductive relations (i.e. the rules of the relation) with case <name>, , as follows:

   Reserved Notation "s =~ re" (at level 80).
   Inductive exp_match  T  : list T -> reg_exp T -> Prop :=
       MEmpty:
       case empty,
       [] =~ EmptyStr
       MChar:
       case char,
       forall x,
       [x] =~ (Char x)
       MApp:
       case app,
       forall s1 re1 s2 re2
       (H1 : s1 =~ re1)
       (H2 : s2 =~ re2),
       (s1 ++ s2) =~ (App re1 re2)
       MUnionL:
       case union_l,
       forall s1 re1 re2
       (H1 : s1 =~ re1),
       s1 =~ (Union re1 re2)
       MUnionR:
       case union_r,
       forall re1 s2 re2
       (H2 : s2 =~ re2),
       s2 =~ (Union re1 re2)
       MStar0:
       case star0,
       forall re,
       [] =~ (Star re)
       MStarApp:
       case star_app,
       forall s1 s2 re
       (H1 : s1 =~ re)
       (H2 : s2 =~ (Star re)),
       (s1 ++ s2) =~ (Star re)
     where "s =~ re" := (exp_match s re).

   This is the definition from the Software Foundations book; only the case <name>, lines are added.
3. Now I can change the proof: After the induction tactic I use ; name_cases to name the cases, and then I can use the relatively new named goal focusing feature ([name]: , which I suggested two years ago, and was implemented by Th o Zimmermann) to focus a specific case:

   Lemma star_app2: forall T (s1 s2 : list T) (re : reg_exp T),
     s1 =~ Star re ->
     s2 =~ Star re ->
     s1 ++ s2 =~ Star re.
   Proof.
     intros T s1 s2 re H1.
     remember (Star re) as re'.
      generalize dependent s2.
     induction H1; name_cases.
     [empty]:  
        discriminate.
      
     [char]:  
        discriminate.
      
     [app]:  
        discriminate.
      
     [unionL]:  
        discriminate.
      
     [unionR]:  
       discriminate.
      
     [star0]:  
       injection Heqre' as Heqre''. intros s H. apply H.
      
     [starApp]:  
       injection Heqre' as Heqre''.
       intros s3 H1. rewrite <- app_assoc.
       apply MStarApp; clear_names.
       + apply H1_.
       + apply IHexp_match2.
         * rewrite Heqre''. reflexivity.
         * apply H1.
       
   Qed.

   The comments have turned into actual names!

Goal focusing is now just much more reliable. For example, let me try to discharge the boring cases by using ; try discriminate after the induction. This means there are suddenly only two goals left. With bullets, the first bullet would now suddenly focus a different goal, and my proof script would likely fail somewhere. With named goals, I get a helpful error message No such goal: empty and I can t even enter the first subproof. So let me delete these goals and, just to show off, focus the remaining goals in the wrong order:

Lemma star_app: forall T (s1 s2 : list T) (re : reg_exp T),
  s1 =~ Star re ->
  s2 =~ Star re ->
  s1 ++ s2 =~ Star re.
Proof.
  intros T s1 s2 re H1.
  remember (Star re) as re'.
   generalize dependent s2.
  induction H1; name_cases; try discriminate.
  [starApp]:  
    injection Heqre' as Heqre''.
    intros s3 H1. rewrite <- app_assoc.
    apply MStarApp; clear_names.
    + apply H1_.
    + apply IHexp_match2.
      * rewrite Heqre''. reflexivity.
      * apply H1.
    
  [star0]:  
    injection Heqre' as Heqre''. intros s H. apply H.
   
Qed.

I did not explain the clear_names tactic yet that I had to use after apply MStarApp. What I am showing here is a hack, and it shows these case names are extra hypothesis (of a trivially true type CaseName), and this tactic gets rid of it.

Even better than Isabelle The above even works when there are multiple inductions/inversions involved. To give an example, let s introduce another inductive predicate, and begin proving a lemma that one can do by induction on one and inversion on the other predicate.

Inductive Palindrome  T  : list T -> Prop :=
  EmptyPalin:
  case emptyP,
  Palindrome []
  SingletonPalin:
  case singletonP,
  forall x,
  Palindrome [x]
  GrowPalin:
  case growP,
  forall l x,
  Palindrome l -> Palindrome ([x] ++ l ++ [x])
.
Lemma palindrome_star_of_two:
  forall T (s : list T) x y,
  Palindrome s -> s =~ Star (App (Char x) (Char y)) ->
  s = [] \/ x = y.
Proof.
  intros T s x y HPalin HRe.
  induction HPalin; inversion HRe; name_cases.

At this point we have four open goals. Can you tell why there are four, and which ones they are? Luckily, Show Existentials will tell us their names (and Coq 8.13 will just show them in the proof state window). These names not only help us focus the goal in a reliable way; they even assist us in understanding what goal we have to deal with. For example, the last goal arose from the GrowP rule and the StarApp rule. Neat!

  [emptyP_star0]:  
    left. reflexivity.
   
  [emptyP_starApp]:  
     left. reflexivity.
   
  [singletonP_starApp]:  
    inversion HRe; clear HRe.
    inversion H5; clear H5.
    inversion H10; clear H10.
    inversion H11; clear H11.
    subst.
    inversion H3.
   
 [growP_starApp]:  
    admit. (* I did not complete the proof *)
  

Under the hood (the hack) The above actually works, but it works with a hack, and I wish that Coq s induction tactic would just do the right thing here. I hope eventually this will be the case, and this section will just be curiosity but until, it may actually be helpful.

1. The trick¹ is to leave markers in the proof state. We use a dedicate type CaseName, and a hypothesis name : CaseName indicates that this goal arose from the that case.

   Inductive CaseName := CaseNameI.

   With this, we can write StarApp: forall (starApp : CaseName), to name this case.
2. For a little bit of polish, we can introduce notation for that:

   Notation "'case' x , t" := (forall  x : CaseName , t) (at level 200).

   This allows us to use the syntax you saw above.
3. To easily discharge these CaseName assumptions when using the introduction forms, I wrote these tactics:

   Ltac clear_names := try exact CaseNameI.
   Ltac named_constructor  := constructor; [ exact CaseNameI   idtac .. ].
   Ltac named_econstructor := econstructor; [ exact CaseNameI   idtac .. ].

4. Finally I wrote the tactic name_cases. What it does is relatively simple:

   For each subgoal: Take all hypotheses of type CaseName, concatenate their names, change the name of the current goal to that, and clear these hypotheses

   Unfortunately, my grasp of Coq tactic programming is rather rudimentary, and the only way I manged to solve this is a horrible monster of Ltac2, including hand-rolled imperative implementations of string concatenation and a little nested Ltac1 tactic within. You have been warned:

   From Ltac2 Require Import Ltac2.
   From Ltac2 Require Option.
   Set Default Proof Mode "Classic".
   Ltac name_cases := ltac2:(
     (* Horribly manual string manipulations. Does this mean I should
        go to the Ocaml level?
     *)
     let strcpy s1 s2 o :=
       let rec go := fun n =>
         match Int.lt n (String.length s2) with
           true => String.set s1 (Int.add o n) (String.get s2 n); go (Int.add n 1)
           false => ()
         end
       in go 0
     in
     let concat := fun s1 s2 =>
       let l := Int.add (Int.add (String.length s1) (String.length s2)) 1 in
       let s := String.make l (Char.of_int 95) in
       strcpy s s1 0;
       strcpy s s2 (Int.add (String.length s1) 1);
       s
     in
     Control.enter (let rec go () :=
       lazy_match! goal with
         [ h1 : CaseName, h2 : CaseName  - _ ] =>
         (* Multiple case names? Combine them (and recurse) *)
         let h := concat (Ident.to_string h1) (Ident.to_string h2) in
         Std.clear [h1; h2];
         let h := Option.get (Ident.of_string h) in
         assert ($h := CaseNameI);
         go ()
         [ _ : CaseName  - _ ] =>
         (* A single case name? Set current goal name accordingly. *)
         ltac1:(
           (* How to do this in ltac2? *)
           lazymatch goal with
             [ H : CaseName  - _ ] => refine ?[H]; clear H
           end
         )
         [  - _ ] =>
         Control.backtrack_tactic_failure "Did not find any CaseName hypotheses"
       end
     in go)
   ).

   If someone feels like re-implementing this in a way that is more presentable, I ll be happy to update this code (and learn something along the way

That s all it takes!

Conclusion With some mild hackery, we can get named cases in Coq, which I find indispensable in managing larger, evolving proofs. I wonder why this style is not more common, and available out of the box, but maybe it is just not known well enough? Maybe this blog post can help a bit here.

---

1. I have vague recollections of seeing at least parts of this trick on some blog some years ago, and I do not claim originality here.

• start from ubuntu:21.04 to be able to install g++-11 later
• install the software-properties-common package to be able to add a PPA
• (plus a few more packages to deal with the repository signing key)
• run the sudo add-apt-repository ppa:ubuntu-toolchain-r/volatile command to add the volatile packages PPA
• install g++-11 (along with, for good measure) gcc-11 and gfortran-11
• use update-alternative (a clever Debian/Ubuntu command) to make version 11 the default
• install R itself (via r-base-core) which we simply take from the distro as 21.04 is by construction very recent
• install Rcpp via the r-cran-rcpp binary which covers all dependencies for the package in question

edd@rob:~/git/rcpptoml(master)$ docker run --rm -ti -v $PWD:/mnt -w /mnt rocker/r-edge:gcc-11 g++ --version
g++ (Ubuntu 11-20201128-0ubuntu2) 11.0.0 20201128 (experimental) [master revision fb6b29c85c4:a331ca6194a:e87559d202d90e614315203f38f9aa2f5881d36e]
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

edd@rob:~/git/rcpptoml(master)$ 
edd@rob:~/git/rcpptoml(master)$ docker run --rm -ti -v $PWD:/mnt -w /mnt rocker/r-edge:gcc-11 R CMD INSTALL RcppTOML_0.1.7.tar.gz
* installing to library  /usr/local/lib/R/site-library 
* installing *source* package  RcppTOML  ...
** using staged installation
** libs
g++ -std=gnu++11 -I"/usr/share/R/include" -DNDEBUG -I../inst/include/ -DCPPTOML_USE_MAP -I'/usr/lib/R/site-library/Rcpp/include'    -fpic  -g -O2 -fdebug-prefix-map=/build/r-base-Fuvi9C/r-base-4.0.3=. -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 -g  -c RcppExports.cpp -o RcppExports.o
g++ -std=gnu++11 -I"/usr/share/R/include" -DNDEBUG -I../inst/include/ -DCPPTOML_USE_MAP -I'/usr/lib/R/site-library/Rcpp/include'    -fpic  -g -O2 -fdebug-prefix-map=/build/r-base-Fuvi9C/r-base-4.0.3=. -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 -g  -c parse.cpp -o parse.o
g++ -std=gnu++11 -shared -L/usr/lib/R/lib -Wl,-Bsymbolic-functions -Wl,-z,relro -o RcppTOML.so RcppExports.o parse.o -L/usr/lib/R/lib -lR
installing to /usr/local/lib/R/site-library/00LOCK-RcppTOML/00new/RcppTOML/libs
** R
** inst
** byte-compile and prepare package for lazy loading
** help
*** installing help indices
** building package indices
** testing if installed package can be loaded from temporary location
** checking absolute paths in shared objects and dynamic libraries
** testing if installed package can be loaded from final location
** testing if installed package keeps a record of temporary installation path
* DONE (RcppTOML)
edd@rob:~/git/rcpptoml(master)$ 

This post by Dirk Eddelbuettel originated on his Thinking inside the box blog. Please report excessive re-aggregation in third-party for-profit settings.

Sings-to-Trees had hair the color of sunlight and ashes, delicately pointed ears, and eyes the translucent green of new leaves. His shirt was off, he had the sort of tanned muscle acquired from years of healthy outdoor living, and you could have sharpened a sword on his cheekbones. He was saved from being a young maiden's fantasy unless she was a very peculiar young maiden by the fact that he was buried up to the shoulder in the unpleasant end of a heavily pregnant unicorn.

Sings-to-Trees gazed off in the middle distance with a vague, pleasant expression, the way that most people do when present at other people's minor domestic disputes, and after a moment, the stag had stopped rattling, and the doe had turned back and rested her chin trustingly on Sings-to-Trees' shoulder. This would have been a touching gesture, if her chin hadn't been made of painfully pointy blades of bone. It was like being snuggled by an affectionate plow.

#!/usr/bin/env python3

import nftables
import json
nft = nftables.Nftables()
nft.set_json_output(True)
rc, output, error = nft.cmd("list ruleset")
print(json.loads(output))

• import the nftables & json modules
• init the libnftables instance
• configure library behavior
• run commands and parse the output (ideally using JSON)

flush ruleset
add table inet mytable
add chain inet mytable mychain
add rule inet mytable mychain tcp dport 22 accept

  "nftables": [
      "flush":   "ruleset": null  ,
      "add":   "table":  
        "family": "inet",
        "name": "mytable"
     ,
      "add":   "chain":  
        "family": "inet",
        "table": "mytable",
        "chain": "mychain"
     
      "add":   "rule":  
        "family": "inet",
        "table": "mytable",
        "chain": "mychain",
        "expr": [
              "match":  
                "left":   "payload":  
                    "protocol": "tcp",
                    "field": "dport"
                 ,
                "right": 22
             ,
              "accept": null  
        ]
     
] 

What does this mean? Over the coming weeks, I will:

• transition packages to be team-maintained where it makes sense
• remove myself from the Uploaders field on packages with other maintainers
• orphan packages where I am the sole maintainer

I will try to keep up best-effort maintenance of the manpages.debian.org service and the codesearch.debian.net service, but any help would be much appreciated. For all intents and purposes, please treat me as permanently on vacation. I will try to be around for administrative issues (e.g. permission transfers) and questions addressed directly to me, permitted they are easy enough to answer.

Why? When I joined Debian, I was still studying, i.e. I had luxurious amounts of spare time. Now, over 5 years of full time work later, my day job taught me a lot, both about what works in large software engineering projects and how I personally like my computer systems. I am very conscious of how I spend the little spare time that I have these days. The following sections each deal with what I consider a major pain point, in no particular order. Some of them influence each other for example, if changes worked better, we could have a chance at transitioning packages to be more easily machine readable.

Change process in Debian The last few years, my current team at work conducted various smaller and larger refactorings across the entire code base (touching thousands of projects), so we have learnt a lot of valuable lessons about how to effectively do these changes. It irks me that Debian works almost the opposite way in every regard. I appreciate that every organization is different, but I think a lot of my points do actually apply to Debian. In Debian, packages are nudged in the right direction by a document called the Debian Policy, or its programmatic embodiment, lintian. While it is great to have a lint tool (for quick, local/offline feedback), it is even better to not require a lint tool at all. The team conducting the change (e.g. the C++ team introduces a new hardening flag for all packages) should be able to do their work transparent to me. Instead, currently, all packages become lint-unclean, all maintainers need to read up on what the new thing is, how it might break, whether/how it affects them, manually run some tests, and finally decide to opt in. This causes a lot of overhead and manually executed mechanical changes across packages. Notably, the cost of each change is distributed onto the package maintainers in the Debian model. At work, we have found that the opposite works better: if the team behind the change is put in power to do the change for as many users as possible, they can be significantly more efficient at it, which reduces the total cost and time a lot. Of course, exceptions (e.g. a large project abusing a language feature) should still be taken care of by the respective owners, but the important bit is that the default should be the other way around. Debian is lacking tooling for large changes: it is hard to programmatically deal with packages and repositories (see the section below). The closest to sending out a change for review is to open a bug report with an attached patch. I thought the workflow for accepting a change from a bug report was too complicated and started mergebot, but only Guido ever signaled interest in the project. Culturally, reviews and reactions are slow. There are no deadlines. I literally sometimes get emails notifying me that a patch I sent out a few years ago (!!) is now merged. This turns projects from a small number of weeks into many years, which is a huge demotivator for me. Interestingly enough, you can see artifacts of the slow online activity manifest itself in the offline culture as well: I don t want to be discussing systemd s merits 10 years after I first heard about it. Lastly, changes can easily be slowed down significantly by holdouts who refuse to collaborate. My canonical example for this is rsync, whose maintainer refused my patches to make the package use debhelper purely out of personal preference. Granting so much personal freedom to individual maintainers prevents us as a project from raising the abstraction level for building Debian packages, which in turn makes tooling harder. How would things look like in a better world?

1. As a project, we should strive towards more unification. Uniformity still does not rule out experimentation, it just changes the trade-off from easier experimentation and harder automation to harder experimentation and easier automation.
2. Our culture needs to shift from this package is my domain, how dare you touch it to a shared sense of ownership, where anyone in the project can easily contribute (reviewed) changes without necessarily even involving individual maintainers.

To learn more about how successful large changes can look like, I recommend my colleague Hyrum Wright s talk Large-Scale Changes at Google: Lessons Learned From 5 Yrs of Mass Migrations .

Fragmented workflow and infrastructure Debian generally seems to prefer decentralized approaches over centralized ones. For example, individual packages are maintained in separate repositories (as opposed to in one repository), each repository can use any SCM (git and svn are common ones) or no SCM at all, and each repository can be hosted on a different site. Of course, what you do in such a repository also varies subtly from team to team, and even within teams. In practice, non-standard hosting options are used rarely enough to not justify their cost, but frequently enough to be a huge pain when trying to automate changes to packages. Instead of using GitLab s API to create a merge request, you have to design an entirely different, more complex system, which deals with intermittently (or permanently!) unreachable repositories and abstracts away differences in patch delivery (bug reports, merge requests, pull requests, email, ). Wildly diverging workflows is not just a temporary problem either. I participated in long discussions about different git workflows during DebConf 13, and gather that there were similar discussions in the meantime. Personally, I cannot keep enough details of the different workflows in my head. Every time I touch a package that works differently than mine, it frustrates me immensely to re-learn aspects of my day-to-day. After noticing workflow fragmentation in the Go packaging team (which I started), I tried fixing this with the workflow changes proposal, but did not succeed in implementing it. The lack of effective automation and slow pace of changes in the surrounding tooling despite my willingness to contribute time and energy killed any motivation I had.

Old infrastructure: package uploads When you want to make a package available in Debian, you upload GPG-signed files via anonymous FTP. There are several batch jobs (the queue daemon, unchecked, dinstall, possibly others) which run on fixed schedules (e.g. dinstall runs at 01:52 UTC, 07:52 UTC, 13:52 UTC and 19:52 UTC). Depending on timing, I estimated that you might wait for over 7 hours (!!) before your package is actually installable. What s worse for me is that feedback to your upload is asynchronous. I like to do one thing, be done with it, move to the next thing. The current setup requires a many-minute wait and costly task switch for no good technical reason. You might think a few minutes aren t a big deal, but when all the time I can spend on Debian per day is measured in minutes, this makes a huge difference in perceived productivity and fun. The last communication I can find about speeding up this process is ganneff s post from 2008. How would things look like in a better world?

1. Anonymous FTP would be replaced by a web service which ingests my package and returns an authoritative accept or reject decision in its response.
2. For accepted packages, there would be a status page displaying the build status and when the package will be available via the mirror network.
3. Packages should be available within a few minutes after the build completed.

Old infrastructure: bug tracker I dread interacting with the Debian bug tracker. debbugs is a piece of software (from 1994) which is only used by Debian and the GNU project these days. Debbugs processes emails, which is to say it is asynchronous and cumbersome to deal with. Despite running on the fastest machines we have available in Debian (or so I was told when the subject last came up), its web interface loads very slowly. Notably, the web interface at bugs.debian.org is read-only. Setting up a working email setup for reportbug(1) or manually dealing with attachments is a rather big hurdle. For reasons I don t understand, every interaction with debbugs results in many different email threads. Aside from the technical implementation, I also can never remember the different ways that Debian uses pseudo-packages for bugs and processes. I need them rarely enough to establish a mental model of how they are set up, or working memory of how they are used, but frequently enough to be annoyed by this. How would things look like in a better world?

1. Debian would switch from a custom bug tracker to a (any) well-established one.
2. Debian would offer automation around processes. It is great to have a paper-trail and artifacts of the process in the form of a bug report, but the primary interface should be more convenient (e.g. a web form).

Old infrastructure: mailing list archives It baffles me that in 2019, we still don t have a conveniently browsable threaded archive of mailing list discussions. Email and threading is more widely used in Debian than anywhere else, so this is somewhat ironic. Gmane used to paper over this issue, but Gmane s availability over the last few years has been spotty, to say the least (it is down as I write this). I tried to contribute a threaded list archive, but our listmasters didn t seem to care or want to support the project.

Debian is hard to machine-read While it is obviously possible to deal with Debian packages programmatically, the experience is far from pleasant. Everything seems slow and cumbersome. I have picked just 3 quick examples to illustrate my point. debiman needs help from piuparts in analyzing the alternatives mechanism of each package to display the manpages of e.g. psql(1). This is because maintainer scripts modify the alternatives database by calling shell scripts. Without actually installing a package, you cannot know which changes it does to the alternatives database. pk4 needs to maintain its own cache to look up package metadata based on the package name. Other tools parse the apt database from scratch on every invocation. A proper database format, or at least a binary interchange format, would go a long way. Debian Code Search wants to ingest new packages as quickly as possible. There used to be a fedmsg instance for Debian, but it no longer seems to exist. It is unclear where to get notifications from for new packages, and where best to fetch those packages.

Complicated build stack See my Debian package build tools post. It really bugs me that the sprawl of tools is not seen as a problem by others.

Developer experience pretty painful Most of the points discussed so far deal with the experience in developing Debian, but as I recently described in my post Debugging experience in Debian , the experience when developing using Debian leaves a lot to be desired, too.

I have more ideas At this point, the article is getting pretty long, and hopefully you got a rough idea of my motivation. While I described a number of specific shortcomings above, the final nail in the coffin is actually the lack of a positive outlook. I have more ideas that seem really compelling to me, but, based on how my previous projects have been going, I don t think I can make any of these ideas happen within the Debian project. I intend to publish a few more posts about specific ideas for improving operating systems here. Stay tuned. Lastly, I hope this post inspires someone, ideally a group of people, to improve the developer experience within Debian.

Measurements Keep in mind that these are one-time measurements. They should be indicative of actual performance, but your experience may vary.

ack (small Perl program)

distribution	package manager	data	wall-clock time	rate
Fedora	dnf	114 MB	33s	3.4 MB/s
Debian	apt	16 MB	10s	1.6 MB/s
NixOS	Nix	15 MB	5s	3.0 MB/s
Arch Linux	pacman	6.5 MB	3s	2.1 MB/s
Alpine	apk	10 MB	1s	10.0 MB/s

qemu (large C program)

distribution	package manager	data	wall-clock time	rate
Fedora	dnf	226 MB	4m37s	1.2 MB/s
Debian	apt	224 MB	1m35s	2.3 MB/s
Arch Linux	pacman	142 MB	44s	3.2 MB/s
NixOS	Nix	180 MB	34s	5.2 MB/s
Alpine	apk	26 MB	2.4s	10.8 MB/s

(Looking for older measurements? See Appendix B (2019). The difference between the slowest and fastest package managers is 30x! How can Alpine s apk and Arch Linux s pacman be an order of magnitude faster than the rest? They are doing a lot less than the others, and more efficiently, too.

Pain point: too much metadata For example, Fedora transfers a lot more data than others because its main package list is 60 MB (compressed!) alone. Compare that with Alpine s 734 KB APKINDEX.tar.gz. Of course the extra metadata which Fedora provides helps some use case, otherwise they hopefully would have removed it altogether. The amount of metadata seems excessive for the use case of installing a single package, which I consider the main use-case of an interactive package manager. I expect any modern Linux distribution to only transfer absolutely required data to complete my task.

Pain point: no concurrency Because they need to sequence executing arbitrary package maintainer-provided code (hooks and triggers), all tested package managers need to install packages sequentially (one after the other) instead of concurrently (all at the same time). In my blog post Can we do without hooks and triggers? , I outline that hooks and triggers are not strictly necessary to build a working Linux distribution.

Thought experiment: further speed-ups Strictly speaking, the only required feature of a package manager is to make available the package contents so that the package can be used: a program can be started, a kernel module can be loaded, etc. By only implementing what s needed for this feature, and nothing more, a package manager could likely beat apk s performance. It could, for example:

• skip archive extraction by mounting file system images (like AppImage or snappy)
• use compression which is light on CPU, as networks are fast (like apk)
• skip fsync when it is safe to do so, i.e.:
  • package installations don t modify system state
  • atomic package installation (e.g. an append-only package store)
  • automatically clean up the package store after crashes

Current landscape Here s a table outlining how the various package managers listed on Wikipedia s list of software package management systems fare:

name	scope	package file format	hooks/triggers
AppImage	apps	image: ISO9660, SquashFS	no
snappy	apps	image: SquashFS	yes: hooks
FlatPak	apps	archive: OSTree	no
0install	apps	archive: tar.bz2	no
nix, guix	distro	archive: nar. bz2,xz	activation script
dpkg	distro	archive: tar. gz,xz,bz2 in ar(1)	yes
rpm	distro	archive: cpio. bz2,lz,xz	scriptlets
pacman	distro	archive: tar.xz	install
slackware	distro	archive: tar. gz,xz	yes: doinst.sh
apk	distro	archive: tar.gz	yes: .post-install
Entropy	distro	archive: tar.bz2	yes
ipkg, opkg	distro	archive: tar ,.gz	yes

Conclusion As per the current landscape, there is no distribution-scoped package manager which uses images and leaves out hooks and triggers, not even in smaller Linux distributions. I think that space is really interesting, as it uses a minimal design to achieve significant real-world speed-ups. I have explored this idea in much more detail, and am happy to talk more about it in my post Introducing the distri research linux distribution".

Appendix A: related work There are a couple of recent developments going into the same direction:

• Revisiting How We Put Together Linux Systems describes mounting app bundles
• Android Q uses ext4 loopback images
• The Haiku Operating System s package manager Haiku Depot uses images

Appendix C: measurement details (2020)

ack You can expand each of these:

Fedora s dnf takes almost 33 seconds to fetch and unpack 114 MB.

% docker run -t -i fedora /bin/bash
[root@62d3cae2e2f9 /]# time dnf install -y ack
Fedora 32 openh264 (From Cisco) - x86_64     1.9 kB/s   2.5 kB     00:01
Fedora Modular 32 - x86_64                   6.8 MB/s   4.9 MB     00:00
Fedora Modular 32 - x86_64 - Updates         5.6 MB/s   3.7 MB     00:00
Fedora 32 - x86_64 - Updates                 9.9 MB/s    23 MB     00:02
Fedora 32 - x86_64                            39 MB/s    70 MB     00:01
[ ]
real	0m32.898s
user	0m25.121s
sys	0m1.408s

NixOS s Nix takes a little over 5s to fetch and unpack 15 MB.

% docker run -t -i nixos/nix
39e9186422ba:/# time sh -c 'nix-channel --update && nix-env -iA nixpkgs.ack'
unpacking channels...
created 1 symlinks in user environment
installing 'perl5.32.0-ack-3.3.1'
these paths will be fetched (15.55 MiB download, 85.51 MiB unpacked):
  /nix/store/34l8jdg76kmwl1nbbq84r2gka0kw6rc8-perl5.32.0-ack-3.3.1-man
  /nix/store/9df65igwjmf2wbw0gbrrgair6piqjgmi-glibc-2.31
  /nix/store/9fd4pjaxpjyyxvvmxy43y392l7yvcwy1-perl5.32.0-File-Next-1.18
  /nix/store/czc3c1apx55s37qx4vadqhn3fhikchxi-libunistring-0.9.10
  /nix/store/dj6n505iqrk7srn96a27jfp3i0zgwa1l-acl-2.2.53
  /nix/store/ifayp0kvijq0n4x0bv51iqrb0yzyz77g-perl-5.32.0
  /nix/store/w9wc0d31p4z93cbgxijws03j5s2c4gyf-coreutils-8.31
  /nix/store/xim9l8hym4iga6d4azam4m0k0p1nw2rm-libidn2-2.3.0
  /nix/store/y7i47qjmf10i1ngpnsavv88zjagypycd-attr-2.4.48
  /nix/store/z45mp61h51ksxz28gds5110rf3wmqpdc-perl5.32.0-ack-3.3.1
copying path '/nix/store/34l8jdg76kmwl1nbbq84r2gka0kw6rc8-perl5.32.0-ack-3.3.1-man' from 'https://cache.nixos.org'...
copying path '/nix/store/czc3c1apx55s37qx4vadqhn3fhikchxi-libunistring-0.9.10' from 'https://cache.nixos.org'...
copying path '/nix/store/9fd4pjaxpjyyxvvmxy43y392l7yvcwy1-perl5.32.0-File-Next-1.18' from 'https://cache.nixos.org'...
copying path '/nix/store/xim9l8hym4iga6d4azam4m0k0p1nw2rm-libidn2-2.3.0' from 'https://cache.nixos.org'...
copying path '/nix/store/9df65igwjmf2wbw0gbrrgair6piqjgmi-glibc-2.31' from 'https://cache.nixos.org'...
copying path '/nix/store/y7i47qjmf10i1ngpnsavv88zjagypycd-attr-2.4.48' from 'https://cache.nixos.org'...
copying path '/nix/store/dj6n505iqrk7srn96a27jfp3i0zgwa1l-acl-2.2.53' from 'https://cache.nixos.org'...
copying path '/nix/store/w9wc0d31p4z93cbgxijws03j5s2c4gyf-coreutils-8.31' from 'https://cache.nixos.org'...
copying path '/nix/store/ifayp0kvijq0n4x0bv51iqrb0yzyz77g-perl-5.32.0' from 'https://cache.nixos.org'...
copying path '/nix/store/z45mp61h51ksxz28gds5110rf3wmqpdc-perl5.32.0-ack-3.3.1' from 'https://cache.nixos.org'...
building '/nix/store/m0rl62grplq7w7k3zqhlcz2hs99y332l-user-environment.drv'...
created 49 symlinks in user environment
real	0m 5.60s
user	0m 3.21s
sys	0m 1.66s

Debian s apt takes almost 10 seconds to fetch and unpack 16 MB.

% docker run -t -i debian:sid
root@1996bb94a2d1:/# time (apt update && apt install -y ack-grep)
Get:1 http://deb.debian.org/debian sid InRelease [146 kB]
Get:2 http://deb.debian.org/debian sid/main amd64 Packages [8400 kB]
Fetched 8546 kB in 1s (8088 kB/s)
[ ]
The following NEW packages will be installed:
  ack libfile-next-perl libgdbm-compat4 libgdbm6 libperl5.30 netbase perl perl-modules-5.30
0 upgraded, 8 newly installed, 0 to remove and 23 not upgraded.
Need to get 7341 kB of archives.
After this operation, 46.7 MB of additional disk space will be used.
[ ]
real	0m9.544s
user	0m2.839s
sys	0m0.775s

Arch Linux s pacman takes a little under 3s to fetch and unpack 6.5 MB.

% docker run -t -i archlinux/base
[root@9f6672688a64 /]# time (pacman -Sy && pacman -S --noconfirm ack)
:: Synchronizing package databases...
 core            130.8 KiB  1090 KiB/s 00:00
 extra          1655.8 KiB  3.48 MiB/s 00:00
 community         5.2 MiB  6.11 MiB/s 00:01
resolving dependencies...
looking for conflicting packages...
Packages (2) perl-file-next-1.18-2  ack-3.4.0-1
Total Download Size:   0.07 MiB
Total Installed Size:  0.19 MiB
[ ]
real	0m2.936s
user	0m0.375s
sys	0m0.160s

Alpine s apk takes a little over 1 second to fetch and unpack 10 MB.

% docker run -t -i alpine
fetch http://dl-cdn.alpinelinux.org/alpine/v3.12/main/x86_64/APKINDEX.tar.gz
fetch http://dl-cdn.alpinelinux.org/alpine/v3.12/community/x86_64/APKINDEX.tar.gz
(1/4) Installing libbz2 (1.0.8-r1)
(2/4) Installing perl (5.30.3-r0)
(3/4) Installing perl-file-next (1.18-r0)
(4/4) Installing ack (3.3.1-r0)
Executing busybox-1.31.1-r16.trigger
OK: 43 MiB in 18 packages
real	0m 1.24s
user	0m 0.40s
sys	0m 0.15s

qemu You can expand each of these:

Fedora s dnf takes over 4 minutes to fetch and unpack 226 MB.

% docker run -t -i fedora /bin/bash
[root@6a52ecfc3afa /]# time dnf install -y qemu
Fedora 32 openh264 (From Cisco) - x86_64     3.1 kB/s   2.5 kB     00:00
Fedora Modular 32 - x86_64                   6.3 MB/s   4.9 MB     00:00
Fedora Modular 32 - x86_64 - Updates         6.0 MB/s   3.7 MB     00:00
Fedora 32 - x86_64 - Updates                 334 kB/s    23 MB     01:10
Fedora 32 - x86_64                            33 MB/s    70 MB     00:02
[ ]
Total download size: 181 M
Downloading Packages:
[ ]
real	4m37.652s
user	0m38.239s
sys	0m6.321s

NixOS s Nix takes almost 34s to fetch and unpack 180 MB.

% docker run -t -i nixos/nix
83971cf79f7e:/# time sh -c 'nix-channel --update && nix-env -iA nixpkgs.qemu'
unpacking channels...
created 1 symlinks in user environment
installing 'qemu-5.1.0'
these paths will be fetched (180.70 MiB download, 1146.92 MiB unpacked):
[ ]
real	0m 33.64s
user	0m 16.96s
sys	0m 3.05s

Debian s apt takes over 95 seconds to fetch and unpack 224 MB.

% docker run -t -i debian:sid
root@b7cc25a927ab:/# time (apt update && apt install -y qemu-system-x86)
Get:1 http://deb.debian.org/debian sid InRelease [146 kB]
Get:2 http://deb.debian.org/debian sid/main amd64 Packages [8400 kB]
Fetched 8546 kB in 1s (5998 kB/s)
[ ]
Fetched 216 MB in 43s (5006 kB/s)
[ ]
real	1m25.375s
user	0m29.163s
sys	0m12.835s

Arch Linux s pacman takes almost 44s to fetch and unpack 142 MB.

% docker run -t -i archlinux/base
[root@58c78bda08e8 /]# time (pacman -Sy && pacman -S --noconfirm qemu)
:: Synchronizing package databases...
 core          130.8 KiB  1055 KiB/s 00:00
 extra        1655.8 KiB  3.70 MiB/s 00:00
 community       5.2 MiB  7.89 MiB/s 00:01
[ ]
Total Download Size:   135.46 MiB
Total Installed Size:  661.05 MiB
[ ]
real	0m43.901s
user	0m4.980s
sys	0m2.615s

Alpine s apk takes only about 2.4 seconds to fetch and unpack 26 MB.

% docker run -t -i alpine
/ # time apk add qemu-system-x86_64
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/main/x86_64/APKINDEX.tar.gz
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/community/x86_64/APKINDEX.tar.gz
[ ]
OK: 78 MiB in 95 packages
real	0m 2.43s
user	0m 0.46s
sys	0m 0.09s

Appendix B: measurement details (2019)

ack You can expand each of these:

Fedora s dnf takes almost 30 seconds to fetch and unpack 107 MB.

% docker run -t -i fedora /bin/bash
[root@722e6df10258 /]# time dnf install -y ack
Fedora Modular 30 - x86_64            4.4 MB/s   2.7 MB     00:00
Fedora Modular 30 - x86_64 - Updates  3.7 MB/s   2.4 MB     00:00
Fedora 30 - x86_64 - Updates           17 MB/s    19 MB     00:01
Fedora 30 - x86_64                     31 MB/s    70 MB     00:02
[ ]
Install  44 Packages
Total download size: 13 M
Installed size: 42 M
[ ]
real	0m29.498s
user	0m22.954s
sys	0m1.085s

NixOS s Nix takes 14s to fetch and unpack 15 MB.

% docker run -t -i nixos/nix
39e9186422ba:/# time sh -c 'nix-channel --update && nix-env -i perl5.28.2-ack-2.28'
unpacking channels...
created 2 symlinks in user environment
installing 'perl5.28.2-ack-2.28'
these paths will be fetched (14.91 MiB download, 80.83 MiB unpacked):
  /nix/store/57iv2vch31v8plcjrk97lcw1zbwb2n9r-perl-5.28.2
  /nix/store/89gi8cbp8l5sf0m8pgynp2mh1c6pk1gk-attr-2.4.48
  /nix/store/gkrpl3k6s43fkg71n0269yq3p1f0al88-perl5.28.2-ack-2.28-man
  /nix/store/iykxb0bmfjmi7s53kfg6pjbfpd8jmza6-glibc-2.27
  /nix/store/k8lhqzpaaymshchz8ky3z4653h4kln9d-coreutils-8.31
  /nix/store/svgkibi7105pm151prywndsgvmc4qvzs-acl-2.2.53
  /nix/store/x4knf14z1p0ci72gl314i7vza93iy7yc-perl5.28.2-File-Next-1.16
  /nix/store/zfj7ria2kwqzqj9dh91kj9kwsynxdfk0-perl5.28.2-ack-2.28
copying path '/nix/store/gkrpl3k6s43fkg71n0269yq3p1f0al88-perl5.28.2-ack-2.28-man' from 'https://cache.nixos.org'...
copying path '/nix/store/iykxb0bmfjmi7s53kfg6pjbfpd8jmza6-glibc-2.27' from 'https://cache.nixos.org'...
copying path '/nix/store/x4knf14z1p0ci72gl314i7vza93iy7yc-perl5.28.2-File-Next-1.16' from 'https://cache.nixos.org'...
copying path '/nix/store/89gi8cbp8l5sf0m8pgynp2mh1c6pk1gk-attr-2.4.48' from 'https://cache.nixos.org'...
copying path '/nix/store/svgkibi7105pm151prywndsgvmc4qvzs-acl-2.2.53' from 'https://cache.nixos.org'...
copying path '/nix/store/k8lhqzpaaymshchz8ky3z4653h4kln9d-coreutils-8.31' from 'https://cache.nixos.org'...
copying path '/nix/store/57iv2vch31v8plcjrk97lcw1zbwb2n9r-perl-5.28.2' from 'https://cache.nixos.org'...
copying path '/nix/store/zfj7ria2kwqzqj9dh91kj9kwsynxdfk0-perl5.28.2-ack-2.28' from 'https://cache.nixos.org'...
building '/nix/store/q3243sjg91x1m8ipl0sj5gjzpnbgxrqw-user-environment.drv'...
created 56 symlinks in user environment
real	0m 14.02s
user	0m 8.83s
sys	0m 2.69s

Debian s apt takes almost 10 seconds to fetch and unpack 16 MB.

% docker run -t -i debian:sid
root@b7cc25a927ab:/# time (apt update && apt install -y ack-grep)
Get:1 http://cdn-fastly.deb.debian.org/debian sid InRelease [233 kB]
Get:2 http://cdn-fastly.deb.debian.org/debian sid/main amd64 Packages [8270 kB]
Fetched 8502 kB in 2s (4764 kB/s)
[ ]
The following NEW packages will be installed:
  ack ack-grep libfile-next-perl libgdbm-compat4 libgdbm5 libperl5.26 netbase perl perl-modules-5.26
The following packages will be upgraded:
  perl-base
1 upgraded, 9 newly installed, 0 to remove and 60 not upgraded.
Need to get 8238 kB of archives.
After this operation, 42.3 MB of additional disk space will be used.
[ ]
real	0m9.096s
user	0m2.616s
sys	0m0.441s

Arch Linux s pacman takes a little over 3s to fetch and unpack 6.5 MB.

% docker run -t -i archlinux/base
[root@9604e4ae2367 /]# time (pacman -Sy && pacman -S --noconfirm ack)
:: Synchronizing package databases...
 core            132.2 KiB  1033K/s 00:00
 extra          1629.6 KiB  2.95M/s 00:01
 community         4.9 MiB  5.75M/s 00:01
[ ]
Total Download Size:   0.07 MiB
Total Installed Size:  0.19 MiB
[ ]
real	0m3.354s
user	0m0.224s
sys	0m0.049s

Alpine s apk takes only about 1 second to fetch and unpack 10 MB.

% docker run -t -i alpine
/ # time apk add ack
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/main/x86_64/APKINDEX.tar.gz
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/community/x86_64/APKINDEX.tar.gz
(1/4) Installing perl-file-next (1.16-r0)
(2/4) Installing libbz2 (1.0.6-r7)
(3/4) Installing perl (5.28.2-r1)
(4/4) Installing ack (3.0.0-r0)
Executing busybox-1.30.1-r2.trigger
OK: 44 MiB in 18 packages
real	0m 0.96s
user	0m 0.25s
sys	0m 0.07s

qemu You can expand each of these:

Fedora s dnf takes over a minute to fetch and unpack 266 MB.

% docker run -t -i fedora /bin/bash
[root@722e6df10258 /]# time dnf install -y qemu
Fedora Modular 30 - x86_64            3.1 MB/s   2.7 MB     00:00
Fedora Modular 30 - x86_64 - Updates  2.7 MB/s   2.4 MB     00:00
Fedora 30 - x86_64 - Updates           20 MB/s    19 MB     00:00
Fedora 30 - x86_64                     31 MB/s    70 MB     00:02
[ ]
Install  262 Packages
Upgrade    4 Packages
Total download size: 172 M
[ ]
real	1m7.877s
user	0m44.237s
sys	0m3.258s

NixOS s Nix takes 38s to fetch and unpack 262 MB.

% docker run -t -i nixos/nix
39e9186422ba:/# time sh -c 'nix-channel --update && nix-env -i qemu-4.0.0'
unpacking channels...
created 2 symlinks in user environment
installing 'qemu-4.0.0'
these paths will be fetched (262.18 MiB download, 1364.54 MiB unpacked):
[ ]
real	0m 38.49s
user	0m 26.52s
sys	0m 4.43s

Debian s apt takes 51 seconds to fetch and unpack 159 MB.

% docker run -t -i debian:sid
root@b7cc25a927ab:/# time (apt update && apt install -y qemu-system-x86)
Get:1 http://cdn-fastly.deb.debian.org/debian sid InRelease [149 kB]
Get:2 http://cdn-fastly.deb.debian.org/debian sid/main amd64 Packages [8426 kB]
Fetched 8574 kB in 1s (6716 kB/s)
[ ]
Fetched 151 MB in 2s (64.6 MB/s)
[ ]
real	0m51.583s
user	0m15.671s
sys	0m3.732s

Arch Linux s pacman takes 1m2s to fetch and unpack 124 MB.

% docker run -t -i archlinux/base
[root@9604e4ae2367 /]# time (pacman -Sy && pacman -S --noconfirm qemu)
:: Synchronizing package databases...
 core       132.2 KiB   751K/s 00:00
 extra     1629.6 KiB  3.04M/s 00:01
 community    4.9 MiB  6.16M/s 00:01
[ ]
Total Download Size:   123.20 MiB
Total Installed Size:  587.84 MiB
[ ]
real	1m2.475s
user	0m9.272s
sys	0m2.458s

Alpine s apk takes only about 2.4 seconds to fetch and unpack 26 MB.

% docker run -t -i alpine
/ # time apk add qemu-system-x86_64
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/main/x86_64/APKINDEX.tar.gz
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/community/x86_64/APKINDEX.tar.gz
[ ]
OK: 78 MiB in 95 packages
real	0m 2.43s
user	0m 0.46s
sys	0m 0.09s