lambdaway :: oops5

2 | list | login |load

| |

{uncover data/LISP-inbinary.jpg 100 500 numbers as lists}

_p This is a recursive algorithm adding two binary numbers of any size.

;; _ul [[https://patents.google.com/patent/US4942549A/en|https://patents.google.com/patent/US4942549A/en]]

_h2 1) scheme version

_p Here is a Scheme code found in [[stackoverflow.com|https://stackoverflow.com/questions/29737768/scheme-full-adder-output-format]]

_p Standard boolean predicate functions {b and, or, xor} are replaced by logic-gates getting and returning {b 0 & 1}

{pre
(define and-gate (lambda (a b) (if (= a b 1) 1 0)))
(define or-gate  (lambda (a b) (if (not (= 0 (+ a b))) 1 0)))
(define xor-gate (lambda (a b) (if (= a b) 0 1)))
}

_p on which is built the {b bitAdder} function

{pre
(define (bitAdder x a b)
  (cons (sum-bit x a b)    
    (carry-out x a b)))

(define (sum-bit x a b)
  (xor-gate x (xor-gate a b)))

(define (carry-out x a b)
  (or-gate (and-gate a b)
           (or-gate (and-gate x a)
                    (and-gate x b))))
}

_p and finally the {b n-bit-adder} recursive function

{pre
(define (n-bit-adder a b)
  (reverseList (recursiveAdd a b 0)))

(define (recursiveAdd a b c)
  (if (null? a)      
      (list (list c))     
      (cons (car (bitAdder (tail a) (tail b) c))            
            (recursiveAdd (rmtail a)
                          (rmtail b) 
                          (cdr (bitAdder (tail a) (tail b) c))))))
}

_p Some helper functions

{pre
(define (tail lst)
  (if (null? (cdr lst))
      (car lst)
      (tail (cdr lst))))

(define (rmtail lst)
  (if (null? (cdr lst))      
      '()
      (cons (car lst)
            (rmtail (cdr lst)))))

(define (reverseList lst)
  (if (null? lst)
      '()
      (append (reverseList (cdr lst)) (list (car lst)))))
}

_p The {b tail} and {b rmtail} functions are time consuming and can be avoided, see below.

_h2 2) lambdatalk version

_p Here is a translation of the Scheme code into lambdatalk, evaluated in realtime in this page.

_h3 2.1) logic gates

_p Logic gates are built on the {b and, or} lambdatalk primitives replacing their outputs {b false & true} by {b 0 & 1} which are to be considered as words, not numbers.

{pre
'{def and-gate
 {lambda {:a :b}
  {if {and {= :a 1} {= :b 1}} then 1 else 0}}}
-> {def and-gate
 {lambda {:a :b}
  {if {and {= :a 1} {= :b 1}} then 1 else 0}}}
;; {and-gate 0 0} {and-gate 0 1} {and-gate 1 0} {and-gate 1 1}
'{def or-gate
 {lambda {:a :b}
  {if {or {= :a 1} {= :b 1}} then 1 else 0}}}
-> {def or-gate
 {lambda {:a :b}
  {if {or {= :a 1} {= :b 1}} then 1 else 0}}}
;; {or-gate 0 0} {or-gate 0 1} {or-gate 1 0} {or-gate 1 1}
'{def xor-gate
 {lambda {:a :b}
  {if {= :a :b} then 0 else 1}}}
-> {def xor-gate
 {lambda {:a :b}
  {if {= :a :b} then 0 else 1}}}

;; {xor-gate 0 0} {xor-gate 0 1} {xor-gate 1 0} {xor-gate 1 1}
}

_h3 2.2) the n-bits adder

{pre
'{def n-bit-adder
 {lambda {:a :b}
  {reverseList 
   {recursiveAdd {reverseList :a} {reverseList :b} 0}}}}
-> {def n-bit-adder
 {lambda {:a :b}
  {reverseList {recursiveAdd {reverseList :a} {reverseList :b} 0}}}}

'{def recursiveAdd
 {lambda {:a :b :c}
  {if {null? :a}
   then {cons {cons :c nil} nil}
   else {cons {car {bitAdder {car :a} {car :b} :c}}
              {recursiveAdd {cdr :a} {cdr :b}
                            {cdr {bitAdder {car :a} {car :b} :c}}}}}}}
-> {def recursiveAdd
 {lambda {:a :b :c}
  {if {null? :a}
   then {cons {cons :c nil} nil}
   else {cons {car {bitAdder {car :a} {car :b} :c}}
              {recursiveAdd {cdr :a} 
                            {cdr :b}
                            {cdr {bitAdder {car :a} {car :b} :c}}}}}}}

'{def bitAdder
 {lambda {:x :a :b}
  {cons {sum-bit :x :a :b} {carry-out :x :a :b}}}}
-> {def bitAdder
 {lambda {:x :a :b}
  {cons {sum-bit :x :a :b} {carry-out :x :a :b}}}}

'{def sum-bit
 {lambda {:x :a :b}
  {xor-gate :x {xor-gate :a :b}}}}
-> {def sum-bit
 {lambda {:x :a :b}
  {xor-gate :x {xor-gate :a :b}}}}

'{def carry-out
 {lambda {:x :a :b}
  {or-gate {and-gate :a :b}
           {or-gate {and-gate :x :a}
                    {and-gate :x :b}}}}}
-> {def carry-out
 {lambda {:x :a :b}
  {or-gate {and-gate :a :b}
           {or-gate {and-gate :x :a}
                    {and-gate :x :b}}}}}
°°°
'{def tail
 {lambda {:lst}
  {if {null? {cdr :lst}}
   then {car :lst}
   else {tail {cdr :lst}}}}}
-> {def tail
 {lambda {:lst}
  {if {null? {cdr :lst}}
   then {car :lst}
   else {tail {cdr :lst}}}}}

'{def rmtail
 {lambda {:lst}
  {if {null? {cdr :lst}}
   then nil
   else {cons {car :lst}
              {rmtail {cdr :lst}}}}}} 
-> {def rmtail
 {lambda {:lst}
  {if {null? {cdr :lst}}
   then nil
   else {cons {car :lst}
              {rmtail {cdr :lst}}}}}}  
°°°
}

_p Note the improvment: reversing inputs in the {b n-bit-adder} function, the {b tail} and {b rmtail} time consuming functions could be forgotten.

_h3 2.3) some helper functions

_p As a matter of choice in lambdatalk {b lists} are not implemented. Instead lambdatalk comes with {b pairs: cons, car, cdr}, and a set functions dealing with {b arrays: A.xxx}, with words, {b W.xxx} and with sentences {b S.xxx}. So we just have to build the {b null?} and the {b reverseList} functions.

{pre
'{def null?
 {lambda {:lst}
  {W.equal? :lst nil}}}
-> {def null?
 {lambda {:lst}
  {W.equal? :lst nil}}}

'{def reverseList
 {def reverseList.r
  {lambda {:a :b}
  {if {null? :a}
   then :b
   else {reverseList.r {cdr :a} {cons {car :a} :b}}}}}
 {lambda {:a}
  {reverseList.r :a nil}}}
-> {def reverseList
 {def reverseList.r
  {lambda {:a :b}
  {if {null? :a}
   then :b
   else {reverseList.r {cdr :a} {cons {car :a} :b}}}}}
 {lambda {:a}
  {reverseList.r :a nil}}}
}

_p Following the Scheme example {b n-bits} numbers are defined as lists, ie recursive pairs ending with the word {b nil}. Lists are manually built this way {b '{cons 1 {cons 0 {cons 1 ... nil}}}}, which is cumbersome. For readability we will define functions to write and read them as words, for instance {b 101110101...}, and finally to display them in a decimal format, for instance {b 10} is displayed as {b 2}.

{pre
'{def bin2list
 {lambda {:s}
  {if {= {W.length :s} 1}
   then {cons {W.first :s} nil}
   else {cons {W.first :s} {bin2list {W.rest :s}}}}}}
-> {def bin2list
 {lambda {:s}
  {if {= {W.length :s} 1}
   then {cons {W.first :s} nil}
   else {cons {W.first :s} {bin2list {W.rest :s}}}}}}

'{def list2bin
 {def list2bin.r
  {lambda {:l}
   {if {null? :l}
    then 
    else {car :l}{list2bin.r {cdr :l}}}}}
 {lambda {:l}
  {car {car :l}}: {list2bin.r {cdr :l}}}}
-> {def list2bin
 {def list2bin.r
  {lambda {:l}
   {if {null? :l}
    then 
    else {car :l}{list2bin.r {cdr :l}}}}}
 {lambda {:l}
  {car {car :l}}: {list2bin.r {cdr :l}}}}

'{def bin2dec
 {def bin2dec.r
  {lambda {:p :r}
   {if {A.empty? :p}
    then :r
    else {bin2dec.r {A.rest :p} {+ {A.first :p} {* 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} {+ {A.first :p} {* 2 :r}}}}}}
 {lambda {:p}
  {bin2dec.r {A.split :p} 0}}}
}

_h3 2.4) tests

{pre
°°°
'{list2bin {n-bit-adder {bin2list 00} {bin2list 00} }}
'{S.map 
 {lambda {:i} 
  {br}{list2bin {n-bit-adder {bin2list 00} {bin2list :i}}}}
 01 10 11}
-> 
{list2bin {n-bit-adder {bin2list 00} {bin2list 00} }} 
{S.map {lambda {:i} {br}{list2bin {n-bit-adder {bin2list 00} {bin2list :i}}}} 01 10 11}

'{list2bin {n-bit-adder {bin2list 000} {bin2list 000} }}
'{S.map
 {lambda {:i}
  {br}{list2bin {n-bit-adder {bin2list 000} {bin2list :i}}}}
 001 010 011 100 101 110 111}
->
{list2bin {n-bit-adder {bin2list 000} {bin2list 000} }}
{S.map
 {lambda {:i}
  {br}{list2bin {n-bit-adder {bin2list 000} {bin2list :i}}}}
 001 010 011 100 101 110 111}
°°°

'{list2bin {n-bit-adder {bin2list 00} {bin2list 00} }} -> {list2bin {n-bit-adder {bin2list 00} {bin2list 00} }}  // 0+0=0
'{list2bin {n-bit-adder {bin2list 00} {bin2list 01} }} -> {list2bin {n-bit-adder {bin2list 00} {bin2list 01} }}  // 0+1=1
'{list2bin {n-bit-adder {bin2list 01} {bin2list 01} }} -> {list2bin {n-bit-adder {bin2list 01} {bin2list 01} }}  // 1+1=2
'{list2bin {n-bit-adder {bin2list 10} {bin2list 01} }} -> {list2bin {n-bit-adder {bin2list 10} {bin2list 01} }}  // 2+1=3
'{list2bin {n-bit-adder {bin2list 11} {bin2list 11} }} -> {list2bin {n-bit-adder {bin2list 11} {bin2list 11} }}  // 3+3=6

'{list2bin
 {n-bit-adder
  {bin2list 1111111111111111}
  {bin2list 0000000000000001} }}
-> {list2bin
 {n-bit-adder
  {bin2list 1111111111111111}
  {bin2list 0000000000000001} }}

'{list2bin
 {n-bit-adder
  {bin2list 11111111111111111111111111111111}
  {bin2list 00000000000000000000000000000001} }} 
-> {list2bin
 {n-bit-adder
  {bin2list 11111111111111111111111111111111}
  {bin2list 00000000000000000000000000000001} }}

where

'{bin2dec 11111111111111111111111111111111} is {bin2dec 11111111111111111111111111111111} = 2{sup 32}-1

'{bin2dec 100000000000000000000000000000000} is {bin2dec 100000000000000000000000000000000} = 2{sup 32}

'{list2bin
 {n-bit-adder
  {bin2list 1111111111111111111111111111111111111111111111111111111111111111}
  {bin2list 0000000000000000000000000000000000000000000000000000000000000001} }}
-> {list2bin
 {n-bit-adder
  {bin2list 1111111111111111111111111111111111111111111111111111111111111111}
  {bin2list 0000000000000000000000000000000000000000000000000000000000000001} }}

which is {long_mult {pow 2 32} {pow 2 32}}, the exact value of {b 2{sup 64}}.
}

_p and so on ...

{prewrap 
'{list2bin
 {n-bit-adder
  {bin2list 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111}
  {bin2list 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001} }}
-> {list2bin
 {n-bit-adder
  {bin2list 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111}
  {bin2list 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001} }}

which is {long_mult {long_mult {pow 2 32} {pow 2 32}} {long_mult {pow 2 32} {pow 2 32}}}, the exact value of 2{sup 128}
}

_p {i This page is computed in about 55ms on my Powerbook Pro and Firefox.}

_p We have built the addition of two binary numbers of any size using three predicate functions, {b and, or, xor}, which could be implemented as pure lambda expressions, as it can seen in [[coding]] and in [[oops3]].

_p {i Alain Marty 2021/09/19}

_p [[HN|https://news.ycombinator.com/item?id=28581965]]

{style 
pre { box-shadow:0 0 8px #000; padding:5px; }
}