ICFP 2022

Here are notes for some of the presentations I attended at ICFP 2022 in Ljubljana, Slovenia. Most of those notes will only be useful for myself but here is my:

TL;DR 

Here are the topics I enjoyed the most (in no particular order):

• Infinite traversals with the Predictable typeclass
• David Christiansen's keynote drawing a future for Haskell
• Modelling probabilistic models with the probfx library
• Open Transactional Actions to get IO + STM
• The advent of OCaml 5 with concurrency and associated tooling
• The ongoing work to make GHC more modular
• The Functional Architecture workshop (lead by Mike Sperber)
• The rec-def library by Joachim Breitner

Now for the fuzzy feelings:

• it is really great to be able to see people in person again. Online conferences are just not my thing. Half the point is being able to have informal discussions
• it feels great to be part of this intersection of academia and industry. They (academia) give us solutions we (industry) give them new problems
• I like the melting pot between the various languages like Haskell and OCaml, but also Adga, Coq and all the research languages. Being in the same place really benefits everyone 
• I am fascinated to see that we are still finding new calculi on top of the lambda calculus with new and better ways to execute them
• Yes it's still tough to walk around with an imposter syndrome but hey I had a meaningful conversation about a language for quantum computing so it's not that bad :-)
• Funding is probably still a problem for Haskell, many ideas, not enough time. But there is definitely some momentum. The past months have been better than before and it seems that it's only improving

NOTES

Haskell Implementors workshop (Sunday)

The Haskell Implementors workshop gathers GHC developers and users discussing the evolution of the language and tooling. Here are my highlights for this year. 

State of GHC 

 The 6-months cadence is bringing us useful production-oriented features like: 

•   profiling without -prof 
•   stacktraces 

Some notable community initiatives: 

• the Haskell error message index 
• proposal: Hackage.X overlay to spread out changes faster (anyone can propose a patch to a library when a new GHC version is out) 
• proposal: "tick-tock" release cadence -> long-term maintenance releases + frequent non-backported releases 

Compiling Mu with GHC: Halfway Down the Rabbit Hole

Mu is a non-lazy Haskell 98 language used at Standard Charted with millions of lines of code. It contains features not present in GHC to support relational algebra types and programs: 

• open data kinds 
• closed type families with fundeps, etc... 

Cortex is the internal language used by Mu and SC is trying to port it to GHC in order to reduce the maintenance burden. It is not trivial because the GHC API is not well-defined nor stable.

One library from Digital Asset helps. ghc-lib-generator turns a GHC source tree into a standalone package (= turns GHC into a library). 

Some code now compiles with GHC much more work remains to be done around specialization/monophormization etc... 

A Termination Checker for Haskell Rewrite Rules

Rewrite rules are generally not checked. We just hope that: 

• they terminate 
• they are consistent (produce the same results depending on the order they are being applied) 

GSOL is a termination + confluence GHC plugin which has been used to check 177 Haskell package (that tool won some termination and checking competitions in 2018 and 2022, yes there is such a thing). 

Good news: all those rules are terminating. 

Maybe bad news, there are many non-confluent rules (for example in Control.Arrow) 

Annotating Deeply Embedded Languages 

Accelerate is a Haskell library to run computations on different hardware like GPUs. It uses a deeply embedded DSL where terms are eventually translated to other programs. 

Problem: how to relate the code which is effectively executed, with arbitrary names, to the names in the original Haskell code? 

Accelerate defined a new constraint which generates compilation error when a HasCallStack constraint is missing in a sequence of function calls. 

type SourceMapped = (?requiresSourceMapping :: ReadTheDocs, HasCallStack) data ReadTheDocs = TakenCareOf sourceMap :: HasCallStack => (SourceMapped => a) -> a

This is probably a good thing for users of free monads but the thing I really need is [exception stacktraces :-). 

Modularizing GHC 

This work is led by a small group at IOG who need to have better backend for GHCJS in order to integrate off-chain JavaScript code in their execution pipeline. 

Problem: GHC is a very old compiler which could benefit from a *lot* of refactorings. The details can be found in ghc-modularity but one obvious example is the sharing of a DynFlags data type which contains dynamic configuration flags which have more than 600 uses. 

We can expect from this work: 

• easier experiments with GHC 
• easier integration with other tools in the eco-system 
• maybe even better performances 

Recursive definitions 

Typical example of an elegant recursive computation in Haskell: compute the transitive closure of a graph. 

Problem: what if the graph is cyclic?

ref-def is a library with a R datatype allowing the recursive definition of sets. It uses unsafePerformIO under the hood but offers a pure interface. 

Across the pond 

 Let's compare the Haskell and the Racket ecosystems. For example Hoogle is nice but 

`hoogle --local` does not work out of the box because it needs information that only Cabal has.

On the other hand all the tools for Racket, documentation, build tool, compiler, etc... are integrated as libraries usable directly from the repl. 

Why is Racket better? 

• the context is shared by all the libraries / tools 
• the context API is very stable 

Haskell Playground 

 The Haskell Playground started as a pastebin for Haskell but it supports now several versions of GHC and produces Core/ASM code. Beside the communication and test of snippets this can be very useful to investigate performance and optimisation issues IMO. 

CSI: Haskell: Fault-Localization in Lazy Languages using Runtime Tracing

Idea: use the Haskell coverage support to add trace information when runtime errors occur - since Haskell is lazy it is likely that the producer of a faulty value is going to be close to its consumer If we report this (summarized) trace information in the error report then we have a form of data flow analysis and we can use it to track down the source of faulty data.

ICFP Day 1

Keynote: Programming the network

Network programming is fairly static with a strong division between a "control plane" (what's the topology of the network) and a "data plane"

(how data is routed from one node to another).

But it would be nice to make it more programmable:

• take an existing in-house network and move it to the cloud keeping the same topology
• do traffic engineering. Traditionally done with a protocol, today we'd like to run optimisers and change the config more dynamically
• debug the traffic: understand how a given packet flows
• support caching, coordination protocols, have failure detectors built into the network

PL techniques can be used to support this. The NetKAT DSL describes links and behaviours which can then be compiled to forwarding tables.

We can also use techniques to make sure that some security policies are maintained when a network is reconfigured.

The Theory of Call-by-Value Solvability

The lambda calculus is a minimal calculus, with no notion of "result".

We need to be able to distinguish divergent terms from other terms.

The proper way, the one that gives a consistent theory, is to define a notion of "solvability":

• a term is solvable if there is a head context H such that H<t> reduces to identity

This is a way of saying that some non-terminating terms can still be subterms of a terminating term and it's ok. There are different characterizations of solvability and one of them is multitypes (multisets of intersected types)

A Simple and Efficient Implementation of Strong Call by Need by an Abstract Machine

Reminder: call by need is like call by name, terms are only evaluated when required but they are evaluated once. How to implement this calculus efficiently?

 1. Start with an abstract machine (KN machine)

 2. deconstruct it to some functional code (definitial interpreter)

 3. optimise the functional code

 4. reconstruct an optimal machine (RKNL machine)

How can we make sure that RKNL implements strong CBN? This is proven through a "Ghost Abstract Machine" which simplifies the rules

The implementation efficiency is proven via a potential function.

Multi-types and reasonable space

In a computational model time is modelled as number of steps to compute something,

and space is modelled as the maximum size of visited configurations.

We can use multi-types to relate the type of a term to the size of derivation of a subterm, hence give an idea of the time taken. What about space? If sharing is used in a machine (for time reasons) then space is hard to compute.

The Space Krivine Abstract Machine accounts for space: sharing is limited to terms (to account for the size of the input), and garbage collection is eager.

The Space KAM is a good ("reasonable" = linearly closed to the reality) space cost model (there's a translation to a Turing Machine to a Space KAM).

Unfortunately multi-types do not account for the size of closures.

Idea: enrich multi-types with closure types. A multi-set is labelled with a natural number for the closure size.

Then closure types are a complete and sound methodology for the Space KAM.

Future work: type systems for space complexity analysis (this is not doable for time since type inference is an undecidable property)

Denotational semantics as a foundation for cost recurrence extraction for functional languages

Can we use denotational semantics to come up with the equations for calculating the algorithmic cost of a function? Several steps:

 1. transform the program into a writer monad with usage costs

 2. interpret in a model, using naturals to interpret a tree for example

 3. have a theorem to prove that we really have a model of the recurrence language

Random Testing of a Higher-Order Blockchain Language (experience report)

In smart contracts we need to deal with:

 1. static semantic bugs: an exception is thrown and the contract function cannot be executed

 2. cost semantic bugs: not enough gas is charged for expensive computations => DDOS attacks

 3. compiler exploit: a compiler can be exploited by sending some code that blows up the size of the generated program

Can we use property-based testing to avoid this? Scilla is a smart contract language based System F + extensions and is not Turing complete (it has structural recursion).

Scilla has an OCaml monadic interpreter. How to generate well-typed terms for System F?

Use QuickChick (Coq library):

• easy to define generators for ASTs
• can generate OCaml code
• has support for fuzzing

Generating type applications in a bit tricky. The trick is to use "unsubstitution".

Bugs were found in:

• the interpreter: conversion bugs
• the interpreter: charged gas
• typeflow analysis

A Completely Unique Account of Enumeration

Enumerators can enumerate all the values of a data type. This can be useful for testing

in the way that smallcheck and leancheck do with the idea that

"If a program fails to meet its specification in some cases, it almost always fails in some simple case".

This work has found a way to define enumerations that are provably:

• complete: they list all elements
• unique: they produce each element once
• fair: they interleave elements of lists

They have also shown that enumerators can be derived from Generics and keep the same properties. It also works with indexed type families. The paper mentions that Generics with true sums-of-products would be better (I agree, I think that should be the default way to have generics).

After discussing with one of the authors and doing a bit of experimentation I realized

that it was hard to do an enumeration of value by size because of the way recursion is handled in recursive data types. The way it is done, we get an enumeration per depth in a tree for example. I think I need to come back to something like FEAT.

ICFP Day 2

Keynote: Call-by-Push-Value, Quantitatively

The Bang Calculus, introduced in 2016, is a call by push value calculus which encompasses call by name (CBN) and call by value (CBV). It is complete and coherent (It took 4 years and some iterations to prove this!)

Concretely speaking the bang calculus adds some constructs to the lambda calculus:

•  !t "bang", to make a thunk)
•  der "dereliction", to force a thunk
•  explicit substitution.

Then 3 rules are given for its execution:

  1. Beta rule: introduces a new explicit substitution (let binding)

  2. substitution: substitutes a bang term

  3. value/computation "dereliction": der(!t) -> t

This calculus has a resource aware semantic, its complete and confluent (and all evaluation sequences to normal form have the same length We have some translations from CBN/CBV to the Bang calculus (due to Girard in '76). This allows to prove some qualitative properties: soundness, completeness.

What about quantitative properties: how much time / space?

Idea: use non-idempotent multitypes: types are multisets (duplicated elements -> then you can count things!) Those types can type non-terminating terms so there's no decidable type inference.

However it is possible to show some properties like time + space <= nb nodes in type derivation.

It is even possible to go further and find some properties for time and space independently.

Another interesting property is: decide if a type is inhabitable. An algorithm has been defined to do this: it terminates, is sound, complete, and finds all the generators for those terms.

Datatype-Generic Programming Meets Elaborator Reflection

For each datatype defined in Agda, like 'List' we expect to have corresponding proofs

like `here` and `there` to do some lookups:

data Any {p} (P : A → Set p) : List A → Set (a ⊔ p) where

  here  : ∀ {x xs} (px  : P x)      → Any P (x ∷ xs)

  there : ∀ {x xs} (pxs : Any P xs) → Any P (x ∷ xs)

Problem: this is tedious and looks quite mechanical to derive

Idea: use the elaborator reflection to define those data type. This would be a bit like using Generics / TemplateHaskell in Haskell.

Main difficulty; writing generic code is difficult and error-prone

Practical generic programming over a universe of datatypes

This is a variation of the previous talk. Can we derive properties like deriving Eq in Agda?

This team has defined some support for generics (a "universe of descriptions") plus some combinators to be able to do that. And now (among other things) decidable equality can be implemented by just deriving it from some data types.

Structural Versus Pipeline Composition of Higher-Order Functions (experience report)

Context: try to have students solve problems using higher-order functions

Problem: most problems are either too easy or to hard

Insight: there's a difference between structural composition and pipeline composition

structural

  example_fun :: [a] -> b

  example_fun as = hof1 (\inner -> hof2 arg inner) as

pipeline

  example_fun :: [a] -> b

  example_fun as = hof1 f (hof2 g as)

An experiment was run on student and it turns out, contrary to experts intuition, that structural solutions are easier to find.

For example "map elements in a list of lists and filter each list", which is `map (filter condition)`.

The reason for this might be related to program synthesis and the fact that structural composition imposes more constraints on the possible types.

ICFP Day 3

Keynote: Retrofitting concurrency

How to add concurrency to OCaml 4.0?

In 2014, OCaml was used a lot but with a GIL like Python. The objective was to add concurrency without breaking anything:

• OCaml has low latency ~10ms tolerance. We want to keep an efficient GC
• we need to make sure that the maintenance burden stays low by not having 2 runtimes like GHC
• existing sequential programs should run the same

Main points:

• there were several iterations and even a full rewrite to implement a concurrent garbage collector (major heap -> mostly concurrent, minor heap -> stop the world parallel)
• working on data races showed the need for a new memory model with a "DRF-SC" guarantee (data-race-freedom sequential-consistency)
• instead of baking the scheduler in the runtime system like in GHC extract it as a library (trying to extract the Scheduler from GHC's RTS proved to be really hard)
• implement delimited continuations, they are easier to understand than shift/reset
• care for users, don't break their code. Most of the code is likely to stay sequential
• use build tools to ease the transition: OPAM heath check checks the compatibiliy of package on every 5.0-alpha release
• benchmark on _real_ programs (Coq, Irmin - database, for example). http://sandmark.tarides.com is a benchmarking site as a service
• invest in tooling
• it is hard to maintain a separate fork for 7 years, hard to keep up with main
• it is hard to get approbation from the main developers
• peer-reviewed papers add credibility to such and effort
• tooling + benchmarks help
• the last 10% to finish Ocaml 5 now requires lots of engineering effort, and less of academic effort

Many more things to come with the vision of being as fast as Rust with a GC and have the type safety of ML.

Beyond Relooper: Recursive Translation of Unstructured Control Flow to Structured Control Flow

Control flow in WASM is very simple:

• if ... then ... else ... conditionals
• loop ... end loop (no conditionals)
• block ... end block of code
• br k escape the current nesting(s)

Problem: translate structured programming with functions, variables, conditionals to the to the form above in a compiler. 

There's a heuristic algorithm for this kind of thing in the JavaScript world (Relooper) but a complete solution has been described since the '70s! That algorithm is hard to understand and has 3 passes. Can we do better?

Yes! Use functional programming and techniques from static analysis

  1. build and ADT

  2. from the outside in

  3. by recursion over dominator trees (which is a notion of which unique nodes need to be executed before executing something else) in the control flow graph

  4. order children by reverse postorder

  5. use control context for branches

Note: within one day Joachim Breitner was able to use his rec-def library to make the code even nicer: https://www.joachim-breitner.de/blog/795-rec-def__Dominators_case_study

Automatically Deriving Control-Flow Graph Generators From Operational Semantics

Various control graphs can be produced from a given program depending on how much information we want to keep. Some analyzers / model checkers need different CFGs. But what is a CFG anyway? Is there a systematic way to derive a CFG from the semantics of a language?

The answer is yes by using abstract machines and abstract evaluation

Analyzing binding extent in CPS

"we are the anti-MLton". MLton is a full program SML compiler for high-performance executables:

• by monomorphization
• by defunctionalization

3CPS is a totally different approach:

•  flexible
•  separate compilation
•  keep polymorphic terms
•  aimed at making FP fast

Problem: 

  FP is all about keeping track of the environment.

  when there are closures some bindings must move from the stack to the heap

Idea:

• define 3 "extents": heap / stack / register
• every variable has an extent describing its lifetime
• heap extent: every variable has it but it is the most heavyweight machine resource
• stack extent: the binding lifetime must be shorter than the stack frame around it. As a syntactic approximation: If there's no reference from x in a lambda it's ok (because we don't need a closure)
• register extent. As a syntactic approximation: there is no function call between the definition of a variable and its uses

The paper shows how to do a lot better than syntactic approximations and as a result rewrites some programs so that 90% of their variables can be moved to the stack. And this analysis is fast to perform.

Question from SPJ: "I envy your work, how will it work for lazy evaluation?". 

Answer "it's always a good thing if SPJ is envying your work etc..." (I did not understand the answer :|)

Note: this work looks actually quite close to the work presented by Stephen Dolan on using global / local modalities to keep values on the stack.

do Unchained

Context: reimplementing Lean 4 in Lean

Problem: some imperative C++ was hard to translate, the do notation had to be used

Idea: 

• implement some "imperative lean" with a new syntax
• model effects as monad transformers: mutation becomes State, return becomes Except monad, for in / break / continue become ExceptT + fold + ExceptT

It was first implemented as a macro in Lean.

Consequences:

• "invisible destructive updates"
• intensively used in Lean 4 but also in 31 out of 43 repositories, people are even starting to use it with the identity monad

Fusing industry and academia at Github

Semantic is a tool which can understand 9 targets languages  (no Haskell yet because the syntax is a bit complex, and there are less users than ruby :-)) and:

• helps make a table of contents in PR
• provides code navigation. This is a high traffic service, no issues or outages

4 case studies in how academia helped:

 1. parsing: they are many parsers, one for each language. Running native tooling is not maintainable. tree-sitter is an incremental, error-tolerant parser. The grammar is in a JavaScript DSL. It gives a consistent API. It is based on GLR parsing, sufficiently expressive for Ruby and fast enough for Github

 2. syntax: can we share syntax types? Yes with a data types a la carte approach, including the case where the code can't parse. The team implemented fast-sum, an "open union" record to work with > 140 syntax nodes for Typescript.

 3. diffing: can we have syntax-aware diffing to get better diffs? Using recursion schemes helped here because diffing is a recursive operation

 4. program analysis: understand programs!

    Implementing this necessitated a new effects library to mix several state effects + non-determinism => fused-effects

Difficulties:

• a la carte syntax is a bit imprecise
• build times, editor tooling
• Generic programming is hard

Successes:

• 30k req/min -> one bug one day because of a crash in the GHC event loop (because of one particular issue with Dell servers)
• tree-sitter became foundational
• recursion schemes work great
• algebraic effects are awesome

Modelling probabilistic models

A probabilistic model is aa set of relationships between random variables. For example a linear regression. We can use it in 2 ways

• simulation: to simulate some outcome
• inference: to compute the model parameters based on the observations

ProbFX is a Haskell library doing this elegantly. The models are:

• first-class citizens
• compositional
• typed

Example

HMM: Hidden Markov Model -> takes a transition model, an observable model for one node and replicates it to get a chain. This can be used to model an epidemic with the the SIR model (susceptible / infected / recovered).

Constraint-based type-inference for FreezeML

'70 Hindler-Milner type inference (algorithm W)

'80 constraint-based type system and inference (more extensible than algo W). Pratically used by GHC

'90 ML with first-class polymorphism (supporting forall a. [a] -> [a], polymorphic instantiation forall b. b -> b/a) -> large design space

'20 FreezeML tries to use algorithm W, focuses on simplicity

single :: forall a. a -> [a], id :: forall b. b -> b

what is single id?

FreezeML uses "freezing" to distinguish the 2 cases:

  single id : [a -> a]

  single |id| : [forall b. b -> b]

Linearly Qualified Types: Generic inference for capabilities and uniqueness

A linear function 'a %1 -> b' should be read as "if the function is consumed exactly once then the resource is consumed exactly once". When your code requires a linear function then you can pass a resource to that function and you know that it will be used safely

Problem: some simple cases are still quite ugly to implement

swap :: Int -> Int -> MArray a %1 -> MArray a

swap i j as =

  let

    !(as, Ur ai) = get i as

    !(as'', Ur aj) = get j as'

    as''' = set i aj as''

    as'''' = set j ai as''''

  in

    as''''

Idea: use GHC constraints (and define "linear constraints")

swap :: RW n %1 => Int -> Int -> MArray n a -> () < RW n

swap i j as = let

  !Ur ai = get i as

  !Ur aj = get j as

  !() = set i aj as

  !() = set j ai as

  in ()

newMArray :: Int (MArray a %1 -> Ur b) %1 -> Ur b

fromList :: Linearly %1 => [a] -> Array a

fromList as = do

  let arr = newArray (length as)

  let arr' = foldr (uncurry set) (zip [1..] as)

  freeze arr'

Haskell Symposium Day 1

Keynote: Cause and effects

This was mostly a talk about "Why I fell in love with Haskell and effects" and a QandA session around fused-effects.

Principle of least privilege: using Alternative instead of Maybe gives you additional power. Because then you can use List, NonDeterm etc... Just require what you need and not more.

Question: checked exceptions can be painful. Did you feel that pain?

Answer:

• one possibility: one error type to rule them all -> bad because coupling
• one effect per error type: annoying to track
• good: prism to extract a specific type out of a global error type. Note: we can do the same thing with lenses and State where we project only the state we need

Question: what about purity? what about having to lift?

Answer: purity / impurity is not so much the question but value vs computation is more relevant.

        For example when getting results if we get a value we get the "least privileged entity" in a sense

Functional Architecture open space

This was not part of the Haskell symposium but I had the opportunity to discuss functional architectures around:

• writing modular applications with records of functions (I quickly introduced registry)
• are large architectures still functional? (cf "turning the database inside out" and what is done at Standard Chartered with relational data as data structures)
• the pitfalls of domain modelling (we traded some examples)

Kudos to Mike Sperber for organizing this!

A Totally Predictable Outcome: An Investigation of Traversals of Infinite Structures

Traversable functors have been fully characterized as being polynomial functors.

But this proof only works in a finitary setting! What about Haskell with its infinite lists?

For example we cannot traverse an infinite list with Maybe because we need to know if there is a Nothing in the list at some stage.

Short answer: infinite traversals are productive iff they use "Predictable Applicative functors".

newtype Later a = Later a deriving (Functor, Applicative)

predictable :: Later (f a) -> f (Later a)

There are more Predictables than Representables (ex Writer)

There are Predictables that are not Applicatives

There are Predictables that are not strictly positive

The paper explores all of this including the traversal of bi-infinite lists where you can infinitely append elements on both ends!

Open Transactional Actions: Interacting with non-transactional resources in STM Haskell

We want to be able to use IO in STM Haskell. Open Transactional Actions allow this:

newtype OT a

liftIO :: IO a -> OT a

onCommit :: IO () -> OT ()

onAbort :: IO () -> OT ()

abort :: OT a

runOT :: OT a -> STM a

```

Once you have described what it means to commit and abort you can mix IO and STM resources.

Examples:

• file access with file locks
• unique id generator
• concurrent hash set
• concurrent linked list

Haskell / OCaml symposium Day 2

Keynote: Industrial strength laziness

Can we build and publish about tools?

Publishing challenges:

• expert users are expensive
• inexperienced programmers are only one target group
• how to do user studies well
• what we can measure might not be the most relevant to practice. "my refactoring does not introduce bugs" is good but not the only thing
• maintenance of tools gives no tenure
• maintenance takes a lot of time (GHC churn etc...)

Some dreams

Dream 1: context aware editor for actions. For example Scala and .

Dream 2: incremental feedback

Dream 3: Haskell debuggers

Dream 4: Add typeclass laws to typeclass definitions -> this gets us automated refactorings! and we can generate tests

Dream 5: Calculate programs (cf Idris with specification / case splitting), better integrate Liquid Haskell

Dream 6: Extensible documentation (inspired by scribble) to add diagrams for example. Better integration of tutorials

Dream 7: Static semantics for software evolution -> checking API compatibility

Dream 8: How should big teams build big applications with Haskell?

Make an impact

Pay attention to what other communities value. Example design patterns, we can still some in Haskell As a high-pain tolerant community we need to attract low-pain tolerant people

The Haskell Foundation

• funding CI for GHC
• the Haskell Error Index. This made to support other tools, like Cabal, Stack, HLS, etc...
• security advisories: as a data source for cabal, dependabot. To ease ISO 27001 certification
• the haskell interlude podcast
• the haskell optimisation Handbook (organised by Jeffrey Young -  from IOG)
• support the community process and audit of the "lottery factor" (better name than the "bus factor" IMO)
• technical Working group, stability working group

Questions:

How to help with accessibility of the language?

• filter out the "good" libraries
• have a culture of using GHC2021 as the default extension
• promote only 2 books on the front page

Suggestion: large scale refactoring tools, have hints of performance optimisations

Suggestion: talk to M. Snoyman to pick up the case studies they did

How to help people get on board with developing on GHC, HLS etc...?

SPJ: how can we push existing programs to use LiquidHaskell?

Efficient “out of heap” pointers for multicore OCaml

A page table classifies if a pointer is inside the major heap. People starting storing pointers to outside the OCaml heap. In OCaml 4.14: speed-up GC with prefetching.

This works shows that a page table can speed-up marking even with concurrency and have other uses: huge pages, etc...

Memo: an incremental computation library that powers Dune

Memo supports Internal incremental building in dune (OCaml build tool) with

• parallelism
• memoization: we don't want to re-read a file many times
• let* is a bind in OCaml
• errors are de-duplicated (it kind of memoize / de-duplicate errors and keeps stack traces)
• it is incremental and if errors are fixed they disappear

Dune is not yet used at Jane Street because 30 millions of lines of code and Dune is not yet fast enough (the graph is too big).

Problem: what about cycles / deadlocks in the build graph? Not trivial to detect deadlocks with concurrency

Solution: use incremental graph detection. The naive solution doesn't scale. Bender 2015 provides a solution and a working library (even proved in Coq). It is in O(m (square-root m)) which is not yet optimal for Jane Street.

Idea: skip the reading edges (still took 35% of the build time)

Idea: check only paths that lead to blocking edges (now execution time is negligeable - but no proof of correctness yet)

Further work: graph flattening, bottom-up/top-down traversal (start from the leaves), storing memoization tables on disk, generalize to other concurrency monads.

Stack allocation for OCaml

Short lived allocations are cheap but not free:

• space is not reused quickly
• poor L1 cache usage
• GC advances towards the next release

We could write all our code in the same function, but how can we safely use several functions? 

Rust with lifetime annotations allows this but is syntactically overweight. It can be polymorphic and higher-order functions become higher-rank which means that type inference stops working.

This work uses a different approach with modal types:

• local or global applied to variable bindings
• local bindings never escape their region
• global bindings can never refer to stack-allocated values
• less expressive than region variables but simpler

The modalities show in the function types

  string -> unit vs local_ string -> unit

Functions can also return values on the stack. They get allocated on the parent stack frame

Examples

val iter : local_ ('a -> unit) -> 'a list -> unit

  the closure can not be captured by iter

  let count = ref

  List.iter ... (use count)

  in that case the count ref can be local because it won't escape iter

What about tail-recursion? To make sure it works we need to make sure that we don't grow the stack.

What about currying? the first iter is not the same as val iter : local_ ('a -> unit) -> ('a list -> unit)

it more like val iter : local_ ('a -> unit) -> local_ ('a list -> unit) so eta expansion might be necessary

What about the with_resource pattern?

val with_file : filename: string -> local_ (local_ filehandle -> 'a) -> 'a

This means that this simple addition to the type system could be useful in other contexts (proving that the file handle is not captured, modifying mutable arrays etc...)

Continuous monitoring of runtime events

Run health checks in production, do some analysis. New in OCaml 5.0

• most probes in the default runtime
• APIs (OCaml, C)
• controllable with env. variables
• very low overhead

Implemented with:

• per-domain ring buffers: one producer / many consumers (this means that events will be overwritten and can be missed)
• file backed memory mapped so accessible from outside processes

30ns when enabled, 0.8% in retired instructions

Next:

• new runtime probes
• custom events
• more work in libraries and tooling

Programming is (should be) fun!

Programming is not coding

• there's often no good specification to meet, just a vague understanding
• joint exploration of achievable specifications, possible implementations
• it rarely relies on physical parameters for mechanical tolerance etc...
• we are limited by our ideas and the arising complexity

This means that bugs are not just programming errors, they are an opportunity to learn:

• they should have names and mitigation strategies
• it's ok to have bugs. We start with simple assumptions and we explore the space of what's possible

Gerald shared some of his insights with Maxwell's equations, eval/apply in a Scheme interpreter, electric circuits, classical mechanics or how they (re)discovered automatic forward differentiation with a colleague with the use of differential objects

Philosophy is also never far from programming with questions about: referent expressions, identity, mutation, the Ravens paradox, etc...

In summary programming is fun because it brings :

• the pleasure of analogies
• philosophical contemplation
• the pleasure of debugging, of the hunt
• the pleasure of discovery of good ideas
• the pleasure of clarity: make difficult subjects clear

and it's even better when we share it as fre (libre) software: cf gnu.org/philosophy/free-sw.html

A better "add" operator for HLists

At Haskell eXchange 2019, Yves Parès was presenting his “porcupine” library, a library to help scientists run data pipelines using the power of Haskell’s arrows. At some stage, he said, “you know if you’re using a ‘records’ library, like Vinyl, you have to build your HList by appending RNil at the end”. And I thought: No!

This is a very small thing that has been bugging me for some time. If I want to build a HList, why do I have to append HNil at the end? As soon as I’m appending 2 things together to form an HList the whole type should be determined, isn’t it? Let’s work on a bit of code.

Here is the standard definition of a HList in Haskell:

data HList (l::[*]) where
  HNil  :: HList '[]
  HCons :: e -> HList l -> HList (e ': l)

-- example
myHList :: HList [Int, Text]
myHList = HCons 1 (HCons "Hello" HNil)

I can define a :+ operator to make the operation of appending an element a bit nicer:

infixr 5 +:
(+:) :: a -> HList as -> HList (a : as)
(+:) = HCons

myHList1 :: HList [Int, Text]
myHList1 =
     1
  +: "Hello"
  +: HNil

I can also define an <+> operator to append 2 HLists together:

-- :++ is a type-level operator (not defined here)
-- for appending 2 lists of types together (see the Appendix)

infixr 4 <+>
(<+>) :: HList as -> HList bs -> HList (as :++ bs)
(<+>) HNil bs = bs
(<+>) (HCons a as) bs = HCons a (as <+> bs)

list1 :: HList [Int, Text]
list1 = 1 +: "Hello" +: HNil

list2 :: HList [Double, Bool]
list2 = 2.0 +: True +: HNil

lists :: HList [Int, Text, Double, Bool]
lists = list1 <+> list2

All good so far, that’s a reasonable API. However we still need to specify HNil every time we create a new HList. Can we avoid it?

A more polymorphic operator

In order to avoid using HNil we need to have an operator, let’s call it <:, to know what to do when:

• adding one element to another: a <: b
• adding one element to a HList: a <: bs

But even better we should be able to:

• append 2 HList together: as <: bs
• append an element at the end of a HList: as <: b

We can already see that this operator can not be a straightforward Haskell functions, because the types of its first and second arguments are not always the same. Annoying. Wait, there’s a tool in Haskell to cope with variations in types like that: typeclasses!

infixr 5 <:
class AddLike a b c | a b -> c where
  (<:) :: a -> b -> c

instance {-# OVERLAPPING #-} (asbs ~ (as :++ bs)) =>
  AddLike (HList as) (HList bs) (HList asbs) where
  (<:) = (<+>)

instance (abs ~ (a : bs)) => AddLike a (HList bs) (HList abs) where
  (<:) = (+:)

instance AddLike a b (HList [a, b]) where
  (<:) a b = a +: b +: HNil

instance (asb ~ (as :++ '[b])) => AddLike (HList as) b (HList asb) where
  as <: b = as <+> (b +: HNil)

This AddLike typeclass will deal with all the cases and now we can write:

a = 1 :: Int
b = "hello" :: Text
c = 2.0 :: Double
d = True :: Bool

ab = a <: b
bc = b <: c

abc = a <: bc
bca = bc <: a

abcd = ad <: cd

That’s it, one operator for all the reasonable cases.

Appendix

Here is the full code:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE PolyKinds #-}
{-# OPTIONS_GHC -fno-warn-unticked-promoted-constructors #-}

module AddLikeApi where

import Protolude

data HList (l :: [Type]) where
  HNil  :: HList '[]
  HCons :: e -> HList l -> HList (e ': l)

myHList :: HList [Int, Text]
myHList = HCons 1 (HCons "Hello" HNil)

infixr 5 +:
(+:) :: a -> HList as -> HList (a : as)
(+:) = HCons

myHList' :: HList [Int, Text]
myHList' =
     1
  +: "Hello"
  +: HNil

-- * Appendix

infixr 4 <+>
(<+>) :: HList as -> HList bs -> HList (as :++ bs)
(<+>) HNil bs = bs
(<+>) (HCons a as) bs = HCons a (as <+> bs)

infixr 5 <:
class AddLike a b c | a b -> c where
  (<:) :: a -> b -> c

instance {-# OVERLAPPING #-} (asbs ~ (as :++ bs)) => 
  AddLike (HList as) (HList bs) (HList asbs) where
  (<:) = (<+>)

instance (abs ~ (a : bs)) => AddLike a (HList bs) (HList abs) where
  (<:) = (+:)

instance AddLike a b (HList [a, b]) where
  (<:) a b = a +: b +: HNil

instance (asb ~ (as :++ '[b])) => AddLike (HList as) b (HList asb) where
  as <: b = as <+> (b +: HNil)

type family (:++) (x :: [k]) (y :: [k]) :: [k] where
  '[]      :++ xs = xs
  (x : xs) :++ ys = x : (xs :++ ys)

-- examples
list1 :: HList [Int, Text]
list1 = 1 +: "Hello" +: HNil

list2 :: HList [Double, Bool]
list2 = 2.0 +: True +: HNil

lists :: HList [Int, Text, Double, Bool]
lists = list1 <+> list2

a = 1 :: Int
b = "hello" :: Text
c = 2.0 :: Double
d = True :: Bool

ab :: HList [Int, Text]
ab = a <: b

bc :: HList [Text, Double]
bc = b <: c

cd :: HList [Double, Bool]
cd = c <: d

abc' :: HList [Int, Text, Double]
abc' = ab <: c

abc :: HList [Int, Text, Double]
abc = a <: bc

abcd :: HList [Int, Text, Double, Bool]
abcd = ab <: cd

Processing CSV files in Haskell

This blog post is the result of a little experiment. I wanted to check how hard it would be to use Haskell to write a small program to help me solve a “real-life” problem. I have always been pretty bad at doing accounting for the family, with a mix of Excel spreadsheets filled with random amounts and dates.

In order to improve our budgeting I decided to give a go at an application called YNAB “You Need A Budget”. Many applications of that nature require you to import your bank transactions in order to really precise about your income and expenses. And now we have an IT problem, right at home. I have, for historical and practical reasons, a bunch of different bank accounts. Of course not one of them exports my transaction data in a format that’s compatible with what YNAB expects.

Is this going to stop a software engineer? No, a software engineer and devoted householder would find the right combination of awk and sed to do the job. But I am also a Haskeller and I wonder how difficult it is to solve that task using Haskell. More precisely I want to gauge what amount of Haskell knowledge is required to do this. Since I am not a beginner anymore (yay!) this is a bit biased but I think that it is very important to do our best to remember we were once beginners.

In the following sections I want to explain what I did and give some pointers to help beginners getting started with Haskell and being able to code a similar application:

1. set-up the project
2. create data types
3. decode CSV lines
4. write tests for the decoders
5. parse and process a full file
6. parse options from the command line
7. tie it all together in an application

For each section I will recommend some things to start learning first and some others to learn later.

The full code can be found here.

Setting-up a Haskell project

This is something I didn’t have to do from scratch since I already had the Haskell build tool stack installed on my machine. From now on I am going to assume that you have installed stack already. Creating your first Haskell project is not that obvious. You need to learn how to declare a few things according to the “Cabal” format:

• where to put your sources, your tests?
• are you going to produce a library, an executable?
• which libraries do you need as dependencies?

Fear not, there is a great Haskell command-line tool helping you with all of this: summoner. Go stack install summoner. Just follow the prompts and create your first project in no time, with the corresponding Github project and CI configuration. I think this is the best way to get started on some immediate coding. You will have plenty of time later to learn Cabal/Stack/Hpack/nix and become a pro at setting up projects.

Funny enough, this step took me a bit of time. Indeed I am frequently using the ghci REPL (with stack ghci, we will talk about it later) when programming in Haskell and I have a global set-up for it in .ghci

:set prompt "λ> "
import Prelude

:def hoogle \str -> return $$ ":!hoogle --count=50 \"" ++ str ++ "\""
:def pointfree \str -> return $$ ":!pointfree \"" ++ str ++ "\""
:def pointful \str -> return $$ ":!pointful \"" ++ str ++ "\""

This configuration file gives me a cute ghci prompt but it also gives me access to some very useful Haskell tools like hoogle for searching type signatures, right in my REPL. Unfortunately when I started my ghci session, stack informed me that it didn’t know about Prelude. The reason is that the project created by summoner is created with a custom prelude which removes the standard Prelude from the search path. Custom preludes are definitely important to know in Haskell but they are also something which is best left for a bit later, when you want to get serious about Haskell development and make sure you are using “safe” functions as much as possible (no head :: [a] -> a for example). In my case I decided to switch to another custom prelude, Protolude.

Learn now

• install stack
• install summoner
• create a project
• start stack ghci
• the Relude prelude and its main functions

Learn later

• the cabal format
• the hpack format, as an alternate format
• the cabal or stack commands for building/testing a project
• other custom preludes: protolude, classy-prelude

Create data types

This is a real cool part of Haskell, cheap (to create) and powerful data types. For this application we want to have a datatype representing the input data and a data type for the output data. Wait, actually no. We just need a data type modelling what it means to be a transaction for YNAB and ways to:

• create values of that type from a CSV line (next section)
• output a CSV line from values of that type from a CSV line (next section)

Each transaction (or line in a ledger) must contain at least a date, an amount, a payee and possibly a category.

import           Data.Text (Text)
import           Data.Time (Day)

data LedgerLine = LedgerLine {
  date      :: Day
, amount    :: Amount
, reference :: Reference
, category  :: Maybe Category
} deriving (Eq, Show)

data Category = Category Text
  deriving (Eq, Show)

data Reference = Reference Text
  deriving (Eq, Show)

data Amount = Amount Double
  deriving (Eq, Show)

Here we are re-using some standard data types like Text and Day but wrapping them with custom data types. This is quite useful because we can’t make the mistake of putting a Reference into a Category for example. This also better documents the LedgerLine fields. The deriving clauses give us ways to display and compare values out of the box (think toString and equals in Java).

My actual datatypes are a bit more complicated:

data LedgerLine = LedgerLine {
  _date      :: Maybe Day
, _amount    :: Amount
, _reference :: Reference
, _category  :: Maybe Category
} deriving (Eq, Show)

newtype Category = Category Text
  deriving (Eq, Show, IsString)
  deriving newtype FromField
  deriving newtype ToField

newtype Reference = Reference Text
  deriving (Eq, Show, IsString)
  deriving newtype FromField
  deriving newtype ToField

newtype Amount = Amount Double
  deriving (Eq, Show)
  deriving newtype FromField
  deriving newtype ToField
  deriving newtype Num

First of all some CSV lines might not have a date yet if the transactions have been created today. Then:

• I use newtype instead of data for Category, Amount, Reference to avoid paying the cost at runtime of wrapping a type
• an IsString instance is used for Category and Reference to be able to use strings directly in tests (to write "restaurant" instead of Category "restaurant")
• I am declaring a Num instance to be able to +, negate,… amounts later as if they were Doubles
• the field names are prefixed with _ to avoid potential clashes with variables having similar names amount, category etc…
• there are some instances for FromField and ToField for… see the next section :-)

Learn now

• how to create data types and the difference between data and newtype
• typeclasses and instances: Show, Eq, Num,…

Learn later

• record fields, how they appear as top-level functions and how to avoid clashes
• different ways of deriving instances for data types
• IsString for text-like data types

Decode a CSV line

This is becoming more involved. We need to find a library knowing how to parse CSV lines. The standard library for CSV files in Haskell is cassava. Like many other libraries for encoding / decoding data structures it uses type classes:

• FromField to specify how to parse a value in a CSV column and transform it to a data type value
• FromNamedRecord to specify how to parse a full CSV row and how to assemble the parsed values

In our case we want parse at least 3 formats, from different banks: Commerzbank, N26, Revolut so we need an auxiliary data type:

data InputLedgerLine =
    CommerzbankLine LedgerLine
  | N26Line LedgerLine
  | RevolutLine LedgerLine
  deriving (Eq, Show)

and we can start defining parsers for each format:

instance FromNamedRecord InputLedgerLine where
  parseNamedRecord r =
        parseCommerzBank
    <|> parseN26
    <|> parseRevolut

    where
      parseCommerzBank = fmap CommerzbankLine $$
            LedgerLine
        <$$> (fmap unCommerzbankDay <$$> r .: "Transaction date")
        <*> r .: "Amount"
        <*> r .: "Booking text"
        <*> r .: "Category"

      parseN26     = panic "todo N26"
      parseRevolut = panic "todo Revolut"

newtype CommerzbankDay = CommerzbankDay { unCommerzbankDay :: Day } deriving (Eq, Show)

instance FromField CommerzbankDay where
  parseField f = CommerzbankDay <$$>
    parseTimeM True defaultTimeLocale "%d.%m.%Y" (toS f)

This is whole jump in complexity all of a sudden, but also quite some power! Think about it, in a few lines of code we have:

• specified how to parse rows for the Commerzbank file format
• specified how to parse each field and what are the field names in the CSV file
• specified a date format for dates like 26.08.2019
• specified that other parsers must be tried if the first parser fails (when we are parsing another format)

I am not going to unpack everything here but give you some pointers what to learn.

Learn now

• cassava for parsing CSV files
• what is anApplicative how to parse data types with MyData <$> p1 <*> p2 <*> p3
• what is an Alternative to try another parser with <|>
• the Data.Time library to parse dates and times
• why newtypes are sometimes necessary to tell Haskell to use a specific type instance (this is why I introduced a special CommerzbankDay here)

Learn later

• other parsers: attoparsec, megaparsec

Decode a CSV line

Pretty cool, if you understand how the parsers in the above section work, you should be able to open a GHCi session and try them out (read the doc of the cassava library for the decodeByName function).

λ> import Data.Csv
λ> let commerzbankHeader = "Transaction date,Value date,Transaction type,Booking text,Amount,Category
λ> let line = "30.08.2019,30.08.2019,debit,\"mobilcom-debitel Kd\",-15.00,Home Phone and Internet"
λ>
λ> fmap snd $$ decodeByName @InputLedgerLine $$ commerzbankHeader <> "\n" <> line
Right [CommerzbankLine (LedgerLine {
  _date = Just 2019-08-30,
  _amount = Amount (-15.0),
  _reference = Reference "mobilcom-debitel Kd",
  _category = Just (Category "Home Phone and Internet")})]

It works!

Perhaps we still want to make sure this code will still work if we make further modifications, so it is time to… write tests! There are many alternatives for writing tests in Haskell and I have my own preferences :-). I reached for my own library, registry-hedgehog which is a layer on top of several libraries:

• hedgehog for writing property-based tests
• registry for assembly data generators without using typeclasses
• tasty-hedgehog for executing hedgehog properties as Tasty tests
• tasty-discover to automatically find tests in files and assemble them into a large suite

This is totally overblown for that little project since I haven’t written a single property so far. But I know the API well and like it since I made it to my taste :-). What do the tests look like?

test_parse_commerzbank_with_date = test "we can parse the commerzbank format with a date" $$ do
  let line = "30.08.2019,30.08.2019,debit,\"mobilcom-debitel Kd\",-15.00,Home Phone and Internet"
  let result = fmap snd $$ decodeByName (toS $$ unlines [header, line])

  result === Just (CommerzbankLine $$ LedgerLine {
      _reference = "mobilcom-debitel Kd"
    , _date = Just (fromGregorian 2019 8 30)
    , _amount = Amount (-15.0)
    , _category = Just ("Home Phone and Internet")
    })

A test is simply a piece of text describing the intention, some action (decodeByName) and an assertion (with ===). This is very similar to what I tried on the command line earlier.

Learn now

• hspec: an easy library to start writing unit tests

Learn later

• quickcheck/hedgehog: for writing property tests
• tasty: a test framework dedicated to the structuring and the running of test suites
• hspec-discover/[tasty-discover]: to avoid having to manually create test suites from tests in test modules
• registry-hedgehog: for an alternative to typeclasses when creating data generators

Parse and process a full file

Now we are entering serious territory. When we parse files we have to be conscious about:

• memory usage: it is not advised to read the full content of a file before processing it
• resource usage: files must be properly closed after use to avoid leaking resources

None of this really counts for my application since the files I am processing are quite small (< 1 Mb) and the application exits right after processing. Anyway I wanted to see if it was as easy to do the “right thing” rather than go for a quick and dirty solution.

There is a beautiful library for streaming data in Haskell, streaming, which I used before. I am in luck since someone created a streaming-cassava library to stream rows decoded by cassava. It provides a function decodeByName which is the equivalent of Data.Csv.decodeByName I have used in the tests but it now operates on “streams” of data. A similar function, encodeByName, also exists to encode values to CSV rows. That’s fine ut we also need to read and write those rows. I am going to decompose the whole processing in 6 parts and explain what are the data types involved in each step:

1. read an input file to get a ByteString m () which is a stream of bytes
2. decode the rows with decodeByName to get a Stream (Of InputLedgerLine) m ()
3. deal with decoding errors
4. process the input ledger lines and transform them to LedgerLine
5. encode the lines as CSV rows with encodeByName to get back a stream of bytes ByteString m ()
6. write those bytes to an output file

Read a file as a Stream of bytes

Again we are lucky, the streaming-with library gives us a function, withBinaryFileContents to read the contents of a file as a stream:

withBinaryFileContents filePath $$ \(contents :: ByteString m ()) ->
  doSomething contents

Not only the contents are being streamed using the ByteString m () data structure, but also withBinaryFileContents is going to make sure the file is closed when the processing (doSomething) is finished, even if there are exceptions.

Decode the lines

The Streaming.Cassava.decodeByName function does the job for us. It takes a ByteString m () and returns a Stream (Of InputLedgerLine) m (), provided we have a FromNamedRecord typeclass instance for InputLedgerLine. Now is a good time to talk about those streaming data types: ByteString and Stream.

What is a stream of data?

Indeed I owe a bit of explanation on the “streaming” types: ByteString m r and Stream (Of a) m r. Why so many types parameters to represent streams? I will just explain Stream here because ByteString m r is just a specialization of Stream when we are streaming bytes.

NOTE: The ByteString name in Haskell (found in Data.ByteString or Data.Lazy.BytesString) could make you believe that we are dealing with strings and their underlying bytes. It is better to think about it as just a collection of bytes. Same thing for Data.ByteString.Streaming.ByteString m () but streaming bytes.

So, what is a Stream (Of a) m r? If you run :info Stream in GHCi, you will more or less read (I’m simplifying a bit here) that it is either:

• Return r: returning a value r, nothing more to do. If you use the fmap operation you can “map” this value to something else (so Stream is a Functor)
• Effect (m (Stream (Of a) m r)): creating a stream with the effect m. For example m = IO when we read from a file
• Step (Of a (Stream (Of a) m r)): producing a value a and another stream of values: “what comes next”. Think about Of as pair where the first element is strictly evaluated

I found it a bit confusing at first because of the various type variables (“do we really need a type for the return value? Yes we do”) but after a while I realized that it was the simplest thing to do to stream values and already super-powerful!

Deal with decoding errors

I think this part is difficult for beginners. I wrote that Streaming.Cassava.decodeByName was returning Stream (Of InputLedgerLine) m (). No error in sight there. How are the parsing errors signaled then? On the monad m. The decodeByName full signature is:

decodeByName :: (MonadError CsvParseException m, FromNamedRecord a) =>
  ByteString m r -> Stream (Of a) m r

Meaning that the monad m must support errors which are CsvParseException. For example m can be ExceptT CsvParseException n where n is another monad. On one hand this is quite nice because we get back a data type Stream (Of a) m r where we don’t have to think too much about errors, it is mostly a stream of parsed values. It is easier to work with than Stream (Of (Either CsvParseException a)) m r for example. On the other hand the constraint on m is going to propagate to the rest of the application and things can become awkward for example if another part of the application is requiring MonadError OtherException m. Then the compilation errors can become confusing and it is not immediately obvious how the error types can be aligned. In this application we nip the problem in the bud by doing to following:

• catch the error as soon as possible
• rethrow it as an exception in IO

rethrow :: (Exception e, MonadIO m) => ExceptT e m a -> m a
rethrow ma = do
   r <- runExceptT ma
   case r of
     Left e  -> throwIO e
     Right a -> pure a

rethrow assumes that we are working with values a in a monad which is ExceptT e m. It catches the errors of type e and, assuming that m is capable of doing IO it is going to throwIO the errors. What we do here is essentially transforming a constraint MonadError CsvParseException m into MonadIO m. We lose a bit in terms of abstraction, m is less general than it could be. But we gain in terms of inter-operability with other parts of the application.

Well, that is, if we can even apply rethrow on our stream! What we need is a function Stream (Of a) m r -> Stream (Of a) n r where m is ExceptT CsvParseException n. This function exists in much more general cases than Stream. It is called hoist. This function works on data types of the form t m a (t = Stream here) and is defined in the mmorph library. This is probably the most complicated transformation of this whole project. However situations with nested “monads/containers” (t and m) appear quite frequently in Haskell so after a while you will reach for hoist quite naturally.

What if I hadn’t done any of this?

The MonadError CsvParseException m constraint would have “bubbled-up” to the top-level, up to the main function where Haskell would have asked me to do something like runExceptT to make sure I dealt with parsing errors.

Process values

The values we read are of type InputLedgerLine but we want to a single format LedgerLine. We are not that far since each parser is already normalizing the input values to a LedgerLine. We only need to extract that line from each InputLedgerLine case:

toLedgerLine :: InputLedgerLine -> LedgerLine
toLedgerLine (CommerzbankLine l) = l
toLedgerLine (N26Line l)         = l
toLedgerLine (RevolutLine l)     = l

Now, how can we use toLedgerLine to convert the lines in a Stream (Of InputLedgerLine) m () to get Stream (Of LedgerLine) m ()? By using the map function in Streaming.Prelude:

import Streaming.Prelude as SP

let decoded = decodeByName contents :: Stream (Of InputLedgerLine) m ()
let processed = SP.map toLedgerLine decoded :: Stream (Of LedgerLine) m ()

I really encourage you to read the documentation on Streaming.Prelude because you will find there most of the operations you generally use on lists but this time on streams.

Encode the lines as CSV

Again streaming-cassava helps us here. encodeByName encodes our values, Stream (Of LedgerLine) m () to a ByteString m (), provided we have a ToNamedRecord instance:

instance ToNamedRecord LedgerLine where
  toNamedRecord (LedgerLine date amount reference category) =
    namedRecord [
       "Date"   .= date
     , "Amount" .= amount
     , "Payee"  .= reference
     , "Memo"   .= category
     ]

Since all our fields have ToField instances which are derived automatically because they are newtypes of well-known types like Text and Double, we just have to specify the name of the fields in the output file, so that cassava knows in which column to put the values.

Write a Stream to a file

streaming-with gives us writeBinaryFile which takes a ByteString m () and writes to an output file, again making sure that resources are properly cleaned-up even if there is an exception in the meantime.

To sum-up all those transformations in a block of code:

processAll =
  withBinaryFileContents inputFilePath $$ \contents -> do
    let decoded   = decodeByName contents
    let processed = Streaming.map toLedgerLine $$ hoist rethrow decoded
    let encoded   = encodeByName ynabHeader processed
    writeBinaryFile outputFilePath encoded

Thanks to all those libraries we have a nice isolation of responsibilities, and guarantees about memory and file handle usage!

Learn now

• all the type classes and functions of cassava
• the streaming, streaming-bytestring, streaming-with libraries to stream data
• the rudiments of monad transformers like ExceptT

Learn later

• other streaming libraries: there are many great alternatives (but slightly more complex) to streaming: conduit, pipes, streamly
• the ResourceT monad transformer to deal with resources
• the Managed monad to simplify situation where the withXXX pattern is nesting too many calls
• different ways of dealing with errors in Haskell

Parse options from the command line

At the minimum we need to be able to read the name of the input file. This can be done with System.getArgs :: IO[String] and would be sufficient for this application. However you are going to need more elaborate parsing of command line options for a non-trivial CLI application. I have used a very well-known library for this: optparse-applicative.

With this library, we define a data type for the data we want to read from the command line:

data CliOptions = CliOptions {
  inputFile  :: Text
, outputFile :: Maybe Text
} deriving (Eq, Show)

The output file is left optional, since we can provide either a hard-coded name for the ouput file result.csv or append a piece of text to the input file name. The parser for CliOptions looks like this:

cliOptionsParser :: Parser CliOptions
cliOptionsParser = CliOptions
   <$$> strArgument
       ( metavar "INPUT FILE"
      <> help "Input CSV file" )
   <*> option auto
       ( long "output-file"
      <> short 'o'
      <> value Nothing
      <> help "Output CSV file" )

This style of parser definition is very similar to the one we used for FromNamedRecord to parse CSV fields. It relies on the notion of an Applicative (hence the library name) and on a series of helper functions to specify the options:

• strArgument parses a string given as an argument (so it is not optional)
• option parses an option (starting with -- on the command line) and the exact type of parser is auto meaning that it will parse everything with a Read instance

You can also see some additional information, like the option name (long and short) for the output file. This information is used both for parsing and for documenting the command line options. Talking about documenting, how do we provide a --help option? optparse-applicative gives a way to “wrap” a Parser with more information

defineCliOptions :: ParserInfo CliOptions
defineCliOptions =
   info (cliOptionsParser <**> helper) $$
   header "ledgit - massage ledger files" <>
   progDesc "Transform a CSV ledger file into a suitable YNAB file"

In defineCliOptions we enrich the CliOptions with a helper option and provide additional information to our parser with “modifiers”:

• progDesc adds a text description of the program displayed under the “Usage” section showing a summary of the options
• header adds an additional header when we display the help
• those 2 modifiers are being “appended” into one with <> (yes they form a Monoid)

While the whole library is quite powerful, there is quite a lot to explain if you really want to understand how it works: parsers, Applicative, Monoid, Read,… Yet I more or less took the examples from the documentation, changed a few things and it worked immediately.

Learn now

• the optparse-applicative library

Learn later

• other options libraries: options, cmdargs

Tie it all together

In reality you could put all the code in one Haskell file (you could even create a stack script) and you would be done. For fun I decided to create small components to isolate the different pieces of the application, using “records-of-functions”:

• Data.hs contains all the data types + the CSV encoders/decoders
• Importer.hs contains the Importer component tasked with reading the file and decoding it
• Exporter.hs contains the Exporter component which takes a stream of lines and outputs it to a file
• App.hs just connects the 2
• Ledgit.hs calls the options parser and create the App

The Importer

Let’s have a closer look at those components. The Importer is defined as:

data Importer m = Importer {
  importCsv :: (Stream (Of LedgerLine) m () -> m ()) -> m ()
}

It is kind of weird. Instead of just exposing an interface like importCsv :: Stream (Of LedgerLine) m () returning the decoded lines, it takes a “consumer” of Stream (Of LedgerLine) m () and executes it. This is because of a limitation of the Streaming library and the libraries we have been using with so far.

The Streaming library does not support any resources management. The resource management (properly closing file handles) is done with withBinaryFileContents which take a function consuming the file contents. If we want to use that library and define a component we need to propagate the same pattern.

There is actually quite a profound principle at play here. In programming, some “things” can be either defined by how they are produced or how they are consumed. For example you can define the Maybe datatype by either

data Maybe a = Just a | Nothing

or

data Maybe a = forall b . ((a -> b), b)

In the second case you specify how to “consume” values that are Just a or values that are Nothing.

If you squint a bit you will also recognize a “continuation-like” type in importCsv :: (a -> r) -> r. The computer science literature is full of such transformations, from “direct style” to “continuation-passing style”. This is a lot of hand-waving, just to justify the weird shape of the Importer interface :-).

Otherwise you will notice that the Importer does not mention its “configuration”, there is no inputFilePath to read from in its interface. This is because this data will be provided by the wiring we do in Ledgit.hs.

The Exporter

Nothing special here, we take a stream of lines and export each of them to a file. Underneath the implementation is using the functions we have seen before: writeBinaryFile, encodeByName.

data Exporter m = Exporter {
  exportCsv :: Stream (Of LedgerLine) m () -> m ()
}

The App

The App just connects the 2 main components, its implementation is super-simple

data App m = App {
  runApp :: m ()
}

newApp :: Importer m -> Exporter m -> App m
newApp Importer {..} Exporter {..} = App {..} where
  runApp = importCsv exportCsv

The “wiring”

Now we need a way to make an App with its Importer, its Exporter and the CliOptions parsed from the command-line. For this we use the registry library and define a registry like so:

newRegistry :: CliOptions -> Registry _ _
newRegistry cliOptions =
     fun (newImporter @IO)
  <: fun (newExporter @IO)
  <: fun (newApp @IO)
  <: val cliOptions

We put all the values and components constructors into a Registry and later ask for an all-wired application:

runApplication :: IO ()
runApplication = do
  cliOptions <- execParser defineCliOptions
  let registry = newRegistry cliOptions
  let app = make @(App IO) registry
  runApp app

That’s it, registry automatically calls all the constructor functions and wires the App. You can also write this code by hand, there’s no real need to use registry for such a simple application.

Learn now

• learn about the Handler pattern

Learn later

There are many other ways to define and wire Haskell applications:

• MTL and monad transformers
• effect libraries: polysemy, fused-effects
• The ReaderT pattern
• registry

Summary

This blog post presents a simple Haskell application which can be seen as the “template” for many CLI applications. We have

• command-line options parsing
• “business” data types
• files input / output
• streaming
• encoding / decoding

There is nonetheless a learning curve which we should not under-estimate, we need to:

• know how to set-up a new project
• know how to compile, run tests, install the application
• know how to find relevant libraries in the Haskell ecosystem
• learn about data and newtype
• learn about type classes and instances
• be comfortable with the Applicative typeclass and combinators
• understand a minimum of monad transformers

I hope this blog post will contribute to making this learning curve less steep by giving pointers on things to start learning right, then other things to read / practice later.

Concluding thoughts

It occurred to me that being computer literate will be an important part of the “citizen-toolkit” in the future. There is no reason why we should not be able to access all of our data in the future through well-crafted APIs. When this happens, I hope someone will use Haskell and write a similar blogpost about REST access (or whatever API standard), blockchain auditing, security libraries etc…