Software engineers often face tricky problems to which they find clever
solutions. One such problem is how to implement sets, including their
commutative and idempotent properties, which run counter to the linear,
sequential organization of computer memory. A solution, going back to the
days when Lisp programmers began to explore symbolic computation, is to
represent sets as lists, with the `empty`
set as `nil` (the empty list), with
adding an element to a set as `cons`
(left juxtaposition), and with union as `append` (concatenation). Then the commutative and
idempotent laws are false - but if the programmer is careful, they
will be behaviorally true; this depends in part on a careful choice
of attributes, that is, of visible valued functions defined on sets,
and of course on writing methods that respect these attributes.
Below is an applet that illustrates how sets of natural numbers may be
implemented with lists: It starts with two sets, A and B, each the empty set,
represented as the empty list; you can add elements to either by using the
Membership is clearly the most important and characteristic attribute for
sets, and in particular, the usual axioms for mathematical set theory
A = B iff ( x) (x in A iff x in B) .Notice that this is a behavioral definition, as are also the usual
definitions of union and intersection,
( x) x in A U B iff x in A or x in B . ( x) x in A & B iff x in A and x in B .To formalize this in hidden algebra, we take the empty set to be a hidden constant, `add` to be a method, `in?` to be an attribute, and `union` and `intersection` to be methods; these last two methods
are excellent motivation for our generalization of hidden algebra to allow
non-monadic operations.
In this example, it suffices to use a special kind of coinduction called We will first show that lists implement sets behaviorally, that is, that they provide a behavioral refinement for sets, and then we will check that some familiar properties of sets (commutativity, idempotency, de Morgan, etc.) hold for our specification of sets; it is then automatic that these properties also hold for the list implementation of sets. It is interesting to notice that our behavioral specification of sets
includes not only all finite sets of natural numbers, but also all
( x) x in I = true .For example, `neg` (add(0,empty)) is the
set of all positive integers. (As an exercise, the reader might want to
consider how to represent cofinite sets as what might be called "negative
lists.")
It is also interesting to speculate about an |

To the Kumo
demos homepage. To the Tatami Project homepage. To the UCSD Meaning and Computation Group homepage. |