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 starting at the deepest nesting level outward until the bag stabilizes.
(3/2 2) ; -> 3 (3/5 5^3) ; -> (3 5^2) (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) -> 4 (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
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
Quoted Fractions
A quoted fraction is applied repeatedly until exhaustion of the denominator in the bag in which it is applied, this mechanism allows for recursion.
('blue/red red^3) ; while(red--) blue++;
('blue/red red^2 blue)
('blue/red red blue^2)
('blue/red blue^3)
blue^3
Quoted fractions also compose, non-quoted fractions will compose with quoted fractions, the resulting fraction will always be a quotation.
('2/3 '2/5 3^2 5^2)
('4/15 3^2 5^2)
('4/15 2^2 3 5)
('4/15 2^4)
2^4
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
Quoted Arguments
Specific items can be injected inside quoted fractions during recursion to create a mechanism similar to function arguments. In the following example, the fraction will remove the items from the location where the fraction was applied, and inject them inside the fraction at %symbol.
'( (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;
}
Macros
Macros are named fractions added to the dictionary of symbols, instead of expanding to a prime, this symbol will be expanded to a fraction.
:sub('neg/y ('pos/x ('1/(x y) %x %y)))
(sub x^5 y^3)
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.