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 `incr`ement 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