FOM: organizing; Boolean rings; signature

[Peter White]

Pratt writes:

> The fact that such an abstract presentation is preferred over the
> traditional term-based approach in some areas of hardware and software
> demonstrates that the term-based approach is not essential for effective
> presentations.
> 
> In fact abstractness helps, permitting more efficient presentations.
> You only need 4 bits to represent all sixteen binary Boolean operations,
> and 8 for the ternary ones, the information-theoretic minimum.  With the
> less abstract approach of building up formulas from the "canonical"
> Boolean signature AND/OR/NOT, the existence of multiple representations
> of binary operations like IMP (as either NOT A OR B, or NOT(A AND NOT
> B), etc.) and EQV guarantees that the information-theoretically minimal
> presentation cannot be achieved with the traditional signature-based
> presentation of Boolean operations.
> 
> Bottom line: When optimizing the representation of Boolean terms, it
> helps to keep the theory in mind.  These optimizations are not available
> for terms considered in isolation from their associated theory.
> 

I would like to agree with Pratt.
I have a similar experience in my applications of mathematical specifications
to software and combined software / hardware problems. It used to seem
paradoxical at first, but now it seems natural that the more abstract
the specification, the more useful it was to us. The most important
property we had to capture was "separation", which means we wanted
to be able to construct different processes that have no capability
to interfere with each other; operations by one are in no way detectable
by another. Having captured this property very abstractly, we are now
able to apply the same property to many different systems, and compose
these systems in a way that yields still more systems with useful
separation properties. To implement differents systems exhibiting
separation, the specifications are transformed (in a very category
theoretic way) into implementations.

This has a bearing on the set theory / category theory foundations
question. In my practice, I came to understand that if I let the
concept of "set", and in particular the concept of "element", creep
into the highest level specifications, then I was doing it wrong.
The reason it was wrong is that the sets and elements really represent
something about the implementation of the system, and not about the
essential properties of the system. When I got into sets and elements
I was worrying about data structures, and the many ways to represents
sets of things with appropriately defined operations upon them.
I viewed "Set" as another specification, another tool in the toolkit,
to be used in implementing abstractions.

In anticipation of the question "What prevents you from specifying
complete nonsense in the higher level specifications", the answer
is nothing prevents you from doing so. HOWEVER, you will not be
able to transform such a nonsensical specification into the bottom
level constructs such as array, list, and integer, in a way that
provably preserves the nonsensical properties you specified at the
higher level.

Peter White, Motorola