# Sunny morning

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.

## Contents

## 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

## 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)?