From Esolang
Jump to: navigation, 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)