# Sunny morning

Paradigm(s) Functional Hakerh400 2020 Category:Turing complete Interpreter `.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
```

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