PDA

View Full Version : Functional Programming in Simba Scripts



Echo_
04-23-2012, 02:35 PM
Functional Programming in Scripts
by Echo_

Welcome to my third tutorial. This tutorial will focus on the functional programming paradigm and how we can use it to make writing and debugging Simba scripts easier. You do not have to use this paradigm to have a better script, it's just a different way of approaching script writing. Some people may prefer this style once they learn it, and some will not. It really doesn't matter. Note that some of the examples in this tutorial are only compatible with Lape and not PascalScript, so if you want to try the examples for yourself you will have to switch interpreters. So let's get started.


What is Functional Programming?

Functional Programming (http://en.wikipedia.org/wiki/Functional_programming) is a style of programming that focuses on ideas found in lambda calculus. You do not need any previous knowledge in calculus to understand this style, but having some knowledge of math would be to your advantage.

Functional programming emphasizes the structural building of a program through "pure functions". You start with a few small functions, you write functions using those functions, and the script builds up from there. Now don't worry if you don't know what a pure function is right now, it will all be explained later. Functional Programming also focuses on "higher-order functions" and "recursion", which will also be explained in more detail later.

Functional programming doesn't really rely upon complicated data types for its power, the main data type used is the function. Many languages have constructs that support functional programming, one of them being Pascal, but you can also find these in mixed-paradigm languages like Python (http://www.python.org/) and Scala (http://www.scala-lang.org/). Some of my favorite programming languages with a focus on functional programming include Clojure (http://clojure.org/) and Haskell (http://www.haskell.org/haskellwiki/Haskell). Because these languages require you to program functionally, it is much easier to implement multithreading and other features that would otherwise be hard to implement in a language with mutable data. But since Simba does not support multithreading at the moment, we won't discuss this advantage to programming in a functional style.


Pure Functions

You may remember functions from your earlier math classes. An simple example would be the following:

f(x) = x + 2

Making a table of the results:

----------
| x | f(x) |
----------
| 0 | 2 |
| 1 | 3 |
| 2 | 4 |
| 3 | 5 |
| 4 | 6 |
| 5 | 7 |
----------

As you can see, this function has one input and one output. The same input will always produce the same output. The function does not rely upon any global state to produce its result, it only relies upon its input. In functional programming, these attributes classify this function as "pure". Any function that relies upon global variables, outside IO (this includes grabbing colors from the screen and reading files), or changing global variables is not a pure function.

Now the goal of functional programming is not to completely eliminate impure functions, because without IO our script wouldn't really do anything. It would just be a black box. The goal is to limit impure functions and have most of the work done in pure functions that are controlled in the script. Since you are 100% sure of the outcome of a pure function by knowing its input, there is less searching for you when you have a bug in your script. Because at that point the only thing that could be causing the bug is outside contact, and that narrows your searching to the impure functions. It also helps to limit your use of global variables, an easy way to accomplish this is by declaring them just above your main loop and using them locally. Now this is hard for counters that need to be held throughout the runtime of the script, such as total logs chopped or whatever. But that can easily be fixed:


//LogsChopped can be accessed by every function in the script
var
LogsChopped: Integer;

procedure BankLogs;
begin
IncEx(LogsChopped, 28);
end;

begin
BankLogs;
end.



procedure BankLogs(var LogsChopped: Integer);
begin
IncEx(LogsChopped, 28);
end;

//LogsChopped can only be accessed by the main loop
var
LogsChopped: Integer;

begin
BankLogs(LogsChopped);
end.


By using this strategy you are keeping the variables in a place that they can be accessed at runtime, but they are encapsulated within the main loop and inaccessible by all other functions.


Higher-order Functions

And now for something interesting. Higher-order functions are functions that can take functions as arguments ore return functions as a result. Pascal has the ability to store procedures and functions in a variable so it has what we need to create higher order functions. The following will print "Hello, World!" when run:


procedure Proc;
begin
WriteLn('Hello, World!');
end;

var
P: procedure;

begin
P := @Proc;
P();
end.


As you can see, the "@" operator points the variable P to procedure Proc. Then you can execute it by calling P as if it is a function. Keep in mind that the parenthesis are mandatory in this context.

So say we want to write a higher-order function that filters unwanted elements out of an array and returns the remaining elements. We could accomplish that with the following higher-order function:


function Filter(P: function(I: Integer): Boolean; A: array of Integer): array of Integer;
var
J: Integer;
begin
for J := 0 to High(A) do
if P(A[J]) then begin
SetLength(Result, Length(Result) + 1);
Result[High(Result)] := A[J];
end;
end;


P is the predicate, or test function. It is run on each element of A, testing each element and removing it if it doesn't fit the requirements. This function is quite powerful because it is so abstract. You could pass in a million different predicates to fit your needs, the possibilities are endless. Here's an example of removing all odd numbers, all numbers less than five, and all numbers that aren't an even square:


function Even(I: Integer): Boolean;
begin
Result := I mod 2 = 0;
end;

function LessThanFive(I: Integer): Boolean;
begin
Result := I < 5;
end;

function EvenSquare(I: Integer): Boolean;
begin
if Int(Sqrt(I)) <> Sqrt(I) then
Result := False
else
Result := True;
end;

var
A, Evens, LessThanFives, EvenSquares: array of Integer;

begin
A := [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
Evens := Filter(@Even, A);
LessThanFives := Filter(@LessThanFive, A);
EvenSquares := Filter(@EvenSquare, A);
end.


As I said before, higher-order functions are also functions that return procedures or functions. Here is an example of this:


procedure Hello;
begin
WriteLn('Hello, World!');
end;

procedure Goodbye;
begin
WriteLn('Goodbye, World!');
end;

function Greeting(Morning: Boolean): procedure;
begin
if Morning then
Result := @Hello
else
Result := @Goodbye;
end;

var
Say: procedure;

begin
Say := Greeting(True);
//Prints Hello, World!
Say();
end.


And that's all there is to it :) Higher order functions can slim down your scripts by creating a generic algorithm and passing in a predicate for that algorithm to work with.


Recursion

Recursion is a method of creating looping behavior without using looping constructs (for and while loops for example). In a language with built in looping constructs like Pascal, recursion isn't really a requirement to script in a functional style. Believe it or not, there are languages (Haskell being one of them) that rely completely upon recursion to provide looping behavior in programs. Since understanding recursion is still important programming knowledge, here's how it works.

Recursion emulates looping by a function calling itself. There are different kinds of recursion. Linear recursion is a loop where the function can only call itself once per call. A perfect example of linear recursion would be an implementation of Pow:


function Power(Base: Extended; Exponent: Cardinal): Extended;
begin
if Exponent = 0 then
Result := 1
else
Result := Base * Power(Base, Exponent - 1);
end;


This may look confusing at first, but it makes perfect mathematical sense. We know that if the exponent is 0 then the answer is 1. We use this as the edge condition of the recursion. Edge conditions are meant to stop recursive calls from entering infinite loops by providing a condition that will eventually be met.

If the exponent isn't 0 then the answer is the base times the power of the base to the decremented exponent. We must decrement the exponent so that it eventually reaches the edge condition. You can think of it in this way for the problem 2 to the power of 8:

Power(2, 8)
0: Power(2, 8)
1: Power(2, 7)
2: Power(2, 6)
3: Power(2, 5)
4: Power(2, 4)
5: Power(2, 3)
6: Power(2, 2)
7: Power(2, 1)
8: Power(2, 0)
8: Result := 1
7: Result := 2
6: Result := 4
5: Result := 8
4: Result := 16
3: Result := 32
2: Result := 64
1: Result := 128
0: Result := 256
256

Once the function reaches the edge condition, it "bounces back" through the call stack and eventually returns the answer :)

Another way to approach linear recursion is using tail recursion. Tail recursion is often more effective for languages that feature tail call optimization, and I am unsure if either the PascalScript or Lape interpreters feature this. But this is how it works for the Power function we wrote earlier:


function Power(B: Extended; E: Cardinal; A: Extended = 1.0): Extended;
begin
if E = 0 then
Result := A
else
Result := Power(B, E - 1, A * B);
end;


This function uses the default parameters feature in Lape. Instead of multiplying the base by the result of the function, it just returns to the top of the function with new parameters. That tail call is what makes it more effective. With tail call optimization, the function will just return to the top of the function rather than making calls to the function and saving the parameters for each call.

In the Power function, we see that the result is "accumulated" in A, A is the accumulator variable. It holds the value of the function after each call. The invocation would look something like this:

Power(2, 8)
0: Power(2, 8, 1)
1: Power(2, 7, 2)
2: Power(2, 6, 4)
3: Power(2, 5, 8)
4: Power(2, 4, 16)
5: Power(2, 3, 32)
6: Power(2, 2, 64)
7: Power(2, 1, 128)
8: Power(2, 0, 256)
8: Result := 256
7: Result := 256
6: Result := 256
5: Result := 256
4: Result := 256
3: Result := 256
2: Result := 256
1: Result := 256
0: Result := 256
256

Multiple recursion is also possible, but it can get pretty slow. An example would be computing the Fibonacci numbers:


function Fibonacci(I: Cardinal): Cardinal;
begin
if I < 2 then
Result := I
else
Result := Fibonacci(I - 1) + Fibonacci(I - 2);
end;


As the call stack gets deeper, the function takes much longer to return a result. So recursion is not always a good way of approaching an algorithm.


Conclusion

This tutorial is shorter than I expected, but I will probably add more code examples and explanations later. Functional programming is a large topic, there are entire books dedicated to the subject. I hope you learned something, and if you have any questions or comments feel free to post :)

Abu
04-23-2012, 05:09 PM
Very nice tutorial! I've read until Recursions so far, I'll read some more later.

Just a quick question, do all higher-order functions require lape or just the final example?

masterBB
04-23-2012, 06:25 PM
Very nice tutorial! I've read until Recursions so far, I'll read some more later.

Just a quick question, do all higher-order functions require lape or just the final example?

Only this part: function Greeting(Morning: Boolean): procedure;

Echo_
04-23-2012, 07:09 PM
Very nice tutorial! I've read until Recursions so far, I'll read some more later.

Just a quick question, do all higher-order functions require lape or just the final example?

Yeah the pascalscript interpreter supports functions as parameters, but not as return types (no idea why).

mixster
04-23-2012, 07:58 PM
program ReturnProc;
type
proc = Procedure;

procedure Test();
begin
Writeln('Hello!');
end;

function ReturnTest(): proc;
begin
Result := @Test;
end;

begin
ReturnTest()();
end.


Lape does feature nested procedures and functions, so the future's bright.

Also, maybe it's clearer to illustrate tail-recursion "optimisation" through an example of what it may be "transformed" into.

function __PowerAux(B: Extended; E: Integer; A: Extended): Extended;
begin
while (True) do
begin
if E = 1 then
begin
Result := A;
Break;
end
else
begin
B := B;
E := E - 1;
A := B * A;
end;
end;
end;

function Power(Base: Extended; Exponent: Integer): Extended;
begin
Result := __PowerAux(Base, Exponent, Base);
end;


As a final little annoyance, the Power function really should have exponent = 0 as its edge case. All it takes is changing the time when it returns to exponent = 0 and setting result or the accumulator to 1, rather than base, at the beginning.

weequ
04-23-2012, 08:18 PM
Nice tutorial. I liked the Higher-order Functions part.

Echo_
04-23-2012, 09:31 PM
program ReturnProc;
type
proc = Procedure;

procedure Test();
begin
Writeln('Hello!');
end;

function ReturnTest(): proc;
begin
Result := @Test;
end;

begin
ReturnTest()();
end.


Lape does feature nested procedures and functions, so the future's bright.

Also, maybe it's clearer to illustrate tail-recursion "optimisation" through an example of what it may be "transformed" into.

function __PowerAux(B: Extended; E: Integer; A: Extended): Extended;
begin
while (True) do
begin
if E = 1 then
begin
Result := A;
Break;
end
else
begin
B := B;
E := E - 1;
A := B * A;
end;
end;
end;

function Power(Base: Extended; Exponent: Integer): Extended;
begin
Result := __PowerAux(Base, Exponent, Base);
end;


As a final little annoyance, the Power function really should have exponent = 0 as its edge case. All it takes is changing the time when it returns to exponent = 0 and setting result or the accumulator to 1, rather than base, at the beginning.

Thanks. I fixed what you said, but I tried the following nested function in Lape and it didn't compile:


function Power(Base: Extended; Exponent: Integer): Extended;
begin
function PowerAux(B: Extended; E: Integer; A: Extended): Extended;
begin
if E = 0 then
Result := A
else
Result := PowerAux(B, E - 1, B * A);
end;

Result := PowerAux(Base, Exponent, 1);
end;


and:


function Power(Base: Extended; Exponent: Integer): Extended;
function PowerAux(B: Extended; E: Integer; A: Extended): Extended;
begin
if E = 0 then
Result := A
else
Result := PowerAux(B, E - 1, B * A);
end;

begin
Result := PowerAux(Base, Exponent, 1);
end;

mixster
04-23-2012, 09:43 PM
function Power(Base: Extended; Exponent: Integer): Extended;
function PowerAux(B: Extended; E: Integer; A: Extended): Extended;
begin
if E = 0 then
Result := A
else
Result := PowerAux(B, E - 1, B * A);
end;

begin
Result := PowerAux(Base, Exponent, 1);
end;

begin
Writeln(Power(2, 3));
end.

It returns 8 for me.

May be that the latest stable Simba doesn't have a recent enough lape - I've been using a somewhat recent nightly build from mopar.

Echo_
04-23-2012, 10:25 PM
function Power(Base: Extended; Exponent: Integer): Extended;
function PowerAux(B: Extended; E: Integer; A: Extended): Extended;
begin
if E = 0 then
Result := A
else
Result := PowerAux(B, E - 1, B * A);
end;

begin
Result := PowerAux(Base, Exponent, 1);
end;

begin
Writeln(Power(2, 3));
end.

It returns 8 for me.

May be that the latest stable Simba doesn't have a recent enough lape - I've been using a somewhat recent nightly build from mopar.

Yep, it works in 0.99-rc4, so I guess function nesting is pretty new. I'll add the nested example and include that it only works in newer versions of Lape ;)

Echo_
04-25-2012, 03:30 PM
[UPDATE] I changed the recursion diagram to better model the call stack.

footballjds
04-25-2012, 03:40 PM
nice tut!

Echo_
04-25-2012, 03:50 PM
nice tut!

Thanks :)

Echo_
05-01-2012, 03:20 PM
UPDATE: I found an better way to use tail call recursion. Instead of using a nested function, I just used a default parameter for the accumulator variable (A: Extended = 1.0)