Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] View of /sml/trunk/src/smlnj-lib/Doc/mldoc/uref.mldoc
ViewVC logotype

View of /sml/trunk/src/smlnj-lib/Doc/mldoc/uref.mldoc

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2 - (download) (annotate)
Sat Oct 4 23:33:09 1997 UTC (21 years, 11 months ago) by monnier
File size: 5490 byte(s)
Initial revision
<!-- uref.mldoc -->
<!-- -->
<!-- This documentation was adapted from comments written by -->
<!-- Fritz Henglein. -->

<!DOCTYPE ML-DOC SYSTEM>

<COPYRIGHT OWNER="AT&AMP;T Research" YEAR=1996>
<VERSION VERID="1.0" YEAR=1996 MONTH=5 DAY=29>
<TITLE>The UREF signature</TITLE>

<SECT>
<HEAD>The <CD/UREF/ signature</HEAD>

<PP>
The <SIGREF NOLINK/UREF/ signature defines the interface to a union/find
data type with ref-like interface.
An implementation of this interface consists of the
<TYREF SIGID="UREF"/uref/ type constructor, with operations for
creating a new uref, getting the contents of
an element, checking for equality of two elements, and
for joining two elements.
The <TYREF SIGID="UREF"/uref/ type is analogous to
<TYREF STRID="General" DOCUMENT=SML-BASIS-DOC/ref/ as expressed in the
following table:
<TABLE>
  <COL ALIGN=LEFT> <COL ALIGN=CENTER> <COL ALIGN=CENTER>
  <TR>
    <TH>		<TH COLSPAN=2>Type
  <TR>
    <TH>Operation	<TH><CD/'a ref/		<TH><CD/'a uref/
  <TR>
    <TD>Introduction
    <TD><VALREF STRID="General" DOCUMENT=SML-BASIS-DOC/ref/
    <TD><VALREF SIGID="UREF"/uRef/
  <TR>
    <TD>Elimination
    <TD><VALREF STRID="General" DOCUMENT=SML-BASIS-DOC/!/
    <TD><VALREF SIGID="UREF"/!!/
  <TR>
    <TD>Equality
    <TD><VALREF STRID="General" DOCUMENT=SML-BASIS-DOC/=/
    <TD><VALREF SIGID="UREF"/equal/
  <TR>
    <TD>Update
    <TD><VALREF STRID="General" DOCUMENT=SML-BASIS-DOC/:=/
    <TD><VALREF SIGID="UREF"/update/
  <TR>
    <TD>Union
    <TD>n.a.
    <TD><VALREF SIGID="UREF"/union/, <VALREF SIGID="UREF"/link/,
        <VALREF SIGID="UREF"/unify/
</TABLE>
The main difference between references and urefs is in the
<VALREF SIGID="UREF"/union/ operation.
Without <VALREF SIGID="UREF"/union/, references and urefs can be used
interchangebly (except in pattern matching).
An assignment to a reference changes only the contents of the reference,
but not the reference itself.
In particular, any two references that were different (in the sense of the
equality predicate = returning <CD/false/) before an assignment will still
be so.
Their contents may or may not be equal after the assignment, though.
In contrast, applying the union operations (<VALREF SIGID="UREF"/link/,
<VALREF SIGID="UREF"/union/, <VALREF SIGID="UREF"/unify/) to two
uref elements makes the two elements themselves equal (in the sense of the
predicate <VALREF SIGID="UREF"/equal/ returning <CD/true/).
As a consequence their contents will also be identical: in the case of
<VALREF SIGID="UREF"/link/ and <VALREF SIGID="UREF"/union/ it will be the
contents of one of the two unioned elements, in the case of
<VALREF SIGID="UREF"/unify/ the contents is determined by a supplied unification
function.

<SIGNATURE SIGID="UREF">
  <SIGBODY SIGID="UREF" FILE=UREF-SIG>
    <SPEC>
      <TYPE><TYPARAM>'a<ID>uref
        <COMMENT>
	  The type constructor for union/find references.
    <SPEC>
      <VAL>uRef<TY>'a -> 'a uref
        <COMMENT>
          <PROTOTY>
          uRef <ARG/a/
          </PROTOTY>
	  creates a new, distinct, uref cell.
    <SPEC>
      <VAL>equal<TY>('a uref * 'a uref) -> bool
        <COMMENT>
          <PROTOTY>
          equal (<ARG/ur1/, <ARG/ur2/)
          </PROTOTY>
          returns <CD/true/ if and only if <ARG/ur1/ and <ARG/ur2/ are either
	  made by the same call to <VALREF/uRef/, or if they have been
	  unioned by a call to <VALREF/unify/, <VALREF/union/ or <VALREF/link/.
    <SPEC>
      <VAL>!!<TY>'a uref -> 'a
        <COMMENT>
          <PROTOTY>
          !! <ARG/ur/
          </PROTOTY>
          returns the contents of <ARG/ur/.
    <SPEC>
      <VAL>update<TY>('a uref * 'a) -> unit
        <COMMENT>
          <PROTOTY>
          update (<ARG/ur/, <ARG/x/)
          </PROTOTY>
          updates the contents of <ARG/ur/ to be <ARG/x/.
	  This update affects all urefs that have been unioned with <ARG/ur/.
    <SPEC>
      <VAL>unify<TY>(('a * 'a) -> 'a) -> ('a uref * 'a uref) -> unit
        <COMMENT>
          <PROTOTY>
          unify <ARG/f/ (<ARG/ur1/, <ARG/ur2/)
          </PROTOTY>
          makes <ARG/ur1/ and <ARG/ur2/ equal, and updates their value
	  to be the result of <CD/f(<VALREF/!!/<ARG/ur1/, <VALREF/!!/<ARG/ur2/)/.
	  The function <ARG/f/ is evaluated prior to unioning the urefs,
	  so if it raises an exception, no union takes place.
    <SPEC>
      <VAL>union<TY>('a uref * 'a uref) -> unit
        <COMMENT>
          <PROTOTY>
          union (<ARG/ur1/, <ARG/ur2/)
          </PROTOTY>
          makes <ARG/ur1/ and <ARG/ur2/ equal; the contents of the unioned
	  element is the contents of one of <ARG/ur1/ and <ARG/ur2/ before
	  the <CD/union/ operation.
	  After unioning, the elements <ARG/ur1/ and <ARG/ur2/ will be
	  congruent in the sense that they are interchangeable in any context.
    <SPEC>
      <VAL>link<TY>('a uref * 'a uref) -> unit
        <COMMENT>
          <PROTOTY>
          link (<ARG/ur1/, <ARG/ur2/)
          </PROTOTY>
          makes <ARG/ur1/ and <ARG/ur2/ equal; the contents of the linked
	  element is the contents of <ARG/ur2/ before the <CD/link/ operation.
  </SIGBODY>
  <SIGINSTANCE><ID>SimpleURef
  <SIGINSTANCE><ID>URef
  <DISCUSS>
    There are two implementations of the <SIGREF/UREF/ signature provided by
    the library: the <STRREF TOPID/SimpleURef/ structure represents urefs using
    a standard union/find data structure with path compression.
    The <STRREF TOPID/URef/ structure adds ranks to balance union operations.
  </DISCUSS>
</SIGNATURE>

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0