Thinking Like a Computer – Functions

As we have learned, a computer works in sequences. To write a program, we write down a sequence of commands. In our programs, we often have the need to use the same sequence multiple times. Remember the sorting algorithm that I needed to sort my socks? If I needed it again in another place in my sequence, I would have to repeat the whole sequence – or wouldn’t I?

Fortunately, a computer does not have to follow the sequence strictly. The Control Unit knows commands to jump to a different address in the code memory. Then the execution continues with the sequence that is stored at that location. This means that if we have a sequence that we want to use multiple times in our code, at each point in the code we add a command to jump to the address where this sequence is stored. At the end of the sequence, we add another command to jump back right after the point where we jumped away from the original sequence. Then the execution continues from there on.

The concept of having a sequence that we can use multiple times is called a function. This concept is so important that it is implemented by all programming languages. The programming language takes care of jumping to the right place in the code memory and returning to the correct position afterwards. And you don’t have to remember the address of the sequence in the memory. Instead, you give the function a name. To use this sequence, you only have to write the name of the function in your sequence. This is also known as calling the function.

This means a function gives us a comfortable means of reusing our code – just give a piece of code a name and we can use it everywhere we like.

A function also encapsulates a concept. When you design a function well, it will perform one task in a way that you don’t have to worry about the details. With a function that is named sortSocks, you can be sure that you will have a sorted list of socks afterwards. At the point where you call it, you don’t have to think about sorting algorithms at all.

But there are even more facts about functions that you need to know:

Functions become even more useful when you provide them with parameters. A parameter is a piece of data that you provide to the function every time you call it. The function behaves differently for different values of the parameter. For instance, the sequence for sorting my socks could take a parameter which kind of socks should come first in the list of sorted socks. If I pass in “black”, then the black socks should come first. If I pass in “white”, then the white ones should come first.

Designing a function to take parameters is optional. A function can take no parameters at all, one, two, or any arbitrary number.

Parameters make functions even more versatile. Instead of having to write a function for each possible value, we can write a function that takes a parameter and can be used in a multitude of situations.

When a function finishes, the code jumps back to the place where it was called from. This is also known as returning. When this happens, the function can provide a value to the calling code as a result of its execution. Just like the calling code can provide input to the function, the function can provide the output it calculated. The calling code can then use this output when it continues.

The sock sorting algorithm could return the sorted list of socks. Then the calling code can use the sorted list of socks to take two socks of the same color out of it.

When a function is called, multiple tasks happen in the background. If you use a programming language, it will take care of all of them. But it is still important to understand them, because you can crash your computer if you use functions incorrectly.

As we have learned above, when a function is called, the execution continues at the address of the function. In technical terms, the Program Counter which we got to know in another article, is set to the address of the function. But how do we get back to where we were at the end of the function?

To achieve this, the return address – the address where execution shall continue when the function returns, is put on the stack. The stack is a special memory section. It literally works like a stack in the real world. You can always put something on top of it (which is called push), but you can also only take what is on top of it (which is called pop). Nothing in between. This is also known as a LIFO – last in, first out.

So we put our return address on top of the stack. But what if the function calls another function from within? The same thing happens again! The return address within our current function is put onto the stack on top of the current return address. Then the program counter changes to the new function. When the new function finishes, the program takes this return address from the stack and removes it. Then the program counter is set to this return address. When the original function finishes, the same happens again, this time with the very first return address. Then the stack is empty again.

When a function that takes parameters is called, they are also pushed on top of the stack. This way, the function knows where to find the parameters. When the function finishes, the parameters are removed (popped) from the stack.

Also all variables that the function creates for its own use are put on the stack.

So during the execution of a program, the stack grows and shrinks, grows and shrinks all the time. Our computer handles all of this for us, but there is a caveat: The memory is limited. The stack resides in a special memory area, and this has a limited size. The actual size depends on the computer you have – a server has a much bigger stack than an embedded microcontroller. But it is finite. And if the stack grows larger than the maximum size, the computer crashes. This event is called a stack overflow. You have to prevent it at all costs. This is often not easy, because functions can call other functions, and thus the stack can grow very large.

But there are a few general rules to follow to prevent a stack overflow. For instance, be very careful when you write a function that calls itself – also known as recursion. If you get it wrong, you can end up with the function calling itself, which calls itself and so on, until the stack is so large that a stack overflow occurs.

Another rule is not to create large variables inside the function. If you need a larger variable, create it on the heap instead. We will learn more about this in another article.

If you follow these general guidelines, you should be able to stay clear of the stack overflow.

The function is one of the most powerful tools of programmers. It allows us to reuse a piece of code so we don’t have to reinvent the wheel every time. And it allows us to encapsulate a task in a way that we don’t have to think about how it is done. This let’s us focus on the bigger picture.

With functions, we can think of our sequences as parts of a bigger solution. Now we can break down large sequences into several smaller ones. You can design a function to sort socks and another one to find the color of the socks for the current weekday. Then you can use these functions in the sequence that gets you dressed in the morning.

Excercises: