Ziim

From Esolang
Jump to: navigation, search

Ziim is a two-dimensional esoteric programming language, invented by Timwi in 2011, consisting entirely of the following Unicode arrow characters:

↑ ↗ → ↘ ↓ ↙ ← ↖ ↕ ⤢ ↔ ⤡

If you cannot see the above arrows, or they are not the same size, then you have a problem. You will need a fixed-width font that includes these characters to display (and edit) Ziim programs properly.

The semantics of a Ziim program depend on which arrows are pointed to by which other arrows, and at what relative angles. With all these arrows pointing at each other, no-one can say this language is pointless! Each instruction is invariant under 45° rotations (although it’s not entirely straight-forward how to rotate an entire program 45° — but it’s certainly possible). The meaning of each arrow depends only on how many other arrows point at it and at what angle (relative to where the arrow itself is pointing). In particular, the distance at which arrows are placed is immaterial.

Apart from these arrows, only spaces (U+0020) and newlines (U+000A, optionally preceded by U+000D) are allowed. Every other character is a syntax error. Lines are allowed to have varying lengths, in which case a compliant interpreter must treat the program as if the lines had been padded with spaces to be equal length.

Semantics

  • Ziim programs are heavily multi-threaded. At every point in time there is a finite set of threads running, some of which may be suspended (paused, on halt).
  • Each thread is at an arrow — its current instruction. After executing the instruction, the thread moves in the direction the arrow is pointing until it finds another arrow, which becomes its new current instruction.
  • Each thread also has a current value, which is a finite-length sequence of bits.
  • At the beginning of execution, a new thread is started at each arrow that is not pointed to by any other arrow. All of these threads start out with an initial value of { 0 }, i.e. a sequence containing a single 0-bit.
  • When a thread encounters an arrow that points to outside the program, the thread’s current value (after executing the instruction) is output to STDOUT. Then the program terminates (not just the thread!). An interpreter is free to interpret the output bit sequence any way it likes; for example, it could decode it as UTF-8 and output as text.
  • If a thread reaches an instruction on which another thread is already executing or suspended, the thread must wait. In other words, threads are not allowed to “overtake” each other on any one instruction. If several threads enter an instruction and are suspended, they must be unsuspended in the same order they came in. (However, it is still possible for a thread to “overtake” another by taking a different route.)
  • If, at any point, all threads are left in a suspended state, the program terminates.
  • The meaning of an instruction depends on the type of arrow (single or double arrow), the number of arrows pointing to it, and the angles at which they point to it (relative to the angle the arrow is pointing to). The table in the following section details the semantics of every instruction. If a program contains an arrow that is pointed to in a combination of angles that is not listed, compliant parsers must issue a syntax error.

Instructions

Ziim Short Very short Detail
{ 0 } 0 Each arrow that has no other arrows pointing to it starts a new thread at the start of execution with the initial value { 0 }.
↘
 →
read R An arrow that has one other arrow pointing to it and that makes a 45° left-turn reads a single bit from STDIN and sets the current value to a single-bit sequence containing that bit. If STDIN is exhausted, the instruction returns the empty sequence ({ }). (If input is provided as bytes, the most significant bit of the first byte comes first.)
→
 ↖
no-op N An arrow that has one other arrow pointing to it and that makes a 135° right-turn is a no-op. The thread continues and the current value remains unchanged.
 ←
↗
invert I An arrow that has one other arrow pointing to it and that makes a 135° left-turn is an inverter. Every bit in the current value is flipped. The length stays the same.

Apart from the read instruction which reads from STDIN, this is the only instruction that can generate a 1-bit.

B ↘
   →
A ↗
concat C An arrow that has two other arrows pointing to it as shown is a concatenator. Every time a thread hits such a concatenator from either side (A or B), it is suspended until the other side is also hit, at which point the current value is set to the concatenation of A’s current value followed by B’s current value. One thread is terminated and execution continues with the concatenated current value.
 ↙
→
 ↖
label L An arrow that has two other arrows pointing to it as shown provides a way for separate paths of execution to merge. Execution simply continues with the current value unchanged. This means it’s effectively a no-op. It enables execution to return to an earlier point (making it possible to construct loops). Think of it like a goto label.
→↕
splitter S A double-arrow that has one other arrow pointing to it at a 90° angle splits the current thread into two threads with the same current value, which continue their execution separately in opposite directions.
 ↕
↗
isZero Z A double-arrow that is pointed to by one other arrow, forming a 45° left-turn and a 135° right-turn, is an “if” instruction that checks and removes the first bit in the current value. If the first bit was zero, the 45° left-turn is taken. If the first bit was one, the 135° right-turn is taken. In both cases, execution continues with the first bit removed from the current value. If the current value was empty, the thread terminates.
 ↔
↗
isEmpty E A double-arrow that is pointed to by one other arrow, forming a 135° left-turn and a 45° right-turn, is an “if” instruction that checks whether the current value is empty or not. If it is empty, the 45° right-turn is taken, otherwise the 135° left-turn is taken. In both cases, the current value is set to the empty sequence; in other words, if the current value was non-empty, all bits are removed from it.

Apart from the read instruction which returns an empty sequence when STDIN is exhausted, this is the only instruction that can generate an empty sequence. (In theory the isZero instruction can generate an empty sequence too, but in practice you can’t test for it without isEmpty.)

Hello, World!

The following example program outputs the string “Hello, World!”. It uses only { 0 }, no-op, inverters, concatenators, splitters and STDOUT. It is “reliable” in the sense that it doesn’t exhibit any race conditions.

Since most systems don’t appear to have the necessary monospace font available for all the arrows to line up correctly, I have also included a graphical representation.

As plain text As image
    ↘↓                        
        ↘                     
↘          ←              ↙   
          ⤢↘           ↘← ↑   
 ↘←     ↑⤡↙ → ↙         ↓↙↙   
      ↙  → ↗           ↙      
 ↘ ←  ↙↙↘     ↙↘ ↙     ↑   ↘← 
↘     ↑↕ ←     ↓↓↑      ↙   ← 
  ↘   ←  ↙ ↕← ↗            ↔↙ 
     ↗↓ ↑↑  →↖  ↙←  ↓   ↘     
 →    ↘ ↘   ↓↘← ↗     ↙↙      
   ↙    ↖ ↘  ←↓↙←     ↑  ↑↑   
↑ →         ↘  →          ↙   
     ↘        ↙      ←↙       
  ↘  ↕     ↔       ↙↙     ←  ↙
                  ⤡           
    ↑ ↘  ←↓↓↓ ↓↓↓   ↙↘        
        ↘→  ↘ ↙  ←    ↑       
   ↓  ↘  → ↘   ↙ ←            
         →↘ ↓ ↓ ↙←   ↕←       
       ↗   →↘ ↙←              
         →↗  ↓  ↖←   ↖ ↕ ↔  ↙ 
    ↗↔ ↖  ↑↓   ↙↑ ↖←       ↑↘ 
    ↙       ↓ →↗→↖↑ ↑        ↑
           ↗↖  ↑→ ↙↓ ↙        
  ↑    ↗      ↔   ↖↙←↙↓↖      
  ↗↔  ↕ ↑  →              ↙   
  ↘  ←↗ →↖ ↘  ↕  ←    ↖   ⤡   
  ↗         ←        ↙  ↑     
      ↙       ↖   ↓↖←     ↖ ↑ 
   ↓ ↓↑↙        → ↘↑↓↖        
   ↗ ↙←    ↑      ↙→     ↕    
  →                   ↖       
   ⤡    ↖       →↗ ↓     ↖    
    ↑            ↑ ↗↖         

Ziim — Hello World.png

Useful constructs

Annotated Raw source Description
Ziim — Producer.png
  →  ↙ 
  ↙⤡   
  ↕←   
→   ↖↑ 

Producer

This construct can be used to produce the same value multiple times (for example, you might need to access the string "bottles of beer" inside a loop). The program is expected to feed some data into the data input of this construct, and then the producer keeps producing that data every time the trigger is hit by a thread. (The data passed in via the trigger is discarded.)

The data passed in through the data input gets to a concatenator, where it waits. The thread passed in through the trigger input is passed through an isEmpty instruction in order to discards its value, and then passed into the concatenator. The result is the original data since it is concatenated with nothing. The thread coming out of the concatenator is then split into two; one goes straight back into the concatenator to wait for the next trigger, while the other is the output.

If the data input is hit multiple times, the producer will produce data in an alternating fashion, which might be useful in some cases. However, doing so creates a race condition and renders the program unreliable.

Ziim — Non-destructive isEmpty.png
 → ↙     
         
   ⤡     
→ ↗      
 ↖  ↙    
  ↕  ↘←  
   ⤡     
 →↘   ↓  
   ⤢  ⤡↖←
  →↖↑    
       ↑ 

Non-destructive IsEmpty

This construct can be used to determine whether a value is empty without discarding it.

The data passed in through the input is split into two threads; one thread is tested for emptiness and then set to the value { 0 } to indicate “empty” or { 1 } for “not empty”. This is then concatenated to the front of the second thread which still contains the original value. Finally, an isZero instruction removes the concatenated bit again and triggers the appropriate output.

Note that this construct uses two producers; however, because we already know the triggering thread will have the empty value because it just came from an isEmpty instruction, the full-blown producer is not necessary.

Ziim — Backward Accumulator.png
  ↘←↙    ↓ 
     →↖    
  ↑ ↕→↖⤢←  
  →  ↙⤡→ ↖ 
  ↙⤡   ←   
  ↕←  ↗→ ↖ 
→   ↖↑     
 →       ↖ 
  ↖        

Backward Accumulator

An accumulator is a construct to use when the output from several iterations of a loop should be concatenated and then returned as a single thread. The backward accumulator concatenates the input back to front.

Here’s how to use it:

  • In each iteration of your loop, pass in a thread whose value begins with a 1 bit. The accumulator removes that 1 bit and accumulates the remaining bits without outputting anything.
  • Finally, pass in a thread whose value begins with a 0. As before, that bit is removed, the rest concatenated on, and then the final result comes out. Furthermore, the accumulator is reset to empty so that it can be used again (in case you have several nested loops).

Internally, the accumulated data is always waiting at a concatenation instruction (which is initially seeded with an empty value). Every time data comes in, it is concatenated to the front and then the first bit removed to determine whether to output or not. When it’s time to output, a splitter is used to trigger a producer that resets the concatenator back to the empty value.

Ziim — Forward Accumulator.png
          ↓   
              
            ↓ 
    ↘←↓⤢      
          ↗←  
    ↗↔  ↖⤡↗  ←
    ↓ ↙←      
     ⤡  ↘ ↓⤢ ↓
            ↗ 
    ↗ ↘←↗↔  ↖ 
    →↙↘←↓ ↙←↓ 
   ↘ ↖ ← ⤡   ↖
   ↕  ↗   ←  ↙
   ↔  ↙ ↗↘    
→↙  ↘      ←  
→⤡ ↓ ↑↑     ↖ 
 ↖    ↘ ←     
 ↗↔  ↖  ↘    ↑
 ↓ ↙←   ↑↑    
  ⤡ ↘         
              
 ↗  ↑ ↑       

Forward Accumulator

The forward accumulator concatenates the input in the order it was passed in. Otherwise it works the same as the backward accumulator.

The forward acculumator is significantly more complex than the backward accumulator because the backward accumulator can conveniently make use of the fact that the IsZero instruction queries the bit at the front. The forward accumulator needs to take that bit off the input first; concatenate that bit to the front and the rest of the payload to the back; and then once again query that front bit to determine whether to output or not.

The producers in here are different from the producer shown above because these have their inputs and outputs at a diagonal angle, which changes the layout significantly. It is still the same construct, however.

Ziim — Reverse.png
  ↙                   ↓   
 →                     ↖  
             ↙   ↓     ↘  
       ↘                ← 
     ↘  ←↓  ↘     ↔↖↓     
   ↓    ↙    ↑↓↙  ↑⤢      
     ↙↗   ↔↖↓    ↗       ←
    →⤡  ↑ ↑⤢ →↘  →  ↖→  ↗ 
 ↘  ←⤡   ↗     ←    ↓   ↑ 
  ↑↗   ← →  ↖ → ↙↓   ↓    
  ↘←↙    ↓↙↕↔      ↕↗↙  ← 
     →↖     ↓   ⤡↗ ↖      
  ↑ ↕→↖⤢←  ↗ → ↗      ↗   
  →  ↙⤡→ ↖↑   ↖  ↙    ↘   
  ↙⤡   ←    ↗  ↕  ↘←   ↑  
  ↕←  ↗→ ↖      ⤡         
→   ↖↑        →↘   ↓      
 →       ↖      ⤢  ⤡↖←    
  ↖            →↖↑        
                   ↓↑→↕   
                          
                   ↗   ←  
                      ↗   

Reverse

The reverse function reverses the order of all the bits in the current value.

It uses an isZero instruction to query each bit of the sequence and then feeds them all into a backwards accumulator, thus generating the sequence backwards.

Ziim — Successor function.png
   ↓                        
             ↓        ↓↓    
  ↘ ↔↖↓             ↓ ↗ ↓   
    ↑⤢  ↙↓          ↗       
 →↙↗   ←                  ↓ 
   →  ↖           ↘←↓⤢      
→    ↕ →↗               ↗←  
  ↓→↖↗→   ↖       ↗↔  ↖⤡↗  ←
     ↓↘←↑↖        ↓ ↙←      
 →↘⤡  ⤢        ↙   ⤡  ↘ ↓⤢ ↓
   ↑   ↖← ↙               ↗ 
      ⤡     ↘   ← ↗ ↘←↗↔  ↖ 
   →↖  ↕          →↙↘←↓ ↙←↓ 
  ↙  ↗  ↘        ↘ ↖ ← ⤡   ↖
 → ↗↙  ↙ ←     ↑ ↕  ↗   ←  ↙
   ↑  ⤡⤢    ↗    ↔  ↙ ↗↘    
    ↑      →↖ →↙  ↘      ←  
      ↗ ← ↕↔↖ →⤡ ↓ ↑↑     ↖ 
    →⤡ ↘ ↘  ←  ↖    ↘ ←     
 ↘    ←↓→   ↙  ↗↔  ↖  ↘    ↑
  ↑   ↖↗  ⤢↓   ↓ ↙←   ↑↑    
         ↑↘↔ ↖  ⤡ ↘         
                            
            ↑  ↗  ↑ ↑       

Successor (binary)

The successor function calculates the successor of a number encoded in binary (that is, it adds 1).

This implementation assumes that the number is encoded with the least significant bit first. Note this is the opposite order compared to how UTF-8 code units are represented in the program input and expected in the program output.

The empty sequence is assumed to encode the number 0. Input sequences consisting of all 1s result in an output sequence that is one bit longer; all other inputs are kept the same length. Trailing zeros (which are numerically leading zeros) are kept.

Ziim — Add.png
            ↓                                                         
      ↘  ←↘ ↙ ← ↓                                                     
        ⤢ ↕  ↗↖→ ↖                                                    
         ↖  ←↓↓    ↓↓                                                 
      → ↙↑   ↗    ← ↖⤡↘↙                                              
          ↗      ⤢  ↘  ↑     ↙                                        
      →      ↙↖      ↑↕ ↙  ↘                                          
              ↘ ↔↖→↖ ⤢            ←                                   
              → ↙   ↕  ↘ ←→     ↙↗  ←                             ↘   
            ↓ ↓  ↘↙↙⤡ ⤡ ↑ ↙ ↘                                      ←↙ 
          →  ↙    ↑↕ ←        →   ↗                        ↙ ↙        
       ↘  ↙⤡   ←    ↘    ↙  ↓    ↘  ←↘ ↙       ↓        ↓      ↓↘ ↑   
       ↑  ↕←  ↗      ← ↑→   ↘      ⤢ ↕        ↘  ←↘ ↙ ↓    ↑  ↗  ←    
        →   ↖↑ →  ↖↖↑     ↑ ↙↑ ↓  ↑ ↖  ←     ↘  ⤢ ↕  ↗   ↔↖↓  ↘       
        ↘  ↓  ↓ ⤡          ↑   ↖  ↙ ↑    ↓       ↖  ←↙   ↑⤢      ↙    
      ↘ ↓ ↗ →  ↖ ↑↘  ←↘ ↙  ↘  ←↘     ↗          ↙↑      ↗   ←   ↑     
    ↘       ←       ⤢ ↕      ⤢ ↕    ↙ →⤢      ↘   ↗ ⤡   →  ↖↓  ↙←     
    ↘←↗↔  ↖  ↘  ←    ↖  ← ↓ ↑ ↖  ←      ↓ ⤡ →↕    →↗ ↑ ↘  ↕     ↘     
      ↓ ↙←↓ →   ↙↘ ↙ ↑        ↑    ↙  ↙ ↖ ↓      ↘  ↔↙↙ ← ↗ ↖    ↑    
       ⤡      ⤢↓ ↑    ↗↘   ↔↖↓ ↗ →      ⤢ ↖↖     ←    ↘  ←  ⤡   ↕     
         ↓↗  ↑↘↔     ↙↓    ↑⤢     ⤡ ↑      ↑   ↖   ↑ ↖ ↑     ↑ ↘  ←   
   ↓  ↗     ↘ ↘         ↓↑↗    ←→↗ ↑ ↘  ←↙↔↙↘↔ ↙↑↗ ↔      ↖↗←→    ↙   
  ↗       ←↖    ↑  ↑↗←↗   →  ↖↗↘  ↔↙ ⤡ ↘ ↘   ←↑      ↓ ↙   ⤢    ⤢↓    
         ↗    ↑       ↘  ↔↖↓↕           ←  ↘    ← ↘ ↓⤢⤡     ⤡  ↑↘↔ ↙  
        ↓↓             ↑ ↑⤢     ⤢↑→↖↘    ↔↖  ↖          ←    →       ↙
  ↘  ←↘↗⤢↖  ↑           ↗    ← ⤡   →↙↓    ↖ ←   ↘ ↗↔  ↖↑   ↘   ←↘ ↑ ↑ 
    ⤢ ↕   ↙             →  ↖   ↘← ⤡   ↑   ↑ ↙  ↙  ↓ ↙←↗     ←   ↑     
     ↖  ← ↕↔↙           →     ↙→ ↙↑  ↖     ↑       ⤡ ↘→  ↖  ↘↗        
  → ↙↑   ↙   ↓↘  ←↘ ↙   ↓    →     ⤢  ↙   ↓  ↑↗     ←    ↗         ←  
     ↙↗ →   ↗↖  ⤢ ↕ ↑        ↙   ⤡ ↘     ↗ ←↑   ↕ ↗↘← ↗←      ↑       
  →    ↙→ ↖↘ ↙↙  ↖  ←    → ↖  → ↗  ↑     ↘  ← ↘              ←        
     ↑      ↑↑↑  ↑  ⤡    ↙    ↙↖  ↙     →   ↙  ↑ ↓  ↓↑                
     →↙↑  ↘  ←↘ ↙ ↗      ↑↑→↖↑  ↕  ↘← ↑ ⤢ ⤢↓    ↗↗                    
     →    ↙ ⤢ ↕   ⤢      ←       ⤡       ↑↘↔     ↙↘↔↖                 
           ↑ ↖  ← ↘↘   ←     ⤡ →↘   ↓ →       ↙↘←   ↗ ←    ↓          
         ↑   ↑  ⤡  ↑          ↑  ⤢↑ ⤡↖←     ↑ →  ↖↘      ↓            
        ↗    ←↗↘     ←          →↖↘      ←  →  ↖→   ↙    ↗ ↗          
      →    ↖↗   ← ↑→           ↙     ↑  ↗←      →↖↑↑↑                 
                    ↗               ←  ↑↗              ←              
                      →                                       ↙       
  →                                                           ↖       
   ↖                    ↖  →                        ↖       ↑             

Addition (binary)

The addition function calculates the sum of two numbers encoded in binary. It expects the input in the same format as the successor function above.

Turing completeness

Not sure, but extremely likely.

Interpreter