DEV Community: Gabriel Schade

C# Functional Programming

Gabriel Schade — Tue, 16 Jul 2019 17:56:03 +0000

Let’s start with a question:

Is it worth it?

Like almost everything in software development, It depends… I really like the functional programming paradigm, then, probably there’s some bias here. But let’s trying to be reasonable, right?

The first major point is: why to use C#? — If you want to use functional programming there’s a huge probability that F# fits better than C# in a .NET environment.

There’s a little problem here, a lot of .NET developers have no idea what is F#, I genuinely think that this is a huge mistake, but it’s topic for another article. So, let’s keep it at C# and this bring us to the next question:

Do you like System.Linq?

The answer probably will be: YES!

Because System.Linq is awesome and guess what, it works with one of the core functional concepts: High Order Functions. There’s also a lot more things related to System.Linq, like extension methods, IEnumerables and so on.

Backing to the original question, well, C# contains some native features related to functional paradigm, so, it’s fair to say, that you can do great things by using it.

Let’s code a simple example, we want to iterate an IEnumerable to show each one of its elements:

Our core feature was implemented successfully, but is that the best code that we can create? — I don’t think so.

Let’s remove the hard coded values and make it a parameter, also, we can use IEnumerable interface with generics, it makes a lot more sense:

The static modifier it’s just for make it callable by Main method directly. This new implementation is better than the previous one, but there’s still some hard code here, can you see it?

It’s called hard coded behavior, as developer I have to say that it’s almost so toxic as hard coded values.

But, what it exactly means?

Well, when we think about code, specially object oriented code, variables are understood as values or attributes and methods as behaviors. So, hard coded behavior occurs when you call a method hard coded, like, Console.WriteLine in our code.

Okay, but is it possible to pass a function as parameter? — Sure, just like System.Linq do.

As I said before, there’s a lot of functional programming support in C# and one of these is the reference type called delegate. It’s used to encapsulate a function/method, it’s like a variable that can work with functions instead of values.

Delegates are a topic apart, so if you don’t know anything about it, just check this link out.

Fortunately, there’s two generic delegates built-in C#. They are Action and Func, both of them can work with generic types.

The only difference between them are the fact that Action is used to encapsulate methods with no return (void methods), for all other type of methods the Func delegate is used.

Let’s change our code a little bit, just replace the hard coded call to a generic one:

Congratulations! You just did your first High Order Function!

This method is a lot more generic than the previous one, now we need to change just the Iterate call if we want a different operation.

For instance, if we want to write the value squared instead of the original one:

As you may notice, delegates work with named and anonymous functions, in the above code, we changed the Iterate call by passing a lambda expression as parameter.

The icing on the cake is make it an extension method, so, it’ll works like a Linq method.

If you don’t know what an extension method is, check this link.

In order to do that, we need to create a new static class and use the this keyword before the first parameter:

Now we can use it as an IEnumerable method:

This is a very simple application of functional programming using C#, but the main point is: knowing functional programming will extends your toolbox, so you probably gonna be a better developer with this skills.

It is more than another language, it is a lot more related to the way of thinking and solving problems than the programming tools you will use.

And please, you shouldn’t try to use your functional programming skills in each single piece of code you develop.

Use it to improve your code and your solutions, not to make them more complex.

And remember:

With great power comes great responsibility

See you in the next post!

How to Create Infinite Collections Using IEnumerable Properly

Gabriel Schade — Mon, 01 Jul 2019 17:33:06 +0000

All C# developers faced these interfaces at some point, but how to use them? And better than that, how to use them properly? — Because I’ve seen a lot of mistakes with these guys.

The main point of writing this article is the fact that I lost the count about how many times I’ve seen mistakes and misunderstoods related to C# collections, so I hope to clarify some points here.

Before we start, let’s go a little back and see the cover image at the beginning of the text. It’s a visualization about how you may thinking about IEnumerables.

It works like a Turing Machine tape with a cursor that start pointing to null. This cursor move only straight forward (to right in the image), without index access and besides that, only the necessary information to iterate the collection is provided by an IEnumerable.

Having said that, we can start to code. Let’s check the IEnumerable implementation (with and without generics):

And that’s all. There’s no one more line code at IEnumerable implementation.

What does this suggest?

IEnumerable actually is a IEnumerator factory. Now we need to check IEnumerator out. It’s a little bit more complex, but we can handle it.

There’s two different interfaces, with and without using generics, just like IEnumerable.

The IEnumerator is the one who provides the information about how to iterate a collection (and IEnumerable that is the famous one, how unfair is that?).

In fact, when we use the foreach loop, C# internally calls the GetEnumerator of the collection we’ll iterate and at each step it calls the MoveNext method to move the cursor forward.

Let’s code a super simple code to iterate an IEnumerable of integers using a foreach loop:

It’s pretty simple, isn’t?

As I said before, this code is a simple syntax sugar to another code a little bit more complex, but still a simple code snippet:

This code is a lot more uglier but it does the exactly same thing. The first step got the enumerator using GetEnumerator method, after that, we can use the MoveNext method to iterate each of IEnumerable elements.

It’s interesting to notice that the MoveNext method is called even before we got the first element. It occurs because the enumerator cursor start pointing to one position before the first element (as shown in the tape image).

The MoveNext method have a design that I particularly don’t like. It does two different things.

One of these things is to move the cursor to the next position, which is the main purpose;
The secondary thing is what this method returns. It returns true if the cursor is pointing to a valid position after it was moved or it will return false if isn’t.

My problem with the design of this method is the fact that the main operation, move the cursor to the next element, is caused only by a side effect, but this is a topic for another article, let’s move on.

After call the MoveNext method the first time, we’ll move the cursor to the very first position of the IEnumerable, like the image below:

And the property Current just returns the value at the position that the cursor points to.

Having said that, how about to create a brand new collection containing all integer positive numbers that exists?

Yeah, you read it correctly, a collection with all numbers, which means, a infinity collection.

Here’s a thing before we start to code, the whole point of this implementation is see how IEnumerator and IEnumerable works under the hood with a foreach loop, so, don’t take it as the best implementation possible for a new collection, it’s just an experiment, right?

Let’s start with an IEnumerator, so, just create a new class that implements IEnumerator<int>, It will looks like the code below:

So, now we need to create our own stuff now. In order to create an infinite collection, we’ll use the cursor itself as a value.

Let’s create a new field called _current which starts at -1 and will be incremented as the MoveNext method is called (usually the value is stored at the IEnumerable, but this isn’t a regular example, remember?)

Ok, but let’s understand why _current starts with -1 instead of zero. The answer is pretty simple, it’s because the MoveNext method is called before the iteration.

Now, let’s go to MoveNext method, you probably already know what to do here. We need to increase the _current value and always return true, after all, it’s an infinite collection, so always is possible to move to the next one.

We don’t need to worry about the Dispose method now, so let’s implement the Reset method by reseting the _current to its initial value.

Now, let’s implement our collection itself. It’ll be easy, trust me. All we need is implement the IEnumerable<int> interface and return an instance of our IEnumerator.

Maybe for some reason, you may need return new instances any time you call GetEnumerator, but for our example, only one instance is enough.

Now we can use our own class inside of a foreach loop:

And we can get the next, the next, and the next and keep doing that forever.

How cool is that?

So, everything was implemented correctly, right? — Not exactly.

Let’s force an interruption by using break:

BANG! — An exception was thrown.

Why this exception was thrown? — Simple, the Dispose method wasn’t implemented yet.

Right, but when it’s called?

Just after the loop! In order to remember, let’s reimplement it without foreach sugar syntax, in other words, by using while loop:

Now the things are more clear, aren’t they?

When we iterate across an IEnumerable we use the using keyword, and as you probably already know, the Dispose method is called at the end of the using scope.

The reason why the Dispose method is called is a lot more clear with this syntax, even though it looks worse. We can fix it just by calling Reset method at Dispose.

Warning

This isn’t the best way to implement the Dispose method whatsoever, this is just an experiment, ok?

Now, you have your own infinite collection, it’s time to snapping your fingers (Like Thanos did)!

See you in the next post!

Recursion without Stack Overflows

Gabriel Schade — Wed, 26 Jun 2019 16:06:49 +0000

This can look like a hard achievement, but actually it isn’t. We’ll use F# language and a technique called Tail Recursion.

Recursion itself is a little bit scary for a lot of developers, but there’s no reason to that, it’s just a repetition loop with another outfit.

Eventually you will need it, so, it’s better to be prepared.

As I said before, recursion is a repetition loop technique, so, it’ll help you to solve problems that can be decomposed into smaller problems.

However, there are some issues around using recursion. In general, a recursive loop is slower than a regular loop. In addition to that, there’s a major limitation called call stack.

The call stack

Before we start to code, let’s understanding what the call stack is. Well, this data structure is used by our program to store a pointer to an execution line.

This storage procedure occurs every time your program call a function (any function, not just the recursive ones), this way, the program will be able to return to the correct execution line after function execution.

Let’s see how it works by create a simple hello function:

You should set a breakpoint at line 2 and open the Call Stack Window, this way, you’ll be able to check the call stack, as you can see below:

The call stack is a very useful structure for our programs, however, it may be the reason for a crash in our application. In fact, there’s an extremely popular exception raised by the call stack: StackOverflow.

Have you ever seen that name? — You probably already have seen it at stackoverflow forum, it’s just a joke, because as I said before, it’s a extremely popular exception, mainly when you are learning about recursion.

This exception occurs because there’s a fixed memory dedicated to the call stack, it can be different depending on the language, but usually it’s around 1MB.

Then, if we call functions enough to overflow it, bang! We got a StackOverflow exception.

A recursive sum

Let’s create a recursive function that sums all elements of a given list:

This is a simple pattern matching that returns zero if the list is empty [] , or otherwise it will return the sum of the head element (first element of the list) and the sum of the tail (all other elements of the list).

Let’s create a 1000 elements list and call this function:

Yay, success!

Now, let’s increase the list size to 10000:

Ooops, it doesn’t looks like a success right now. We just got a StackOverflow exception.

It happens because we aren’t using tail recursion yet. Ok, I got it, but after all, what tail recursion is?

Tail Recursion and the Tail Call

Tail recursion is a specific type of recursion implemented by some languages (mainly the functional programming languages). This concept is directly related to what we call as tail call.

A tail call is when a function call occurs with the guarantee that there’s no instructions to be executed after it. It should be the last instruction at all.

So, because the call is the last thing to happen, is pretty fair to say that the instruction line to return after this new call is the same instruction line to the previous call, because there’s no code to be executed after this tail call.

Because of that, the program doesn’t need to store a pointer to each call, because it’s all the same. Internally the compiler will replace this recursive tail call with a JUMP instruction, it’ll avoid the overflow exception and improve performance as well, it’s a win win deal.

Now, we need to understanding why our code isn’t using a tail call. Well, a tail call only happens when the function call is at a tail position. Tail position is just the name of the last instruction of a function, it may be a lot of different things, let’s see some examples:

Hold on a second, the function4 isn’t the same structure of our previous code? — No, it isn’t.

It’s almost the same, in fact each branch of an pattern matching can be a tail position, however, there’s an extra code on our pattern branch.

We aren’t simply return a value, we are making a sum between a value and the result of a function call. As you probably know, the function call occurs before the sum itself, so, the call isn’t the last instruction.

Are you already figured out how to solve it?

It’s pretty simple, instead to accumulate the value with returns, we’ll accumulate the value as a parameter. So, our function now contains two different parameters: the list and the accumulator.

To prevent the function consumer to give a wrong value as accumulator, we gonna make this new function a nested function, and call it internally always passing zero as accumulator initial value.

Maybe this code looks a little more unfamiliar to you, but it’s ok, tail recursion is very important (and useful) when we are talking about functional programming, as recursive functions is preferred over regular loops.

So, let’s check our code again:

No StackOverflow at all!

In fact, we can set a breakpoint to check the call stack:

As we can see, there’s no new pointers added in each call! How cool is that?

Now we implemented a tail recursion properly, but how can I check if my new random function was implemented correctly?

Well, the simplest test ever is just execute your function with a very large input, another simple test is check the call stack. But of course, there’s a more accurated test.

IL Disassembler

You can use the IL Disassembler in order to make a more deep analysis.

If you don’t know IL at all, I strongly recomend you to check this link. Here’s a quick overview: IL is the intermediate language generated by .NET compiler. When you compile your .NET code this is the result, which’ll be compiled again in execution time (JIT).

The IL Disassembler can be open by Visual Studio Developer Command Prompt, you can type “developer command” at Windows search box and it’ll be listed (it looks like the regular command prompt).

You can navigate to your project folder and execute the command ildasm project-name.dll, it’ll open the IL Disassembler, as shown in the following image:

Now, let’s check the first sum function, which raised the StackOverflow exception.

Maybe the IL language looks weird to you, but this isn’t a problem, we don’t want to understanding the language in a comprehensive way right now. Let’s focus on call instruction, it happens in four different moments:

IL 003 — call to get_TailOrNull() function;
IL 011 — call to get_TailOrNull() function;
IL 018 — call to get_HeadOrDefault() function;
IL 020 — call to sum function;

The last call is the most important one, because it shows that a new call really occurs here.

Now, let’s check the tailRecursionSum function:

Oops, something is wrong, there’s also a call instruction here. Well, actually to check our recursive function we need to open the nested function.

In order to open this IL code, we need to navigate at program tree and open the Invoke file:

Now, let’s see the code:

There’s also three call instructions here. But if we look carefully we gonna see that all calls are related to head and tail functions.

Instead our last recursive call we can see a br.s instruction, which works like a JUMP to another instruction. In this specific case, a JUMP to the first instruction (IL_0000 ).

Just before this br.s we can see two starg.s instructions, this is a short for store argument, in other words, our IL code is updating the value of the arguments (acc and list), and after that, it’ll back to the first instruction with updated values, like an regular loop.

Because of this JUMP structure, there’s no Stackoverflow and there’s a performance improvement, it’s really nice to see how the things works under the hood.