Designing software in language that can't let you **reason about your code** is like building a house **without architect**. Fixing something afterward will be very hard. Very hard because you will not be able to **measure the impact of a change**.

We can use a very simple definition for **equational**

Designing software in language that can't let you **reason about your code** is like building a house **without architect**. Fixing something afterward will be very hard. Very hard because you will not be able to **measure the impact of a change**.

We can use a very simple definition for **equational reasoning**: replacing **equivalent expressions (the same value)**. Let's start with a short, rather uninteresting piece of code:

```
public static int Dummy1()
{
var x = 1;
var y = x++;
var z = y + y;
return z;
}
```

Try to think a little bit and ask yourself whether the following code will return the same value:

```
public static int Dummy2()
{
var x = 1;
var z = x++ + x++;
return z;
}
```

Let's continue with this one:

```
public static int Dummy3()
{
var x = 1;
var y = x++;
var z = y + x++;
return z;
}
```

Don't scratch your head, you are trying to understand something that is **very difficult to follow**. In fact, we are not used to this kind of **imperative thinking**. Things are even worse when **we mix pure code with side-effects**. Here it is:

```
private static int _k;
public static int Dummy4(int x)
{
var r = x * _k;
_k++;
return r;
}
public static int Dummy5()
{
var x = 5;
var y = Dummy4(x);
var z = Dummy4(x);
return y + z;
}
public static void Dummy6()
{
var d = Dummy5();
var dd = Dummy5();
Console.WriteLine(dd);
Console.WriteLine(_k);
}
public static void Main(string[] args)
{
Dummy6();
/*
25
4
*/
}
```

If we keep focusing on the `Dummy5`

function and try to reason about the code, we may judge that $y = z$. If we do remove $z$ to use $y$ only, the result of calling `Dummy5`

will be totally different (directly affecting Dummy6 and so on...).

```
private static int _k;
public static int Dummy4(int x)
{
_k++;
return x * _k;
}
public static int Dummy5()
{
var y = Dummy4(5);
return y + y;
}
public static void Dummy6()
{
var d = Dummy5();
var dd = Dummy5();
Console.WriteLine(dd);
Console.WriteLine(_k);
}
public static void Main(string[] args)
{
Dummy6();
/*
20
2
*/
}
```

Remember, we want to replace **equivalent expressions**. Unfortunately, we are not doing maths, in our case, we have to be sure that the expressions are free of **side-effects**. Let's say it, `Dummy4`

is not a function (in the mathematical sense) as it is not **pure**.

Pretty disastrous. Since we are **not controlling the side-effects**, we are forced to check the complete call tree. Now you realize that even if 90% of your code is pure, having a single side-effect in a leaf function **infects the whole tree**, resulting in an impure, top level function.

The big problems arise when you maintain a software that is relying on multiple libraries and a complex stack of **tightly coupled objects**. One day, your manager tell you to fix a bug. Reproducing this bug is easy: given a set of input comming from the client interface, **clicking on the same button twice does not produce the same output**. Enjoy having to ~~debug and~~ find the underlying side-effect.

Fortunately, escaping this situation is possible. It is a matter of **thinking differently**. We can't avoid side-effects as our program would be useless without them. Interacting with the **real world is mandatory** for our company: database access, console logging, API calls and so on... The ultimate solution is simple: **identifiying** the pure/impure functions and **composing** them correctly:

- pure (business logic relying on data transformations only)
- impure (access to real world stuff such as the database read/write)

We have to remember that combining a pure function with an impure one yield an impure function (infection). Doing this composition at the leaf of our program call tree **is a bad idea** as we are going to fall into the problem we just described. You know it, **we should** apply this composition at the top level. Let's rewrite our example:

```
// Our function is now pure as we are not using a global mutable state
public static int Dummy4(int x, int k)
{
return x * k;
}
public static int Dummy5(int k)
{
var x = 5;
var y = Dummy4(x, k);
var z = Dummy4(x, k + 1);
return y + z;
}
private static int _k;
public static void Dummy6()
{
var d = Dummy5(_k);
_k += 2;
var dd = Dummy5(_k);
_k += 2;
Console.WriteLine(dd);
Console.WriteLine(_k);
}
public static void Main(string[] args)
{
Dummy6();
/*
25
4
*/
}
```

Our `Dummy5`

is now very clear. Stating that $z = y$ doesn't make sense any more, everything is explicit. Furthemore, following the program is much easier as the ~~very bad~~ mutable state has been **extracted to the top level**.

Generalizing this example to a more complex program is not a hard task. Imagine having multiple side-effects depending on each others, **mixed with pure code**, splitted accross different layers of the application. Evil software. Maintainance nightmare.

Finally, in **pure** functional programming languages such as Haskell, the distinction between the two types of functions is ~~easy~~ explicit as we have monads (something I will be talking about in a future article).

Thanks for reading.

https://en.wikipedia.org/wiki/Side_effect_(computer_science)

https://en.wikipedia.org/wiki/Referential_transparency

https://en.wikipedia.org/wiki/Monad_(functional_programming)

We are not going to transform code into curry but rather try to curry some code. As a former C# developer, when I started Haskell, I felt like functions were very differents from what I was used to see in object oriented languages. **I just forgot maths**:

$$

f : \mathbb{Z}

We are not going to transform code into curry but rather try to curry some code. As a former C# developer, when I started Haskell, I felt like functions were very differents from what I was used to see in object oriented languages. **I just forgot maths**:

$$

f : \mathbb{Z} \to \mathbb{Z} \to \mathbb{Z} \to \mathbb{Z}

\\

f(x, y, z) = x + y + z

$$

```
public static int f(int x, int y, int z) => x + y + z;
```

```
f :: Int -> Int -> Int -> Int
f x y z = x + y + z
```

Everyone was used to see the mathematical definition at school. Why do we have such a verbose and ugly notation is OOP? I don't have the answer but I believe that it is far **easier to read the Haskell definition**.

In opposition, the C# side is **mixing** both the **function signature** and its **implementation**, this is a reason why it is harder to read (note that we are using the version 7 of C#, it would be worse otherwise).

Now let's think a little bit about $f$. The function is telling us:

Give me $x$, $y$, and $z$. I will give you $x + y + z$.

We can rephrase this sentence:

Give me $x$ and then $y$ and finally $z$. I will give you $x + y + z$

This is very important. Providing the three variables at the **same time is not mandatory**. What I mean is that we can **first fix** $x$, then fix $y$ and fix $z$ **later**. Let's welcome currying:

$$

f : x \mapsto y \mapsto z \mapsto x + y + z

$$

This mathematical definition is pretty much straight forward. The function $f$ is a **map of map of map**, it's possible to fix the variables **step by step by step**:

$$

\begin{eqnarray*}

g &=& f(1)

\\

g &:& y \mapsto z \mapsto 1 + y + z

\\

\\

h &=& g(2)

\\

h &:& z \mapsto 1 + 2 + z

\\

\\

i &=& h(3)

\\

&=& 6

\\

&=& h(3)

\\

&=& g(2)(3)

\\

&=& f(1)(2)(3)

\end{eqnarray*}

$$

What we want to understand here is that we can treat **every function** as a function of a **single argument**:

$$f(1, 2, 3) = f(1)(2)(3)$$

Instead of providing every parameters at once, we **fix them one at a time**. This give us more flexibility. Now remove the useless commas and parenthesis:

$$f\enspace1\enspace2\enspace3 = f\enspace1\enspace2\enspace3$$

Wow, go back to our Haskell definition:

```
f :: Int -> Int -> Int -> Int
f x y z = x + y + z
```

You can **partially apply functions** in Haskell, every function is a function of a single argument. What you don't see here is the implicit right associative arrow `Int -> (Int -> (Int -> Int))`

. We can read it as **a function of function of function**.

Applying a parameter to a function is just a matter of space `f a`

. With the application being left associative `f a b = (f a) b`

:

```
f :: Int -> Int -> Int -> Int
f x y z = x + y + z
k :: Int -> Int
k = f 1 2
```

Having this kind of behaviour in C# is pretty hard as we have to write a lot of boilerplate code to reach the same level of abstraction:

```
public static int f(int x, int y, int z)
=> x + y + z;
public static Func<int, Func<int, Func<int, int>>> curriedf =
x
=> y
=> z
=> x + y + z;
```

Unfortunately, the code is ugly and unreadable, notice how it is hard to understand the nested **Func**. Perhaps you ask yourself whether this concept is useful or not. Imagine that you want to filter a list of persons by their age:

```
public static bool OlderThan30(Person person) => person.Age > 30;
// call site
var persons = new List<Person>(...);
var result = persons.Where(OlderThan30);
```

```
olderThan30 :: Person -> Bool
olderThan30 person = age person > 30
-- call site
persons = [...]
result = filter olderThan30 persons
```

Now, you realize that you also want to filter people older than 50. You try to abstract the function by accepting the lower bound as a parameter, but **you are stuck** to write:

```
public static bool OlderThan(int lowerBound, Person person)
=> person.Age > lowerBound;
// call site
var persons = new List<Person>(...);
/* Impossible to write this even if it mathematically equivalent
var result = persons.Where(OlderThan(50));
*/
Func<Person, bool> olderThan50 = person => OlderThan(50, person);
var result = persons.Where(olderThan50);
```

```
olderThan :: Int -> Person -> Bool
olderThan lowerBound person = age person > lowerBound
-- call site
persons = [...]
result = filter (olderThan 50) persons
```

Regrettably, the `Where`

function is accepting a function of a single argument, but we are not able to partially apply `OlderThan`

in C#. We are forced to have an intermediate function (`olderThan50`

) to **give all the parameters at once**...

Moreover, the compiler is not able to infer `Func<Person, bool>`

as we can't replace it by `var`

.

Thanks for reading.

https://en.wikipedia.org/wiki/Currying

https://wiki.haskell.org/Currying

Take a programmer, ask him to write a function that doubles an integer.

It's highly likely that he will give you something similar to the following:

```
public static int Double(int x) => x * 2;
```

```
double :: Int -> Int
double x = x * 2
```

The solutions are trivial, but

]]>Take a programmer, ask him to write a function that doubles an integer.

It's highly likely that he will give you something similar to the following:

```
public static int Double(int x) => x * 2;
```

```
double :: Int -> Int
double x = x * 2
```

The solutions are trivial, but can we have a different answer? Something equivalent to the above? Something that can't be *reduced* to this expression? Something different in how it *computes things*? Yes, this code is an example of **direct style** programming, but we can write a similar program in a very unusual way.

I have to admint that **continuation passing** is very strange when first looked at. Here is an implementation that is actually equivalent to the previous code:

```
public static R Double<R>(int x, Func<int, R> cont)
=> cont(x * 2);
```

```
double :: Int -> (Int -> r) -> r
double x f = f (x * 2)
```

The function is saying:

Give me an integer and the rest of the program, I'll feed it with the doubled integer and give you the response.

Instead of having to call the function to get the result, we have to give the **continuation** of the program.

But hey, do we have a **1:1** correspondence between the two styles? I mean, can we transform any direct style function in its continutation passing form? Fortunately, yes, my blog post would be useless otherwise. It's a consequence of the Curry-Howard correspondence.

The concept of continuation can be extended to data types with the Böhm-Berarducci encoding (the intuition can be extracted from the Church encoding). In fact, we can transform any data type into a bunch of functions. Pretty strange you may say. Let me show you.

To start, we define a product type `int * int`

, we usually call it *class* with two fields in C#:

```
public sealed class Product
{
public readonly int X;
public readonly int Y;
public Product(int x, int y)
{
X = x;
Y = y;
}
}
public static int SumProduct(Product product)
=> product.X + product.Y;
// call site
var x = SumProduct(new Product(4, 5));
```

```
data Product = Product { x :: Int, y :: Int }
sumProduct :: Product -> Int
sumProduct product = x product + y product
-- call site
x = sumProduct (Product 4 5)
```

I hope that you start to see the difference between C# and Haskell here, the former being far more verbose than the latter (this will hopefully change in C# 8/9 as we will be able to inline classes).

Let's step back for a second. We have a product of two int and a function that, given a product of int, computes the sum of the two parts. We can generalize this concept, having a product of different types `A * B`

associated with an interesting higher order function:

```
public sealed class Product<A, B>
{
public readonly A X;
public readonly B Y;
public Product(A x, B y)
{
X = x;
Y = y;
}
}
public static R FoldProduct<A, B, R>(Product<A, B> product,
Func<A, B, R> f)
=> f(product.X, product.Y);
public static int SumProduct(Product<int, int> product)
=> FoldProduct<int, int, int>(product, (x, y) => x + y
// call site
var x = SumProduct(new Product(4, 5));
```

```
data Product a b = Product { x :: a, y :: b }
foldProduct :: Product a b -> (a -> b -> r) -> r
foldProduct product f = f (x product) (y product)
sumProduct :: Product Int Int -> Int
sumProduct product = foldProduct product (\x y -> x + y)
-- call site
x = sumProduct (Product 4 5)
```

**FoldProduct** is what we call folding/evaluation/elimination or even destruction of a structure. We are evaluating the whole structure (our product type here) to raise a result. It's the inverse of the structure construction (keyword ** new** in C#).

We can go further and transform the whole product into a single function:

```
public static Func<Func<A, B, R>, R> Product<A, B, R>(A x, B y)
=> f
=> f(x, y);
// call site
var result = Product<int, int, int>(5, 6)((x, y) => x + y);
```

```
type Product a b = forall r. (a -> b -> r) -> r
product :: a -> b -> Product a b
product x y f = f x y
-- call site
x = product 1 2 (+)
```

If we pay enough attention, we can notice a big difference between the C# code and its Haskell counterpart. Indeed, in Haskell, the `Product`

type alias does not tell what `r`

will be. In contrast, `a`

and `b`

are known at construction time. We want `r`

to be instantiated later because we may have multiple continuations.

Imagine that you create a `Product Int Int`

and want to fold it using a function that concatenates the two ints like: $$f : \mathbb{Z} \to \mathbb{Z} \to String$$ Imagine that you also want to compute the sum with: $$g : \mathbb{Z} \to \mathbb{Z} \to \mathbb{Z}$$ If we had to fix `r`

while creating our `Product Int Int`

, the continutations would be constrained to the same codomain (`r`

constant after the object creation). This is the case in C#, look at the following:

```
public static Func<Func<A, B, R>, R> Product<A, B, R>(A x, B y)
=> f
=> f(x, y);
// call site
var prod = Product<int, int, int>(5, 6);
// impossible as R is already fixed to int
var str = prod((x, y) => x.ToString() + y.ToString()); // prod(f)
// type checking correctly
var sum = prod((x, y) => x + y); // prod(g);
```

```
type Product a b = forall r. (a -> b -> r) -> r
product :: a -> b -> Product a b
product x y f = f x y
-- call site
x = product 1 2 (+)
y = product 1 2 (\x y -> (show x) <> (show y))
```

While the Haskell code is perfectly right (some type annotations are required as the literals are ambiguous). **We are stuck in C#** because the generic type `R`

has to be defined **when constructing our object**.

The limitation is related to something called higher-rank types (we need **rank 2 types** here but we only have

`r`

can be instantiated after the product creation (when calling with our continuation). Yeah, Haskell is supporting arbitrary-rank polymorphism.Here is an example of a C# implementation if we had **rank 2 types**:

```
public static Func<TYPE, Func<Func<A, B, TYPE>, TYPE>>
Product<A, B>(A x, B y)
=> TYPE
=> f // public TYPE f(A x, B y)
=> f(x, y);
// call site
var prod = Product<int, int>(1, 2);
// we would like to vary R depending on the context
var x = prod<int>((x, y) => x + y);
var y = prod<string>((x, y) => x.ToString() + y.ToString());
```

You get the idea, we ask for a type `TYPE`

associated with a function `f`

that should have the signature `TYPE f(A x, B y)`

. Kinda like giving a type as a classic parameter.

Perhaps you want a more sophisticated example:

```
/*
public sealed class Example
{
public int X;
public int Y;
public int Z;
public Example(int x, int y, int z)
{
X = x;
Y = y;
Z = z;
}
public int Sum()
=> X + Y + Z;
public int Prod()
=> X * Y * Z;
public string ToString()
=> X.ToString();
}
*/
public static Func<Func<A, B, C, Func<U>,
Func<V>,
Func<W>,
R>, R>
Example<A, B, C, U, V, W, R>(A x,
B y,
C z,
Func<A, B, C, U> sum,
Func<A, B, C, V> prod,
Func<A, B, C, W> toString)
=> f
=> f(x, y, z,
() => sum(x, y, z),
() => prod(x, y, z),
() => toString(x, y, z));
// call site
var example = Example<int, int, int, int, int, string, int>(
1,
2,
3,
(x, y, z) => x + y + z,
(x, y, z) => x * y * z,
(x, y, z) => x.ToString());
var result = example((x, y, z, sum, prod, toString) => sum());
```

Voilà! We will dig more into algebraic data types next time. If you want something more theoretical about the subject, you should read Oleg's fantastic article.

Thanks for reading.

_{http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.html}

_{https://en.wikipedia.org/wiki/Church_encoding}

_{https://en.wikipedia.org/wiki/Continuation-passing_style}

_{http://oleg.fi/gists/posts/2019-06-26-linear-church-encodings.html}

Several years ago, I found myself watching Andre Staltz's talk about Cycle.js. A JavaScript framework that would leverage reactive programming paradigm in front-end developement.

The reactive programming paradigm interested me and I wanted to understand the underlying concepts. I had no clue what "side effects" meant, what

]]>Several years ago, I found myself watching Andre Staltz's talk about Cycle.js. A JavaScript framework that would leverage reactive programming paradigm in front-end developement.

The reactive programming paradigm interested me and I wanted to understand the underlying concepts. I had no clue what "side effects" meant, what functional meant. I was writing ugly imperative C# code, with no wonder of the cost. Null pointer exceptions and their friends... Story is known.

One day I tried to write some Haskell. My attempt to write a simple program miserably failed. I asked myself whether I deserved my title of software engineer or not. This is how I tried to dove into type theory and category theory to understand this incredibly powerful language.

]]>