Caballo

Caballo is a programming language made by User:CatIsFluffy in 2021. It was inspired by the discussion in Cabra's talk page about an alternative interpretation of the parallel composition operation in terms of pairs, and (some of) its programs form an algebraic ring.

Description

A Caballo program's data is stored as a mapping from lists of natural numbers (treated as stacks) to integers. The initial mapping maps the input (interpreted as a stack) to 1, and everything else to 0.

The following commands are specified as operations mapping stacks to stacks. The mapping resulting from one of these commands, when accessed at a particular stack, is the sum of the original mapping's outputs for all stacks which, after applying the operation, result in the provided stack. For example, the ! operation applied to {[1]:1,[2]:2} is {[]:3}. Note that if the mapping is empty all of these commands are no-ops, and thus can be skipped. Stacks are considered to have infinitely many zeros at their bottoms, and any zeros at the bottom of the stack disappear.

Command	Operation
p	Pop the top of the stack.
q	Push a 0.
i	Increment the top stack element.
d	Decrement the top stack element. If this would result in a negative number, ignore this stack for the result calculation.
1	Do nothing.
2,3...9	Swap the top stack element with the second, third,..., ninth stack element.

The following commands directly manipulate the mapping.

Command	Operation
(x+y+...)	Run each of x, y, etc on a copy of the mapping, then add the outputs elementwise.
[x]	Run (1+x[x]).
0	Empty the mapping.
-	Negate the mapping.

At the end of the program, all input/output pairs in the mapping with negative output are discarded, and then a randomly selected input stack is send to standard output, weighted by its output in the mapping. If after the discarding the mapping is empty, nothing is output.

Examples

Zero test

   (1+di-)

If the top stack element is 0, the d in the second branch fails and suppresses that branch's effect. Otherwise, it is cancelled by the i and the - makes the branches cancel each other in the final mapping.

Conditional

   (dix+(1+di-)y)

If the d fails, then the first branch and the di- become irrelevant and y runs. Otherwise, x runs, and the (1+di-) prevents y from running.

Addition

   [d2i2] (1+di-)p

The first part converts {[2,1]:1} to {[2,1]:1,[1,2]:1,[0,3]:1}, and the second part eliminates all the outputs except [0,3]:1 and pops the 0. This is a common pattern when using [x]. This pattern can be used to iterate any program that does not use 2, by replacing the i with another program.

Pairing function

   q2[d2ii2](1+di-)pi q3[d32[d2ii2](1+di-)3](1+di-)pp

The first part doubles and increments the top stack element. The second part doubles the top stack element (second stack element) times. An unpairing function is left as an exercise for the reader.

Lookup table

   ((1+di-)x|d(1+di-)iy|dd(1+di-)iiz|...)

This structure allows you to choose a code segment to run based on the top stack element. It's somewhat similar to Burro's conditional chains, except that Burro's conditionals use multiplication instead of addition, and require code repetition because Burro has no analogue of the distributive property.

Algebraic structure

The main property of Caballo is that always-halting programs form a ring (with 0 and 1 as units, (x+y) as addition, concatenation as multiplication, and - as -1). For example, for always-halting x and y, the conditional can be rewritten as (y+di(x+-y)). These axioms apply to other programs as well, except that nonterminating inputs may be introduced or removed by some of the axioms (notably right distributivity). For the ring axioms to hold for all programs, the language's ability to express nonterminating programs would have to be removed. Turing completeness can be preserved by adding an external loop as in Burro or some other esolangs, but for this language I would rather avoid such a discrepancy between the semantics of program snippets and whole programs. Additionally, the below observation requires a nontermination-capable looping construct.

Another interesting observation is that [x], applied in a skewfield, produces 1/(1-x). To a limited extent, this also works in Caballo. For example, the ring identities and definition of [x] can be used to prove that ([-1]+[-1])=1. Of course, this doesn't work in practice, since [-1] is nonhalting and so the ring identities do not hold for it, but it is still worth noting.

This language, or at least an always-halting relative, disproves a conjecture by Chris Pressey from the Cabra reference distribution that any addition operation in a programming language satisfying the ring axioms cannot use both of its inputs' outputs simultaneously in its own output.

Computational class

A register machine with a small number of registers can be straightforwardly converted to Caballo. Thus, it is Turing complete. The conversion uses the above lookup table structure, with each entry being one of the following:

   Decrement the nth stack element and jump to m if successful  n(dnpq{(i)^m}+(1+di-)ni)
   Increment the nth stack element                              nin
   Halt                                                         0