Bag is derived from John Conway's Fractran game/language, adding syntax and side effects to make it a "practical" programming language (although still an esoteric one), while being backwards compatible with it, and perhaps allowing a semiefficient implementation.
The power, indeed Turing completeness of Fractran comes from viewing a natural number as the product of a bag (multiset) of prime factors, where the order of primes is immaterial but the number of each is important. The name of Bag is derived from this.
For example, if you let n=2^{x}3^{y}, then the below program will end with n=5^{xy}, effectively calculating the product of x and y.
385/13, 13/21, 1/7, 3/11, 7/2, 1/3To see this, let us factorize the list into primes:
7 11 5/13, 13/7 3, 1/7, 3/11, 7/2, 1/3(In Bag syntax multiplication is usually expressed simply as concatenation, even with numerals.)
If we start with say 36 = 2^{2} 3^{2}, then the first fraction to apply is 7/2, giving 2 3^{2} 7. Then the two first fractions "cooperate" repeatedly to turn this into 2 5^{2} 7 11^{2}. Then the 1/7 removes the 7, giving 2 5^{2} 11^{2}, and the 3/11 repeatedly applies to give 2 3^{2} 5^{2}.
To sum up so far, a factor 2 was removed while simultaneously adding as many factors 5 as there were factors 3 originally. If we write a number as 2^{x} 3^{y} 5^{z}, this corresponds to decrementing x and adding y to z. Note that z+xy is preserved by this.
Now the process repeats with another factor 2, until x becomes 0 and z has become the original xy. Finally the fraction 1/3 applies repeatedly to set y=0, giving just 5^{xy} as the final number.
Note that in this argument, the prime factorization of fractions and numbers is important, but which primes are used does not matter. The algorithm would work just as well if we replaced every 2 by 31 and every 7 by 43, say.
Bag allows you to write numbers like in Fractran if you want to (both versions of the list above are legal Bag programs), but it also allows you to use a symbolic representation, where you can give names to the primes used, possibly with intuitive meanings. For example the above list can be written symbolically as
tx ty z/tz, tz/tx y, /tx, y/ty, tx/x, /y
Comments begin with the character #
and last until the
following newline, or begin with the characters <#
and last until the matching #>
. The latter form may
be nested.
Whitespace consists of any number of space, newline or tab characters.
Comments and whitespace are ignored outside strings,
except that they separate other tokens.
Numerals may be given in base 8 (with prefix 0o
or
0O
), 10 (no prefix) or 16 (with prefix 0x
or
0X
). They represent natural numbers.
Strings begin and end with the character "
. Inside a
string, the character \
starts an escape sequence. The following escape
sequences are defined:
\\  a literal \

\"  a literal "

\n  newline character 
\t  tab character 
\ gap\  ignore a gap of whitespace and comments 
\ numeral  character with code numeral 
Prime names begin with a letter or underscore and may contain letters, digits, and underscores. Prime names are case sensitive, and each name represents an arbitrary prime which is not a factor of any other number in the program.
Operators are the usual arithmetical +*/
, parentheses
()
and exponentiation ^
. The *
of
multiplication is usually omitted like in mathematical notation, while
/
has a slightly lower precedence, optional first argument, and is nonassociative (may
not be nested without using parentheses). See the table below.
Commas are used to separate fractions at the top level of the program. Angle brackets are used around a module's export/import list.
Notation  Precedence/ Associativity  Meaning  Notes 

numeral  not applicable  natural number  
string  only in exponents  
prime name  arbitrary prime  not in exponents  
()  bracketing  parentheses  
^  right assoc  exponentiation  all subexpressions of second argument must be integers 
* or none  assoc  multiplication  does not reduce result to lowest terms outside exponents 
/  nonassoc/ prefix  division  
  prefix  unary minus  only in exponents 
+  left assoc  addition  
  subtraction 