stroke-lang

Stroke

Stroke, also {/|\}, is an esoteric structured programming language.

With only three instructions, it aims to be the simplest structured programming language ever.

It uses conditional loops and an unbounded number of binary variables, along with flipping their values.

Stroke is almost Turing complete, unlike its bigger brother Stroke+- which truly is.

Language

Stroke code consists only of stroke symbols /, |, \, and white spaces to separate them.

All other symbols are ignored.

Instructions

Instr	Name	Meaning
/ var	Loop start	Enters a new loop if var is non-zero
\	Loop end	Jumps back to the matching loop start
| × n	Flip value	Flips the value of the variable n-1

All instructions and their attributes are separated by one or more white spaces.

The example code in Stroke:

| 
/ | 
  | 
  || 
\ 
|||

can be translated into the following pseudocode:

flip var0
while var0
  flip var0
  flip var1
flip var2

Optionally, the instruction for output ! may be implemented.

Variables

A Stroke program runs on a theoretically infinite tape of binary cells that are randomly accessible via variables denoted by consecutive vertical stroke symbols (|) in unary form starting from zero. For instance, | flips the variable indexed by 0, || flips the variable indexed by 1, ||| flips the variable indexed by 2, and so on.

A variable occurring in code directly after a loop start will be just read (and checked to be non-zero), while a variable anywhere else in the code will flip its binary value.

The binary tape can simulate integers of arbitrary size, e.g. 4-bit unsigned:

  variable index   0  1  2  3  4  5  6  7  8  9  10 11 ...
       bit index   3  2  1  0  3  2  1  0  3  2  1  0  ...
virtual variable   \   A    /  \   B    /  \   C    /  ...

Examples

The following examples operate on virtual 4-bit variables A, B, and C.

Empty program

The simplest program is the empty program:

Infinite loop

As variable 0 is never reset, the program loops forever:

| / | \

Conditional branching

Conditional branching (IF) can be simulated via loops:

IF A:
|||||||       running
/ | |         first bit not zero
    |||||     result
    ||||||    shall reset bit
    |||||||   stop
\
/ |||||| |||||| | \  reset bit
/ |||||||            still running
    / || ||          second bit not zero
    |||||            result
    ||||||           shall reset bit
    |||||||          stop
    \
    / |||||| |||||| || \  reset bit
    / |||||||             still running
    / ||| |||             third bit not zero
        |||||             result
        ||||||            shall reset bit
        |||||||           stop
    \
    / |||||| |||||| ||| \  reset bit
    / |||||||              still running
        / |||| ||||        fourth bit not zero
        |||||              result
        ||||||             shall reset bit
        \
        / |||||| |||||| |||| \  reset bit
        |||||||                 stop (all bits checked)
    \
    \
\
/ ||||| |||||  
  
  do something conditionally...

\

Equality check

Compares A and B bit by bit:

EQ A B => v8:
||||||||| ||||||||||||| |||||||||||
/ | | ||||||||||||
    / ||||| ||||| |||||||||| |||||||||||| \
    / |||||||||| |||||||||| ||||| \
    / |||||||||||| |||||||||||| ||||||||| ||||||||||||| \
    |||||||||| |||||||||||
\
/ |||||||||| |||||||||| | \
/ ||||||||||| ||||||||||| 
    / ||||| ||||| |||||||||| ||||||||| |||||||||||||
    / |||||||||| |||||||||| ||||| \
\
/ ||||||||||||| |||||||||||
    / || || ||||||||||||
    / |||||| |||||| |||||||||| |||||||||||| \
    / |||||||||| |||||||||| |||||| \
    / |||||||||||| |||||||||||| ||||||||| ||||||||||||| \
    |||||||||| |||||||||||
    \
    / |||||||||| |||||||||| || \
    / ||||||||||| |||||||||||
    / |||||| |||||| |||||||||| ||||||||| ||||||||||||| \
    / |||||||||| |||||||||| |||||| \
    \
    / ||||||||||||| |||||||||||
    / ||| ||| ||||||||||||
        / ||||||| ||||||| |||||||||| |||||||||||| \
        / |||||||||| |||||||||| ||||||| \
        / |||||||||||| |||||||||||| ||||||||| ||||||||||||| \
        |||||||||| |||||||||||
    \
    / |||||||||| |||||||||| ||| \
    / ||||||||||| |||||||||||
        / ||||||| ||||||| |||||||||| ||||||||| ||||||||||||| \
        / |||||||||| |||||||||| ||||||| \
    \
    / ||||||||||||| |||||||||||
        / |||| |||| ||||||||||||
        / |||||||| |||||||| |||||||||| |||||||||||| \
        / |||||||||| |||||||||| |||||||| \ 
        / |||||||||||| |||||||||||| ||||||||| \
        |||||||||| |||||||||||
        |||||||||||||
        \
        / |||||||||| |||||||||| |||| \
        / ||||||||||| |||||||||||
        / |||||||| |||||||| |||||||||| ||||||||| \
        / |||||||||| |||||||||| |||||||| \
        |||||||||||||
        \
    \
    \
\
\ ||||||||| |||||||||

  do something if equal...

/

Increment and decrement

The following program increments A and decrements B:

INC A:    
||||||       carry
/ |||| |||| ||||| |||||| \
/ ||||| ||||| |||||| 
    / ||| ||| ||||| |||||| \
    / ||||| ||||| ||||||
    / || || ||||| |||||| \
    / ||||| ||||| ||||||
        / | | |||||| \
        / |||||| |||||| | \
    \
    / |||||| |||||| || \
    \
    / |||||| |||||| ||| \
\
/ |||||| |||||| |||| \

DEC B:
|||||||||
/ |||||||| |||||||| ||||||||| \
/ ||||||||| ||||||||
/ ||||||| ||||||| ||||||||| \
/ ||||||||| ||||||| 
    / |||||| |||||| ||||||||| \
    / ||||||||| |||||| 
    / ||||| ||||| ||||||||| \
    / ||||||||| |||||
        |||||||||
    \
    \
\
\

Addition

Having conditional branching, increment, and decrement intact, a program to add A and B is just a simple composition:

ADD A B => A:
IF B
   INC A
   DEC B

Fibonacci sequence

FIB:
x 
/ x   forever
  IF B
     DEC B
     INC C
  IF A
     DEC A
     INC B
  IF C
     DEC C
     INC A
     INC B  
\

Hello World

For computing "Hello World" the tape must interpreted as a string. It can achieved by defining a binary alphabet:

Symbol	Binary
	000
d	001
e	010
H	011
l	100
o	101
r	110
W	111

The following program set the tape to 011010100100101000111101110100001 which corresponds to "Hello World":

|| ||| ||||| ||||||| |||||||||| 
||||||||||||| ||||||||||||||| 
||||||||||||||||||| 
|||||||||||||||||||| 
||||||||||||||||||||| 
|||||||||||||||||||||| 
|||||||||||||||||||||||| 
||||||||||||||||||||||||| 
|||||||||||||||||||||||||| 
|||||||||||||||||||||||||||| 
|||||||||||||||||||||||||||||||||

Computational class

The minimalistic nature of Stroke has its price: it had to give up Turing completeness.

As every variable (bit) must be represented in code as a sequence of | the program cannot access an infinite number of bits as required for Turing completeness.

However, variables of arbitrary size can be used which brings the language very close to being Turing complete according to the structured program theorem, as conditional branching (selection) can easily be simulated via loops.

In short, Stroke can do everything a Turing complete language can but only with limited data.

JavaScript interpreter

npm i stroke-lang

const stroke = require('stroke-lang')

stroke('| / | | || \\ |||')  // "011"

License

MIT