Rejoice!

Rejoice is a concatenative programming language and notation where data is encoded as multisets that compose by multiplication. Think Fractran, without the rule-searching of rewriting, or Forth in which the program state is unordered instead of 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.
• 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.
• Rewrite rules are written as fractions, applied by matching the things in the denominator, subtracting them and adding the things in the nominator. For example, owl/[cat^2], means to replace two cat with one owl.

The documentation below will display the content of bags in bold. Multiple instances of things are grouped as thing^count. The empty bag, or identity, is represented as [].

( a comment )

red green blue      [yellow red]/blue
red^2 green yellow

Evaluation consists of applying fractions in a sequence when their denominators are found in the bag. The program halts when there are no more fractions left to apply.

blue^3 red           cyan/pink red [cyan^2]/red red/[blue^2 cyan]
blue^3 red           red [cyan^2]/red red/[blue^2 cyan]
blue^3 red^2         [cyan^2]/red red/[blue^2 cyan]
blue^3 red cyan^2    red/[blue^2 cyan]
blue red^2 cyan

Logic

Here is the implementation of a NOT logic gate.

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

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

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

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

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

Functions

Functions are symbols that are evaluated when they enter the bag. A definition starts with colon, followed by the function name, a comment that indicates the transformation and finally, a semi-colon. Notice how the AND gate uses a sentinel value and to catch the absence of input.

: And? ( x y -- bool )
	and true/[and x y] false/[and x] false/[and y] false/and ;

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

If two or more functions may be called at once, the interpreter can choose to evaluated them non-deterministically, or throw an error.

Arithmetic

The function [x Add]/y drains y into x and calls itself again for as long as y is in the bag, effectively finding the sum by resource transfer.

: Add ( x y -- x^2 ) [x Add]/y ;

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

To find the difference between two symbols, the program can take out one of each symbol until exhaustion, leaving either x for a positive result, or y for a negative result. The following recursive function can find the result:

: Sub ( x y -- x|y ) Sub/[x y] ;

x^4 y^2 Sub
x^4 y^2      Sub/[x y]
x^3 y Sub
x^3 y        Sub/[x y]
x^2 Sub
x^2          Sub/[x y]
x^2

To double the value of a symbol:

: Double ( x -- y^2 ) [y^2 Double]/x ;

x^3 Double    
x^3             [y^2 Double]/x
x^2 y^2 Double
x^2 y^2         [y^2 Double]/x
x y^4 Double
x y^4           [y^2 Double]/x
y^6 Double
y^6             [y^2 Double]/x
y^6

Loops

A function can include its own name in the definition, allowing for loops:

: loop ( x -- ) x done/x^4 [x^2 loop]/x ;

x loop
x         done/x^4 [x^2 loop]/x
x         [x^2 loop]/x
x^2 loop
x^2       done/x^4 [x^2 loop]/x
x^2       [x^2 loop]/x
x^3 loop
x^3       done/x^4 [x^2 loop]/x
x^3       [x^2 loop]/x
x^4 loop
x^4       done/x^4 [x^2 loop]/x
done      [x^2 loop]/x
done

FizzBuzz

This is a first draft of the language, I'm currently working on an implementation. One last thing before I end this, here's a fizzbuzz:

: FizzBuzz ( i -- )
	i^2 f b 
	print-fb/[f^2 b^4] 
	print-f/[f^2] 
	print-b/[b^4] 
	done/[i^100] FizzBuzz/i ;

• Multiset Languages: Fractran, Bägel.

incoming: tropical arithmetic fractran bagel 2026