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. άBoolOps.mesa Copyright Σ 1984, 1987 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 April 14, 1987 3:54:16 am 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šœB™BJšœ+Οk™.Jšœ2™5Icodešœ-™-—J™JšœRœ ™_J˜š œ˜ Jšœœœ˜Jšœœœ˜J˜—šΠbnœœ œ˜"J˜JšΟcM™MJšžœœœ˜,šΟb œœŸ˜,JšœŸ)˜>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™w—Jš ‘œœœœœ˜6J˜J™/Jš‘ œœœœ˜2Jš ‘ œœœœœ˜6J™0Jš‘œœœœ˜:Jš ‘œœœœœ˜>J˜Jšœ˜—J˜J˜J˜—…—ŽN