Divide And Conquer
Now that we have the ability to perform recursive functions, we can define a division function.
The process of dividing
value2 is simply keeping track of how times
value2 can be subtracted from
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.
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
Then we need to modify the definition of
div to call the Y-Combinator using
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
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 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
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
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
For the time being though, we'll take the easy option and convert the result from
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:
- Replace the two parameters
val2with a single parameter called
val1parameter now becomes the first value in this pair, and the
val2parameter becomes the second value.
- All occurrences of
val1must now be replaced with
pair(TRUE), and all occurrences of
val2must be replaced with
- Since we have combined two parameters into one, when we now make the recursive call to
div_next, we must combine the
val2values into a single
- Also, we can no longer pass two individual quantity functions to our
DIVfunction. We need to combine these values into a
PAIRfunction at the time we call
- Use a
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
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
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
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
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
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
RANGE on the list.
All source code from the Mindshift blog series can be found on GitHub