rejoice

Rejoice!

Rejoice is a concatenative programming language and notation in which data is encoded as multisets that compose by multiplication. Think Fractran, without the rule-searching, or Forth without a stack.

Basics

The program state is a bag of unordered things. For example, the bag [cube cone^3] contains one cube, and three cones. The empty bag, or identity, is represented as [].
Symbols are things in the bag written as either numeric decimal integers or names representing prime values. For example, the bag [8 ball^2] and [2^3 ball ball] are equal.
Transformations are represented as fractions in which the denominator indicates things to remove from the bag, and the numerator, the things to add. For example, owl/[cat^2], means to replace two cat with one owl.

Evaluation consists of applying each fraction, when the contents of the denominator are found in the bag: these are removed from the bag and the contents of the numerator are added; otherwise the fraction has no effect. The following fraction is then tried, and so on. The program halts when there are no more fractions to apply.

[] es nihil, identitate. []/n es predecessore. n es successore.

Basics

Rejoice is a single-instruction postfix concatenative notation, read from left to right, in which fractions correspond to transformations applied by multiplication on a set of symbols.

3 4 + 2 - . ( In Forth )

n^3 n^4 []/n^2 .#n( In Rejoice )

Logic I

Logic is implemented by sequencing fractions for each possible state of the gate. For example, here is the implementation of a NOT logic gate:

false not
	true/[false not]
	false/[true not]

[false not] true/[false not] false/[true not] 
[true] false/[true not] 
[true]

The different cases are sequenced one after the other, here is a OR gate. Note the need for a sentinel or symbol.

x y or
	true/[x y or]
	true/[x or]
	true/[y or]
	false/or

[x y or] true/[x y or] true/[x or] true/[y or] false/or 
[true] true/[x or] true/[y or] false/or 
[true] true/[y or] false/or 
[true] false/or 
[true]

Lastly, here is an AND gate which also needs a sentinel symbol to capture the state when both inputs aren't present in the bag.

x y and
	true/[x y and]
	false/[x and]
	false/[y and]
	false/and

Labels

A @label is a special symbol that represents a jump target. When the corresponding label symbol enters the bag, execution continues from the @label position in the program. A conditional jump is done by inserting a label when specific things are found in the bag. The capitalization of label is merely a convention.

chores
	SkipPlay/chores
		play
	@SkipPlay

Labels allow for programs to loop and drain symbols. For example, here is the implementation of a greater comparison:

x^3 y^2

@Gth ( x y -- x y true|false )
	Gth/[x y]
	true/x Gth/x
	false/y Gth/y

[x^3 y^2] Gth/[x y] true/x Gth/x false/y Gth/y 
[x^2 y] Gth/[x y] true/x Gth/x false/y Gth/y 
[x] Gth/[x y] true/x Gth/x false/y Gth/y 
[x] true/x Gth/x false/y Gth/y 
[true] Gth/x false/y Gth/y 
[true] false/y Gth/y 
[true] Gth/y 
[true]

Anonymous Functions

Anonymous functions are operations that are retried until the denominator is no longer present in the bag. For example, the addition fraction @Add [x Add]/y, can also be written as 'x/y, telling the compiler to create a symbol at the fraction's position in the program.

x^3 y^4 'x/y

[x^3] y^4 'x/y 
[x^3 y^4] ( ) 'x/y 
[x^7]

Arithmetic

To find the difference between two values, the program removes one of each symbol until exhaustion, leaving either x for a positive result, or y for a negative result. The last two labels drain the values into either pos or neg:

x^2 y^5

@Sub ( x y -- x|y )
	Sub/[x y] 'pos/x 'neg/y

[x^2 y^5] Sub/[x y] 'pos/x 'neg/y 
[x y^4] Sub/[x y] 'pos/x 'neg/y 
[y^3] Sub/[x y] 'pos/x 'neg/y 
[y^3] 'pos/x 'neg/y 
[y^3] ( ) 'neg/y 
[neg^3]

Here's a slightly more complex program that finds the product of two numbers using multiple labels.

x^2 y^3

@Mul ( x y -- res )
	[Mul z res]/y 'y/z Mul/x '1/[y res]

And the quotient:

x^24 y^3

@Div ( x y -- res )
	[Div t]/[y x] res 'y/t [Div x]/x '1/y

I/O

Symbols that start with . will be emitted as text and immediately removed from the bag. Symbols that start with .# will emit the number of instances of that symbol in the bag. For example: A token like .bat^2 will emit batbat.

pigs^3
	( print a word ) .pigs:
	( print the count ) .#pigs

pigs:3

The supported escape sequences are: \t(tab), \s(space) and \n(linebreak). There is presently no definition for input, this is a work in progress.

FizzBuzz

This would not be complete without an example of FizzBuzz:

times^100 f b

@Loop ( times -- )
	[num f b .FizzBuzz\n Loop]/[times f^3 b^5]
	[num f b .Fizz\n Loop]/[times f^3]
	[num f b .Buzz\n Loop]/[times b^5]
	[num f b .#num .\n Loop]/times

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, 17, ..

On Optimization

There are various levels of optimizations possible, the interpreter implements one in which draining symbols with anonymous functions is done in a single step. This allows for moving or copying values from a single denominator, to any number of symbols, without having to run through each value one at a time.

c^5 '[a b]/c ( c = 5; a = b = c; )

[] c^5 '[a b]/c 
[c^5] ( ) '[a b]/c 
[a^5 b^5]

'x/a: One symbol to another.
'[x y]/a: One symbol to many symbols.
'[x^2 y]/a: One symbol to many symbol, multiple values at a time.
'[x^2 y]/a^4: Multiple values from one symbol to many symbols.

On Linear Logic

Traditional logic treats propositions as infinite, whereas linear logic accounts for resources. Rejoice is an attempt at making a linear logic playground in which every transformation equates to a transaction that consumes rules.

In Rejoice, the linear logic ! modality applies to rules, not to values. A one-shot fraction can freely duplicate or discard symbols(x^2/x), but the fraction itself is consumed after firing. Anonymous functions and the @label mechanism are what promote rules to unlimited use. This is illustrated with file handles: once file is consumed, any fraction requiring it in its denominator simply won't fire; the resource is inaccessible through absence rather than enforcement. A fraction requiring a consumed symbol doesn't crash, it just becomes dead code.

file^1
	closed/file
	read/file ( unreachable )

Labelled rules can fire indefinitely, like a vending machine accepting any number of coins. Without @VendingMachine, the rule fires once and the program ends.

coin^3

@VendingMachine ( coin -- candy )
	[VendingMachine candy]/coin

Unlike linear types in traditional programming languages like Rust or Clean, where resource tracking constrains what programmers can do with values, in Rejoice linearity governs rules. Entities don't persist because they're protected, but because nothing consumed them.

On Fractran

A Fractran program can be thought of as a Rejoice program with a single label at the top. For example, the Fractran program: 225, 7/3, 7/5

r3^2 r5^2

@Fractran ( r3 r5 -- r3+r5.r7 )
	[Fractran r7]/r3
	[Fractran r7]/r5

[r3^2 r5^2] [Fractran r7]/r3 [Fractran r7]/r5 
[r3 r5^2 r7] [Fractran r7]/r3 [Fractran r7]/r5 
[r5^2 r7^2] [Fractran r7]/r3 [Fractran r7]/r5 
[r5^2 r7^2] [Fractran r7]/r5 
[r5 r7^3] [Fractran r7]/r3 [Fractran r7]/r5 
[r5 r7^3] [Fractran r7]/r5 
[r7^4] [Fractran r7]/r3 [Fractran r7]/r5 
[r7^4] [Fractran r7]/r5 
[r7^4]

Source, Uxntal.
Repository, Uxntal.
Read a translation in Peano's Latino Sine Flexione.
Multiset Languages: Fractran, Bägel.

incoming: multisets tropical arithmetic latino sine flexione concatenative fractran bagel 2026