Function Repository Resource:

# CombinatorEncode

Encode an SK combinator expression into a list of 0s and 1s

Contributed by: Daniel Sanchez
 ResourceFunction["CombinatorEncode"][comb] encodes the combinator expression comb (composed of the symbols s and k) as a list of 0s and 1s. ResourceFunction["CombinatorEncode"][comb, fmt] yields the encoding of comb in the format fmt.

## Details and Options

The encoding (as a binary string) of a combinator c is defined as:
 00 01 1
ResourceFunction["CombinatorEncode"][{comb1, comb2, }] returns the encoding of each combinator.
Valid formats fmt include "Color", List, Number and String.
ResourceFunction["CombinatorEncode"][expr,{fmt1, fmt2, }] returns a list of differently formatted encoded expressions.
ResourceFunction["CombinatorEncode"] has the following option:
 CombinatorSymbols Automatic which combinator symbols should be used instead of s and k
The value of CombinatorSymbols should be an Association of the form <|"CombinatorS"s1,"CombinatorK"k1|>, where the symbols s1 and k1 will be encoded instead of s and k, respectively.

## Examples

### Basic Examples (2)

Encode a combinator expression into a unique list of 1s and 0s:

 In[1]:=
 Out[1]=

Return the result of the encoding in various formats:

 In[2]:=
 Out[2]=

### Options (1)

#### CombinatorSymbols (1)

Specify which combinator symbols to encode instead of s and k:

 In[3]:=
 Out[3]=

### Applications (1)

Encode the five combinators that appear in Schönfinkel’s original paper:

 In[4]:=
 Out[4]=

### Properties and Relations (2)

Define a function for visualizing encodings:

Visualize states of a multiway combinator evaluation graph:

 In[5]:=
 Out[5]=

### Neat Examples (2)

Plot the contraction of the Ω term, which reduces to itself after three steps:

 In[6]:=
 Out[8]=

Plot the successive applications of the successor function s[b] starting with k[i] (0):

 In[9]:=
 Out[10]=

### Possible Issues (1)

Unknown symbols in the expression cannot be encoded:

 In[11]:=
 Out[11]=
 In[12]:=
 Out[12]=

Daniel Sanchez

## Version History

• 1.0.0 – 03 November 2020