DIRECTORY IO USING [STREAM], Rope USING [ROPE]; BoolOps: CEDAR DEFINITIONS = BEGIN 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 [ 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]; 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. ήFile: BoolOps.mesa Copyright c 1984 by Xerox Corporation. All rights reserved. Created by: Mayo, July 16, 1984 3:34:59 pm PDT Last Edited by: Mayo, August 24, 1984 12:16:14 pm PDT Bertrand Serlet May 27, 1986 3:14:16 pm PDT -- Operations on boolean equations consisting of named variables and the operators 'AND' and 'OR'. -- all errors return a rope describing the problem, as well as an error code. -- 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. Any procedure may raise the Error indication. Convert a rope into an expresion tree. Convert an expression tree into a rope. Convert an arbitrary expression tree into sum-of-products (SOP) form. Perform logical operations on SOP trees to produce another SOP tree. Optimize a truth table. Method used is tailored for PLAs. Convert between SOP equations and truth tables. -- 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. Convert between truth tables and a text stream. Same as above but in Berkeley truth table format Κ¨˜šœ™Jšœ Οmœ1™Jšœ‘&˜:Jšœ‘1˜GJšœ‘-˜@Jšœ‘+˜>Jšœ‘/˜EJšœ‘V˜nJšœ‘˜*Jšœ‘ ˜4Jšœ‘2˜CJšœ‘˜1Jšœ˜—J˜š œžœ˜&J˜—Jš œžœ ˜Jš  œžœžœžœ‘0˜LJ˜š  œžœžœ˜J˜Jšœ žœžœ ž˜J˜—š œžœžœ˜Jšœžœžœ˜Jšœž˜ J˜—J˜Jš œžœžœ‘œ˜>š œžœžœ˜J™ΒJšœžœžœžœ ˜$J˜—Jš  œžœžœ˜%š  œžœžœ˜Jšœ"žœ˜*Jš œžœžœžœžœ˜'J˜—J˜J™J™.J™J™&JšΟn œžœ žœžœ˜2J˜J™'Jš’ œžœžœžœ˜2J™J™EJš’ œžœžœ˜,J˜J™DJš’œžœžœ˜)Jš’œžœžœ˜1Jš’œžœžœ˜0J™J™:Jš’ œžœžœ˜7J˜J™/š’œžœ žœžœžœ žœžœžœ˜SJšœ.™.J™w—Jš ’œžœžœžœžœ˜6J˜J™/Jš’ œžœžœžœ˜2Jš ’ œžœžœžœžœ˜6J™0Jš’œžœžœžœ˜:Jš ’œžœžœžœžœ˜>J˜Jšžœ˜—J˜J˜J˜—…—Ž