Version 0.10 Last updated 2002-02-25-23:37 -0800 (pst)
This is a piece of an exploration that has been broken into components.
R010101: Do Programs Teach Algorithms?
Miser Note N010201: Manifest Abstractions
Miser Note N010202: Homage to the Bit
Miser Note N010204: Framework Versus Structure
Miser Note N010205: Programs Are Rarely Algorithms
Summary
References
Say something
Say something more.
We point out that we are talking about a computational mechanism that is organized in such a way that behavior is delivered as if an abstraction is actually present. However, all we have is behavior that can be so interpreted.
How the behavior is elicited is through programs -- via formal expression, and we will adopt a notation that is intended to support that.
So we have two levels of framework already:
whatever the supporting machinery of the computational mechanism is that allows us to introduce these programs and have them operate in a way that allows us our interpretation, or that validly admits that interpretation.
The formal expression by which we state to the mechanism the behavior we want.
Then there is the additional fact that we are talking about (1-2) here, and we are using a formal expression to do it.
ADAPT THIS MATERIAL:
Point out that we pretty much always say more than is essential. And it is still important to have a form of expression that has it be understood that the algorithm is definitely and always more abstract than the implementation.
Every expression of an algorithm has baggage. This includes assumptions about the existence of orderings, the assumption of 0-origin indexing, the use of natural numbers for indexes, and the stability of the objects involved. That the algorithm is effectively carried out atomically, while itself being composed of definite steps, is a key assumption in almost all expression of algorithms. This is part of the framework.
Then there is the simple use of ordinary language along with borrowing of mathematical objects and notations, all more framework for expressing algorithms.
The value of using ordinary language and distinct notations from that for program code must not be underestimated. It gives us a way of distinguishing the two, and of being able to establish what is essential and what is incidental (but perhaps inescapable baggage) of the given implementation. We can also begin to separate the baggage of the algorithmic framework and the baggage of the implementation system.
It is important that we appreciate the value of having more than one perspective on this. It gives us a place to separate problem from solution, and be clear which is a statement of what. the algorithm-implementation separation contributes to the separation of the abstraction from the statements of it.
ADAPT THIS MATERIAL: Consider that the level of abstraction for statements of algorithms might need to be improved.
One way is to notice that the objects appealed to in the statement of the algorithm might be at the wrong level. A large part of the baggage in our example is related to the level at which we deal with ordered lists via indexes. There might be a way to change the level such that we address lists in other terms that are somehow liberated from the baggage about indexes and their origins. It might be a quite different algorithm, assuming quite different basic operations, and we won't go there.
Another approach is to make reliance on abstract elements explicit rather than tacit. What we might get to is a form of expression of algorithms that can be taken as concrete, given a representation of the abstract elements.We are always going to have algorithmic baggage. Can we arrange baggage in such a way that the baggage is understandable and the abstracted algorithm is pretty clear? We take a look at a toy case using an abstract structure for the bit.
This might be better described as manifesting abstractions. That is, we want to make the subject-matter of the algorithm, the structures that are understood, explicitly abstracted so that we can see what the dependencies are. To do this, we still need a framework, but one that makes explicit that which was originally tacit. (2001-02-20)Add the definition of manifest and manifestation that matters to us here.
The bit abstraction began as an exercise early in the original Miser Project when I began to look at how to abstract out data types from algorithms, and look at the kind of automatic program transformations that become available as a consequence. The title for this is Homage to the Bit, and I fancy publishing it in BIT, on some anniversary occasion. Here is a sketch, with the full treatment better done in its own paper. I will put enough in this article to expand on the problem of baggage and what one must deal with to "deliver abstractions" into the concrete world of a programming system.
1. Consider that we arrange a way for data types to always be typical of their class. We won't expand on that here, just introduce it as the adopted approach. We want to introduce concrete data types that have certain qualities that preserve abstractness in some useful and extremely practical sense. In particular, the implementations are fully substitutable, and this can be done selectively and anywhere in a computational method. We illustrate this idea by presenting a "concrete abstraction" for one of the most fundamental data types of all, the binary bit.
2. For example, whenb
is an01bit
(read "oh-one-bit") thenb.0
is the 0-bit andb.1
is the 1-bit. If we have an01bit
, we can get any01bit
we want. Every instance is typical of the class.
3. Notice how much framework we are heaping on this very simple notational invention. I mean some01bit
,b
, and I specify features of01bit
s by using the.
-notation. That is, the0
feature,b.0
, is the 0-bit of01bit
s, and the1
feature,b.1
, is the 1-bit of01bit
s.
4. Don't worry about this too much. This is not an ordinary way of speaking, and the notation is used in a critical way. Just look and notice how we are using ordinary language to talk about a concrete (implemented) thing, and what it takes for us to be rigorous in doing that. Also notice that almost everything is in our (framework) language. What makes these concrete abstractions, in our way of speaking here, is that we have a rigorous (formal) framework language that allows us to say all there is that can be discerned about some things. They have some concrete existence, lets suppose, but we are only able to "see" them as if there is an actual abstraction there. That is, the framework guarantees that we don't get to see (in the framework context) anything more than the abstraction. Now, notice how this is not entirely true. For one thing, the idea of bits is extremely simple. What we have here is a pretty elaborate framework so we can talk about them as if they are something that can be talked about! Basically,01bit
s are concrete abstractions that have two distinct individuals. The one we call the 0-bit is designated01bit.0
. The one we call the 1-bit is designated01bit.1
. And the way that we have of telling whether the one we have in hand,b
, is the 0-bit or not is by the designationb.is-0
. Notice that almost everything in the framework is about how we are going to designate individuals and tell which one is at hand, so to speak. Our biggest job is agreement on language and terminology. (2001-02-21)
5. Even at this point, you don't have any assurance that01bit
s have anything to do with our everyday notion of bits other than I have said so. That is, there are 0-bits, 1-bits, and they are different. That's about all there is to bits. It doesn't even matter how I pick one01bit
individual to be the 0-bit and the other to be the 1-bit, so long as I keep it all straight. This is important: there are syntactic features that allow us to converse about bits and think we know what we are talking about. It happens that the choice of feature is arbitrary, although it must be fixed. (The notion of the dual of Boolean algebras lurks in here. We'll not go into that here.)
6. I am saying that to come up with a concrete abstraction, we need to fix the features and their expression. The labels don't matter, the discrimination among the features and any specific behavioral conditions are what matter. So much baggage. So few bits.
7. When we have an01bit
, how do we know which bit we have? We have to take a position about that to be able to operate with these objects. We could take a common approach and introduce a proposition that applies to all bits:b.is-0
. The framework assumption here is that we have some notion of truth or, at the very least, are able to deal conditionally with the answers to questions. This is pretty fundamental for algorithmic frameworks, so we'll go withb.is-0
.
8. There is a metaquestion here too. How do I know that I have an01bit
at hand? Hold that thought. (2001-02-20)
9.b.is-0
works for01bit
s because in our ordinary notion of binary bits, a given bit is either the 0-bit or it isn't, and if it isn't it must be the 1-bit. The use of a specific proposition is a little inconvenient when generalizing to more-interesting finite sets, and we will ultimately prefer to introduce some equality determination for members of abstractions like01bit
s. Either way, we are making even more framework assumptions. For now,b.is-0
works just dandy.Now, if I presented you with a programming system's fixed data type,
01bit
, and said these are (representations of) the binary bits and here's a notation for specifying them and examining them, I wouldn't have done much.
1. I would have presented you with an implementation that has an intended interpretation as binary bits. It might even have the intended pragmatic interpretation of corresponding to the binary bits of an underlying computational mechanism with the assurance that these bits correspond to the bits in the memory system of that mechanism.
2. I want to do something different than that. The01bit
s are intended to be concrete abstractions, and we don't want to lose the abstractness of it. There might be some flavor of01bit
that has all of that connection to a predictable and known implementation. But that is not to be assumed of01bit
s generally.
3. Here is a Python-flavored function using01bit
s:
def 01and(a: 01bit, b:
01bit
)
01bit
:
Although I would never expect to be able to say this in Python (it not being in the spirit of the language), I am using this form for contrast and to have an existing framework. This is also an imperfect model, so take it as merely exemplary.
if a.is-0:
return a
else:
return b
4. What I want to suggest is programming-system machinery where the01and
function is understood as the expression of an algorithm as much as that is possible in a concrete programming system. In particular, this definition does not depend on a fixed sense of01bit
, but simply requires delivery of01bit
s -- parameters that have the features of01bit
s and that satisfy whatever conditions exist for a concrete flavor to satisfy the abstraction.
5. It might be more general to suggest the following notation, not unlike the template notion of some languages:
def 01and(bit: 01bit)(a: bit, b:
bit
)
bit
:
This might provide a stronger sense of what is intended. I am concerned that this implies too much and I am not wedded to this approach. So far.
if a.is-0:
return a
else:
return b
6. I haven't said how one defines01bit
in this kind of system. I'm not prepared to make a commitment to that, which is my nice way of saying I haven't figured it out yet.
7. What you can count on is that if any a and b are supplied that do not satisfy the conditions for the concrete abstraction, bit, then the function fails. It doesn't return a result, it fails. Furthermore, if the implementation of the function returns a result, it is assured to satisfy the concrete abstraction, bit.
8. Given this function,01and
, assume that the programming system allows ways that one can cast an existing object that has the necessary qualities of a bit as an01bit
. That is, one does not have to be content with arranging things to be01bit
s before they are useable in operations defined on01bit
s. We could instead define an01bit
over some other type, lets sayBoolean
, in which we specify how the features of an01bit
are derived from the features of aBoolean
. This gives an interpretation of aBoolean
as an01bit
. Generally, there are many ways to do this, so we might want to name particular interpretations or use a descriptive notation in which we show the particular interpretation. Suppose we use the nameBoolean01bit
for the interpretation that hastrue
be the 1-bit andfalse
be the 0-bit. ThenBoolean01bit(Boolean.true)
is01bit.1
. (2001-02-20)
9. There's something I want to add here, but I have forgotten it for the moment. It is about how all we are talking about is the features of some hidden thing, a concrete thing that we only want to see in accordance with an abstraction that it supports. We are, let us say, using these concrete abstractions as attributive views onto something. The something is the concrete part. The abstraction is what we have when we only allow those particular attributions to be seen as the features. The validity of the concrete abstraction is that its behavior never contradicts the abstraction. In computing terms, we would talk about hiding an implementation. In logic, we would say that we have a valid interpretation of the abstraction. (2001-02-21)
10. There can be ways to cast values from01bit
toBoolean
, and this means that the result of01and
can be made into aBoolean
without much difficulty. For example,01bitBoolean(01bit.1)
could beBoolean.true
.
11. I am messing with the typography here. I am not quite prepared to concede thatBoolean01bit
and01bitBoolean
are regular functions (with regard to whatever functions are in the framework), so I have used special typograhy in their names.
12. It can appear, at this point, that we haven't done anything. That is, We have made explicit a way to use01bit
s asBoolean
s andBoolean
s as01bit
s. Aren't we just stating the obvious? Exactly so. We have made explicit what, in some frameworks, is not only taken as tacit, but it might not even be recognized that such is being done -- that there is any other way to look at it. Until I told you that the definitions ofBoolean01bit
and01bitBoolean
were the obvious ones, I say it wasn't obvious yet. One could jump to those conclusions, but there is no basis in anything said up to this point. (2001-02-20)
13. Here's the next piece of information. All there is to know about01bit
s is what you've been told here. That is, the only known features are01bit.0
,01bit.1
, and01bit.is-0
. All that is implied forBoolean
s, so far, is that there areBoolean.true
andBoolean.false
. One might suppose that there is also aBoolean.is-false
, in which case our suspicions about there being no difference here, other than a choice of labels, are difficult to resist. However, that there is such a prospect is different than it being so. And we have not said whether there are only these features ofBoolean
s. In fact, I assert that there is noBoolean.is-false
as part of the definition forBoolean
s. There is, however, aBoolean.is-true
. (Notice that we still haven't said what kind of object is determined by the01bit
.is-0 andBoolean
.is-true features.) (2001-02-20)
14. Here's a little more. LetN
be a concrete abstraction for the natural numbers (or at least the Peano numbers). FeatureN.0
is the zero or origin of the naturals,N
.s
is the successor of whatever natural number that anN
represents, andN
.p
is the predecessor of whatever natural number anN
represents. It happens thatN.0.p
is alwaysN.0
in this formulation. Finally,N.is-0
is defined analogously to01bit.is-0
. That is all there is to know aboutN
's. It is useful to introduceBooleanN
so thatBooleanN(N.0)
isBoolean.false
andBooleanN(N.s)
isBoolean.true
. Likewise,NBoolean(Boolean.false)
isN.0
andNBoolean(Boolean.true)
isN.0.s
. (2001-02-20)1. It may seem that
Boolean
s and01bit
s are not much different and they could be defined to be the same or equivalent in some way. While it might be useful to do that, I am intentionally avoiding doing so here. Where we to do that, there is still no such obvious equivalence betweenBoolean
s andN
's, even though the interpretationsBooleanN
andNBoolean
are very useful in practice (and are tacitly employed in the C programming language and its relatives.)
2. I am going to make a framework commitment now. Suppose that features01bit.is-0
,Boolean.is-true
, andN.is-0
are allBoolean
s. I immediately no longer requireBoolean.is-true
and one might plausibly claim thatBoolean
s are now more primitive and essential than01bit
s. The algorithmic framework inherently depends onBoolean
s. It is what we use to be specific about having the answer to a question and being able to operate conditionally with that answer.
3. One can argue that ensnarling the framework with a commitment to a particular concrete abstraction for choice is unnecessary and also inconsistent with the idea of carefully managing the choice of abstractions. It is the case that the statement of algorithms depends almost always on having a way to distinguish particular objects and vary the progression of operations based on that. But this need not be the best way to deal with it. That is not important for this discussion. The point here is how things can fall into place when one makes such a commitment. It is also the case that there is an underlying commitment that becomes invisible while shaping the statement of algorithms. (2001-02-20)
4. In thinking about whether we collapse the truth system of the framework withBoolean
or not, I realize there is a similar concern with regard to explicit identity. I defined these concrete abstractions using is- features, avoiding having an explicit identity (and the messiness of binary operations, which I didn't want to drag in). On the other hand, natural formulations of axiomatic theories for structuresBoolean
,01bit
, andN
, all appeal to some identity function. I could look to see how to avoid use of identity there, but I don't see how to avoid it, especially forN
. I am becoming more inclined not to collapse any framework structure with these (supposedly) concrete structures. I will also have to cure myself of the idea of concrete abstractions, finding better terminology. (2001-02-21)
Cross-reference the kindred notes as appropriate. Also to notational conventions.
Also consider George Mealy's paper on "Notions" and anything else that suggests what is useful here.
Russell's discussion of attributive sets, rather than extensional ones might be useful too.
We can also contrast this kind of idealism with Platonism and even neo-Platonism if we want, but probably not here.
- 0.10 2001-03-10 Make Separate Sketch for Exploration (orcmid)
- Initial exploration of this topic began in an exploratory note that needed to be broken apart so that I could complete a simple argument that programs are insufficient for instilling an understanding of algorithms.
created 2001-03-10-08:12 -0800 (pst) by orcmid
$$Author: Orcmid $
$$Date: 04-01-06 13:03 $
$$Revision: 5 $