Incident

From Esolang
Jump to navigation Jump to search

Incident is a language created by User:ais523 for the CALESYTA 2016 contest. The goals of the language were to make an interesting puzzle for programmers (trying to figure out how to write anything at all in the language is decidedly nontrivial, although once you know the tricks the language is viably possible to write by hand); and to create a language which would allow programs to obey almost arbitrary restrictions on what can appear in the source (e.g. bans on certain characters, polyglotting with some other language, valid as an image / executable / save file for some other program, and the like).

Syntax

Incident's syntax is fairly unusual, specifically the lexical analyser; what counts as a valid token in the language is determined via analysis of the source code, rather than being predetermined. The basic rule is that the tokens for a particular program are the substrings that appear exactly three times in it. (The input program is interpreted as a string via converting it to a sequence of octets, if it isn't already in that form.) There are some restrictions:

  • A token cannot be a substring of a longer token; in this case, the shorter token is disregarded entirely.
  • Two tokens cannot overlap within the source; if they would, neither is treated as a token.

Anything that isn't part of a token is treated as a comment and discarded.

These syntax rules mean that an Incident interpreter can be fairly hard to write efficiently, given that changing any part of the program can affect how the entire rest of the program is parsed. They also mean that a syntax highlighter is a fairly essential tool when writing programs by hand.

Semantics

Obviously, Incident can't specify its commands via an explicit list. Instead, each token is treated as a command of its own (which also has an associated stack of bits, initially empty), but the behaviour of a command depends on where it appears in the program:

  • Running the first copy of a command pushes a 0 bit onto the stack associated with that command, then jumps to just after the second copy.
  • Running the third copy of a command pushes a 1 bit onto the stack associated with that command, then jumps to just after the second copy.
  • Running the second copy of a command pops a bit from the stack associated with that command, then jumps to just after the first copy if it was a 0 bit, or just after the third copy if it was a 1 bit.

There are a few exceptions. Two minor ones are to do with I/O, and have no effect on otherwise valid programs (thus, they act like backward-compatible extensions to a hypothetical version of the language with no I/O):

  • When pushing a bit onto the stack associated with the centremost token in the program (breaking ties towards the start of the program), the bit is also output to standard output (in a little-endian way).
  • When attempting to pop an empty stack, the bit is taken from standard input instead (again, in a little-endian way); this applies to all commands, not just the one associated with the centremost token. At EOF, the command simply fails to run (it's just skipped, and doesn't jump anywhere).

There's also an exception that changes the meaning of an otherwise valid program:

  • If a command would trivially cause an infinite loop, it is skipped and has no effect. A command is defined as causing a trivial infinite loop if it pushes a value to a stack, it has pushed that value to that stack before, and no stack has been popped since then.

Examples

Cat program

    |\ /|
    /"^"\
    (0 0)
    \_*_/_________
      (          _^^,
      (_________) ( )
cat    |||   |||   "
       ||^   ||^
       ^^    ^^

Hello world program

A1.A2.A3,A4.A5,A6,A7;A8;B1;B2,B3.B4,B5;B6.B7.B8;C1,C2.C3;C4.C5,C6;C7,
C8.D1;D2,D3.D4,D5.D6;D7.D8,E1;E2;E3;E4,E5,E6.E7,E8.F1;F2.F3.F4,F5.F6;
F7.F8;G1,G2;G3,G4;G5.G6.G7.G8;H1.H2;H3.H4.H5.H6,H7;H8;I1,I2.I3;I4,I5.
I6,I7.I8,J1;J2,J3,J4,J5;J6;J7.J8;K1;K2;K3;K4,K5,K6;K7.K8,L1;L2,L3;L4,
L5;L6;L7,L8,M1.M2.M3.M4,M5,M6,M7,M8,N1.N2;N3,N4.N5;N6,N7.N8,Z4;a1,a1.
Z3.A1,a1;a2,a2,A1,A2.a2,a3.a3.A2,A3,a3.a5,a5,A3;A5.a5,a6,a6.A5;A6.a6.
a8.a8.A6;A8.a8;b2,b2.A8;B2.b2,b4.b4,B2,B4;b4.b5;b5;B4;B5;b5.b8.b8,B5.
B8.b8.c1;c1,B8,C1;c1,c2,c2;C1;C2,c2.c5,c5;C2,C5,c5.c8.c8,C5;C8;c8,d1;
d1.C8,D1;d1.d2;d2.D1.D2.d2.d5,d5,D2.D5.d5.d8,d8;D5;D8.d8,e5.e5.D8;E5,
e5,e8,e8,E5,E8;e8,f1.f1.E8.F1;f1;f2,f2;F1.F2.f2;f5.f5;F2;F5,f5;f7;f7.
F5,F7,f7;f8.f8;F7.F8,f8,g1;g1.F8;G1.g1,g2;g2.G1,G2,g2,g3;g3;G2,G3;g3,
g4,g4.G3;G4.g4.g5.g5,G4,G5.g5;g7;g7.G5;G7,g7,g8;g8.G7,G8;g8;h4.h4,G8;
H4,h4;h8,h8,H4.H8,h8.i5.i5;H8;I5;i5.i8;i8.I5,I8,i8.j1;j1;I8,J1;j1.j3.
j3;J1,J3;j3;j4,j4.J3,J4.j4,j8,j8.J4;J8,j8.k1.k1.J8.K1,k1,k2.k2;K1,K2;
k2.k5;k5;K2,K5.k5,k8;k8,K5.K8,k8;l1,l1;K8;L1;l1,Z1;Z2;Z2,Z3.Z2;Z1.Z1,
l2;l2;L1;L2,l2;l4.l4.L2.L4;l4.l5.l5.L4;L5;l5.l8.l8,L5.L8;l8;m2;m2.L8;
M2.m2,m3,m3,M2,M3,m3;m4.m4.M3;M4.m4,m5.m5.M4,M5,m5;m7,m7.M5.M7;m7.m8.
m8,M7,M8,m8,n1;n1.M8,N1;n1.n3,n3;N1;N3,n3.n5,n5;N3,N5;n5,n6.n6.N5.N6.
n6,n7;n7;N6.N7;n7.n8,n8;N7,N8;n8,a4,a4;Z3;A4,a4;a7.a7.A4.A7;a7,b1.b1;
A7;B1,b1;b3;b3,B1,B3.b3,b6.b6;B3;B6,b6;b7;b7,B6,B7,b7;c3,c3.B7,C3,c3.
c4.c4,C3,C4.c4;c6.c6,C4,C6.c6;c7,c7;C6.C7,c7.d3;d3.C7,D3,d3;d4;d4.D3,
D4,d4;d6,d6,D4,D6.d6;d7,d7,D6,D7.d7,e1,e1;D7,E1.e1,e2,e2;E1;E2,e2.e3;
e3,E2,E3,e3.e4;e4.E3.E4;e4,e6;e6;E4,E6,e6.e7.e7;E6.E7.e7,f3,f3.E7,F3;
f3.f4;f4,F3;F4,f4;f6;f6.F4.F6,f6,g6.g6;F6.G6.g6.h1;h1;G6;H1,h1.h2;h2.
H1;H2,h2.h3,h3,H2,H3,h3.h5.h5;H3,H5;h5;h6;h6;H5.H6.h6,h7.h7.H6,H7.h7;
i1,i1,H7.I1,i1.i2;i2;I1;I2,i2,i3.i3,I2,I3.i3;i4;i4;I3,I4,i4.i6,i6,I4.
I6,i6.i7.i7,I6;I7;i7.j2;j2;I7.J2;j2,j5;j5.J2.J5;j5.j6,j6.J5,J6,j6;j7;
j7;J6,J7.j7;k3,k3;J7.K3.k3.k4.k4,K3.K4;k4,k6;k6,K4.K6;k6,k7.k7;K6,K7.
k7,l3.l3.K7;L3;l3.l6;l6,L3;L6,l6;l7,l7,L6;L7.l7,m1.m1,L7;M1;m1,m6;m6,
M1;M6,m6;n2;n2;M6,N2,n2;n4.n4,N2;N4,n4.N8.N4,Z4,Z4

Computational class

Incident's original documentation (in examples/triangle.md) noted that Minsky machines could be compiled into Incident parses "so long as no counter is the subject of more than one decrement instruction that's capable of failing", explaining how. This restriction turns out not to matter: The Amnesiac From Minsk level 1 is Turing complete, and as it has a more stringent restriction (TAFMl1 requires all decrements of a particular counter to return to the same place, which can be implemented in Incident via jumping all decrements to a common location and then running the decrement from there), there must therefore be an Incident parse corresponding to any Turing machine.

To prove Incident Turing complete, all that remains is to show that for any Incident parse, there's some program that parses to that parse. It turns out that this is indeed true; see the talk page for discussion of this subject.

External resources

  • The CALESYTA submission (including documentation, programming advice / spoilers on how to program in it, the motivation behind the language design, examples, and an implementation) can be obtained via running the command darcs clone http://nethack4.org/esolangs/calesyta-2016.
    • Note: the URL in question will not work in a web browser; you will need to use darcs to retrieve the submission. Alternatively, a sporadically updated tarball is available here.

See also

  • Lenguage and A Pear Tree, two other different ways of getting around source format restrictions
Retrieved from "https://esolangs.org/w/index.php?title=Incident&oldid=67279"