Semper dissolubilis

From Esolang
Jump to navigation Jump to search
Semper dissolubilis
Paradigm(s) Functional, Object-oriented, String-rewriting
Designed by Hakerh400
Appeared in 2020
Computational class Category:Turing complete
Major implementations Interpreter
File extension(s) .txt


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, &lt, &gt):
  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, &lt, &gt):
  Pair(0, Pair(0, 1))
cmp(null, Pair(&x, &y), &eq, &lt, &gt):
  Pair(0, Pair(1, 0))
cmp(null, null, &eq, &lt, &gt):
  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

References

Template:Reflist