A blog about in-depth analysis and understanding of programming, with a focus on C++.

Saturday, November 04, 2006

Functional Programming in C++ 1

What is functional programming?

The answer to that question is strange. If you've graduated from high school, odds are you've seen functional programming... in math class. As such, I'm going to use that as an analogy to explain what functional programming is.

In Math, you learned that a function looks like this:

f(x) = x + 4

The function f takes a single parameter 'x', and returns the value of x added to 4. Algebra tells us that the function f can legally take any value of x. That is, x can be any number, real or imaginary. And the result of the function f is also any number, real or imaginary.

Here's another example of a math function:

f(x) = 1 / x

Algebra tells us that f can take any number, real or imaginary, except 0. That would make the result of f undefined, as 1/0 is illegal. Therefore, the function cannot take that as an input. Also, the function f can return any output, real or imaginary, except 0.

Another example that's even more limited:

f(x) = log(x)

f can only take positive real numbers or 0 (we'll ignore complex numbers, as the log of a complex number is... wierd). And it will only ever return positive real numbers or 0.

Something a bit more complex:

f(x, y) = x / y

This time, f takes two parameters. The parameter x can be any number, but y must not be 0. And the function can return any number as well.

And now for something a bit weird:

f() = 3 + 4

This is a function that takes no parameters. And it returns only one number: 7.

So, what was the point of that? Well, that was functional programming.

Not convinced that this could be considered programming of any kind? Well, let's proceed.

Let's say we have these functions:

f(x) = x * 5
g(x, y) = x + (4 * y)

Two functions now. I'll skip the input/output analysis and move on to composition. Let's say you want to do this:

h(x, y) = g(f(y), x)

Well, determining what the function h is is pretty simple:

h(x, y) = (y * 5) + (4 * x)

See that? We just did functional programming. We took two functions, composed them together, and created a third function.

You can do more with functional composition. You can lose parameters:

h(x) = f(g(x, x))

Add new ones:

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

And so on.

By now, you're probably kinda annoyed with this math lesson. What does this have to do with programming? Well, it's simple.

Forget the fact that what I'm about to write is not legal C/C++.

float f(float x)
return x * 5;
float g(float x, float y)
return x + (y * 4);

float h(float x, float y) = g(f(y), x);

That last line is totally bogus C++. But... what if it wasn't? What would it mean if it were real and legal?

Well, actually, it wouldn't be too amazing, because you can do:

float h(float x, float y)
return g(f(y), x);

But, what you can't do is:

void main()
float h(float x, float y) = g(f(y), x);

h(4, 5);

You cannot dynamically define functions. And that is the fundamental difference between functional programming and procedural programming.

In functional programming, functions can be thrown around, created, destroyed, composed, etc. They're no different from any other construct; they're just like an integer, a float, or an object.

So, back to that question: what would it mean for C++ if you could do this? Forget the fact that we defined this all as math so far; it's now just C++ function calls. In fact, the math stuff is C++ function calls. After all, operator +, *, etc will call functions when provided with objects for operands. So even those are function calls.

Now that you understand what functional programming is, next time we'll discuss what you could do with it if it worked in C++. In the third article, we'll discuss, well, turning this from an academic "what if" into the truth: that C++ is very capable of all of this. Once you use the right library, of course.

No comments: