Gödel's bag, Gödel's bag,
Gödel's bag.
Bägel is a programming language where data is encoded as multisets(unordered bags of things) and compose by multiplication. Think Fractran, without the rule-searching of rewriting, or a strange Lisp in which cons cells are unordered lists.
In this mirror world, order does not matter, only presence and reduction.
Basics
Parentheses denotes an unordered bag of things, which may contain items, fractions or other bags. An item is either a non-numeric symbol assigned an unused prime number or a whole number. The order of things inside a bag does not matter. The caret notation is a shorthand that the represents the number of instances of an item in a bag.
; This is a comment () ; Empty(1), identity (x^3) ; -> (x x x) (2 (y)) ; -> (2 y) (3 (2 5/2) 7) ; -> (3 5 7)
Evaluation consists of applying fractions on whole numbers, locally until exhaustion, starting at the deepest nesting level outward until the bag stabilizes.
(3/2 2) ; -> 3 (5/3 2 3 3) ; -> (5/3 2 3 3) -> (5/3 2 3 5) -> (2 5 5) (1/5 (5/7 7)) ; -> (1/5 5) -> ()
If a bag contains multiple fractions, the fractions are composed before application.
(2/3 2/5 3 5) ; -> (4/15 3 5) -> (2 2) (1/5 1/7 5) ; -> (1/35 5) -> 5
A fraction is applied if the bag in which it is being applied includes the denominator. If a fraction inside a bag cannot be applied, it is discarded during the reduction. A fractions does not fall through to the outer bag if application fails.
((3/4 2) 2) ; -> (2 2) (1/4 3) ; -> 3
A fraction may also output other fractions or other bags.
(2/3/5 3 5) ; -> (2/3 3) -> 2 ((5/3 3)/7 7) ; -> (5/3 3) -> 5 (3/2/2/2 2^4) ; -> (3/2/2 2^3) -> (3/2 2^2) -> 6
Logic
Bägel can handle negation, or the lack of something, but it requires an explicit token to ground the computation. For example here is a NOT logic gate, notice the a resource.
(false/a (true/(x a) x a)) (false/a true) true
(false/a (true/(x a) a)) (false/a a) false
Building on this idea, we can make a OR gate.
(false/a (true/(x a) (true/(y a) (true/(x y a) x a)))) (false/a (true/(x a) (true/(y a) x a))) (false/a (true/(x a) x a)) (false/a true) true
(false/a (true/(x a) (true/(y a) (true/(x y a) a)))) (false/a (true/(x a) (true/(y a) a))) (false/a (true/(x a) a)) (false/a a) false
Notice how the AND gate doesn't need to the a symbol to check for the abscence of things.
(false/x (false/y (true/(x y) x y))) (false/x (false/y true)) (false/x true) true
(false/x (false/y (true/(x y) y))) (false/x (false/y y)) (false/x false) false
Arithmetic
The fraction y/x drains x into y, effectively finding the sum by resource transfer.
(y/x x^3 y^2) ; 3 + 2 (y/x x^2 y^3) (y/x x y^4) (y/x y^5) y^5
The fraction 1/(x y) finds the difference between two symbols, but the program must handle positive and negative results:
(neg/y (pos/x (1/(x y) x^4 y^2))) ; 4 - 2 (neg/y (pos/x (1/(x y) x^3 y))) (neg/y (pos/x (1/(x y) x^2))) (neg/y (pos/x x^2)) ; drain x into pos (neg/y (pos/x x pos)) (neg/y (pos/x pos^2)) (neg/y pos^2) pos^2
(neg/y (pos/x (1/(x y) x^2 y^4))) ; 2 - 4 (neg/y (pos/x (1/(x y) x y^3))) (neg/y (pos/x (1/(x y) y^2))) (neg/y (pos/x y^2)) ; drain y into neg (neg/y y^2) (neg/y y neg) (neg/y neg^2) neg^2
Complex Fractions
Specific items can be injected inside fractions during recursion to create a mechanism similar to function arguments. In the following example, during replacement, the fraction will pull the items %f and %b from the location where the fraction is applied, and put them inside where they are needed.
((fizz/f^3 (buzz/b^5 (fizzbuzz/(f^3 b^5) %f %b))) f b)/i
while(i--) {
f++, b++;
if(f >= 3 && b >= 5)
fizzbuzz++, f -= 3, b -= 5;
else if(f >= 3)
fizz++, f -= 3;
else if(b >= 5)
buzz++, b -= 5;
}
Implementation and details will be added soon, I wrote all this, as if in a fever, on the night of Halloween and expanded on it over the winter.