CoreBooleExtrasImpl:
CEDAR
PROGRAM
IMPORTS CoreBoole, CoreOps, CoreProperties, FS, IO, Rope, RopeList, TerminalIO
EXPORTS CoreBooleExtras =
BEGIN
OPEN CoreBooleExtras;
false: Expression = CoreBoole.false;
true: Expression = CoreBoole.true;
Size:
PUBLIC
PROC [expr: Expression]
RETURNS [size:
INT ← 0] = {
var: ROPE ← CoreBoole.FindVar[expr];
whenTrue, whenFalse: Expression;
IF var=NIL THEN RETURN;
[whenTrue, whenFalse] ← CoreBoole.Eval[var, expr];
IF CoreBoole.Equal[whenTrue, true] OR CoreBoole.Equal[whenTrue, false] THEN RETURN[Size[whenFalse]];
IF CoreBoole.Equal[whenFalse, true] OR CoreBoole.Equal[whenFalse, false] THEN RETURN[Size[whenTrue]];
size ← 1 + Size[whenTrue] + Size[whenFalse];
};
Reorder:
PUBLIC
PROC [expr: Expression, public: Wire]
RETURNS [newExpr: Expression] = {
vars: LIST OF ROPE ← NIL;
AddToVars: CoreOps.EachWireProc = {
IF wire.size=0 THEN vars ← CONS [CoreOps.GetShortWireName[wire], vars];
};
[] ← CoreOps.VisitWire[public, AddToVars];
vars ← RopeList.Reverse[vars];
RETURN [ReorderVars[expr, vars]];
};
ReorderVars:
PUBLIC
PROC [expr: Expression, vars:
LIST
OF
ROPE]
RETURNS [newExpr: Expression] = {
var: ROPE;
whenTrue, whenFalse: Expression;
IF expr=true OR expr=false THEN RETURN [expr];
var ← vars.first;
[whenTrue, whenFalse] ← CoreBoole.Eval[var, expr];
newExpr ← CoreBoole.If[CoreBoole.Var[var], ReorderVars[whenTrue, vars.rest], ReorderVars[whenFalse, vars.rest]];
};
coreBoolePermuteProp: PUBLIC ATOM ← CoreProperties.RegisterProperty[$CoreBoolePermuteProp];
Permute:
PUBLIC
PROC [expr: Expression, public: Wire]
RETURNS [bestPermutedExpr: Expression, bestPermutedWire: Wire] = {
SeqListWire: TYPE = REF SeqListWireRec;
SeqListWireRec: TYPE = RECORD [c: SEQUENCE size: NAT OF LIST OF Wire];
CartesianProduct: PROC [seqListWire: SeqListWire, permutations: LIST OF Wire] RETURNS [newPermutations: LIST OF Wire] = {
size: NAT ← seqListWire.size;
wire: Wire;
FOR i: NAT IN [0 .. size) DO
IF seqListWire[i].rest#NIL THEN {
seqListWire1: SeqListWire ← NEW [SeqListWireRec[size]];
seqListWire2: SeqListWire ← NEW [SeqListWireRec[size]];
FOR j: NAT IN [0 .. size) DO
IF i#j
THEN {seqListWire1[j] ← seqListWire[j]; seqListWire2[j] ← seqListWire[j]}
ELSE {seqListWire1[j] ← LIST [seqListWire[j].first]; seqListWire2[j] ← seqListWire[j].rest};
ENDLOOP;
newPermutations ← CartesianProduct[seqListWire1, CartesianProduct[seqListWire2, permutations]];
RETURN;
};
ENDLOOP;
wire ← NEW [WireRec ← [structure: record, elements: NEW [WireSequenceRec[size]]]];
FOR i: NAT IN [0 .. size) DO
wire.elements[i] ← seqListWire[i].first;
ENDLOOP;
newPermutations ← CONS [wire, permutations];
};
PermuteSeqListWire: PROC [rank: NAT, seqListWire: SeqListWire, permutations: LIST OF SeqListWire] RETURNS [newPermutations: LIST OF SeqListWire] = {
size: NAT ← seqListWire.size;
newPermutations ← permutations;
IF rank=0 THEN RETURN [CONS[seqListWire, newPermutations]];
FOR i: NAT IN [0 .. rank] DO
newSeqListWire: SeqListWire ← NEW [SeqListWireRec[size]];
FOR j: NAT IN [0 .. size) DO
newSeqListWire[j] ← seqListWire[IF j=i THEN rank ELSE IF j=rank THEN i ELSE j];
ENDLOOP;
newPermutations ← PermuteSeqListWire[rank-1, newSeqListWire, newPermutations];
ENDLOOP;
};
EnumeratePermutedWires: PROC [wire: Wire] RETURNS [permutations: LIST OF Wire] = {
size: NAT;
IF wire.structure=atom THEN RETURN [LIST[wire]];
size ← wire.elements.size;
SELECT CoreProperties.GetProp[wire.properties, coreBoolePermuteProp] FROM
$DoNot => RETURN [LIST[wire]];
$DoNotButDoSons => {
seqListWire: SeqListWire ← NEW [SeqListWireRec[size]];
FOR i: NAT IN [0 .. size) DO
seqListWire[i] ← EnumeratePermutedWires[wire.elements[i]];
ENDLOOP;
permutations ← CartesianProduct[seqListWire, NIL];
};
$DoNotApartReverse => {
seqListWire: SeqListWire ← NEW [SeqListWireRec[size]];
revSeqListWire: SeqListWire ← NEW [SeqListWireRec[size]];
FOR i: NAT IN [0 .. size) DO
seqListWire[i] ← EnumeratePermutedWires[wire.elements[i]];
ENDLOOP;
FOR i: NAT IN [0 .. size) DO
revSeqListWire[i] ← seqListWire[size-i-1];
ENDLOOP;
permutations ← CartesianProduct[seqListWire, NIL];
permutations ← CartesianProduct[revSeqListWire, permutations];
}
ENDCASE => {
seqListWire: SeqListWire ← NEW [SeqListWireRec[size]];
listSeqListWire: LIST OF SeqListWire;
FOR i: NAT IN [0 .. size) DO
seqListWire[i] ← EnumeratePermutedWires[wire.elements[i]];
ENDLOOP;
listSeqListWire ← PermuteSeqListWire[size-1, seqListWire, NIL];
WHILE listSeqListWire#NIL DO
permutations ← CartesianProduct[listSeqListWire.first, permutations];
listSeqListWire ← listSeqListWire.rest;
ENDLOOP;
};
};
min: INT ← LAST[INT];
permutations: LIST OF Wire ← EnumeratePermutedWires[public];
bestPermutedExpr ← expr;
bestPermutedWire ← public;
WHILE permutations#NIL DO
expr ← Reorder[bestPermutedExpr, permutations.first];
IF Size[expr]<min THEN {bestPermutedExpr ← expr; bestPermutedWire ← permutations.first; min ← Size[expr]};
permutations ← permutations.rest;
Process.CheckForAbort[! ANY => EXIT]; Process.Yield[];
ENDLOOP;
};
ReadPLAFile:
PUBLIC
PROC [fileName:
ROPE, inputs, outputs:
LIST
OF
ROPE ←
NIL]
RETURNS [exprs: ExprsSeq] =
BEGIN
terms: ExprsSeq;
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: NAT ← 0;
We make a first pass to count the number of inputs, terms and outputs
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;
TerminalIO.WriteF["."];
nbterms ← nbterms+1;
ENDLOOP;
2nd Pass
IF inputs=
NIL
AND outputs=
NIL
THEN {
TerminalIO.WriteF["First pass on %g done: %g inputs; %g terms; %g outputs.\n", IO.rope[fileName], IO.int[nbins], IO.int[nbterms], IO.int[nbouts]];
FOR i:
INT
DECREASING
IN [0..nbins)
DO
inputs ← CONS [Rope.Cat["Input", IO.PutR[IO.int[i]]], inputs];
ENDLOOP;
FOR i:
INT
DECREASING
IN [0..nbouts)
DO
outputs ← CONS [Rope.Cat["Output", IO.PutR[IO.int[i]]], outputs];
ENDLOOP;
} ELSE {
IF nbins#RopeList.Length[inputs] THEN {TerminalIO.WriteF["*** Number of inputs of the TruthTable (%g) does NOT agree with the inputs given.\n", IO.int[nbins]]; ERROR};
IF nbouts#RopeList.Length[outputs] THEN {TerminalIO.WriteF["*** Number of outputs of the TruthTable (%g) does NOT agree with the outputs given.\n", IO.int[nbouts]]; ERROR};
};
exprs ← NEW[ExprsSeqRec[nbouts]];
FOR i: NAT IN [0 .. nbouts) DO exprs[i] ← false ENDLOOP;
terms ← NEW[ExprsSeqRec[nbterms]];
We now read for good the PLA
inStm ← FS.StreamOpen[fileName: fileName];
TerminalIO.WriteF["\n"];
FOR term:
NAT
IN [0 .. nbterms)
DO
-- for each line
termName: ROPE ← Rope.Cat["Term", IO.PutR[IO.int[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:
NAT
IN [0..nbins)
DO
IF rope.Fetch[0]='1 THEN operands ← CONS [CoreBoole.Var[Nth[inputs, nbins-input-1]], operands];
IF rope.Fetch[0]='0 THEN operands ← CONS [CoreBoole.Not[CoreBoole.Var[Nth[inputs, nbins-input-1]]], operands];
rope ← Skip[rope];
ENDLOOP;
IF rope.Fetch[0]#'| THEN ERROR;
rope ← Skip[rope];
terms[term] ← CoreBoole.AndList[operands];
TerminalIO.WriteF["term: %g\n", RopeFromExpression[table, expr]];
FOR outs:
NAT
IN [0 .. nbouts)
DO
IF rope.Fetch[0]='1 THEN exprs[outs] ← CoreBoole.Or[terms[term], exprs[outs]];
ENDLOOP;
TerminalIO.WriteF["."];
ENDLOOP;
TerminalIO.WriteF["\n"];
END;