Revision 677b972c-cb7b-4f28-a872-6e1157cb0658 - Code Golf Stack Exchange

#[Brachylog](https://github.com/JCumin/Brachylog)

###Factoid

Brachylog is a declarative logic programming language based on Prolog. Its name is constituted of the prefix *brachy-* (meaning *short*, from ancient greek *βραχύς*) and the suffix *-log*, to mark its link to Prolog.

###Length 1

 r

A seemingly simple program, that is useful to understand some fundamental basics about Brachylog (and declarative programming in general): Reverse something.

In Brachylog, the program `r` is a main predicate consisting of one rule (namely, `r`). All rules in Brachylog implicitely start with the Input (noted `?`) and end with the Output (noted `.`).

Therefore, our program is really `?r.`, which can be read as *Output is the reverse of the Input*. The built-in `r - Reverse` works on the three main data types of Brachylog: [lists](http://brachylog.tryitonline.net/#code=cg&input=WzE6InRlc3QiOjI6IlBQQ0ciXQ&args=Wg), [strings](http://brachylog.tryitonline.net/#code=cg&input=InRlc3Qi&args=Wg) and [integers](http://brachylog.tryitonline.net/#code=cg&input=MTIzNDU&args=Wg).

But more interestingly, it is a *relationship* that we state with `r`, not a one-way function like most programming languages. As such, `r` also works as expected [when the Output is ground and the Input is not!](http://brachylog.tryitonline.net/#code=cg&input=Wg&args=WzE6InRlc3QiOjI6IlBQQ0ciXQ) It even works if both the input and the output have no value, though that doesn't show well on the online interpreter and with a program limited to one character.

We will continues to see in the next examples that predicates in Brachylog are relationships between variables and are as such much more expressive than traditional imperative function. We can also note that the Input and Output of predicates are merely called that because that's usually how those variables are used, but those are simply names and they don't mean that for example the Input necessarily has to be a ground variable.

###Length 2

[<pre>r?</pre>](http://brachylog.tryitonline.net/#code=cj8&input=MTIzNDU0MzIx)

Now that we know that `r` is *reverse*, and that `?` is the Input, you can probably guess what this program does: test whether the input is a palindrome or not.

Indeed, `r?` is really `?r?.`, which can be read as: *Input is the reverse of the Input, and Output is the same as the Input*. Since we do not need the Output at all here, the second part of the sentence can be disregarded and we then see that it is indeed a palindromeness checking program.

The program [`.r`](http://brachylog.tryitonline.net/#code=LnI&input=&args=MTIzNDU0MzIx) would have worked the same if we passed our input through the Output variable.

###Length 3

[<pre>:^a</pre>](http://brachylog.tryitonline.net/#code=Ol5h&input=WzQ6ODoxNToxNjoyMzo0Ml0&args=Wg)

As you can see from the TIO link, the code above squares each element of the input. `^` being the squaring built-in predicate, and `a` being *Apply*, a *meta-predicate*.

In Brachylog, all predicates have only an input and an output argument. Therefore, when we need to "pass" more than one thing to the predicate, we put them in a list.

This is what we are doing with `:`, which is also the list separator. By writing `:^`, we are constructing the list `[Input, brachylog_power]`. So, just like numbers, strings and lists, we can also put *predicates* in lists.

*Apply* takes the last element of its input argument as being a predicate, and queries that predicate each time with an element of the rest of its input argument as input (hence why it is called a meta-predicate). The output of *apply* accumulates the outputs of the queries. This predicate is usually called `map` in other languages (`maplist` in Prolog).

###Length 4

[<pre>:@\[f</pre>](http://brachylog.tryitonline.net/#code=OkBbZg&input=InRlc3Qi&args=Wg)

Continuing on meta-predicates, here is `f`: *Findall*. As its name suggests, this will find all valid outputs of a predicate for a specific input.

Here, the input to *Findall* is the list `[Input, brachylog_string_prefix]`. The predicate *string_prefix* `@[` is true if its output is a prefix of the input. By running *Findall* on it, we will obtain all prefixes of `?`.

Note that the *string* in *string_prefix* only comes from the fact that it is a 2 symbols predicate which starts with `@` (which represent operations that are more often done on strings). This predicate of course doesn't only work on strings, but also on integers and lists.

###Length 5

[<pre>:Lc.r</pre>](http://brachylog.tryitonline.net/#code=OkxjLnI&input=InRlc3Qi&args=Wg) 

This is probably my favorite Brachylog program (most likely because [it is twice as short as the Jelly answer on this challenge!](http://codegolf.stackexchange.com/questions/77095/palindromizing-the-strings)). This is a program which palindromizes its input.

In Brachylog, strings and integers can contain variable characters/digits, just like how lists can contain variables as elements. Therefore, `:Lc.` means *“Output is the result of concatenating the Input and a variable `L`”*. Then, we impose with `.r` that the output reversed is still the output (thus, that the output is a palindrome). This will force Brachylog to **unify** the variable values of `L` so that the output is indeed a palindrome.

###Length 6

[<pre>:1f
~c
</pre>](http://brachylog.tryitonline.net/#code=OjFmCn5j&input=InRlc3Qi&args=Wg)

Here is another example of the use of `f - Findall` and `c - Concatenate`.
 
The first line is the main predicate and states *“Find all valid outputs of predicate 1 given the Input as input”*. The second line is predicate 1 and states `The output, when concatenated, results in the Input`.

Here, `~` is a simple control symbol which "flips" the arguments of the following predicate: `AcZ` means “`Z` is the result of concatenating the elements of `A`” whereas `A~cZ` means “concatenating the elements of `Z` results in `A`”.

Therefore the program above will find all possible lists of strings (excluding the ones containing the empty string), which when concatenated will result in the input.

Note that `~c` is not a second built-in which does the reverse of `c` ; it **is** the same as `c`, but called with swapped arguments. To convince you of this, [rewriting predicate 1 as `,.c?,` will result in the same program](http://brachylog.tryitonline.net/#code=OjFmCiwuYz8s&input=InRlc3Qi&args=Wg).

Side note: this program could have been written `:{~c}f`, which does the exact same thing. Choosing one or the other is mostly a matter of preference.

###Length 7

[<pre>:1y
\#p=</pre>](http://brachylog.tryitonline.net/#code=OjF5CiNwPQ&input=MTAw&args=Wg)

This demonstrates another meta-predicate: `y - Yield`, and a major feature of Brachylog: constraints-based arithmetic.

`y - Yield` is a meta predicate very similar to `f - Findall`, the difference between the two being that `y` will unify its output with the first `N` outputs of the queried predicate (`N` being the penultimate element of the input arguments), instead of all of the outputs. This is thus very useful for predicates that have an infinite number of choice points, such as arithmetic series.

In Brachylog, all integer arithmetic is based on **constraints**. This makes operations on integers very declarative in nature ; if we declare the relationship that `X + Y = Z` (which in Brachylog would be written as `X:Y+Z`), then this constraint will hold even if those variables have no ground value. Adding more and more constraints will keep on reducing the search space for the possible values of those variables. Then, the labeling process (using `=` in Brachylog) will assign values to variables such that they respect all constraints that were applied to them.

`#p - constraint_prime` is a predicate which constrains its input `?` (which is unified with its output `.`) such that it must be a prime number. Using `= - Equals`, we can then label that variable so that it takes a ground value. The labeling process will order choice points according to the magnitude of the values, which is why overall this program yields the first `N` prime numbers, starting from `2`.