# Release Notes¶

## Version 0.24¶

Variables names are now required to be C-style identifiers.
I.e., `[a-zA-Z_][a-zA-Z0-9_]*`.

The expression parser now handles both `a[1][2][3]` and `a[1,2,3]` syntaxes
(Issue 91).
The `a[1][2][3]` is deprecated.

Got rid of expression `is_neg_unate`, `is_pos_unate`,
and `is_binate` functions.
I haven’t been able to find an *efficient* algorithm for this,
so just convert expressions and BDDs to truth tables first.
If your function is too big to fit in a truth table,
it’s probably also too big to expand to a canonical expression.

`Not(Not(...))` double negation is now automatically reduced,
just like `Not(Nand(...))`, etc.

Cleaned up the definition of expression depth (Issue 92). This is not backwards compatible.

Fixed Issue 93, picosat script fails with trivial zero input:

```
$ picosat
p cnf 0 1
0
```

Changed `RegexLexer` to yield `EndToken` at the end of a token stream.
This makes parsing nicer, avoiding catching `StopIteration` everywhere.

Got rid of `factor=False` on expression factory functions.
This was overly designed UI.

The expression `restrict` method is a little faster now.
Especially for big functions.

Added *lots* of new reference documentation.

Added new `farray` documentation chapter.
Fixed several little issues with function arrays during this process.
The constructor now takes an `ftype=None` parameter.
Negative indices make more sense now.
Slices behave more like Python tuple slices.
Fixed several inconsistencies with empty arrays.

Deprecated `bitvec` function.

## Version 0.23¶

This version introduces a new `picosat` script.
Now you can solve DIMACS CNF files from the command-line.
See http://pyeda.readthedocs.org/en/latest/expr.html#picosat-script
for details.

Finally there is a proper documentation chapter for binary decision diagrams! While writing this documentation, I noticed, and fixed some obscure bugs related to incorrect usage of weak references to BDD nodes.

Made some minor changes to the public interface of the `bdd` module.

Replaced the `traverse` method with three options for BDD iteration:

`bdd.dfs_preorder`- Depth-first search pre-order traversal`bdd.dfs_postorder`- Depth-first search post-order traversal`bdd.bfs()`- Breadth-first search

Got rid of the deprecated `uint2bv` and `int2bv` functions.
Use the `uint2exprs`, `int2exprs` functions instead.

Changed the `pyeda.parsing.parse_pla` function so it takes a string input.
This makes it much easier to test.

Deprecated the `is_neg_unate`, `is_pos_unate`, `is_binate`
methods for expressions.
I haven’t found a correct algorithm that is better than just 1) converting
to a truth table, and 2) checking for monotonicity in the cofactors.

As of this release, I will be dropping support for Python 3.2.

## Version 0.22¶

A couple features, and some good bug-fixes in this release.

Fixed Issue 80.
Apparently, I forgot to implement the right-side version of XOR operator: `0 ^ x`.

Fixed Issue 81.
I continue finding bugs with degenerate forms.
This particular one comes up when you try to do something similar to
`Or(Or(a, b))`.
The `__new__` method was implemented incorrectly,
so I moved the `Or(a) = a` (and similar) rules to the `simplify` method.

To match the notation used by Univ of Illinois VLSI class, I changed BDD low/high nodes to “lo”, and “hi”.

Got rid of the “minus” operator, `a - b`.
This was previously implemented as `a | ~b`,
but I don’t think it has merit anymore.

The `farray` type now uses the `+` operator for concatenation,
and `*` for repetition.
These are very important features in SystemVerilog.
See Issue 77 for details.

Implemented the `farray.__setitem__` method.
It is very useful to instantiate an `farray` using `exprzeros`,
and then programmatically assign indices one-by-one.
See Issue 78 for details.

To demonstrate some of the fancy, new `farray` features,
I added the AES algorithm to the `logic` package.
It manages to complete all the logic assignments,
but I haven’t been able to test its correctness yet,
because it explodes the memory on my machine.
At a bare minimum, it will be a nice test case for performance optimizations
necessary to handle large designs.

## Version 0.21¶

Important bug fix! Issue 75.
Harnesser pointed out that Espresso was
returning some goofy results for
degenerate inputs (a literal or `AND(lit, lit, ...)`).

The major new feature in this release is the `farray` mult-dimensional
array (MDA) data type.
The implementation of `BitVector` was a kludge –
it was built around the `Expression` function type,
and didn’t support all the fancy things you could do with numpy slices.
All usage of the old `Slicer` and `BitVector` types has been eliminated,
and replaced by `farray`.
This includes the `bitvec`, `uint2bv`, and `int2bv` functions,
and the contents of the `pyeda.logic` package (addition, Sudoku, etc).

Both `uint2bv` and `int2bv` are deprecated,
superceded by `uint2exprs` and `int2exprs` (or `uint2bdds`, etc).
So far I haven’t deprecated `bitvec`,
because it’s a very commonly-used function.

See Issue 68 for some details
on the `farray` type.
My favorite part is the ability to multiplex an `farray` using Python’s
slice syntax:

```
>>> xs = exprvars('x', 4)
>>> sel = exprvars('s', 2)
>>> xs[sel]
Or(And(~s[0], ~s[1], x[0]), And(s[0], ~s[1], x[1]), And(~s[0], s[1], x[2]), And(s[0], s[1], x[3]))
```

This even works with MDAs:

```
>>> xs = exprvars('x', 4, 4)
>>> sel = exprvars('s', 2)
>>> xs[0,sel]
Or(And(~s[0], ~s[1], x[0][0]), And(s[0], ~s[1], x[0][1]), And(~s[0], s[1], x[0][2]), And(s[0], s[1], x[0][3]))
```

Added `AchillesHeel` function to expression parsing engine.

Eliminated the `+` and `*` operators for Boolean OR, AND, respectively.
This is annoying, but I need these operators for
Issue 77.
Sorry for any trouble, but that’s what major version zero is for :).

## Version 0.20¶

Probably the most useful feature in this release is the `espresso` script:

```
$ espresso -h
usage: espresso [-h] [-e {fast,ness,nirr,nunwrap,onset,strong}] [--fast]
[--no-ess] [--no-irr] [--no-unwrap] [--onset] [--strong]
[file]
Minimize a PLA file
positional arguments:
file PLA file (default: stdin)
optional arguments:
...
```

This script implements a subset of the functionality of the original
`Espresso` command-line program.
It uses the new `parse_pla` function in the `pyeda.parsing.pla` module
to parse common PLA files.
Note that the script only intends to implement basic truth-table functionality
at the moment.
It doesn’t support multiple-valued variables,
and various other Espresso built-in features.

Added Espresso `get_config` and `set_config` functions,
to manipulate global configuration

New `Bitvector` methods:

`unor`- unary nor`unand`- unary nand`uxnor`- unary xnor

Made `BitVector` an immutable type.
As a result, dropped item assignment `X[0] = a`,
zero extension `X.zext(4)`, sign extension `X.sext(4)`,
and `append` method.

The `BitVector` type now supports more overloaded operators:

`X + Y`concatenate two bit vectors`X << n`return the bit vector left-shifted by`n`places`X >> n`return the bit vector right-shifted by`n`places

Both left shift and right shift are simple shifts–they use the default “carry-in” of zero.

Got rid of `boolify` utility function.
It had been replaced over time by more sophisticated techniques.

There is a new `Mux` factory function,
for multiplexing arbitrarily many input functions.

Update to PicoSAT 959. Check the homepage for details, but it looks like the only changes were related to header file documentation.

Added a neat capability to specify assumptions for SAT-solving using a `with`
statement.
It supports both literal and product-term forms:

```
>>> f = Xor(a, b, c)
>>> with a, ~b:
... print(f.satisfy_one())
{a: 1, b: 0, c: 0}
>>> with a & ~b:
... print(f.satisfy_one())
{a: 1, b: 0, c: 0}
```

At the moment, this only works for the `satisfy_one` method,
because it is so handy and intuitive.

## Version 0.19¶

### Release 0.19.3¶

Enhanced error handling in the Espresso C extension.

### Release 0.19.2¶

Added the `espresso_tts` function,
which allows you to run Espresso on one or more `TruthTable` instances.

### Release 0.19.1¶

Fixed a bone-headed mistake: leaving `espresso.h` out of the source
distribution.
One of these days I will remember to test the source distribution for all the
necessary files before releasing it.

### Release 0.19.0¶

This is a very exciting release! After much hard work, PyEDA now has a C extension to the famous Espresso logic minimization software from Berkeley! See the new chapter on two-level logic minimization for usage information.

Also, after some feedback from users, it became increasingly obvious that
using the `-+*` operators for NOT, OR, AND was a limitation.
Now, just like Sympy, PyEDA uses the `~|&^` operators for symbolic algebra.
For convenience, the legacy operators will issue deprecation warnings for now.
In some upcoming release, they will no longer work.

After other feedback from users, I changed the way `Expression` string
representation works.
Now, the `__str__` method uses `Or`, `And`, etc, instead of ascii
characters.
The idea is that the string representation now returns valid Python that can
be parsed by the `expr` function (or the Python interpreter).
To provide support for fancy formatting in IPython notebook,
I added the new `to_unicode` and `to_latex` methods.
These methods also return fancy string representations.

For consistency, the `uint2vec` and `int2vec` functions have been renamed
to `uint2bv` and `int2bv`, respectively.

Since `is_pos_unate`, `is_neg_unate`, and `is_binate` didn’t seem like
fundamental operations,
I remove them from the `Function` base class.

## Version 0.18¶

### Release 0.18.1¶

Three minor tweaks in this release:

`expr`/`bdd``to_dot`methods now return undirected graphs.- Added
`AchillesHeel`factory function to`expr`. - Fixed a few obscure bugs with simplification of
`Implies`and`ITE`.

### Release 0.18.0¶

New stuff in this release:

- Unified the
`Expression`and`Normalform`expression types, getting rid of the need for the`nfexpr`module. - Added
`to_dot`methods to both`Expression`and`BinaryDecisionDiagram`data types.

Mostly incremental changes this time around.
My apologies to anybody who was using the `nfexpr` module.
Lately, `Expression` has gotten quite fast, especially with the addition
of the PicoSAT C extension.
The normal form data type as `set(frozenset(int))` was not a proper
implementation of the `Function` class,
so finally did away with it in favor of the new “encoded” representation that
matches the Dimacs CNF convention of mapping an index 1..N to each variable,
and having the negative index correspond to the complement.
So far this is only useful for CNF SAT-solving,
but may also come in handy for any future, fast operations on 2-level covers.

Also, somewhat awesome is the addition of the `to_dot` methods.
I was playing around with IPython extensions,
and eventually hacked up a neat solution for drawing BDDs into the notebook.
The magic functions are published in my
ipython-magic repo.
See the
usage notes.
Using `subprocess` is probably not the best way to interface with Graphviz,
but it works well enough without any dependencies.

## Version 0.17¶

### Release 0.17.1¶

Got rid of the `assumptions` parameter from `boolalg.picosat.satisfy_all`
function, because it had no effect.
Read through `picosat.h` to figure out what happened,
and you need to re-apply assumptions for every call to `picosat_sat`.
For now, the usage model seems a little dubious, so just got rid of it.

### Release 0.17.0¶

New stuff in this release:

- Added
`assumptions=None`parameter to PicoSAT`satisfy_one`and`satisfy_all`functions. This produces a*very*nice speedup in some situations. - Got rid of extraneous
`picosat.py`Python wrapper module. Now the PicoSAT Python interface is implemented by`picosatmodule.c`. - Updated Nor/Nand operators to secondary status. That is, they now can be natively represented by symbolic expressions.
- Added a Brent-Kung adder to logic.addition module
- Lots of other miscellaneous cleanup and better error handling

## Version 0.16¶

### Release 0.16.3¶

Fixed bug: absorption algorithm not returning a fully simplified expression.

### Release 0.16.2¶

Significantly enhance the performance of the absorption algorithm

### Release 0.16.1¶

Fixed bug: PicoSAT module compilation busted on Windows

### Release 0.16.0¶

New stuff in this release:

- Added Expression
`complete_sum`method, to generate a normal form expression that contains all prime implicants. - Unicode expression symbols, because it’s awesome
- Added new Expression ForEach, Exists factory functions.
- Changed
`frozenset`implementation of`OrAnd`and`EqualBase`arguments back to`tuple`. The simplification aspects had an unfortunate performance penalty. Use`absorb`to get rid of duplicate terms in DNF/CNF forms. - Added flatten=False/True to Expression to_dnf, to_cdnf, to_cnf, to_ccnf methods. Often, flatten=False is faster at reducing to a normal form.
- Simplified absorb algorithm using Python sets.
- Expression added a new splitvar property, which implements a common heuristic to find a good splitting variable.

## Version 0.15¶

### Release 0.15.1¶

- Thanks to Christoph Gohlke, added build support for Windows platforms.

### Release 0.15.0¶

This is probably the most exciting release of PyEDA yet! Integration of the popular PicoSAT fast C SAT solver makes PyEDA suitable for industrial-strength applications. Unfortunately, I have no idea how to make this work on Windows yet.

Here are the full release notes:

- Drop support for Python 2.7. Will only support Python 3.2+ going forward.
- Integrate PicoSAT, a compact SAT solver written in C.
- Added
*lots*of new capabilities to Boolean expression parsing:`s ? d1 : d0`(ITE),`p => q`(Implies), and`p <=> q`(Equal) symbolic operators.- Full complement of explicit form Boolean operators:
`Or`,`And`,`Xor`,`Xnor`,`Equal`,`Unequal`,`Nor`,`Nand`,`OneHot0`,`OneHot`,`Majority`,`ITE`,`Implies`,`Not` - The
`expr`function now simplifies by default, and has`simplify=True`, and`factor=False`parameters.

- New
`Unequal`expression operator. - New
`Majority`high-order expression operator. `OneHot0`,`OneHot`, and`Majority`all have both disjunctive (`conj=False`) and conjunctive (`conj=True`) forms.- Add new
`Expression.to_ast`method. This might replace the`expr2dimacssat`function in the future, - Fixed bug:
`Xor.factor(conj=True)`returns non-equivalent expression. - Changed the meaning of
`conj`parameter in`Expression.factor`method. Now it is only used by the top-level, and not passed recursively. - Normal form expression no longer inherit from
`Function`. They didn’t implement the full interface, so this just made sense. - Replaced
`pyeda.expr.expr2dimacscnf`with a new`pyeda.expr.DimacsCNF`class. This might be unified with normal form expressions in the future.

## Version 0.14¶

### Release 0.14.2¶

Fixed Issue #42.

There was a bug in the implementation of `OrAnd`,
due to the new usage of a frozenset to represent the argument container.

With `0.14.1`, you could get this:

```
>>> And('a', 'b', 'c') == Or('a', 'b', 'c')
True
```

Now:

```
>>> And('a', 'b', 'c') == Or('a', 'b', 'c')
False
```

The `==` operator is only used by PyEDA for hashing,
and is not overloaded by `Expression`.
Therefore, this could potentially cause some serious issues with `Or`/`And`
expressions that prune arguments incorrectly.

### Release 0.14.1¶

Fixed Issue #41.
Basically, the package metadata in the `0.14.0` release was incomplete,
so the source distribution only contained a few modules. Whoops.

### Release 0.14.0¶

This release reorganizes the PyEDA source code around quite a bit, and introduces some awesome new parsing utilities.

Probably the most important new feature is the addition of the
`pyeda.boolalg.expr.expr` function.
This function takes `int` or `str` as an input.
If the input is a `str` instance, the function *parses the input string*,
and returns an `Expression` instance.
This makes it easy to form symbolic expression without even having to declare
variables ahead of time:

```
>>> from pyeda.boolalg.expr import expr
>>> f = expr("-a * b + -b * c")
>>> g = expr("(-x[0] + x[1]) * (-x[1] + x[2])")
```

The return value of `expr` function is **not** simplified by default.
This allows you to represent arbitrary expressions, for example:

```
>>> h = expr("a * 0")
>>> h
0 * a
>>> h.simplify()
0
```

- Reorganized source code:
- Moved all Boolean algebra (functions, vector functions) into a new package,
`pyeda.boolalg`. - Split
`arithmetic`into`addition`and`gray_code`modules. - Moved all logic functions (addition, gray code) into a new package,
`pyeda.logic`. - Created new Sudoku module under
`pyeda.logic`.

- Moved all Boolean algebra (functions, vector functions) into a new package,
- Awesome new regex-based lexical analysis class,
`pyeda.parsing.RegexLexer`. - Reorganized the DIMACS parsing code:
- Refactored parsing code to use
`RegexLexer`. - Parsing functions now return an abstract syntax tree,
to be used by
`pyeda.boolalg.ast2expr`function. - Changed
`dimacs.load_cnf`to`pyeda.parsing.dimacs.parse_cnf`. - Changed
`dimacs.load_sat`to`pyeda.parsing.dimacs.parse_sat`. - Changed
`dimacs.dump_cnf`to`pyeda.boolalg.expr2dimacscnf`. - Changed
`dimacs.dump_sat`to`pyeda.boolalg.expr2dimacssat`.

- Refactored parsing code to use
- Changed constructors for
`Variable`factories. Unified`namespace`as just a part of the`name`. - Changed interactive usage. Originally was
`from pyeda import *`. Now use`from pyeda.inter import *`. - Some more miscellaneous refactoring on logic expressions:
- Fixed weirdness with
`Expression.simplified`implementation. - Added new private class
`_ArgumentContainer`, which is now the parent of`ExprOrAnd`,`ExprExclusive`,`ExprEqual`,`ExprImplies`,`ExprITE`. - Changed
`ExprOrAnd`argument container to a`frozenset`, which has several nice properties for simplification of AND/OR expressions.

- Fixed weirdness with
- Got rid of
`pyeda.alphas`module. - Preliminary support for logic expression
`complete_sum`method, for generating the set of prime implicants. - Use a “computed table” cache in BDD
`restrict`method. - Use weak references to help with BDD garbage collection.
- Replace distutils with setuptools.
- Preliminary support for Tseitin encoding of logic expressions.
- Rename
`pyeda.common`to`pyeda.util`.

## Version 0.13¶

Wow, this release took a huge leap from version 0.12. We’re probably not ready to declare a “1.0”, but it is definitely time to take a step back from API development, and start focusing on producing useful documentation.

This is not a complete list of changes, but here are the highlights.

- Binary Decision Diagrams! The recursive algorithms used to implement this datatype are awesome.
- Unification of all Variable subclasses by using separate factory functions
(
`exprvar`,`ttvar`,`bddvar`), but a common integer “uniqid”. - New “untyped point” is an immutable 2-tuple of variable uniqids assigned
to zero and one.
Also a new
`urestrict`method to go along with it. Most important algorithms now use untyped points internally, because the set operations are very elegant and avoid dealing with which type of variable you are using. - Changed the Variable’s
`namespace`argument to a tuple of strings. - Restricting a function to a 0/1 state no longer returns an integer. Now every function representation has its own zero/one representations.
- Now using the fantastic Logilab PyLint program!
- Truth tables now use the awesome stdlib array.array for internal representation.
- Changed the names of almost all Expression sublasses to ExprSomething.
the Or/And/Not operators are now functions.
This simplified lots of crummy
`__new__`magic. - Expression instances to not automatically simplify,
but they do if you use Or/And/Not/etc with default
`**kwargs`. - Got rid of
`constant`and`binop`modules, of dubious value. - Added
`is_zero`,`is_one`,`box`, and`unbox`to Function interface. - Removed
`reduce`,`iter_zeros`, and`iter_ones`from Function interface. - Lots of refactoring of SAT methodology.
- Finally implemented
`unate`methods correctly for Expressions.

## Version 0.12¶

- Lots of work in
`pyeda.table`:- Now two classes,
`TruthTable`, and`PCTable`(for positional-cube format, which allows`X`outputs). - Implemented
*most*of the`boolfunc.Function`API. - Tables now support
`-`,`+`,`*`, and`xor`operators.

- Now two classes,
- Using a set container for And/Or/Xor argument simplification results in about 30% speedup of unit tests.
- Renamed
`boolfunc.iter_space`to`boolfunc.iter_points`. - New
`boolfunc.iter_terms`generator. - Changed
`dnf=True`to`conf=False`on several methods that give the option of returnin an expression in conjunctive or disjunctive form. - Added
`conj=False`argument to all expression`factor`methods. - New
`Function.iter_domain`and`Function.iter_image`iterators. - Renamed
`Function.iter_outputs`to`Function.iter_relation`. - Add
`pyeda.alphas`module for a convenience way to grab all the a, b, c, d, ... variables. `Xor.factor`now returns a flattened form, instead of nested.

## Version 0.11¶

### Release 0.11.1¶

- Fixed bug #16:
`Function.reduce`only implemented by Variable

### Release 0.11.0¶

- In
`pyeda.dimacs`changed`parse_cnf`method name to`load_cnf` - In
`pyeda.dimacs`changed`parse_sat`method name to`load_sat` - In
`pyeda.dimacs`added new method`dump_cnf`, to convert expressions to CNF-formatted strings. - In
`pyeda.dimacs`added new method`dump_sat`, to convert expressions to SAT-formatted strings. - Variables now have a
`qualname`attribute, to allow referencing a variable either by its local name or its fully-qualified name. - Function gained a
`reduce`method, to provide a standard interface to reduce Boolean function implementations to their canonical forms. - Expressions gained a
`simplify`parameter, to allow constructing unsimplified expressions. - Expressions gained an
`expand`method, to implement Shannon expansion. - New if-then-else (ITE) expression type.
- NormalForm expressions now both support
`-`,`+`, and`*`operators.