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 norunand
- unary nanduxnor
- 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 vectorsX << n
return the bit vector left-shifted byn
placesX >> n
return the bit vector right-shifted byn
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.
Enhanced error handling in the Espresso C extension.
Added the espresso_tts
function, which allows you to run Espresso on one or more TruthTable
instances.
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.
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.
Three minor tweaks in this release:
expr
/bdd
to_dot
methods now return undirected graphs.- Added
AchillesHeel
factory function toexpr
. - Fixed a few obscure bugs with simplification of
Implies
andITE
.
New stuff in this release:
- Unified the
Expression
andNormalform
expression types, getting rid of the need for thenfexpr
module. - Added
to_dot
methods to bothExpression
andBinaryDecisionDiagram
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.
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.
New stuff in this release:
- Added
assumptions=None
parameter to PicoSATsatisfy_one
andsatisfy_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 bypicosatmodule.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
Fixed bug: absorption algorithm not returning a fully simplified expression.
Significantly enhance the performance of the absorption algorithm
Fixed bug: PicoSAT module compilation busted on Windows
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 ofOrAnd
andEqualBase
arguments back totuple
. The simplification aspects had an unfortunate performance penalty. Useabsorb
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.
- Thanks to Christoph Gohlke, added build support for Windows platforms.
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), andp <=> 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 hassimplify=True
, andfactor=False
parameters.
- New
Unequal
expression operator. - New
Majority
high-order expression operator. OneHot0
,OneHot
, andMajority
all have both disjunctive (conj=False
) and conjunctive (conj=True
) forms.- Add new
Expression.to_ast
method. This might replace theexpr2dimacssat
function in the future, - Fixed bug:
Xor.factor(conj=True)
returns non-equivalent expression. - Changed the meaning of
conj
parameter inExpression.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 newpyeda.expr.DimacsCNF
class. This might be unified with normal form expressions in the future.
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.
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.
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
intoaddition
andgray_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
topyeda.parsing.dimacs.parse_cnf
. - Changed
dimacs.load_sat
topyeda.parsing.dimacs.parse_sat
. - Changed
dimacs.dump_cnf
topyeda.boolalg.expr2dimacscnf
. - Changed
dimacs.dump_sat
topyeda.boolalg.expr2dimacssat
.
- Refactored parsing code to use
- Changed constructors for
Variable
factories. Unifiednamespace
as just a part of thename
. - Changed interactive usage. Originally was
from pyeda import *
. Now usefrom 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 ofExprOrAnd
,ExprExclusive
,ExprEqual
,ExprImplies
,ExprITE
. - Changed
ExprOrAnd
argument container to afrozenset
, 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
topyeda.util
.
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
andbinop
modules, of dubious value. - Added
is_zero
,is_one
,box
, andunbox
to Function interface. - Removed
reduce
,iter_zeros
, anditer_ones
from Function interface. - Lots of refactoring of SAT methodology.
- Finally implemented
unate
methods correctly for Expressions.
- Lots of work in
pyeda.table
:- Now two classes,
TruthTable
, andPCTable
(for positional-cube format, which allowsX
outputs). - Implemented most of the
boolfunc.Function
API. - Tables now support
-
,+
,*
, andxor
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
toboolfunc.iter_points
. - New
boolfunc.iter_terms
generator. - Changed
dnf=True
toconf=False
on several methods that give the option of returnin an expression in conjunctive or disjunctive form. - Added
conj=False
argument to all expressionfactor
methods. - New
Function.iter_domain
andFunction.iter_image
iterators. - Renamed
Function.iter_outputs
toFunction.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.
- Fixed bug #16:
Function.reduce
only implemented by Variable
- In
pyeda.dimacs
changedparse_cnf
method name toload_cnf
- In
pyeda.dimacs
changedparse_sat
method name toload_sat
- In
pyeda.dimacs
added new methoddump_cnf
, to convert expressions to CNF-formatted strings. - In
pyeda.dimacs
added new methoddump_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.