Instanciation of expressions
Low level function for creating Expressions.
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]]]};
Creates an expression, setting the case field to the appriopriate value depending on possible simplifications.
If comp=FALSE then both whenTrue and whenFalse have in fact opposite values
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;
Does not take expr.norm into account
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]]};
Listify: PUBLIC PROC [expr1, expr2, expr3, expr4, expr5, expr6: Expression ← NIL]
RETURNS [list: LIST OF Expression ← NIL] =
{IF expr6#NIL THEN list ← LIST [expr6];
IF expr5#NIL THEN list ← CONS [expr5, list];
IF expr4#NIL THEN list ← CONS [expr4, list];
IF expr3#NIL THEN list ← CONS [expr3, list];
IF expr2#NIL THEN list ← CONS [expr2, list];
IF expr1#NIL THEN list ← CONS [expr1, list]};
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]];
};
Returns (expr AND exprTrue) OR (~expr AND exprFalse)
Norm specifies whether or not If should negate both exprTrue and exprFalse
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]]]};
Expanses once the expression expr, assuming that its first variable is an auxiliary
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.varNb<auxVarNb
THEN expr
ELSE IF expr.varNb>auxVarNb
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]]]};
This one is the primitive for the others
OrTwo:
PUBLIC
PROC [table: TableOfVariables, expr1, expr2: Expression, norm1, norm2:
BOOL ←
TRUE]
RETURNS [result: Expression] =
BEGIN
varNb: VarNb ← 0;
Output["OrTwo : ", RopeFromExpression[table, expr1, norm1], " & ", RopeFromExpression[table, expr2, norm2], "\n"];
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]];
compute variable on which to switch
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]];
Output["-->", 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]]};
Procs operating on expressions
NegCase:
PROC [case: CompClass]
RETURNS [CompClass] =
{RETURN [SELECT case FROM case0X => case1X, case1X => case0X, caseX0 => caseX1, caseX1 => caseX0, ENDCASE => case]};
This Equal follows auxVar for equality
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;
};
RopeFromExpressions: PUBLIC PROC [exprs: LIST OF Expression] RETURNS [rope: ROPE ← NIL] =
{IF exprs#NIL THEN {rope ← RopeFromExpression[table, exprs.first]; exprs ← exprs.rest};
WHILE exprs#NIL DO
rope ← Rope.Cat[rope, ", ", RopeFromExpression[table, exprs.first]]; exprs ← exprs.rest ENDLOOP};
Utilities
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];
};
Append: PUBLIC PROC [list1, list2: LIST OF Expression] RETURNS [LIST OF Expression] =
{RETURN [IF list1=NIL THEN list2 ELSE CONS [list1.first, Append[list1.rest, list2]]]};
Reverse: PUBLIC PROC [list: LIST OF Expression] RETURNS [newList: LIST OF Expression ← NIL] =
{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, t6:
ROPE ←
NIL] = {
TerminalIO.WriteRope[Rope.Cat[t1, t2, t3, t4, t5, t6]];
};
Alps heart
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;
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;
Output["."];
nbterms ← nbterms+1;
ENDLOOP;
2nd Pass
IF inputs=
NIL
AND outputs=
NIL
THEN {
Output["First pass on ", fileName, " done: ", Convert.RopeFromInt[nbins], " inputs; ", Rope.Cat[Convert.RopeFromInt[nbterms], " 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};
};
Initialize the table
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;
We now read for good the PLA
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
]]];
Output["term: ", RopeFromExpression[table, expr], "\n"];
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;
};
To create a fresh UsedVarsSequence with contents being ALL[FALSE]
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;
};
printLevel=0 prints nothing and just returns statistics
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 -- statistics about variables
FOR input: VarNb IN (0..table.size) DO
nbOfCasesArray: NbOfCasesArray ← ALL[0];
addCase: EachNodeProc = {IF expr.varNb=input THEN nbOfCasesArray[expr.case] ← nbOfCasesArray[expr.case] + 1};
FOR outs: LIST OF OutputRef ← table.outputs, outs.rest WHILE outs#NIL DO
Enumerate[outs.first.expr, addCase];
ENDLOOP;
Output[table[input].name, " => "];
FOR case: CompClass IN [case10..caseXY] DO
IF nbOfCasesArray[case]#0 THEN Output[RopeFromCompClass[case], ": ", Convert.RopeFromInt[nbOfCasesArray[case]], "; "];
ENDLOOP;
Output["\n"];
ENDLOOP;
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"];
};
};
With printLevel=0, just final statistics are printed
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
Returns an expression equalling expr when aux is equal to valAux (true/false depending on norm), but which does not depend on any variable used in aux, or NIL if it is not possible to find such an expression.
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;
if meaninglesss when variable is true, just assume variable is false
FullEqual[table, WhenTrue[aux], true, ~norm] =>
RETURN [EvalExprWhenAuxIs[IF expr.varNb=aux.varNb THEN WhenFalse[expr] ELSE expr, WhenFalse[aux], norm]];
if meaninglesss when variable is false, just assume variable is true
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<aux.varNb
THEN
RETURN [expr];
The two following are case that happen quite frequently, and which are easy to test
IF Equal[table, expr, aux]
THEN
{Output["="]; RETURN [ExprFromVarNb[auxVar, TRUE]]};
IF Equal[table, expr, aux,
FALSE]
THEN
{Output["="]; RETURN [ExprFromVarNb[auxVar, FALSE]]};
Some factorization can be tried
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<varNb THEN RETURN[expr];
IF expr.varNb=varNb THEN RETURN[Norm[(IF varNbNorm THEN WhenTrue ELSE WhenFalse)[expr], expr.norm]];
newExpr ← CopyTree[table, expr, Construct];
};
Enumerate[expr, IsUsed];
RETURN [IF ~isUsed THEN expr ELSE Construct[expr]];
};
Checksum:
PUBLIC
PROC [table: TableOfVariables]
RETURNS [checksum:
INT ← 0] = {
ExprWhenAll:
PROC [expr: Expression, varValue:
BOOL]
RETURNS [
BOOL] = {
aux: OutputRef ← table[expr.varNb].fromOutput;
IF expr=true OR expr=false THEN RETURN[expr=true];
RETURN[ExprWhenAll[
(IF (IF aux#NIL AND aux.type=aux THEN ExprWhenAll[aux.expr, varValue] ELSE varValue) THEN WhenTrue ELSE WhenFalse)[expr],
varValue] = expr.norm];
};
FOR outs:
LIST
OF OutputRef ← table.outputs, outs.rest
WHILE outs#
NIL
DO
type: OutputType = outs.first.type;
IF type=output
OR type=latch
THEN {
IF ExprWhenAll[outs.first.expr, TRUE] THEN checksum ← checksum+100;
IF ExprWhenAll[outs.first.expr, FALSE] THEN checksum ← checksum+1;
};
ENDLOOP;
};
EstimatedArea:
PUBLIC
PROC [table: TableOfVariables]
RETURNS [area:
INT ← 0] = {
FOR outs:
LIST
OF OutputRef ← table.outputs, outs.rest
WHILE outs#
NIL
DO
area ← area + MaxWidth[table, outs.first.expr] + (IF outs.first.type=output THEN 1 ELSE 2);
ENDLOOP;
area ← area * (table.size-1);
};