PLAWright:
CEDAR
PROGRAM
IMPORTS Commander, Convert, FS, IO, IOClasses, Menus, PLAOps, Process, Rope, TypeScript, ViewerIO =
BEGIN
OPEN PO: PLAOps;
CardSeq: TYPE = REF CardSeqRec;
CardSeqRec: TYPE = RECORD[SEQUENCE size: CARDINAL OF CARDINAL];
RopeSeq: TYPE = REF RopeSeqRec;
RopeSeqRec: TYPE = RECORD[SEQUENCE size: CARDINAL OF IO.ROPE];
BoolSeq: TYPE = REF BoolSeqRec;
BoolSeqRec: TYPE = RECORD[SEQUENCE size: CARDINAL OF BOOL];
Format: TYPE = RECORD[in, out: CardSeq, outFirst, outLast: CARDINAL, mode: Mode];
Mode: TYPE = {field, single, composite};
log, logV, logF, trace: IO.STREAM;
PLAGrinder: Commander.CommandProc = {
DO
ENABLE {
UNWIND => {log.Close[]; trace.Close[]};
FS.Error => IF error.group = user THEN {
cmd.err.PutRope[error.explanation]; EXIT }};
tt: PO.TermList;
format: Format;
comSum: BOOL;
time: CARDINAL;
source, key, root: IO.ROPE ← NIL;
[source, key, format.mode, format.outFirst, format.outLast, time, comSum]
← GetCommandLineParams[cmd];
IF source=
NIL
OR source.Length[]=0
THEN
{cmd.err.PutRope["\n >>> No source file** \n"]; RETURN};
IF source.Index[s2: "."]=source.Length[] THEN source ← source.Cat[".tt"];
source ← FS.ExpandName[source].fullFName; -- adds current working directory
root ← source.Substr[len: source.Index[s2: "."]];
trace ← BuildControlPanel[];
logF ← FS.StreamOpen[fileName: root.Cat[".log"], accessOptions: $append, keep: 2];
logV ← ViewerIO.CreateViewerStreams[name: root.Cat[".log"]].out;
log ← IOClasses.CreateDribbleOutputStream[ output1: logV, output2: logF];
TypeScript.ChangeLooks[ViewerIO.GetViewerFromStream[logV], 'f];
TypeScript.ChangeLooks[ViewerIO.GetViewerFromStream[logV], 's];
[tt, format.in, format.out] ← ReadTermList[source, key, trace];
IF format.outFirst=177777B
THEN {
format.outFirst ← 0;
format.outLast ←
IF format.mode = field
THEN (format.out.size-2) ELSE (tt.outBits-1) };
TRUSTED {Process.Detach[FORK DoPLAReduce[tt, comSum, time, format, root]]};
EXIT ENDLOOP};
BuildControlPanel:
PROC
RETURNS [out:
IO.
STREAM] = {
viewer: ViewerClasses.Viewer;
out ← ViewerIO.CreateViewerStreams["PLAWright Trace"].out;
viewer ← ViewerIO.GetViewerFromStream[out];
TypeScript.ChangeLooks[viewer, 'f];
TypeScript.ChangeLooks[viewer, 's];
Menus.AppendMenuEntry[
menu: viewer.menu,
entry: Menus.CreateEntry[name: "Trace", clientData: out, proc: TraceProc]];
Menus.AppendMenuEntry[
menu: viewer.menu,
entry: Menus.CreateEntry[name: "FinishCS", clientData: out, proc: FinishCSProc]];
Menus.AppendMenuEntry[
menu: viewer.menu,
entry: Menus.CreateEntry[name: "FinishMin", clientData: out, proc: FinishMinProc]];
Menus.AppendMenuEntry[
menu: viewer.menu,
entry: Menus.CreateEntry[name: "Abort", clientData: out, proc: AbortProc]] };
FinishCSProc: Menus.ClickProc = {
out: IO.STREAM ← NARROW[clientData];
PO.FinishCS ← TRUE;
out.PutRope["\nTruncate complete sum"]};
FinishMinProc: Menus.ClickProc = {
out: IO.STREAM ← NARROW[clientData];
PO.FinishMin ← TRUE;
out.PutRope["\nTruncate minimum sum search"]};
AbortProc: Menus.ClickProc = {
out: IO.STREAM ← NARROW[clientData];
PO.FinishCS←PO.FinishMin←PO.Abort ← TRUE;
out.PutRope["\nAbort"]};
TraceProc: Menus.ClickProc = {
out: IO.STREAM ← NARROW[clientData];
PO.Trace ← NOT PO.Trace;
out.PutF["\nTrace %g", IO.rope[(IF PO.Trace THEN "ON" ELSE "OFF")]]};
GetCommandLineParams:
PROC[cmd: Commander.Handle]
RETURNS
[source, key: IO.ROPE, mode: Mode, begin, end, time: CARDINAL, comSum: BOOL] = {
cls: IO.STREAM ← IO.RIS[cmd.commandLine];
token: IO.ROPE ← IO.GetTokenRope[cls].token;
source ← NIL;
time ← 177777B; -- delay in minutes ~ 45 days
key ← NIL;
mode ← field;
begin ← end ← 177777B;
comSum ← TRUE;
DO
ENABLE IO.EndOfStream => EXIT;
Next: PROC = {token←IO.GetTokenRope[cls].token};
SELECT token.Fetch[0]
FROM
'/, IN ['a..'z], IN ['A..'Z ] => {source ← source.Cat[token]; Next[]; LOOP};
'- => {
Next[];
SELECT token.Fetch[0]
FROM
'f, 'F => mode ← field;
's, 'S => mode ← single;
'c, 'C => mode ← composite;
'k, 'K => {key←IO.GetRopeLiteral[cls]; Next[]; LOOP};
'q, 'Q => {comSum←FALSE; Next[]; LOOP};
'p, 'P => {comSum←FALSE; Next[]; LOOP};
't, 'T => {time𡤌onvert.CardFromRope[token.Substr[1]]; Next[]; LOOP};
ENDCASE =>
{cmd.err.PutF["\n**Unknown switch: %g\n", IO.rope[token]]; RETURN};
IF token.Length[] > 1
THEN {
token ← token.Substr[1];
begin ← end ← Convert.CardFromRope[token]; Next[]; LOOP};
Next[];
SELECT token.Fetch[0]
FROM
'[ => {begin ← 0};
'( => {begin ← 1};
ENDCASE => LOOP;
Next[];
begin ← Convert.CardFromRope[token.Substr[len: token.Index[s2:".."]]] + begin;
token ← token.Substr[token.Index[s2:".."]+2];
end ← Convert.CardFromRope[token];
Next[];
SELECT token.Fetch[0]
FROM
'] => {};
') => {end ← end-1};
ENDCASE =>
{cmd.err.PutF["\n**I don't understand '%g'. I was expecting an end of range\n", IO.rope[token]]; RETURN};
Next[]; LOOP};
ENDCASE =>
{cmd.err.PutF["\n**I don't understand '%g'. I was expecting a switch or filename\n", IO.rope[token]]; RETURN};
ENDLOOP;
cls.Close[]};
TOD:
PROC
RETURNS[
IO.Value] = {
time: IO.ROPE ← IO.PutFR["%g", IO.time[]];
time ← time.Substr[time.Index[s2:"198"]+5];
time ← time.Substr[len: time.Index[s2:" "]];
IF time.Length[] = 7 THEN time ← Rope.Cat[" ", time];
RETURN[IO.rope[time]]};
DoPLAReduce:
PROC[
sourcePLA: PO.TermList,
comSum: BOOL,
time: CARDINAL,
format: Format,
root: IO.ROPE] = {
nofPLAs:
CARDINAL
← IF format.mode=composite THEN 1 ELSE format.outLast-format.outFirst+1;
index: CARDINAL ← 0;
dfSeqTot: CARDINAL ← 0;
csSeqTot: CARDINAL ← 0;
initEssentialTot: CARDINAL ← 0;
initDeleteTot: CARDINAL ← 0;
coverTot: CARDINAL ← 0;
finishCSTot: CARDINAL ← 0;
finishMinTot: CARDINAL ← 0;
outsTot: CARDINAL ← 0;
dfSeq: PO.TermListSeq ← NEW[PO.TermListSeqRec[nofPLAs]];
csSeq: PO.TermListSeq ← NEW[PO.TermListSeqRec[nofPLAs]];
initEssential: CardSeq ← NEW[CardSeqRec[nofPLAs]];
initDelete: CardSeq ← NEW[CardSeqRec[nofPLAs]];
cover: CardSeq ← NEW[CardSeqRec[nofPLAs]];
filename: RopeSeq ← NEW[RopeSeqRec[nofPLAs]];
label: RopeSeq ← NEW[RopeSeqRec[nofPLAs]];
file: IO.STREAM ← IO.noWhereStream;
Process.SetPriority[Process.priorityBackground];
PO.Trace ← PO.FinishCS ← PO.FinishMin ← PO.Abort ← FALSE;
log.PutF["\n\n%g - %g", IO.rope[root.Cat[".log"]], IO.time[]];
PO.SortTermList[sourcePLA, TRUE];
log.PutF["\n\nSource PLA: %g - sorted %g", IO.rope[root.Cat[".tt"]], TOD[] ];
log.PutF["\n\nSource PLA: %g", IO.rope[root.Cat[".tt"]]];
log.PutF[" Ins:%3g Outs:%3g Fields:%3g Terms:%3g Result PLAs:%3g\nResult PLA:",
IO.card[ sourcePLA.inBits],
IO.card[ sourcePLA.outBits],
IO.card[ format.out.size-1],
IO.card[ sourcePLA.length],
IO.card[ nofPLAs]];
FOR index
IN [0..nofPLAs)
DO
first, last, biasIdx: CARDINAL;
biasIdx ← format.outFirst+index;
SELECT format.mode
FROM
field => {
first ← format.out[biasIdx];
last ← format.out[biasIdx+1]-1};
single => {first ← biasIdx; last ← first};
composite => {first ← biasIdx; last ← format.outLast}; ENDCASE;
dfSeq[index] ← PO.CopyTermList[sourcePLA, first, last];
csSeq[index] ← PO.CopyTermList[sourcePLA, first, last];
SELECT format.mode
FROM
field => filename[index] ←IO.PutFR["%g-F%02g.tt", IO.rope[root], IO.card[biasIdx]];
single => filename[index] ←IO.PutFR["%g-S%02g.tt", IO.rope[root], IO.card[biasIdx]];
composite => filename[index] ←IO.PutFR["%g-C%02g-%02g.tt", IO.rope[root], IO.card[first], IO.card[last]];
ENDCASE => ERROR;
IF format.mode = field THEN label[index] ← IO.PutFR["Field:%3g ", IO.card[biasIdx]];
label[index] ← label[index].Cat[ IO.PutFR["[%2g..%2g]", IO.card[first], IO.card[last]] ];
log.PutF["\n%3g %g %g Terms: %3g", IO.card[index], IO.rope[filename[index]], IO.rope[label[index]], IO.card[dfSeq[index].length] ];
ENDLOOP;
log.PutRope["\n"]; log.Flush[];
FOR index
IN [0..nofPLAs)
DO
ENABLE UNWIND => GOTO AbortExit;
MSG: PROC[msg: IO.ROPE] = {file.PutRope[msg]; logV.PutRope[msg]};
finishCS, finishMin:BOOL ← FALSE;
file ← FS.StreamOpen[filename[index], $create];
logV.PutRope["\n\n"];
IF
PO.Abort
THEN {logV.PutRope["\n<<<<ABORT>>>>\n"]; log.Flush[];
EXIT};
MSG[IO.PutFR["%g - %g", IO.rope[filename[index]], IO.time[]]]; file.Flush[]; log.Flush[];
IF dfSeq[index].length=0 THEN {MSG["\n(Empty)"]; file.Close[]; log.Flush[]; LOOP};
MSG[
IO.PutFR["\nDEF PLA:%3g %g Terms: %3g %g",
IO.card[index], IO.rope[label[index]], IO.card[dfSeq[index].length], TOD[]]];
PO.ListTermList[list: dfSeq[index], log: file]; file.Flush[]; log.Flush[];
IF PO.Abort THEN GOTO AbortExit;
finishCS ←
PO.ConvertTermListToCompleteSum
[list: csSeq[index], addMerges: comSum, addConsensus: comSum, log: trace];
MSG[
IO.PutFR["\nSUM PLA:%3g %g Terms: %3g %g",
IO.card[index], IO.rope[label[index]], IO.card[csSeq[index].length], TOD[]]];
IF finishCS
THEN {
MSG[" ~finished"];
PO.ListTermList[list: csSeq[index], log: file]; file.Flush[]; log.Flush[]};
IF PO.Abort THEN GOTO AbortExit;
[initEssential[index], initDelete[index], cover[index], finishMin]
← PO.FindAMinimalCover[list: csSeq[index], time: time, log: trace];
MSG[
IO.PutFR["\nMIN PLA:%3g %g Terms: %3g %g",
IO.card[index], IO.rope[label[index]], IO.card[cover[index]], TOD[]]];
IF finishMin THEN MSG[" ~finished"];
PO.ListTermList[list: csSeq[index], omitDeletes: TRUE, log: file];
outsTot ← outsTot + dfSeq[index].outBits;
dfSeqTot ← dfSeqTot + dfSeq[index].length;
csSeqTot ← csSeqTot + csSeq[index].length;
initEssentialTot ← initEssentialTot+ initEssential[index];
initDeleteTot ← initDeleteTot + initDelete[index];
coverTot ← coverTot + cover[index];
finishCSTot ← finishCSTot + (IF finishCS THEN 1 ELSE 0);
finishMinTot ← finishMinTot + (IF finishMin THEN 1 ELSE 0);
log.PutF["\n%3g %g", IO.card[index], IO.rope[label[index]]];
log.PutF[" Def:%3g %g:%3g",
IO.card[dfSeq [index].length],
IO.rope[(IF comSum THEN "CS" ELSE "Sum")],
IO.card[csSeq [index].length] ];
log.PutF[" Ess:%3g Del:%3g Cov:%3g",
IO.card[initEssential [index]],
IO.card[initDelete [index]],
IO.card[cover [index]] ];
log.PutF[" %g", TOD[]];
IF finishCS
OR finishMin
THEN {
IF finishCS THEN log.PutRope[" CS"];
IF finishMin THEN log.PutRope[" Min"];
log.PutRope[" ~finished"]};
log.Flush[];
file.Close[];
REPEAT AbortExit => {
log.PutRope["\n<<<<ABORT>>>>\n"]; log.Flush[];
file.PutRope["\n<<<<ABORT>>>>\n"]; file.Close } ENDLOOP;
log.PutF["\n\nSummary:"];
log.PutF["\n Inputs Bits:%4g", IO.card[sourcePLA.inBits]];
log.PutF["\n Total Outputs Bits:%4g", IO.card[outsTot]];
log.PutF["\n SourcePLA Terms:%4g", IO.card[sourcePLA.length]];
log.PutF["\n Definition Terms:%4g", IO.card[dfSeqTot]];
log.PutF["\n Complete Sum Terms:%4g", IO.card[csSeqTot]];
log.PutF["\n Essential Terms:%4g", IO.card[initEssentialTot]];
log.PutF["\n Init Deletes Terms:%4g", IO.card[initDeleteTot]];
log.PutF["\n Cover Terms:%4g", IO.card[coverTot]];
log.PutF["\n CS Unfinished Srchs:%4g", IO.card[finishCSTot]];
log.PutF["\n Min Unfinished Srchs:%4g", IO.card[finishMinTot]];
PO.Trace ← PO.FinishCS ← PO.FinishMin ← PO.Abort ← FALSE;
log.Close;
trace.Close};
BuildTermList:
PROC[rope:
IO.
ROPE, list:
PO.TermList ←
NIL]
RETURNS[new:
PO.TermList] = {
IF (new←list) =
NIL
THEN {
inBitSize, outBitSize: CARDINAL;
[inBitSize, outBitSize] ← CountBits[rope];
new ← NEW[PO.TermListRec ← [inBits: inBitSize, outBits: outBitSize] ] };
PO.AppendTerm[PO.RopeToTerm[rope, new], new] };
ReadTermList:
PROC [fileName, key:
IO.
ROPE, log:
IO.
STREAM]
RETURNS[termList: PO.TermList, in, out: CardSeq] = {
inStm: IO.STREAM ← FS.StreamOpen[fileName: fileName];
rope: IO.ROPE ← NIL;
OK:
PROC
RETURNS[
BOOL] = {
IF rope=NIL OR rope.Length=0 THEN RETURN[FALSE];
RETURN[SELECT rope.Fetch[0] FROM '0, '1, '-, 'x, 'X => TRUE, ENDCASE => FALSE] };
IF key#
NIL
THEN
IF key.Length>0
THEN
WHILE
NOT inStm.EndOf[]
DO
rope ← IO.GetLineRope[inStm];
IF rope.Find[s2: key] >= 0 THEN EXIT ENDLOOP;
WHILE
NOT (inStm.EndOf[]
OR
OK[])
DO
rope ← IO.GetLineRope[inStm] ENDLOOP;
[in, out] ← GetFormats[rope];
termList ← BuildTermList[rope, termList];
WHILE
NOT inStm.EndOf[]
DO
rope←IO.GetLineRope[inStm];
IF ~OK[] THEN EXIT;
termList ← BuildTermList[rope, termList];
IF (termList.length
MOD 100)=0
THEN log.PutRope["!"]
ELSE
IF (termList.length MOD 10)=0 THEN log.PutRope["."];
ENDLOOP;
log.PutF["\n In bit size: %g Out bit size: %g Nof Terms: %g\n",
IO.card[termList.inBits], IO.card[termList.outBits], IO.card[termList.length]] };
CountBits:
PROC [rope:
IO.
ROPE]
RETURNS[inBitSize, outBitSize:
CARDINAL] = {
i: INT ← 0;
inBitSize ← 0;
FOR i ← i, i+1
WHILE i < rope.Length[]
DO
SELECT rope.Fetch[i]
FROM
'0, '1, '-, 'x, '. => { };
'| => EXIT;
ENDCASE => LOOP;
inBitSize ← inBitSize + 1 ENDLOOP;
outBitSize ← 0;
FOR i ← i, i+1
WHILE i < rope.Length[]
DO
SELECT rope.Fetch[i]
FROM
'0, '1, '-, 'x, '. => { };
ENDCASE => LOOP;
outBitSize ← outBitSize + 1 ENDLOOP};
GetFormats:
PROC [rope:
IO.
ROPE]
RETURNS[in, out: CardSeq] = {
i: INT ← 0;
spaceBefore: BOOL ← TRUE;
spaceIndex, bitIndex, startIndex: INT ← 0;
temp: CardSeq ← NEW[CardSeqRec[rope.Length[]]];
FOR i ← startIndex, i+1
WHILE i < rope.Length[]
DO
SELECT rope.Fetch[i]
FROM
'0, '1, '-, 'x, 'X => {
IF spaceBefore THEN {temp[spaceIndex]𡤋itIndex; spaceIndex←spaceIndex+1};
bitIndex ← bitIndex+1;
spaceBefore ← FALSE };
IO.SP, IO.TAB => spaceBefore ← TRUE;
'| => EXIT;
ENDCASE ENDLOOP;
temp[spaceIndex]𡤋itIndex;
in ← NEW[CardSeqRec[spaceIndex]];
FOR i ← 0, i+1 WHILE i < spaceIndex DO in[i] ← temp[i+1]-temp[i] ENDLOOP;
spaceIndex ← bitIndex ← 0; spaceBefore ← TRUE; startIndex ← i;
FOR i ← startIndex, i+1
WHILE i < rope.Length[]
DO
SELECT rope.Fetch[i]
FROM
'0, '1, '-, 'x, 'X => {
IF spaceBefore THEN {temp[spaceIndex]𡤋itIndex; spaceIndex←spaceIndex+1};
bitIndex ← bitIndex+1;
spaceBefore ← FALSE };
IO.SP, IO.TAB => spaceBefore ← TRUE;
ENDCASE ENDLOOP;
temp[spaceIndex]𡤋itIndex;
out ← NEW[CardSeqRec[spaceIndex]];
FOR i ← 0, i+1 WHILE i < spaceIndex DO out[i] ← temp[i+1]-temp[i] ENDLOOP };
GetFormats: PROC [rope: IO.ROPE] RETURNS[in, out: CardSeq] = {
i: INT ← 0;
spaceBefore: BOOL ← TRUE;
spaceIndex, bitIndex, startIndex: INT ← 0;
FOR i ← startIndex, i+1 WHILE i < rope.Length[] DO
SELECT rope.Fetch[i] FROM
'0, '1, '-, 'x, '. => {
IF spaceBefore THEN spaceIndex←spaceIndex+1;
spaceBefore ← FALSE };
IO.SP, IO.TAB => spaceBefore ← TRUE;
'| => EXIT;
ENDCASE ENDLOOP;
in ← NEW[CardSeqRec[spaceIndex+1]];
spaceIndex ← bitIndex ← 0; spaceBefore ← TRUE;
FOR i ← startIndex, i+1 WHILE i < rope.Length[] DO
SELECT rope.Fetch[i] FROM
'0, '1, '-, 'x, '. => {
IF spaceBefore THEN {in[spaceIndex]𡤋itIndex; spaceIndex←spaceIndex+1};
bitIndex ← bitIndex+1;
spaceBefore ← FALSE };
IO.SP, IO.TAB => spaceBefore ← TRUE;
'| => EXIT;
ENDCASE ENDLOOP;
in[spaceIndex]𡤋itIndex;
spaceIndex ← bitIndex ← 0; spaceBefore ← TRUE; startIndex ← i;
FOR i ← startIndex, i+1 WHILE i < rope.Length[] DO
SELECT rope.Fetch[i] FROM
'0, '1, '-, 'x, '. => {
IF spaceBefore THEN spaceIndex←spaceIndex+1;
spaceBefore ← FALSE };
IO.SP, IO.TAB => spaceBefore ← TRUE;
ENDCASE ENDLOOP;
out ← NEW[CardSeqRec[spaceIndex+1]];
spaceIndex ← bitIndex ← 0; spaceBefore ← TRUE;
FOR i ← startIndex, i+1 WHILE i < rope.Length[] DO
SELECT rope.Fetch[i] FROM
'0, '1, '-, 'x, '. => {
IF spaceBefore THEN {out[spaceIndex]𡤋itIndex; spaceIndex←spaceIndex+1};
bitIndex ← bitIndex+1;
spaceBefore ← FALSE };
IO.SP, IO.TAB => spaceBefore ← TRUE;
ENDCASE ENDLOOP;
out[spaceIndex]𡤋itIndex };
Commander.Register[key:"PLAWright", proc: PLAGrinder, doc: "PLA compression program"];
PLAWright foo.tt reduces the PLA represented by the truth table in foo.tt producing foo.log and one or more files of the form foo-xxx.tt.
If an input file contains more than one truth table, then truth table selection can be made using the key switch (-k"something unique found in line just before the desired truth table"). Input scanning will begin on the first line after the key which contains 0,1 or - as the first character. Scanning will end on the first line which fails to satisfy the above condition.
Subsets of the outputs are specified using three mutually exclusive switches and numerical modifiers. The default switch -f treats the outputs as being clumped into fields which are defined in the input .tt file by inserting spaces.
-f => reduce each output field (default) producing foo-F00.tt, foo-F01.tt, etc.
-f[3..4] => reduce each output field in[3..4] producing foo-F03.tt and foo-F04.tt.
-f6 => reduce the seventh output field producing foo-F06.tt
-s => reduce each single output producing foo-S00.tt, foo-S01.tt, etc.
-s[3..4] => reduce each single output in[3..4] producing foo-S03.tt and foo-S04.tt.
-s6 => reduce the seventh output producing foo-S06.tt
-c => reduce composite outputs producing foo-C00-xx.tt. (xx+1 outs total)
-c[3..4] => reduce composite outputs in[3..4] producing foo-C03-04.tt.
-c6 => reduce output producing foo-C06-06.tt (same as -s6).
-k"xxx" => look for key string xxx in input file before scanning
The last switch (-p), is used to request construction of only a partial sum from the definition prior to performing the minimization. It's useful for pla's that take a long time (forever) to generate complete sums. Use of this switch of course removes all guarantee's about the minimal size of the reduced truth table.
END.