Building Math from the Ground Up

arithmetic-from-scratch.js

// A bit of intellectual masturbation inspired by
// https://www.scottaaronson.com/writings/bignumbers.html
// https://en.wikipedia.org/wiki/Graham%27s_number
// https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation
// and
// currying (https://en.wikipedia.org/wiki/Currying)

// A little cheat to move to right on the integer line
const increment = i => ++i

// A little cheat to move to the left on the integer line
const decrement = i => --i

// A somewhat narrow definition of 'iteration'
//
// Arguments:
//   - func: a single argument function whose result can be used as its argument
//   - arg: value that will be used as the initial argument
//   - executionCount: number of times to execute the function
//
// Each time the function is executed, its result is captured and fed into the
// function as its argument on the next execution. Result of the final execution
// is returned as the final result
const iterate = (func, arg, executionCount) => {
    if(executionCount === 0) {
        return arg
    }
    return iterate(func, func(arg), decrement(executionCount) )
}

// The 'iterate' above uses recursion. JS engines that don't do tail call
// optimization (which is pretty much all of them) will run into stack overflow
// errors. Following implementation side steps this by using iteration to
// implement 'iterate' (there are reasons I put the 'intellectual masturbation'
// disclaimer above).
// const iterate = (func, arg, executionCount) => { 
//    let result = arg;
//    for (let i = 0; i < executionCount; i = increment(i)) {
//        result = func(result);
//    }
//    return result;
// }

// Curried declaration of addition of natural numbers implemented as an iteration
// of increment
const add = a => b => iterate (increment, a, b)

// Curried declaration of multiplication of natural numbers implemented as an
// iteration of add
const multiply = a => b => iterate ( add(a), a, decrement(b) )

// Curried definition of power operation using natural numbers implemented as an
// iteration of multiply
const power = a => b => iterate (multiply(a), a, decrement(b) )

// Curried definition of Knuth's up-arrow notation
// See https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation
const arrow = a => arrowNum => b => {

    // base case is just the power operation
    if (arrowNum === 1) {
        return power(a)(b);
    }

    // general case is a recursive operation
    const arrowMinusOne = decrement(arrowNum)
    const bMinusOne = decrement(b)
    return iterate ( arrow (a) (arrowMinusOne), a, bMinusOne );
}