XXIIVV

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

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, arithmetic emerges entirely from the application of fractions. 

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.

[cat bat rat^2]      ( I have 1 cat, 1 bat and 2 rats )
    [cat bat^3]/rat  ( If I have 1 rat, I replace it with 1 cat & 3 bats )
    []/[rat cat^2]   ( If I have have 1 rat and 2 cats, I discard them )
    yak/bat^cat      ( If I have at least as many bats as cats..
                          .. I replace the amount of cats in bats with 1 yak )
[bat^4 yak]          ( I am left with 4 bats and 1 yak )

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

Numbers are stored as counts, for example, x^5 indicates five instances of x. Variable exponents, like x^y, 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 ( Copy y instances onto x, then drain y: )
	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 ( Remove as many x as there are y, then drain y: )
	[]/x^y
	[]/y^y

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

All variable exponents within a single bracket are resolved simultaneously against an atomic read of the bag. No symbol inside a bracket can observe the effects of any other symbol in the same bracket. For example, the following finds whether x is equal to y:

x^6 y^6 ( Fires only when x and y are equal counts, consuming both: )
	eq/[x^y y^x]

[x^6 y^6] eq/[x^y y^x] 
[eq]

Labels

A @label is a special symbol that represents a jump target. When the corresponding label symbol enters the bag, the label symbol is immediately consumed and 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]

When two labels enter the bag at the same time, one is picked at random.

( flip a coin ) [Head Tail] 

@Head head End
@Tail tail 
@End

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]

The Fibonacci numbers can be found with a single anonymous function, by swapping x and y while a counter n is present:

n^6 y ( n y -- n.fib y )
	'[y^x x^y]/[x^x n]

[n^6 y] '[y^x x^y]/[x^x n] 
[n^5 y x] '[y^x x^y]/[x^x n] 
[n^4 y^2 x] '[y^x x^y]/[x^x n] 
[n^3 y^3 x^2] '[y^x x^y]/[x^x n] 
[n^2 y^5 x^3] '[y^x x^y]/[x^x n] 
[n y^8 x^5] '[y^x x^y]/[x^x n] 
[y^13 x^8] '[y^x x^y]/[x^x n] 
[y^13 x^8]

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 the word "pigs:" ) .pigs:
	( print the number of pigs in decimal ) .#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 ..
[] es nihil, identitate. []/n es predecessore. n es successore.

incoming: left multisets tropical arithmetic wdr computer concatenative rejoice devlog fractran bagel meta 2026