Thoughts on Rejoice

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

• A fraction is Linear if every resource involved is consumed exactly once and produced exactly once. The resource exists in both the numerator and denominator, and its exponent on both sides is equal. No resource is created, and no resource is destroyed. It is a state transition. apple/dollar
• A fraction is Affine if it is allowed to throw data away. A resource exists in the denominator, but its exponent in the numerator is smaller. You are consuming a resource and intentionally forgetting it without replacing it. []/trash
• A fraction is Relevant if it requires a resource to exist, but duplicates it rather than consuming it. The resource's exponent in the numerator is greater than its exponent in the denominator. The resource is acting as a catalyst. cell^2/cell
• A fraction is Unrestricted if a resource can be copied or ignored at will. x^y/[]

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

Every atomic step in Rejoice is mathematically invertible because multiplying by the inverse of a fraction undoes the application of that fraction, allowing for a certain level of reversibility at the operand level. But a program as a whole is only 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

We can infer the thermodynamics of a fraction by comparing the sum of the exponents in the denominator versus the numerator.

• Expansion Rules: The numerator is greater than the denominator, the system is generating complexity.
• Compression Rules: The denominator is greater than the numerator, the system is consolidating data.

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 symbols, 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 Subroutines

Rejoice has no return stack, and no way to automatically handle returning from a goto, these must be implemented in the program itself:

x^3 y^4 r1 Add @R1
x^5 y^5 r2 Add @R2
End

@Add ( x y -- )
	( x+y   ) x^y/y^y
	( print ) .#x/x^x .\s
	R1/r1
	R2/r2

@End

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.

Fractran programs are a subset of Rejoice programs, a fraction with variable exponents alone would need one Fractran fraction per possible exponent value, and since the exponents are unbounded, there would need an infinite amount of Fractran fractions to emulate it. That difference makes Rejoice a higher-order multiset system.

Synthetic GCD

To find the GCD of two bags, we can lean on object-like symbols:

( bag x ) [x:cat^4 x:fox]
( bag y ) [y:cat^2 y:fox^2 y:owl]

'gcd:cat/[x:cat y:cat]
'gcd:fox/[x:fox y:fox]
'gcd:owl/[x:owl y:owl]

[.. gcd:cat^2 gcd:fox] 

Multifix

Unlike rewriting languages like Modal, Rejoice does not have a mixfix notation, it is strictly concatenative and postfix. But it has a particularity that order does not matter whatsoever which possibly makes for something even more malleable by not having to do any transformation to handle the various notations.

( prefix   ) [add x^3 y^4]
( localize ) +/add
( apply    ) [r^x r^y]/[x^x + y^y]

[] [add x^3 y^4]
[add x^3 y^4] +/add
[x^3 y^4 +] [r^x r^y]/[x^x + y^y]
[r^7] 

Text Adventure

Here's an implementation of the controller to move between the living room, attic and garden. Inspired by Conrad Barski's Land of Lisp.

( start in the living room ) EnterLivingroom
( will queue commands ) cmd1 

@Eval
	( living room to attic ) [Use ladder cmd2]/cmd1 
	( back to living room ) [Use ladder cmd3]/cmd2 
	( living room to garden ) [Use door cmd4]/cmd3
	( back to living room ) [Use door]/cmd4
	End

@Use 
	EnterAttic/[livingroom ladder^2 door]
	EnterLivingroom/[attic ladder^2]
	EnterGarden/[livingroom ladder door^2]
	EnterLivingroom/[garden door^2]
	End

@EnterGarden ( -- )
	."You have entered the garden, you see a well.\n"
	garden door
	Eval

@EnterLivingroom ( -- )
	."You have entered the living room.\n"
	livingroom door ladder 
	Eval

@EnterAttic ( -- )
	."You have entered the attic.\n"
	attic ladder
	Eval

@End

Bestiary

incoming: reversible computing rejoice 2026