Borrowing From Math Class

special thanks to @bencallahan for the shot!

A review of code samples and ideas from my talk ‘Borrowing from Math Class’ given at Front End Design Conference, in St. Petersburg, FL, April 2017.

The purpose of the code exercises below are to illustrate how we move from discrete solutions that rely on the combination of code and data, and move towards a more generic solution that relies on higher level functions to remove the code/data coupling.

In order to provide context, the code exercise I propose is to implement multiplication using only addition. That is to say that you have a calculator with only an add button and you want to implement a multiplication button.

A discrete solution

If we think about the operation of multiplication, it is simply the additive combination of groups of the same number. So for example `3 x 3 = 9` because we are adding three sets of three (represented here 3 sets of 3).

||| + ||| + |||

The first step is to see if we can write a function that can take a number and repeatedly add itself. We could define a triple function like so.

triple = (x) => x + x + x;
triple(3) // 9

Parts of a function

This is a side note to the content I provided in the talk but I realize in retrospect it might be nice to define the taxonomy of a function. For the function triple above we have several parts:

  • The ‘variable’ triple that will for the life of the program be available to use. In some languages this would also be called a reference, or a symbol. It is a reference that is bound to the code on the right side of the equals sign.
  • The equals sign = is the assignment operation in JavaScript.
  • The argument signature (in this case (x)) describes the argument list that the function depends on to work. It is often described as the parameters of the function.
  • The function body x + x + x is the unit of work that will use the function parameters to return a new value from the result of the operations in the unit body.
  • The semicolon, in this case, represents the end of the statement.

Type signatures

In many functional languages we would also include a type signature to describe the types of data that can be used by the function. In this case we intend to supply an integer x to the function, but it also can work for floats, and even strings, since the `+` function can be applied to string types in javascript.

“e” + “d” + “f” // ‘edf’

So while the use case we have for triple should be defined as

triple :: Number -> Number

A function takes a number and returns a number, it should be more generically described like:

// triple :: a -> a
triple = (x)=> x + x + x;

Which can be thought of as a function that takes any generic type `a` and returns a new `a` of the same type.

We now have a solution. However, if we want to produce a function to quadruple a value then we must create a new ‘unique function’; but one that borrows most of its code from the triple function.

// quadruple :: a -> a
quadruple = (x) => x + x + x + x;

extra credit, we could define the function like this as well:

quadruple = (x) => x + triple(x);

Towards a more generic solution

Going back to the first solution, what we realize, is that the implementation of quadruple and triple are nearly identical, it is only the number of `x`s in the function body that differ. The applied function (addition) does not change. When we see that pattern emerge, it should inform us that what we have is ‘data’ encoded in our program. So we can look at the above function and realize it contains three pieces of information, the input (`x`), the function (+), and the number of iterations we apply the function to `x`. So it would be nice if we could have an API for our new function that would allow us to abstract the process of the triple function to something like:

// addMultiple : Number -> Number -> Number
/* addMultiple intentionally not defined here */
// triple :: Number -> Number
triple = addMultiple(3)
// and the use it like
triple(3) // 9

The type signature

Number -> Number -> Number

explains that we want to provide a Number (representing the number of times we are going to recursively add), and then another number to be recursively added, and finally return a number that is the result of the function execution. `triple` is the concrete solution of how we might use our abstract function to define a use case.

More Math

We can also leverage known theorems in mathematics to help in our quest. The Fundamental theorem of arithmetic explains that:

every positive integer has a single unique prime factorization.

In practice what this means is that we can take any positive divisible integer and describe it in terms of its set of unique non-divisible (prime) numbers. For example, if we want to describe the process of multiplying the number 3 by 40, eg `3 x 40`. We could define 40 in terms of its unique set of primes:

40 = 20 * 2

2 is a prime number, so we can add it to the list of primes, and then move to recursively identify the prime factors of 20.

[2] // list of primes
20 = 10 * 2
[2,2] // add 2 to the list of primes
10 = 5 * 2
[2,2,2,5] // the complete list of primes that describes 40
2 * 2 * 2 * 5 // 40 (try it out if you don’t believe me)

We can then apply the multiplicative factor of 3 to that number set to arrive at the product of `3 x 40` which is 120.

3 * 5 * 2 * 2 * 2 = 120

Another way to describe this is to say that we can take the input from one piece of the product and use it to feed into the next product, feeding the result of one evaluation to the next prime factor, for example:

5 * 3 = 15
2 * 15 = 30
2 * 30 = 60
2 * 60 = 120

Now we can see that if we had just two functions, a doubling function `d`, and a quintuple function `q`, we could solve the ‘times 40` problem.

// d :: a -> a
d = (a) => a + a ;
// q :: a -> a
q = (x) => x + x + x + x + x;

and then we can describe `times40` as:

// times40 :: a -> a
times40 = (x) => d(d(d(q(x))));

Now we are relying on the composition of functions that are based on the prime factors of the desired number. We still have a code/data coupling problem. This function body `d(d(d(q(x))))` must exist. We have no way to ‘get rid’ of that code yet and so this function is only valid for the specific use case of multiplying by 40. But again we see there is a pattern of execution there that seems like we could have some abstraction for that would work for more than one specific solution.

Function composition

It turns out, that there is an abstraction that is readily available in functional programming to help us in this goal. You might recall from high school algebra the idea of function composition. you might have seen it in the style of:

f(x) = 2 * x
g(x) = 5 * x
Question: 
x’ = f(g(x))
What is the value of x’ when x is 3.
Solution:
g(3) = 15
f(15) = 30
 x’ = 30

In math we would describe this as functional composition and the shorthand notation for the above would be to say that

x’ = f • g

and would be read “x prime is equal to f of g”. Our function to multiply by 40 can be redefined in terms of composition of the ‘d’ and ‘q’ methods above

d • d • d • q

Read “d of d of d of q”.

In most functional languages, compose is a core concept, and most languages will have some notion of compose as a core function available. For the purposes of this article, I am relying on a functional utility library that provides some of these concepts directly for the JavaScript language. We could redefine our times40 method in terms of R.compose.

R = require(‘ramda’);
// times40 :: a -> a
times40 = R.compose(d, d, d, q);

It should be no surprise that compose in functional programming land ‘borrows’ directly from the mathematical definition. That is to say that the arguments to the compose function adhere to the same positional ordinance as the mathematical definition. The function `q` is the right most argument and is the first applied, rather than how we might anticipate based on other positional arrangements we are used to dealing with in other parts of computing. Eg, with arrays, the first position is the left most value. Operations like ‘pipe’, or ‘chain’ are usually applied left to right, and since many people are exposed first functional programming though data structure manipulation, the notion of chaining is also done left to right:

[1,2,3].map(x => x + 1).reduce((acc, i) => acc + i, 0) // 9

Add Multiple

Returning to our idea of addMultiple, we can use another type of functional composition. Let us review what we’d want our final API to look like:

// triple :: Number -> Number
triple = addMultiple(3);
// and the use it like
triple(3) // 9

And to review the type signature.

addMultiple :: Number -> Number -> Number

Given our desired API, what returns from addMultiple is a function, so, lets start by doing that.

addMultiple = (a)=> (b)=> 9;

This would now work for `triple` because I’m hard coding 9 as a result, but the pattern now fits the use case. I am returning a function that will accept one more argument `b`, and then return the result. In order to make the internal method a little nicer I am going to write a method up front that I can use as a helper:

add = (a,b)=> a + b;

The function composition I am going to use in this case builds on what we learned with composition above, but we will do it in a more subtle way using recursion. Recession relies on two or more primary cases. They are often referred to as boundary conditions. The boundary conditions typically determine when to recur, and when to stop and return a value. In the domain of addMultiple what might make sense is to ‘count down’ the number of times we’ve added multiple and end when we are at zero. For instance:

addMultiple(3, 3)
addMultiple(2, 3)
addMultiple(1, 3)
addMultiple(0, 3) // return 9

The other typical strategy in recursion is to pass the value you are building along with the signature. A possible function might look like this then:

// _addMultiple (Number -> Number -> Number -> Number
_addMultiple = (a,b,res=0)=> 9

By default the result value starts as 0, but we can supply that value in our recursive calls as necessary to a pass a value along. The next step is to define the edge conditions that will stop the recursive call, in this case, it is when `a` is 0.

// _addMultiple (Number -> Number -> Number -> Number
_addMultiple = (a,b,res=0)=> if (a === 0) { return res } ;

And then we can safely add the recursion.

_addMultiple = (a,b,res=0)=> {
if( a === 0 ) {
return res;
} else {
return _addMultiple( — a, b, b + res );
}
};

We are sorta cheating here by using subtraction to decrement, so lets redefine the recursive call using our `add` helper function.

_addMultiple = (a,b,res=0)=> {
if(a === 0 ) {
return res;
} else {
return _addMultiple( add(-1, a), b, add(b, res) );
}
};

finally we can wrap this up in another function such that the internals of our function are closed over:

// addMultiple :: Number -> Number -> Number
addMultiple = function(a) {
var _addMultiple = (a,b,res=0)=> {
if( a === 0 ) {
return res;
} else {
return _addMultiple( add(-1, a), b, add(b , res) );
}
};
  // return a function waiting to apply b
return (b)=> _addMultiple( a, b );
};

And now we have an implementation of our addMultiple function that could be used to implement triple. The astute reader will realize this is not a complete arithmetic solution. The astute comp. sci. major will also notify me that this could blow the stack since javascript does not support TCO yet. You may also realize at this point that you could actually rename addMultiple to multiply and in fact, the ramda library I introduced earlier has an API compliant multiply function.

R = require(ramda);
triple = R.multiply(3);
triple(3) // 9
R.multiply(3,3) // 9

Concluding remarks

Given that Ramda provides us a multiply function with the desired API I describe is no coincidence. That library provides us the functions we want without the hard coded function bodies; and now we can define our time40 function like so.

times40 = R.multiply(40);

or to follow up on other ideas:

d = R.multiply(2);
q = R.multiply(5);
times40 = R.compose(d, d, d, q);

What I hope you walk away with is a deeper understanding of why we desire to remove the code/data coupling. This coupling binds our use case in the realm of discrete solutions. By understanding the underlying patterns in our code, and then abstracting these to data provided to the function, we start to move towards more unifying solutions. This is just one important idea exposed by ‘thinking functionally’ but I hope it has been useful.

I’d like to extend a special thanks to Fuelixir and access.mobile. Two organizations that make it possible to think about the things I like to think about. And also Front End Design Conference, for the opportunity to speak!

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.