# int**

Paradigm(s) Imperative, Functional Hakerh400 2020 Uncomputable Partial implementation (WIP) `.txt`

int** is a programming language that allows you to work with different arithmetical hierarchies.

## Overview

Syntax is similar to C++, but the semantics are totally different.

Only built-in types are allowed and they are `bool`, `int` and pointers to `int` (`int*`, `int**`, `int***`, etc). Pointer is not a good name for `int*` in this language, because here it does not mean what it means in C++.

### Boolean type

Boolean type is denoted as `bool` and can have only two different values: `true` and `false`. It can be used in if/while statements and in logical operations such as `&&` and `||`.

Pointers to boolean type are not allowed.

### Integer type

Denoted as `int`. It represents a signed integer of arbitrary size. There are no constraints regarding the size of the integer, but it must be finite. You cannot construct an infinitely large integer.

All standard arithmetic operations are allowed on integers (addition, subtraction, multiplication, division, bitwise operations, etc).

Variables of type `int` can be initialized with literal integer constants. Example:

```int x = 5;
```

It is possible to compare `int` values:

```int x = 1 + 2;
int y = 3;
x == y; // true
```

### Type int*

Type `int*` represents a mapping from the set of all `int` values to itself. Since there are infinitely many different `int` values, the set of all `int` values is infinite in size (although it is enumerable). There is no length of the `int*`, because it is infinite in size. The set of all `int*` values is not enumerable.

All `int*` values (unlike in C++) are primitives, so if variables `A` and `B` are both of type `int*`, assigning `A` to `B` and then modifying `B` (or any element of `B`) will not modify `A` (and vice-versa).

Variables of type `int*` can be initialized only using a function which maps `int` to `int`. For example:

```int f(){
int* x = g;
return x;
}

int g(int n){
return n + 7;
}
```

In the example above, function `f` returns `10` because `x` is initialized with the mapping represented as function `g`. Variable `x` is equal to `[..., 7, 8, 9, 10, 11, 12, 13, 14, 15, ...]`. Then we return the third element of it, which is `10`.

Note: `int*` is unlimited in both directions (both positive and negative indices are allowed). We only show positive indices for simplicity, but there are also indices `-1`, `-2`, `-3`, etc. Variable `x` is actually:

```[..., -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...]
^
|
Index 0
```

It is also allowed to modify any index of the `int*` type. For example:

```int* x = g;
x = 100;
// Now x is equal to [..., 7, 8, 9, 10, 11, 100, 13, 14, 15, ...]
```

Modifying an index will not modify function `g` nor will it modify any source of the initialization of the variable `x`. Example:

```int* x = g;
int* y = x;
x = 100;
y = 200;
// x: [..., 7, 8, 9, 10, 11, 100, 13, 14, 15, ...]
// y: [..., 7, 8, 9, 10, 11, 12, 200, 14, 15, ...]
```

It is also possible to compare `int*` types:

```bool test(){
int* x = f1;
int* y = f2(x);
return x == y; // true
}

int f1(int n){
return 0;
}

int f2(int param, int n){
if(n == 0) return 0;
return param == n ? 1 : 0;
}
```

Explanation: in this example we also see parametrized initialization. `x` is initialized with function `f1` and it contains all zeros. However, `y` is initialized with parametrized function `f2` (we pass `x` (which is `0`) as the parameter). All arguments except the last one are parameters. It is also the difference between function call and `int*` initialization: we call function with one argument less than the actual number of formal arguments that the function takes.

Then we initialize `y` with all zeros (because `param` is `0` and all indices map to `0` if they are different from `param`, and in case of `0` it returns `0` unconditionally, so it also has all zeros, like `x`). Therefore, `x` and `y` are equivalent.

### Type int**

`int**` is a mapping from `int*` to `int*` (unlike in C++ where it is a mapping from `int` to `int*`). Indices must be of type `int*`. Initialization can be done using a function which maps `int*` to `int*`. Example:

```bool test(){
int* x = f(); // We can also omit parentheses, so f also works
int** y = g;

return y[x] == 0; // true
}

int f(int n){
return 0;
}

int* g(int* n){
return f;
}
```

Like `int*`, variables of type `int**` (and also all higher pointers) are primitives and they are always copied and transfered by-value and never by-reference. It is not possible to modify one variable throught other.

### Higher integer pointers

Type `int` can be followed by any number of `*` symbols. The pattern is the same: type `int***` is a mapping from `int**` to `int**`, type `int****` is a mapping from `int***` to `int***`, etc.

### Functions

Functions must not have side-effects. This is an illegal code:

```int x = 0;
int* y = f;

int f(int n){
return x++;
}
```

because it violates constraint that all variables of `int` type must be finite. Function `f` used as the initialization for variable `y` will be caled infinitely many times, so `x` will no longer be finite, because it will be incremented on each call.

Therefore, global variables, nested function and side-effects are forbidden. All functions are pure and their result depends only on the arguments.

## I/O format

Implementation-dependent. One idea is to represent input as a value of `int*` type and fill indices from `0` to the `n - 1` (where `n` is the length of the input) with ASCII codes of the corresponding input characters, while all other indices maps to value `0`.

## Computational class

It is uncomputable on a Turing-machine. Determining whether two `int*` (and higher) values are equal (which can be either explicit comparison `x == y`, or implicit `x[y1] = z; x[y2] == 0`) is not possible on a standard Turing-machine. However, a partial approximation implementation is still possible.

The interpreter provided works in some cases, but it may never halt if it is unable to prove that two values are equivalent.

For questions regarding consistency and value comparison, see the talk page.

## Interpreters

Partial implementation (WIP, works only for computable programs).