transformations
¶
Interfaces for transforming representations of expressions.
transformations.bexpr
module¶
Transformation functions for expressions.
-
tt.transformations.bexpr.
apply_de_morgans
(expr)[source]¶ Convert an expression to a form with De Morgan’s Law applied.
Returns: A new expression object, transformed so that De Morgan’s Law has been applied to negated ANDs and ORs. Return type: BooleanExpression
Raises: InvalidArgumentTypeError – If expr
is not a valid type.Here’s a couple of simple examples showing De Morgan’s Law being applied to a negated AND and a negated OR:
>>> from tt import apply_de_morgans >>> apply_de_morgans('~(A /\ B)') <BooleanExpression "~A \/ ~B"> >>> apply_de_morgans('~(A \/ B)') <BooleanExpression "~A /\ ~B">
-
tt.transformations.bexpr.
apply_idempotent_law
(expr)[source]¶ Convert an expression to a form with the Idempotent Law applied.
Returns: A new expression object, transformed so that the Idempotent Law has been applied to applicable clauses. Return type: BooleanExpression
Raises: InvalidArgumentTypeError – If expr
is not a valid data type.This transformation will apply the Idempotent Law to clauses of AND and OR operators containing redundant operands. Here are a couple of simple examples:
>>> from tt import apply_idempotent_law >>> apply_idempotent_law('A and A') <BooleanExpression "A"> >>> apply_idempotent_law('B or B') <BooleanExpression "B">
This transformation will consider similarly-negated operands to be redundant; for example:
>>> from tt import apply_idempotent_law >>> apply_idempotent_law('~A and ~~~A') <BooleanExpression "~A"> >>> apply_idempotent_law('B or ~B or ~~B or ~~~B or ~~~~B or ~~~~~B') <BooleanExpression "B or ~B">
Let’s also take a quick look at this transformation’s ability to prune redundant operands from CNF and DNF clauses:
>>> from tt import apply_idempotent_law >>> apply_idempotent_law('(A and B and C and C and B) or (A and A)') <BooleanExpression "(A and B and C) or A">
Of important note is that this transformation will not recursively apply the Idempotent Law to operands that bubble up. Here’s an example illustrating this case:
>>> from tt import apply_idempotent_law >>> apply_idempotent_law('(A or A) and (A or A)') <BooleanExpression "A and A">
-
tt.transformations.bexpr.
apply_identity_law
(expr)[source]¶ Convert an expression to a form with the Identity Law applied.
It should be noted that this transformation will also annihilate terms when possible. One such case where this would be applicable is the expression
A and 0
, which would be transformed to the constant value0
.Returns: A new expression object, transformed so that the Identity Law has been applied to applicable ANDs and ORs. Return type: BooleanExpression
Raises: InvalidArgumentTypeError – If expr
is not a valid type.Here are a few simple examples showing the behavior of this transformation across all two-operand scenarios:
>>> from tt import apply_identity_law >>> apply_identity_law('A and 1') <BooleanExpression "A"> >>> apply_identity_law('A and 0') <BooleanExpression "0"> >>> apply_identity_law('A or 0') <BooleanExpression "A"> >>> apply_identity_law('A or 1') <BooleanExpression "1">
-
tt.transformations.bexpr.
apply_inverse_law
(expr)[source]¶ Convert an expression to a form with the Inverse Law applied.
Returns: A new expression object, transformed so that the Inverse Law has been applied to applicable ANDs and ORs. Return type: BooleanExpression
Raises: InvalidArgumentTypeError – If expr
is not a valid type.This transformation will apply the Identity Law to simple binary expressions consisting of negated and non-negated forms of the same operand. Let’s take a look:
>>> from tt.transformations import apply_inverse_law >>> apply_inverse_law('A and ~A') <BooleanExpression "0"> >>> apply_inverse_law('A or B or ~B or C') <BooleanExpression "1">
This transformation will also apply the behavior expected of the Inverse Law when negated and non-negated forms of the same operand appear in the same CNF or DNF clause in an expression:
>>> from tt.transformations import apply_inverse_law >>> apply_inverse_law('(A or B or ~A) -> (C and ~C)') <BooleanExpression "1 -> 0"> >>> apply_inverse_law('(A or !!!A) xor (not C or not not C)') <BooleanExpression "1 xor 1">
-
tt.transformations.bexpr.
coalesce_negations
(expr)[source]¶ Convert an expression to a form with all negations condensed.
Returns: A new expression object, transformed so that all “runs” of logical NOTs are condensed into the minimal equivalent number. Return type: BooleanExpression
Raises: InvalidArgumentTypeError – If expr
is not a valid type.Here’s a simple example showing the basic premise of this transformation:
>>> from tt import coalesce_negations >>> coalesce_negations('~~A or ~B or ~~~C or ~~~~D') <BooleanExpression "A or ~B or ~C or D">
This transformation works on more complex expressions, too:
>>> coalesce_negations('!!(A -> not not B) or ~(~(A xor B))') <BooleanExpression "(A -> B) or (A xor B)">
It should be noted that this transformation will also apply negations to constant operands, as well. The behavior for this functionality is as follows:
>>> coalesce_negations('~0') <BooleanExpression "1"> >>> coalesce_negations('~1') <BooleanExpression "0"> >>> coalesce_negations('~~~0 -> ~1 -> not 1') <BooleanExpression "1 -> 0 -> 0">
-
tt.transformations.bexpr.
distribute_ands
(expr)[source]¶ Convert an expression to distribute ANDs over ORed clauses.
Parameters: expr ( str
orBooleanExpression
) – The expression to transform.Returns: A new expression object, transformed to distribute ANDs over ORed clauses. Return type: BooleanExpression
Raises: InvalidArgumentTypeError – If expr
is not a valid type.Here’s a couple of simple examples:
>>> from tt import distribute_ands >>> distribute_ands('A and (B or C or D)') <BooleanExpression "(A and B) or (A and C) or (A and D)"> >>> distribute_ands('(A or B) and C') <BooleanExpression "(A and C) or (B and C)">
And an example involving distributing a sub-expression:
>>> distribute_ands('(A and B) and (C or D or E)') <BooleanExpression "(A and B and C) or (A and B and D) or (A and B and E)">
-
tt.transformations.bexpr.
distribute_ors
(expr)[source]¶ Convert an expression to distribute ORs over ANDed clauses.
Parameters: expr ( str
orBooleanExpression
) – The expression to transform.Returns: A new expression object, transformed to distribute ORs over ANDed clauses. Return type: BooleanExpression
Raises: InvalidArgumentTypeError – If expr
is not a valid type.Here’s a couple of simple examples:
>>> from tt import distribute_ors >>> distribute_ors('A or (B and C and D and E)') <BooleanExpression "(A or B) and (A or C) and (A or D) and (A or E)"> >>> distribute_ors('(A and B) or C') <BooleanExpression "(A or C) and (B or C)">
And an example involving distributing a sub-expression:
>>> distribute_ors('(A or B) or (C and D)') <BooleanExpression "(A or B or C) and (A or B or D)">
-
tt.transformations.bexpr.
to_cnf
(expr)[source]¶ Convert an expression to conjunctive normal form (CNF).
This transformation only guarantees to produce an equivalent form of the passed expression in conjunctive normal form; the transformed expression may be an inefficent representation of the passed expression.
Parameters: expr ( str
orBooleanExpression
) – The expression to transform.Returns: A new expression object, transformed to be in CNF. Return type: BooleanExpression
Raises: InvalidArgumentTypeError – If expr
is not a valid type.Here are a few examples:
>>> from tt import to_cnf >>> b = to_cnf('(A nor B) impl C') >>> b <BooleanExpression "A or B or C"> >>> b.is_cnf True >>> b = to_cnf(r'~(~(A /\ B) /\ C /\ D)') >>> b <BooleanExpression "(A \/ ~C \/ ~D) /\ (B \/ ~C \/ ~D)"> >>> b.is_cnf True
-
tt.transformations.bexpr.
to_primitives
(expr)[source]¶ Convert an expression to a form with only primitive operators.
All operators will be transformed equivalent form composed only of the logical AND, OR,and NOT operators. Symbolic operators in the passed expression will remain symbolic in the transformed expression and the same applies for plain English operators.
Parameters: expr ( str
orBooleanExpression
) – The expression to transform.Returns: A new expression object, transformed to contain only primitive operators. Return type: BooleanExpression
Raises: InvalidArgumentTypeError – If expr
is not a valid type.Here’s a simple transformation of exclusive-or:
>>> from tt import to_primitives >>> to_primitives('A xor B') <BooleanExpression "(A and not B) or (not A and B)">
And another example of if-and-only-if (using symbolic operators):
>>> to_primitives('A <-> B') <BooleanExpression "(A /\ B) \/ (~A /\ ~B)">
transformations.utils
module¶
Utilities for building more complex transformations.
-
class
tt.transformations.utils.
ComposedTransformation
(fn, next_transformation=None, times=1)[source]¶ Bases:
tt.transformations.utils.RepeatableAction
An encapsulation of composed transformation functions.
This class opens up a world of functionality consisting of buildable (i.e., composed) transformation functions. While instances of this class will work when manually initialized by the user, it will likely be easier to compose functions using the
tt_compose()
method from this module.Transformation functions, held within the
fn
attribute of this class, are intended to be pure functions that both receive and produce an instance ofBooleanExpression
.When called, instances of this class will repeatedly apply the
fn
callable to the passed argument. The repeated application of thefn
callable will continue until either the specified number oftimes
is met or the callable produces no change to the expression during the transformation.Let’s take a look at a simple example, where all we do is compose two fairly basic transformations:
>>> from tt import coalesce_negations, to_primitives, tt_compose >>> f = tt_compose(to_primitives, coalesce_negations) >>> f <ComposedTransformation [to_primitives -> coalesce_negations]> >>> to_primitives('~A <-> ~B') <BooleanExpression "(~A /\ ~B) \/ (~~A /\ ~~B)"> >>> f('~A <-> ~B') <BooleanExpression "(~A /\ ~B) \/ (A /\ B)">
This fairly simple example gives us an idea of how to compose functions using the
tt_compose()
helper. A few operators make manual composition of instances of this class a little more intuitive, too. Let’s take a look at how we would make the same composition from above using the>>
operator:>>> from tt import ComposedTransformation >>> one = ComposedTransformation(to_primitives) >>> two = ComposedTransformation(coalesce_negations) >>> one >> two <ComposedTransformation [to_primitives -> coalesce_negations]>
The
>>
and<<
operators shown above are just shallow wrappers around the corecompose
function.It is important to note that instances of this class are immutable and hashable; consequently, they support
==
and!=
equality checks. We can see this by continuing our example from above:>>> three = ComposedTransformation(to_primitives) >>> one == two False >>> one == three True >>> two == three False
The hash of instances of this class is computed at initialization and never updated, so meddling with
ComposedTransformation
instances will likely have unintended consequences for you.Parameters: - fn (
Callable
) – The callable transformation function wrapped by this class. - next_transformation (
ComposedTransformation
) – The next transformation in the constructed composed sequence of transformation functions. - times (Typically an
int
) – The number of times the wrapped function is to be repeatedly applied to its passed argument when called.
Raises: - InvalidArgumentTypeError – If the passed
fn
argument is not a callable. - InvalidArgumentValueError – If
times
is not valid, as per theRepeatableAction
initialization logic.
-
__init__
(fn, next_transformation=None, times=1)[source]¶ Initialize self. See help(type(self)) for accurate signature.
-
compose
(other)[source]¶ Compose this transformation with another.
Parameters: other (A Callable
, instance ofComposedTransformation
, or instance ofAbstractTransformationModifier
.) – The callable transformation function, composed transformation object, or modifier object to either be composed with or modify this object.Returns: A new composed transformation instance, with the intended composition or modification applied. Return type: ComposedTransformation
Raises: InvalidArgumentType – If the other
argument is not of an expected type.
-
fn
¶ The callable transformation function that this class wraps.
This callable should both accept as an argument and produce as its result an instance of the
BooleanExpression
class.Type: Callable
>>> from tt import tt_compose, apply_de_morgans, twice >>> f = tt_compose(apply_de_morgans, twice) >>> f.fn.__name__ 'apply_de_morgans'
-
next_transformation
¶ The next transformation that this object’s result will be passed to.
The next transformation function in the chain of composed functions. A value of
None
indicates that this is the last function in the composition.Type: ComposedTransformation
- fn (
-
class
tt.transformations.utils.
RepeatableAction
(times=1)[source]¶ Bases:
object
A mixin for describing actions that can be repeated.
This class is meant to be used as a mixin when simple access to a
times
attribute is needed, presumably to perform some action or task multiple times. Here’s a simple look at the class:>>> from tt import RepeatableAction >>> r = RepeatableAction(5) >>> print(r) 5 times >>> r <RepeatableAction [5 times]> >>> r.times 5
The passed
times
argument to this class must be a value that implements__lt__
that is not less than 1. Here’s an example:>>> r = RepeatableAction(-1) Traceback (most recent call last): ... tt.errors.arguments.InvalidArgumentValueError: `times` must be at least 1
Instances of
RepeatableAction
are immutable, hashable, and implement all rich comparison operators. Let’s take a look:>>> r1, r2 = RepeatableAction(3), RepeatableAction(4) >>> hash(r1) 3 >>> hash(r2) 4 >>> r1 < r2 True >>> r1 == r2 False >>> r1 > r2 False >>> r3 = RepeatableAction(4) >>> r2 == r3 True
Parameters: times (Typically an int
) – The number of times that this action would be repeated when executed.Raises: InvalidArgumentValueError – If times
is less than 1.
-
tt.transformations.utils.
ensure_bexpr
(expr)[source]¶ Return an expression object or raise an InvalidArgumentTypeError.
Parameters: expr ( BooleanExpression
orstr
) – The expression whose type is being checked.Raises: InvalidArgumentTypeError – If expr
is not of a valid type.
-
tt.transformations.utils.
forever
= <RepeatableAction [inf times]>¶ A repeating modifier to perform a transformation forever.
Type: repeat
-
class
tt.transformations.utils.
repeat
(times)[source]¶ Bases:
tt.transformations.utils.AbstractTransformationModifier
,tt.transformations.utils.RepeatableAction
Factory for a repeating transformation modifier.
This factory method is largely meant to provide repeating modifier for the
tt_compose()
function. As an example, let’s compose a transformation that will be applied 7 times to expressions passed to it:>>> from tt import tt_compose, coalesce_negations, repeat >>> tt_compose(coalesce_negations, repeat(7)) <ComposedTransformation [coalesce_negations (7 times)]>
Check out the
twice
andforever
modifiers for some pre-made utilities that may come in handy.-
modify
(other)[source]¶ Modify a transformation composition or other modifier.
This method must be implemented by descendants of this class.
Parameters: other ( ComposedTransformation
orAbstractTransformationModifier
) – A transformation composition orReturns: A modified composition or modifier. Return type: The same type as other
-
-
tt.transformations.utils.
tt_compose
(*fns)[source]¶ Compose multiple transformations into a new callable transformation.
This function will compose multiple transformations and transformation modifiers into a single callable. When called, this new transformation will apply the composition to generate a transformed expression.
Parameters: fns (
Callable
,ComposedTransformation
, orAbstractTransformationModifier
) – A sequence of callable transformation functions or transformation modifiers from which a single composed transformation will be constructed.Returns: The callable composition of all functions in
fn
, which will return aBooleanExpression
object when called.Return type: Raises: - InvalidArgumentTypeError – If a modifier is ordered incorrectly or a non-callable function is included in the sequence.
- InvalidArgumentValueError – If an insufficient number of arguments is provided (must be at least 2).
Let’s say we wanted a transformation that would first convert all operators in our expression to their equivalent primitive form, and then apply De Morgan’s Law twice:
>>> from tt.transformations import * >>> f = tt_compose( ... to_primitives, ... apply_de_morgans, twice ... ) >>> f <ComposedTransformation [to_primitives -> apply_de_morgans (2 times)]> >>> f('~A <-> ~B') <BooleanExpression "(~A /\ ~B) \/ (~~A /\ ~~B)">
Composed transformations can be nested, too. Let’s add some functionality to our composed transformation so that all redundant negations are coalesced:
>>> g = tt_compose(f, coalesce_negations) >>> g <ComposedTransformation [to_primitives -> apply_de_morgans (2 times) -> coalesce_negations]> >>> g('~A <-> ~B') <BooleanExpression "(~A /\ ~B) \/ (A /\ B)">