ETAS

From Esolang
Jump to: navigation, search
ETAS
Paradigm(s) imperative
Designed by User:Quintopia
Appeared in 2011
Computational class Turing complete
Reference implementation Unimplemented
Influenced by DNA
File extension(s) .eta


ETAS, short for etas,teas,sate,eats,east,tase,seat,esta,ates,stae,tesa,esat,aest,saet,taes,etsa,aset,tsae,seta,atse,tsea,aets,stea,aste or, if you prefer, Especially Tiny and Annoying Self-modifier, is a language created in 2011 by User:Quintopia inspired by DNA and at the urging of User:Zzo38 to make a language wherein the same piece of code could be interpreted as two different things by reading it beginning at different places.

Structure

ETAS is structured as a circular buffer with a program pointer that jumps 8 characters after each instruction, and an independent data pointer (DP) into the same buffer. The buffer is divided into quaternary "digits" which are represented, as expected, by the letters a, e, s, and t, (equal to 00,01,10, and 11 respectively). Any 16-bit number given by eight of these digits is interpreted programmatically in the following way:

Instructions

Capital letters here are metasyntactic variables, each equivalent to one of the four digits.

Digit Sequence Name Operation
aaXXXXXX DATA NOP
aeXXXXXX RIGHT Move DP XXXXXX digits right
asXXXXXX LEFT Move DP XXXXXX digits left
ataXXXXX OUTPUT Output XXXXX UTF-16 code units beginning at DP. (Note that a UTF-16 code unit is the same length in digits as an instruction.)
ateXXXXX INPUT Insert XXXXX UTF-16 characters from input at DP.
atsXXXXX SELECT Select XXXXX digits beginning at DP, mark for deletion, copy to buffer.
attaXXXX INSERT Insert entire buffer before DP, delete all marked digits.
atteXXXX JUMP Move program pointer to XXXX digits past DP, do NOT move ahead 8 digits ahead afterwards.
attsXXXX RESERVED If it turns out this language is not Turing-Complete, something can be put here to make it so. Otherwise, this can be used for interpreter-dependent extended functionality.
atttAEST TRANSFORM Substitute another digit for the one at the DP by making it A if a, E if e, S if s, T if t
eXXXXXXX DATA NOP
sXXXXXXX DATA NOP
tXXXXXXX DATA NOP

Halting

A program halts when the program pointer arrives at a digit it has been at before if the program has not changed at all since the last time it was there and the DP is in the same place. (It is trivial to show that nothing interesting will ever happen again in this case. Note that this means even writing a program that produces the same output forever requires some extra effort.) An optimizing interpreter would do analysis to ensure it jumps automatically from one instruction to another without scanning the DAT/NOPs in between. In addition, it could check in advance whether this was going to be the case, and, if nothing was going to be output, halt as soon as possible. Note that a halt-checker would not have to store data about every non-self-modifying instruction, but only the first ones occurring after RIGHT, LEFT, or, INSERT commands.

Memory Management

Note that there is no way to shrink the length of a program, and so most programs that do useful things will grow without bound. Perhaps a DELETE command should go in the RESERVED slot to fix this?

Complexity Class

Unknown for the moment, though it is highly likely that it is TC. Note that memory is not bounded: it can grow by SELECTing the same digit repeatedly before INSERTing it. Conditionals are easy: every command has an implicit "if the first digit is 'a' (zero)." Arithmetic can be implemented (possibly with some difficulty) using TRANSFORM (attttaes does one-digit decrementing, or atttaaes for the non-wrapping version). However, even trivial programs are difficult to implement, so proving TCness will take some thought.

Examples

Cat:

ateaaaaeaseeeeeeaseeeeeeaseeeeeeaseeeeeeaseeeeeeaseeeeeeaseeeeeeaseeeeeeataaaaaeaeeeeeeeaeeeeeeeaeeeeeeeaeeeeeeeaeeeeeeeaeeeeeeeaeeeeeeeaeeeeeeeatteaaaa