BoolExImpl.mesa
Copyright Ó 1986, 1987 by Xerox Corporation. All rights reserved.
Barth, July 17, 1987 5:46:59 pm PDT
Bertrand Serlet April 2, 1987 9:39:46 pm PST
Don Curry July 21, 1987 8:59:20 am PDT
Last Edited by: Don Curry December 12, 1987 11:09:33 am PST
DIRECTORY Basics, BoolEx, FileNames, FS, IO, Rope, RopeList, SParse, SymTab;
BoolExImpl: CEDAR PROGRAM
IMPORTS Basics, FileNames, FS, IO, Rope, RopeList, SParse, SymTab
EXPORTS BoolEx
= BEGIN
Expression: TYPE = BoolEx.Expression;
OpIndex:  TYPE = BoolEx.OpIndex;
LevCnt:  TYPE = RECORD[lev, cnt: INT];
traceLog:  IO.STREAMIO.noWhereStream;
NmOp: PUBLIC PROC[nm: IO.ROPE] RETURNS[op: OpIndex] = {
FOR op IN OpIndex DO IF nm.Equal[OpNm[op]] THEN RETURN[op] ENDLOOP;
IF nm.Equal["*"]  THEN RETURN[and];
IF nm.Equal["+"] THEN RETURN[or];
IF nm.Equal["~"] THEN RETURN[not];
RETURN[func]};
OpNm: PUBLIC PROC[op: OpIndex] RETURNS[nm: IO.ROPE] = {RETURN[SELECT op FROM
mach  => "MACH",
out  => "OUT",
var  => "VAR",
nand  => "NAND",
nor  => "NOR",
and  => "*",
or   => "+",
not  => "~",
ENDCASE => "function"]};
ExpressionStats: PUBLIC PROC [expr: Expression] RETURNS [exprStatRope: IO.ROPE] = {
ScanExpr: PROC[e: REF] = {
WITH e SELECT FROM
int: REF INT => RETURN;
rope: IO.ROPE => IF SymTab.Insert[varTab, rope, rope] THEN inputs ← inputs+1;
elist: LIST OF REF => {
op: OpIndex ← NmOp[NARROW[elist.first]];
SELECT op FROM
mach  => {
opCnts[op][1] ← opCnts[op][1]+1;
machineName ← NARROW[elist.rest.first];
FOR el: LIST OF REF ← elist.rest.rest, el.rest WHILE el#NIL DO
dList: LIST OF REF ← NARROW[el.first];
name: IO.ROPE  ← NARROW[dList.rest.first];
op ← NmOp[NARROW[dList.first]];
opCnts[op][1] ← opCnts[op][1]+1;
SELECT op FROM
out =>
IF ~SymTab.Insert[outTab, name, Copy[dList.rest.rest.first]] THEN ERROR;
var =>
IF ~SymTab.Insert[varTab, name, Copy[dList.rest.rest.first]] THEN ERROR;
ENDCASE => ERROR;
ENDLOOP;
FOR el: LIST OF REF ← elist.rest.rest, el.rest WHILE el#NIL DO
dList: LIST OF REF ← NARROW[el.first];
ScanExpr[dList.rest.rest.first] ENDLOOP};
out  => ERROR; -- should have been caught above
var  => ERROR; -- should have been caught above
ENDCASE => {
cnt: INT ← 0;
FOR el: LIST OF REF ← elist.rest, el.rest WHILE el#NIL DO cnt ← cnt+1 ENDLOOP;
cnt ← MIN[cnt, maxCount];
opCnts[op][cnt] ← opCnts[op][cnt]+1;
FOR el: LIST OF REF ← elist.rest, el.rest WHILE el#NIL
DO ScanExpr[el.first] ENDLOOP}};
ENDCASE => ERROR};
maxCount: NAT = 20;
varTab: SymTab.Ref ← SymTab.Create[];
outTab: SymTab.Ref ← SymTab.Create[];
stream:   IO.STREAMIO.ROS[];
opCnts:   ARRAY OpIndex OF ARRAY [1..maxCount] OF INTALL[ALL[0]];
machineName: IO.ROPE ← "???";
inputs:   INT ← 0;
gates:    INT ← 0;
ScanExpr[expr];
stream.PutF["%g\n IN:%3g ", IO.rope[machineName], IO.int[inputs]];
FOR ii: INT IN [1..maxCount] DO stream.PutF["%3g", IO.int[ii]] ENDLOOP;
stream.PutRope["\n"];
FOR op: OpIndex IN OpIndex DO
cnt: INT ← 0;
IF op=mach THEN LOOP;
FOR ii: INT IN [1..maxCount] DO cnt ← cnt+opCnts[op][ii] ENDLOOP;
stream.PutF["%7g:%3g ", IO.rope[OpNm[op]], IO.int[cnt]];
IF op#out AND op#var THEN gates ← gates + cnt;
FOR ii: INT IN [1..maxCount] DO IF opCnts[op][ii]=0
THEN stream.PutRope[" "]
ELSE stream.PutF["%3g", IO.int[opCnts[op][ii]]] ENDLOOP;
stream.PutRope["\n"];
ENDLOOP;
stream.PutF[" GATES:%3g\n", IO.int[gates]];
exprStatRope ← IO.RopeFromROS[stream]};
DefaultEachInputProc:  BoolEx.EachInputProc = {};
DefaultEachOutputProc: BoolEx.EachOutputProc = {};
ScanExpression: PUBLIC PROC[
expr:   BoolEx.Expression,
eachInput: BoolEx.EachInputProc ← NIL,
eachOutput: BoolEx.EachOutputProc ← NIL]
RETURNS[machName: IO.ROPENIL] = {
outTab: SymTab.Ref ← SymTab.Create[];
inTab: SymTab.Ref ← SymTab.Create[];
RegisterDefs: PROC[e: REF] = {
WITH e SELECT FROM
int: REF INT  => RETURN;
rope: IO.ROPE  => RETURN;
elist: LIST OF REF =>
SELECT NmOp[NARROW[elist.first]] FROM
mach  => {
machName ← NARROW[elist.rest.first];
FOR elist ← elist.rest.rest, elist.rest WHILE elist#NIL
DO RegisterDefs[elist.first] ENDLOOP};
out  => {
name: IO.ROPENARROW[elist.rest.first];
IF SymTab.Insert[outTab,name, Copy[elist.rest.rest.first]]
THEN eachOutput[name, elist.rest.rest.first]};
var  => {
name: IO.ROPENARROW[elist.rest.first];
IF NOT SymTab.Insert[inTab,name, Copy[elist.rest.rest.first]] THEN ERROR};
ENDCASE => RETURN;
ENDCASE => ERROR};
RegisterIns: PROC[e: REF] = {
WITH e SELECT FROM
int: REF INT   => RETURN;
rope: IO.ROPE   =>
IF SymTab.Insert[inTab, rope, rope] THEN eachInput[rope];
elist: LIST OF REF =>
SELECT NmOp[NARROW[elist.first]] FROM
mach  => {
FOR elist ← elist.rest.rest, elist.rest WHILE elist#NIL
DO RegisterIns[elist.first] ENDLOOP};
out, var => RegisterIns[elist.rest.rest.first];
ENDCASE => FOR elist ← elist.rest, elist.rest WHILE elist#NIL
DO RegisterIns[elist.first] ENDLOOP;
ENDCASE => ERROR};
IF eachInput  = NIL THEN eachInput  ← DefaultEachInputProc;
IF eachOutput = NIL THEN eachOutput ← DefaultEachOutputProc;
RegisterDefs[expr];
RegisterIns[expr]};
For leaf inputs in inTab, val=key
GetExpressionTables: PUBLIC PROC[mach: BoolEx.Expression]
RETURNS[machName: IO.ROPE, inTab, outTab: SymTab.Ref] = {
RegisterDefs: PROC[e: REF] = {
WITH e SELECT FROM
int: REF INT => RETURN;
rope: IO.ROPE => RETURN;
elist: LIST OF REF =>
SELECT NmOp[NARROW[elist.first]] FROM
mach  => {
machName ← NARROW[elist.rest.first];
FOR elist ← elist.rest.rest, elist.rest WHILE elist#NIL
DO RegisterDefs[elist.first] ENDLOOP};
out  => {
name: IO.ROPENARROW[elist.rest.first];
IF ~SymTab.Insert[outTab, name, Copy[elist.rest.rest.first]] THEN ERROR};
var  => {
name: IO.ROPENARROW[elist.rest.first];
IF ~SymTab.Insert[inTab, name, Copy[elist.rest.rest.first]] THEN ERROR};
ENDCASE => RETURN;
ENDCASE => ERROR};
RegisterIns: PROC[e: REF] = {
WITH e SELECT FROM
int: REF INT => RETURN;
rope: IO.ROPE => []←SymTab.Insert[inTab, rope, rope]; -- succeeds if new leaf
elist: LIST OF REF =>
SELECT NmOp[NARROW[elist.first]] FROM
mach  => {
FOR elist ← elist.rest.rest, elist.rest WHILE elist#NIL
DO RegisterIns[elist.first] ENDLOOP};
out, var => RegisterIns[elist.rest.rest.first];
ENDCASE => FOR elist ← elist.rest, elist.rest WHILE elist#NIL
DO RegisterIns[elist.first] ENDLOOP;
ENDCASE => ERROR};
inTab  ← SymTab.Create[];
outTab ← SymTab.Create[];
RegisterDefs[mach];
RegisterIns[mach]};
ReadExprFile: PUBLIC PROC[name: IO.ROPE] RETURNS[expr: Expression] = {
file: IO.ROPE ← name;
rope: IO.ROPE;
in:  IO.STREAM;
IF file.Find["."]=-1 THEN file ← file.Cat[".expr"];
in  ← FS.StreamOpen[fileName: file, wDir: wDir ! FS.Error => {in ← NIL; CONTINUE}];
IF in=NIL THEN RETURN[NIL];
rope ← IO.GetRope[in];
expr ← SParse.ToTree[rope];
in.Close[]};
WriteExprFile: PUBLIC PROC[expr: Expression, indentedLevs: INT ← 2] = {
out: IO.STREAM;
file: IO.ROPE  ← NARROW[NARROW[expr, LIST OF REF].rest.first];
rope: IO.ROPE  ← SParse.ToRope[expr, indentedLevs];
IF file.Find["."]=-1 THEN file ← file.Cat[".expr"];
out     ← FS.StreamOpen[fileName: file, accessOptions: $create, wDir: wDir];
out.PutRope[rope];
out.Close[]};
wDir: IO.ROPE ← FileNames.CurrentWorkingDirectory[]; -- when module runs
Compare: PUBLIC PROC[i0, i1: REF] RETURNS[comp: Basics.Comparison] = {
IF i0=NIL AND i1=NIL THEN RETURN[equal];
IF i0=NIL THEN RETURN[less];
IF i1=NIL THEN RETURN[greater];
WITH i0 SELECT FROM
int0: REF INT => WITH i1 SELECT FROM
int1: REF INT   => RETURN[Basics.CompareInt[int0^, int1^]];
ENDCASE      => RETURN[less];
rope0: IO.ROPE    => WITH i1 SELECT FROM
int1: REF INT    => RETURN[greater];
rope1: IO.ROPE    => RETURN[Rope.Compare[rope0, rope1, FALSE]];
ENDCASE      => RETURN[less];
elist0: LIST OF REF   => WITH i1 SELECT FROM
int1: REF INT    => RETURN[greater];
rope1: IO.ROPE    => RETURN[greater];
elist1: LIST OF REF   => DO
IF (comp ← Compare[elist0.first, elist1.first])#equal THEN RETURN[comp];
elist0 ← elist0.rest;
elist1 ← elist1.rest;
IF elist0=NIL AND elist1=NIL THEN RETURN[equal];
IF elist0=NIL THEN RETURN[less];
IF elist1=NIL THEN RETURN[greater]; ENDLOOP;
ENDCASE      => ERROR
ENDCASE => ERROR};
Sort: PUBLIC PROC[expr: Expression] = {
SortList: PROC[init: LIST OF REF] = {
TwoRefs: TYPE = RECORD[r0,r1: REF];
done: BOOL;
FOR lst: LIST OF REF ← init, lst.rest WHILE lst#NIL DO Sort[lst.first] ENDLOOP;
DO
done ← TRUE;
FOR lst: LIST OF REF ← init, lst.rest WHILE lst.rest#NIL DO
IF Compare[lst.first, lst.rest.first]#greater THEN LOOP;
done ← FALSE;
[lst.first, lst.rest.first] ← TwoRefs[lst.rest.first, lst.first] ENDLOOP;
IF done THEN EXIT ENDLOOP};
IF expr=NIL THEN RETURN;
WITH expr SELECT FROM
int: REF INT    => RETURN;
rope: IO.ROPE    => RETURN;
list: LIST OF REF   => {
op: BoolEx.OpIndex ← NmOp[NARROW[list.first]];
SELECT op FROM
mach, var, out => {SortList[list.rest.rest]; RETURN};
ENDCASE   => {SortList[list.rest];  RETURN}};
ENDCASE => ERROR};
Copy: PUBLIC PROC[expr: Expression] RETURNS[new: Expression] = {
IF expr=NIL THEN RETURN[NIL];
WITH expr SELECT FROM
int: REF INT     => RETURN[NEW[INT ← int^]];
rope: IO.ROPE    => RETURN[rope];
list: LIST OF REF   => {
lst: LIST OF REF ← list; list ← NIL;
FOR lst ← lst, lst.rest WHILE lst#NIL DO list ← CONS[Copy[lst.first], list] ENDLOOP;
lst ← list; list ← NIL;
FOR lst ← lst, lst.rest WHILE lst#NIL DO list ← CONS[lst.first, list] ENDLOOP;
RETURN[list]};
ENDCASE => ERROR};
OpExpr: PUBLIC PROC[op: OpIndex, e1, e2: Expression] RETURNS[Expression] = {
e1 ← Copy[e1];
e2 ← Copy[e2];
IF e1=NIL THEN RETURN[e2]; -- This may not be right but...
IF e2=NIL THEN RETURN[e1]; -- This may not be right but...
IF e1=NIL THEN ERROR;
IF e2=NIL THEN ERROR;
WITH e1 SELECT FROM
rope1: IO.ROPE  => WITH e2 SELECT FROM
rope2: IO.ROPE  => RETURN[LIST[OpNm[op], rope1, rope2]];
list2: LIST OF REF => IF NmOp[NARROW[list2.first]]=op
THENRETURN[CONS  [OpNm[op], CONS[ rope1, list2.rest] ] ]
ELSERETURN[LIST  [OpNm[op],    rope1, list2 ]];
ENDCASE    => ERROR;
list1: LIST OF REF => WITH e2 SELECT FROM
rope2: IO.ROPE  => IF NmOp[NARROW[list1.first]]=op
THENRETURN[CONS  [OpNm[op], CONS[ rope2, list1.rest] ] ]
ELSERETURN[LIST  [OpNm[op],    rope2, list1 ]];
list2: LIST OF REF => {
ok1: BOOL ← NmOp[NARROW[list1.first]]=op;
ok2: BOOL ← NmOp[NARROW[list2.first]]=op;
IF ~ok1 AND ~ok2 THEN RETURN[LIST[OpNm[op], list1, list2]];
IF ~ok1 AND ok2 THEN RETURN[CONS [OpNm[op], CONS[ list1, list2.rest] ] ];
IF ok1 AND ~ok2 THEN RETURN[CONS [OpNm[op], CONS[ list2, list1.rest] ] ];
list2 ← list2.rest;
FOR list1 ← list1.rest, list1.rest WHILE list1#NIL DO
list2 ← CONS[list1.first, list2] ENDLOOP;
RETURN[CONS[OpNm[op], list2]]};
ENDCASE    => ERROR;
ENDCASE    => ERROR};
ReplaceID: PUBLIC PROC[old, new: IO.ROPE, symTab: SymTab.Ref] = {
DoReplace: PROC[expr: Expression] = {
WITH expr SELECT FROM
int: REF INT   => RETURN;
elist: LIST OF REF => {
FOR elist ← elist.rest, elist.rest WHILE elist#NIL DO WITH elist.first SELECT FROM
rp: IO.ROPE  => IF rp.Equal[old] THEN elist.first ← new;
ENDCASE  => DoReplace[elist.first] ENDLOOP};
ENDCASE => ERROR };
Replace: SymTab.EachPairAction = {
WITH val SELECT FROM
rope: IO.ROPE => IF old.Equal[rope] THEN []←SymTab.Store[symTab, key, new];
ENDCASE   => DoReplace[val]};
[]←SymTab.Pairs[symTab, Replace]};
Eval: PUBLIC PROC[expr: REF, varTab: SymTab.Ref] RETURNS[BOOL] = {
Must be a simple expression (nand, and, nor, or, not)
All variables must be registered in varTab as "TRUE" or "FALSE"
true:  IO.ROPE ← "TRUE";
false:  IO.ROPE ← "FALSE";
WITH expr SELECT FROM
rope: IO.ROPE  => {
val: IO.ROPE;
IF rope.Equal[true] THEN RETURN[TRUE];
IF rope.Equal[false] THEN RETURN[FALSE];
val ← NARROW[SymTab.Fetch[varTab, rope].val];
RETURN[val.Equal[true]]};
elist: LIST OF REF => {
op: OpIndex ← NmOp[NARROW[elist.first]];
val: BOOL  ← Eval[elist.rest.first, varTab];
IF elist.rest.rest#NIL THEN FOR elist ← elist.rest.rest, elist.rest WHILE elist#NIL
DO SELECT op FROM
nand, and => IF NOT (val ← val AND Eval[elist.first, varTab]) THEN EXIT;
nor, or  => IF    (val ← val OR Eval[elist.first, varTab]) THEN EXIT;
ENDCASE; ENDLOOP;
RETURN[SELECT op FROM nand, nor, not => ~ val, ENDCASE => val ]};
ENDCASE => ERROR};
Equal: PUBLIC PROC[expr1, expr2: REF] RETURNS[equal: BOOLTRUE] = {
Must be a simple expressions (nand, and, nor, or, not)
true:  IO.ROPE   ← "TRUE";
false:  IO.ROPE   ← "FALSE";
varTab: SymTab.Ref  ← SymTab.Create[];
vars:  LIST OF IO.ROPE;
RegisterVars: PROC[e: REF] = {
WITH e SELECT FROM
rope: IO.ROPE =>
IF ~rope.Equal[true] AND ~rope.Equal[false] THEN vars ← CONS[rope, vars];
elist: LIST OF REF =>
SELECT NmOp[NARROW[elist.first]] FROM
mach, out, var, func => ERROR;
ENDCASE => FOR elist ← elist.rest, elist.rest WHILE elist#NIL
DO RegisterVars[elist.first] ENDLOOP;
ENDCASE => ERROR};
VerifyPairEqual: PROC[vs: LIST OF IO.ROPE] = {
IF vs = NIL
THEN equal ← (Eval[expr1, varTab] = Eval[expr2, varTab])
ELSE {
[]←SymTab.Store[varTab, vs.first, true]; VerifyPairEqual[vs.rest];
IF equal THEN
[]←SymTab.Store[varTab, vs.first, false]; VerifyPairEqual[vs.rest]}};
RegisterVars[expr1];
RegisterVars[expr2];
vars ← RopeList.Sort[vars, RopeList.Compare];
FOR temp: LIST OF IO.ROPE ← vars, temp.rest WHILE temp#NIL AND temp.rest#NIL DO
IF temp.first.Equal[temp.rest.first] THEN temp.rest ← temp.rest.rest ENDLOOP;
VerifyPairEqual[vars]};
END.