Conglument

Conglument

Paradigm(s)	Functional
Designed by	User:Hakerh400
Appeared in	2020
Computational class	Turing complete
Major implementations	Interpreter
File extension(s)	.txt

Conglument is an esolang that literally follows the definition of general recursive functions.

Overview

This programming language literally follows the definition of general recursive functions. However, instead of operating on integers, this programming language operates on strings of bits. A string of bits consists of zero or more bits (a bit is 0 or 1).

This is a functional programming language. There are 6 different ways to construct a function: 3 basic functions and 3 functional operators. All functions are $S^{n}\to S$, where $S$ is the set of all strings of bits. Some functions may be partial. A function cannot be an argument to an other function.

Functions can be combined via functional operators by simply writing all the functions that represent the operands for the operator. That is, there are no explicit structures: you simply write all the functions in a row and the interpreter figures out which function belongs to which operator based on the arity.

Each function has arity. Arity is the number of arguments the function takes. Arity usually can be deduced from the arities of the operands (in case of functional operators). If it cannot be deduced implicitly, arity must be specified explicitly (and there is just one such case, which is explained below).

Syntax

Whitespace is ignored. Literally ignored. Even if appear in the middle of a number or an identifier (identifiers are just syntactic sugar, see below). All numbers and identifiers are by default single-char (so 12 represents two numbers 1 and 2, instead of single number 12). Multi-char numbers and identifiers can be achieved by prepending backslash before them (so \123 is number 123 and not three numbers 1, 2 and 3). But, since whitespace is ignored, \12 3 is still number 123. In order to get 12 and 3, you need two backslashes: \12\3.

A full function in the source code is either a basic function, or a functional operator followed by a number of other full functions such that there are enough operands for that operator.

Identifiers can be used to name functions that are used in multiple places in the source code, so that we do not need to copy-paste them. The first time an identifier appears, it represents a definition for that identifier. Other times it represents a reference to the function from the definition of that identifier. Definition is just an identifier followed by a full function. Definition is also a reference at the same time, so the function literally appears where it is defined.

Recursive identifier definition is not allowed, but also it is not a syntax error. Instead, it shadows the previous identifier name. Identifiers cannot be redefined. Note that identifiers do not have any meaning in the runtime, they are just syntactic sugar.

Functions

In mathematical formulas, we denote the empty string by $\epsilon$ and string concatenation by $+$ (infix binary operator). Note that concatenation is not commutative.

Basic functions

There are 3 basic function: Empty string, Prefix and Projection.

Empty string

Denoted by .n where $n$ is the number of arguments the function takes. Mathematically, it is $f\left(x_{1},\dots ,x_{n}\right)=\epsilon$. The arity of this function is $n$.

Prefix

Denoted by either +0 or +1. The first one represents function $f(x)=0+x$ (here 0 is a string containing single bit 0), while second one represents function $f(x)=1+x$ (here 1 is a string containing single bit 1). That is, this function prepends a single bit before the argument. The arity of this function is $1$.

Projection

Denoted by %mn where $m$ is the number of arguments the function takes and $n$ is the index (0-indexed) of the argument it returns as the result. Mathematically, it is $f\left(x_{1},\dots ,x_{m}\right)=x_{n+1}$ (here $n+1$ is because of 0-indexing and we started from $x_{1}$ in our formula). The arity of this function is $m$.

Functional operators

There are 3 functional operators: Composition, Recursion and Minimization.

Composition

Denoted by ~ followed by an appropriate number of full functions (operands for this functional operator). It takes exactly $1+n$ operands, where $n$ is the arity of the first operand (so it must take at least one operand). In general: ~ a b1 b2 ... bn, where a, b1, b2, ..., bn are full functions and $n$ is the arity of a. All functions b must have the same arity. Let's say that the arity of each b is $m$. The arity of the composition is $m$.

Mathematically, the result of the composition is $f\left(x_{1},\dots ,x_{m}\right)=a\circ \left(b_{1},\dots ,b_{n}\right)=a\left(b_{1}\left(x_{1},\dots ,x_{m}\right),\dots ,b_{n}\left(x_{1},\dots ,x_{m}\right)\right)$.

There is a special case when a is a nullary function (takes no arguments). In that case, there are no b function, so we cannot determine the arity of the composition. In that case, the arity must be specified explicitly by putting a number after the ~ sign and it represents the arity of the composition. However, it is not allowed to define the explicit arity if it turns out that the first operand of the composition is not a nullary function (that is a syntax error).

Consider this example: ~ +1 .0. In this example, a is +1, b1 is .0, $n$ is $1$ and $m$ is $0$. This composition represents the function $f()=1+\epsilon$.

Another example: ~ %21 %30 %32. Function %21 is $f_{1}\left(x,y\right)=y$, function %30 is $f_{2}\left(x,y,z\right)=x$, and function %32 is $f_{1}\left(x,y,z\right)=z$. So, the whole composition is

${\begin{aligned}f\left(x,y,z\right)&=f_{1}\circ \left(f_{2},f_{3}\right)\\&=f_{1}\left(f_{2}\left(x,y,z\right),f_{3}\left(x,y,z\right)\right)\\&=f_{1}\left(x,z\right)\\&=z\end{aligned}}$

One more example: ~ ~ %10 .1 ~ %10 ~ +0 .1. This is an example that shows how "full functions" work. Basically, we cannot say that the second ~ is the first operand for the first ~, because the second ~ alone does not represent a full function. But, ~ %10 .1 does represent a full function. It would be easier to write it in a more structured manner:

~
  ~
    %10
    .1
  ~
    %10
    ~
      +0
      .1

This is the same code, but with proper indentation. Now we can clearly see that the top composition has two operands, one being ~ %10 .1 and the other being ~ %10 ~ +0 .1. The arity of the top composition is $1$ and it is equivalent to $f(x)=\epsilon$ (after simplification).

Just one more example: ~1 .0. In this example, the first argument of the composition is .0, which is a nullary function. Therefore, the number $1$ from ~1 represents the explicit arity of the composition. So, the composition takes one argument (and ignores it), and then calls .0 with no arguments.

Recursion

Denoted by - followed by three full functions. For example - a b c. The arity of b and c must be equal and it also must be by $2$ larger than the arity of a. The arity of the recursion is by $1$ larger than the arity of a.

Let's say that the arity of a is $n$. The recursion is defined as:

$f\left(s,x_{1},\dots ,x_{n}\right)={\begin{cases}a\left(x_{1},\dots ,x_{n}\right),&s=\epsilon \\b\left(y,f\left(y,x_{1},\dots ,x_{n}\right),x_{1},\dots ,x_{n}\right),&s=0+y\\c\left(z,f\left(z,x_{1},\dots ,x_{n}\right),x_{1},\dots ,x_{n}\right),&s=1+z\end{cases}}$

where $y$ and $z$ are some strings of bits.

Minimization

Denoted by * followed by one full function. In general: * a. Let's say that the arity of a is $n$. The arity of the minimization is $n-1$ (note that a cannot be nullary).

Instead of writing a mathematical formula, here is a pseudocode showing how minimization works:

minimize (func) {
  strings = new Queue() // FIFO structure
  strings.push(ε)

  while (true) {
    if (strings.isEmpty()) {
      // At this point we know for sure that
      // the minimization does not halt.
      // Either display a warning, or simply
      // enter an infinite loop.
      while (true) {}
    }

    str = strings.pop()
    result = func(str)

    if (result starts with 1) {
      return str
    }

    if (result == ε) {
      strings.push(str + 0)
      strings.push(str + 1)
    }
  }
}

Basically, we start calling the function (argument of the minimization) with all possible binary strings (ε, 0, 1, 00, 01, 10, 11, 000, ...), until the function returns a string that starts with 1, in which case we return the last string. If the function returns a string that starts with 0, it means that the last string that we checked cannot be a prefix of a string for which the minimization may halt. So, for example, if we called func with 01 and the function returned 0, then we ne longer check strings that have prefix 01. That is also the reason why we do not check for the case result starts with 0 in the pseudocode (because we removed the string from the queue and we added nothing to it).

Syntactic sugar

Identifiers

Identifiers can be used to name functions and then reference them. The first appearance of an identifier is a definition and other appearances are references. A definition consists of an identifier followed by a single full function.

For example, ~ %10 %10 can be transformed into ~ a%10 a. Here, a%10 represents definition of identifier a and then a is the reference to %10.

Another example:

~
  ~ %10 %10
  ~ %10 %10

It can be transformed into:

~
  ~ b%10 b
  ~ b b

and then:

~
  a ~ b%10 b
  a

which is ~a~b%10ba when we remove whitespace.

Multiple identifiers can be used as aliases. For example: ~ abc%10 b. Here, a, b and c all represent function %10.

Multi-character identifiers can also be used: ~ \xyz %10 \xyz. Note that, in general, \a is identical to a (it is the same identifier).

Scopes

Scopes are syntactic sugar. A scope is represented by a pair of parentheses containing a single full function. All the identifiers that are defined in a scope will not be accessible outside the scope. Also, identifiers from a scope cannot access identifiers from the surrounding scopes. Scopes can be nested.

Example:

~
  (~ a%10 (a%20))
  (~ a%10 a)
  (~ a%10 a)

The above example is equivalent to ~~a%10%20b~aab.

I/O format

Input and output are strings of bits. The main function (the top full function from the source code) must be unary (takes exactly one argument). The main function is called with the input of the program and the result is the output of the program.

Total and partial functions

All basic functions are total. The only way to construct a partial function is via minimization (optionally in combination with other operators). However, the requirements for a function to be total differ a bit from the conventional requirements.

For example, the conventional definition says that a composition is total iff all their operands are total. In this language, that is not the case. For example, in the following snippet ~ %20 .0 X (where X is a partial function), the composition is actually a total function, because according to %20, we only need the first argument (which is .0), so the second argument X is not even evaluated.

There are some other cases when a function obtained from a functional operator is total even if some operands of the operator are partial. For example, a recursion does not need to be fully expanded. If it turns out that the result is already known (for example due to a projection picking up a constant argument), we can stop expanding the recursion and just return the result.

Also, one particularly complicated case is the minimization. Since we may know in advance that some prefixes can be eliminated from further search, if all remaining strings in the queue have the same prefix, we may go one stack frame back and check whether that information can be used to cut some recursion or another minimization. The official interpreter has all these optimization tricks implemented.

Examples

We do not explain these examples. See the interpreter for details.

Output empty string

.1

Cat program

%10

Invert bits

-.0~+1a%21~+0a

Reverse string

-a.0~-~b+0ac~bd%21e~f+1dd~-~faced

Remove the first bit

-.0a%20a

Remove the last bit

~-a.0b.2c%20-~d+0a~e+1~-ab~dcf%21~e~-ab~ecf

Truth-machine

-.0~a+0b.2*-b~ac.4~+1c

Duplicate string

~-a%10~+0b%31~+1baa

Escape string

Prepend 1 before each bit and append 0 after the string.

-~a+0.0~b+1~ac%21~b~bc

Unescape string

Opposite of the previous example. Escaping and unescaping can be used in a recursion to combine multiple strings into a single argument.

~-a.0b%20b~-c%10~-a~d+1e~f+0b~f.2g%31~-a~d~dbegc~-~fah~-a~di%21~fiihc

Remove zeros

-.0a%21~+1a

Remove ones

-.0~+0a%21a

Output 1 iff the input has odd length

-~a+0b.0c~-b~+1d%21~addc

Extract the first bit

-.0~+0a.2~+1a

Extract the last bit

~-a.0~b+0c.2~d+1c-a~-~bae~bf%21g~dff~-~daegf

Remove zeros from the beginning

-.0%21~+1%20

Increment binary number

~-a.0b%21c~d+1e%20~-aec-~da~-a~f+0g~feh~fcb~-ah~dgb

Decrement binary number

~-a.0b%21c~d+1e%20~-aee-~da~-af~g+0~ge~dcb~-a~gcfb

Output 1 iff the input is a palindrome

~~-a+1b~-c.0d~e+0.2~-f~ac~-g~ech~ai%20dj~k-c~-gl~em%21n~amm~-flnmi~-gdhjio%31bp~-q%10~eo~ao~r-g~al~a
ni~k~rmpq~kq

Alternative solution (different approach):

 ~--a~b+1c.0d~e+0f.2d~g~h-f%42%43~~~hi%20j%21i~k~-bl~-cd~-a~-m~ecn~bido~p-c~-mq~ejr~bjj~-aqrji~-mdnoi
 s%31lt~u-v%10~es~bs~w-m~bq~bri~p~wjtj~uoi~kj~uo~-ciiix%30y%32s~b.3~exsy~g~bxsyvv

Snippets

Here are some useful code snippets.

Concatenate two strings

-a%10~+0b%31~+1b

Combine two strings into a unique pair

~-a%10~b+0c%31~d+1c~e-f~bg.0~dh~bi%21~dj~di%20~-g~-fhji~-~dghji~ei

Get the first element of a pair

~-a.0b%20b~-c%10~-a~d+1e~f+0b~f.2g%31~-a~d~dbegc~-~fah~-a~di%21~fiihc

Get the second element of a pair

~~-a.0b%20b~-c%10~-a~d+1e~f+0b~f.2g%31~-a~d~dbegc~-h~fai~-aj~dk%21l~fkkic-a~-hljk~-~daljk

Truth test

Takes three arguments. If the first bit of the first argument is 0, returns the second argument, otherwise returns the third argument.

-.2%42%43

Equality

Returns 1 iff the two given arguments are equal.

~-a+1b~-c.0d~e+0.2~-f~ac~-g~ech~ai%20dj~k-c~-gl~em%21n~amm~-flnmi~-gdhjio%31bp~-q%10~eo~ao~r-g~al~an
i~k~rmp

Interpreters

Interpreter