Iota and Jot

From HandWiki
Short description: Esoteric programming languages
Iota, Jot, Zot
ParadigmsFormal language, Turing tarpit, esoteric
Designed byChris Barker
DeveloperChris Barker
First appeared2001; 23 years ago (2001)
Final release
2001 / 2001; 23 years ago (2001)
Implementation languageScheme, JavaScript
PlatformScheme interpreter, Web browser (JavaScript)
LicensePublic domain
Websitewww.nyu.edu/projects/barker
Influenced
Zot

In formal language theory and computer science, Iota and Jot (from Greek iota ι, Hebrew yodh י, the smallest letters in those two alphabets) are languages, extremely minimalist formal systems, designed to be even simpler than other more popular alternatives, such as the lambda calculus and SKI combinator calculus. Thus, they can also be considered minimalist computer programming languages, or Turing tarpits, esoteric programming languages designed to be as small as possible but still Turing-complete. Both systems use only two symbols and involve only two operations. Both were created by professor of linguistics Chris Barker in 2001. Zot (2002) is a successor to Iota that supports input and output.[1]

Note that this article uses Backus-Naur form to describe syntax.

Universal iota

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

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

 

 

 

 

(1)

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

[math]\displaystyle{ I\, =\, (\iota \iota),\; K\, =\, (\iota(\iota(\iota\iota))), \;S\, =\, (\iota(\iota(\iota(\iota\iota)))) }[/math]

 

 

 

 

(2)

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

Iota

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 [math]\displaystyle{ ((\iota\iota)(\iota\iota)) }[/math], whereas 0101011 denotes [math]\displaystyle{ (\iota(\iota(\iota\iota))) }[/math].

Jot

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 [math]\displaystyle{ I }[/math], [math]\displaystyle{ w0 }[/math] denotes [math]\displaystyle{ (([w]S)K) }[/math], where [math]\displaystyle{ [w] }[/math] is the translation of [math]\displaystyle{ w }[/math], and [math]\displaystyle{ w1 }[/math] denotes [math]\displaystyle{ (S(K[w])) }[/math].

The point of the [math]\displaystyle{ w1 }[/math] case is that the translation satisfies [math]\displaystyle{ (([w1]A)B) = ([w](A B)) }[/math] for arbitrary SKI terms [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math]. For example, [math]\displaystyle{ [w11100] = (([w1110]S)K) = (((([w111]S)K)S)K) = ((([w11](SK))S)K) = (([w1]((SK)S))K) = ([w](((SK)S)K)) = ([w]K) }[/math] holds for arbitrary strings [math]\displaystyle{ w }[/math]. Similarly, [math]\displaystyle{ [w11111000] = (((((([w11111]S)K)S)K)S)K) = ([w](((((SK)S)K)S)K)) = ([w]S) }[/math] 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 [math]\displaystyle{ [w0] = (\iota[w]) }[/math] and by using the same identities on SKI terms for obtaining the basic combinators [math]\displaystyle{ K }[/math] and [math]\displaystyle{ S }[/math].

Zot

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 [math]\displaystyle{ \lambda cL.L(\lambda lR.R(\lambda r.c(lr))) }[/math], and 0 produces the continuation [math]\displaystyle{ \lambda c.c\iota }[/math], and wi consumes the final input digit i by continuing through the continuation w.

See also

References

  1. Barker, Chris. "Zot". https://www.nyu.edu/projects/barker/Iota/zot.html. 
  2. Stay, Michael (August 2005). "Very Simple Chaitin Machines for Concrete AIT". Fundamenta Informaticae (IOS Press) 68 (3): 231–247. Bibcode2005cs........8056S. http://content.iospress.com/articles/fundamenta-informaticae/fi68-3-03. Retrieved 20 February 2011. 

External links