int**
| Paradigm(s) | Imperative, Functional |
|---|---|
| Designed by | Hakerh400 |
| Appeared in | 2020 |
| Computational class | Uncomputable |
| Major implementations | Partial implementation (WIP) |
| File extension(s) | .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[3];
}
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[5] = 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[5] = 100; y[6] = 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[0]);
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[0] (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] == 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] == 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).