Going Declarative with Functional programming

The Partridge Family were neither partridges nor a family. Discuss.
User avatar
cyboryxmen
Posts: 190
Joined: November 14th, 2014, 2:03 am

Going Declarative with Functional programming

Post by cyboryxmen » March 5th, 2019, 7:53 am

You may have heard of this term floating around a lot but might not know entirely what it means. It's simple really.

Normal(Imperative) code would do this:

Code: Select all

sort(array);
while Functional code would do this:

Code: Select all

const auto sorted_array = sort(array);
Or this

Code: Select all

const auto sorted_array = array.sorted();
In Functional programming, when x = 1, x will always be 1. You cannot change the value of x nor can x change by itself. By extension, functions in Functional programming will always return the same value assuming that you give it the same arguments every time.

Code: Select all

const auto x = get_input(0);
const auto y = get_input(0); // same as x.
The meaning of a variable is its value. Change its value and you change its meaning.

Code: Select all

// An array of numbers that the user has inputted.
auto inputted_numbers = get_input();
// Now it's an array of numbers that the user has inputted with the numbers greater than 100 removed.
remove(inputted_numbers, GreaterThan{100});
// Now it's an array of numbers that the user has inputted with the numbers greater than 100 removed sorted in ascending order.
sort(inputted_numbers);

std::cout << "Here are the numbers you have inputted!\n";
// You wanted to print out the exact numbers that the user has inputted but it was I, modified array!
print_array(inputted_numbers)
As such, the value of a variable should be set upon declaration and must not be changed afterwards. In doing so, you make it much clearer as to what values you are operating on.

Code: Select all

print_array(inputted_numbers);
print_array(inputted_numbers.sorted());
Having variables that can't mutate after declaration allows you to make more assumptions that you otherwise wouldn't be able to.

Code: Select all

auto player_index = array.push_back(player);

auto a = func1(array);
auto b = func2(array);
auto c = func3(array);

// Someone has removed player from the array so now this code is going to cause a segfault. Whoops.
array[player_index].update(a, b, c);
As you can see, having immutable values are good for saving your sanity as your codebase becomes more and more complex.

In Functional programming, you would calculate a new values from old ones instead of mutating them.

Code: Select all

const auto a = 2 + 2;
const auto b = a - 1;
const auto c = a + b;
This essentially turns your code into a log of every variable that you have calculated. These variables would point to the variables that are used in its calculation and those variables would then point to the variables used in their calculation and so on. This makes it incredibly trivial to retrace your steps and predict what the outcome of a calculation might be. Not only that but you can also track down errors by detecting if a variable doesn't have the right value that you had expected. Once you've done that, you'll simply have to inspect the section of your code between the parts that calculated the right values and the parts that didn't to find the error.

Code: Select all

// a is fine
const auto a = func1(start);
// b is fine
const auto b = func2(a);
// c is fine
const auto c = func3(b);
// ...
// k is fine
const auto k = func11(j);
// l is fine
const auto l = func12(k);
// Error! The culprit must be func13!
const auto m = func13(l);
In more Imperative style code, where variables can mutate at any point, tracking down the culprits that caused the variable to be in its error state is not as easy. More often than not, the variable was in an error state long before you've managed to detect it.

Code: Select all

int x;

func1();
func2();
func3();
// 3000 function calls later...
func3004();
func3005();
if(x > limit)
{
	// Error! Good luck tracking down the function that has caused this!
}
Modern Imperative programming has gone to great lengths to place restrictions as to where exactly certain variables can mutate because of this. Global variables are heavily discouraged, private member variables are encouraged and const references are commonplace. In the end, these are all band aids to solving the problem of having variables that can mutate in the first place.

Functional programming isn't all about immutable values however. That's the technical explanation of it. From a conceptual standpoint, Functional programming is about expressing a calculation.

Code: Select all

const auto new_velocity = old_velocity + acceleration * time;
const auto new_position = old_position + new_velocity * time;
Imperative programming on the other hand is about stating actions that you want to execute in the exact order that you want to execute them in.

Code: Select all

boot.raise();
boot.move_over_to(bug);
boot.step_on_whatever_is_underneath();
While statements can be used to express a calculation, Functional programming is simply more direct about it.

Here is a good example of what mainly Imperative style code would look like

Code: Select all

template<typename iterator>
void quick_sort(const iterator begin, const iterator end)
{
	if (begin == end)
	{
		return;
	}

	auto middle = *begin;
	auto lower_end = begin + 1;

	for ( auto it = begin + 1; it != end; ++it )
	{
		if ( *it < middle )
		{
			std::swap ( *lower_end, *it );
			++lower_end;
		}
	}

	std::swap ( middle, *( lower_end - 1 ) );

	quick_sort ( begin, lower_end - 1 );
	quick_sort ( lower_end, end );
}
Although you can see clearly what is being done, it can be hard to tell what exactly is happening in this code snippet. Now here's what a purely Functional style code would do instead.

Code: Select all

template<typename List>
auto quick_sort(List list)
{
	if(!list.empty())
	{
		auto [middle, list_to_sort] = list.pop_front();
		
		auto [lower, upper] = list_to_sort.split(Int < middle);
		
		return merge(quick_sort(lower), middle, quick_sort(upper));
	}
	else
	{
		return list;
	}
}
Functional programming is simply better at expressing the results of a calculation while Imperative programming is better at stating the actual actions that are taking place.

Some of you might look at these two snippets of code only to ask "wouldn't that be a much less optimal way of doing quick sort since you're returning a new array every time?" You are not wrong. I've done benchmarks on both on these implementations and on average, the Functional code runs 60% slower. That percentage is not something that you can easily scoff at. A game that runs on a buttery smooth 60fps would be running at 37fps instead if is was 60% slower.

By trying to make your code more expressive, you sacrifice your ability to truly specify the most optimal order of steps to take for a certain procedure. On average, running Functional code would consume much more memory and do actions that, while more expressive, are less optimal than Imperative code that just does what it needs to do.

For this reason, some people prefer to take the middle ground; write functions that do Imperative actions when it matters but try to make them as Functional-like as possible. In places where it won't matter as much, they'll just go pure Functional and not bother trying to minimax it.

However, this doesn't mean that Functional programming is always less optimal than Imperative programming. Nowadays, Functional programming has picked up a lot of optimization techniques in its implementation that make it much more optimal than before. These optimizations can even make it more optimal than the Imperative version by allowing the compiler to make much more assumptions than it would have been able to with mutable variables. Not to mention that with the rise of concurrency, Functional programming has become much more prominent in the industry as it is more easily able to handle the concept of concurrent execution. Most of these are better off being their own topics so I won't discuss them in detail here.

But performance was never the real strength of Functional programming. The strength of Functional programming lies in the mindset it puts you in by treating every operation you do as a calculation. A computer is just a programmable calculator and a program is just a giant function that calculates an output like an image or text. Instead of calculating this output on its own, it passes its input to other functions which then passes their output as input to other functions. As data gets passed from function to function, it morphs and transforms into different forms until eventually, it transforms into the output. This output is then sent to the monitor or speaker where it will then be displayed to the user. In a way, Functional programming represents what a computer truly is better than Imperative programming ever did.
Last edited by cyboryxmen on March 8th, 2019, 3:59 pm, edited 8 times in total.
Zekilk

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Going Declarative with Functional programming

Post by albinopapa » March 5th, 2019, 10:36 am

I see where you are coming from, and the benefit functional programming offers for multi-threading is enticing.

Imperative programming can be just as expressive to be honest. Functions are a bunch of steps that need to be executed. So it would make sense to group smaller bits of code into a named function and build other functions from those smaller steps.

The immutability of objects as I understand it is the driving force behind functional programming. I can see doing it in certain cases, such as maybe a Vec2D/Vec3D, objects that are no larger than 64 bytes in size ( cache line size ). Anything larger or anything that allocates on the heap, I can't imagine with the exception of NEEDING the original after the transformation. Though with C++17's RVO and NRVO guaranteed ( in most cases ), it's becoming even easier to accept using return by value instead of using in/out params.

The only time I have seriously used functional programming is with SIMD. Everything was const __m128, which as pretty annoying coming up with names for the in between steps of a calculation, or horribly unreadable.

Code: Select all

__m128i alphahi = _mm_shufflehi_epi16( srchi, _MM_SHUFFLE( 3,3,3,3 ) );
alphahi = _mm_shufflehi_epi16( alphahi , _MM_SHUFFLE( 3,3,3,3 ) );

// or

const __m128i alphahi = _mm_shufflehi_epi16( _mm_shufflehi_epi16( srchi, _MM_SHUFFLE( 3,3,3,3 ), _MM_SHUFFLE( 3,3,3,3 ) );

// or

const _m128i alphahiTemp = _mm_shufflehi_epi16( srchi, _MM_SHUFFLE( 3, 3, 3, 3 ) );
const _m128i alphahi = _mm_shufflehi_epi16( alphahiTemp, _MM_SHUFFLE( 3, 3, 3, 3 ) );
So, there is one issue with the third one and that's leaking out to the rest of the function when it could be popped from the stack once I get my alphahi value. It's not really a big deal really, but it's still unnecessary. You could write an immediately invoked lambda to have the alphahi returned and the lambda could be the first implementation.

Code: Select all

const auto alphahi = [&]{ 
	const auto alphahi = _mm_shufflehi_epi16( srchi, _MM_SHUFFLE( 3,3,3,3 ) );
	return _mm_shufflehi_epi16( alphahi, _MM_SHUFFLE( 3,3,3,3 ) );
}();
To be fair, I've tried all four and I still don't know which I prefer, they all suck. I enjoy the speed increase using SIMD instructions give, but I fund it very cumbersome to write and to plan for. I suppose if I had to choose one, the lambda option is probably the easiest, to maintain const-ness and avoid temp named variables and to be honest read/follow assuming you know SSE instructions.

NOTE: It's been awhile since I've had to write this, so the second shuffle command might be wrong and might be _mm_shufflelo_epi16 instead. It's suppose to broadcast the bottom value ( alpha ) to all eight 16 bit slots first the higher eight slots, then the lower eight slots for those that haven't looked into SSE instructions and are wondering.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
cyboryxmen
Posts: 190
Joined: November 14th, 2014, 2:03 am

Re: Going Declarative with Functional programming

Post by cyboryxmen » March 5th, 2019, 12:56 pm

albinopapa wrote:
March 5th, 2019, 10:36 am
Functions are a bunch of steps that need to be executed.
This is where your Imperative bias is clouding your judgement.

If you've read up on the von Neumann machine(the model all modern computers base themselves off of), you'll know that a computer is just a programmable calculator. By that logic, a program is just a calculation takes in input and then calculates an output based on that. This output can be a number but can also include things like an image, sound or just pure text. Instead of calculating this output on its own, it passes the data to other functions which then passes their output to other functions. As data gets passed from function to function, it morphs and transforms into different forms depending on the calculation you need it for until eventually, it transforms into its final value. In a way, Functional programming represents what a computer truly is better than Imperative programming ever did.
Last edited by cyboryxmen on March 5th, 2019, 5:16 pm, edited 2 times in total.
Zekilk

User avatar
cyboryxmen
Posts: 190
Joined: November 14th, 2014, 2:03 am

Re: Going Declarative with Functional programming

Post by cyboryxmen » March 5th, 2019, 1:45 pm

If you want to learn more about this, you can go look up on lambda calculus
Zekilk

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Going Declarative with Functional programming

Post by chili » March 5th, 2019, 1:52 pm

Image
Chili

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Going Declarative with Functional programming

Post by albinopapa » March 5th, 2019, 5:53 pm

@Chili, that gif is wasted on me, not sure what it's suppose to mean, no context, no subtitles, now sound.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Going Declarative with Functional programming

Post by albinopapa » March 5th, 2019, 7:39 pm

cyboryxmen wrote:As data gets passed from function to function, it morphs and transforms into different forms depending on the calculation you need it for until eventually, it transforms into its final value.
Transformation would not be the correct word in my opinion to describe functional programming then. Transformation is morphing a thing into something new, but still remains to be the same object, like changing the state of an object to behave differently.

Something along the lines of what you describe would be a pipeline or call graph of filters for images or sound. Make a copy of the source, send to first stage/filter/function after transforming the data, pass to next stage/filter/function and so on. Can you honestly say that all programs can follow this pattern in all cases?

Just out of curiosity, how would a game loop benefit from functional programming? Your entities need to maintain state and have their state updated to reflect it's new position, change in speed and health as examples. So instead of updating a player's velocity internally, you'd just create a new PlayerEntity with the new velocity, then what? Your original entity is static, here meaning immutable, so you lose any changes past the one function and therefore cannot "make entities move" across the screen.

Even if your entity isn't immutable, I'm never going to create a whole new entity just to update the velocity, then another to update it's position, then another to change the sprite frame. Now, I have created Position and Velocity classes that can be easily to update by replacing the entire structure because it's eight or twelve bytes total, even if it were the case that only one of the members ( x, y or z ) are the only thing that has changed. This I would consider a transformation as the PlayerEntity would remain the same object, where only the Velocity and therefor the Position and SpriteFrame will change.

When I was working on my software 3D program, I had the stages of the pipeline pass by value as I needed the source to remain the same, but needed to "transform" the vertices from model space to view space. This is where it makes sense to use functional programming idioms. The rest of the program where the logic lies, I wouldn't even know where to begin. The reason something like this or passing data through filters works is because the result is basically discarded after it's final use and form. You have your source vertices that remain immutable, a copy is made then transformed to their final position then rendered then thrown away. Source image data is immutable, then copied, the copy is then transformed to produce lightening or darkening or transparent. The "transformed" copy can then be saved to disk or used as a texture, but the original source image data doesn't ever need to be replaced except to maybe be replaced when the user saves and overwrites the original to disk. Video and audio that go through filters maintain their original source, and a copy is made only for the goal of presentation and the results ( final form ) are discarded.

All that was to point out that I don't see how that can be synonymous with a game loop where state must be maintained and must be alterable. It may not always be about speed, and you are correct about my use of the word function, as I should have used procedure instead.

The distinction between function and procedure is a bit difficult for most because they are often used interchangeably, however those who take functional programming or mathematicians would argue that functions serves a specific "function" of transforming data, whereas a procedure is a list of steps to be executed mostly in order, even transforming data or state of an object.

Functional programming has it's place like all things, and I can see the appeal. Since objects do not share or modify their state, multi-threading is threadsafe. Going by your quick sort examples, the functional version looks sexy as hell, and I would definitely like to get my code to look that clean and perhaps some tinkering or new perspective would take care of the 30%+ deficit in performance, but I doubt it.

As I sit here thinking about it, each transformation function would NEED to return a new copy so that in the event that they were called in a different order or some not called, they would still be able to stand on their own. This means that an object that has to go through ten transformations, would create at least ten copies just for the output parameters alone and another ten for the input parameters. So, maybe you could cut the copies in half by making a single copy outside the first function and passing it by reference and returning by value. The transformation is done on the copy's data, then passed by reference to the next transformation function and so on, and then once the final transformation is complete, the result is returned by value all the way back up the call chain.

Code: Select all

// Pass by reference, return by reference
class Image
{
public:
   template<typename T>Image( T&& _filename );
   Image(const Image&)=delete;
   Image& operator=(const Image&) = delete;
   Image clone()const;
   Image& Lighten( float _value ) noexcept;
   Image& IncreaseContrast( float _value ) noexcept;
   Image& AlphaBlend( const Image& _other ) noexcept;

private:
   std::unique_ptr<Color[]> m_pPixelData;
   std::size_t m_width = 0, m_height = 0;
};

Image water( "Images\\Water.png" );
Image riverbed( "Images\\riverbed.png" );
Image river = water.clone().Lighten( .1f ).IncreaseContrast( .2f ).AlphaBlend( riverbed );
I would think creating the river Image object in this way would be more efficient than having each of those transformation functions create a new copy to work on and returning them by value.

Alternative 1:

Code: Select all

// Pass by value, return by value
Image water( "Images\\Water.png" );
Image riverbed( "Images\\riverbed.png" );
Image river = AlphaBlend( IncreaseContrast( Lighten( water, .1f ), .2f ), riverbed );
Alternative 2:

Code: Select all

// Pass by value, return by value
const Image water( "Images\\Water.png" );
const Image riverbed( "Images\\riverbed.png" );
const Image lightened_water = Lighten( water.clone(), .1f );
const Image lightened_contrasted_water = IncreaseContrast( lightened_water , .2f );
const Image river = AlphaBlend( lightened_contrasted_water, riverbed );
Alternative 3:

Code: Select all

// Pass by reference, return by value
const Image water( "Images\\Water.png" );
const Image riverbed( "Images\\riverbed.png" );
Image river = water.clone();
river = Lighten( river, .1f );
river = IncreaseContrast( river, .2f );
river = AlphaBlend( river, riverbed );
Alternative 4:

Code: Select all

class Image
{
// Pass by reference, Return by value
public:
   template<typename T>Image( T&& _filename );
   Image(const Image&)=delete;
   Image& operator=(const Image&) = delete;
   Image clone()const;
   Image Lighten( float _value )const;
   Image IncreaseContrast( float _value )const;
   Image AlphaBlend( const Image& _other )const;

private:
   std::unique_ptr<Color[]> m_pPixelData;
   std::size_t m_width = 0, m_height = 0;
};

Image water( "Images\\Water.png" );
Image riverbed( "Images\\riverbed.png" );
Image river = water.Lighten( .1f ).IncreaseContrast( .2f ).AlphaBlend( riverbed );
Here, you gain immutability at the expense of possible exceptions. Each new Image has the chance to throw because of heap allocation and the same would hold true for Alternatives 1 and 2 since they keep around so many temp variables, remember state shouldn't be able to change in functional programming. Alternative 3 isn't functional programming as the same object is used over and over for input and output.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
cyboryxmen
Posts: 190
Joined: November 14th, 2014, 2:03 am

Re: Going Declarative with Functional programming

Post by cyboryxmen » March 9th, 2019, 3:56 am

If you've read my last post, you'll know that a player is never just a player. In a multiplayer game, you may start with 4 players receiving input from the network. Then, those players will get transformed into a generic physics object and be inserted into a list with all the other physics objects. After updating their positions, those physics objects will then transform into generic collision objects and be inserted into a list with all the other collision objects. After detecting all collisions in the frame, those collision objects will be transformed into generic renderable objects and be inserted into a list with all the other renderable objects. After rendering everything onto the screen, you'll take the calculations that you want to save and pass them onto a new "task" for the program to run. More on that later.

It's never enough to just have a player datatype. You need to have different datatypes for the different calculations if you want to be efficient. Since you're transforming the very datatype of the data you're operating on, you're forced to allocate and not just mutate the data. Doing so makes the data much more compact and easily processable.

You'll understand this much better once you get into GPGPU where all you ever do is calculate values.
Zekilk

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Going Declarative with Functional programming

Post by albinopapa » March 9th, 2019, 6:25 am

Ok, I think I see what you mean about the player.

I think this would be,
create updater list,
fill updater list
run updater list
updater list returns a newly transformed collider list
run handle collisions, get a newly transformed renderer list
run renderer list
after rendering, it would return an updater list
pop the old task off the queue, add new task for updater list

Is that about right?
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
cyboryxmen
Posts: 190
Joined: November 14th, 2014, 2:03 am

Re: Going Declarative with Functional programming

Post by cyboryxmen » March 11th, 2019, 4:01 am

Essentially, yeah.

When you put it all together, a simple console program would look like this:

Code: Select all

auto start()
{
	return PrintJob{"Hello world!\n", printCallback};
}

auto printCallback = [](ConsoleState console)
{

	return GetInputJob<int>{getInputCallback};
}

auto getInputCallback = [](ConsoleState console, int input)
{
	auto output = std::string{"You have outputted"} + std::to_string(input) + '\n';
	return PrintJob{output, finalCallback(input)};
}

auto finalCallback(int input)
{
	return [input](ConsoleState console)
	{
		auto output = std::to_string(input) + " multiplied by 2 is " + std::to_string(input * 2);
		return PrintJob{output};
	}
}
If you want to return multiple jobs to run simultaneously, just return a tuple/vector instead. Just set a callback that the multiple jobs will join into. From this primitive structure, you can write your own expressive Functional code that efficiently creates tasks for a task-based program.
Zekilk

Post Reply