Function Repository Resource:

BinaryCombinator

Source Notebook

Perform bitwise operations through SK combinators

Contributed by: Austin Jiang

ResourceFunction["BinaryCombinator"][n, length]

converts the integer n into its representative combinator in binary form of length bits.

ResourceFunction["BinaryCombinator"][cmb]

converts the binary combinator cmb into the integer.

ResourceFunction["BinaryCombinator"][, cmb]

displays the binary combinator cmb as a string.

ResourceFunction["BinaryCombinator"][, length]

gives a combinator that can convert the binary combinator cmb of length bits into the Church numeral.

ResourceFunction["BinaryCombinator"][op, length]

gives a combinator corresponding to the operator op for binary numbers of length bits.

Details and Options

Church numerals are used in lambda calculus, which is a way of encoding primitive data types. ResourceFunction["ChurchCombinator"] is a related encoder.

In ResourceFunction["BinaryCombinator"][n, length], n must be a non-negative integer.

In ResourceFunction["BinaryCombinator"][n, length] and ResourceFunction["BinaryCombinator"][n, length], length must be a non-negative integer.

In ResourceFunction["BinaryCombinator"][op, length], op can be any of the operators BitNot, BitAnd, BitOr, BitXor, BitShiftLeft, BitShiftRight, Increment, Decrement, Plus, and Subtract.

BinaryCombinator can take the following option:

"SKGlyphs"

{CombinatorS,CombinatorK}

symbols used to specify combinators

Examples

Basic Examples (5)

Generate a combinator that represent 5 in binary form:

In[1]:=

Out[1]=

Convert the combinator of 5 in binary form back into an integer:

In[2]:=

Out[2]=

Display the combinator of 5 in binary form as a string:

In[3]:=

Out[3]=

Convert the combinator of 5 in binary form into the Church numeral:

In[4]:=

Out[4]=

In[5]:=

$%[a][b] //. {CombinatorS[x_][y_][z_] -> x[z][y[z]], CombinatorK[x_][y_] -> x}$

Out[5]=

Apply the operation BitNot to 5:

In[6]:=

Out[6]=

In[7]:=

Out[7]=

Scope (10)

Bitwise-not a binary combinator:

In[8]:=

Out[8]=

Bitwise-and two binary combinators:

In[9]:=

Out[9]=

Bitwise-or two binary combinators:

In[10]:=

Out[10]=

Bitwise-xor two binary combinators:

In[11]:=

Out[11]=

Left-shift a binary combinator:

In[12]:=

Out[12]=

Right-shift a binary combinator:

In[13]:=

Out[13]=

Increment a binary combinator:

In[14]:=

Out[14]=

Decrement a binary combinator:

In[15]:=

Out[15]=

Plus two binary combinators:

In[16]:=

Out[16]=

Subtract a binary combinator from another:

In[17]:=

Out[17]=

Options (2)

SKGlyphs (2)

Compute a binary combinator using the default glyphs S and K:

In[18]:=

Out[18]=

Change the glyphs:

In[19]:=

Out[19]=

Possible Issues (3)

The number of bits for all binary combinators in an evaluation should be the same:

In[20]:=

Out[20]=

If the number of bits of a binary combinator is too small, the result may be incorrect, wrapping around and starting over (mod 2^length):

In[21]:=

Out[21]=

Negative numbers resulting from subtraction will also wrap around:

In[22]:=

Out[22]=

Publisher

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

1.0.0 – 21 August 2024

Related Resources

Author Notes

This submission is an outcome of the author's 2024 WSRP project.

License Information

This work is licensed under a Creative Commons Attribution 4.0 International License