Tag Archives: Java

Every journey begins with a single step

Purpose

I started this blog because I wanted to understand functional programming better. Having taught traditional programming for over 7 years now I firmly believe the best way to really understand something is to be forced to explain it to someone else. Secondarily, I feel that there’s a lot of interest in functional programming concepts but not a lot of good text on the subject that doesn’t presuppose a lot of terminology, concepts, syntax, and even language constructs from the functional world. My aim here is to introduce as much as I can about functional programming but through the lens of a traditional OO programmer. If you use Java or C# you should feel right at home here. Ruby and Python practitioners will also be able to follow right along although I’ll be using the curly brace and semi-colon syntax of the C lineage.

Another problem I often see is that as soon as anything functional gets mentioned it’s approximately 0.21 seconds before the author then says “so since it’s soooooo much easier to do this in Haskell, I’m going to show all my examples using that now”. While this may be convenient for the author, it is rather unfortunate for the intended goal of communicating any useful information to the reader who almost surely would not be reading an “intro to functional programming” post if they already knew Haskell well enough to read your code example. Sigh. So, my intent here is to use C# as the lingua franca of learning about all this fancy pants functional business.

Some context

Let’s get to it then, what is the “functional” in functional programming about? Honestly it’s nothing radical, no new keywords or libraries or such things, just a different application of the tools we already have. You probably are familiar with many of the concepts I’m going to talk about, but perhaps you’ve never heard them presented as a cohesive set of techniques. I would liken it to the shift that took place with structured programming, a development that took place long before I was born.

The TL;DR version is that at one point, it was common practice to use goto statements to jump all around your program as needed. You can do some nifty things with your control flow and clever individuals loved to squeeze extra little bits out of their machines, both by making smaller programs and by consuming fewer CPU cycles. The downside to this approach was that reading such programs became very difficult. So it was decided, although you lose some flexibility in how you put your program together by requiring that every subroutine (aka function/method) must return to the point in the program that called it when finished, the maintainability upside was pretty huge. This did not mean that the usage of goto disappeared. Your compiler is free to (and does) make great use of such a construct to achieve all sorts of optimizations and even the very structures that were advocated as replacements for goto as a technique, but you never see this part. To you, goto statements probably don’t exist except as the internal business of various tools you don’t need and/or want to know the internals of. We don’t maintain the binary output of our compiler, we instead compile a new version from our source code, so it really doesn’t matter what the compiler does in the process of converting our source to something runnable, as long as the meaning of the instructions is not altered.

Today we don’t even bat an eye at the concept of structured programming, “of course your method returns to where you called it from!” you might exclaim, how could it be any other way? Madness! However, to the goto-loving programmer of 1968, the idea of doing things differently might have seemed as if it was a bad trade, after all they were giving up precious control over their program and perhaps even believed it to be impossible to write certain types of programs under such draconian restrictions. Again, a laughable position from a modern programming viewpoint but I hope you can empathize just a teeny tiny bit. We are that goto programmer of the 1960’s.

Part 1: The function

Being named functional programming, you may have had an inkling that functions might play a role, and right you are! Lest I be guilty of the sins I have accused others of above, let me start at the beginning. I promise I’m not trying to be patronizing to anyone here, I just want to be super clear on the way functional programming sees functions.

In the beginning, we had instructions that came one after the other. This is machine code, which was then slightly abstracted into assembly code. Your program starts at the first instruction and proceeds down the program unless something redirects it (that would be the goto statement). So a totally unrealistic made up example program might look like this

A
B
C
D
E
..more instructions here..
H
I
B
C
D
J
K

Now you may have noticed that that some of those instructions are repeated. It seems rather wasteful to have to keep putting the same instructions in over and over each time we might want to use them so we can instead put them in a single place and then go use that chunk of functionality on demand.

:subroutine // this is a label and is the target of a goto statement
B
C
D
goto place I was called from

:main // program starts running here
A
goto subroutine
E
..more instructions here..
H
I
goto subroutine
J
K

Of course the “goto ” would need some information to actually work, clearly we can’t just use a single goto here as we need to return to 2 different parts of the program (and possibly many more). This idea of how you wire up the going to and coming back from different parts of your program is a good part of what structured programming was about and in the process we got the concept of a function in our programming languages.

So there’s the classical view of functions, they’re nice little containers for parts of your program so you don’t have to copy/paste them everywhere. Well, that’s one view of functions, one specifically in the imperative line of thinking. Imperative programming is about meeting the computer half way. We write programs that are kind-of-sorta doing what the underlying CPU will actually do and the compiler takes care of bridging the gap. When you say:

int x;
x = 5;
int y = x;

You’re being fairly explicit with both what the computer should do (bind the name x and y to the value 5), as well as how the computer should go about doing that (allocate 2 int sized areas in memory and write the bits that represent 5 to those memory locations). In assembly the gap between what the CPU does and what your program tells it to do is very small, in C it’s a bit higher, and by the time you get to languages with runtimes such as Java/C#/Ruby/Python/Perl/PHP you’re at best dealing with generating instructions for a virtual machine that then get taken and converted into the real instructions your computer knows how to understand. Still, even with all that abstraction we’re still fundamentally telling the computer to allocate memory, put values in that memory, copy that memory to other places and so on. Object oriented programming puts yet another organizational layer on top of all of this but does not fundamentally alter how you view your relationships between yourself and the machine. The difference between Assembly and C# is conceptually less than the difference between C# and a functional language like Lisp. C# and Lisp will look syntactically more similar than ASM and C#, but how you go about building your app will be a much wider gap. This is one reason people find learning functional programming so difficult, it looks in many ways to be so similar syntactically but requires you think about your problem in a whole new way.

There is another view that comes at the whole business of writing programs from the opposite approach. You may have guessed that this is indeed functional programming. In this view, a function has nothing to do with memory and CPU opcodes and registers and such, a function is an algorithm that takes in one or more values and produces a result. Of course, to be useful this algorithm must be expressed in some sort of form that can be translated to bits that do indeed allocate memory and care very much about registers and CPU opcodes, but from the programmer’s perspective that sort of thing is an implementation detail. In the same way you probably don’t fret over not knowing exactly how the JVM or CLR interfaces with the operating system to enable “Hello World” to be printed out, a functional approach to programming doesn’t care about how exactly the runtime allocates memory and in many cases even how most of the functions in the program work.

Now this is the point at which you probably think that functional programmers are lazy or stupid or some amazing combination of the two. Why would willful ignorance be of any use to a professional who needs to build real applications that solve real (and hard) problems? It does indeed seem as if there is something magical about controlling where your data goes and the ability to alter it at will. But consider this, we don’t (generally) fret that our for loops won’t get turned into efficient jump statements when translated to opcodes. The compiler has demonstrated the ability to do this competently for so long that no one worries about it anymore, although this was not always true. I can recall reading over many threads of argumentation where programmer A claims that the compiled output of compiler B is not as efficient as their hand rolled assembly and thus they should continue using assembly over C/Pascal/etc. This same argument happened with the transition from C to C++ and then from C++ to Java. At each point, we as programmers gave up some control over the specifics of the execution of our program and got in trade a lot less things to have to worry about. In the functional world, things have always been this way, the problem was always that enabling a blissfully ignorant view of the program’s execution was not particularly feasible for quite some time leading to dreadfully slow functional programs. Thankfully this problem has largely rectified itself thanks to the amazing work of our electrical engineering brethren who give us faster and faster computers to run our terrible bug ridden programs on. This excess computing power has allowed traditional imperative programming languages to take on more aspects that functional languages once embodied such as garbage collection and conversely has allowed functional languages to become fast enough to participate in our everyday computing needs.

TL;DR – Imperative languages started off fast and then got good, functional languages started off good and then got fast.

Clearly it’s not just the functional programming converts that naturally abstract away parts of their systems so they do not have to deal with the complexity, that is a fundamental requirement of programming a large complex system using a human brain (or team of human brains). A functional style adopts the mantra of “I don’t know, I don’t want to know”, if I may steal the phrase from Rich Hickey. Now of course in a functional program you do have the capability to go look under the covers and see what every part is doing, but the point is that you don’t have to do this when you don’t actually need to. What is the secret to this amazing way of building programs you ask? Ah young padawan, you already know the answer, it is indeed the humble function.

Part 2: The function

Wha? You just spent like 10 minutes talking about functions in imperative languages and how functional has a better way of doing things and now you’re telling me it was that same thing all along? Pretty much, with one eensy teensy little modification. Functions in a functional language want to only operate on their parameters. This may seem like a tiny stupid distinction, of course functions operate on their parameters, why on earth are you passing in the param if you’re not going to use it? Ah, but the distinction here is only operate on their parameters. We can easily write a function that operates on the parameters but also operates on some other variable along the way.

// assuming a C style language where globals exist, or
// alternately assuming all this is inside a class for a
// Java / C# style language
int x;

int Sum(int a, int b) {
    x = a;
    return a + b;
}

As you can see, even though x was not passed into the function, it was modified as a result. This sort of thing is referred to as a “side effect”. When functional languages talk about functions, they usually mean “pure” functions, which are side-effect free. Some languages such as Haskell even go so far as to prevent side effects at a language level. Once you have functions that are pure, you can then begin to make assumptions about them. Given the same input they will always produce the same output, so adding memoization is safe and in many cases trivial to implement. Also, when you need to dive into a function to figure out why you’re getting the color Blue when you fully expected to get the color Red you can safely confine your searching to the function itself. Since there can be no outside interference from other functions or variables, when something breaks inside a function it is contained to stay inside that function. Needing to look at less lines of code to understand what is happening is a pretty big motivator for our industry. It could be argued that this idea is one of the primary drivers for the adoption of OOP, grouping all the related functions (aka methods) and the variables they operate on in one place where you can see them as a whole. Pure functions sort of do that on a per-function level.

Part 3: Values

We’ve been talking about variables and functions and I hope it’s beginning to become clear to you now how a function in the imperative world is different from a function in the functional world, however there is still one more bit that functional languages want to stick their oh-so-mathematically-pure fingers into, your variables. This again is an area where imperative and functional viewpoints differ. In the imperative world, a variable is a label for a location in memory. You can use the variable to get at the bits it is referring to and to send new bits to reside there. The bits that you get or set at a particular memory address (aka variable) comprise some sort of data, at the simplest they are things like the number 9 or 5.2. There’s a good reason our languages let us do things like

int x;
x = 5;

but not

int x;
5 = x;

Assigning the bits that represent 5 to the memory address referred to by the name x makes sense. Changing the value 5 to be a different value does not.  5 is 5, it can be no other way. This sets up a variable/value dichotomy. We often conflate the two (often referred to as identity and value), but as you can see they are very different. For any given variable we can put a new value in that memory location and now x is 7 instead of 5 or 23 or … well whatever bits conform to the type rule of our compiler. Functional languages do not generally operate this way. In a functional language, a variable name is bound to a value, and from then on, that name refers to the value, not some memory address. Yes of course under the hood that is exactly what is happening but conceptually we don’t care about that, we care that if I say x = 5, then as long as that variable is in scope, it will be 5. Of course there can be other x’s in other functions or in different calls to this same function each with their own values bound to them, we’re not talking about some magical global variable that exists throughout your entire program, just a variable that is only assigned to once. In C# you can get values for primitive types, just add the readonly keyword and voila. Paired with functions that don’t rely on any outside variables to do their job and now you really have something. Unfortunately readonly only works on member variables, not local variables so while we’d like to do this

int DoSomething(int a, int b) {
    readonly int x = a + b;
    .. hundreds of lines of code, please don't actually write functions this way..
    // I know for a fact that x is still a + b, it can not have changed
}

That is unfortunately not possible. You can see though, that if we could guarantee x never changed (either at the language level or via our own discipline and standards), that knowledge would allow us to look at a very small part of our function and reason about it more clearly, we wouldn’t have to be concerned with the preceding lines (except the one that set the initial value of x of course).

The terms you will hear for these concepts are mutable (as in changeable) and immutable (as in not changeable).

It is now that I will direct your attention to

by the aforementioned Rich Hickey who will do a fantastic job of explaining why concept of values is so powerful and desirable in our applications.

No seriously, go watch the talk, it is amazing.

Part 4: Recap

Ok, so it’s been about 3000 words now and so far we’ve covered … functions… and um, variables. Yeah! Off to a good start I’d say. All joking aside, functional programming is way less about new tools than it is about a different approach to how you think about your tools, and how you put them together. Hopefully you have lots of questions like, how on earth can you do something as simple as add up a list of numbers if you can’t change the value bound to your variable? That is indeed a fantastic question and will be one of the topics in the next post.

Continued in part 2

Tagged , , ,