Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!noao!arizona!gudeman
From: gudeman@arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: side effects
Message-ID: <12796@megaron.arizona.edu>
Date: 24 Jul 89 08:56:46 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 55

In article  <MYltLT200VsiM0U3Yx@andrew.cmu.edu> gb17+@andrew.cmu.edu (George Thomas Baggott) writes:
>In a truly functional language (i.e. no side effects at all), a function
>for altering a large data structure (adding an entry to a dictionary,
>for example) would be written as:
>
>	dictionary_add(dictionary, entry) returns dictionary;
>	/* return a copy of dictionary with entry added to it */
>
>This is very costly, however....
>Is there some way to have a language with no side effects, yet still be
>able to solve this class of problems in a practical way?...

There are ways to design data structures such that your function
doesn't really copy the entire dictionary.  The most common method is
probably this:

Assume the dictionary is represented by a reference block:

struct rblock {        /* reference block for a hashtable */
  ...
  struct hashtable *t; /* a hash table containing the entries */
  struct rblock *p     /* the updated version of this hash table */
  struct backup *b;    /* a description of what was changed to make this
                        * table outdated, NULL means this table is current */
  }

struct rblock *dictionary_add_internal(old_dict, entry)
{
  old_dict->p = /* a way to reverse the change that is about to be made */
  update(old_dict->t, entry);
  new_dict = copy(old_dict);
  new_dict->p = new_dict->b = NULL;
  return new_dict;
}

Obviously a reference to an entry now has to make sure that the rblock
is current, and if not, then it has to follow the chain of updated
entries -- keeping track of significant updates -- to the current
table.   Also obviously, this still uses more storage than a
non-applicative dictionary would need, but you don't have to copy the
whole table, and unneeded rblocks can usually be garbage-collected.

Alternatively, you can write a smart compiler that recognizes if the
program never references the old dictionary again -- a very common
case, and usually possible for a compiler to recognize.  Then you can
usually avoid all the busy-work and just update the dictionary in
place.  There is a very large body of literature on this subject, in
addition to papers on implementation of functional languages, you
might look for references to "applicative" languages and data
structures.
-- 
					David Gudeman
Department of Computer Science
The University of Arizona        gudeman@arizona.edu
Tucson, AZ 85721                 {allegra,cmcl2,ihnp4,noao}!arizona!gudeman