Re: Fragmented arrays?

--===============8212321394312988439==
Content-Type: multipart/alternative; boundary=0015175cab10655cdc047d87f87c

--0015175cab10655cdc047d87f87c
Content-Type: text/plain; charset=ISO-8859-1

2010/1/19 John Reppy <[email protected]>

> I'm not sure what you are getting at.  Arrays support update in place, so
> at the machine-level, the
> update operation is just a store instruction (plus any write-barrier
> overhead required by the GC).
>
>        - John
>


I think I see where the confusion lies. I believe(d) that even referenced
values (eg. arrays) were immutable.

If they are immutable:
When updating a cell in such an array, one would have to write only the new
content of that celle to memory. Else, it wouldn't be constant time. That
again would mean that the new content would be placed somewere outside the
existing array (as we are not allowed to overwrite the existing array). This
means that the new array (semantically: the old array modified with the new
value) would physically be fragmented.

If they are mutable:
Well then theres no problems with constant time read and write - they would
not fragment the array.


A local SML-expert told me that referenced values were immutable, and that
if they weren't, it would be a hazard for the purity of the functional parts
of the program, as a reference passed around as a parameter would ruin the
promise that a function has no side effect.


/Jon

--0015175cab10655cdc047d87f87c
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<br><div class=3D"gmail_quote">2010/1/19 John Reppy <span dir=3D"ltr">&lt;<=
a href=3D"mailto:[email protected]">[email protected]</a>&gt;</span><br=
><blockquote class=3D"gmail_quote" style=3D"border-left: 1px solid rgb(204,=
 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

I&#39;m not sure what you are getting at. =A0Arrays support update in place=
, so at the machine-level, the<br>
update operation is just a store instruction (plus any write-barrier overhe=
ad required by the GC).<br>
<br>
 =A0 =A0 =A0 =A0- John<br></blockquote><div>=A0<br><br>I think I see where =
the confusion lies. I believe(d) that even referenced values (eg. arrays) w=
ere immutable.<br><br>If they are immutable:<br>When updating a cell in suc=
h an array, one would have to write only the new content of that celle to m=
emory. Else, it wouldn&#39;t be constant time. That again would mean that t=
he new content would be placed somewere outside the existing array (as we a=
re not allowed to overwrite the existing array). This means that the new ar=
ray (semantically: the old array modified with the new value) would physica=
lly be fragmented.<br>

<br>If they are mutable:<br>Well then theres no problems with constant time=
 read and write - they would not fragment the array.<br></div></div><br><br=
>A local SML-expert told me that referenced values were immutable, and that=
 if they weren&#39;t, it would be a hazard for the purity of the functional=
 parts of the program, as a reference passed around as a parameter would ru=
in the promise that a function has no side effect.<br>

<br><br>/Jon<br>

--0015175cab10655cdc047d87f87c--


--===============8212321394312988439==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

------------------------------------------------------------------------------
Throughout its 18-year history, RSA Conference consistently attracts the
world's best and brightest in the field, creating opportunities for Conference
attendees to learn about information security's most important issues through
interactions with peers, luminaries and emerging and established companies.
http://p.sf.net/sfu/rsaconf-dev2dev
--===============8212321394312988439==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
Smlnj-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/smlnj-list

--===============8212321394312988439==--