the_bits is a utility for working with binary logic expressions. There are several modes, invoked by simple pattern matching on the input: "help": prints very basic help, useful for when the_bits is run on IRC. "(.+) = (.+)": checks if two expressions are equivalent "a=0,b=1,...; (.+)": evaluates an expression with the variables set to a specific value ".*": parses the expression and prints a canonical form One of the goals was to support the most common conventions for writing equations, which leads to a bit of a mess. The overview of what the syntax supports: grouping: use (), {} or [] in any combination (though like must close like) ex: (1) + [a] ^ [a + {0 + 1}] canonical form: () negation: use prefix ! or ~, and postfix ' ex: !a ex: ~a ex: a' ex: !ab'~c canonical form: ! and: implicit, *, & or && ex: ab ex: a * b ex: a & b ex: a && b canonical form: implicit xor: ^ ex: a ^ b canonical form: ^ or: +, |, || ex: a + b ex: a | b ex: a || b canonical form: + constants: true false 0 1 canonical form: 0 1 variables: lowercase a through lowercase z canonical form: itself When tokenizing an expression, the longest match is used. This is primarily to ensure that && is not split into two adjacent & tokens, but is also used to settle constant values vs strings of implicitly and'd variables. Unfortunately this leads to the downside that "false" is a constant, but "flase" is 5 variables and'd together. Help mode: Give "help" as an expression. Yes, this means that if you want to parse a 4 variable expression of the vars 'h', 'e', 'l', and 'p' and'd together you must put them in an order that does not spell "help", or there must be an explicit and. "help" as a subexpression is valid and does not trigger the help message to print. Parse and canonicalize mode: Give an expression that does not have an equals or semicolon. the_bits will parse the expression, printing an error if the expression is malformed. If the expression parses correctly the_bits prints the canonical form as a lisp-like function tree, the parseable string, and a list of how frequently each variable occurs. ex: ab+c (+ (* a b) c) : { a: 1 }, { b: 1 }, { c: 1 } : ab+c ex: (a+) error: (a+) error: ^ binary operators must have rhs Evaluate mode: Give a list of variable definitions followed by an expression. The variable definition list should be of the form "var=val" separated by commas. Whitespace is ignored, as well as empty comma groups. Currently only 0 and 1 are supported as values, not "true" and "false". ex: a=1, b = 0,,c=1; !a + b + ca true Equivalence mode: Give two expressions separated by a run of the symbol '='. We're a little liberal here, you can use one or more equals as long as it's not split by whitespace or any other token. Currently we support up to 10 variables in the expressions, since we do a naive recursive brute force of the space. ex: ab + c == (c + ba)(b + !b) expressions are equivalent ex: ab + c == ac + b error: expressions are not equivalent: a=0, b=1, c=0 : 0 != 1 Future work: Minification. We remove certain trivial constructs such as a double negate, but we could also fold things like (a + true) or (b * false). It would be cool to use something like Karnaugh maps as an algorithm to simplify further. Better evaluation. We do not short circuit or and and logic currently. We could split the search space up and check it on multiple threads. For each thread, we can take a 3 variable prefix and set their values as constants in the AST, then rerun the simplification. Capital variables? Sounds like a recipe for disaster.