Semper dissolubilis

Semper dissolubilis is a programming language that allows you to use types and objects without defining them.
== Overview ==
The only two things in this programming language are types and functions. You define functions explicitly, but you do not define types in any way. Interpreter figures out what are types and what are functions. The same part of the source code may represent both function call and object instantiation. It depends on the context and arguments.
Source code consists of zero or more function definitions. Each definition has left side and right side, separated by a colon. Both on the left side and on the right side an expression must appear.
Expression is simply an identifier followed by optional arguments. For example, this is an expression:
 a(b, c)
It means: function a is called with arguments b and c. It also can mean that type a is constructed with attributes b and c.
This is a function definition:
 a(b, c): d(e, f)
It means: everytime a(b, c) appears somewhere, it will be replaced with d(e, f). Parametrized arguments are also allowed:
 a(&b, &c): d(b, c)
It means: everytime a(&b, &c) appears somewhere, but &b and &c means anything, it will be replaced with d(b, c), where b and c match &b and &c, respectively.
Destructuring and overloading are also allowed:
 a(b(&c), &d): d
 a(b(&c, &d), f): a(b(c), f)
Omitting arguments (like in f) is equivalent to empty arguments f().
== 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 we construct the following expression:
 firstBit(secondBit(thirdBit(fourthBit(...))))
where firstBit, secondBit, thirdBit, etc, are bits of the obtained input bit array. For example:
 1(1(1(0(1(0(...))))))
Then call the main function with that bit array:
 main(1(1(1(0(1(0(...)))))))
and extract the bits from the returned value of the main function. Use the same I/O format to reconstruct the output.
== Basic examples ==
=== Cat ===
Program:
 main(&x): x
Explanation:
It simply returns the input bit array.
=== Invert bits ===
Program:
 main(1(0(&x))): 1(1(main(x)))
 main(1(1(&x))): 1(0(main(x)))
 main(0(&x)): 0(x)
Explanation:
It uses destructuring to detect 0s and 1s. Then it inverts the bit and recursively calls main with the remaining bits.
=== Reverse bits ===
Program:
 main(&x): reverse(x, eof)
 reverse(1(0(&x)), &y): reverse(x, 1(0(y)))
 reverse(1(1(&x)), &y): reverse(x, 1(1(y)))
 reverse(0(&x), &y): y
 eof: 0(eof)
Explanation:
It keeps track of two arrays. Iteratively pops from one and pushes to the other. When reaches the end of the first array, returns the second one.
== Advanced examples ==
=== Add two big integers ===
Program:
 main(&x):
 write(int2str(add(strs2ints(split(read(x))))))
 
 strs2ints(Pair(&str1, &str2)):
 Pair(str2int(str1), str2int(str2))
 
 str2int(&str): str2int(str, 0n)
 str2int(Pair(&char, &rest), &result):
 str2int(rest, add(mul(result, 10n), char2int(char)))
 str2int(null, &result): result
 
 char2int(Pair(&x, &y)): char2int(x, 4n)
 char2int(Pair(&x, &y), &mult):
 add(
 char2int(x, shr(mult)),
 mul(char2int(y, shr(mult)), mult)
 )
 char2int(0, &mult): 0n
 char2int(1, &mult): 1n
 
 int2str(null): Pair(int2char(0n), null)
 int2str(&int): int2str(int, null)
 int2str(&int, &str):
 if(neq(int, null),
 int2str(
 div(int, 10n),
 Pair(int2char(mod(int, 10n)), str)
 ),
 str
 )
 
 int2char(&int): Pair(int2char(int, 4n), int2char(3n, 4n))
 int2char(&int, Pair(0, &mult)):
 Pair(
 int2char(mod(int, shl(mult)), mult),
 int2char(div(int, shl(mult)), mult)
 )
 int2char(null, Pair(1, null)): 0
 int2char(Pair(1, null), Pair(1, null)): 1
 
 cmp(Pair(&x, &y)): cmp(x, y)
 cmp(&x, &y): cmp(x, y, 1, 0, 0)
 cmp(Pair(&x1, &y1), Pair(&x2, &y2), &eq, <, >):
 cmp(
 y1, y2,
 and(eq, eq(x1, x2)),
 or(and(not(x1), x2), and(lt, eq(x1, x2))),
 or(and(x1, not(x2)), and(gt, eq(x1, x2)))
 )
 cmp(Pair(&x, &y), null, &eq, <, >):
 Pair(0, Pair(0, 1))
 cmp(null, Pair(&x, &y), &eq, <, >):
 Pair(0, Pair(1, 0))
 cmp(null, null, &eq, <, >):
 Pair(eq, Pair(lt, gt))
 
 lt(Pair(&x, &y)): lt(x, y)
 gt(Pair(&x, &y)): gt(x, y)
 le(Pair(&x, &y)): le(x, y)
 ge(Pair(&x, &y)): ge(x, y)
 lt(&x, &y): fst(snd(cmp(x, y)))
 gt(&x, &y): snd(snd(cmp(x, y)))
 le(&x, &y): or(lt(x, y), eq(x, y))
 ge(&x, &y): or(gt(x, y), eq(x, y))
 
 inc(&x): add(x, Pair(1, null))
 dec(&x): sub(x, Pair(1, null))
 
 shl(Pair(&x, &y)): Pair(0, Pair(x, y))
 shl(null): null
 
 shr(Pair(&x, &y)): y
 shr(null): null
 
 add(Pair(&x, &y)): add(x, y)
 add(&x, &y): add(x, y, 0, null)
 add(Pair(&x1, &y1), Pair(&x2, &y2), &carry, &result):
 add(
 y1, y2,
 if(carry,
 or(x1, x2),
 and(x1, x2)
 ),
 Pair(xor(xor(x1, x2), carry), result)
 )
 add(Pair(&x, &y), null, &carry, &result):
 add(y, null, and(x, carry), Pair(xor(x, carry), result))
 add(null, Pair(&x, &y), &carry, &result):
 add(Pair(x, y), null, carry, result)
 add(null, null, &carry, &result):
 reverse(if(carry, Pair(1, result), result))
 
 sub(Pair(&x, &y)): sub(x, y)
 sub(&x, &y): sub(x, y, 0, null)
 sub(Pair(&x1, &y1), Pair(&x2, &y2), &carry, &result):
 sub(
 y1, y2,
 if(x1,
 and(x2, carry),
 or(x2, carry)
 ),
 Pair(xor(xor(x1, x2), carry), result)
 )
 sub(Pair(&x, &y), null, &carry, &result):
 sub(
 y, null,
 and(carry, not(x)),
 Pair(xor(x, carry), result)
 )
 sub(null, null, 0, &result): reverse(trim(result))
 
 mul(Pair(&x, &y)): mul(x, y)
 mul(&x, &y): mul(x, y, null)
 mul(Pair(&x, &y), &z, &result):
 mul(
 y,
 shl(z),
 if(x,
 add(result, z),
 result
 )
 )
 mul(null, &x, &result): result
 
 div(Pair(&x, &y)): div(x, y)
 div(&x, &y): fst(div(reverse(x), y, 0n, 0n))
 div(Pair(&x, &y), &d, &q, &r):
 divAux(
 y, d, q,
 add(shl(r), if(x, 1n, 0n))
 )
 divAux(&n, &d, &q, &r):
 if(ge(r, d),
 div(n, d, Pair(1, q), sub(r, d)),
 div(n, d, shl(q), r)
 )
 div(null, &d, &q, &r): Pair(q, r)
 
 mod(Pair(&x, &y)): div(x, y)
 mod(&x, &y): snd(div(reverse(x), y, 0n, 0n))
 
 pow(Pair(&x, &y)): pow(x, y)
 pow(&x, &y): pow(x, y, 1n)
 pow(&x, Pair(&y, &z), &result):
 pow(x, dec(Pair(y, z)), mul(result, x))
 pow(&x, null, &result): result
 
 trim(Pair(0, &x)): trim(x)
 trim(Pair(1, &x)): Pair(1, x)
 trim(null): null
 
 0n: null 1n: inc(0n) 2n: inc(1n) 3n: inc(2n)
 4n: inc(3n) 5n: inc(4n) 6n: inc(5n) 7n: inc(6n)
 8n: inc(7n) 9n: inc(8n) 10n: inc(9n) 11n: inc(10n)
 
 isSpace(&x): not(fst(fst(snd(x))))
 
 split(&str): split(str, null)
 split(Pair(&char, &rest), &str):
 if(
 isSpace(char),
 Pair(reverse(str), rest),
 split(rest, Pair(char, str))
 )
 
 join(Pair(&x, &y)): join(x, y)
 join(&x, &y): join(x, y, null)
 join(&x, &y, &str): prepend(prepend(str, y), x)
 
 unshift(&str, &x): Pair(x, str)
 push(&str, &x): reverse(Pair(x, reverse(str)))
 
 prepend(&str, &x): prepend(str, reverse(x), 1)
 prepend(&str, Pair(&x, &y), 1): prepend(Pair(x, str), y, 1)
 prepend(&str, null, 1): str
 
 fst(Pair(&x, &y)): x
 snd(Pair(&x, &y)): y
 
 if(0, &x, &y): y
 if(1, &x, &y): x
 
 not(&x): if(x, 0, 1)
 or(0, &x): x
 or(1, &x): 1
 and(0, &x): 0
 and(1, &x): x
 xor(&x, &y): not(eq(x, y))
 
 eq(Pair(&x, &y)): eq(x, y)
 eq(Pair(&x1, &y1), Pair(&x2, &y2)): and(eq(x1, x2), eq(y1, y2))
 eq(Pair(&x, &y), null): 0
 eq(null, Pair(&x, &y)): 0
 eq(null, null): 1
 eq(0, &x): not(x)
 eq(1, &x): x
 
 neq(Pair(&x, &y)): neq(x, y)
 neq(&x, &y): not(eq(x, y))
 
 swap(Pair(&x, &y)): Pair(y, x)
 
 reverse(&str): reverse(str, null)
 reverse(Pair(&char, &rest), &str):
 reverse(rest, Pair(char, str))
 reverse(null, &str): str
 
 read(1(&x)):
 Pair(read(1(x), b8), read(skip(1(x), b8)))
 read(0(&x)): null
 b8: 1(1(1(0)))
 
 read(&x, 1(&y)):
 Pair(read(x, y), read(skip(x, y), y))
 read(1(0(&x)), 0): 0
 read(1(1(&x)), 0): 1
 read(0(&x), 0): 0
 
 skip(&x, 1(&y)): skip(skip(x, y), y)
 skip(1(0(&x)), 0): x
 skip(1(1(&x)), 0): x
 skip(0(&x), 0): eof
 
 write(&x): write(x, eof)
 write(Pair(&x, &y), &str):
 write(x, write(y, str))
 write(0, &str): 1(0(str))
 write(1, &str): 1(1(str))
 write(null, &str): str
 
 eof: 0(eof)
Explanation:
Input is a string containing two non-negative decimal integers, separated by a space. This program reads the integers, adds them and outputs the result in decimal.
Usage:
Input: 91786213054648993581521967910921680940913000343861935857201380160344997705962750307255326176796576033524717009614238760075172425684200860804144105964721514716499805544065667651494 950344094593606271019968417196569446314035272998030841482919336381983775703214756358469341448529580283034578348171450747408349814962923884756452900751996020309117549268332354437638410863947501621
Output: 950344094593606362806181471845563027836003183919711782395919680243919632904594916703467047411279887538360755144747484272125359429201683959928878584952856824453223513989847070937443954929615153115
== Interpreters ==
Interpreter
Category:Languages
Category:Turing complete
Category:Implemented
Category:2020
Category:Functional paradigm
Category:Object-oriented paradigm
Category:String-rewriting paradigm