lambdaway :: oops6

2 | list | login |load

| |

_h2 λ-calculus using binary numbers of variable length

{{block}
{uncover https://figurinepop.com/public/agnes1_2.jpg 100 800 Agnes loves logic gates as frozen cascades of lambdas.} 
_h2 introduction

{pre {@ style="text-align:center; box-shadow:0 0 8px #000; padding:10px;"}
fibonacci(100) = 354224848179261915075
factorial(22) = 1124000727777607680000
}
 
_p The goal is to build some efficient binary arithmetic at the {b λ-calculus} level, that is to say using a reduced set of lambdatalk functionalities, two special forms, {b lambda} and {b def}, no data or control structures - {b if then else} doesn't exist - and an empty dictionary, at least for the main algorithms. 
_p Note that in lambdatalk lambdas are not closures, have no free variables, are independant of any lexical context and are nothing but combinatory replacement machines. Everything can be reduced to an {b IIFE}, an Immediately Invoked Function Expression, {b '{{λ {w} x} x}}, which inevitably brings to mind the CPU's logic gates.

_h3 content

_ul introduction
_ul basics
_ul20 booleans: #1, #0, IF
_ul20 logic gates: NOT, AND, OR, XOR
_ul20 pairs: PAIR, LEFT, RIGHT
_ul20 lists: L.DISP, L.REV

_ul numbers
_ul20 bin2bool, bool2bin
_ul20 dec2bin, bin2ded
_ul20 ZERO, ONE, B.ZERO?
_ul20 B.SHFTL, B.SHFTR

_ul addition
_ul20 one bit: B.ADD.bit
_ul20 n bits: B.ADD

_ul subtraction
_ul20 B.SUB
_ul20 B.SUCC, B.PRED
_ul20 B.LT?, B.GT?, B.EQ?
_ul20 B.FIB

_ul multiplication
_ul20 B.MUL
_ul20 B.FAC

_ul division
_ul20 B.DIVMOD
_ul20 division with shifts
_ul20 B.GCD

_ul conclusion
_ul references

_p This page is similar to [[oops7]] where binary numbers are of {b constant length}. See also [[binary_digit]] and [[lambdacode5]] if you need {b closures}. And also [[liquid computers|https://royalsocietypublishing.org/doi/10.1098/rstb.2018.0372]] to discover logic gates out of silicium...
_p [[HN|https://news.ycombinator.com/item?id=30485787]]
}

{{block}
{uncover https://mindsarentmagic.files.wordpress.com/2020/02/l_1-2.png 100 300 Binary Lambda Calculus and Combinatory Logic}
 
_h2 basics

_p Here is a reduced set of lambdatalk functions built exclusively on {b lambdas} and {b defs}. See [[coding]] for details about lambdas, booleans, pairs and lists.

_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}}}

'{IF #1 James Bond}
-> {IF #1 James Bond}
'{IF #0 James Bond}
-> {IF #0 James Bond}
}

_h3 logic gates

{pre
'{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}}}}}

'{AND #1 #1} '{AND #0 #1}   -> {AND #1 #1} {AND #0 #1}
'{AND #1 #0} '{AND #0 #0}   -> {AND #1 #0} {AND #0 #0}

'{OR #1 #1} '{OR #0 #1}     -> {OR #1 #1} {OR #0 #1}
'{OR #1 #0} '{OR #0 #0}     -> {OR #1 #0} {OR #0 #0}

'{XOR #1 #1} '{XOR #0 #1}   -> {XOR #1 #1} {XOR #0 #1}
'{XOR #1 #0} '{XOR #0 #0}   -> {XOR #1 #0} {XOR #0 #0}
}

_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 {lambda {:a} #1}}
-> {def NIL {lambda {:a} #1}}
'{def NIL? {lambda {:c} {:c {lambda {:a :b} #0}}}}
-> {def NIL? {lambda {:c} {:c {lambda {:a :b} #0}}}}

'{def JB {PAIR James Bond}}
-> {def JB {PAIR James Bond}}
'{LEFT {JB}}
-> {LEFT {JB}}
'{RIGHT {JB}}
-> {RIGHT {JB}}

'{NIL? NIL}
-> {NIL? NIL}
'{NIL? {JB}}
-> {NIL? {JB}}
}

{blockquote {@ style="transform:rotate(-2.5deg)"}
_h3 before going further ...
_p ... it's important to understand how this structure works. Let's analyze the evaluation of the {b '{LEFT {JB}}} application, replacing the names with their lambda-definitions

{pre
0: '{LEFT {JB}}
1: '{{lambda {:c} {:c #1}}
                 {PAIR James Bond}}
2: '{{lambda {:c} {:c {lambda {:a :b} :a}}} 
                 {{lambda {:a :b :c} {:c :a :b}}
                                     James Bond}}
3: '{{{lambda {:a :b :c} {:c :a :b}} James Bond}
                                    {lambda {:a :b} :a}} 
4: '{{{lambda {:c} {:c James Bond}}} 
                  {lambda {:a :b} :a}}     
5: '{{lambda {:a :b} :a} James Bond} 
6: James 
}

_p The key passage is in {b the partial application} from line 3 to line 4:
{pre 
'{{lambda {:a :b :c} {:c :a :b}} James Bond} 
-> '{lambda {:c} {:c James Bond}}
}
_p The function expects three values but only gets two. It stores them in its body and returns a new function waiting for the missing value. That's all!
_p Lambdatalk does not know closures but accepts {b partial application} natively, a powerful property used extensively in the following.
}

_h3 lists

_p A list is a pair whose first term is a {b word} and the second is a pair or {b NIL}. We will have to reverse and display lists.

{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 HI
 {PAIR hello
 {PAIR brave
 {PAIR new
 {PAIR world NIL}}}}}
-> {def HI {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}}

'{L.DISP {HI}}
-> {L.DISP {HI}}

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

}

{{block}
{uncover https://mindsarentmagic.files.wordpress.com/2020/02/l_1-2.png 100 300 Binary Lambda Calculus and Combinatory Logic}

_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}.

{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}}
'{NIL? {FIVE}}
-> {NIL? {FIVE}}
}
_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 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}
}

_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} {L.REV {bin2bool {dec2bin :n :m}}}}}

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

'{L.DISP {dec2bool 4 5}}
-> {L.DISP {dec2bool 4 5}}   // which  is 0101 reversed

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

_p {b Notes:} 
_ul 1) The {b dec2bin} function translates a decimal number into a binary one; this function waits for two values, the number of bits choosed to store the number and the decimal number.
_ul 2) With {code '{long_add {A.first :p} {long_mult 2 :r}}} the {b bin2dec} function accepts big numbers.
_ul 3) except for the input and output functions using the plain lambdatalk, the core of the operations will always be at the lambda-calculus level.

_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.

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

'{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} #0 :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} {B.ZERO?.rec {RIGHT :a} {IF {LEFT :a} #0 :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}}  
}

_h3 shiftleft & shiftright

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

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

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

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

}
}

{{block}
{uncover https://mindsarentmagic.files.wordpress.com/2020/02/l_1-2.png 100 300 Binary Lambda Calculus and Combinatory Logic}
 
_h2 addition

_p See an improvement in this recent paper: [[tromp]].

_p The addition of two bits {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}}}}
}

_p So

{pre
{quote 
{LEFT {B.ADD.bit #0 #0 #0}}
      {RIGHT {B.ADD.bit #0 #0 #0}}
{LEFT {B.ADD.bit #0 #0 #1}}
      {RIGHT {B.ADD.bit #0 #0 #1}}
{LEFT {B.ADD.bit #0 #1 #0}}
      {RIGHT {B.ADD.bit #0 #1 #0}}
{LEFT {B.ADD.bit #0 #1 #1}}
      {RIGHT {B.ADD.bit #0 #1 #1}}
}->
 s  x     a+b(x)    s(x)
{LEFT {B.ADD.bit #0 #0 #0}} {RIGHT {B.ADD.bit #0 #0 #0}}  // 0+0(0) -> 0(0)
{LEFT {B.ADD.bit #0 #0 #1}} {RIGHT {B.ADD.bit #0 #0 #1}}  // 0+1(0) -> 1(0)
{LEFT {B.ADD.bit #0 #1 #0}} {RIGHT {B.ADD.bit #0 #1 #0}}  // 1+0(0) -> 1(0)
{LEFT {B.ADD.bit #0 #1 #1}} {RIGHT {B.ADD.bit #0 #1 #1}}  // 0+0(0) -> 0(1)
}

_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}
  {B.ADD.rec #0 :a :b }}}

'{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}
}

_h3 successor & predecessor

_p Computing the successor and the predecessor of a number can be viewed as special cases of adding and subtracting two numbers. Here is a more efficient way to compute {b n+1} and {b n-1}, using the {b B.ADD} function slightly modified.

{pre

'{def B.SUCC

{def B.SUCC.rec
  {lambda {:a :c}
   {{IF {NIL? :a}
    {lambda {:a :c} {PAIR :c NIL} }
    {lambda {:a :c}
     {{lambda {:a :c}
       {PAIR {LEFT :c} {B.SUCC.rec {RIGHT :a} {RIGHT :c}}}
      } :a {B.ADD.bit {LEFT :a} #0 :c}} }} :a :c}}}

{lambda {:a}
   {L.REV {RIGHT {L.REV {B.SUCC.rec :a #1}}}}}}
-> {def B.SUCC
 {def B.SUCC.rec
  {lambda {:a :c}
   {{IF {NIL? :a}
    {lambda {:a :c} {PAIR :c NIL} }
    {lambda {:a :c}
     {{lambda {:a :c}
       {PAIR {LEFT :c} {B.SUCC.rec {RIGHT :a} {RIGHT :c}}}
      } :a {B.ADD.bit {LEFT :a} #0 :c}} }} :a :c}}} 
 {lambda {:a}
   {L.REV {RIGHT {L.REV {B.SUCC.rec :a #1}}}}}}

'{bool2dec {B.SUCC {dec2bool 8 7}}}
-> {bool2dec {B.SUCC {dec2bool 8 7}}}

'{def B.PRED

{def B.PRED.rec
  {lambda {:a :c}
   {{IF {NIL? :a}
    {lambda {:a :c} {PAIR :c NIL} }
    {lambda {:a :c}
     {{lambda {:a :c} {PAIR {LEFT :c}
                            {B.PRED.rec {RIGHT :a} {RIGHT :c}}}
      } :a {B.ADD.bit {LEFT :a} #1 :c}} }} :a :c}}}

{lambda {:a}
   {L.REV {RIGHT {L.REV {B.PRED.rec :a #0}}}}}}  
-> {def B.PRED
 {def B.PRED.rec
  {lambda {:a :c}
   {{IF {NIL? :a}
    {lambda {:a :c} {PAIR :c NIL} }
    {lambda {:a :c}
     {{lambda {:a :c}
       {PAIR {LEFT :c} {B.PRED.rec {RIGHT :a} {RIGHT :c}}}
      } :a {B.ADD.bit {LEFT :a} #1 :c}} }} :a :c}}} 
 {lambda {:a}
   {L.REV {RIGHT {L.REV {B.PRED.rec :a #0}}}}}}

'{bool2dec {B.PRED {dec2bool 8 7}}}
-> {bool2dec {B.PRED {dec2bool 8 7}}}

'{bool2dec {B.PRED {dec2bool 128 4294967296}}}
-> 4294967295    // 2{sup 32}-1
}

} ;; block

{{block}
{uncover https://mindsarentmagic.files.wordpress.com/2020/02/l_1-2.png 100 300 Binary Lambda Calculus and Combinatory Logic}
 
_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}. 
_p The two's complement is calculated by inverting the bits and adding one.

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

'{def B.SUB
 {lambda {:n :a :b}
  {RIGHT
   {L.REV {B.ADD {L.REV :a} 
          {B.ADD {B.invert :b NIL} {ONE :n} }}}}}}
-> {def B.SUB
 {lambda {:n :a :b}
  {RIGHT
   {L.REV {B.ADD {L.REV :a} 
          {B.ADD {B.invert :b NIL} {ONE :n} }}}}}}

'{bool2dec {B.SUB 4 {dec2bool 4 7} {dec2bool 4 3}}}
-> {bool2dec {B.SUB 4 {dec2bool 4 7} {dec2bool 4 3}}}

}

_h3 lesser, greater or equal

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

{pre
'{def B.LT?
 {lambda {:n :a :b}
  {LEFT {B.SUB :n {L.REV :a} {L.REV :b}}}}}
-> {def B.LT? {lambda {:n :a :b} {LEFT {B.SUB :n {L.REV :a} {L.REV :b}}}}}
'{def B.GT?
 {lambda {:n :a :b}
  {LEFT {B.SUB :n {L.REV :b} {L.REV :a}}}}}
-> {def B.GT? {lambda {:n :a :b} {LEFT {B.SUB :n {L.REV :b} {L.REV :a}}}}}
'{def B.EQ?
 {lambda {:n :a :b}
  {B.ZERO? {B.SUB :n {L.REV :a} {L.REV :b}}}}}
-> {def B.EQ? {lambda {:n :a :b} {B.ZERO? {B.SUB :n {L.REV :a} {L.REV :b}}}}}

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

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

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

_h3 fibonacci

_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}

{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 {:n :m}
  {B.FIB.rec {ZERO :n} {ONE :n} :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 {:n :m}
  {B.FIB.rec {ZERO :n} {ONE :n} :m}
}}

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

} ;; block

{{block}
{uncover https://mindsarentmagic.files.wordpress.com/2020/02/l_1-2.png 100 300 Binary Lambda Calculus and Combinatory Logic}
 
_h2 multiplication

_p The multiplication could be {i naïvely} defined as a sequence of additions.

{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.PRED :a} :b {B.ADD :b :c}}}} :a :b :c}}}
 {lambda {:a :b}
  {B.MUL.rec :a :b {ZERO}}}}
}

_p This is a better alternative using shifts only.

{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

}}

{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 {:n :a :b}
  {B.MUL.rec :a :b {ZERO :n}}}}
-> {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 {:n :a :b}
  {B.MUL.rec :a :b {ZERO :n}}}}

'{bool2dec
 {B.MUL 64 {dec2bool 64 5830}
           {dec2bool 64 23958233}}}
-> 139676498390    
}

_h3 factorial

_p The {b factorial} of a number is defined as {b fac(n) = n*fac(n-1) with fac(0) = 1}

{prewrap
'{def B.FAC
 {lambda {:n :i}
  {{IF {B.ZERO? :i}
   {lambda {:n :i} {ONE :n}}
   {lambda {:n :i}
           {B.MUL :n :i {B.FAC :n {B.PRED :i}}}}} :n :i}}}  
-> {def B.FAC
  {lambda {:n :i}
   {{IF {B.ZERO? :i}
    {lambda {:n :i} {ONE :n}}
    {lambda {:n :i}
     {B.MUL :n :i {B.FAC :n {B.PRED :i}}}}} :n :i}}}

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

'{bool2dec {B.FAC 128 {dec2bool 128 22}}}
-> 1124000727777607680000
}

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

_p And so, binary based λ-calculus can deal with big numbers.

}

{{block}
{uncover https://mindsarentmagic.files.wordpress.com/2020/02/l_1-2.png 100 300 Binary Lambda Calculus and Combinatory Logic}
 
_h2 division

_p This is the basic process

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

'{/ 7 2} = {/ 7 2} 
'{// 7 2} = ({floor {/ 7 2}},{% 7 2})

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!
}

_p and the translation

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

_p The result is the pair {b (q,r)}. Testing

{pre
'{let { {:divmod {B.DIVMOD 16 {dec2bool 16 123}
                             {dec2bool 16 12}}}
     } ({bool2dec {LEFT :divmod}},
        {bool2dec {RIGHT :divmod}})
}
-> (10,3)
}

_p We can also split {b B.DIVMOD} into {b B.DIV} and {b B.MOD}

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

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

_p Testing

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

_h3 gcd

_p As an application we compute the greater commun divisor of two numbers

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

}

_h3 alternative: division using shifts

_p Using {b shifts} should be better.

{pre {@ style="transform:rotate(-2deg); color:#ccc; white-space:pre-wrap;"} 
Following [[compoasso.free.fr/primelistweb|http://compoasso.free.fr/primelistweb/page/prime/euclide.php]]

var euclide = function(a,b) '{

var r = a,
      q = 0,
      n = 0,
      x = b;

while (x <= a) {
    x = (x << 1);
    n++;
  }

while (n > 0) {
    x = (x >> 1);
    n--;
    q = (q << 1);
    if (r >= x) {
      r = r - x;
      q++;
    }
  }

return [q,r];
}

translated into lambdatalk

'{def euclide
{def euclide.init
 {lambda {:a :x :n}
  {if {<= :x :a}
   then {euclide.init :a {shiftl :x 1} {+ :n 1}}
   else {cons :n :x}}}}

{def euclide.loop
 {lambda {:n :x :q :r}
  {if {> :n 0}
   then {{lambda {:n :x :q :r}
             {euclide.loop :n :x {if {>= :r :x} 
                                  then {+ :q 1} {- :r :x} 
                                  else :q :r}}
         } {- :n 1} {shiftr :x 1} {shiftl :q 1} :r}
   else {cons :q :r} }}}

{lambda {:a :b}  
  {{lambda {:xn :q :r}
           {euclide.loop {car :xn} {cdr :xn} :q :r}
   } {euclide.init :a :b 0} 0 :a}}}
-> {def euclide
{def euclide.init
 {lambda {:a :x :n}
  {if {<= :x :a}
   then {euclide.init :a {shiftl :x 1} {+ :n 1}}
   else {cons :n :x}}}}

{def euclide.loop
 {lambda {:n :x :q :r}
  {if {> :n 0}
   then {{lambda {:n :x :q :r}
                 {euclide.loop :n :x {if {>= :r :x} 
                                      then {+ :q 1} {- :r :x} 
                                      else :q :r}}
         } {- :n 1} {shiftr :x 1} {shiftl :q 1} :r}
   else {cons :q :r} }}}

{lambda {:a :b}  
  {{lambda {:xn :q :r}
           {euclide.loop {car :xn} {cdr :xn} :q :r}
   } {euclide.init :a :b 0} 0 :a}}}
 
'{euclide 218 6}
-> {euclide 218 6}

'{let { {:e {euclide 218 6}}
     } 218 = 6*{car :e}+{cdr :e}
}
-> {let { {:e {euclide 218 6}}
        } 218 = 6*{car :e}+{cdr :e}
}

'{let { {:e {euclide 123456789 123456}}
        } 123456789 = 123456*{car :e}+{cdr :e}
}
-> {let { {:e {euclide 123456789 123456}}
        } 123456789 = 123456*{car :e}+{cdr :e}
}
}

_p Waiting for final translation using binary numbers ...

{pre

'{def DIV
{def DIV.init
 {lambda {:a :x :n}
  {{IF {B.LT? 32 :x :a}
   {lambda {:a :x :n} {DIV.init :a {B.SHFTL :x} {B.SUCC :n}} }
   {lambda {:a :x :n} {PAIR :n :x}}}
            :a :x :n}}}

{def DIV.loop
 {lambda {:n :x :q :r}
  {{IF {B.GT? 32 :n {ZERO 32}}
   {lambda {:n :x :q :r} 
    {{lambda {:n :x :q :r}
      {DIV.loop :n :x 
     {{IF {B.GT? 32 :r :x} 
      {lambda {:q :r :x} {B.SUCC :q} {B.SUB 32 :r :x}  }
      {lambda {:q :r :x} :q :r} }}
               :q :r :x}
         } {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}
           {DIV.loop {LEFT :xn} {RIGHT :xn} :q :r}
   } {DIV.init :a :b {ZERO 32}} {ZERO 32} :a}}}
-> {def DIV
{def DIV.init
 {lambda {:a :x :n}
  {{IF {B.LT? 32 :x :a}
   {lambda {:a :x :n} {DIV.init :a {B.SHFTL :x} {B.SUCC :n}} }
   {lambda {:a :x :n} {PAIR :n :x}}}
            :a :x :n}}}

{lambda {:a :b}  
  {{lambda {:xn :q :r}
           {DIV.loop {LEFT :xn} {RIGHT :xn} :q :r}
   } {DIV.init :a :b {ZERO 32}} {ZERO 32} :a}}}

'{bool2dec {LEFT {DIV {dec2bool 32 218} {dec2bool 32 6}}}}
-> ???
}

} ;; block

{{block}
{uncover http://epsilonwiki.free.fr/epsilonwiki/data/2CV_boule_et_bill.jpg 100 500 KISS}

_h2 conclusion

_p Thanks to the natural numbers binary implementation, it becomes possible at the lambda-calculus level, to break the glass ceiling quickly found using the Church numerals or naïvely representing numbers as simple lists of dots. 
_p Currently we have built a small set of operators working on binary numbers of variable length :

{pre °°
{bool2bin
 {PAIR #0
 {PAIR #1
 {PAIR #1
 {PAIR #1 NIL}}}}} 
-> 0111

{bin2bool 0111} 
-> {PAIR #0 {PAIR #1 {PAIR #1 {PAIR #1 NIL}}}}

{bin2dec 0111} -> 7

{dec2bin 4 7}  -> 0111

====

{ZERO N}    -> {PAIR #0 {PAIR ... {PAIR #0 NIL} ...}}

{ONE N}     -> {PAIR #0 {PAIR ... {PAIR #1 NIL} ...}}

{B.ZERO? a} -> #1 if a = NIL else #0

{B.LT? N {dec2bool N a}
         {dec2bool N b}} -> #1 if a < b else #0

{B.GT? N {dec2bool N a}
         {dec2bool N b}} -> #1 if a > b else #0

{B.EQ? N {dec2bool N a}
         {dec2bool N b}} -> #1 if a = b else #0

====

{bool2dec {B.SHFTL {dec2bool N a}}}    -> a*2

{bool2dec {B.SHFTR {dec2bool N a}}}    -> a/2

{bool2dec {B.SUCC {dec2bool N a}}}     -> a+1

{bool2dec {B.PRED {dec2bool N a}}}     -> a-1

{bool2dec {B.ADD {dec2bool N a}
                 {dec2bool N b}}}      -> a+b

{bool2dec {B.SUB N {dec2bool N a}
                   {dec2bool N b}}}    -> a-b

{bool2dec {B.MUL N {dec2bool N a}
                   {dec2bool N b}}}    -> a*b

{B.DIVMOD N {dec2bool N a}
            {dec2bool N b}}            -> (q,r) with a=b*q+r

{bool2dec {B.GCD N {dec2bool N a}
                   {dec2bool N b}}}    -> gcd(a,b)

====

{bool2dec {B.FIB N {dec2bool N a}}}    -> fib(a-1)+fib(a-2)
{bool2dec {B.FAC N {dec2bool N a}}}    -> a*(a-1)*...*2*1

°°}

_p More to come.

_p Alain Marty | created: 2021/10/08, last update: 2024/09/26
}

{{block}
{uncover http://lambdaway.free.fr/workshop/data/dancing_minions.gif 100 300 ¡Bananas y lambada!}

_h2 references

_ul [[uclouvain.be|https://sites.uclouvain.be/LSINC1102/pfo/_downloads/327ac02a8e63a0ee237c6ccbeeac2a2b/LSINC1102.pdf]], following "The Elements of Computing Systems"
_ul [[BLC|https://tromp.github.io/cl/Binary_lambda_calculus.html]], discovered on 2021/10/05, but too hard for me
_ul [[https://arxiv.org/abs/1401.0379|https://arxiv.org/abs/1401.0379]]
_ul [[encoding-binary-numerals-in-lambda-calculus|https://stackoverflow.com/questions/18399188/encoding-binary-numerals-in-lambda-calculus]]
_ul [[TrompJohn.Paper|https://drops.dagstuhl.de/opus/volltexte/2006/628/pdf/06051.TrompJohn.Paper.628.pdf]]
_ul [[https://csvoss.com/circuit-notation-lambda-calculus|https://csvoss.com/circuit-notation-lambda-calculus]]
_ul [[https://tromp.github.io/cl/diagrams.html|https://tromp.github.io/cl/diagrams.html]]
_ul [[https://blog.segger.com/algorithms-for-division-part-1/|https://blog.segger.com/algorithms-for-division-part-1/]]
_ul [[liquid computers|https://royalsocietypublishing.org/doi/10.1098/rstb.2018.0372]]
_ul [[Justine Tunney|https://justine.lol/]]
_ul [[evolution|https://erkin.party/blog/200715/evolution/]]
_ul [[HN|https://news.ycombinator.com/item?id=41207784]], [[HN|https://news.ycombinator.com/item?id=41656518]]
_ul ...

_p and, thanks to John Tromp, a graphical representation of logic gates as λ-terms compositions.

<table cellspacing=16>
<tr> <td>term</td><td>definition</td> <td>diagram</td> <td>alternative</td> </tr>
<tr> <td>I/1</td> <td> λx.x</td>
  <td><IMG SRC="{PATH}/I.gif"><td> </tr>
<tr> <td>K/#1</td> <td> λx.λy.x</td>
  <td><IMG SRC="{PATH}/K.gif"><td> </tr>
<tr> <td>#0/0</td> <td> λx.λy.y</td>
  <td><IMG SRC="{PATH}/#0.gif"><td> </tr>
<tr> <td>S</td> <td> λx.λy.λz.(x z)(y z)</td>
  <td><IMG SRC="{PATH}/S.gif"></td>
  <td><IMG SRC="{PATH}/S.alt.gif"></td> </tr>
<tr> <td>Y</td> <td> λf.(λx.x x)(λx.f(x x))</td>
  <td><IMG SRC="{PATH}/Y.gif"></td>
  <td><IMG SRC="{PATH}/Y.alt.gif"></td> </tr>
<tr> <td>2</td> <td> λf.λx.f(f x)</td>
  <td><IMG SRC="{PATH}/2.gif"></td>
  <td><IMG SRC="{PATH}/2.alt.gif"></td> </tr>
<tr> <td>3</td> <td> λf.λx.f(f(f x))</td>
  <td><IMG SRC="{PATH}/3.gif"></td>
  <td><IMG SRC="{PATH}/3.alt.gif"></td> </tr>
<tr> <td>4</td> <td> λf.λx.f(f(f(f x)))</td>
  <td><IMG SRC="{PATH}/4.gif"></td>
  <td><IMG SRC="{PATH}/4.alt.gif"></td> </tr>
<tr> <td>pred</td> <td> λn.λf.λx.n(λg.λh.h(g f))(λu.x)(λu.u)</td>
  <td><IMG SRC="{PATH}/pred.gif"></td>
  <td><IMG SRC="{PATH}/pred.alt.gif"></td> </tr>
<tr> <td>fac</td> <td> λn.λf.n(λf.λn.n(f(λf.λx.n f(f x))))(λx.f)(λx.x)</td>
  <td><IMG SRC="{PATH}/fac.gif"></td>
  <td><IMG SRC="{PATH}/fac.alt.gif"></td> </tr>
<tr> <td>fib</td> <td> λn.λf.n(λc.λa.λb.c b(λx.a (b x)))(λx.λy.x)(λx.x)f</td>
  <td><IMG SRC="{PATH}/fib.gif"></td>
  <td><IMG SRC="{PATH}/fib.alt.gif"></td> </tr>
<tr> <td>Ω</td> <td> (λx.x x)(λx.x x)</td>
  <td><IMG SRC="{PATH}/Omega.gif"></td>
  <td><IMG SRC="{PATH}/Omega.alt.gif"></td> </tr>
</table>

}

{{hide}
{def block 
  div {@ style="display:inline-block; width:570px; vertical-align:top; padding:5px; "}}
{def PATH https://tromp.github.io/img/cl}
}

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

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

{script 
LAMBDATALK.DICT['shiftl'] = function () {
  var args = arguments[0].trim().split(' ');
  return args[0] << args[1]
};
LAMBDATALK.DICT['shiftr'] = function () {
  var args = arguments[0].trim().split(' ');
  return args[0] >> args[1]
};
LAMBDATALK.DICT['even'] = function () {
  var args = arguments[0].trim(); //.split(' ');
  return /^-?\d*[02468]$/.test(args)
};
LAMBDATALK.DICT['odd'] = function () {
  var args = arguments[0].trim(); //.split(' ');
  return /^-?\d*[13579]$/.test(args)
};
}