rejoice

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 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.

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.

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]

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, 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]

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 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, 16, 17, ..

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

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

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