[M3devel] small set comparisons understood, now just to understand the front end code..
Mika Nystrom
mika at async.caltech.edu
Mon Apr 14 22:10:05 CEST 2008
Sorry, I think the Green Book is completely unambiguous about this.
a < b is the same as a <= b AND a # b for all a and b, no matter
the type (set, integer, or floating). That's what 2.6.11 says, and
it seems correct, because it implies that for sets, <= is the subset
relation, and < is the proper subset relation.
Mika
Jay writes:
>--_a67e670a-e4c4-4f68-a1a3-4f4661e52338_
>Content-Type: text/plain; charset="iso-8859-1"
>Content-Transfer-Encoding: quoted-printable
>
> a < b "should be implemented as" (a & b) =3D=3D a=20
>=20
> I believe, and so on.=20
>I could be wrong. I only thought about it a few minutes.=20
>=20
> The current incorrect code is:=20
>PROCEDURE Set_compare (s: Size; op: Cmp) =3D BEGIN IF Force_pair (comm=
>ute :=3D TRUE) THEN op :=3D M3CG.SwappedCompare [op]; END; IF (s=
> <=3D Target.Integer.size) THEN cg.compare (Target.Word.cg_type, Targe=
>t.Integer.cg_type, op); ELSE cg.set_compare (AsBytes (s), op, Target.I=
>nteger.cg_type); END; SPop (2, "Set_eq"); SPush (Type.Int32); END=
> Set_compare;
>=20
>which generates simply, I think this was <=3D (jbe -- jump if below or equa=
>l):
>=20
>=20
> 0040119C: 56 push esi 0040119D: E8 AE FE FF FF =
> call _Main__m 004011A2: 83 C4 04 add esp,4
>=20
> ... end of previous line that just called m("foo")=20
>=20
> ; push a string to print=20
> 004011A5: 8D 35 2C 12 40 00 lea esi,ds:[40122Ch] 004011AB: 56 =
> push esi
>=20
> ; compare two sets=20
> ; one is constant 0x15; one is a global=20
> 004011AC: 83 3D 44 90 45 00 cmp dword ptr ds:[459044h],15h =
> 15
>=20
> ; spend a while converting the compare result to a boolean 004011B3: 0F =
>96 45 FC setbe byte ptr [ebp-4] 004011B7: 33 DB =
>xor ebx,ebx 004011B9: 8A 5D FC mov bl,byte ptr [=
ebp-4] 004011BC: 83 FB 00 cmp ebx,0 004011BF: 0F 94 45 =
>F8 sete byte ptr [ebp-8] 004011C3: 33 D2 xor =
> edx,edx 004011C5: 8A 55 F8 mov dl,byte ptr [ebp-8]
> ; and then push that boolean=20
> 004011C8: 52 push edx
> 004011C9: E8 6C FF FF FF call _Main__checkM
>oh, you are right, < needs to also be !=3D.
>I thought it was suspicious to have only two implementations of four operat=
>ions, but I did like the resulting efficiency. :)
>Hey, I was at least sure the current code was wrong.
>=20
> - Jay
>
>
>
>> To: jayk123 at hotmail.com> Subject: Re: [M3devel] small set comparisons und=
>erstood, now just to understand the front end code.. > Date: Mon, 14 Apr 20=
>08 10:16:01 -0700> From: mika at async.caltech.edu> > Jay writes:> >--_6435b74=
>a-d943-44c2-9091-ab0408dc7ed0_> >Content-Type: text/plain; charset=3D"iso-8=
>859-1"> >Content-Transfer-Encoding: quoted-printable> >> >> >currently set =
><,>,<=3D3D,>=3D3D are implemented merely as> >integer <,>,<=3D3D,>=3D3D> >=
>=3D20> >This is wrong.> >=3D20> >I believe it should be:> >=3D20> >a < b =
>=3D3D> (a & b) =3D3D=3D3D a> >a <=3D3D b =3D3D> (a & b) =3D3D=3D3D a (same =
>as <=3D3D)> >a > b =3D3D> (a & b) =3D3D=3D3D b> >a >=3D3D b =3D3D> (a & b) =
>=3D3D=3D3D b (same as >)> > You don't actually mean logical implication by =
>your arrows do you,> but equivalence, where the objects to the left of the =
>arrow refer> to the abstract sets a and b and the objects to the right of t=
>he> arrow refer to bit-vector implementations (in C) of the same?> > Green =
>Book, page 57, section 2.6.1:> > "In all cases, x < y means (x <=3D y) AND =
>(x # y), and x > y means y < x."> > So in your syntax a > b would be ((a & =
>b) =3D=3D a) && (a !=3D b).> > Also, just above it, > > "The expression x >=
>=3D y is equivalent to y <=3D x."> > Why not define the operation "x >=3D y=
>" and then use the two statements> from the Green Book to generate the rest=
>?> > Mika=
>
>--_a67e670a-e4c4-4f68-a1a3-4f4661e52338_
>Content-Type: text/html; charset="iso-8859-1"
>Content-Transfer-Encoding: quoted-printable
>
><html>
><head>
><style>
>.hmmessage P
>{
>margin:0px;
>padding:0px
>}
>body.hmmessage
>{
>FONT-SIZE: 10pt;
>FONT-FAMILY:Tahoma
>}
></style>
></head>
><body class=3D'hmmessage'> a < b "should be implemented as" (a &=
>; b) =3D=3D a <BR>
> <BR>
> I believe, and so on. <BR>
>I could be wrong. I only thought about it a few minutes. <BR>
> <BR>
> The current incorrect code is: <BR>
><BR>PROCEDURE Set_compare (s: Size; op: Cmp) =3D<BR> BEGIN<BR>&=
>nbsp; IF Force_pair (commute :=3D TRUE) THEN<BR> &nb=
>sp; op :=3D M3CG.SwappedCompare [op];<BR> END=
>;<BR> IF (s <=3D Target.Integer.size)<BR> &=
>nbsp; THEN cg.compare (Target.Word.cg_type, Target.Integer.cg_t=
>ype, op);<BR> ELSE cg.set_compare (AsBytes (s=
>), op, Target.Integer.cg_type);<BR> END;<BR> &=
>nbsp; SPop (2, "Set_eq");<BR> SPush (Type.Int32);<BR>&nbs=
>p; END Set_compare;<BR><BR>
> <BR>
>which generates simply, I think this was <=3D (jbe -- jump if below or e=
>qual):<BR>
> <BR>
> <BR>
> 0040119C: 56 &n=
>bsp; push =
> esi<BR> 0040119D: E8 AE FE FF FF =
> call _Main__m<BR> 004011A2=
>: 83 C4 04 add&=
>nbsp; esp,4<BR>
> <BR>
> ... end of previous line that just called m("foo") <BR>
> <BR>
> ; push a string to print <BR>
> 004011A5: 8D 35 2C 12 40 00 lea &=
>nbsp; esi,ds:[40122Ch]<BR> 004011AB: 56 =
> &nb=
>sp; push esi<BR>
> <BR>
> ; compare two sets <BR>
> ; one is constant 0x15; one is a global <BR>
> 004011AC: 83 3D 44 90 45 00 cmp &=
>nbsp; dword ptr ds:[459044h],15h<BR> &nb=
>sp; 15<BR>
> <BR>
> ; spend a while converting the compare result to a boolean <BR> =
> 004011B3: 0F 96 45 FC setbe =
>; byte ptr [ebp-4]<BR> 004011B7: 33 DB&=
>nbsp; &nbs=
>p; xor ebx,ebx<BR> 00=
>4011B9: 8A 5D FC  =
>; mov bl,byte ptr [ebp-4]<B=
>R> 004011BC: 83 FB 00 =
> cmp ebx,0<BR>&=
>nbsp; 004011BF: 0F 94 45 F8 sete&=
>nbsp; byte ptr [ebp-8]<BR> 004011=
>C3: 33 D2 =
> xor edx,edx<BR=
>> 004011C5: 8A 55 F8 &=
>nbsp; mov dl,byte ptr=
> [ebp-8]<BR><BR>
> ; and then push that boolean <BR>
> 004011C8: 52 &n=
>bsp; push =
> edx<BR>
> 004011C9: E8 6C FF FF FF call &nb=
>sp; _Main__checkM<BR><BR><BR>
>oh, you are right, < needs to also be !=3D.<BR>
>I thought it was suspicious to have only two implementations of four operat=
>ions, but I did like the resulting efficiency. :)<BR>
Hey, I was at least sure the current code was wrong.<BR>
> <BR>
> - Jay<BR><BR><BR><BR>
>
><HR id=3DstopSpelling>
><BR>
>> To: jayk123 at hotmail.com<BR>> Subject: Re: [M3devel] small set compa=
>risons understood, now just to understand the front end code.. <BR>> Dat=
>e: Mon, 14 Apr 2008 10:16:01 -0700<BR>> From: mika at async.caltech.edu<BR>=
>> <BR>> Jay writes:<BR>> >--_6435b74a-d943-44c2-9091-ab0408dc7e=
>d0_<BR>> >Content-Type: text/plain; charset=3D"iso-8859-1"<BR>> &g=
>t;Content-Transfer-Encoding: quoted-printable<BR>> ><BR>> ><BR>=
>> >currently set <,>,<=3D3D,>=3D3D are implemented merely=
> as<BR>> >integer <,>,<=3D3D,>=3D3D<BR>> >=3D20<BR>=
>> >This is wrong.<BR>> >=3D20<BR>> >I believe it should b=
>e:<BR>> >=3D20<BR>> >a < b =3D3D> (a & b) =3D3D=3D3D =
>a<BR>> >a <=3D3D b =3D3D> (a & b) =3D3D=3D3D a (same as <=
>;=3D3D)<BR>> >a > b =3D3D> (a & b) =3D3D=3D3D b<BR>> >=
>;a >=3D3D b =3D3D> (a & b) =3D3D=3D3D b (same as >)<BR>> <B=
>R>> You don't actually mean logical implication by your arrows do you,<B=
>R>> but equivalence, where the objects to the left of the arrow refer<BR=
>>> to the abstract sets a and b and the objects to the right of the<BR>&=
>gt; arrow refer to bit-vector implementations (in C) of the same?<BR>> <=
>BR>> Green Book, page 57, section 2.6.1:<BR>> <BR>> "In all cases,=
> x < y means (x <=3D y) AND (x # y), and x > y means y < x."<BR=
>>> <BR>> So in your syntax a > b would be ((a & b) =3D=3D a) &=
>amp;& (a !=3D b).<BR>> <BR>> Also, just above it, <BR>> <BR>&g=
>t; "The expression x >=3D y is equivalent to y <=3D x."<BR>> <BR>&=
>gt; Why not define the operation "x >=3D y" and then use the two stateme=
>nts<BR>> from the Green Book to generate the rest?<BR>> <BR>> Mika=
><BR><BR></body>
></html>=
>
>--_a67e670a-e4c4-4f68-a1a3-4f4661e52338_--
More information about the M3devel
mailing list