<> <> <> <> <> <<>> <<-- Operations on boolean equations consisting of named variables and the operators 'AND' and 'OR'.>> DIRECTORY IO USING [STREAM], Rope USING [ROPE]; 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 ]; <<>> <> <<>> <> RopeToTree: PROC [expr: Rope.ROPE] RETURNS [Tree]; <> TreeToRope: PROC [tree: Tree] RETURNS [Rope.ROPE]; <<>> <> TreeToSOP: PROC [tree: Tree] RETURNS [Tree]; <> SOPNot: PROC [tree: Tree] RETURNS [Tree]; SOPAnd: PROC [tree1, tree2: Tree] RETURNS [Tree]; SOPOr: PROC [tree1, tree2: Tree] RETURNS [Tree]; <<>> <> TTOptimize: PROC [tt: TruthTable] RETURNS [TruthTable]; <> 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]; <> TTToStream: PROC [tt: TruthTable, out: IO.STREAM]; StreamToTT: PROC [in: IO.STREAM] RETURNS [TruthTable]; <> BerkeleyTTToStream: PROC [tt: TruthTable, out: IO.STREAM]; BerkeleyStreamToTT: PROC [in: IO.STREAM] RETURNS [TruthTable]; END.