Rejoice!

Rejoice is a concatenative programming language 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^2] 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.

Rejoice is a single-instruction postfix 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 )

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 the program counter reaches the end of the program.

Logic

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 symbol, or, that persists through each case, without which, the false case could not be reached.

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

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

Variable Exponents

Variable exponents are symbols used as the exponent value in a fraction. Their value is resolved when the fraction is evaluated, for example, to find the sum of two values, the program creates as many instances of x as there are of y, and then drain the left-over instances of y:

x^2 y^5
	x^y
	[]/y^y

[x^2 y^5] x^y []/y^y 
[x^7 y^5] []/y^y 
[x^7] 

To find the difference between two values, the program removes as many instances of x as there are of y:

x^5 y^2
	[]/x^y
	[]/y^y

[x^5 y^2] []/x^y []/y^y 
[x^3 y^2] []/y^y 
[x^3] 

The following finds whether x is greater than y without consuming the original symbols:

x^7 y^6 gth
	[false y^x]/[gth y^x]
	true/gth

[x^7 y^6] gth [false y^x]/[gth y^x] true/gth 
[x^7 y^6 gth] [false y^x]/[gth y^x] true/gth 
[x^7 y^6 gth] true/gth 
[x^7 y^6 true] 

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. The capitalization of labels is merely a convention. For example, here is a program to find the product:

x^2 y^3

@Mul ( x y -- res )
	[Mul res^x]/y

[x^2 y^3] [Mul res^x]/y 
[x^2 y^2 res^2] [Mul res^x]/y 
[x^2 y res^4] [Mul res^x]/y 
[x^2 res^6] [Mul res^x]/y 
[x^2 res^6] 

Anonymous Functions

Anonymous functions are operations that are retried until the denominator is no longer present in the bag. For example, here is a program to find the quotient:

x^24 y^6 'res/x^y

[x^24 y^6] 'res/x^y 
[x^18 y^6 res] 'res/x^y 
[x^12 y^6 res^2] 'res/x^y 
[x^6 y^6 res^3] 'res/x^y 
[y^6 res^4] 'res/x^y 
[y^6 res^4] 

• Multiplication: ( x y -- x r=x*y ) 'r^x/y
• Division: ( x y -- y r=x/y ) 'r/x^y
• Square: ( x -- x res=x*x ) y^x '[res^x]/y
• Modulo: ( x y -- x=x%y y ) '[]/x^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 Linear Logic

Traditional logic treats propositions as inexhaustible, whereas linear logic accounts for resources, using something changes the world. This is illustrated with file handles: once the file is consumed, any fraction requiring it in its denominator simply won't fire; the resource is inaccessible through absence rather than enforcement.

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

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.

coin^3

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

Typically, resource tracking constrains what programmers can do with values, but here, entities persist because nothing consumed them, not because they're protected.

On Reversibility

Multiplying by the inverse of a fraction undoes the application of that fraction, allowing for a certain level of reversibility at the operand level. A program is reversible if it has exactly one forward rule match per input state and exactly one reverse rule match per output state. If that holds, the system cannot lose information.

a^3 b^2 ( fwd ) '[a c]/b -> a^5 c^2
a^5 c^2	( bwd ) 'b/[a c] -> a^3 b^2

To find if a program is within the subset of reversible programs: ignore any program with labels and check if there are any pairs of fractions whose denominators are compatible with the same input bag but whose numerators produce the same output. For example, the OR gate is provably irreversible at compile-time, due to having converging outputs on true.

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

On Optimization

There are various levels of optimizations possible, the interpreter might choose to drain symbols by anonymous functions 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. But each layer of optimization adds runtime costs.

• '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.
• '[x^2 y]/[a^4 b^3]: Multiple values from multiple symbols to many symbols.

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

[c^5] '[a b]/c 
[c^4 a b] '[a b]/c 
[c^3 a^2 b^2] '[a b]/c 
[c^2 a^3 b^3] '[a b]/c 
[c a^4 b^4] '[a b]/c 
[a^5 b^5] '[a b]/c 
[a^5 b^5] 

Many of these loop-shaped behaviors are better handled explicitly with variable exponents instead of labels:

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

[c^5] [a^c b^c]/c^c 
[a^5 b^5] 

On Fractran

A Fractran program can be thought of as a Rejoice program with a single label, at the top of the program, present in each numerator. For example, the Fractran program: [3^2 5^2], 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]

Bestiary

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

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