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 written as unreduced fractions. Non-numeric symbols are bound to prime factors beyond the highest utilized factor in a program.

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

Intersection

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

This is the only building block needed for conditionals, the intersection yields a register mask that can be used to reduce the bag one way or another.

(% 2 (x 5/2)) ; if x2 then 5, otherwise ()
(% 6 (x 5/6)) ; if x2 && x3 then 5, otherwise ()
(% x (x 5/11)) ; if !x11 then x, otherwise ()

Function

The function operator (λ fn) tries to apply a transformation until it stabilizes, in other words, until no more reduction can occur.

(λ 3/2 (2 2))       ; (2 3), (3 3).
(λ 5/3 (3 3 3 7))   ; (3 3 5 7), (3 5 5 7), (5 5 5 7).
(% 2 (λ 1/2 2^5))   ; 2 for odd, () for even.

For example, to count until 5, a fraction containing the boundary of the iteration can halt the transformation.

(λ 2/1 3/2^5)

(λ 2/1 3/2^4)
(λ 2/1 3/2^3)
(λ 2/1 3/2^2)
(λ 2/1 3/2^1)
3

The named operator (name λ fn) allows for recursion and for symbols to operate as functions.

(double λ 9/2)      

2^2 3 double/3
2^2 (λ 9/2) 
2 3^2 (λ 9/2)  
3^4

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

incoming: 2025