In this iteration of provenance in the wild we have John Wiegley writing about no less than three topics I’m interested in:
- recursion schemes
The context is hnix, a Haskell reimplementation of the nix expression language. It is a pure, lazy, dynamically typed, functional language. On top of that the nix package manager is built. And on top of that NixOS, a Linux distribution. If you don’t know about nix, check it out. It’s awesome.
Here is the Github issue that describes the new
--trace option to hnix. Hnix takes a nix expression as input and evaluates it. With the new
--trace option, it also outputs a nix expression that is somehow smaller than the original input but produces the same output. I haven’t looked at the implementation, and I don’t see a formal definition of how the output nix expression is related to the input nix expression, but it sounds like program slicing to me, which is related closely enough to provenance for this to make it into the provenance in the wild series.
I have thought about the possibility of doing something similar before, because Weili Fu, who started her PhD at the same time as me, works on provenance in the context of the configuration language Puppet. I’m happy similar things are happening in the real world.
If you want to read more about slicing, my advisor and other Edinburgh people recently wrote an ICFP paper on slicing functional programs: Imperative Functional Programs that Explain their Work, Wilmer Ricciotti, Jan Stolarek, Roly Perera and James Cheney. ICFP 2017.
Here’s the blog post about the implementation: http://newartisans.com/2018/04/win-for-recursion-schemes/ Turns out hnix is based on recursion schemes and this allows for a very neat implementation. I really need to find time some day soon to have more than a cursory glance at recursion schemes.