<> <> <> <<>> <> <<>> DIRECTORY AlpsBool, Convert, FS, IO, Process, Rope, RopeList, TerminalIO; AlpsBoolImpl: CEDAR PROGRAM IMPORTS Convert, FS, IO, Process, Rope, RopeList, TerminalIO EXPORTS AlpsBool = BEGIN OPEN AlpsBool; <> <<>> <> true: PUBLIC Expression = NEW [ExpressionRec _ [varNb: 0, case: case11]]; false: PUBLIC Expression = NEW [ExpressionRec _ [varNb: 0, case: case11, norm: FALSE]]; RopeFromCompClass: PUBLIC PROC [case: CompClass] RETURNS [rope: ROPE] = { rope _ SELECT case FROM case11 => "case11", case10 => "case10", caseX1 => "caseX1", caseX0 => "caseX0", case1X => "case1X", case0X => "case0X", caseXNotX => "caseXNotX", caseXY => "caseXY", ENDCASE => ERROR; }; <> <<>> <> MakeComp: PUBLIC PROC [case: CompClass, varNb: VarNb, subexpr1, subexpr2: Expression, norm: BOOL _ TRUE] RETURNS [Expression] = {RETURN [NEW [ExpressionRec _ [ varNb: varNb, case: case, subexpr1: subexpr1, subexpr2: subexpr2, norm: norm]]]}; <> <> Comp: PUBLIC PROC [table: TableOfVariables, varNb: VarNb, whenTrue, whenFalse: Expression, norm: BOOL _ TRUE] RETURNS [Expression] = BEGIN SELECT TRUE FROM whenTrue=true => SELECT TRUE FROM whenFalse=true => RETURN [IF norm THEN true ELSE false]; whenFalse=false => RETURN [MakeComp[case10, varNb, NIL, NIL, norm]]; ENDCASE => RETURN [MakeComp[case1X, varNb, NIL, whenFalse, norm]]; whenTrue=false => SELECT TRUE FROM whenFalse=true => RETURN [MakeComp[case10, varNb, NIL, NIL, ~norm]]; whenFalse=false => RETURN [IF norm THEN false ELSE true]; ENDCASE => RETURN [MakeComp[case0X, varNb, NIL, whenFalse, norm]]; ENDCASE => SELECT TRUE FROM whenFalse=true => RETURN [MakeComp[caseX1, varNb, whenTrue, NIL, norm]]; whenFalse=false => RETURN [MakeComp[caseX0, varNb, whenTrue, NIL, norm]]; Equal[table, whenTrue, whenFalse, TRUE] => RETURN [Norm[whenTrue, norm]]; Equal[table, whenTrue, whenFalse, FALSE] => RETURN [MakeComp[caseXNotX, varNb, whenTrue, NIL, norm]]; ENDCASE => RETURN [MakeComp[caseXY, varNb, whenTrue, whenFalse, norm]]; END; <> WhenTrue: PUBLIC PROC [expr: Expression] RETURNS [Expression] = {RETURN [SELECT expr.case FROM case11, case10, case1X => true, case0X => false, caseX1, caseX0, caseXNotX, caseXY => expr.subexpr1, ENDCASE => ERROR]}; WhenFalse: PUBLIC PROC [expr: Expression] RETURNS [Expression] = {RETURN [SELECT expr.case FROM case11, caseX1 => true, case10, caseX0 => false, case0X, case1X, caseXY => expr.subexpr2, caseXNotX => Not[expr.subexpr1], ENDCASE => ERROR]}; Var, ExprFromVarNb: PUBLIC PROC [varNb: VarNb, norm: BOOL _ TRUE] RETURNS [Expression] = {RETURN [MakeComp[case10, varNb, true, false, norm]]}; <> <> <<{IF expr6#NIL THEN list _ LIST [expr6];>> <> <> <> <> <> Xor: PUBLIC PROC [table: TableOfVariables, expr1, expr2: Expression] RETURNS [expr: Expression] = { expr _ Or[ table, AndTwo[table, expr1, expr2, TRUE, FALSE], AndTwo[table, expr1, expr2, FALSE, TRUE]]; }; <> <> If: PUBLIC PROC [table: TableOfVariables, expr, exprTrue, exprFalse: Expression, norm: BOOL _ TRUE] RETURNS [Expression] = {RETURN [OrTwo[table, AndTwo[table, expr, exprTrue, TRUE, norm], AndTwo[table, expr, exprFalse, FALSE, norm]]]}; <> ExpandAux: PUBLIC PROC [table: TableOfVariables, expr: Expression] RETURNS [Expression] = { auxOutput: OutputRef _ table[expr.varNb].fromOutput; IF auxOutput=NIL THEN ERROR; IF auxOutput.type#aux THEN ERROR; RETURN [If[table, auxOutput.expr, WhenTrue[expr], WhenFalse[expr], expr.norm]]}; ExpanseAux: PUBLIC PROC [table: TableOfVariables, expr, auxExpr: Expression, auxVarNb: VarNb] RETURNS [Expression] = {RETURN [IF expr.varNbauxVarNb THEN Comp[ table, expr.varNb, ExpanseAux[table, WhenTrue[expr], auxExpr, auxVarNb], ExpanseAux[table, WhenFalse[expr], auxExpr, auxVarNb], expr.norm] ELSE If[table, auxExpr, WhenTrue[expr], WhenFalse[expr], expr.norm]]}; And: PUBLIC PROC [table: TableOfVariables, expr1, expr2, expr3, expr4, expr5, expr6: Expression _ true] RETURNS [Expression] = {RETURN [AndTwo[table, AndTwo[table, expr1, expr2], AndTwo[table, AndTwo[table, expr3, expr4], AndTwo[table, expr5, expr6]]]]}; AndList: PUBLIC PROC [table: TableOfVariables, exprs: LIST OF Expression] RETURNS [Expression] = {RETURN [IF exprs=NIL THEN true ELSE IF exprs.rest=NIL THEN exprs.first ELSE AndTwo[table, exprs.first, AndList[table, exprs.rest]]]}; AndTwo: PUBLIC PROC [table: TableOfVariables, expr1, expr2: Expression, norm1, norm2: BOOL _ TRUE] RETURNS [Expression] = {RETURN [NorTwo[table, expr1, expr2, ~norm1, ~norm2]]}; Or: PUBLIC PROC [table: TableOfVariables, expr1, expr2, expr3, expr4, expr5, expr6: Expression _ false] RETURNS [Expression] = {RETURN [OrTwo[table, OrTwo[table, expr1, expr2], OrTwo[table, OrTwo[table, expr3, expr4], OrTwo[table, expr5, expr6]]]]}; OrList: PUBLIC PROC [table: TableOfVariables, exprs: LIST OF Expression] RETURNS [Expression] = {RETURN [IF exprs=NIL THEN false ELSE IF exprs.rest=NIL THEN exprs.first ELSE OrTwo[table, exprs.first, OrList[table, exprs.rest]]]}; Nor: PUBLIC PROC [table: TableOfVariables, expr1, expr2, expr3, expr4, expr5, expr6: Expression _ false] RETURNS [Expression] = {RETURN [Not[Or[table, expr1, expr2, expr3, expr4, expr5, expr6]]]}; NorList: PUBLIC PROC [table: TableOfVariables, exprs: LIST OF Expression] RETURNS [Expression] = {RETURN [Not[OrList[table, exprs]]]}; NorTwo: PUBLIC PROC [table: TableOfVariables, expr1, expr2: Expression, norm1, norm2: BOOL _ TRUE] RETURNS [Expression] = {RETURN [Not[OrTwo[table, expr1, expr2, norm1, norm2]]]}; <> OrTwo: PUBLIC PROC [table: TableOfVariables, expr1, expr2: Expression, norm1, norm2: BOOL _ TRUE] RETURNS [result: Expression] = BEGIN varNb: VarNb _ 0; <> IF expr1 = (IF norm1 THEN true ELSE false) OR expr2 = (IF norm2 THEN true ELSE false) THEN RETURN [true]; IF expr1 = (IF norm1 THEN false ELSE true) THEN RETURN [Norm[expr2, norm2]]; IF expr2 = (IF norm2 THEN false ELSE true) THEN RETURN [Norm[expr1, norm1]]; <> varNb _ MAX [expr1.varNb, expr2.varNb]; result _ Comp[table, varNb, OrTwo[table, IF expr1.varNb=varNb THEN WhenTrue[expr1] ELSE expr1, IF expr2.varNb=varNb THEN WhenTrue[expr2] ELSE expr2, IF expr1.varNb=varNb THEN norm1=expr1.norm ELSE norm1, IF expr2.varNb=varNb THEN norm2=expr2.norm ELSE norm2], OrTwo[table, IF expr1.varNb=varNb THEN WhenFalse[expr1] ELSE expr1, IF expr2.varNb=varNb THEN WhenFalse[expr2] ELSE expr2, IF expr1.varNb=varNb THEN norm1=expr1.norm ELSE norm1, IF expr2.varNb=varNb THEN norm2=expr2.norm ELSE norm2]]; <", RopeFromExpression[table, result], "\n"];>> END; Norm: PUBLIC PROC [expr: Expression, norm: BOOL] RETURNS [Expression] = {RETURN [IF norm THEN expr ELSE Not[expr]]}; Not: PUBLIC PROC [expr: Expression] RETURNS [Expression] = {RETURN [IF expr = true THEN false ELSE IF expr = false THEN true ELSE MakeComp[varNb: expr.varNb, norm: ~expr.norm, case: expr.case, subexpr1: expr.subexpr1, subexpr2: expr.subexpr2]]}; <> <<>> NegCase: PROC [case: CompClass] RETURNS [CompClass] = {RETURN [SELECT case FROM case0X => case1X, case1X => case0X, caseX0 => caseX1, caseX1 => caseX0, ENDCASE => case]}; <> FullEqual: PUBLIC PROC [table: TableOfVariables, expr1, expr2: Expression, norm: BOOL _ TRUE] RETURNS [BOOL] = BEGIN IF expr1=expr2 THEN RETURN [norm]; norm _ IF expr1.norm=expr2.norm THEN norm ELSE ~norm; IF table[expr1.varNb].fromOutput#NIL THEN RETURN [FullEqual[table, ExpandAux[table, expr1], expr2, IF expr1.norm=expr2.norm THEN norm ELSE ~norm]]; IF table[expr2.varNb].fromOutput#NIL THEN RETURN [FullEqual[table, expr1, ExpandAux[table, expr2], IF expr1.norm=expr2.norm THEN norm ELSE ~norm]]; IF expr1.varNb#expr2.varNb THEN RETURN [FALSE]; IF expr1.case#(IF norm THEN expr2.case ELSE NegCase[expr2.case]) THEN RETURN [FALSE]; RETURN [SELECT expr1.case FROM case10, case11 => norm, caseX0, caseX1, caseXNotX => FullEqual[table, expr1.subexpr1, expr2.subexpr1, norm], case0X, case1X => FullEqual[table, expr1.subexpr2, expr2.subexpr2, norm], ENDCASE => FullEqual[table, expr1.subexpr1, expr2.subexpr1, norm] AND FullEqual[table, expr1.subexpr2, expr2.subexpr2, norm]]; END; Equal: PUBLIC PROC [table: TableOfVariables, expr1, expr2: Expression, norm: BOOL _ TRUE] RETURNS [BOOL] = BEGIN IF expr1=expr2 THEN RETURN [norm]; norm _ IF expr1.norm=expr2.norm THEN norm ELSE ~norm; IF expr1.varNb#expr2.varNb THEN RETURN [FALSE]; IF expr1.case#(IF norm THEN expr2.case ELSE NegCase[expr2.case]) THEN RETURN [FALSE]; RETURN [SELECT expr1.case FROM case10, case11 => norm, caseX0, caseX1, caseXNotX => Equal[table, expr1.subexpr1, expr2.subexpr1, norm], case0X, case1X => Equal[table, expr1.subexpr2, expr2.subexpr2, norm], ENDCASE => Equal[table, expr1.subexpr1, expr2.subexpr1, norm] AND Equal[table, expr1.subexpr2, expr2.subexpr2, norm]]; END; RopeFromExpression: PUBLIC PROC [table: TableOfVariables, expr: Expression, norm: BOOL _ TRUE, deep: INT _ 4] RETURNS [ROPE] = {IF deep<=0 THEN RETURN[" ... "]; IF ~expr.norm THEN norm _ ~norm; RETURN [IF norm THEN SELECT expr.case FROM case11 => "true", case10 => Rope.Cat["Var[", RopeFromVarNb[table, expr.varNb], "]"], caseX0 => Rope.Cat["And[", RopeFromVarNb[table, expr.varNb], ", ", RopeFromExpression[table, expr.subexpr1, TRUE, deep-1], "]"], caseX1 => Rope.Cat["Or[~", RopeFromVarNb[table, expr.varNb], ", ", RopeFromExpression[table, expr.subexpr1, TRUE, deep-1], "]"], case0X => Rope.Cat["And[~", RopeFromVarNb[table, expr.varNb], ", ", RopeFromExpression[table, expr.subexpr2, TRUE, deep-1], "]"], case1X => Rope.Cat["Or[", RopeFromVarNb[table, expr.varNb], ", ", RopeFromExpression[table, expr.subexpr2, TRUE, deep-1], "]"], caseXNotX => Rope.Cat["Xor[", RopeFromVarNb[table, expr.varNb], ", ", RopeFromExpression[table, expr.subexpr1 , FALSE, deep-1], "]"], ENDCASE => Rope.Cat["If[", RopeFromVarNb[table, expr.varNb], ", ", Rope.Cat[RopeFromExpression[table, expr.subexpr1, TRUE, deep-1], ", ", RopeFromExpression[table, expr.subexpr2, TRUE, deep-1], "]"]] ELSE SELECT expr.case FROM case11 => "false", case10 => Rope.Cat["~", RopeFromVarNb[table, expr.varNb]], caseX0 => Rope.Cat["Or[~", RopeFromVarNb[table, expr.varNb], ", ", RopeFromExpression[table, expr.subexpr1, FALSE, deep-1], "]"], caseX1 => Rope.Cat["And[", RopeFromVarNb[table, expr.varNb], ", ", RopeFromExpression[table, expr.subexpr1, FALSE, deep-1], "]"], case0X => Rope.Cat["Or[", RopeFromVarNb[table, expr.varNb], ", ", RopeFromExpression[table, expr.subexpr2, FALSE, deep-1], "]"], case1X => Rope.Cat["And[~", RopeFromVarNb[table, expr.varNb], ", ", RopeFromExpression[table, expr.subexpr2, FALSE, deep-1], "]"], caseXNotX => Rope.Cat["Xor[", RopeFromVarNb[table, expr.varNb], ", ", RopeFromExpression[table, expr.subexpr1, TRUE, deep-1], "]"], ENDCASE => Rope.Cat["If[", RopeFromVarNb[table, expr.varNb], ", ", Rope.Cat[RopeFromExpression[table, expr.subexpr1, FALSE, deep-1], ", ", RopeFromExpression[table, expr.subexpr2, FALSE, deep-1], "]"]]]}; AlpsRopeFromExpr: PUBLIC PROC [table: TableOfVariables, expr: Expression] RETURNS [rope: ROPE] = { AlpsVarFromExpr: PROC [expr: Expression, norm: BOOL _ TRUE] RETURNS [rope: ROPE] = { rope _ Rope.Cat["AlpsBool.Var[", RopeFromVarNb[table, expr.varNb], IF norm THEN "" ELSE ", FALSE", "]"]; }; IF expr=true THEN RETURN["AlpsBool.true"]; IF expr=false THEN RETURN["AlpsBool.false"]; IF ~expr.norm THEN RETURN[Rope.Cat["AlpsBool.Not[", AlpsRopeFromExpr[table, Not[expr]], "]"]]; rope _ SELECT expr.case FROM case10 => AlpsVarFromExpr[expr], caseX0 => Rope.Cat["table.And[", AlpsVarFromExpr[expr], ", ", AlpsRopeFromExpr[table, expr.subexpr1], "]"], caseX1 => Rope.Cat["table.Or[", AlpsVarFromExpr[expr, FALSE], ", ", AlpsRopeFromExpr[table, expr.subexpr1], "]"], case0X => Rope.Cat["table.And[", AlpsVarFromExpr[expr, FALSE], ", ", AlpsRopeFromExpr[table, expr.subexpr2], "]"], case1X => Rope.Cat["table.Or[", AlpsVarFromExpr[expr], ", ", AlpsRopeFromExpr[table, expr.subexpr2], "]"], caseXNotX => Rope.Cat["table.Xor[", AlpsVarFromExpr[expr, FALSE], ", ", AlpsRopeFromExpr[table, expr.subexpr1], "]"], caseXY => Rope.Cat["table.If[", AlpsVarFromExpr[expr], ", ", Rope.Cat[AlpsRopeFromExpr[table, expr.subexpr1], ", ", AlpsRopeFromExpr[table, expr.subexpr2], "]"]], ENDCASE => ERROR; }; <> <<{IF exprs#NIL THEN {rope _ RopeFromExpression[table, exprs.first]; exprs _ exprs.rest};>> <> <> <> <<>> nameCounter: INT _ 0; NewName: PUBLIC PROC [rope: ROPE _ NIL] RETURNS [ROPE] = {nameCounter _ nameCounter + 1; RETURN [Rope.Cat[rope, Convert.RopeFromInt[nameCounter]]]}; <<>> InitTableOfVariables: PUBLIC PROC [size: INT] RETURNS [table: TableOfVariables] = BEGIN Process.Yield[]; Process.SetPriority[Process.priorityBackground]; table _ NEW [TableOfVariablesRec[size]]; END; AddOutput: PUBLIC PROC [table: TableOfVariables, output: OutputRef] = { table.outputs _ CONS[output, table.outputs]; IF output.fedBackInput=0 THEN RETURN; table[output.fedBackInput].fromOutput _ output; }; VarNbFromRope: PUBLIC PROC [table: TableOfVariables, name: ROPE] RETURNS [varNb: VarNb] = BEGIN FOR i: VarNb IN [0..table.size) DO IF Rope.Equal[table[i].name, name] THEN RETURN [i] ENDLOOP; Output["Use of an illegal Variable\n"]; ERROR; END; RopeFromVarNb: PUBLIC PROC [table: TableOfVariables, varNb: VarNb] RETURNS [name: ROPE _ NIL] = { IF table[varNb].name=NIL THEN ERROR; RETURN [table[varNb].name]; }; <> <<{RETURN [IF list1=NIL THEN list2 ELSE CONS [list1.first, Append[list1.rest, list2]]]};>> <> <<{WHILE list#NIL DO newList _ CONS [list.first, newList]; list _ list.rest ENDLOOP};>> Input: PUBLIC PROC [text: ROPE] RETURNS [ROPE] = { RETURN[TerminalIO.RequestRope[text]]; }; Output: PUBLIC PROC [t1, t2, t3, t4, t5: ROPE _ NIL] = { TerminalIO.WriteRope[Rope.Cat[t1, t2, t3, t4, t5]]; }; <> ReadPLAFile: PUBLIC PROC [fileName: ROPE, inputs, outputs: LIST OF ROPE _ NIL] RETURNS [table: TableOfVariables] = BEGIN SkipNext: PUBLIC PROC [rope: ROPE] RETURNS [ROPE] = {RETURN [IF rope.IsEmpty THEN rope ELSE Rope.Substr[rope, 1]]}; SkipWhite: PUBLIC PROC [rope: ROPE] RETURNS [ROPE] = {RETURN [IF rope.IsEmpty OR rope.Fetch[0]#' THEN rope ELSE SkipWhite[SkipNext[rope]]]}; Nth: PROC [list: LIST OF ROPE, n: INT] RETURNS [x: ROPE] = { WHILE n>0 DO list _ list.rest; n _ n-1 ENDLOOP; x _ list.first; }; Skip: PROC [rope: ROPE] RETURNS [ROPE] = {RETURN[SkipWhite[SkipNext[rope]]]}; inStm: IO.STREAM _ FS.StreamOpen[fileName: fileName]; nbins, nbterms, nbouts: VarNb _ 0; <> DO -- for each line ENABLE IO.EndOfStream => EXIT; rope: ROPE _ SkipWhite[IO.GetLineRope[inStm]]; IF rope.IsEmpty OR (SELECT rope.Fetch[0] FROM '0, '1, '., '-, 'x, 'X => FALSE, ENDCASE => TRUE) THEN LOOP; WHILE ~rope.IsEmpty AND rope.Fetch[0]#'| DO IF nbterms=0 THEN nbins _ nbins+1; rope _ Skip[rope]; ENDLOOP; rope _ Skip[rope]; WHILE ~rope.IsEmpty DO IF nbterms=0 THEN nbouts _ nbouts+1; rope _ Skip[rope]; ENDLOOP; Output["."]; nbterms _ nbterms+1; ENDLOOP; <<2nd Pass>> IF inputs=NIL AND outputs=NIL THEN { Output["First pass on ", fileName, " done: ", Convert.RopeFromInt[nbins]]; Output[" inputs; ", Convert.RopeFromInt[nbterms]]; Output[" terms; ", Convert.RopeFromInt[nbouts], " outputs.\n"]; FOR i: INT DECREASING IN [0..nbins) DO inputs _ CONS[Rope.Cat["Input", Convert.RopeFromInt[i]], inputs]; ENDLOOP; FOR i: INT DECREASING IN [0..nbouts) DO outputs _ CONS[Rope.Cat["Output", Convert.RopeFromInt[i]], outputs]; ENDLOOP; } ELSE { IF nbins#RopeList.Length[inputs] THEN {Output["Number of inputs of the TruthTable (", Convert.RopeFromInt[nbins], ") does NOT agree with the inputs given.\n"]; ERROR}; IF nbouts#RopeList.Length[outputs] THEN {Output["Number of outputs of the TruthTable (", Convert.RopeFromInt[nbouts], ") does NOT agree with the outputs given.\n"]; ERROR}; }; <> table _ InitTableOfVariables[nbins+nbterms+1]; FOR i: VarNb IN [1..nbins] DO table[i].name _ Nth[inputs, i-1] ENDLOOP; FOR i: VarNb DECREASING IN [0..nbouts) DO AddOutput[table, NEW [OutputRec _ [name: Nth[outputs, i], expr: false]]]; ENDLOOP; <> inStm _ FS.StreamOpen[fileName: fileName]; Output["\n"]; FOR term: VarNb IN [1..nbterms] DO -- for each line termName: ROPE _ Rope.Cat["Term", Convert.RopeFromInt[term]]; operands: LIST OF Expression _ NIL; -- operands making the AND plane rope: ROPE _ ""; WHILE rope.IsEmpty OR (SELECT rope.Fetch[0] FROM '0, '1, '., '-, 'x, 'X => FALSE, ENDCASE => TRUE) DO rope _ SkipWhite[IO.GetLineRope[inStm]] ENDLOOP; FOR input: VarNb IN [1..nbins] DO IF rope.Fetch[0]='1 THEN operands _ CONS [ExprFromVarNb[nbins+1-input], operands]; IF rope.Fetch[0]='0 THEN operands _ CONS [ExprFromVarNb[nbins+1-input, FALSE], operands]; rope _ Skip[rope]; ENDLOOP; IF rope.Fetch[0]#'| THEN ERROR; rope _ Skip[rope]; table[nbins+term].name _ termName; AddOutput[table, NEW [OutputRec _ [ name: termName, expr: AndList[table, operands], type: aux, fedBackInput: nbins+term ]]]; <> FOR outs: LIST OF OutputRef _ table.outputs, outs.rest WHILE outs#NIL DO IF outs.first.type=output THEN { IF rope.Fetch[0]='1 THEN outs.first.expr _ Or[table, Var[nbins+term], outs.first.expr]; rope _ Skip[rope]; }; ENDLOOP; Output["."]; ENDLOOP; Output["\n"]; END; DumpTT: PUBLIC PROC [table: TableOfVariables, stream: IO.STREAM] = { FOR outs: LIST OF OutputRef _ table.outputs, outs.rest WHILE outs#NIL DO PrintTerm: PROC [previousRope: ROPE, previousInput: VarNb, expr: Expression, out: OutputRef, norm: BOOL _ TRUE] = { norm _ norm=expr.norm; IF expr.case=case11 THEN { IF norm THEN { THROUGH (0..previousInput) DO previousRope _ Rope.Cat[previousRope, "-"] ENDLOOP; IO.PutRope[stream, previousRope]; IO.PutRope[stream, " | "]; FOR outs: LIST OF OutputRef _ table.outputs, outs.rest WHILE outs#NIL DO IO.PutRope[stream, IF outs.first=out THEN "1" ELSE "."]; ENDLOOP; IO.PutRope[stream, "\n"]; }; RETURN; }; THROUGH (expr.varNb .. previousInput) DO previousRope _ Rope.Cat[previousRope, "-"]; ENDLOOP; PrintTerm[Rope.Cat[previousRope, "1"], expr.varNb, WhenTrue[expr], out, norm]; PrintTerm[Rope.Cat[previousRope, "0"], expr.varNb, WhenFalse[expr], out, norm]; }; IF outs.first.type=aux THEN ERROR; PrintTerm["", table.size, outs.first.expr, outs.first]; ENDLOOP; }; DumpAlps: PUBLIC PROC [table: TableOfVariables, name: ROPE, stream: IO.STREAM] = { QuoteRope: PROC [rope: ROPE] RETURNS [ROPE] = {RETURN[Rope.Cat["""", rope, """"]]}; stream.PutRope["DIRECTORY AlpsBool;\n"]; stream.PutRope[Rope.Cat[name, ": CEDAR PROGRAM IMPORTS AlpsBool = BEGIN\n"]]; stream.PutRope["AlpsTable: PUBLIC PROC RETURNS [table: AlpsBool.TableOfVariables] = {\n"]; FOR i: VarNb IN [1 .. table.size) DO stream.PutRope[Rope.Cat[" ", table[i].name, ": AlpsBool.VarNb = ", Convert.RopeFromInt[i], ";\n"]]; ENDLOOP; stream.PutRope[Rope.Cat[" table _ AlpsBool.InitTableOfVariables[", Convert.RopeFromInt[table.size],"];\n"]]; FOR i: VarNb IN [1 .. table.size) DO stream.PutRope[Rope.Cat[" table[", table[i].name, "].name _ ", QuoteRope[table[i].name], ";\n"]]; ENDLOOP; FOR outs: LIST OF OutputRef _ table.outputs, outs.rest WHILE outs#NIL DO stream.PutRope[Rope.Cat[" AlpsBool.AddOutput[table, NEW[AlpsBool.OutputRec _ [name: "]]; stream.PutRope[Rope.Cat[QuoteRope[outs.first.name], ", fedBackInput: ", Convert.RopeFromInt[outs.first.fedBackInput], ", type: ", SELECT outs.first.type FROM aux => "aux", output => "output", latch => "latch", ENDCASE => ERROR]]; stream.PutRope[Rope.Cat[", expr: ", AlpsRopeFromExpr[table, outs.first.expr], "]]];\n"]]; ENDLOOP; stream.PutRope[" };\n"]; stream.PutRope["END.\n"]; }; Enumerate: PUBLIC PROC [expr: Expression, eachNodeProc: EachNodeProc] = { IF eachNodeProc[expr] THEN RETURN; SELECT expr.case FROM case11, case10 => {}; caseX1, caseX0, caseXNotX => Enumerate[expr.subexpr1, eachNodeProc]; case1X, case0X => Enumerate[expr.subexpr2, eachNodeProc]; ENDCASE => {Enumerate[expr.subexpr1, eachNodeProc]; Enumerate[expr.subexpr2, eachNodeProc]}; }; CopyTree: PUBLIC PROC [table: TableOfVariables, expr: Expression, eachBranchProc: EachBranchProc] RETURNS [newExpr: Expression] = { subTrue: Expression _ eachBranchProc[WhenTrue[expr]]; subFalse: Expression _ eachBranchProc[WhenFalse[expr]]; newExpr _ Comp[table, expr.varNb, subTrue, subFalse, expr.norm]; }; Size: PUBLIC PROC [table: TableOfVariables, expr: Expression, varNb: VarNb] RETURNS [size: INT _ 0] = { SizeProc: EachNodeProc = {size _ size + 1}; Enumerate[expr, SizeProc]; }; NbOfCaseXY: PUBLIC PROC [table: TableOfVariables, expr: Expression] RETURNS [nbCaseXY: INT _ 0] = { NbOfCaseXYProc: EachNodeProc = {IF expr.case=caseXY THEN nbCaseXY _ nbCaseXY+1}; Enumerate[expr, NbOfCaseXYProc]; }; NbOfCaseXNotX: PUBLIC PROC [table: TableOfVariables, expr: Expression] RETURNS [nbCaseXNotX: INT _ 0] = { NbOfCaseXNotXProc: EachNodeProc = {IF expr.case=caseXNotX THEN nbCaseXNotX _ nbCaseXNotX+1}; Enumerate[expr, NbOfCaseXNotXProc]; }; MaxWidth: PUBLIC PROC [table: TableOfVariables, expr: Expression] RETURNS [INT] = { RETURN [1+NbOfCaseXY[table, expr]+NbOfCaseXNotX[table, expr]]; }; MinWidth: PUBLIC PROC [table: TableOfVariables] RETURNS [minWidth: INT _ 0] = { FOR input: VarNb IN [1..table.size) DO width: INT _ 0; ExprAddWidth: EachNodeProc = {IF expr.varNb<=input THEN {width _ width+1; quit _ TRUE}}; FOR outs: LIST OF OutputRef _ table.outputs, outs.rest WHILE outs#NIL DO Enumerate[outs.first.expr, ExprAddWidth]; ENDLOOP; minWidth _ MAX[width, minWidth]; ENDLOOP; }; <> NoUsedVarsSequence: PUBLIC PROC [table: TableOfVariables] RETURNS [allFalseUsedVarSequence: UsedVarsSequence] = { allFalseUsedVarSequence _ NEW [UsedVarsSequenceRec[table.size]]; FOR i: VarNb IN [1 .. table.size) DO allFalseUsedVarSequence[i] _ FALSE ENDLOOP; }; ExprAddUsedVars: PUBLIC PROC [expr: Expression, usedVars: UsedVarsSequence] = { ExprAddUsedVarsProc: EachNodeProc = {usedVars[expr.varNb] _ TRUE}; Enumerate[expr, ExprAddUsedVarsProc]; }; NbVars: PUBLIC PROC [table: TableOfVariables, expr: Expression] RETURNS [nb: INT _ 0] = { usedVars: UsedVarsSequence _ NoUsedVarsSequence[table]; ExprAddUsedVars[expr, usedVars]; FOR i: VarNb IN [1 .. table.size) DO IF usedVars[i] THEN nb _ nb + 1 ENDLOOP; }; NbUsedVar: PUBLIC PROC [expr: Expression, varNb: VarNb] RETURNS [nbUsedVar: INT _ 0] = { NbUsedVarProc: EachNodeProc = {quit _ expr.varNb<=varNb; IF expr.varNb=varNb THEN nbUsedVar _ nbUsedVar+1}; Enumerate[expr, NbUsedVarProc]; }; Deep: PUBLIC PROC [table: TableOfVariables, expr: Expression] RETURNS [INT] = { DeepVarNb: PUBLIC PROC [varNb: VarNb] RETURNS [INT] = { RETURN [IF table[varNb].fromOutput#NIL AND table[varNb].fromOutput.type=aux THEN 3+Deep[table, table[varNb].fromOutput.expr] ELSE 0]; }; RETURN [SELECT expr.case FROM case11 => 0, case10 => DeepVarNb[expr.varNb], caseX1, caseX0, caseXNotX => 1 + MAX [DeepVarNb[expr.varNb], Deep[table, expr.subexpr1]], case1X, case0X => 1 + MAX [DeepVarNb[expr.varNb], Deep[table, expr.subexpr2]], ENDCASE => 1 + MAX [DeepVarNb[expr.varNb], Deep[table, expr.subexpr1], Deep[table, expr.subexpr2]]]; }; NbOfVars: PUBLIC PROC [table: TableOfVariables] RETURNS [input, aux, output, latch: VarNb _ 0] = { FOR outs: LIST OF OutputRef _ table.outputs, outs.rest WHILE outs#NIL DO SELECT outs.first.type FROM aux => aux _ aux + 1; output => output _ output + 1; latch => latch _ latch+1; ENDCASE => ERROR; ENDLOOP; input _ table.size-1-aux; }; <> PrintExpression: PUBLIC PROC [table: TableOfVariables, output: OutputRef, printLevel: INT _ 4] RETURNS [size, nbOfCaseXY, maxWidth, deep: INT] = BEGIN expr: Expression _ output.expr; Process.Yield[]; size _ Size[table, expr, table.size-1]; nbOfCaseXY _ NbOfCaseXY[table, expr]; maxWidth _ MaxWidth[table, expr]; deep _ Deep[table, expr]; IF printLevel#0 THEN Output[ SELECT output.type FROM aux => "Aux ", latch => "Latch ", output => "Output ", ENDCASE => ERROR, output.name, IF output.fedBackInput#0 THEN Rope.Cat[" (fedBackInput: ", table[output.fedBackInput].name, ") : "] ELSE ": ", RopeFromExpression[table, expr, TRUE, printLevel], "\n" ]; IF printLevel#0 THEN { Output[" size: ", Convert.RopeFromInt[size], " NbOfCaseXY: ", Convert.RopeFromInt[nbOfCaseXY]]; Output[" MaxWidth: ", Convert.RopeFromInt[maxWidth], " Deep: ", Convert.RopeFromInt[deep], "\n"]; }; END; TableStatistics: PUBLIC PROC [table: TableOfVariables, print: BOOL _ FALSE] RETURNS [area, sigmaSize, sigmaNbOfCaseXY, sigmaMaxWidth, maxDeep: INT _ 0] = { nbOfCasesArray: NbOfCasesArray _ ALL[0]; addCase: EachNodeProc = { case: CompClass _ IF expr.norm THEN expr.case ELSE NegCase[expr.case]; nbOfCasesArray[case] _ nbOfCasesArray[case] + 1; }; FOR outs: LIST OF OutputRef _ table.outputs, outs.rest WHILE outs#NIL DO size, nbOfCaseXY, maxWidth, deep: INT; [size, nbOfCaseXY, maxWidth, deep] _ PrintExpression[table, outs.first, 0]; sigmaSize _ sigmaSize + size; sigmaNbOfCaseXY _ sigmaNbOfCaseXY + nbOfCaseXY; sigmaMaxWidth _ sigmaMaxWidth + maxWidth; maxDeep _ MAX [maxDeep, deep]; Enumerate[outs.first.expr, addCase]; ENDLOOP; IF print THEN { FOR case: CompClass IN CompClass DO Output[RopeFromCompClass[case], ": ", Convert.RopeFromInt[nbOfCasesArray[case]], "; "]; ENDLOOP; Output["\n"]; }; area _ EstimatedArea[table]; <> <> <> <> <> <> <> < "];>> <> <> <> <> <> IF print THEN { Output["\n**** sigmaSize: ", Convert.RopeFromInt[sigmaSize]]; Output[" sigmaNbOfCaseXY: ", Convert.RopeFromInt[sigmaNbOfCaseXY]]; Output[" MinWidth: ", Convert.RopeFromInt[MinWidth[table]]]; Output[" sigmaMaxWidth: ", Convert.RopeFromInt[sigmaMaxWidth]]; Output[" maxDeep: ", Convert.RopeFromInt[maxDeep], "\n\n"]; }; }; <> PrintTable: PUBLIC PROC [table: TableOfVariables, printLevel: INT _ 4] = BEGIN Output["\n"]; FOR outs: LIST OF OutputRef _ table.outputs, outs.rest WHILE outs#NIL DO [] _ PrintExpression[table, outs.first, printLevel]; ENDLOOP; [] _ TableStatistics[table, TRUE]; END; IdentityRenum: PUBLIC RenumProc = {newVarNb _ oldVarNb}; ChangeVars: PUBLIC PROC [table: TableOfVariables, expr: Expression, renumProc: RenumProc] RETURNS [Expression] = { NoChange: PROC [expr: Expression] RETURNS [BOOL] = { RETURN [expr=true OR expr=false OR (renumProc[expr.varNb]=expr.varNb AND NoChange[WhenTrue[expr]] AND NoChange[WhenFalse[expr]])]; }; RETURN [IF NoChange[expr] THEN expr ELSE If[ table, ExprFromVarNb[renumProc[expr.varNb]], ChangeVars[table, WhenTrue[expr], renumProc], ChangeVars[table, WhenFalse[expr], renumProc], expr.norm]]; }; Factorize: PUBLIC PROC [table: TableOfVariables, expr, aux: Expression, auxVar: VarNb] RETURNS [Expression] = BEGIN <> EvalExprWhenAuxIs: PUBLIC PROC [expr, aux: Expression, norm: BOOLEAN] RETURNS [res: Expression _ NIL] = BEGIN subTrue, subFalse: Expression; SELECT TRUE FROM expr=false OR expr=true => RETURN [expr]; expr.varNb>aux.varNb => BEGIN subTrue _ EvalExprWhenAuxIs[WhenTrue[expr], aux, norm]; IF subTrue=NIL THEN RETURN; subFalse _ EvalExprWhenAuxIs[WhenFalse[expr], aux, norm]; IF subFalse=NIL THEN RETURN; RETURN [Comp[table, expr.varNb, subTrue, subFalse, expr.norm]]; END; <> FullEqual[table, WhenTrue[aux], true, ~norm] => RETURN [EvalExprWhenAuxIs[IF expr.varNb=aux.varNb THEN WhenFalse[expr] ELSE expr, WhenFalse[aux], norm]]; <> FullEqual[table, WhenTrue[aux], true, ~norm] => RETURN [EvalExprWhenAuxIs[IF expr.varNb=aux.varNb THEN WhenTrue[expr] ELSE expr, WhenTrue[aux], norm]]; ENDCASE => BEGIN subTrue _ EvalExprWhenAuxIs[IF expr.varNb=aux.varNb THEN WhenTrue[expr] ELSE expr, WhenTrue[aux], norm]; IF subTrue=NIL THEN RETURN; subFalse _ EvalExprWhenAuxIs[IF expr.varNb=aux.varNb THEN WhenFalse[expr] ELSE expr, WhenFalse[aux], norm]; IF subFalse=NIL THEN RETURN; IF ~FullEqual[table, subTrue, subFalse, TRUE] THEN RETURN; -- no way to be independent of that variable RETURN [subTrue]; END; END; IF expr=true OR expr=false THEN RETURN [expr]; IF expr.varNb > aux.varNb THEN RETURN [Comp[ table, expr.varNb, Factorize[table, WhenTrue[expr], aux, auxVar], Factorize[table, WhenFalse[expr], aux, auxVar], expr.norm]]; IF expr.varNb> IF Equal[table, expr, aux] THEN {Output["="]; RETURN [ExprFromVarNb[auxVar, TRUE]]}; IF Equal[table, expr, aux, FALSE] THEN {Output["="]; RETURN [ExprFromVarNb[auxVar, FALSE]]}; <> Output["/"]; -- to show we are starting the real work BEGIN subTrue, subFalse, fact: Expression; subTrue _ EvalExprWhenAuxIs[expr, aux, TRUE]; IF subTrue=NIL THEN RETURN [expr]; -- failed! subFalse _ EvalExprWhenAuxIs[expr, aux, FALSE]; IF subFalse=NIL THEN RETURN [expr]; -- failed! fact _ Comp[table, auxVar, subTrue, subFalse]; IF NbOfCaseXY[table, fact] < NbOfCaseXY[table, expr] THEN {Output["*"]; RETURN [fact]}; Output["?"]; -- probably a bug in the algorithm if this appear RETURN [expr]; END; END; Permute2Vars: PUBLIC PROC [table: TableOfVariables, varNb1, varNb2: VarNb] RETURNS [newTable: TableOfVariables] = { Renum: RenumProc = {RETURN [IF oldVarNb=varNb1 THEN varNb2 ELSE IF oldVarNb=varNb2 THEN varNb1 ELSE oldVarNb]}; newTable _ InitTableOfVariables[table.size]; FOR i: VarNb IN [1 .. table.size) DO newTable[Renum[i]].name _ table[i].name; ENDLOOP; FOR outs: LIST OF OutputRef _ table.outputs, outs.rest WHILE outs#NIL DO output: OutputRef _ outs.first; AddOutput[newTable, NEW[OutputRec _ [name: output.name, type: output.type, expr: ChangeVars[newTable, output.expr, Renum], fedBackInput: Renum[output.fedBackInput]]]]; ENDLOOP; }; ExprWhenVarIs: PUBLIC PROC [table: TableOfVariables, expr: Expression, varNb: VarNb, varNbNorm: BOOL _ TRUE] RETURNS [newExpr: Expression] = { IsUsed: EachNodeProc = {quit _ expr.varNb<=varNb; isUsed _ expr.varNb=varNb}; isUsed: BOOL _ FALSE; Construct: EachBranchProc = { IF expr.varNb