## Functional Pipelines

### Functional Pipelines? What's that?

I came across this term when working through Barski's Land of Lisp (be sure to check out his site Lisperati as well!) on page 309. I've googled around a bit and there seems to be no formal definition on the web, Pipeline Programming comes up frequently as a result of my queries, and although it seems similar i don't quite think that it's an exact explanation for what we're about to do. So for all practical purposes we'll stick with Barski's definition: "A succession of functions that operate, one after another, on a big chunk of data."

But before we get into that, we should think about what the important concepts in functional programming are and what it really means to "think functionally".

### Data

According to Paul Callaghan in his article Thinking Functionally with Haskell, the most important concept in functional style programming is this:

You should read the post to for a deeper look at his ideas and reasons behind them, but it boils down to this: The code should focus on what kind of data is being entered and the various transformations of the data that have to be done in order to achieve our goals.

This thinking is perfect for discussing and understanding the technique that Barski talks about and demonstrates in his chapter on writing a game in the functional style. We won't go into too much detail here, instead I will try to show the broad strokes and the logic that is being applied. For those who want a more specific example, go buy the book and read Chapter 15.

### Pipelines and Data

The basic premise here is that, instead of modifying the input we are given, we take the data and pipe it into functions, which create new sets of data based on their particular algorithms, without touching the original arguments. The term pipeline is used because the functions each take the output of other functions as their input, thus chaining them together. This is called the composition of functions in math (this differs from the concept of passing around first-class functions wherein functions take other functions, not their results, as their arguments).

Let's do a quick example, just to explain the basic concept. Suppose we want a list (or array, or tuple, or... you get the idea) of all the natural numbers, under a thousand, that are multiples of either 3 or 5. In Lisp I can define a function that gives me the results thus:

When run:

Now we get to the first pipeline. What if we want a list of all natural numbers under a thousand, multiples of 3 or 5, and even? We could rewrite the original function to include this capability but that would be sub-optimal in a few ways. First of all you never know when you want a complete list, not just the even numbers. Second of all you would miss out on creating another function that can be used elsewhere, not just in this scenario.

So we'll write a function that takes a list as its argument and returns, without touching the original input, a new list that consists of only the even members of the first list.

Now once we apply it to the results of the under-1000 function we get...

So you can see how the argument of my-even is given as the result of under-1000. Of course my-even will take any list as its argument, and this is also why it is a much better idea to decouple the two functions in this manner. If you need to apply an "even number filter" on other lists, other results of functions, then you can just call my-even and pass them those results. If we had coded the "even number filter" into the function under-1000 itself, we wouldn't be able to use it in any other place.

Now what if we want to add the results of my-even and under-1000 together? We would just write another function that would take a list and add their elements, returning the total.

For this example I'll use an in-built feature of Lisp called reduce.

You can see a three-tier chaining of functions here. The results of under-1000 are piped into the function my-even, which filters them and removes the odd numbers, these are then further piped into reduce, which takes all the elements and adds them up.

$$\boxed{\text{under-1000 }} \rightarrow \boxed{\text{my-even }} \rightarrow \boxed{\text{reduce }}$$

Nowhere in the code is there any sort of variable assignment or use of mutable data, the results of each functions are entirely new data sets; the argument that was passed into each of them remains untouched.

### The Game Example

So say that we have a 2 player game, and we have to find a way to code it in such a way that it can be expanded into a 3, 4, or even 5 player game. We might or might not want to change the rules, and we will probably want to add an AI opponent later on.

To make the addition of an AI player easier, and to showcase the pipeline technique, we will create code that will output a game-tree, a list of all possible moves from a starting position.

We will need 3 basic chunks of code:

• The game-tree function
• A chunk that handles the human input
• The AI code

We will feed the initial data from the game-tree function (a list of all possible moves) to the handle-human part(and AI if we're playing as one player) of our code, the handle-human function will then further refine the list of possible moves (based on the human player's choices) until there are no possible moves and there is a winner or a draw is declared.

### game-tree

So let's take a look at what the game-tree function is composed of. Basically it will take as an input a starting board (this is randomly generated by another function, it contains starting positions), the player whose turn it is, and a list of all possible moves (these are represented as board positions) from that particular board representation. It then calls itself and passes the new board positions (the possible moves) to itself, thus creating a new list of possible board combinations based on the previous possible movements.

$$\large{ \text{game-tree} \\ {\rm~~}\Rightarrow \text{player} \\ {\rm~~}\Rightarrow \text{board} \\ {\rm~~}\Rightarrow \text{possible-moves} \\ {\rm~~~~}\Rightarrow \text{game-tree} \\ {\rm~~~~~~}\Rightarrow \text{player} \\ {\rm~~~~~~}\Rightarrow \text{board} \\ {\rm~~~~~~}\ldots \ldots \ldots \\ {\rm~~~~~~}\ldots \ldots \ldots \\ }$$

Let's generate a random example to give some visual imagery to what we're talking about.


(0 #((0 2) (1 2) (1 1) (1 1))
(((0 2)
(0 #((0 1) (1 2) (0 1) (1 1))
((NIL
(1 #((0 1) (1 2) (0 1) (1 1))
(((1 0)
(1 #((1 1) (1 1) (0 1) (1 1))
((NIL (0 #((1 1) (1 1) (0 1) (1 1)) NIL)))))))))))
((0 3)
(0 #((0 1) (1 2) (1 1) (0 1))
((NIL
(1 #((0 1) (1 2) (1 1) (0 1))
(((1 3)
(1 #((0 1) (1 1) (1 1) (1 1))
((NIL (0 #((0 1) (1 1) (1 1) (1 1)) NIL)))))
((1 0)
(1 #((1 1) (1 1) (1 1) (0 1))
((NIL (0 #((1 1) (1 1) (1 1) (0 1)) NIL)))))))))))))

This is the result of calling the game-tree function.

The highlighted section designates the player whose turn it is, 0 is for player A and 1 is for player B; at the moment it is player A's turn. The next bit is the present board: here it's saying that player A occupies one square of the board with 2 dice, while player B has 3 squares with 2, 1, and 1 die respectively.


(0 #((0 2) (1 2) (1 1) (1 1))
(((0 2)
(0 #((0 1) (1 2) (0 1) (1 1))
((NIL
(1 #((0 1) (1 2) (0 1) (1 1))
(((1 0)
(1 #((1 1) (1 1) (0 1) (1 1))
((NIL (0 #((1 1) (1 1) (0 1) (1 1)) NIL)))))))))))
((0 3)
(0 #((0 1) (1 2) (1 1) (0 1))
((NIL
(1 #((0 1) (1 2) (1 1) (0 1))
(((1 3)
(1 #((0 1) (1 1) (1 1) (1 1))
((NIL (0 #((0 1) (1 1) (1 1) (1 1)) NIL)))))
((1 0)
(1 #((1 1) (1 1) (1 1) (0 1))
((NIL (0 #((1 1) (1 1) (1 1) (0 1)) NIL)))))))))))))

These instead are the possible moves of A (the first number designates the player). He can either go to the third square or the fourth square (the count starts at 0, 0 is square 1, 1 is square 2, etc.)


(0 #((0 2) (1 2) (1 1) (1 1))

(((0 2)
(0 #((0 1) (1 2) (0 1) (1 1))
((NIL
(1 #((0 1) (1 2) (0 1) (1 1))
(((1 0)

(1 #((1 1) (1 1) (0 1) (1 1))
((NIL (0 #((1 1) (1 1) (0 1) (1 1)) NIL)))))))))))
((0 3)
(0 #((0 1) (1 2) (1 1) (0 1))
((NIL
(1 #((0 1) (1 2) (1 1) (0 1))
(((1 3)
(1 #((0 1) (1 1) (1 1) (1 1))
((NIL (0 #((0 1) (1 1) (1 1) (1 1)) NIL)))))
((1 0)
(1 #((1 1) (1 1) (1 1) (0 1))
((NIL (0 #((1 1) (1 1) (1 1) (0 1)) NIL)))))))))))))


If A goes to square 3 then the results will be as follows, It is still player A's turn, and he will occupy squares 1 and 2 with 1 die each, while B will have squares 2 and 4 with 2 and 1 die respectively.

However with the present board he has no more possible moves, hence the NIL, and the turn will pass to B, who has only one move open to him.

So we can see that game-tree will create a tree of all possible moves given a starting position. This is the data that we will pass into our functions, which will then transform the data (in our case as you will soon see, it will merely chop off irrelevant moves) and then recursively pass it again into the said functions.

### handle-human

Now we pass on to the function that handles the human decisions regarding which squares to attack. The code looks like this

$$\large{ \text{handle-human} \leftarrow \text{tree}\\ {\rm~~}\Rightarrow \text{list of moves for player} \\ {\rm~~~~}\rightarrow \text{choose-a-move} \\ {\rm~~~~~~}\Rightarrow \text{returns the branches (or nodes) belonging to that move (let's call this new-tree)} \\ {\rm~~~~~~}\Rightarrow \text{handle-human} \leftarrow \text{new-tree}\\ }$$

So what's happening here? handle-human takes a tree with all the possible moves from the present position as its argument, displays the moves to the player, and waits for a choice. The player chooses a move, then handle-function will take the branches of the tree that belong to the move (which contain all the possible moves from that position), discard the other nodes (they are no longer relevant to the game), and call itself with the newly-revised tree as the new input.

Let's show a possible execution as an example. We'll use the same tree as in the previous example to make it easier:

(0 #((0 2) (1 2) (1 1) (1 1))
(((0 2)
(0 #((0 1) (1 2) (0 1) (1 1))
((NIL
(1 #((0 1) (1 2) (0 1) (1 1))
(((1 0)
(1 #((1 1) (1 1) (0 1) (1 1))
((NIL (0 #((1 1) (1 1) (0 1) (1 1)) NIL)))))))))))
((0 3)
(0 #((0 1) (1 2) (1 1) (0 1))
((NIL
(1 #((0 1) (1 2) (1 1) (0 1))
(((1 3)
(1 #((0 1) (1 1) (1 1) (1 1))
((NIL (0 #((0 1) (1 1) (1 1) (1 1)) NIL)))))
((1 0)
(1 #((1 1) (1 1) (1 1) (0 1))
((NIL (0 #((1 1) (1 1) (1 1) (0 1)) NIL)))))))))))))


handle-human will display two possible moves to player A.

(0 2) -> square one to three (0 3) -> square one to four

Let's say A chooses the second choice, square one to four. handle-human then takes the nodes belonging to that particular choice and discard the rest.


(0 #((0 2) (1 2) (1 1) (1 1))
(((0 2)
(0 #((0 1) (1 2) (0 1) (1 1))
((NIL
(1 #((0 1) (1 2) (0 1) (1 1))
(((1 0)
(1 #((1 1) (1 1) (0 1) (1 1))
((NIL (0 #((1 1) (1 1) (0 1) (1 1)) NIL)))))))))))

((0 3)
(0 #((0 1) (1 2) (1 1) (0 1))
((NIL
(1 #((0 1) (1 2) (1 1) (0 1))
(((1 3)
(1 #((0 1) (1 1) (1 1) (1 1))
((NIL (0 #((0 1) (1 1) (1 1) (1 1)) NIL)))))
((1 0)
(1 #((1 1) (1 1) (1 1) (0 1))
((NIL (0 #((1 1) (1 1) (1 1) (0 1)) NIL)))))))))))))



This new tree is then passed again to handle-human which will determine if there are possible moves from the new position. According to the tree there are none, as evidenced by the NIL. The turn then passes to player B, who has two choices: square two to three or square two to one.


((0 3)
(0 #((0 1) (1 2) (1 1) (0 1))
((NIL
(1 #((0 1) (1 2) (1 1) (0 1))

(((1 3)

(1 #((0 1) (1 1) (1 1) (1 1))
((NIL (0 #((0 1) (1 1) (1 1) (1 1)) NIL)))))

((1 0)

(1 #((1 1) (1 1) (1 1) (0 1))
((NIL (0 #((1 1) (1 1) (1 1) (0 1)) NIL)))))))))))))


Player B takes the first choice, square two to three, and handle-human again picks up all the child nodes belonging to that particular branch and drops the rest.


(((1 3)
(1 #((0 1) (1 1) (1 1) (1 1))
((NIL (0 #((0 1) (1 1) (1 1) (1 1)) NIL)))))



And so on until there are no possible moves and a draw or a winner is declared.

### So what happened exactly?

So what's so special about the way this game was coded?

What stands out here is that there were no changes of state with regards to the data; the initial data was not modified in any way.

1. game-tree takes a starting board and produces all possible moves.
2. handle-human takes the tree and displays the moves available.
3. player makes his choice, and handle-human makes a new tree based on the choice made.
4. go back to step 2

This is an exemplary representation of the concept "data first". The code was based around the data given by game-tree and worked around transforming that data based on player decisions. Each transformation gave rise to a new tree; the old data was not touched, hence there was no assigning of variables, no book-keeping of state, of any kind.

This is what Functional Pipelines are all about, taking initial data and passing it around from function to function, each function taking the result of the previous function as its input. The advantage of this type of programming is that since there is no (or minimal) variable assignment, you can more or less be sure that the functions will always have the same result if they are called with the same input. This makes debugging code incredibly easy and hassle-free.

Of course some state is inevitable, but the idea here is to keep it to an absolute minimum.

### Where to Go from Here

The complete source (the AI code is missing from this example) can be found in the book Land of Lisp.

Joel's Can your Programming Language do This? (talks about first-class functions and the map and reduce functions)