DEV Community: Vijesh Salian

Recursion - How to overflow the stack and how not to

Vijesh Salian — Fri, 19 Jul 2019 07:30:27 +0000

Recursive functions are functions that calls itself. If you were new to recursive function, it may have hurt your brain. Today's blog is in the similar lines. It may help you understand recursion better.
Fun exercise: Try searching 'recursion' on Google.

We will create a recursive function to find the factorial of a number. A factorial of a number is the product of all the integers before it down until 1. The factorial of 1 is 1. And that is the base case.

let rec fact x =
 if x <= 1 then 1
 else
  x * fact (x-1)

Any recursive function written by humans must have base case or a terminating case. Recursive functions have a tendency to get sucked into a black hole which in turn is a recursive sucker. Luckily when we write recursive functions on computers, the call-stack comes to rescue us from the black hole.

What is the call stack?

A call stack is where function calls are stored. When a function is called, the control needs to go into the function. When the function completes executing, the control needs to go back to the function it was called from. The call stack keeps track of the current executing function and the function it needs to go back to when it finishes executing. The data structure the call stack uses for this is, you guessed it, the stack.

In the title of this blog, I use the word stack. For the purposes of this blog I use stack and call stack interchangeably. A call stack is made up of stack frames. Every stack frame represents a function call. The top-most stack frame represents the latest.

Call stack of the running factorial function.

Courtesy: Visual Studio 2017

The number of frames the stack can hold is finite. When the stack can take no more frames, it is said to be overflowed. That's when you get the infamous stack overflow exception. It is important to learn to break things in order to prevent it from breaking.

Let's get the stack overflow exception deliberately.
Call the above function with a very large number. Say a hundred thousand.

let factorial = fact 100000

And that is how you overflow the stack.

Tail Recursion
Tail recursion is a recursion of a function where it does not consumes stack space and hence prevents stack overflow. If the recursive function is made tail-recursive then it is more efficient than a non-tail-recursive function because every function call does not need to go on stack and pop when the call is done. And it prevents the ugly stack overflow.

Let's create a recursive function to find the sum of integers from 1 to a given n. That will be a parameter to the function. The base case where the recursion stops is when n is zero. Here is the function

let rec sumOfIntegers n =
 if n = 0 then 0
 else
  n + sumOfIntegers (n-1)

If you debug this function, you will notice that every function call consumes a stack space. This function is not tail-recursive. If you notice in the recursive function above, there is a base case and a recursive case. Recursive case is where all the recursion action takes place. The last expression of the recursive case is an addition. When the recursive call is made, it still has to come back after a series of calls to do the addition. If we make the last expression just a recursive call, then we give a chance to the compiler to optimize the recursion so as to not consume stack space. So we can make the above function tail-recursive if we can make the last expression of the recursive case to be just a recursive function call without any other additional evaluation. Here is the tail-recursive version of the sumOfIntegers

let sumOfIntegersTr n =
 let rec sumrec n sum =
  if n<= 0 then sum
  else
   sumrec (n-1) (n+sum)
 sumrec n 0

The function sumOfIntegersTr takes n as an argument. Notice that it is not a recursive function. It defines a nested function sumrec which is recursive. Right after the definition of sumrec, it invokes sumrec.

The recursive function sumrec, looks to be tail recursive because the last expression in its recursive case is just a function call.
sumrec takes 2 argument. n, the obvious one and sum, which it uses to accumulate the sum of number. The first invocation of sumrec is done by the outer function sumOfIntegersTr. It is invoked with n and 0, 0 is the initial value for sum.This way it does the addition in the argument to the function call. The base case returns the accumulated sum. Pretty neat. Debug and take a look at the call-stack to verify.

Now, lets make that factorial function tail-recursive. Remember that the last expression of the recursive case must be just a function call. I will also be using an accumulator named factorial to hold the value of the factorial. Just like sum in sumrec.

let factTr n =
 let rec factRec n factorial =
  if n <= 1I then factorial
  else
   factRec (n-1I) (n*factorial)
 factRec n 1I

Notice the 'I' suffixed to the the integer? It just means that the number is a Big Integer. Its a type to hold large integers. Go ahead and take a look at the call stack, it should consume only one stack frame for any number of calls.

Hope you enjoyed reading this. Until next time. Cheers.

Broken array covariance

Vijesh Salian — Fri, 28 Jun 2019 15:16:12 +0000

Array covariance is broken? Yes it is!

The code examples I show here applies to C# and it applies to Java as well, because I think Java was the first to make(break?) this. C# unwillingly had to do the same in its language.

Variance (Covariance, contravariance, invariance) is a hard topic to explain. But I am going to try anyway.

When designing a language with types, the designers must set certain rules about how types and its related types are substitutable. Any operation dealing with types is subjected to those rules. An operation could be covariant, contravariant or invariant. Note that an operation could not just be a function/method, but could also be an assignment.

Consider these classes. Small and Little are both subclasses of Big.

public class Big
{
}

public class Small : Big
{
}

public class Little : Big
{
}

If I can assign a Small type to a Big type, then that assignment operation was covariant with those types.

Big a = new Small();
Big b = new Little();

The converse is not true for the above operation. Contraviance is the converse of covariance. Covariance feels more intuitive than contravariance. The assigment operation is not contravariant with those types. If you try to do this, the compiler should warn you, because the rules of variance are well defined.

Small s = new Big();

These are very simplified examples. If you would like me to cover this topic elaborately in another post, please let me know in the comments.

In this post I am going to talk only about broken array covariance.

The language designers decided to make arrays covariant. The following code is perfectly compile-able.

Big[] bigArray = new Small[10];

The above assigment operation is legal, because it obeys the rules of variance.

Now consider the following code. We are using the bigArray defined in the previous code. This code also perfectly legal. Because a Small object is assignable to a Big type. It satifies the covariance rules.

bigArray[0] = new Small();

Little assigned to Big also follows the covariance rules.

bigArray[1] = new Little();

Here's where things go wrong. The above code is still perfectly valid code. The poor compiler does not know that the runtime disagrees.

If you run the program, it will end up with an exception trying to assign Little to Big. This is why the array covariance is broken. The problem is, even though the type is Big, the underlying storage is of Small. Small and Little are not substitutable with each other.

Could the language designers have avoided this problem? May be. Let's create List instead of array.

List<Big> bigs = new List<Small>();

The above code does not compile. The problem is completely avoided by the compiler here to keep the types safe.

If you are working with array with related types, before inserting an object into an array, check its type first to avoid runtime errors. Next time when you are reviewing code with arrays, remember array covariance is broken!

Hope you found this interesting. Thank you for your attention.

Cheers 🍺

.NET Assembly Roundtripping

Vijesh Salian — Tue, 25 Jun 2019 10:08:03 +0000

What the heck is Roundtripping?

Assembly roundtripping is the act of decompiling an assembly to its IL( Intermediate Language) to edit it and then recompiling it to generate the assembly back.

In this post I am going to demonstrate how to roundtrip a .NET assembly.
To roundtrip, we need to

Decompile to IL
Edit IL
Recompile to assembly

Tools required

ildasm
Visual Studio Developer Command Prompt
csc.exe - The C# compiler

Here is the C# file we are going to use for our demo.

using System;

public class Program
{
    public static void Main()
    {
        int x = 10;
        int y = 20;
        Console.WriteLine("The answer is {0}", x + y);
        Console.WriteLine("Hello, World!");
    }
}

I am going to name this file as roundtrip.cs.

In the VS developer command prompt, navigate to the location of the file roundtrip.cs. Now, I am going to compile this cs file into an assembly, an exe in this case. Here is the command.

csc.exe roundtrip.cs

There is an assembly created. roundtrip.exe. If you run this program you should get the following output. Nothing out of normal here.

The answer is 30
Hello, World!

Decompile to IL

Let's create an IL file for roundtrip.exe using ildasm with the following command.

ildasm /out=roundtrip.il roundtrip.exe

This will create a file roundtrip.il with IL code for roundtrip.exe.

Open this roundtrip.il in any editor. You will find all the IL code in the file. The main method in our C# file has a corresponding section in the IL. Look for the following line the IL file.

.method public hidebysig static void  Main() cil managed

In this section you should find a set of instructions that correspond to declaring and initializing the integers with 10, 20 respectively. There is a string that we are using. You will find that too.

.locals init (int32 V_0,
             int32 V_1)
    IL_0000:  nop
    IL_0001:  ldc.i4.s   10
    IL_0003:  stloc.0
    IL_0004:  ldc.i4.s   20
    IL_0006:  stloc.1
    IL_0007:  ldstr      "The answer is {0}"
    IL_000c:  ldloc.0
    IL_000d:  ldloc.1
    IL_000e:  add

Edit IL

Now for the edit part, let change the add operation to a multiplication. Replace add to mul

IL_000e:  mul

There is a Hello World string, let's change that string to Hello Dev.

Before:

IL_001a:  ldstr      "Hello, World!"

After:

IL_001a:  ldstr      "Hello, Dev!"

Make sure to save the IL file.

Recompile to assembly

Now is the time to recompile. In the VS dev prompt, type the following command. Note that this time we use ILASM and not ILDASM. We pass the edited IL file to the command.

ilasm /exe roundtrip.il

If there are no mistakes made in the IL, then you should find the new roundtrip.exe. When you run it you should see the following output.

The answer is 200
Hello, Dev!

Hope you found this interesting. Thank you for your attention.

Cheers 🍺

Starting with Rust - Cargo

Vijesh Salian — Wed, 05 Jun 2019 11:46:38 +0000

In the last post, we saw how to compile a rust file ( .rs file) with the rust compiler. Here's that post in case you are interested.

Starting with Rust

Vijesh Salian ・ Jun 4 '19 ・ 3 min read

#rust #programming #learning

In real world, applications that programmer writes can be made of several files. These files are grouped together in what we call a project. It is very common to have multiple projects in an application. In most cases, more than one developer is involved in building the application. Each project has a clear responsibility. Rust files serving a similar responsibility are generally in the same project. It is common that one Rust file could be dependent on another. It is also common that one Rust project could depend on another. If project X is dependent on project Y. Then Y is a dependency of X. A Rust project coud have multiple dependencies and it should list them and know them. The dependency however will not and should not know about the projects depending on it. Sometimes a project may have a dependency which was written by developers outside your team/company. They can make that dependency available in a central repository so that you can download and use them.

So, when working with Rust you will be compiling, downloading dependencies, building a lot. This is where Cargo comes in to picture. If you have been programming in other languages, all this may seem obvious and you possibly already know what Cargo can do.

How do I use Cargo?

First lets check Cargo is installed correctly. Fire up your shell.

cargo --version

If you see a version number, you are good to go. If not, search engine is your friend.

cargo new hello_rust

This is a command to create a new project. We created a new project called hello_rust. This creates a directory with the project name. If you look into the directory you will find that Cargo initialized it with a git repo. You can choose not to do so if you want. Then you will find a Cargo.toml file. This file is the configuration file for your project. In the project directory you will also find another directory called src. This contains the Rust code files.

Cargo.toml file contains metadata about the project and a list of dependencies if any.

The src directory contains a Rust file which you are familiar with.

Okay, what else can I do with Cargo?

Well, we can build and run our code with Cargo. Cargo knows how to make use of the rustc compiler.

In your shell, be at your project directory and run

cargo run

This commands builds and runs your projects with just one command.
This may look trivial now, but as your projects grow bigger, the benefit of Cargo becomes more visible. By this, Cargo provides a uniform way of building and managing dependencies, for all projects big and small.

If you want to quickly check if your code compiles, but don't want to run it, then use this command.

cargo check

If you want to compile and build an executable, but not run it, then use this command.

cargo build

If you want to ship your program, use this command to build with release mode to create a shippable program.

cargo build --release

Nice, so what else can I do with Cargo?

If you want to know more about cargo, you will find the Cargo book extensive.
Go here for the Cargo book. https://doc.rust-lang.org/cargo/index.html

Thank you for your attention.
Cheers 🍺

Starting with Rust

Vijesh Salian — Tue, 04 Jun 2019 15:37:36 +0000

Programming has been my profession for over 10 years now, but I am proficient in only one language. Even though I may use other languages, I cannot call myself proficient in any other than my primary language. That does not make me very comfortable. Learning a different language gives you a much needed different perspective about programming. So I decided to learn other languages. There is a plethora of languages available. I decided to pick 2 languages that bring a slight counter-intuitiveness to my conditioned object-oriented-thinking mind. I picked F# and Rust. I am no language design enthusiast, so I won't be talking about what are the languages' good and bad parts. As a programmer I would like to know the language well enough to be able to build reliable systems. An expertise in the language is required to avoid known pitfalls. In this post, and in a following few, I will be writing about Rust. This post will cover introduction and installation of Rust.

Rust began its journey from within Mozilla. https://research.mozilla.org/rust/. It is an open sourced programming language and is still sponsored by Mozilla. https://github.com/rust-lang/rust.

Rust is known to be a systems programming language. It is also a general purpose programming language from what I see. So what can you build with Rust? Well, you can build web applications, distributed applications, embedded applications and many more. You can even build your own operating system if you want to. What is so special about Rust? Rust was built from scratch as a systems programming language as an alternative to C and C++, but without the known pitfalls of those languages, especially around memory management. It is a modern language that addresses so many of the issues which makes building systems highly resilient which was really hard to achieve with other programming languages. It is said that if you write code that compiles in Rust, you would have written an efficient code without having to do micro-optimizations.

How do you I get started with Rust
Install Rust on your machine from here https://www.rust-lang.org/tools/install.

If you are on Windows make sure to add Rust path in your PATH system variable.

rustup is a command line tool that manages Rust versions and other associated tools required for development.

Update your Rust installation by running the following in your shell.

rustup update

Run this to check the Rust version. If it shows a version then it has installed correctly.

rustc --version

Note the -- before the word version. That is important; its an argument for the command. The first time I tried the command without -- and got this weird error.

error: couldn't read version: The system cannot find the file specified. (os error 2)

error: aborting due to previous error

So, if you see that error, then check the syntax once again, you may be missing --. Also note that I am on Windows 10. Depending on your operating system you may experience it differently.

Okay, now show me the code!

Let's do an obligatory Hello World program.

Create a directory where you would like this program to reside.

mkdir HelloRust
cd HelloRust

Create a file called main.rs. Type the following code in and save the file.

fn main() {
    println!("Hello Rust");
}

Go to the shell and run the command to compile that rust code.

rustc main.rs

And then run the main executable. On Windows it's the main.exe file. You should see Hello Rust.

If you look at the code you will see that it defines a main function and prints a string. If you have been coding before, this syntax is obvious. There may be some things that may not seem familiar like the ! after the println. Well that is something we may need to cover at a later point in time. This post is not meant for that.

If you would like to learn about Rust, the official documentation is fantastic. The official Rust website has a whole well-written book for free. You can find it here. https://doc.rust-lang.org/book/title-page.html

If you would like to know about my experiments with Rust, then follow this space. Thank your for your attention.

Cheers! 🍺