lambdaway
::
oops4
7
|
list
|
login
|
load
|
|
{uncover https://figurinepop.com/public/agnes1_2.jpg 100 800 Agnes loves logic gates as lambda frozen cascades.} {uncover https://upload.wikimedia.org/wikipedia/commons/c/c0/74181aluschematic.png 100 500 ALU} _h2 [[oops]] | [[oops3]] | oops4 | [[oops5]] | [[oops6]] _h1 add, sub & Co _ul [[operations|http://guendouzi.u.g.f.unblog.fr/files/2013/11/operations.pdf]] _ul [[Principes de fonctionnement des ordinateurs|https://sites.uclouvain.be/LSINC1102/pfo/]] _ul [[uclouvain.be|https://sites.uclouvain.be/LSINC1102/pfo/_downloads/327ac02a8e63a0ee237c6ccbeeac2a2b/LSINC1102.pdf]] _ul [[Two's complement|https://en.wikipedia.org/wiki/Two%27s_complement]] _p Here we implement the addition and subtraction of binary numbers of any size as pure {b lambda expressions}, at the λ-calculus level. In other words we use lambdatalk supposed to be reduced to two special forms, {b lambda & def}, working on an empty dictionary. Numbers don't exist, we will use them exclusively for display purposes. _h2 1) basics _p Binary numbers are defined as lists of booleans. As everything else the two words {b TRUE} and {b FALSE} will be defined as functions. {pre '{def TRUE {lambda {:a :b} :a}} -> {def TRUE {lambda {:a :b} :a}} '{def FALSE {lambda {:a :b} :b}} -> {def FALSE {lambda {:a :b} :b}} '{def IF {lambda {:a :b :c} {:a :b :c}}} -> {def IF {lambda {:a :b :c} {:a :b :c}}} } _p We build 4 {b logic gates}, {b NOT, AND, OR, XOR} {pre '{def NOT {lambda {:a} {IF :a FALSE TRUE}}} -> {def NOT {lambda {:a} {IF :a FALSE TRUE}}} '{def AND {lambda {:a :b} {IF :a :b FALSE}}} -> {def AND {lambda {:a :b} {IF :a :b FALSE}}} '{def OR {lambda {:a :b} {IF :a TRUE :b}}} -> {def OR {lambda {:a :b} {IF :a TRUE :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}}}}} } _p Then we define a data structure aggregating two words, the {b PAIR}, coming with two accessors and a predicate function, {b NIL?}, returning {b TRUE} if the given input is {b NIL} else {b FALSE} if it is a {b PAIR}. {pre '{def PAIR {lambda {:a :b :c} {:c :a :b}}} -> {def PAIR {lambda {:a :b :c} {:c :a :b}}} '{def LEFT {lambda {:c} {:c TRUE}}} -> {def LEFT {lambda {:c} {:c TRUE}}} '{def RIGHT {lambda {:c} {:c FALSE}}} -> {def RIGHT {lambda {:c} {:c FALSE}}} '{def NIL {lambda {:a} TRUE}} -> {def NIL {lambda {:a} TRUE}} '{def NIL? {lambda {:c} {:c {lambda {:a :b} FALSE}}}} -> {def NIL? {lambda {:c} {:c {lambda {:a :b} FALSE}}}} } _p Binary numbers will be defined as lists of booleans, that is to say {b PAIR}s whose first term is {b TRUE} or {b FALSE}, and the second is a PAIR or {b NIL}. We will display a binary number as a sequence of its values, using {b L.DISP} {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}}} '{L.DISP {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}} -> {L.DISP {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}} } _p We will have to compute the length of a list, using decimal numbers {pre '{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.LENGTH {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}} -> {L.LENGTH {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}} } _p Sometimes lists have to be reversed with {b L.REV} {pre '{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}}} '{L.DISP {L.REV {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}}} -> {L.DISP {L.REV {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}}} } _h2 2) numbers as boolean lists _h3 2.1) adding two numbers _p With all the previous building blocks we can add two bits {pre '{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}}}} '{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}}}}} } _p and now we can add two equal length lists of bits {pre '{def B.ADD {lambda {:a :b} {{lambda {:c} {IF {LEFT {LEFT :c}} {PAIR {LEFT {LEFT :c}} {RIGHT :c}} {RIGHT :c}}} {B.ADD.sub :a :b}}}} -> {def B.ADD {lambda {:a :b} {{lambda {:c} {IF {LEFT {LEFT :c}} {PAIR {LEFT {LEFT :c}} {RIGHT :c}} {RIGHT :c}}} {B.ADD.sub :a :b}}}} '{def B.ADD.sub {lambda {:a :b} {L.REV {B.ADD.rec {L.REV :a} {L.REV :b} FALSE}}}} -> {def B.ADD.sub {lambda {:a :b} {L.REV {B.ADD.rec {L.REV :a} {L.REV :b} FALSE}}}} '{def B.ADD.rec {lambda {:a :b :c} {{IF {NIL? :a} {lambda {:a :b :c} {PAIR {PAIR :c NIL} NIL}} {lambda {:a :b :c} {PAIR {LEFT {B.ADD.bit {LEFT :a} {LEFT :b} :c}} {B.ADD.rec {RIGHT :a} {RIGHT :b} {RIGHT {B.ADD.bit {LEFT :a} {LEFT :b} :c} }}}} } :a :b :c}}} -> {def B.ADD.rec {lambda {:a :b :c} {{IF {OR {NIL? :a} {NIL? :b}} {lambda {:a :b :c} {PAIR {PAIR :c NIL} NIL}} {lambda {:a :b :c} {PAIR {LEFT {B.ADD.bit {LEFT :a} {LEFT :b} :c}} {B.ADD.rec {RIGHT :a} ;; {IF {NIL? {RIGHT :a}} FALSE :a} {RIGHT :b} ;; {IF {NIL? {RIGHT :b}} FALSE :b} {RIGHT {B.ADD.bit {LEFT :a} {LEFT :b} :c} }}}} } :a :b :c}}} '{L.DISP {B.ADD {PAIR FALSE {PAIR TRUE {PAIR TRUE {PAIR TRUE NIL}}}} // 0111 = 7 {PAIR FALSE {PAIR FALSE {PAIR TRUE {PAIR TRUE NIL}}}}}} // 0011 = 3 -> {L.DISP {B.ADD {PAIR FALSE {PAIR TRUE {PAIR TRUE {PAIR TRUE NIL}}}} {PAIR FALSE {PAIR FALSE {PAIR TRUE {PAIR TRUE NIL}}}}}} // 1010 = 10 } _h2 from booleans to bits _p Here we introduce a small set of lambdatalk functions to use the standard representation of binary numbers and to get their decimal representation. {pre '{def bin.new {def bin.new.sub {lambda {:n :b} {if {= :n 0} then :b else {bin.new.sub {- :n 1} 0:b}}}} {lambda {:n :b} {bin.new.sub {- :n {W.length :b}} :b}}} -> {def bin.new {def bin.new.sub {lambda {:n :b} {if {= :n 0} then :b else {bin.new.sub {- :n 1} 0:b}}}} {lambda {:n :b} {bin.new.sub {- :n {W.length :b}} :b}}} '{bin.new 16 1} -> {bin.new 16 1} '{def bin2bool // 011 -> (FALSE TRUE TRUE) {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 {:s} {bin2bool.r {S.replace _ by space in {S.replace 1 by TRUE_ in {S.replace 0 by FALSE_ in :s}}}}}} -> {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 {:s} {bin2bool.r {S.replace _ by space in {S.replace 1 by TRUE_ in {S.replace 0 by FALSE_ in :s}}}}}} '{L.DISP {bin2bool 0011}} -> {L.DISP {bin2bool 0011}} '{def bool2bin // (FALSE TRUE TRUE) -> 011 {lambda {:b} {S.replace \s by in {S.replace FALSE by 0 in {S.replace TRUE by 1 in {L.DISP :b}}}}}} -> {def bool2bin {lambda {:b} {S.replace \s by in {S.replace FALSE by 0 in {S.replace TRUE by 1 in {L.DISP :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 {:dec :w} {let { {:b {dec2bin.r :dec}} {:w :w} } {zpadd {- :w {W.length :b}}}:b}}} // '{dec2bin 7 4} -> {dec2bin 7 4} -> {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 {:dec :w} {let { {:b {dec2bin.r :dec}} {:w :w} } {zpadd {- :w {W.length :b}}}:b}}} '{def bin2dec // 011 -> 3 {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}}} '{L.DISP {bin2bool 0111}} -> {L.DISP {bin2bool 0111}} '{bool2bin {PAIR FALSE {PAIR FALSE {PAIR TRUE {PAIR TRUE NIL}}}}} -> {bool2bin {PAIR FALSE {PAIR FALSE {PAIR TRUE {PAIR TRUE NIL}}}}} '{bool2bin {B.ADD {bin2bool {bin.new 4 111}} {bin2bool {bin.new 4 11}}}} -> {bool2bin {B.ADD {bin2bool {bin.new 4 111}} {bin2bool {bin.new 4 11}}}} } _h3 ZERO & ONE _p Let's define {b ZERO} & {b ONE} as lists of 32 booleans {pre '{def N 32} -> {def N 32} '{def ZERO {bin2bool {bin.new {N} 0}}} -> {def ZERO {bin2bool {bin.new {N} 0}}} '{bool2bin {ZERO}} -> {bool2bin {ZERO}} '{def ONE {bin2bool {bin.new {N} 1}}} -> {def ONE {bin2bool {bin.new {N} 1}}} '{bool2bin {ONE}} -> {bool2bin {ONE}} } _h3 2.2) subtracting two numbers _p 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}. _p The two's complement is calculated by inverting the bits and adding one. {pre '{def B.SUB {def B.2CPL.rec {lambda {:a :b} {{IF {NIL? :a} {lambda {:a :b} {L.REV :b}} {lambda {:a :b} {B.OPP.rec {RIGHT :a} {PAIR {NOT {LEFT :a}} :b}}}} :a :b}}} {def B.2CPL {lambda {:a} {B.ADD {B.2CPL.rec :a NIL} {ONE} }}} {lambda {:a :b} {RIGHT {B.ADD :a {B.2CPL :b}}}}} -> {def B.SUB {def B.2CPL.rec {lambda {:a :b} {{IF {NIL? :a} {lambda {:a :b} {L.REV :b}} {lambda {:a :b} {B.2CPL.rec {RIGHT :a} {PAIR {NOT {LEFT :a}} :b}}}} :a :b}}} {def B.2CPL {lambda {:a} {B.ADD {B.2CPL.rec :a NIL} {ONE} }}} {lambda {:a :b} {RIGHT {B.ADD :a {B.2CPL :b}}}}} '{bool2bin {B.SUB {bin2bool {bin.new {N} 111}} // 7 {bin2bool {bin.new {N} 11}}}} // -3 -> {bool2bin {B.SUB {bin2bool {bin.new {N} 111}} {bin2bool {bin.new {N} 11}}}} // 4 } _h3 comparing two numbers _p ... {pre '{def B.ZERO? {def B.ZERO?.rec {lambda {:a :b} {{IF {NIL? :a} {lambda {:a :b} :b} {lambda {:a :b} {B.ZERO?.rec {RIGHT :a} {IF {LEFT :a} FALSE :b} }}} :a :b}}} {lambda {:a} {B.ZERO?.rec :a TRUE}}} -> {def B.ZERO? {def B.ZERO?.rec {lambda {:a :b} {{IF {NIL? :a} {lambda {:a :b} :b} {lambda {:a :b} {B.ZERO?.rec {RIGHT :a} {IF {LEFT :a} FALSE :b} }}} :a :b}}} {lambda {:a} {B.ZERO?.rec :a TRUE}}} '{B.ZERO? {ZERO}} -> {B.ZERO? {ZERO}} '{B.ZERO? {ONE}} -> {B.ZERO? {ONE}} } {pre '{def B.GT? {lambda {:a :b} ... }} '{def B.LT? {lambda {:a :b} ... }} '{def B.EQ? {lambda {:a :b} ... }} } _h3 multiplication {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.SUB :a {ONE}} :b {B.ADD :b :c}}}} :a :b :c}}} {lambda {:a :b} {B.MUL.rec :a :b {ZERO}}}} -> {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.SUB :a {ONE}} :b {B.ADD :b :c}}}} :a :b :c}}} {lambda {:a :b} {B.MUL.rec :a :b {ZERO}}}} '{bool2bin {B.MUL {bin2bool {bin.new {N} 10}} // 2 {bin2bool {bin.new {N} 100000}}}} // * 32 -> {bool2bin {B.MUL {bin2bool {bin.new {N} 10}} {bin2bool {bin.new {N} 100000}}}} // 64 } _h3 factorial {pre '{def B.FAC {lambda {:n} {{IF {B.ZERO? :n} {lambda {:n} {ONE}} {lambda {:n} {B.MUL :n {B.FAC {B.SUB :n {ONE}}}}}} :n}}} -> {def B.FAC {lambda {:n} {{IF {B.ZERO? :n} {lambda {:n} {ONE}} {lambda {:n} {B.MUL :n {B.FAC {B.SUB :n {ONE}}}}}} :n}}} '{bin2dec {bool2bin {B.FAC {bin2bool {bin.new {N} 1100}}}}} -> {* {S.serie 1 12}} (= {bin2dec 1100}!) } °°° _p With 32 bits we can compute in the interval [0,4294967295], ie {b 2{sup 32}-1} {pre '{bool2bin {B.ADD {bin2bool {bin.new 32 11111111111111111111111111111111}} {bin2bool {bin.new 32 1}}}} -> {bool2bin {B.ADD {bin2bool {bin.new 32 11111111111111111111111111111111}} {bin2bool {bin.new 32 1}}}} } °°° _p Wait & see. _p Alain Marty (2021/10/03)
lambdaway v.20211111