From Esolang
Jump to navigation Jump to search

An imperative language analogous to Iota

I've defined an imperative language, Im, analogous to Iota. Whereas Iota's semantics use combinatory logic as an underlying computational model, Im uses Jm (a language I defined in terms of Fm for this purpose).

Jm programs are strings on the alphabet {J,L,r}, with the brainfuck correspondences

'L' <--> '<'  
'r' <--> '+>'
'JL' <--> '['
'Jr' <--> ']'

Im programs are strings on the alphabet {0,1}, and the semantics are analogous to Iota's. Im instructions have the correspondences

 '0' <--> 'J'
'10' <--> 'L'
'11' <--> 'r'

Details are at --R.e.s. 20:46, 23 Jul 2005 (GMT)

Why Iota is not "the simplest programming language"

The programming language Iota is "defined" as follows:

Iota Syntax

  • <expression> ::= i | * <expression> <expression>

Iota Semantics

  • [* <expresssion> <expresssion>] == ( [<expresssion>] [<expresssion>] )
  • [i] == \x.xSK
where [...] denotes "the meaning of ...". 

The syntax is nice & simple, but there are problems with the semantics:

  1. The semantics as stated is not complete, because it implicitly requires the additional unstated semantics of λ-calculus to give meaning to "\x.xSK" (e.g., the stated semantics is insufficient to perform a calculation);
  2. If CL, rather than λ-calculus, were used as the underlying model, the additional semantics would be simpler, but then \x.xSK, being an improper combinator would also need to be replaced by an equivalent proper combinator, e.g. ((S((S((SK)K))(KS)))(KK)).

Thus to completely and properly define the language Iota, a great deal of semantic detail must be added to the incomplete "definition" stated above.

In my opinion, to qualify as "the simplest language", the whole definition -- comprising both the syntactical & semantic parts -- would need to be as simple as possible, and it would need to be at least complete enough to perform computations without invoking unstated semantics. It would not refer to any "underlying" computational model (e.g. λ-calculus) whose semantics are omitted.

If either of the above two problems were remedied, the result would be an Iota that is not simpler than the better-known "binary CL" (as at John's Lambda Calculus and Combinatory Logic Playground), a version of which can be stated very concisely as follows:

Binary CL (BCL)

BCL Syntax

  • <term> ::= 00 | 01 | 1 <term> <term>

BCL Semantics(as string-rewriting rules for any terms x, y, z)

  • 1100xy --> x
  • 11101xyz --> 11xz1yz

That's the entire "Binary CL" programming language, and it seems much simpler than an adequately-defined Iota. --R.e.s. 21:15, 23 Jul 2005 (GMT)

Whew. Okay, but Iota is pretty much the same thing, except with an added function that is the only one allowed to appear in the source code. Simpler syntax, more complicated semantics, right? --Ihope127 15:15, 9 Oct 2005 (GMT)


This page needs to be improved. It says 'can be defined as' and if * is dot notation I still don't know what's going on. Imaginer1 (talk)

Hope this helps. --Ørjan (talk) 22:58, 8 September 2014 (UTC)
I think that the explanation at Iota's archived website should be added. As far as I can tell, the explanation given here is inaccurate (the equivalent combinator doesn't depend at all on how many asterisks you have in a row) --BrightBlackHole (talk) 18:47, 2 May 2023 (UTC)

sed regex to split Iota into newline separated CL primitives

   sed 's/ii/ii\n/g;s/\(\*\+\)\*/\1\n\*/g' <<< "**i*i*i*ii***i*i*ii****ii*****i*i*ii"
  • S  : *i*i*i*ii
  • K  : *i*i*ii
  • I  : *ii
  • KI : *i*ii

I made this to help read Zot code, which has the same structure, but uses 01 instead of i*. Sharing here as it might be useful to someone else trying to decipher this language family. Salpynx (talk) 00:41, 5 July 2019 (UTC)