lambdaway :: words

3 | list | login |load

| |

_h1 binary arithmetic in λ-calculus

_h4 [[words_numbers]] | [[words_numbers2]] | words_numbers3 | [[words_numbers4]] | [[words_numbers5]]

{{block}

_h2 introduction

_p In λ-calculus numbers don't exist and use to be implemented as "Church numerals". There are a few alternatives but none of them can deal with big numbers. In this document we explore four arithmetic operators, {b addition, subtraction, multiplication & division}, working on natural numbers implemented as {b lists of booleans}, using exclusively the {b lambda & def} lambdatalk special forms, with the exception of a set of functions used to write and read them in a human binary and decimal representations.

_p Content:
 
{pre
introduction
foundations
    booleans
    pairs
    lists
numbers
    addition
        ADD
    subtraction
        INVERT, SUB
        SUCC, PRED
        LT?, GT?
        FIB
    multiplication
        SHFTL, SHFTR
        MUL
        POW
        FAC
    division
        DIVMOD
        DIV, MOD
        GCD
conclusion
}

_p Results on my iPad Pro:

{pre
'{bool2dec
 {B.ADD {dec2bool 64 999999999999999}
        {dec2bool 64 1}}}
-> 1000000000000000

'{bool2dec
 {B.SUB {dec2bool 64 999999999999999}
        {dec2bool 64 1}}}
-> 999999999999998

'{bool2dec
 {B.MUL {dec2bool 64 111111111111111}
        {dec2bool 64 3}}}
-> 333333333333333

'{bool2dec
 {B.DIV {dec2bool 64 999999999999999}
        {dec2bool 64 3}}}
-> 333333333333333

'{bool2dec {B.FIB {dec2bool 8 10}}}      // about 50ms
-> fib(10) = 55

'{bool2dec {B.FIB {dec2bool 80 100}}}    // about 5000ms
-> fib(100) = 354224848179261915075

'{bool2dec {B.FAC {dec2bool 24 10}}}     // about 300ms
-> {S.reduce long_mult {S.serie 1 10}}

'{bool2dec {B.FAC {dec2bool 180 35}}}    // about 12000ms 
-> fac(35) = {S.reduce long_mult {S.serie 1 35}}
}

_p At the beginning the dictionary is supposed to be empty, there is no primitive, just {b lambdas, defs & words}. Let's begin to build the foundations, {b booleans, pairs & lists}.

}

{{block}
_h2 foundations

_p Booleans, pairs and lists are supposed not to exist, we build them as anonymous functions with {b lambda} and give them a name with {b def}.

_h3 booleans
 
{pre 
'{def #1 {lambda {:a :b} :a}}              // true
-> {def #1 {lambda {:a :b} :a}}
'{def #0 {lambda {:a :b} :b}}              // false
-> {def #0 {lambda {:a :b} :b}}
'{def IF {lambda {:a :b :c} {:a :b :c}}}
-> {def IF {lambda {:a :b :c} {:a :b :c}}}

'{def NOT {lambda {:a} {IF :a #0 #1}}}
-> {def NOT {lambda {:a} {IF :a #0 #1}}}
'{def AND {lambda {:a :b} {IF :a :b #0}}}
-> {def AND {lambda {:a :b} {IF :a :b #0}}}
'{def OR  {lambda {:a :b} {IF :a #1 :b}}}
-> {def OR  {lambda {:a :b} {IF :a #1 :b}}}
'{def XOR 
 {lambda {:a :b}
  {OR {AND :a {NOT :b}} 
      {AND :b {NOT :a}}}}}
-> {def XOR {lambda {:a :b} {OR {AND :a {NOT :b}} {AND :b {NOT :a}}}}}

}

_h3 pairs

_p A pair is a data structure aggregating two words.

{pre
'{def PAIR {lambda {:a :b :c} {:c :a :b}}} 
-> {def PAIR {lambda {:a :b :c} {:c :a :b}}}
'{def LEFT {lambda {:c} {:c #1}}}
-> {def LEFT {lambda {:c} {:c #1}}}
'{def RIGHT {lambda {:c} {:c #0}}}
-> {def RIGHT {lambda {:c} {:c #0}}}

'{def NIL #1}                        // NIL is TRUE
-> {def NIL #1}    
'{def !NIL #0}                       // !NIL is FALSE
-> {def !NIL #0}
'{def NIL? {lambda {:c} {:c !NIL}}}  // if NIL then TRUE
-> {def NIL? {lambda {:c} {:c !NIL}}}

'{def P {PAIR a b}}
-> {def P {PAIR a b}}
'{LEFT {P}}
-> {LEFT {P}}
'{RIGHT {P}}
-> {RIGHT {P}}

'{NIL? {P}}
-> {NIL? {P}}
'{NIL? NIL}
-> {NIL? NIL}

'{{NIL? NIL} yes no}
-> {{NIL? NIL} yes no}
'{{NIL? {P}} yes no}
-> {{NIL? {P}} yes no}
}

_h3 lists

_p A {b list} is a pair whose first term is a {b word} and the second is {b NIL} or a {b list}. It's a recursive definition.

{pre
'{def A {PAIR a NIL}}
-> {def A {PAIR a NIL}}
'{def B {PAIR b {A}}}
-> {def B {PAIR b {A}}}
'{def C {PAIR c {B}}}
-> {def C {PAIR c {B}}}
'{def ABC {PAIR a {PAIR b {PAIR c NIL}}}}
-> {def ABC {PAIR a {PAIR b {PAIR c NIL}}}}
}

_p We will have to display and reverse lists and to compute their length.

{pre
'{def L.DISP
 {lambda {:l}
  {{IF {NIL? :l}
   {lambda {:l} }
   {lambda {:l} {LEFT :l}
                {L.DISP {RIGHT :l}}}
          } :l}}}
-> {def L.DISP
 {lambda {:l}
  {{IF {NIL? :l}
   {lambda {:l} }
   {lambda {:l} {LEFT :l} {L.DISP {RIGHT :l}}}} :l}}}

'{def L.REV
 {def L.REV.r
  {lambda {:a :b}
   {{IF {NIL? :a}
    {lambda {:a :b } :b}
    {lambda {:a :b} {L.REV.r {RIGHT :a}
                             {PAIR {LEFT :a} :b}}}
           } :a :b}}}
 {lambda {:l}
  {L.REV.r :l NIL}}}
-> {def L.REV
 {def L.REV.r
  {lambda {:a :b}
   {{IF {NIL? :a}
    {lambda {:a :b } :b}
    {lambda {:a :b} {L.REV.r {RIGHT :a} {PAIR {LEFT :a} :b}}}} :a :b}}}
 {lambda {:l}
  {L.REV.r :l NIL}}}

'{def L.LENGTH
 {lambda {:l}
  {{IF {NIL? :l}
   {lambda {:l} 0}
   {lambda {:l} {+ 1 {L.LENGTH {RIGHT :l}}}}
          } :l}}}
-> {def L.LENGTH
 {lambda {:l}
  {{IF {NIL? :l}
   {lambda {:l} 0}
   {lambda {:l} {+ 1 {L.LENGTH {RIGHT :l}}}}} :l}}}

'{L.DISP {A}}
-> {L.DISP {A}}
'{L.DISP {B}}
-> {L.DISP {B}}
'{L.DISP {C}}
-> {L.DISP {C}}
'{L.DISP {ABC}}
-> {L.DISP {ABC}}

'{L.DISP {L.REV {ABC}}}
-> {L.DISP {L.REV {ABC}}}

'{L.LENGTH {ABC}}
-> {L.LENGTH {ABC}}
}

_p Note that the {b L.LENGTH} function is "impure", using JS Math objects. Only used to make easier writings and readings this function could be forgotten. More explanations on booleans, pairs and lists can be seen in [[words_numbers]].
}

{{block}
_h2 numbers

_p Natural numbers will be defined as {b lists of booleans}, that is to say {b pairs} whose first term is a boolean, {b #1} or {b #0}, and the second is a pair or {b NIL}. For instance:

{pre
'{def FIVE
 {PAIR #0
 {PAIR #1
 {PAIR #0 
 {PAIR #1 
       NIL}}}}}
-> {def FIVE {PAIR #0 {PAIR #1 {PAIR #0 {PAIR #1 NIL}}}}}
'{L.DISP {FIVE}}
-> {L.DISP {FIVE}}
}

_p Writing and reading numbers defined as lists of booleans being rather painful, we will define a set of lambdatalk functions to deal with them more easily using the binary digits and decimal representations. For instance the number {b FIVE} will be written more easily as a binary number, "{b 0101}", or as a decimal number, "{b 5}".

{pre
'{bool2bin {FIVE}}
-> {bool2bin {FIVE}}
'{bool2dec {FIVE}}
-> {bool2dec {FIVE}}

'{dec2bin 4 5}    // 4 defines the binary number's length
-> {dec2bin 4 5}
'{L.DISP {bin2bool 0101}}
-> {L.DISP {bin2bool 0101}}
}

_h3 ZERO & ONE

_p We define {b ZERO} and {b ONE} as n-bits functions, and the predicate function {b B.ZERO?} returning #1 for ZERO else #0. Note that the {b ZERO & ONE} functions use two lambdatalk functions dedicated to input/outputs and are "inpure". They could be replaced by defining {b ZERO & ONE} manualy, as we did for {b FIVE} but that should be boring.

{pre 
'{def ZERO {lambda {:n} {bin2bool {zpadd :n}}}}
-> {def ZERO {lambda {:n} {bin2bool {zpadd :n}}}}
'{def ONE  {lambda {:n} {bin2bool {zpadd {- :n 1}}1}}}
-> {def ONE {lambda {:n} {bin2bool {zpadd {- :n 1}}1}}}

'{L.DISP {ZERO 4}}
-> {L.DISP {ZERO 4}}
'{L.DISP {ONE 4}}
-> {L.DISP {ONE 4}}

'{def B.ZERO?
 {def B.ZERO?.rec
  {lambda {:a :b}
   {{IF {NIL? :a}
    {lambda {:a :b} :b}
    {lambda {:a :b}
   {{IF {LEFT :a}
    {lambda {:a :b} #0}
    {lambda {:a :b} {B.ZERO?.rec {RIGHT :a}
                                 {IF {LEFT :a} #0 :b}}}
           } :a :b}}
           } :a :b}}}
 {lambda {:a}
  {B.ZERO?.rec :a #1}}} 
-> {def B.ZERO?
 {def B.ZERO?.rec
  {lambda {:a :b}
   {{IF {NIL? :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {{IF {LEFT :a}
    {lambda {:a :b} #0}
    {lambda {:a :b} {B.ZERO?.rec {RIGHT :a}
                                 {IF {LEFT :a} #0 :b}}}
          } :a :b}}
          } :a :b}}}
 {lambda {:a}
  {B.ZERO?.rec :a #1}}}

'{B.ZERO? {ZERO 4}}
-> {B.ZERO? {ZERO 4}}
'{B.ZERO? {ONE 10}}
-> {B.ZERO? {ONE 10}}  
}  
 
{{hide}
{def zero?
 {def zero?.r
  {lambda {:w :z :n}
   {if {A.empty? :w}
    then :z (:n) 
    else {if {W.equal? {A.first :w} 1}
          then false (:n)
          else {zero?.r {A.rest :w}
                        {W.equal? {A.first :w} 0}
                        {+ :n 1}} }}}}
 {lambda {:w}
  {zero?.r {A.split :w} false 0}}}

{zero? 00000000000000000000}
{zero? 00100000000000000000}
{zero? 00001010000000000000}
{zero? 00000000000000000001}
} 
}

{{block}

_h2 addition

_p The addition of two booleans {b a} and {b b} is based on these rules

{center {pre
a b s x
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
}}

_p where {b s} is the sum and {b x} is the carry.

_h3 adding two 1-bit numbers

{pre

'{def B.ADD.bit.sum
 {lambda {:x :a :b}
  {XOR :x {XOR :a :b}}}}
-> {def B.ADD.bit.sum
 {lambda {:x :a :b}
  {XOR :x {XOR :a :b}}}}

'{def B.ADD.bit.carry
 {lambda {:x :a :b}
  {OR {AND :a :b}
      {OR {AND :x :a}
          {AND :x :b}}}}}
-> {def B.ADD.bit.carry
 {lambda {:x :a :b}
  {OR {AND :a :b}
      {OR {AND :x :a}
          {AND :x :b}}}}}

'{def B.ADD.bit
 {lambda {:x :a :b}
  {PAIR {B.ADD.bit.sum :x :a :b}
        {B.ADD.bit.carry :x :a :b}}}}
-> {def B.ADD.bit
 {lambda {:x :a :b}
  {PAIR {B.ADD.bit.sum :x :a :b}
        {B.ADD.bit.carry :x :a :b}}}}
}

_h3 adding two n-bits numbers

{pre
'{def B.ADD

{def B.ADD.rec
  {lambda {:x :a :b}
   {{IF {OR {NIL? :a} {NIL? :b}}
    {lambda {:x :a :b} {{lambda {:x} {IF {LEFT :x} :x {RIGHT :x}}
                        } {PAIR :x NIL}}}
    {lambda {:x :a :b} {{lambda {:x :a :b} {PAIR {LEFT :x}
                                                 {B.ADD.rec {RIGHT :x}
                                                            {RIGHT :a}
                                                            {RIGHT :b}}}
                        } {B.ADD.bit :x {LEFT :a} {LEFT :b}} :a :b}}
           } :x :a :b}}}

{lambda {:a :b}
  {L.REV {B.ADD.rec #0 {L.REV :a} {L.REV :b}} }}} 
-> {def B.ADD
  {def B.ADD.bit
 {lambda {:x :a :b}
  {PAIR {XOR :x {XOR :a :b}}
        {OR {AND :a :b}
            {OR {AND :x :a}
                {AND :x :b}}}}}}
 {def B.ADD.rec
  {lambda {:x :a :b}
   {{IF {OR {NIL? :a} {NIL? :b}} 
        {lambda {:x :a :b}
         {{lambda {:x} {IF {LEFT :x} :x {RIGHT :x}}}
           {PAIR :x NIL}}}
        {lambda {:x :a :b}
         {{lambda {:x :a :b}
           {PAIR {LEFT :x}
                 {B.ADD.rec {RIGHT :x}
                            {RIGHT :a}
                            {RIGHT :b}}}
          } {B.ADD.bit :x {LEFT :a} {LEFT :b}} :a :b}}}
      :x :a :b }}} 
 {lambda {:a :b}
  {L.REV {B.ADD.rec #0 {L.REV :a} {L.REV :b} }}} }

}

{pre

'{bool2bin
 {B.ADD {bin2bool 0111}
        {bin2bool 0001}}}
-> {bool2bin {B.ADD {bin2bool 0111} {bin2bool 0001}}}

'{bool2dec
 {B.ADD {dec2bool 4 7}
        {dec2bool 4 1}}}
-> 8

'{bool2dec
 {B.ADD {dec2bool 32 {pow 2 31}}
        {dec2bool 32 {pow 2 31}}}} 
-> 4294967296  // 2{sup 32}
}
}

{{block}
_h2 subtraction

_p Subtracting two numbers will be done by adding to the first the two's complement of the second. The two's complement of an N-bit number is defined as its complement with respect to 2{sup N}; the sum of a number and its two's complement is 2{sup N}. For instance, for the three-bit number 010{sub 2}, the two's complement is 110{sub 2}, because 010{sub 2} + 110{sub 2} = 1000{sub 2} = 8{sub 10} which is equal to 2{sup 3}.

_h3 B.INVERT

_p The two's complement is calculated by inverting the bits and adding one.

{pre
'{def B.INVERT
 {lambda {:a}
  {{IF {NIL? :a} 
   {lambda {:a} NIL}
   {lambda {:a} {PAIR {NOT {LEFT :a}}
                      {B.INVERT {RIGHT :a}}}}
         } :a}}}
-> {def B.INVERT
 {lambda {:a}
  {{IF {NIL? :a} 
   {lambda {:a} NIL}
   {lambda {:a} {PAIR {NOT {LEFT :a}}
                      {B.INVERT {RIGHT :a}}}}} :a}}}

'{bool2bin {B.INVERT {bin2bool 10101}}} // 01010
'{bool2bin {B.INVERT {bin2bool 1010}}}  // 0101
'{bool2bin {B.INVERT {bin2bool 101}}}   // 010
'{bool2bin {B.INVERT {bin2bool 10}}}    // 01
'{bool2bin {B.INVERT {bin2bool 1}}}     // 0
}

_h3 B.SUB

{pre
'{def B.SUB
 {lambda {:a :b}  
  {RIGHT 
   {B.ADD :a 
          {B.ADD {B.INVERT :b} 
                 {ONE {L.LENGTH :a}}}} } }}   
-> {def B.SUB
 {lambda {:a :b}  
  {RIGHT 
     {B.ADD :a {B.ADD {B.INVERT :b} {ONE {L.LENGTH :a}}}} } }}

'{bool2dec {B.SUB {dec2bool 4 7} {dec2bool 4 1}}} // 6
'{bool2dec {B.SUB {dec2bool 4 7} {dec2bool 4 2}}} // 5
'{bool2dec {B.SUB {dec2bool 4 7} {dec2bool 4 3}}} // 4
'{bool2dec {B.SUB {dec2bool 4 7} {dec2bool 4 4}}} // 3
'{bool2dec {B.SUB {dec2bool 4 7} {dec2bool 4 5}}} // 2
'{bool2dec {B.SUB {dec2bool 4 7} {dec2bool 4 6}}} // 1
'{bool2dec {B.SUB {dec2bool 4 7} {dec2bool 4 7}}} // 0
 
}

_h3 B.SUCC & B.PRED

_p Computing the successor and the predecessor of a number can be viewed as special cases of adding and subtracting two numbers.

{pre

'{def B.SUCC
 {lambda {:a}
  {B.ADD :a {ONE {L.LENGTH :a}} }}}    
-> {def B.SUCC
 {lambda {:a}
  {B.ADD :a {ONE {L.LENGTH :a}} }}}

'{bool2dec {B.SUCC {dec2bool 8 0}}} -> 1
'{bool2dec {B.SUCC {dec2bool 8 1}}} -> 2
'{bool2dec {B.SUCC {dec2bool 8 2}}} -> 3
'{bool2dec {B.SUCC {dec2bool 8 3}}} -> 4
'{bool2dec {B.SUCC {dec2bool 8 4}}} -> 5
'{bool2dec {B.SUCC {dec2bool 8 5}}} -> 6

'{def B.PRED
 {lambda {:a}
  {B.SUB :a {ONE {L.LENGTH :a}}} }}   
-> {def B.PRED 
 {lambda {:a}
  {B.SUB :a {ONE {L.LENGTH :a}}} }}

'{bool2dec {B.PRED {dec2bool 8 7}}} -> 6
'{bool2dec {B.PRED {dec2bool 8 6}}} -> 5
'{bool2dec {B.PRED {dec2bool 8 5}}} -> 4
'{bool2dec {B.PRED {dec2bool 8 4}}} -> 3
'{bool2dec {B.PRED {dec2bool 8 3}}} -> 2
'{bool2dec {B.PRED {dec2bool 8 2}}} -> 1
'{bool2dec {B.PRED {dec2bool 8 1}}} -> 0
}

_h3 B.LT?, B.GT?

_p A number whose left boolean is #1 is negative.

{pre
'{def B.LT?
 {lambda {:a :b}
  {LEFT {B.SUB :a :b}}}}
-> {def B.LT?
 {lambda {:a :b}
  {LEFT {B.SUB :a :b}}}}

'{def B.GT?
 {lambda {:a :b}
  {LEFT {B.SUB :b :a}}}}
-> {def B.GT?
 {lambda {:a :b}
  {LEFT {B.SUB :b :a}}}}

'{B.LT? {ONE 4} {ZERO 4}}
-> {B.LT? {ONE 4} {ZERO 4}}
'{B.LT? {ZERO 4} {ONE 4}}
-> {B.LT? {ZERO 4} {ONE 4}}
'{B.LT? {ONE 4} {ONE 4}}
-> {B.LT? {ONE 4} {ONE 4}}

'{B.GT? {ONE 4} {ZERO 4}}
-> {B.GT? {ONE 4} {ZERO 4}}
'{B.GT? {ZERO 4} {ONE 4}}
-> {B.GT? {ZERO 4} {L.REV {ONE 4}}}
'{B.GT? {ONE 4} {ONE 4}}
-> {B.GT? {ONE 4} {ONE 4}}
}

_h3 B.FIB

_p The {b fibonacci} of a number is defined as {b fib(n) = fib(n-1)+fib(n-2)} avec {b fib(0)=0, fib(1)=1}. We will use the tail-recursive algorithm.

{pre
'{def B.FIB

{def B.FIB.rec
  {lambda {:a :b :i}
   {{IF {B.ZERO? :i}
    {lambda {:a :b :i} :a}
    {lambda {:a :b :i} {B.FIB.rec {B.ADD :a :b}
                                  :a 
                                  {B.PRED :i}}}
           } :a :b :i}}}

{lambda {:m}
  {B.FIB.rec {ZERO {L.LENGTH :m}} {ONE {L.LENGTH :m}} :m}}}
-> {def B.FIB
 {def B.FIB.rec
  {lambda {:a :b :i}
   {{IF {B.ZERO? :i}
    {lambda {:a :b :i} :a}
    {lambda {:a :b :i} {B.FIB.rec {B.ADD :a :b} :a {B.PRED :i}}}}
             :a :b :i}}}
 {lambda {:m} 
   {B.FIB.rec {ZERO {L.LENGTH :m}}
              {ONE {L.LENGTH :m}}
              :m}}}

'{bool2dec {B.FIB {dec2bool 8 10}}}
-> 55

'{bool2dec {B.FIB {dec2bool 128 100}}}
-> 354224848179261915075  
}

_p Fibonacci code viewed by [[John Tromp|https://tromp.github.io/cl/diagrams.html]]:

_img https://tromp.github.io/img/cl/fib.gif

}

{{block}

_h2 multiplication

_p Multiplying and dividing by 2 is quick, just shifting bits left or right.

_h3 B.SHFTL & B.SHFTR

{pre
'{def B.SHFTL
 {lambda {:b}
  {L.REV {PAIR #0 {L.REV {RIGHT :b}}}}}}
-> {def B.SHFTL
 {lambda {:b}
  {L.REV {PAIR #0 {L.REV {RIGHT :b}}}}}}

'{def B.SHFTR
 {lambda {:b}
  {PAIR #0 {L.REV {RIGHT {L.REV :b}}}}}}
-> {def B.SHFTR
 {lambda {:b}
  {PAIR #0 {L.REV {RIGHT {L.REV :b}}}}}}

'{bool2bin {B.SHFTL {bin2bool 0010}}}
-> {bool2bin {B.SHFTL {bin2bool 0010}}}
'{bool2bin {B.SHFTR {bin2bool 0010}}}
-> {bool2bin {B.SHFTR {bin2bool 0010}}}

'{bool2dec {B.SHFTL {dec2bool 16 256}}}
-> {bool2dec {B.SHFTL {dec2bool 16 256}}} 
'{bool2dec {B.SHFTR {dec2bool 16 256}}}
-> {bool2dec {B.SHFTR {dec2bool 16 256}}}

}

_h3 B.MUL

_p Here is an example illustrating the algorithm.

{center {pre
5830 * 23958233 = 139676498390

Decimal:               Binary: shifts only        
;;x=x//2   y=y*2   shift x right        shift y left
5830  {del 23958233}   1011011000110  {del 1011011011001001011011001}
2915  47916466   101101100011  10110110110010010110110010
1457  95832932   10110110001  101101101100100101101100100
728  {del 191665864}   1011011000  {del 1011011011001001011011001000}
364  {del 383331728}   101101100  {del 10110110110010010110110010000}
182  {del 766663456}   10110110  {del 101101101100100101101100100000}
91  1533326912   1011011  1011011011001001011011001000000
45  3066653824   101101  10110110110010010110110010000000
22  {del 6133307648}   10110  {del 101101101100100101101100100000000}
11 12266615296   1011  1011011011001001011011001000000000
5  24533230592   101  10110110110010010110110010000000000
2  {del 49066461184}   10  {del 101101101100100101101100100000000000}
1  98132922368   1  1011011011001001011011001000000000000
  ————————————      —————————————————————————————————————
  139676498390     10000010000101010111100011100111010110

}}

_p Translated into the following code.

{pre
'{def B.MUL

{def B.MUL.rec
  {lambda {:a :b :c}
   {{IF {B.ZERO? :a}
    {lambda {:a :b :c} :c}
    {lambda {:a :b :c} {B.MUL.rec {B.SHFTR :a}   // a / 2
                                  {B.SHFTL :b}   // b * 2
                                  {IF {LEFT :a}
                                      {B.ADD :c :b}
                                      :c}} }
           } :a :b :c}}}

{lambda {:a :b}
  {B.MUL.rec :a :b {ZERO {L.LENGTH :a}}}}} 
-> {def B.MUL
 {def B.MUL.rec
  {lambda {:a :b :c}
   {{IF {B.ZERO? :a}
    {lambda {:a :b :c} :c}
    {lambda {:a :b :c}
     {B.MUL.rec {B.SHFTR :a}
                {B.SHFTL :b}
                {IF {LEFT {L.REV :a}} {B.ADD :c :b} :c}} }
    } :a :b :c}}}
 {lambda {:a :b}
  {B.MUL.rec :a :b {ZERO {L.LENGTH :a}}}}}

'{bool2bin
 {B.MUL {bin2bool 0010}
        {bin2bool 0011}}}
-> 0110

'{bool2dec
 {B.MUL {dec2bool 16 123}
        {dec2bool 16 456}}}
-> {* 123 456}

'{bool2dec
 {B.MUL {dec2bool 80 123456789123}
        {dec2bool 80 123456789123}}}
-> 15241578780560891109129

to be compared with the {b long_mult} lambdatalk operator

'{long_mult 123456789123 123456789123}
-> {long_mult 123456789123 123456789123}

and the {b *} JS operator

'{* 123456789123 123456789123}
-> {* 123456789123 123456789123}
}

_h3 B.POW

_p Here is an example illustrating the algorithm.

{center {pre
3{sup 9} = {pow 3 9}

Decimal:              Binary: shifts             
a*a    b//2         shiftleft        siftright      
3       9        {dec2bin 16 3}  {dec2bin 16 9}
{* 3 3}       4        {dec2bin 16 9}  {dec2bin 16 4}
{* 9 9}      2        {dec2bin 16 81}  {dec2bin 16 2}
{* 81 81}    1        {dec2bin 16 6561}  {dec2bin 16 1}
{* 6561 3}   0        {dec2bin 16 19683}  {dec2bin 16 0}
}}

_p Translated into the following code.

{pre
'{def B.POW
 {def B.POW.rec
  {lambda {:a :b :c}
   {{IF {B.ZERO? :b}
    {lambda {:a :b :c} :c}
    {lambda {:a :b :c} {B.POW.rec {B.MUL :a :a} 
                                  {B.SHFTR :b}  
                                  {IF {LEFT {L.REV :b}} 
                                      {B.MUL :a :c}
                                      :c} }}
           } :a :b :c}}}
 {lambda {:a :b}
  {B.POW.rec :a :b {ONE {L.LENGTH :a}}}}} 
-> {def B.POW
 {def B.POW.rec
  {lambda {:a :b :c}
   {{IF {B.ZERO? :b}
    {lambda {:a :b :c} :c}
    {lambda {:a :b :c} {B.POW.rec {B.MUL :a :a} 
                                  {B.SHFTR :b}  
                                  {IF {LEFT {L.REV :b}} {B.MUL :a :c} :c} }}
           } :a :b :c}}}
 {lambda {:a :b}
  {B.POW.rec :a :b {ONE {L.LENGTH :a}}}}}

'{bool2dec 
 {B.POW {dec2bool 16 3}
        {dec2bool 16 9}}}
-> {pow 3 9}

'{bool2dec 
 {B.POW {dec2bool 64 2}
        {dec2bool 64 32}}}
-> {pow 2 32} 
}

_h3 B.FAC

_p The {b factorial} of a number is defined as {b fac(n) = n*fac(n-1) with fac(0) = 1}. We will use the tail-recursive algorithm.

{prewrap
'{def B.FAC

{def B.FAC.rec
  {lambda {:a :b}
   {{IF {B.ZERO? :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {B.FAC.rec {B.PRED :a}
                               {B.MUL :a :b}}}} 
             :a :b}}}

{lambda {:a}
  {B.FAC.rec :a {ONE {L.LENGTH :a}}}}}
-> {def B.FAC

{def B.FAC.rec
  {lambda {:a :b}
   {{IF {B.ZERO? :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {B.FAC.rec {B.PRED :a} {B.MUL :a :b}}}} 
             :a :b}}}

{lambda {:a}
  {B.FAC.rec :a {ONE {L.LENGTH :a}}}}}

'{bool2dec {B.FAC {dec2bool 16 6}}}
-> 720

'{bool2dec {B.FAC {dec2bool 128 30}}}
-> {S.reduce long_mult  {S.serie 1 30}}
}

_p So {b '{B.FAC 128 30}} returns the exact value (computed in about 20 seconds) to be compared with the approximation {b {* {S.serie 1 30}}} given (instantanly) by Javascript.

_p Factorial code viewed by [[John Tromp|https://tromp.github.io/cl/diagrams.html]]

_img https://tromp.github.io/img/cl/fac.gif

°°°
_h3 B.DIVMOD, B.DIV, B.MOD, B.GCD

{pre
a//b -> (q,r)

'{/ 7 2} = 3.5 
'{// 7 2} = (3,1)

a  b  q  x
==========
7  2  1  2        < 7
7  2  2  2+2 = 4  < 7
7  2  3  2+4 = 6  < 7 -> q=3, r=7-2*3 -> (3,1)
7  2  4  2+6 = 8  > 7 -> oops!

'{def B.DIVMOD   
 {def B.DIVMOD.rec                        
  {lambda {:a :b :q :x}
   {{IF {B.GT? :x :a}       
    {lambda {:a :b :q :x} {PAIR {B.PRED :q} {B.SUB :a {B.MUL :b {B.PRED :q}}}}} 
    {lambda {:a :b :q :x} {B.DIVMOD.rec :a :b {B.SUCC :q} {B.ADD :b :x}}}}
             :a :b :q :x}}}
 {lambda {:a :b}
  {B.DIVMOD.rec :a :b {L.REV {ONE {L.LENGTH :a}}} :b}}} 
-> {def B.DIVMOD   
 {def B.DIVMOD.rec                        
  {lambda {:a :b :q :x}
   {{IF {B.GT? :x :a}       
    {lambda {:a :b :q :x}
            {PAIR {B.PRED :q} {B.SUB :a {B.MUL :b {B.PRED :q}}}}}  
    {lambda {:a :b :q :x}
            {B.DIVMOD.rec :a :b {B.SUCC :q} {B.ADD :b :x}}}}
             :a :b :q :x}}}
 {lambda {:a :b}
   {B.DIVMOD.rec :a :b {ONE {L.LENGTH :a}} :b}}}

The result is the pair (q,r).

'{let { {:divmod {B.DIVMOD {dec2bool 8 7}
                          {dec2bool 8 2}}} 
     } ({bool2dec {LEFT :divmod}},    
        {bool2dec {RIGHT :divmod}})
}
-> (3,1)

'{let { {:divmod {B.DIVMOD {dec2bool 8 8} 
                          {dec2bool 8 2}}} 
     } ({bool2dec {LEFT :divmod}}, 
        {bool2dec {RIGHT :divmod}})
}
-> (4,0)
}
°°°
}

{{block}
_h2 division

_p Following [[http://compoasso.free.fr/primelistweb/page/prime/euclide.php|http://compoasso.free.fr/primelistweb/page/prime/euclide.php]]

{pre
'{def B.DIVMOD

{def B.DIVMOD.init
 {lambda {:a :x :n}
  {{IF {B.GT? :x :a}
   {lambda {:a :x :n} {PAIR :n :x}}
   {lambda {:a :x :n} {B.DIVMOD.init :a
                                     {B.SHFTL :x}
                                     {B.SUCC :n}} }
          } :a :x :n}}}  
 
{def B.DIVMOD.loop
 {lambda {:n :x :q :r}
  {{IF {B.GT? :n {ZERO {L.LENGTH :n}}}   
   {lambda {:n :x :q :r} 
    {{lambda {:n :x :q :r}
      {B.DIVMOD.loop :n
                     :x
                     {{IF {B.LT? :r :x} 
                      {lambda {:n :x :q :r} :q :r} 
                      {lambda {:n :x :q :r} {B.SUCC :q}
                                            {B.SUB :r :x}}  
                             } :n :x :q :r} }
     } {B.PRED :n} {B.SHFTR :x} {B.SHFTL :q} :r}}
   {lambda {:n :x :q :r} {PAIR :q :r}}
          } :n :x :q :r}}}

{lambda {:a :b}  
  {{lambda {:xn :q :r}
           {B.DIVMOD.loop {LEFT :xn} {RIGHT :xn} :q :r}
   } {B.DIVMOD.init :a :b {ZERO {L.LENGTH :a}}}
                          {ZERO {L.LENGTH :a}} :a}}}
-> {def B.DIVMOD

{def B.DIVMOD.init
 {lambda {:a :x :n}
  {{IF {B.GT? :x :a}
   {lambda {:a :x :n} {PAIR :n :x}}
   {lambda {:a :x :n} {B.DIVMOD.init :a {B.SHFTL :x} {B.SUCC :n}} }
          } :a :x :n}}}  
 
{def B.DIVMOD.loop
 {lambda {:n :x :q :r}
  {{IF {B.GT? :n {ZERO {L.LENGTH :n}}}   
   {lambda {:n :x :q :r} 
    {{lambda {:n :x :q :r}
      {B.DIVMOD.loop :n :x {{IF {B.LT? :r :x} 
                       {lambda {:n :x :q :r} :q :r} 
                       {lambda {:n :x :q :r} {B.SUCC :q} {B.SUB :r :x}}  
                              } :n :x :q :r} }
     } {B.PRED :n} {B.SHFTR :x} {B.SHFTL :q} :r}}
   {lambda {:n :x :q :r} {PAIR :q :r}}
          } :n :x :q :r}}}

{lambda {:a :b}  
  {{lambda {:xn :q :r}
           {B.DIVMOD.loop {LEFT :xn} {RIGHT :xn} :q :r}
   } {B.DIVMOD.init :a :b {ZERO {L.LENGTH :a}}} {ZERO {L.LENGTH :a}} :a}}}

'{let { {:div {B.DIVMOD {bin2bool 0111}     // 7
                  {bin2bool 0010}}}        // 2
     } ({bool2bin {LEFT :div}} {bool2bin {RIGHT :div}})}
-> (0011 0001)
   (3 1)  // 7=2*3+10

'{let { {:div {B.DIVMOD {dec2bool 32 218}
                  {dec2bool 32 6}}}
     } ({bool2dec {LEFT :div}} {bool2dec {RIGHT :div}})}
-> (36 2) //  218=6*36+2

'{let { {:div {B.DIVMOD {dec2bool 64 6666666667} 
                  {dec2bool 64 2}}}
     } ({bool2dec {LEFT :div}} {bool2dec {RIGHT :div}})}
-> (3333333333 1)  // 6666666667 = 2*3333333333+1
}

_h3 B.DIV, B.MOD

{pre
'{def B.DIV
 {lambda {:a :b}
  {LEFT {B.DIVMOD :a :b}}}}
-> {def B.DIV
 {lambda {:a :b}
  {LEFT {B.DIVMOD :a :b}}}}

'{def B.MOD
 {lambda {:a :b}
  {RIGHT {B.DIVMOD :a :b}}}}
-> {def B.MOD
 {lambda {:a :b}
  {RIGHT {B.DIVMOD :a :b}}}}

'{bool2dec {B.DIV {dec2bool 8 7}
                 {dec2bool 8 2}}} -> 3
'{bool2dec {B.DIV {dec2bool 8 8}
                 {dec2bool 8 2}}} -> 4
'{bool2dec {B.MOD {dec2bool 8 7}
                 {dec2bool 8 2}}} -> 1
'{bool2dec {B.MOD {dec2bool 8 8}
                 {dec2bool 8 2}}} -> 0 
}

_h3 B.GCD

{pre
'{def B.GCD
 {lambda {:a :b}
  {{IF {B.ZERO? :b} 
   {lambda {:a :b} :a}
   {lambda {:a :b} {B.GCD :b
                          {RIGHT {B.DIVMOD :a :b}}}}
          } :a :b}}} 
-> {def B.GCD
 {lambda {:a :b}
  {{IF {B.ZERO? :b} 
   {lambda {:a :b} :a}
   {lambda {:a :b} {B.GCD :b
                          {RIGHT {B.DIVMOD :a :b}}}}
          } :a :b}}}
 
'{bool2dec {B.GCD {dec2bool 8 99}
                    {dec2bool 8 48}}}
-> 3

'{bool2dec {B.GCD {dec2bool 32 9999}
                    {dec2bool 32 4888}}}
-> 1
}

}

{{block}
_h2 translations

_p Writing and reading numbers defined as lists of booleans being rather painful, we will define a set of functions to deal with them more easily using the binary digits and decimal representations. For instance the number {b FIVE} will be written more easily as a binary number, "{b 0101}", or as a decimal number, "{b 5}".

_h3 dec2bool & bool2dec

_p The {b dec2bool} function translates a decimal number into a reversed list of booleans. The {b bool2dec} function translates a reversed list of booleans into a decimal number.

{pre
'{def dec2bool
 {lambda {:n :m}
  {L.REV {bin2bool {dec2bin :n :m}}}}}
-> {def dec2bool {lambda {:n :m} {bin2bool {dec2bin :n :m}}}}

'{def bool2dec
 {lambda {:m}
  {bin2dec {bool2bin {L.REV :m}}}}}
-> {def bool2dec {lambda {:m} {bin2dec {bool2bin :m}}}}

'{L.DISP {dec2bool 4 5}}
-> {L.DISP {dec2bool 4 5}}

'{bool2dec {PAIR #1 {PAIR #0 {PAIR #1 {PAIR #0 NIL}}}}}
-> {bool2dec {PAIR #0 {PAIR #1 {PAIR #0 {PAIR #1 NIL}}}}}

}

_h3 bin2bool & bool2bin

{pre
'{def bin2bool            
 {def bin2bool.r     
  {lambda {:s}
   {if {= {S.length :s} 1}
    then {PAIR :s NIL}
    else {PAIR {S.first :s}
               {bin2bool.r {S.rest :s}}}} }}
 {lambda {:w}
  {bin2bool.r {S.replace _ by space in
              {S.replace 1 by #1_ in 
              {S.replace 0 by #0_ in :w}}}}}}
-> {def bin2bool
 {def bin2bool.r     
  {lambda {:s}
   {if {= {S.length :s} 1}
    then {PAIR :s NIL}
    else {PAIR {S.first :s} {bin2bool.r {S.rest :s}}}} }}
 {lambda {:w}
  {bin2bool.r {S.replace _ by space in
              {S.replace 1 by #1_ in 
              {S.replace 0 by #0_ in :w}}}}}}

'{L.DISP {bin2bool 0011}}
-> {L.DISP {bin2bool 0011}}

'{def bool2bin            
 {lambda {:b}
  {S.replace \s by in
  {S.replace #0 by 0 in
  {S.replace #1 by 1 in {L.DISP :b}}}}}}
-> {def bool2bin
 {lambda {:b}
  {S.replace \s by in
  {S.replace #0 by 0 in
  {S.replace #1 by 1 in {L.DISP :b}}}}}}

'{bool2bin
 {PAIR #0
 {PAIR #1
 {PAIR #1
 {PAIR #1 NIL}}}}}
-> {bool2bin {PAIR #0 {PAIR #1 {PAIR #1 {PAIR #1 NIL}}}}}
}

_h3 dec2bin & bin2dec

{pre
'{def dec2bin
 {def zpadd
  {lambda {:n}
   {if {= :n 0}
    then
    else 0{zpadd {- :n 1}}}}}
 
 {def dec2bin.r
 {lambda {:dec}
  {if {= :dec 0}
   then 0
   else {if {< :dec 2}
         then 1
         else {dec2bin.r {floor {/ :dec 2}}}{% :dec 2} }}}}

{lambda {:n :dec}
  {let { {:n :n} {:b {dec2bin.r :dec}}
       } {zpadd {- :n {W.length :b}}}:b}}}  
-> {def dec2bin
 {def zpadd
  {lambda {:n}
   {if {= :n 0}
    then
    else 0{zpadd {- :n 1}}}}}

{def dec2bin.r
 {lambda {:dec}
  {if {= :dec 0}
   then 0
   else {if {< :dec 2}
         then 1
         else {dec2bin.r {floor {/ :dec 2}}}{% :dec 2} }}}}

{lambda {:n :dec}
  {let { {:n :n} {:b {dec2bin.r :dec}}
       } {zpadd {- :n {W.length :b}}}:b}}}

'{dec2bin 4 7}
-> {dec2bin 4 7}
'{dec2bin 32 7}
-> {dec2bin 32 7}

'{def bin2dec
 {def bin2dec.r
  {lambda {:p :r}
   {if {A.empty? :p}
    then :r
    else {bin2dec.r {A.rest :p}
                    {long_add {A.first :p}
                              {long_mult 2 :r}}}}}}
 {lambda {:p}
  {bin2dec.r {A.split :p} 0}}}
-> {def bin2dec
 {def bin2dec.r
  {lambda {:p :r}
   {if {A.empty? :p}
    then :r
    else {bin2dec.r {A.rest :p} {long_add {A.first :p} {long_mult 2 :r}}}}}}
 {lambda {:p}
  {bin2dec.r {A.split :p} 0}}}

'{bin2dec 0111} 
-> {bin2dec 0111}
}

}

{{block}
_h2 conclusion

_p And so λ-calculus in which natural numbers are implemented as lists of booleans can deal with big ones.

_p {i alain marty | 2022/07/04}
_p [[HN|https://news.ycombinator.com/item?id=31996475]]
}

{{hide}
{def block 
  div {@ style="display:inline-block; width:700px; vertical-align:top; padding:5px; "}}
}

{style 
body { background:#444; } 
#page_frame { border:0; background:transparent; width:600px; margin-left:0; }
#page_content { background:transparent; color:#fff; border:0; width:6500px; box-shadow:0 0 0; font:normal 1.2em papyrus, optima; }
.page_menu { background:transparent; color:#fff; }
a { color:#f80; }
pre { box-shadow:0 0 8px #000; padding:5px; background:transparent; color:#fff; font:normal 1.0em courier; }
b { color:#f80; }
h1 { font-size:4.0em; margin-left:0; }
h2 { font-size:3.0em; }
h3 { font-size:1.5em; }

a[href^="https://"]:after { content: " ➚"; } 
}