BoolOps:
CEDAR
DEFINITIONS =
BEGIN
-- all errors return a rope describing the problem, as well as an error code.
Error: ERROR[ec: ErrorCode, msg: Rope.ROPE];
ErrorCode:
TYPE = {Null,
-- never raised
InternalError, -- should never happen, but probably will
SyntaxError, -- input rope was not of proper syntax
UnknownOperator, -- a bad operator was found in an expression tree
BadPointer, -- expression tree contains a strange pointer
TreeIsNil, -- the passed tree was NIL and shouldn't be
EmptyExpression, -- an expression was found that had no children
VariableNotAnInput, -- a variable was used in an equation but is not one of the inputs (raised by SOPToTT)
NotSOP, -- tree is not in SOP form
DoubleInputs, -- two inputs have the same name
TTIsNil, -- the passed truth table was NIL and shouldn't be
UnknownTTBit -- strange bit in truth table
};
Operator:
TYPE = {And, Or, Not, None};
Tree: TYPE = SubTree;
SubTree: TYPE = REF ANY; -- either points to an 'Expression' or a 'Leaf'.
Expression:
TYPE =
RECORD [
op: Operator ← None,
children: LIST OF SubTree ← NIL
];
Leaf:
TYPE =
RECORD [
neg: BOOL ← FALSE,
var: ATOM
];
TruthBit: TYPE = {One, Zero, NC -- NC means no connection --};
PTerm:
TYPE =
RECORD [
-- If there are N inputs and M outputs, then the size of a product term is N+M and the first N values list the variables in the pterm and the next M values describe which outputs use this pterm.
bits: SEQUENCE size: NAT OF TruthBit
];
TruthTable: TYPE = REF TruthTableRec;
TruthTableRec:
TYPE =
RECORD [
numInputs, numOutputs, numPTerms: INT ← 0,
pterms: SEQUENCE size: NAT OF REF PTerm
];
Any procedure may raise the Error indication.
Convert a rope into an expresion tree.
RopeToTree: PROC [expr: Rope.ROPE] RETURNS [Tree];
Convert an expression tree into a rope.
TreeToRope: PROC [tree: Tree] RETURNS [Rope.ROPE];
Convert an arbitrary expression tree into sum-of-products (SOP) form.
TreeToSOP: PROC [tree: Tree] RETURNS [Tree];
Perform logical operations on SOP trees to produce another SOP tree.
SOPNot: PROC [tree: Tree] RETURNS [Tree];
SOPAnd: PROC [tree1, tree2: Tree] RETURNS [Tree];
SOPOr: PROC [tree1, tree2: Tree] RETURNS [Tree];
Optimize a truth table. Method used is tailored for PLAs.
TTOptimize: PROC [tt: TruthTable] RETURNS [TruthTable];
Convert between SOP equations and truth tables.
SOPToTT:
PROC [inputs:
LIST
OF
ATOM, equations:
LIST
OF Tree]
RETURNS [TruthTable];
-- SOPToTT eliminates redundant product terms.
-- The 'inputs' argument orders the inputs from [0..n) and the 'equations' argument orders the outputs in the same way.
TTToSOP: PROC [tt: TruthTable] RETURNS [LIST OF Tree];
Convert between truth tables and a text stream.
TTToStream: PROC [tt: TruthTable, out: IO.STREAM];
StreamToTT: PROC [in: IO.STREAM] RETURNS [TruthTable];
Same as above but in Berkeley truth table format
BerkeleyTTToStream: PROC [tt: TruthTable, out: IO.STREAM];
BerkeleyStreamToTT: PROC [in: IO.STREAM] RETURNS [TruthTable];
END.