# order of evaluation ?

Konst Sushenko konsu@microsoft.com
Sun, 17 Feb 2002 20:50:22 -0800

```This is a multi-part message in MIME format.

--------------InterScan_NT_MIME_Boundary
Content-Type: multipart/alternative;
boundary="----_=_NextPart_001_01C1B837.C5CE3A92"

------_=_NextPart_001_01C1B837.C5CE3A92
Content-Type: text/plain;
charset="us-ascii"
Content-Transfer-Encoding: quoted-printable

hello,
=20
below is the code that i wrote as an excercise for myself (I am still
=20
it implements a straighforward way to simplify boolean expressions, and
should be self-explanatory.
=20
my question is, if i have an expression such as ((Const False) :&:
<subexp>), will <subexp> be reduced first (according to the definition
'simplify (x :&: y) =3D simplify' ((simplify x) :&: (simplify y))') or
will laziness do the right thing, and emit (Const False) without looking
into <exp>?
=20
i think the latter, but would appreciate a word from an expert.
=20
thanks
konst
=20
PS: any coding suggestions, etc. are also welcome
=20
=20
=20

infixr 3 :&:
infixr 2 :|:
=20
data Exp =3D Const Bool
| Sym String
| Not Exp
| Exp :&: Exp
| Exp :|: Exp
=20
instance Eq Exp where
(Const x) =3D=3D (Const y) =3D x=3D=3Dy
(Sym x)   =3D=3D (Sym y)   =3D x=3D=3Dy
(Not x)   =3D=3D (Not y)   =3D x=3D=3Dy
(x :&: y) =3D=3D (u :&: v) =3D x=3D=3Du && y=3D=3Dv || x=3D=3Dv && =
y=3D=3Du
(x :|: y) =3D=3D (u :|: v) =3D x=3D=3Du && y=3D=3Dv || x=3D=3Dv && =
y=3D=3Du
_         =3D=3D _         =3D False
=20
simplify (x :&: y) =3D simplify' ((simplify x) :&: (simplify y))
simplify (x :|: y) =3D simplify' ((simplify x) :|: (simplify y))
simplify (Not x)   =3D simplify' (Not (simplify x))
simplify x         =3D x
=20
simplify' (Not (Const True))     =3D Const False
simplify' (Not (Const False))    =3D Const True
=20
simplify' (Not (Not x))          =3D x
=20
simplify' ((Not x) :&: y) | x=3D=3Dy =3D Const False
simplify' (x :&: (Not y)) | x=3D=3Dy =3D Const False
simplify' ((Not x) :|: y) | x=3D=3Dy =3D Const True
simplify' (x :|: (Not y)) | x=3D=3Dy =3D Const True
=20
simplify' ((Const False) :&: _)  =3D Const False
simplify' (_ :&: (Const False))  =3D Const False
simplify' ((Const True) :&: x)   =3D x
simplify' (x :&: (Const True))   =3D x
=20
simplify' ((Const True) :|: _)   =3D Const True
simplify' (_ :|: (Const True))   =3D Const True
simplify' ((Const False) :|: x)  =3D x
simplify' (x :|: (Const False))  =3D x
=20
simplify' (x :&: y) | x=3D=3Dy       =3D x
simplify' (x :|: y) | x=3D=3Dy       =3D x
=20
simplify' x                      =3D x
=20

------_=_NextPart_001_01C1B837.C5CE3A92
Content-Type: text/html;
charset="us-ascii"
Content-Transfer-Encoding: quoted-printable

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; =
charset=3Dus-ascii">
<TITLE>Message</TITLE>

<BODY>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2>hello,</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2></FONT></SPAN>&nbsp;</DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New" =
size=3D2>below is the=20
code that i wrote as an excercise for myself (I am still learning=20
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2></FONT></SPAN>&nbsp;</DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New" =
size=3D2>it=20
implements a straighforward way to simplify boolean expressions, and =
should be=20
self-explanatory.</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2></FONT></SPAN>&nbsp;</DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New" =
size=3D2>my question=20
is, if i have an expression such as ((Const False) :&amp;: =
&lt;subexp&gt;), will=20
&lt;subexp&gt; be reduced first (according to the definition=20
'</FONT></SPAN><SPAN class=3D142474104-18022002><FONT face=3D"Courier =
New"=20
size=3D2>simplify (x :&amp;: y) =3D simplify' ((simplify x) :&amp;: =
(simplify y))')=20
or will laziness do the right thing, and emit (Const False) without =
looking into=20
&lt;exp&gt;?</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2></FONT></SPAN>&nbsp;</DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New" =
size=3D2>i think the=20
latter, but would appreciate a word from an expert.</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2></FONT></SPAN>&nbsp;</DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2>thanks</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2>konst</FONT></SPAN></DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New"=20
size=3D2></FONT></SPAN>&nbsp;</DIV>
<DIV><SPAN class=3D142474104-18022002><FONT face=3D"Courier New" =
size=3D2>PS: any=20
coding suggestions, etc. are also welcome</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT><FONT face=3D"Courier =
New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT><FONT face=3D"Courier =
New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><BR></DIV></SPAN><FONT face=3D"Courier New" =
size=3D2></FONT>
<DIV><FONT face=3D"Courier New" size=3D2></FONT><FONT face=3D"Courier =
New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><FONT =
face=3D"Courier New"=20
size=3D2></FONT><FONT face=3D"Courier New" size=3D2></FONT><BR><FONT=20
face=3D"Courier New" size=3D2>infixr 3 :&amp;:<BR>infixr 2 =
:|:</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2>data Exp =3D Const=20
Bool<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | Sym=20
String<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | Not=20
Exp<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | Exp :&amp;:=20
Exp<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | Exp :|:=20
Exp</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2>instance Eq Exp =
where<BR>&nbsp;&nbsp;&nbsp;=20
(Const x) =3D=3D (Const y) =3D x=3D=3Dy<BR>&nbsp;&nbsp;&nbsp; (Sym =
x)&nbsp;&nbsp; =3D=3D (Sym=20
y)&nbsp;&nbsp; =3D x=3D=3Dy<BR>&nbsp;&nbsp;&nbsp; (Not x)&nbsp;&nbsp; =
=3D=3D (Not=20
y)&nbsp;&nbsp; =3D x=3D=3Dy<BR>&nbsp;&nbsp;&nbsp; (x :&amp;: y) =3D=3D =
(u :&amp;: v) =3D=20
x=3D=3Du &amp;&amp; y=3D=3Dv || x=3D=3Dv &amp;&amp; =
y=3D=3Du<BR>&nbsp;&nbsp;&nbsp; (x :|: y) =3D=3D=20
(u :|: v) =3D x=3D=3Du &amp;&amp; y=3D=3Dv || x=3D=3Dv &amp;&amp; =
y=3D=3Du<BR>&nbsp;&nbsp;&nbsp;=20
_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =3D=3D=20
_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =3D False</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify (x :&amp;: y) =3D =
simplify'=20
((simplify x) :&amp;: (simplify y))<BR>simplify (x :|: y) =3D simplify' =
((simplify=20
x) :|: (simplify y))<BR>simplify (Not x)&nbsp;&nbsp; =3D simplify' (Not =
(simplify=20
x))<BR>simplify x&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =3D=20
x</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify' (Not (Const=20
True))&nbsp;&nbsp;&nbsp;&nbsp; =3D Const False<BR>simplify' (Not (Const=20
False))&nbsp;&nbsp;&nbsp; =3D Const True</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify' (Not (Not=20
x))&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =3D =
x</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify' ((Not x) :&amp;: y) | =
x=3D=3Dy =3D=20
Const False<BR>simplify' (x :&amp;: (Not y)) | x=3D=3Dy =3D Const =
False<BR>simplify'=20
((Not x) :|: y) | x=3D=3Dy =3D Const True<BR>simplify' (x :|: (Not y)) | =
x=3D=3Dy =3D Const=20
True</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify' ((Const False) =
:&amp;: _)&nbsp; =3D=20
Const False<BR>simplify' (_ :&amp;: (Const False))&nbsp; =3D Const=20
False<BR>simplify' ((Const True) :&amp;: x)&nbsp;&nbsp; =3D =
x<BR>simplify' (x=20
:&amp;: (Const True))&nbsp;&nbsp; =3D x</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify' ((Const True) :|: =
_)&nbsp;&nbsp;=20
=3D Const True<BR>simplify' (_ :|: (Const True))&nbsp;&nbsp; =3D Const=20
True<BR>simplify' ((Const False) :|: x)&nbsp; =3D x<BR>simplify' (x :|: =
(Const=20
False))&nbsp; =3D x</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify' (x :&amp;: y) |=20
x=3D=3Dy&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =3D x<BR>simplify' (x :|: =
y) |=20
x=3D=3Dy&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =3D x</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT>&nbsp;</DIV>
<DIV><FONT face=3D"Courier New" size=3D2>simplify'=20
x&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=20
=3D x</FONT></DIV>
<DIV><FONT face=3D"Courier New" =
size=3D2></FONT>&nbsp;</DIV></BODY></HTML>

------_=_NextPart_001_01C1B837.C5CE3A92--

--------------InterScan_NT_MIME_Boundary--

```