[M3devel] small set comparisons understood, now just to understand the front end code..

Jay jayk123 at hotmail.com
Mon Apr 14 23:55:48 CEST 2008


I think we are in agreement now on this.
My original assertions were indeed wrong for <= and >=.
I'm not even sure they were correct for < and >.
 
 - Jay



> To: jayk123 at hotmail.com> CC: m3devel at elegosoft.com> Subject: Re: [M3devel] small set comparisons understood, now just to understand the front end code.. > Date: Mon, 14 Apr 2008 13:10:05 -0700> From: mika at async.caltech.edu> > 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 &amp=> >; 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&nbsp=> >;      byte ptr [ebp-4]<BR>  004011B7: 33 DB&=> >nbsp;           &nbs=> >p; xor         ebx,ebx<BR>  00=> >4011B9: 8A 5D FC         &nbsp=> >; 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 &lt=> >;=3D3D)<BR>> >a > b =3D3D> (a & b) =3D3D=3D3D b<BR>> &gt=> >;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_--
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20080414/b44b69f1/attachment-0002.html>


More information about the M3devel mailing list