Iota and Jot

Chris Barker's universal iota combinator ι has the very simple λf.fSK structure defined here, using denotational semantics in terms of the lambda calculus,

${\displaystyle \iota$ :=\lambda f.((fS)K):=\lambda f.((f\lambda a.\lambda b.\lambda c.((ac)(bc)))\lambda d.\lambda e.d)}

(1)

From this, one can recover the usual SKI expressions, thus:

${\displaystyle I\,=\,(\iota \iota ),\;K\,=\,(\iota (\iota (\iota \iota ))),\;S\,=\,(\iota (\iota (\iota (\iota \iota ))))}$

(2)

Because of its minimalism, it has influenced research concerning Chaitin's constant.[2]

Iota is the LL(1) language that prefix orders trees of the aforementioned Universal iota ι combinator leafs, consed by function application ε,

iota = "1" | "0" iota iota

so that for example 0011011 denotes ${\displaystyle ((\iota \iota )(\iota \iota ))}$, whereas 0101011 denotes ${\displaystyle (\iota (\iota (\iota \iota )))}$.

Jot is the regular language consisting of all sequences of 0 and 1,

jot = "" | jot "0" | jot "1"

The semantics is given by translation to SKI expressions. The empty string denotes ${\displaystyle I}$, ${\displaystyle w0}$ denotes ${\displaystyle (([w]S)K)}$, where ${\displaystyle [w]}$ is the translation of ${\displaystyle w}$, and ${\displaystyle w1}$ denotes ${\displaystyle (S(K[w]))}$.

The point of the ${\displaystyle w1}$ case is that the translation satisfies ${\displaystyle (([w1]A)B)=([w](AB))}$ for arbitrary SKI terms ${\displaystyle A}$ and ${\displaystyle B}$. For example,

$${\displaystyle [w11100]=(([w1110]S)K)=(((([w111]S)K)S)K)=((([w11](SK))S)K)=(([w1]((SK)S))K)=([w](((SK)S)K))=([w]K)}$$

holds for arbitrary strings ${\displaystyle w}$. Similarly,

$${\displaystyle [w11111000]=(((((([w11111]S)K)S)K)S)K)=([w](((((SK)S)K)S)K))=([w]S)}$$

holds as well. These two examples are the base cases of the translation of arbitrary SKI terms to Jot given by Barker, making Jot a natural Gödel numbering of all algorithms.

Jot is connected to Iota by the fact that ${\displaystyle [w0]=(\iota [w])}$ and by using the same identities on SKI terms for obtaining the basic combinators ${\displaystyle K}$ and ${\displaystyle S}$.

The Zot and Positive Zot languages command Iota computations, from inputs to outputs by continuation-passing style, in syntax resembling Jot,

zot = pot | ""
pot = iot | pot iot
iot = "0" | "1"

where 1 produces the continuation ${\displaystyle \lambda cL.L(\lambda lR.R(\lambda r.c(lr)))}$, and 0 produces the continuation ${\displaystyle \lambda c.c\iota }$, and wi consumes the final input digit i by continuing through the continuation w.

• Lambda calculus
• Combinatory logic
• Binary combinatory logic
• SKI combinator calculus

• Official website
• Barker, Chris. "Iota and Jot: the simplest languages?". The Esoteric Programming Languages Webring. Archived from the original on 23 August 2016. Retrieved 13 August 2004.
• https://esolangs.org/wiki/Iota
• https://esolangs.org/wiki/Jot
• https://esolangs.org/wiki/Zot