Gödel's bag, Gödel's bag,
Gödel's bag.

Bägel is a programming language where functions return multisets(bags) and compose by multiplication. Every item is a bag of factors and every function a multiplicative transformation. Think Fractran, without the rule-searching of rewriting, or a strange Lisp in which cons cells are unordered lists.

Primitives

Parentheses denotes a bag, which may contain items or other bags. The final bag left after the reduction is the output of a program.

; This is a comment

()        ; Empty[1], identity
(2)       ; 2
(2 ())    ; 2
(2 (2 3)) ; 12

The order of items in a bag does not matter.

((2 3) 2)  ; 12
(3 (2 ())) ; 6

Items in a bag are fractions that can invert or remove factors.

(125 1/5) ; 5^3 * 1/5 = 5^2
(2 3/2)   ; 2 * 3/2 = 3
(5 1/5)   ; ()

The intersection operator (% a b c..) returns the GCD of all arguments.

(% 6 15)    ; 2 * [3] % [3] * 5 = 3
(% 6 7)     ; 2 * 3 % 7 = Empty[1]
(2 (% 6 2)) ; 2 * (2 * 3 % 3) = 2^2

The conditional operator (? bag a b) returns the a when the bag is not Empty[1], otherwise it returns b.

(? ()
	("Not Empty")
	("Empty"))

(? (% (2 3 7 7) (7 7))
	("bag contains twice 7")
	("bag does not contain twice 7"))

The anonymous function (λ args body) binds names to bags within its scope. Functions always return bags.

((λ (x y) x) 2 18)      ; 2
((λ (x y) y) 2 (2 3^2)) ; 18

The named function (name λ args body) allows reuse and enables recursion.

(double λ (a) (a a))

(double 2)              ; 4

For example, if a contains 3, remove it, put a 2 instead and repeat, otherwise stop.

(merge λ (a)
	(? (% a 3)
		(merge (a 2/3)) ; remove one 3, add one 2
		a))

(merge (2^2 3^3))     ; 2^5 = 32

FizzBuzz

Symbols within double-quotes create new symbols instead of references, this allows for ordering the items that remain in the bag for the output.

(fizzbuzz λ (num acc)
	(? (% num 2^100)
		(? (% acc (2^3 3^5))
			((fizzbuzz (num 2) (acc 1/2^3 1/3^5)) ("FizzBuzz"))
			(? (% acc 2^3)
				((fizzbuzz (num 2) (acc 1/2^3 3)) ("Fizz"))
				(? (% acc 3^5)
					((fizzbuzz (num 2) (acc 2 1/3^5)) ("Buzz"))
					((fizzbuzz (num 2) (acc 2 3)) ("#num")))))
		()))

(fizzbuzz (2) (2 3))

Implementation and details will be added soon, I wrote all this, as if in a fever, on the night of Halloween.

incoming: 2025