Mindshift: Part 12

Divide And Conquer

Now that we have the ability to perform recursive functions, we can define a division function.

The process of dividing value1 by value2 is simply keeping track of how times value2 can be subtracted from value1 until value2 becomes larger than the remainder. The answer is then two values: the count of how many times we performed the subtraction, and whatever number is over left.

To keep things simple, we will just return an integer remainder rather than a decimal fraction.

So let's write out the division operation as a regular JavaScript arrow function that uses recursion. Then we will convert it to use the Y-Combinator and abstract quantity functions.

Ok, that works; but the API to the div function is not exactly intuitive. We want to divide one number by another, yet this function requires three parameters instead of the expected two. It's a pretty poor API design to expect the user to know they should also supply some internal implementation value such as the initial value of the quotient counter.

That's exactly not how people expect a division function to work - so we'll have to fix that.

All we need to do is to treat the existing div function as an inner function (let's rename it do_div), and then create a new div function that acts as the public API to do_div and passes in the initial value of the quotient counter.

Ok, that's a lot more user friendly.

Now Use The Y-Combinator For Recursion

Next, we can remove do_div's self-reference by using the Y-Combinator. However, as we've seen before, the Y-Combinator requires that the function being called recursively has as its first parameter, the function to be called next. So we'll give do_div a new first parameter called div_next and where we used to call do_div using its external name, we will replace this with a call to the function received in parameter div_next.

Then we need to modify the definition of div to call the Y-Combinator using do_div.

Ok, that was easy enough.

Replace The Integer Values With Abstract Quantity Functions

Now we need to adapt the do_div function so that instead of working with integers, it works with abstract quantity functions. To start with, the easiest value to change is the quotient counter called count.

If you look at the code, we don't actually do much with the count parameter other than add one to it. So this is easy enough to adapt. However, if we are now treating parameter count as a quantity function, we can't simply perform the arithmetic operation + 1 on it anymore. But, we do have a function that can work out the successor of any quantity function - and this is the same as adding one.

However, we need to be careful. Since count is now an abstract quantity function and not an integer, it wouldn't be very user friendly if we a returned an object in which one property is an abstract quantity function, and the other is an integer. Therefore, we will convert the count parameter back to an integer before returning its value. (Remember that in order to do this conversion, we will need both a to_integer function and an increment function. See the Mindshift: Part 5 blog for details of their definition.)

Also, to keep our naming convention consistent, we should rename div to DIV to indicate that it now works with quantity functions rather than integers.

So our code is adapted as follows:

Good. So far we haven't broken anything.

So, how about changing val1 and val2 from integers to quantity functions?

So to do this, we must look at what operations are we performing on these two parameters. First we're comparing them using the "less than or equal" operator, then we're subtracting val2 from val1.

Fortunately for us, we already know how to perform these operations on abstract quantity functions. We already have an IS_LTE function and a SUBTRACT function (see Mindshift: Part 7 and Mindshift: Part 8 for the definitions of these functions)

Oh, hang on a minute - that's not going to work is it?

The problem here is that the IS_LTE function is not a JavaScript predicate function. That is, it returns one of the abstract Boolean functions TRUE or FALSE rather than a JavaScript Boolean value; therefore, it will not work correctly with the JavaScript ternary operator.

For the time being though, we'll take the easy option and convert the result from IS_LTE into a JavaScript Boolean value: that way, we're not changing too much coding all at once.

OK, that works...

Combine The Two Parameters Into An Abstract PAIR Function

Since we are treating the dividend and the divisor parameters as a pair, and also returning the quotient and remainder values as a pair, it makes sense to represent these values using abstract PAIR functions. So we need to make the following changes:

  1. Replace the two parameters val1 and val2 with a single parameter called pair. The val1 parameter now becomes the first value in this pair, and the val2 parameter becomes the second value.
  2. All occurrences of val1 must now be replaced with pair(TRUE), and all occurrences of val2 must be replaced with pair(FALSE).
  3. Since we have combined two parameters into one, when we now make the recursive call to div_next, we must combine the val1 and val2 values into a single PAIR function.
  4. Also, we can no longer pass two individual quantity functions to our DIV function. We need to combine these values into a PAIR function at the time we call DIV.
  5. Use a PAIR function as the return value instead of a JavaScript object.

Well, OK that works. But again, we've messed up the API to our DIV function. That fact that the internal implementation of do_div uses a PAIR function is really of no concern to the developer using DIV; so let's modify the definition of DIV to create the PAIR function for us.

Now, use a PAIR function as the return value instead of a JavaScript object.

Great, so we now have a function that can divide one quantity function by another and give back a PAIR function as the answer. We know this PAIR function contains two quantity functions - the first representing the quotient and the second the remainder - so we can extract them (using TRUE and FALSE) and then reify them to give actual integers.

Should We Stop Here Or Carry On?

Well, the point we've now reached is a good place to stop if you want. Inside function do_div, the only JavaScript operator still in use is the ternary operator, and this performs a very useful service - not only because it acts as a compact way to represent an If/Then/Else construct, but more importantly, because JavaScript is smart enough to test the condition first, and only then processes the branch that corresponds to the success or failure of the condition.

If we want to take the next step and eliminate the use of the ternary operator, then we need to be careful. As soon as we remove the use of this operator, JavaScript will look at the IS_LTE function as exactly that - just a function and not a condition operator. Therefore, JavaScript will automatically attempt to evaluate both the true and false branches of the condition. Apart from this being a nonsensical thing to do (since a condition cannot be both true and false simultaneously), it will also lead to run-away recursion.

Remove The Use Of The JavaScript Ternary Operator

Ok, so lets take the plunge and remove the use of the JavaScript ternary operator. This means that the call to div_next must go in parentheses to delimit it as the condition's "true" branch, and similarly the call to PAIR must also go in parentheses since that is the condition's "false" branch.

Uncaught RangeError: Maximum call stack size exceeded(…)

Well, we were expecting that to happen...

To avoid runaway recursion, we need to refactor the call to div_next by wrapping it in another function.

How many parameters should this wrapper function take? Well, that depends on how many parameters the function being wrapped takes.

Generally speaking, the job of the <some_name>_next function (div_next in our case) is to perform the next step of the recursive calculation, and this will take whatever value is first passed to the Y-Combinator. In our case, this is a single PAIR function; therefore, this wrapper function needs to take one parameter.

So there you have it. A function that implements the division operator by means of the Y-Combinator recursively calling a function that uses repeated subtraction and returns a quotient and a remainder as a PAIR function.

Now, It's But A Small Step To Create A Modulus Function

If we want to create a MOD function, then we've actually done all the leg work already. Since the modulus function is a division operation that ignores the quotient and returns the remainder, we can define the MOD function to be simply the second value in the PAIR function returned from DIV.

So we have now expanded our set of arithmetic tools to include division and modulus.

In the next blog, we'll take a look at how lists can be implemented. Then once we have a list, we can implement the functions MAP, REDUCE and RANGE on the list.

Chris W


All source code from the Mindshift blog series can be found on GitHub