Simpler Subskin

From Esolang
Jump to: navigation, search

Simpler Subskin is an esoteric programming language created by User:ais523 in 2018. Although the original inspiration for the language was quite different (being based on an observation about what Brain-Flak minimizations could and couldn't do efficiently), the resulting language was retrofitted into being a Subskin derivative.

Definition

Simpler Subskin is an OISC with instructions of the form A−=B; in other words, each command in a program subtracts one variable in-place from another (or from itself). Additionally, if the result of such a subtraction is negative, the following command is skipped.

There's no indirection or memory-mapping; the only variables available will be those named in the program. However, each of these can store an unbounded integer (positive or negative). Likewise, there's no access to the instruction pointer; rather, at the end of the program, there's an implicit "goto" command that jumps back to the start of the program. (It's possible to terminate the program via "skipping this command", i.e. if the last command in the program produces a negative result the program will exit, if it produces a zero or positive result the program will continue from its start.)

I/O

A Simpler Subskin program can take one rational number from its environment as input, and produce one rational number as its output, in a batch way (i.e. all input is done as the program starts and output is done as the program ends). This number is I/O, i.e. at the start of the program, the values of I and O will be the numerator and denominator of the rational number given as input (in lowest terms, and with O nonzero); at the end of the program, the value of I/O will be the rational number produced as output (this doesn't have to be in lowest terms; all rational numbers with the same numerical value are equivalent, regardless of which numbers were used in the ratio). All other variables will start at 0.

Syntax

Because (as an OISC) the language has only one command, the only thing that need be specified by a program is the two variables that make up each command. Thus, in Simpler Subskin's syntax, each command consists of two characters, the variable being subtracted from and the variable being subtracted from it, with no delimiters or separators. Any single character (in the encoding used for the program) can be used as a variable name.

Complexity class

Simpler Subskin is very likely to be Turing-complete (although this has not yet been proven). However, the language is intended as a simple but efficient counter machine; in particular, the aim with the language is to be able to implement any Turing machine with only a linear slowdown (assuming, overly-optimistically, that subtraction on unbounded integers can be done in O(1)). To this end, Simpler Subskin was designed as a scale-independent language; multiplying the value of every variable by a constant has no influence on how the execution of the language proceeds. This means that not only is it possible to implement multiplication by a constant (using a hardcoded repeated addition; an addition is just two subtractions), it's also possible to implement division by a constant (by multiplying every other variable in use by that constant). It's then possible to construct stacks using the digits of a terminating rational that come after the binary point: to push 0 you halve the variable representing the stack, to push 1 you halve it and add 1, to pop it you experimentally subtract 1 (recording whether the result is negative), add 1 if you sent it negative, and double it. Two stacks makes a tape, so there's no issue with data storage; the only potential reason why Simpler Subskin might be Turing-incomplete is the restrictions on its control flow (which are likely but not proven to be easy to work around).