The purpose of this Spotlight is to demonstrate the use of the DoWhile module to loop within a Composable DataFlow.
The Fibonacci sequence is one of the best-known series in Mathematics. The series is composed of Fibonacci numbers, where the sum of each consecutive pair of numbers becomes the next number in the series (a + b = c). Since the addition of a new term yields a fresh consecutive pair to sum (b + c = d), this series is infinite (c + d = e, …).
More than a mere mathematical parlor trick, Fibonacci appears in designs both natural and man-made. Patterns described (or approximated) by Fibonacci are found in mathematics, computer algorithms, spiral structures from organisms to galaxies, architecture and design, the growth of plants and populations… even city planners can use Fibonacci in planning expansion of a power grid. I actually worked with a team that used Fibonacci numbers as a non-linear ranking of tasks in Scrum meetings.
Since Fibonacci is so useful in so many situations, how could we use a Composable DataFlow to generate this limitless list – and how do we constrain it so it doesn’t run forever?
At any given point in building out the Fibonacci series, we really only need access to three numbers: the two most recent, and the new number in the series that they create. Of course, we also need to be able to store the results as the series grows.
This is an iterative process, so we need a way to repetitively grab the two numbers to add, add them, add a new number to the series, and then start over again with the next “most recent pair”.
Lastly, since series this is theoretically infinite, we need to decide how to practically terminate a loop of otherwise undefined length.
Functionally, that means we need a minimum of six items: The start and endpoint of the loop, the three relevant values of the current iteration, and a way to identify the next pair.
In a Composable DataFlow, that means we need six modules and some thoughtful ways to link them together. If we wanted to expand the functionality, like inserting a value threshold, that would add another module (and we will do such things in a future exercise).
Let’s create a new DataFlow and think our way through the modules we want.
Starting the Loop:
Starting at the top, we need a way to iterate indefinitely.
As we saw in a prior Spotlight post, Spotlight: Looping with ForEach, For loops are great for iterating, but each loop has the number of iterations defined by the input list. Six items in the list means six trips through the loop.
For our task, the stopping point will be defined by conditions within the loop, not by list length. We need an iterator that will continue until conditions change.
That’s a textbook use case for a DoWhile module.
Like the ForEach module in the previously-mentioned blog post, we have InitialPassedOutputs and MaxIterations as inputs, but we do not have a List input.
For our use case, this is all we need.
The Fibonacci series commonly starts with 0 and 1 (i.e., [0, 1]) as the seed values, although there are those who use the next pair (0+1=1, so the next pair is [1, 1]). I have read that Fibonacci himself actually used the pair after that (1+1=2, so [1, 2] is the next pair) as his starting point.
We will choose [0,1] as our seed values. We will explore adding some user-driven flexibility, and the implications on F(n) (the Fibonacci series index) in a future post on Nested DataFlows.
We will also set MaxIterations to… 6 to start with, so that we can get some cycles in for testing.
Getting the Three Values:
The outputs passed from the DoWhile will contain a pair of values in a list/array structure. To parse those out individually, we can use the Array Indexer module.
We can connect the PassedOutputs output of the DoWhile to the Array input of an Array Indexer. We haven’t set up the endpoint of the loop yet, so I’m not concerned with iterations at this point.
Index 0 means that we will get the first value in the passed array.
When we run this, we can see that [0,1] is indeed the expected output and 0 the parsed value.
Note: If your line doesn’t look like mine and you want to change it, take a look at our DYK blog post on Changing Wire Type.
To get the second value in the pair, we can add a second Array Indexer, set its Index to 1, and connect the same output from the DoWhile to the new Array Indexer’s Array input.
Just as a double-check that we aren’t simply grabbing the index numbers, or some other defaults, we can set test values to something else, like … 7 and 5. We’ll replace the [0,1] later.
We can see [7,5] as the passed output and the 7 and 5 being parsed correctly, respectively.
To get our third value, we need to derive it by adding the other two together.
Here we can use the Calculator module.
We add the Calculator module and simply connect the Value outputs of our Array Indexers to the Param1 and Param2 inputs of the Calculator. Since we are summing, we can leave the Operator as “+”. I am also going to set the default input values in the Calculator to 0. That way, if there were an error, we have a known, expected value to test for that we wouldn’t get if the process was working (there is no 0 + 0 = 0 in Fibonacci). Not that I expect an error, but old programmer habits die hard.
Leaving our test values of [7,5] in place and running again, we can see the 7, 5, and 12 as the correct outputs from their respective modules.
To keep track of the pieces in our DataFlow so far, let’s rename the modules of the three values as Val1, Val2, and Val3, as appropriate.
Setting the “Next Pair”:
Now that we have our three values identified, it’s a simple step to set up the “next pair”
Let’s add an Array Builder module.
Now we connect the Value outputs from our data sources.
Many people would do this from the top down (Val3, then Val2), so I will do that to show the ramifications and how we can correct it without rewiring.
If we hover over the Array Builder’s InputCollection input, we see that the connection to Val3 has a 0, and Val2 shows a 1. If we were just adding two terms, it wouldn’t matter (a + b = b + a). But, in our case, we’re not dealing with the commutative property of addition. We need an array where the terms are in a specific order.
No need to worry. If you ever attach in a different order than you intended, or need, you can simply shift+right-click on the relevant input port. That pops up a list of the attachments, in the order that they will be handled. Better still, the list items are movable. Here, you can see that I have started to click-and-drag the lower list item (Val2) and move it up.
When rearranged, a click on the input shows that the index numbers have flipped to 1 and 0.
Let’s rename the Array Builder to Next Pair and run the DataFlow.
Here we can see that our test values [7,5] get parsed into 7 and 5, summed to 12, and our second term and new term (Val2, Val3) are correctly ordered [5, 12] as our Next Pair.
Restoring to our actual Fibonacci seed values of [0,1], we see we can finish the first round of processing as expected.
Now, [0,1] becomes 0 and 1, summed to 1, and [1,1] is the Next Pair.
Making the Loop Endpoint:
At this point, we have five of the six functions that we need in place.
What’s left? We need to make the loop, loop.
In the ForEach post, we discussed two types of endpoints, Loop Terminator and Accumulator.
Loop Terminator has Trigger and Break inputs and LoopComplete output to control and signal the end of the loop.
Accumulator adds an Input input and Result output, to allow for storing values on completed iterations and passing them out upon completion.
We, however also need to be able to pass values back into the next iteration of the loop.
For that, we need a Passing Accumulator module.
Here, we see the addition of a PassedLoopValues input (what will be passed back), as well as FinalLoopValues (what the next passing value would be when the loop terminated).
Let’s add a Passing Accumulator and some thoughtful wiring to tie this all together.
For any loop, we tie the iterator module’s LoopComplete output to the endpoint module’s Trigger input, so let’s start there.
The whole purpose of the Next Pair is to pass it back to the next iteration, so let’s connect that ArrayOutput output to the Passing Accumulator’s PassedLoopValues input.
Hmmm…what should our input be?
Well, as we loop, we will want to do the same operation each time, so we should add one value per iteration. I’m not in favor of seeding our otherwise initially-empty Result list, as it breaks the simplicity of the loop. We also don’t need to.
If we simply make Val1 our input, and pass [Val2, Val3] to the next iteration, we will end up with one value in our Result list for every iteration of the loop.
So, let’s do that. That gives us:
As a reminder, our goal stated at the outset was to be able to construct a Fibonacci series.
If we’ve done this all correctly, we’re done building. But any process needs testing, so we’ll do that next.
I always like to Save before running anything, so I’ll do that here.
I’m going to call my DataFlow “Fibonacci Loop” and add a Description. The easily memorable name will come in handy in a later blog post…
Next, I want to be able to step through the early stages of the loop to see what is happening, so I’ll switch from Run mode to Debug mode.
Now, when I press Debug, I get the stepping controls at the top of the canvas and the blue color is drained out of the outputs and connectors until those tasks have been activated and completed.
Press the play button seven times. That will allow each of our six modules to run once (the first click initiates the debug run and sets the first module to be ready to run, plus one click to run each module from that point forward), so that we can examine the first cycle of the loop to completion.
Now, let’s use View Results from the outputs shown.
DoWhile’s PassedOutputs, LoopComplete, and Current Iteration results show that the seed pair list ([0,1]) is being passed to Val1 and Val2, the Boolean false is being passed to the Passing Accumulator’s Trigger, and we are on CurrentIteration 1.
Val1, Val2, and Val3 are 0, 1, 1 as expected, and Next Pair’s ArrayOutput is set to [1,1].
For our Passing Accumulator, DoWhile’s LoopComplete false is passed into Trigger, Val1’s 0 is passed into Input to start our ResultList, and Next Pair’s [1,1] is passed into PassedLoopValues.
The Passing Accumulator’s Result is not yet available because the loop is not yet finished. This is a safety measure so that no results are passed out of the module until the finished results are ready to go.
All good so far.
But here’s where the rubber meets the road.
Pressing the debugger’s play button six more times has us cycle the six-module loop one more time.
We can see that this cycle’s starting pair is [1,1], successfully passed from last cycle’s Next Pair.
CurrentIteration 2 uses LoopComplete to tell the Trigger that we’re still not done, 1 + 1 = 2, and the Next Pair is [1,2]. Val1 adds 1 to our accumulating ResultList.
Six more clicks for the debugger and we complete the third cycle.
CurrentIteration 3 starts with [1,2], we’re still not done, 1 + 2 = 3, 1 gets added to the ResultList, and [2,3] is the Next Pair.
This could go on, literally, forever. How will it know when to stop? Well, remember that DoWhile’s MaxIterations is set to 6.
We could step through each iteration, but let’s jump to the end by hitting the debugger’s Continue button (third of the three).
Now we can see all of the outputs at their final stage.
We can see that our sixth and final iteration passed true to the Trigger, signalling that this is the last pass.
Our starting pair of [5,8] passed 5 in as the sixth and final term in our Result list. 5 + 8 = 13, and [8,13] is ready to go as our Next Pair.
Our Passing Accumulator now shows that the loop is complete (LoopComplete is true). With the task finished, we can now see both the Result list of six items, [0,1,1,2,3,5], made from the six iterations, and also what the next two terms would be, [8,13], as the FinalLoopValues to passed to the next cycle, if there were one.
One final test. Let’s set the MaxIterations to something larger, like… 12.
We don’t need to step through, as the first six steps will be exactly the same. But let’s check out where we end up. Switch back to Run mode and click Run.
We can see that the 12th cycle starts with [89,144], and 89 + 144 = 233. 89 is at the end of our 12-item list, [0,1,1,2,3,5,8,13,21,34,55,89], and [144,233] would be next up.
The key takeaway: we have shown that this list will run until a stopping condition is met and we currently have the option to control the loop’s termination with a simple parameter of how many times we want it to run.
We have built this DataFlow as a standalone, but to truly make use of the power of this functionality, we would want to be able to encapsulate this as a functional block in our library of modules, to be called upon whenever needed. We would also want to expose control of inputs and outputs to the external user, without them needing to see how the sausage is made inside our loop.
Our next Spotlight post on Nested DataFlows will add another loop termination control method (using the Break input of Passing Accumulator), discuss how to handle a potential off-by-one error in assigning F(n) (hint: Fibonacci numbers with [0,1] start at F(0), but iterations start at 1), and show how to customize inputs and outputs when authoring your very own module!
Later, you’ll see how to utilize both DoWhile and ForEach looping techniques (and Nested DataFlows) in an upcoming Project Lab in our NASDAQ API series. I will link here when that Lab is available.
Until next time…