Results 1 to 13 of 13

Thread: Functional Programming in Simba Scripts

  1. #1
    Join Date
    Jan 2011
    Location
    Denver, CO
    Posts
    1,351
    Mentioned
    2 Post(s)
    Quoted
    72 Post(s)

    Default Functional Programming in Simba Scripts

    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 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 and Scala. Some of my favorite programming languages with a focus on functional programming include Clojure and 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:

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

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

    begin
      BankLogs;
    end.

    Simba Code:
    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:

    Simba Code:
    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:

    Simba Code:
    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:

    Simba Code:
    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:

    Simba Code:
    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:

    Simba Code:
    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:

    Progress Report:
    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:

    Simba Code:
    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:

    Progress Report:
    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:

    Simba Code:
    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
    Last edited by Echo_; 05-01-2012 at 03:21 PM.

  2. #2
    Join Date
    Feb 2012
    Location
    Somewhere, over the rainbow...
    Posts
    2,272
    Mentioned
    3 Post(s)
    Quoted
    45 Post(s)

    Default

    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?

  3. #3
    Join Date
    Oct 2006
    Location
    Netherlands
    Posts
    3,285
    Mentioned
    105 Post(s)
    Quoted
    494 Post(s)

    Default

    Quote Originally Posted by abu_jwka View Post
    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;
    Working on: Tithe Farmer

  4. #4
    Join Date
    Jan 2011
    Location
    Denver, CO
    Posts
    1,351
    Mentioned
    2 Post(s)
    Quoted
    72 Post(s)

    Default

    Quote Originally Posted by abu_jwka View Post
    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).

  5. #5
    Join Date
    Jun 2007
    Location
    Wednesday
    Posts
    2,446
    Mentioned
    3 Post(s)
    Quoted
    1 Post(s)

    Default

    Simba Code:
    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.

    Simba Code:
    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.
    By reading this signature you agree that mixster is superior to you in each and every way except the bad ways but including the really bad ways.

  6. #6
    Join Date
    Nov 2006
    Posts
    2,369
    Mentioned
    4 Post(s)
    Quoted
    78 Post(s)

    Default

    Nice tutorial. I liked the Higher-order Functions part.
    Quote Originally Posted by DeSnob View Post
    ETA's don't exist in SRL like they did in other communities. Want a faster update? Help out with updating, otherwise just gotta wait it out.

  7. #7
    Join Date
    Jan 2011
    Location
    Denver, CO
    Posts
    1,351
    Mentioned
    2 Post(s)
    Quoted
    72 Post(s)

    Default

    Quote Originally Posted by mixster View Post
    Simba Code:
    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.

    Simba Code:
    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:

    Simba Code:
    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:

    Simba Code:
    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;
    Last edited by Echo_; 04-23-2012 at 09:39 PM.

  8. #8
    Join Date
    Jun 2007
    Location
    Wednesday
    Posts
    2,446
    Mentioned
    3 Post(s)
    Quoted
    1 Post(s)

    Default

    Simba Code:
    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.
    By reading this signature you agree that mixster is superior to you in each and every way except the bad ways but including the really bad ways.

  9. #9
    Join Date
    Jan 2011
    Location
    Denver, CO
    Posts
    1,351
    Mentioned
    2 Post(s)
    Quoted
    72 Post(s)

    Default

    Quote Originally Posted by mixster View Post
    Simba Code:
    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

  10. #10
    Join Date
    Jan 2011
    Location
    Denver, CO
    Posts
    1,351
    Mentioned
    2 Post(s)
    Quoted
    72 Post(s)

    Default

    [UPDATE] I changed the recursion diagram to better model the call stack.

  11. #11
    Join Date
    Feb 2007
    Location
    PA, USA
    Posts
    5,240
    Mentioned
    36 Post(s)
    Quoted
    496 Post(s)

    Default

    nice tut!

  12. #12
    Join Date
    Jan 2011
    Location
    Denver, CO
    Posts
    1,351
    Mentioned
    2 Post(s)
    Quoted
    72 Post(s)

    Default

    Quote Originally Posted by footballjds View Post
    nice tut!
    Thanks

  13. #13
    Join Date
    Jan 2011
    Location
    Denver, CO
    Posts
    1,351
    Mentioned
    2 Post(s)
    Quoted
    72 Post(s)

    Default

    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)

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •