Sunny morning

Sunny morning

Paradigm(s)	Functional
Designed by	Hakerh400
Appeared in	2020
Computational class	Category:Turing complete
Major implementations	Interpreter
File extension(s)	.txt

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:

1. Create a triple with bit 0
2. Create a triple with bit 1
3. Get the second element of a triple
4. Get the third element of a triple
5. Check whether the first element of a triple is 0 or 1
6. 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