Gbagbo
The Gbagbo programming language expresses calculations on bags. It is named after the former Ivory Coast President Laurent Gbagbo.
Lexical structure
Single character tokens are: = . [ ] ∪ ∩ △ | & ^ ⊖ × * ( )
Comments are introduced by == and extend to the end of the line.
Uninterrupted sequences of non-space non-token characters are identifiers. Identifiers consisting of only numeric characters (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) are also numbers when used as the count in bag expressions.
EBNF Syntax
program = { function-decl } ;
function-decl = identifier { identifier } "=" expr "." ;
expr = bag-expr | expr binary-op expr | identifier { [ "*" ] expr } | "(" expr ")" ;
bag-expr = "[" { [ count ] expr } "]" ;
binary-op = "∪" | "∩" | "△" | "|" | "&" | "^" | "⊖" ;
count = number ( "×" | "*" ) ;
Expressions
Bag expressions
A bag expression starts with [ followed by zero or more bag elements and ends with ]. Bag elements may be repeated for multiple counts of elements. Bag elements may be preceded by a count multiplier to indicate multiple counts.
For example, [2×[]] is equivalent to [[][]] and [3×[]2×[]] is equivalent to [5×[]].
Binary operators
| ∪ or |: union | If c = a ∪ b, for each unique element e in c, the count of e in c is
the maximum of the count of e in a and the count of e in b, and for each unique element e in a, the count of e in c is greater than or equal to the count of e in a, and for each unique element e in b, the count of e in c is greater than or equal to the count of e in b. |
| ∩ or &: intersection | If c = a ∩ b, for each unique element e in c, the count of e in c is
the minimum of the count of e in a and the count of e in b, where the count may be zero, and for each unique element e in a, the count of e in c is less than or equal to the count of e in a, and for each unique element e in b, the count of e in c is less than or equal to the count of e in b. This does not uniquely define c, so c can be uniquely defined as the union of all bags satisfying the previous conditions. |
| △ or ⊖ or ^: difference | If c = a △ b, for each unique element e in c, the count of e in c is
the absolute value of the count of e in a minus the count of e in b, and for each unique element e in a, the count of e in c is the absolute value of the count of e in a minus the count of e in b, and for each unique element e in b, the count of e in c is the absolute value of the count of e in a minus the count of e in b. |
The binary operators are all left associative and have equal precedence. Parentheses may be used to specify associativity and precedence.
Map operator
A * before a function argument causes the function to be evaluated with each element of the argument with the result being the sum all the results. When multiple arguments are preceded by *, the result is the sum of the function evaluated over the Cartesian product of those arguments.
Input/output encoding
EOF is an empty bag.
A zero bit is a bag containing one element representing the following bits.
A one bit is a bag containing an empty bag and another element (possibly another empty bag) representing the following bits.
Examples
cat
cat x = x.
Hello world
hello = 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 1
0 0 0 1 1 0 1 1 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 0
1 1 1 1 0 1 1 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0
1 0 0 0 0 1 0 0 0 0 1 0 1 0 [].
0 x = [x].
1 x = [[]x].