HELP NEWANYPROPERTY John Williams Jan 1985
Mark Rubinstein Jun 1985
A.Sloman Oct 1986
Adrian Howard Mar 1992
newanyproperty(LIST, SIZE, EXPANSION_FACTOR, EXPANSION_THRESHOLD,
HASHING_PROCEDURE, EQUALITY_PROCEDURE, GC_TYPE,
DEFAULT_VALUE, DEFAULT_PROCEDURE) -> PROPERTY;
CONTENTS - (Use <ENTER> g to access desired section)
-- Introduction
-- LIST [a list]
-- SIZE [integer]
-- EXPANSION_FACTOR [integer or false]
-- EXPANSION_THRESHOLD [integer or false]
-- HASHING_PROCEDURE [procedure or false]
-- EQUALITY_PROCEDURE [procedure or false]
-- GC_TYPE [word]
-- DEFAULT_VALUE
-- DEFAULT_PROCEDURE [procedure or false]
-- Using Complex Keys
-- See Also:-- Introduction -------------------------------------------------------
A POPLOG property is a procedure that efficiently maps items of data,
called "keys", to other items, called "values".
Each property contains a table of "entries", each of which associates a
particular "key" with a particular "value". POP-11 provides two
procedures for creating properties: -newproperty-, which deals with
simple cases using a default mapping rule, and -newanyproperty- offering
more flexibility.
The procedure -newanyproperty- takes various arguments (described below)
and returns a property, that is a procedure that takes one argument, a
key item, and looks up its associated value. The updater of this
procedure can add or delete entries to or from the property.
Information retrieval from properties is usually considerably faster
than from functionally similar structures such as association-lists (see
HELP *ASSOC). This is because, given a key item to locate, properties
use a "hashing procedure" to compute the location of the relevant entry.
Hashing procedures usually use some invariant feature of the key object
to calculate a number that (appropriately scaled) indicates the position
in the property of an entry with that key item. If the hashing
procedure produces a wide variety of results for different key items,
most entries are stored in unique locations, and thus very little
"blind" searching is needed when entries are retrieved.
The arguments taken by -newanyproperty- are described below.
-- LIST [a list] ------------------------------------------------------
This is a list of initial key/value associations, as with -newproperty-.
For example:
newanyproperty([[one 1] [two 2] [three 3]], ....) -> prop;
creates a property, prop, that maps the word "one" to the number 1, and
so on. It is equivalent to:
newanyproperty([], ...) -> prop;
1 -> prop("one");
2 -> prop("two");
3 -> prop("three");
-- SIZE [integer] -----------------------------------------------------
This argument allows you to specify the approximate size of the property
table. The figure given (which should be a positive integer greater
than one) does not affect how many entries you can store in the table,
but can affect the speed with which they can be retrieved. In general,
the larger the property, the faster entries can be found. A rough guide
might be that properties are at their most efficient if they are about
75% full. However, if lots of properties are made with too much spare
capacity the wasted space can lead to excessive paging, slowing programs
down. So users will need to experiment to find appropriate sizes.
-- EXPANSION_FACTOR [integer or false] ---------------------------------- EXPANSION_THRESHOLD [integer or false] -----------------------------
It is not always easy to predict in advance how many entries are to be
stored in a property. In such cases, it may be better to create an
"expandable" property, which will automatically grow bigger when a
certain number of entries (the EXPANSION_THRESHOLD) has been added.
The EXPANSION_FACTOR argument (which should be a positive integer)
indicates how much bigger the property should get:
new size = old size << expansion factor
= old size * (2 ** expansion factor)
Thus an EXPANSION_FACTOR of 1 means that the property will expand to
twice its original size. If this argument is -false-, the property size
is fixed (whatever the value supplied to the EXPANSION_THRESHOLD
argument). If the EXPANSION_THRESHOLD is false then property will
first expand when SIZE items have been added to the property.
After expansion, the EXPANSION_THRESHOLD is increased in proportion to
the property's new size.
-- HASHING_PROCEDURE [procedure or false] -----------------------------
If this argument is -false-, the system default hashing procedure
-syshash- is used (this is the hashing procedure used by -newproperty-.)
HASHING_PROCEDURE should be a procedure that takes one argument and
returns one result. The result can be any POP-11 object which is then
automatically mapped into a location in the table. The simplest method
is to return an integer or a simple decimal number.
If the hashing procedure relies on the absolute address of the key item
then it is necessary to enclose the procedure as a reference, ie:
HASHING_PROCEDURE == consref(PROCEDURE)
This tells POP-11 to rehash the contents of the property after a garbage
collection.
If the hashing procedure does not return a number or simple decimal,
then it is a POP-11 data structure and its address will be used to
determine a location in the table.
NOTE: Unless the property is required to produce a random result, the
HASHING_PROCEDURE must always return an identical object for equivalent
items. For example it would be a mistake for the procedure to return a
string unless it is always the same identical string.
-- EQUALITY_PROCEDURE [procedure or false] ----------------------------
This procedure is used to check that a given key item matches the key
item in the table.
The default procedure, used if the argument is -false- is the identity
matcher "==". This is the equality procedure used by -newproperty-. For
implementation reasons it is not possible to specify an
EQUALITY_PROCEDURE if no HASHING_PROCEDURE has been specified.
-- GC_TYPE [word] -----------------------------------------------------
This controls whether an association is removed from the table if either
the key item or the value or both would be garbage collected but for the
fact that they are in the table. Possible values for GC_TYPE are
explained in REF *PROPS.
The two most commonly used values are "perm" meaning the items remain
there permanently unless explicitly removed from the table, and
"tmparg", which means the association is removed from the table if ever
the key item (or argument) would have been garbage collected but for
being in the table. In the first case it is a "permanent" property, in
the second case a "temporary" property.
If a property is "permanent", then an item/value pair in it will remain
forever even if the user has lost all pointers to the item. If this
occurs the only way the user can get at the item/value pair is by using
-appproperty-.
-- DEFAULT_VALUE -------------------------------------------------------- DEFAULT_PROCEDURE [procedure or false] -----------------------------
If an entry cannot be found for a key item when looking up the property
table, then if the DEFAULT_PROCEDURE is false the DEFAULT_VALUE, which
can be any POP-11 item, is returned. If however the DEFAULT_PROCEDURE
is a procedure then it is applied to the key item item and the property
and the result returned.
On updating an entry in a property, if you update a key item with the
DEFAULT_VALUE then the effect is to remove the key item and its value
from the property table, regardless of the value of DEFAULT_PROCEDURE.
For example:
define nochange(key, prop);
key;
enddefine;
;;; a property which returns the key item if no other value is found
vars alter =
newanyproperty(
[[foo baz]], 5, 2, 5, false, false, "perm", "gone", nochange
);
alter("foo") =>
** baz
alter("other") =>
** other
"gone" -> alter("foo");
alter("foo") =>
** foo
;;; a property which mishaps if the key item is not found in the
;;; table.
vars must_be_present =
newanyproperty(
[[one 1][two 2]], 5, 2, 5,
false, false, "perm",
false,
procedure(key, prop);
mishap('vital data not present', [^key])
endprocedure
);
must_be_present("one") =>
** 1
must_be_present("three") =>
;;; MISHAP - vital data not present
;;; INVOLVING: three
;;; DOING : compile nextitem compile
-- Using Complex Keys -------------------------------------------------
The procedure -newanyproperty- can be used to create a property that
maps a collection of items into a value. An algorithm, supplied by the
user, is needed that maps each collection onto a unique object, which
can then be used to find an address in the table. The object could most
conveniently be a number, reducing the need for re-hashing.
For example, the following procedure takes a list of words, and maps
them into a number, using the positions and first characters of the
words:
define hash_words(wordlist)-> num;
lvars word, num=0, position=1, wordlist;
for word in wordlist do
subscrw(1,word) fi_<< position fi_+ num -> num;
position fi_+ 1 -> position;
endfor;
enddefine;
See REF *FASTPROCS For information on the 'fast integer' procedures
-fi_<<- etc.
To ensure proper equality testing we have to use "=" rather than "==".
vars procedure job=
newanyproperty(
[[[joe bloggs] teacher] [[fred smith] dustman]], 99, 1,
false, hash_words, nonop =, "perm",
undef,false
);
job([joe bloggs])=>
** teacher
job([fred smith])=>
** dustman
That would not have worked with -newproperty-, since the list now given
as argument is not the original list.
job([jerry black])=>
** undef
"programmer" -> job([jerry black]);
job([jerry black])=>
** programmer
For properties keyed by more varied and complex structures -syshash- is
more useful. It makes use of the -class_hash- facility, see HELP
*SYSHASH for more details.
-- See Also: ----------------------------------------------------------
HELP *PROPERTIES --- Summary of property related procedures
HELP *NEWPROPERTY --- Simple interface to -newanyproperty-
HELP *NEWSPARSE --- Using properties to implement N dimensional
*NEWANYSPARSE sparse arrays with non-numeric subscripts
HELP *VIEWS --- Demo application using properties
REF *PROPS --- Full information on properties in POP-11
REF *APPPROPERTY --- Applying a procedure to every element of a
property
REF *CLEARPROPERTY --- Removing all entries from a property
HELP *DATALIST --- Listing all the elements of a structure
HELP *DATALENGTH --- Getting the length of a structure
HELP *APPDATA --- Applying a procedure to every element of a
structure
--- C.all/help/newanyproperty
--- Copyright University of Sussex 1992. All rights reserved. ----------