44:["$","title",null,{"children":"Mindshift: Part 19 | Chris Whealy | Observable"}] 4c:T7a1,md`# Mindshift: Part 19 Republished on Dec 17th, 2018 ## Multiplication & Division Having introduced the use of a NUMBER function to represent a signed integer, we've seen how to add and subtract these functions. Now we can look at how to multiply and divide them. ## Multiplication As we saw towards the end of part 5 of this blog series, multiplication is implemented as repeated addition. So using only "naked" quantity functions, we performed the multiplication 8 * 5 as follows: * Start with the quantity function EIGHT, and pass it * Function ADD as the transformation function, and the * Quantity function FIVE as the starting value In other words, we performed multiplication by constructing an abstract quantity function that applies function ADD a total of EIGHT times to a starting value of FIVE. (Since multiplication is commutative, we could just have easily applied function ADD FIVE times to a starting value of EIGHT). Now that we are working with NUMBER functions, we still need to perform the computation shown above, but first, we must examine the sign part of the NUMBER. Since a NUMBER is a PAIR formed from a SIGN and a quantity function, our existing MULTIPLY function will still work perfectly well, as long as we remember that it operates only on quantity functions, not these more exotic NUMBER pairs. Therefore, to record this difference, we should rename the MULTIPLY function to be MULTIPLY_MAGNITUDES. Notice that we must also rename the internal references to ADD and ZERO to refer to ADD_MAGNITUDES and ZERO_MAGNITUDE.`4d:T5cc,md`See part 17 and part 18 of this blog series for definitions of functions ADD_MAGNITUDES and ZERO_MAGNITUDE. Now we need to take care of the signs of each operand. As before, writing out a table of sign permutations will help us see the desired result. | Operands | Resulting Sign |:-:|:-:| | +n1 * +n2 | +(n1 * n2) | +n1 * -n2 | -(n1 * n2) | -n1 * +n2 | -(n1 * n2) | -n1 * -n2 | +(n1 * n2) First, we can see that no matter what the signs are, we will simply multiply the absolute values of the operands. Second, if the signs of both operands are the same, the result is positive and if they're different, then the result is negative. Looking at the "Resulting Sign" column, we can see whether the resulting sign "is negative" by XORing the signs of the two operands. However, we want to know whether the sign "is positive", so we NOT the result of XORing the signs together. Therefore, to multiply two NUMBERs all we need to do is construct a new NUMBER in which the resulting sign is the NOT(XOR) of the two operands' signs, and the magnitude is the absolute values of the two operands multiplied as before, giving:`4e:Td06,md`Well that was pretty straight-forward, so now let's look at division. ## Division Just as we did with multiplication, the division of two NUMBERs will use the same functionality as the division of two abstract quantity functions, and the resulting sign will be calculated just as we did above. However, there is one very important difference, the result of the DIVISION operation is not necessarily going to be an integer - we must now account for a two-part answer, the quotient and the remainder. Since we're doing integer division (and to keep things simple), we will represent the remainder as another integer rather than a decimal fraction. Let's have a quick recap on how the existing DIVision operator works using "naked" quantity functions. ## Recap Of How Division Works In any integer division operation such as a / b = c rem d, each term has a name. * a is known as the *dividend* * b is known as the *divisor* * c is known as the *quotient* * d is known as the *remainder* The division computation works by counting how many times the divisor can be subtracted from the dividend until such time as the remainder becomes less than the divisor. For example, the division 13 ÷ 5 written out in pseudocode would be:

dividend  = 13
divisor   = 5
counter   = 0
remainder = dividend

Is remainder(13) < divisor(5)?

No -> decrement remainder by the divisor (remainder = 8)
      Increment the counter (counter = 1)

Is remainder(8) < divisor(5)?

No -> decrement remainder by the divisor (remainder = 3)
      Increment the counter (counter = 2)

Is remainder(3) < divisor(5)?

Yes -> return the PAIR formed by the counter(2) and remainder(3)
       PAIR(2)(3)

Since we have to perform an unknown number of subtraction operations, we need to use recursion. As you may recall from part 12 of this blog series, recursion in Lambda Calculus is performed by passing the Y-Combinator a function that has been specially constructed to receive as its first parameter, a copy of itself, and as its second and subsequent parameters, any further parameters needed for the calculation being performed. So in the original version of the DIV function, we created a function called do_div that takes four parameters: | Argument | Description |---|---| | div_next | A copy of function do_div itself. This is supplied by the Y-Combinator and allows the function to identify itself without the need for any external or global name. | count | Starts at zero and counts the number of recursive calls needed to complete the division operation. | remainder | At the start of recursion, this parameter holds the dividend, I.E. the number that is being divided by the divisor. Each time we take another recursice step, this parameter has the divisor subtracted from it until its value becomes less than the divisor. At this point, recursion stops and whatever value is left in this parameter is the actual remainder. | divisor | The value being divided into the dividend.`4f:T48a,md`So now that function do_div_magnitudes works only with abstract quantity functions rather than NUMBERs, we can look at adjusting the definition of function DIV itself. Here we need to do several things listed here in the order of the coding shown below: 1. Whatever result comes back from the Y-Combinator will now be a PAIR formed from the *quotient* and the *remainder*; therefore, we must package this result inside a new NUMBER with the correct sign The calculation of the sign is exactly the same as for the MULTIPLY operator; that is, we NOT(XOR) the operands' sign values together. 1. We must pass the function do_div_magnitudes to the Y-Combinator instead of do_div 1. Since the do_div_magnitudes function works only with abstract quantity functions, we must be careful not pass it any NUMBERs. This has two consequences: 1. We must supply a counter start value of ZERO_MAGNITUDE not ZERO 1. We must supply the absolute values of the NUMBER operands `50:T507c,lib = { // ******************************************************************** // Naming Conventions // // Functions with all uppercase names return abstract functions // // Functions with all lowercase names return native JavaScript data // types // ******************************************************************** // ******************************************************************** // Generic operations // ******************************************************************** var adder = val1 => val2 => val1 + val2 var multiplier = p => q => q*p var str_concatenate = char => acc => acc.concat(char) var asPlusChar = str_concatenate('+') // The increment and decrement functions can now be created var incr = adder(1) var decr = adder(-1) // Use the multiplier function to create partial functions that // double, triple and quadruple their subsequent operand var double = multiplier(2) // -> double = q => q*p (p = 2) var triple = multiplier(3) // -> triple = q => q*p (p = 3) var quadruple = multiplier(4) // -> quadruple = q => q*p (p = 4) var add5 = adder(5) // -> add5 = q => q+5 // ******************************************************************** // Function Composition // ******************************************************************** var compose = fn1 => fn2 => val => fn2(fn1(val)) // Now we can "compose" double and add5 into a single function var doubleAndAdd5 = compose(double)(add5) // ******************************************************************** // Reification functions // ******************************************************************** var to_string = qtyFn => qtyFn(asPlusChar)('') var to_boolean = fn => fn(true)(false) var magnitude = qtyFn => qtyFn(incr)(0) // ******************************************************************** // Functions that operate on pairs and return abstract functions // ******************************************************************** var TRUE = true_part => false_part => true_part var FALSE = true_part => false_part => false_part // HEAD and TAIL are synonyms for TRUE and FALSE var HEAD = pair => pair(TRUE) var TAIL = pair => pair(FALSE) var PAIR = val1 => val2 => fn => fn(val1)(val2) var EMPTY_LIST = PAIR(null)(null) var IS_EMPTY = pair => (HEAD(pair) === null && TAIL(pair) === null) ? TRUE : FALSE var IS_LAST = pair => IS_EMPTY(TAIL(pair)) // ******************************************************************** // Functions that operate on pairs and return JavaScript data types // ******************************************************************** var is_empty = pair => (HEAD(pair) === null) && (TAIL(pair) === null) var is_last = pair => is_empty(TAIL(pair)) var is_pos = number => to_boolean(IS_POS(number)) // ******************************************************************** // Boolean Operators // ******************************************************************** var NOT = bool => bool(FALSE)(TRUE) var AND = bool1 => bool2 => bool1(bool2)(FALSE) var OR = bool1 => bool2 => bool1(TRUE)(bool2) var XOR = bool1 => bool2 => bool1(NOT(bool2))(bool2) // ******************************************************************** // Define an abstract quantity function for unsigned ZERO and ONE // ******************************************************************** var ZERO_MAGNITUDE = transform => start_value => start_value var UNIT_MAGNITUDE = transform => start_value => transform(start_value) // ******************************************************************** // Signed integer functions // ******************************************************************** var NUMBER = isPositive => qtyFn => PAIR(isPositive)(qtyFn) var ABS = number => TAIL(number) var SIGN = number => HEAD(number) var ZERO = NUMBER(TRUE)(ZERO_MAGNITUDE) // ******************************************************************** // Predicate functions // ******************************************************************** var IS_POS = SIGN var IS_NEG = test_for_negative => NOT(IS_POS(test_for_negative)) var IS_ZERO = number => ABS(number)(dont_care => FALSE)(TRUE) var HAS_ZERO_MAGNITUDE = qtyFn => qtyFn(dont_care => FALSE)(TRUE) var HAS_UNIT_MAGNITUDE = qtyFn => magnitude(qtyFn) === 1 ? TRUE : FALSE var IS_MINUS_ONE = number => AND(IS_NEG(number)) (HAS_UNIT_MAGNITUDE(ABS(number))) var sign = number => to_boolean(SIGN(number)) // ******************************************************************** // Reify signed integers // ******************************************************************** var to_integer = number => magnitude(ABS(number)) * IS_POS(number)(1)(-1) // ******************************************************************** // Successor and predecessor functions // ******************************************************************** var SUCC_MAGNITUDE = qtyFn => transform => start_value => transform(qtyFn(transform)(start_value)) var SUCC_MAGNITUDE_PAIR = pair => PAIR(pair(FALSE))(SUCC_MAGNITUDE(pair(FALSE))) var PRED_MAGNITUDE = qtyFn => qtyFn(SUCC_MAGNITUDE_PAIR) (PAIR(ZERO_MAGNITUDE) (ZERO_MAGNITUDE)) (TRUE) var ADD_MAGNITUDES = qtyFn1 => qtyFn2 => qtyFn1(SUCC_MAGNITUDE)(qtyFn2) var SUBTRACT_MAGNITUDES = qtyFn1 => qtyFn2 => qtyFn2(PRED_MAGNITUDE)(qtyFn1) var IS_LTE = num1 => num2 => to_integer(num1) <= to_integer(num2) ? TRUE : FALSE var IS_LT = num1 => num2 => NOT(IS_LTE(num2)(num1)); var SUCC = number => // Is the number positive? IS_POS(number) // Yup, so it must be >= 0, therefore return the positive // number created by calling SUCC_MAGNITUDE on the number's // absolute value (NUMBER(TRUE)(SUCC_MAGNITUDE(ABS(number)))) // Nope, so check for the special case of minus one (IS_MINUS_ONE(number) // Yup, so return value of ZERO (ZERO) // Nope, so the number must be <= -2 // Therefore, return the negative number // created by calling PRED_MAGNITUDE on the // number's absolute value (NUMBER(FALSE)(PRED_MAGNITUDE(ABS(number))))) var PRED = number => // Check for the special case of zero (IS_ZERO(number) // Yup, so return MINUS_ONE (NUMBER(FALSE)(UNIT_MAGNITUDE)) // Is the number positive? (IS_POS(number) // Yup, so the number must be >= 1 // Return the positive number created by calling // PRED_MAGNITUDE on the number's absolute value (NUMBER(TRUE)(PRED_MAGNITUDE(ABS(number)))) // Nope, so the number must be <= -1 // Therefore, return the negative number // created by calling SUCC_MAGNITUDE on the // number's absolute value (NUMBER(FALSE)(SUCC_MAGNITUDE(ABS(number)))))) // ******************************************************************** // Signed integers // ******************************************************************** var PLUS_ONE = SUCC(ZERO) var PLUS_TWO = SUCC(PLUS_ONE) var PLUS_THREE = SUCC(PLUS_TWO) var PLUS_FOUR = SUCC(PLUS_THREE) var PLUS_FIVE = SUCC(PLUS_FOUR) var PLUS_SIX = SUCC(PLUS_FIVE) var PLUS_SEVEN = SUCC(PLUS_SIX) var PLUS_EIGHT = SUCC(PLUS_SEVEN) var PLUS_NINE = SUCC(PLUS_EIGHT) var PLUS_TEN = SUCC(PLUS_NINE) var MINUS_ONE = PRED(ZERO) var MINUS_TWO = PRED(MINUS_ONE) var MINUS_THREE = PRED(MINUS_TWO) var MINUS_FOUR = PRED(MINUS_THREE) var MINUS_FIVE = PRED(MINUS_FOUR) var MINUS_SIX = PRED(MINUS_FIVE) var MINUS_SEVEN = PRED(MINUS_SIX) var MINUS_EIGHT = PRED(MINUS_SEVEN) var MINUS_NINE = PRED(MINUS_EIGHT) var MINUS_TEN = PRED(MINUS_NINE) // ******************************************************************** // Arithmetic operations based on abstract quantity functions // ******************************************************************** var ADD = num1 => num2 => // Inner function (qtyFn1 => qtyFn2 => // Is the 1st number +ve? IS_POS(num1) // Yup, what's the sign of the 2nd number? (IS_POS(num2) // Both numbers are +ve // Return sum of magnitudes and +ve sign (NUMBER(TRUE)(ADD_MAGNITUDES(qtyFn1)(qtyFn2))) // 2nd number is -ve // Which number is bigger? (IS_LTE(num1)(num2) // 1st number is bigger // Subtract 2nd number from 1st and return with +ve sign (NUMBER(TRUE)(SUBTRACT_MAGNITUDES(qtyFn1)(qtyFn2))) // 2nd number is bigger // Subtract 1st number from 2nd and return with -ve sign (NUMBER(FALSE)(SUBTRACT_MAGNITUDES(qtyFn2)(qtyFn1))))) // Nope, so is the 2nd number +ve? (IS_POS(num2) // 2nd number is +ve // Which number is bigger? (IS_LTE(num1)(num2) // 2nd number is bigger // Subtract 1st number from 2nd and return with +ve sign (NUMBER(TRUE)(SUBTRACT_MAGNITUDES(qtyFn2)(qtyFn1))) // 1st number is bigger // Subtract 2nd number from 1st and return with -ve sign (NUMBER(FALSE)(SUBTRACT_MAGNITUDES(qtyFn1)(qtyFn2)))) // Both numbers are -ve // Return sum of magnitudes with -ve sign (NUMBER(FALSE)(ADD_MAGNITUDES(qtyFn1)(qtyFn2)))) ) // Extract the numbers' absolute values and pass them to the above inner function (ABS(num1)) (ABS(num2)) var MULTIPLY = qtyFn1 => qtyFn2 => qtyFn1(ADD(qtyFn2))(ZERO_MAGNITUDE) var POWER = qtyFn1 => qtyFn2 => qtyFn2(MULTIPLY(qtyFn1))(UNIT_MAGNITUDE) var SUBTRACT = num1 => num2 => ADD(num1) (NUMBER(NOT(SIGN(num2)))(ABS(num2))) // ******************************************************************** // Combinators // ******************************************************************** var U = fn => fn(fn) var Y = (rec_fn => (gen_rec => U(gen_rec)) (gen_rec => rec_fn((n,a,b) => U(gen_rec)(n,a,b))) ) // ******************************************************************** // Create our own push function that returns the new array rather than // the index of the newly inserted item // ******************************************************************** var push = arr => val => (idx => arr)(arr.push(val)) // ******************************************************************** // Convert a character string to a list whilst preserving the // character order // ******************************************************************** var make_str2list = fn_next=> list => str => (str.length > 0) ? fn_next(PAIR(str.substr(-1))(list))(str.slice(0,-1)) : list var str2list = str => Y(make_str2list)(EMPTY_LIST)(str) // ******************************************************************** // Convert a list back into a character string // ******************************************************************** var make_list2str = fn_next=> str => list => is_last(list) ? str.concat(HEAD(list)) : fn_next(str.concat(HEAD(list)))(TAIL(list)) var list2str = list => Y(make_list2str)("")(list) // ******************************************************************** // Convert a JavaScript array into a list // ******************************************************************** var make_array2list = fn_next=> list => array => (array.length === 0) ? list : fn_next(PAIR(array[array.length-1])(list)) (array.slice(0,-1)) var array2list = Y(make_array2list)(EMPTY_LIST) // ******************************************************************** // Convert a list to a JavaScript array // ******************************************************************** var make_list2array = fn_next=> arr => list => is_last(list) ? push(arr)(HEAD(list)) : fn_next(push(arr)(HEAD(list)))(TAIL(list)) var list2array = list => Y(make_list2array)([])(list) // ******************************************************************** // Reverse a list // ******************************************************************** var do_reverse = next_rev => new_list => old_list => IS_LAST(old_list) (PAIR(HEAD(old_list))(new_list)) (f => (next_rev(PAIR(HEAD(old_list))(new_list)) (TAIL(old_list))) (f)) var REVERSE = Y(do_reverse)(EMPTY_LIST) // ******************************************************************** // Generic MAP function // ******************************************************************** var make_map = next_map => new_list => fn => list => (list_acc => // Have we reached the end of the list? IS_LAST(list) // Yup, so reverse the items in the list and // we're done (f => REVERSE(list_acc)(f)) // Nope, so recursively call ourselves passing // in the list accumulator, the function being // applied and whatever is left in the current // list (f => (next_map(list_acc) (fn) (TAIL(list))) (f)) ) // Apply the mapping function to the first list item and // append the result to the start of the new list. This // value is then received as argument list_acc in the // function above (PAIR(fn(HEAD(list)))(new_list)) var MAP = Y(make_map)(EMPTY_LIST) // ******************************************************************** // Generic REDUCE function // ******************************************************************** var make_reduc = next_reduc => list => fn => acc => (new_acc => // Have we reached the end of the list? IS_LAST(list) // Yup, so simply return the accumulator (f => (new_acc)(f)) // Nope, so recursively call ourselves passing the // remainder of the list, the reduction function and the // new accumulator value (f => (next_reduc(TAIL(list)) (fn) (new_acc)) (f) ) ) // Calculate the new accumulator value. This value // appears as parameter new_acc in the above function (fn(HEAD(list))(acc)) // Create the REDUCE function using the Y-Combinator var REDUCE = Y(make_reduc) // Define a function to count the number of items in a list var COUNT = list => REDUCE(list) // The list being reduced (dont_care => acc => SUCC(acc)) // The reduction function (ZERO_MAGNITUDE) // The accumulator start value // ******************************************************************** // Convert a positive integer to its Church encoding // Null must be explicitly tested for to avoid disappearing down the // rabbit hole of infinite recursion. This is because JavaScript will // coerce null to be zero; therefore, the "(n-1)" part of the // expression "next_qty_fn(lib.SUCC(qty_fn))(n-1)" will become 0-1 // which then leads to infinite recursion. // // This behaviour does however result in mapping null to ZERO, which // might produce misleading results... // ******************************************************************** var do_qty_fn = next_qty_fn => qty_fn => n => (n === 0 || n === null) ? qty_fn : next_qty_fn(SUCC(qty_fn))(n-1) var TO_CHURCH = Y(do_qty_fn)(ZERO_MAGNITUDE) // Define a FACTORIAL function var FACTORIAL = list => REDUCE(list) // The list being reduced (val => acc => MULTIPLY(TO_CHURCH(val))(acc)) // The reduction function now using Church numerals (UNIT_MAGNITUDE) // The accumulator start value // Define a SUM function var SUM = list => REDUCE(list) // The list being reduced (val => acc => ADD(TO_CHURCH(val))(acc)) // The reduction function now using Church numerals (ZERO_MAGNITUDE) // The accumulator start value // Fold left is simply a synonym for REDUCE // Fold right is simply a fold left performed on the reversed list var FOLDL = REDUCE var FOLDR = list => REDUCE(REVERSE(list)) return { adder : adder , multiplier : multiplier , str_concatenate: str_concatenate , asPlusChar : str_concatenate('+') , incr : adder(1) , decr : adder(-1) , push : push , magnitude : magnitude , to_integer : to_integer , to_string : to_string , to_boolean : to_boolean , is_empty : is_empty , is_last : is_last , is_pos : is_pos , sign : sign , str2list : str2list , list2str : list2str , array2list : array2list , list2array : list2array , PAIR : PAIR , TRUE : TRUE , FALSE : FALSE , HEAD : HEAD , TAIL : TAIL , EMPTY_LIST : EMPTY_LIST , IS_EMPTY : IS_EMPTY , IS_LAST : IS_LAST , SUCC : SUCC , PRED : PRED , NUMBER : NUMBER , ABS : ABS , SIGN : SIGN , ZERO_MAGNITUDE : ZERO_MAGNITUDE , UNIT_MAGNITUDE : UNIT_MAGNITUDE , HAS_ZERO_MAGNITUDE : HAS_ZERO_MAGNITUDE , HAS_UNIT_MAGNITUDE : HAS_UNIT_MAGNITUDE , SUCC_MAGNITUDE : SUCC_MAGNITUDE , PRED_MAGNITUDE : PRED_MAGNITUDE , ADD_MAGNITUDES : ADD_MAGNITUDES , SUBTRACT_MAGNITUDES : SUBTRACT_MAGNITUDES , ZERO : ZERO , PLUS_ONE : PLUS_ONE , PLUS_TWO : PLUS_TWO , PLUS_THREE : PLUS_THREE , PLUS_FOUR : PLUS_FOUR , PLUS_FIVE : PLUS_FIVE , PLUS_SIX : PLUS_SIX , PLUS_SEVEN : PLUS_SEVEN , PLUS_EIGHT : PLUS_EIGHT , PLUS_NINE : PLUS_NINE , PLUS_TEN : PLUS_TEN , MINUS_ONE : MINUS_ONE , MINUS_TWO : MINUS_TWO , MINUS_THREE : MINUS_THREE , MINUS_FOUR : MINUS_FOUR , MINUS_FIVE : MINUS_FIVE , MINUS_SIX : MINUS_SIX , MINUS_SEVEN : MINUS_SEVEN , MINUS_EIGHT : MINUS_EIGHT , MINUS_NINE : MINUS_NINE , MINUS_TEN : MINUS_TEN , ADD : ADD , MULTIPLY : MULTIPLY , POWER : POWER , SUBTRACT : SUBTRACT , NOT : NOT , AND : AND , OR : OR , XOR : XOR , IS_POS : IS_POS , IS_NEG : IS_NEG , IS_ZERO : IS_ZERO , IS_MINUS_ONE : IS_MINUS_ONE , IS_LTE : IS_LTE , IS_LT : IS_LT , Y : Y , REVERSE : REVERSE , MAP : MAP , REDUCE : REDUCE , COUNT : COUNT , TO_CHURCH : TO_CHURCH , FACTORIAL : FACTORIAL , SUM : SUM , FOLDL : FOLDL , FOLDR : FOLDR } }51:[] 48:{"id":"0efd2be936d1ac34","slug":"mindshift-part-19","title":"Mindshift: Part 19","thumbnail":"2c5f1c5e24da279123536b326eb76e7ef625f14caa520001032cd5bc547b5d70","access_level":"public","create_time":"$D2018-12-07T17:50:11.234Z","update_time":"$D2020-01-10T18:33:00.155Z","view_time":null,"first_public_time":"$D2018-12-14T13:18:29.454Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"224d52e60cffa1e1","login":"chriswhealy","name":"Chris Whealy","avatar_url":"https://avatars-next.observableusercontent.com/fe4f3dea84e903c1f07bbfa1cc8292304033a736d3ab9d0e5c009d1340bfefb8","tier":"starter_2024","bio":"","followed_by_you":false,"follows_you":false},"version":561,"publish_version":561,"role":null,"authored":false,"authors":[{"type":"individual","id":"c2414676c206a65f","login":"chriswhealy","name":"Chris Whealy","avatar_url":"https://avatars-next.observableusercontent.com/fe4f3dea84e903c1f07bbfa1cc8292304033a736d3ab9d0e5c009d1340bfefb8","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"c2414676c206a65f","login":"chriswhealy","name":"Chris Whealy","avatar_url":"https://avatars-next.observableusercontent.com/fe4f3dea84e903c1f07bbfa1cc8292304033a736d3ab9d0e5c009d1340bfefb8","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Mindshift: Part 19","cells":[{"id":0,"value":"$4c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"MULTIPLY_MAGNITUDES = qtyFn1 => qtyFn2 =>\n qtyFn1(lib.ADD_MAGNITUDES(qtyFn2))\n (lib.ZERO_MAGNITUDE)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"$4d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"MULTIPLY = num1 => num2 =>\n lib.NUMBER(lib.NOT(lib.XOR(lib.SIGN(num1))(lib.SIGN(num2))))\n (MULTIPLY_MAGNITUDES(lib.ABS(num1))(lib.ABS(num2)))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"md`Let's make sure this function behaves correctly:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"{\n return {\n \"EIGHT_times_FIVE\" : lib.to_integer(MULTIPLY(lib.PLUS_EIGHT)(lib.PLUS_FIVE))\n , \"MINUS_EIGHT_times_FIVE\" : lib.to_integer(MULTIPLY(lib.MINUS_EIGHT)(lib.PLUS_FIVE))\n , \"EIGHT_times_MINUS_FIVE\" : lib.to_integer(MULTIPLY(lib.PLUS_EIGHT)(lib.MINUS_FIVE))\n , \"MINUS_EIGHT_times_MINUS_FIVE\" : lib.to_integer(MULTIPLY(lib.MINUS_EIGHT)(lib.MINUS_FIVE))\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"$4e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"do_div =\n div_next =>\n count =>\n remainder =>\n divisor =>\n // Should we continue with recursion?\n lib.IS_LTE(divisor)(remainder)\n // Yup, call div_next with an incremented counter, a new remainder\n // (of the divisor subtracted from the old remainder) and the divisor\n (fn =>\n (div_next(lib.SUCC(count))\n (lib.SUBTRACT(remainder)(divisor))\n (divisor))\n (fn))\n // Nope, we've reached the end so return a PAIR formed from the\n // the counter (now the quotient) and whatever is left over in the\n // remainder\n (lib.PAIR(count)(remainder))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":68,"value":"md`The do_div function is passed to the Y-Combinator which generates the value of the div_next parameter (this is a partial function capable of recursion). In the case of our DIV operation, the partial function returned by the Y-Combinator requires us to supply it with three further values: count, remainder and divisor.\n\nAs explained above, the initial value passed to remainder is the number being divided (the *dividend*)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":223,"value":"_DIV = remainder => divisor => lib.Y(do_div)(lib.ZERO_MAGNITUDE)(remainder)(divisor)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":74,"value":"md`## Division With NUMBERs\n\nIn the same way that we renamed the old MULTIPLY function to be MULTIPLY_MAGNITUDES, we need to rename the do_div function to reflect the fact that it now works only with abstract quantity functions (a.k.a. magnitudes). So we'll call it do_div_magnitudes.\n\nHowever, if we stopped after only renaming this function, it would produce nonsense results. The reason is that within do_div_magnitudes, we use other functions that have now been modified to work with NUMBERs and not abstract quantity functions. These are SUCCessor, SUBTRACT and IS_LTE.\n\nIn the case of IS_LTE, we need to take the old definition of this function (that operated on abstract quantity functions) and rename it to be IS_MAGNITUDE_LTE.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":78,"value":"IS_MAGNITUDE_LTE =\n lte_qtyFn1 =>\n lte_qtyFn2 =>\n lib.HAS_ZERO_MAGNITUDE(lib.SUBTRACT_MAGNITUDES(lte_qtyFn1)(lte_qtyFn2))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":349,"value":"md`So our new do_div_magnitudes function now looks like this:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"do_div_magnitudes =\n div_next =>\n count =>\n remainder =>\n divisor =>\n // Should we continue with recursion?\n IS_MAGNITUDE_LTE(divisor)(remainder)\n // Yup, call div_next with an incremented counter, a new remainder\n // (of the divisor subtracted from the old remainder) and the divisor\n (fn =>\n (div_next(lib.SUCC_MAGNITUDE(count))\n (lib.SUBTRACT_MAGNITUDES(remainder)(divisor))\n (divisor))\n (fn))\n // Nope, we've reached the end so return a PAIR formed from the\n // the counter (now the quotient) and whatever is left over in the\n // remainder\n (lib.PAIR(count)(remainder))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":495,"value":"lib.to_boolean(IS_MAGNITUDE_LTE(lib.PLUS_EIGHT)(lib.PLUS_FIVE))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":95,"value":"$4f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":97,"value":"DIV = dividend => divisor =>\n lib.NUMBER(lib.NOT(lib.XOR(lib.SIGN(dividend))(lib.SIGN(divisor))))\n (lib.Y(do_div_magnitudes)\n (lib.ZERO_MAGNITUDE)\n (lib.ABS(dividend))\n (lib.ABS(divisor))\n )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":102,"value":"md`The next thing we must remember is that although the value coming back from DIV has been packaged inside a NUMBER function, it is in fact not really a NUMBER in the sense we have previously been using.\n\nThe first part of the NUMBER pair is still the sign, but second part is another PAIR containing the *quotient* and the *remainder*.\n\nSo we can put together some helper functions to unload these values into a JavaScript object.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"magnitude_quot = numFn => lib.magnitude(lib.HEAD(lib.TAIL(numFn)))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":105,"value":"magnitude_rem = numFn => lib.magnitude(lib.TAIL(lib.TAIL(numFn)))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"div_result = numFn =>\n ({ isPos : lib.sign(numFn),\n quot : magnitude_quot(numFn),\n rem : magnitude_rem(numFn)\n })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":114,"value":"md`We can now test that our DIV operator works correctly.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"{\n return {\n \"EIGHT_divided_by_FIVE\" : div_result(DIV(lib.PLUS_EIGHT)(lib.PLUS_FIVE))\n , \"MINUS_EIGHT_divided_by_FIVE\" : div_result(DIV(lib.MINUS_EIGHT)(lib.PLUS_FIVE))\n , \"EIGHT_divided_by_MINUS_FIVE\" : div_result(DIV(lib.PLUS_EIGHT)(lib.MINUS_FIVE))\n , \"MINUS_EIGHT_divided_by_MINUS_FIVE\" : div_result(DIV(lib.MINUS_EIGHT)(lib.MINUS_FIVE))\n\n , \"FIVE_divided_by_EIGHT\" : div_result(DIV(lib.PLUS_FIVE)(lib.PLUS_EIGHT))\n , \"MINUS_FIVE_divided_by_EIGHT\" : div_result(DIV(lib.MINUS_FIVE)(lib.PLUS_EIGHT))\n , \"FIVE_divided_by_MINUS_EIGHT\" : div_result(DIV(lib.PLUS_FIVE)(lib.MINUS_EIGHT))\n , \"MINUS_FIVE_divided_by_MINUS_EIGHT\" : div_result(DIV(lib.MINUS_FIVE)(lib.MINUS_EIGHT))\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":124,"value":"md`Cool!\n\n## Exponentiation?\n\nJust in case you were wondering, I'm ***not*** going to implement exponentiation here because raising any number to the power of a negative number -n is the same as taking the nth root of that number.\n\nThis would require me to implement an nth-root algorithm in Lambda Calculus which in turn, will lure me into the Turing tar-pit where, as Alan Perlis said in his 1982 article Epigrams on Programming:\n\n> 54 *Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy*.\n\n:-)\n\nChris W\n\n\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"$50","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W51","stdlib":"1"}} 24:null