Sunny morning

Sunny morning is a functional Turing-complete programming language, but each function takes exactly one argument and can perform exactly one operation.
== Overview ==
Source code consists of one or more function definitions.
Function definition contains function name, the operation that the function performs and the next functions that are going to be called. Note that functions cannot access the argument directly.
=== Function argument ===
All values (arguments) in this programming language are ordered triples. The first element of a triple is either bit 0, or bit 1. The second and third elements are other triples. Note that each value can be expanded indefinitely.
There is no way to compare whether two values are equal (there are no pointers or memory allocations). All values that have the same structure also have the same behavior (extensional equivalence).
=== Function name ===
It is an identifier consisting of alphanumeric characters. Function names must be unique in the entire program. All referenced functions must have exactly one definition.
The first function that appears in the source code is the main function (its name is irrelevant).
=== Operation ===
Each function performs exactly one of the following 6 operations:
# Create a triple with bit 0
# Create a triple with bit 1
# Get the second element of a triple
# Get the third element of a triple
# Check whether the first element of a triple is 0 or 1
# Combine two functions
=== Next functions ===
Each function must specify what are the next functions that will be invoked with the same argument after the current function finishes.
== Syntax ==
To make it simple for understanding, we provide examples for all 6 different operations and we also write the same in pseudocode.
=== Create a triple with bit 0 ===
Code:
 func1 0 func2 func3
What it does in pseudocode:
 Triple func1(Triple arg){
 return new Triple(0, func2(arg), func3(arg));
 }
=== Create a triple with bit 1 ===
Code:
 func1 1 func2 func3
What it does in pseudocode:
 Triple func1(Triple arg){
 return new Triple(1, func2(arg), func3(arg));
 }
=== Get the second element of a triple ===
Code:
 func1 < func2
What it does in pseudocode:
 Triple func1(Triple arg){
 return func2(arg.getSecondElement());
 }
=== Get the third element of a triple ===
Code:
 func1 > func2
What it does in pseudocode:
 Triple func1(Triple arg){
 return func2(arg.getThirdElement());
 }
=== Check whether the first element of a triple is 0 or 1 ===
This operation has two variants.
==== Variant 1 ====
Code:
 func1 ? func2 func3
What it does in pseudocode:
 Triple func1(Triple arg){
 if(arg.getFirstElement() == 0)
 return func2(arg);
 else
 return func3(arg);
 }
==== Variant 2 ====
Code:
 func1 * func2 func3 func4
What it does in pseudocode:
 Triple func1(Triple arg){
 if(func2(arg).getFirstElement() == 0)
 return func3(arg);
 else
 return func4(arg);
 }
=== Combine two functions ===
Code:
 func1 . func2 func3
What it does in pseudocode:
 Triple func1(Triple arg){
 return func2(func3(arg));
 }
Some examples
Here is an example:
 allZeros 0 allZeros allZeros
This example defines a single function named allZeros. The function performs the first operation, i.e. it constructs a new triple whose first element is bit 0 and the second and third element are the results of applying allZeros to the same argument. In other words, this function, as its name says, recursively constructs all zeros.
We can also define identity function:
 identity ? bit0 bit1
 bit0 0 left right
 bit1 1 left right
 left < identity
 right > identity
The identity function returns the same argument it receives. By modifying it a little bit, we can construct an invertor:
 invert ? bit1 bit0
 bit0 0 left right
 bit1 1 left right
 left < invert
 right > invert
Now the function replaces each 0 with 1 and each 1 with 0.
== I/O format ==
Can be defined in various ways. It is implementation-dependent.
In this article we assume the following I/O format: input is a sequence of ASCII characters. Convert the input to bit array by first placing the lowest bit of the first byte, then the second lowest bit of the first byte, and so on, after the highest bit of the first byte put the lowest bit of the second byte, etc. Then before each bit prepend 1 and append infinitely many zeros. For example, string abcde will be converted to array of bits:
 11101010101111101011101010111110111110101011111010101110101111101110111010111110000000000000000000000...
Then construct the main triple in the following way:
 (firstBit, allZeros, (secondBit, allZeros, (thirdBit, allZeros, (fourthBit, allZeros, ...))))
The output is the triple obtained by calling the main function with the main triple as the argument. Then we reconstruct the ASCII string using the reversed process.
== Examples ==
=== Cat ===
 main ? cat cat
 cat ? ctor0 ctor1
 ctor0 0 left right
 ctor1 1 left right
 left < cat
 right > cat
=== Invert all bits ===
Note: it inverts bits, but keeps the beforementioned I/O format, so it inverts every second bit moving to the right.
 invert ? zeros invertBit
 invertBit 1 right1 right1
 right1 > inv1
 inv1 ? inv3 inv4
 inv3 1 zeros inv5
 inv4 0 zeros inv5
 inv5 > invert
 zeros 0 zeros zeros
=== Remove first bit ===
 removeFirstBit > a
 a > b
 b ? c d
 c 0 e f
 d 1 e f
 e < b
 f > b
=== Reverse bits ===
Reverse input bits using the beforementioned I/O format.
 main . reverse a
 a 0 ident zeros
 
 reverse * left right rest1
 rest1 . reverse rest2
 rest2 * lr rest3 rest4
 rest3 0 lrr rest5
 rest4 0 lrr rest6
 rest5 1 zeros rest7
 rest6 1 zeros rest8
 rest7 0 zeros right
 rest8 1 zeros right
 
 lr . right left
 lrr . right lr
 ident ? ctor0 ctor1
 ctor0 0 left right
 ctor1 1 left right
 left < ident
 right > ident
 zeros 0 zeros zeros
=== Output 'H' ===
A full 'Hello World' would be very long.
 main 1 allZeros main2
 main2 0 allZeros main3
 main3 1 allZeros main4
 main4 0 allZeros main5
 main5 1 allZeros main6
 main6 0 allZeros main7
 main7 1 allZeros main8
 main8 1 allZeros main9
 main9 1 allZeros main10
 main10 0 allZeros main11
 main11 1 allZeros main12
 main12 0 allZeros main13
 main13 1 allZeros main14
 main14 1 allZeros main15
 main15 1 allZeros allZeros
 allZeros 0 allZeros allZeros
== Computational class ==
Any Intramodular Transaction program can trivially be translated to Sunny morning. Therefore Sunny morning is Turing-complete.
== Open questions ==
* Would it be Turing-complete without . operation?
* Would it be Turing-complete without * operation (leaving only ? variant)?
== Interpreters ==
Interpreter
Category:Languages
Category:Turing complete
Category:Implemented
Category:2020