Programming - model the (wanted) programmed computer's behavior (descriptive/prescriptive)
[cf. paradigms]
|
(a) Concrete model.
An unusual way of describing what a computer does or should do is through a concrete model:
Emulation: "I want a clone of that other (programmed) computer".
Replication: "I want a computer operationally equivalent to that other one".
Simulation: "I want a computer simulating the input-output behavior of that one".
(b) Abstract model.
Typical model descriptions are used.
«Software ... is merely a more or less accurate theory of the workings of a hardware system,
a computer. It is at least a correct predictive theory (predicting the correct output
given the input), but it may not be a very good explanatory theory
(that is, a theory which is strong than extensional equivalence,
one that explains something about how the output it reached).
The accuracy of software in a traditional computer system
as a theory of the states through which the system passes
depends on the compilation ... and execution of the result»
[AAI:80, underlining added].
«We can view a program two ways.
1. A program is a description of a set of actions
that we want a computer to carry out. ... [=> glas box view]
2. A program is a model of some process in the real or mathematical world
[not a model of what the real computer does].
... [=> gray box view]
These two world-views are analogous to the way a builder
and an architect view a house.
The builder is concerned with the method for achieving a finished house. ...
The architect is concerned with the overall function and form of the house
...
A "builder's language" allows to prescribe how to do something.
An "architect's language" deals with abstractions
to express models of objects and processes»
[TAPL 15f].
| |
Programming on a physical theory of computation:
| |
Programming in various models of computation
(in aworld of software objects)
| |
Programming with no theory/model of computation:
|
Physical programming:
| |
Computer (glas-box) programming:
| |
Model-based (grey-box) programming:
| |
Declarative (black-box) programming:
|
Specify in physical terms
| |
Specify how the computer should compute
At different levels of abstraction:
real memory
-> virtual memory
-> flat store
-> structured store
bit patterns
-> integers/floats (ie. machine-lang. supported values)
-> primitive values (of prog. lang.)
-> abstract values (incl. user defined)
micro instructions
-> machine instructions
-> HLPL statements
-> structured control constructs
|
Specify an input-output relation by describing one way how it could be computed
| |
Specify an input-output relation for the entire program
without use of a model of computation,
without hypothesizing internal states, steps, components.
(This is easier said than done:
any closed formula result = F(x,y)
contains subterms corresponding ot intermediate steps in the compuation)
|
(b1) descriptions for humans
|
| |
(a) i.e., a way in terms of abstractions of how computers work:
| |
(b) in terms of a model of computation (MOC)
not derived from the computer by abstraction:
|
|
Specification of direct physical manipulation:
rewiring and setting-of-switches
(eg. programming of the ENIAC 1944)
|
| |
| |
Model-based spec.
of entire program
|
Modural specifications
(trace, algebraic, model-based)
|
| |
Trace specification
of entire program
|
Algebraic specification
of entire program
|
| |
(b2) code = can be loaded on computer to program it
«Programming languages ... can be instantiated in arbitrary many physical ways.
Any attempt to characterise the behavior of the programs at the physical level
is doomed, Fodor and Pylyshyn claim» [AAI:20].
| |
Algorithmic code
| |
open formula:
|
Logic code
relational logic
constraint-logic
|
partial list of input:output pairs
(to be inter- and extrapolated) used in
|
Low-level programming in the imperative model:
micro code
machine code
assembly code
|
High-level programming in the imperative model:
imperative, procedural, structured
|
In the applicative model:
monadic-style functional code
|
| |
<---|
inductive translation
| |
|--->
through optimizer
(reordering, unrolling, inlining, pre- evaluation, ...)
| |
|
In the applicative model:
Functional code
|
|
Code in the dataflow model
|
|
In the multiagent model:
Event-based code
|
|
Code in the object change propagation model
|
|
| |
|
|
|
|
In the message passing model:
Object-oriented code
with 'clients', 'servers', 'links', 'messages'
|
|
| |
| |
|
Cognitive Science - description levels of computer systems (±humans) - or - system levels
|
[AAI] C L Foster: Algorithms, Abstraction and Implementation: Levels of Detail in Cognitive Science; Academic Press 1992.
«In cognitive psychology and in computer science the notion of levels
is an important one. To speak only in terms of one level of components,
such as `memory' or `lists', rules out the possibility of further explaining
how those components are themselves structured and how their subcomponents interact.
On the other hand, to limit explanation or even description to the lowest level
(if that could be determined), say the level of physics,
would be to miss out on important generalizations.
The fundamental importance of levels is as uncontroversial as anything in cognitive science.
...
Still, the variety of levels [proposed by different authors]
is wide-ranging, and the definitions are less than precise» [AAI:31].
System level (description level) =/= level of abstraction!
«Computer systems levels are not simply levels of abstraction.
That a system has a description at a given level
does not necessarily imply it has a description at higher [system] levels.
... ([Newell 82] p. 97)» [AAI 17].
Cf. abstraction = selectively ignoring properties - always applicable.
System level =/= point of view!
«`... [C]omputer system levels ...
are a reflection of the nature of the physical world.
They are not just a point of view that exists solely in the eye of the beholder.
This reality comes from computer system levels being genuine specializations,
rather than being just abstractions that can be applied uniformely.
(Newell, 1982:98)» [AAI 15f].
They are not just points of view since they depend on technologies
(`circuit technology', `programming language technology', ...):
«Computer systems levels are realized by technologies.
... It is not possible to invent arbitary additional computer system levels
that nestle between existing levels.
Potential levels do not become technologies, just by being thought up.
Nature has a say in whether a technology can exist.
([Newell 82] p. 97 ...)» [AAI 17]
OTOH: «I don't understand what it is to say, for example, that a level
`really exists', rather than being a point of view. Usually there are
theoretical framewaorks under which we describe computational devices;
in one sense these are viewpoints, but that fact doesn't make the objects
viewed from those viewpoints any less real, or
descriptions in the viewpoints' terms any less true.»
[Smith 1986:42, quoted from AAI 32].
«Perhaps the most frequently cites theory of levels of explanation
is that of David Marr ...» [AAI:9].
And then there is
«Newell's `standard hierarchy, familiar to everyone in computer science'» [AAI 16].
But let us proceed chronologically:
|
D C Dennett: Intentional Systems; 87-106: The Journal of Philosophy 68; 1971.
|
Physical stance. Here
«predications are based on the actual physical state of the particular object
and are worked out by applying whatever knowledge we have of the laws of nature.»
«[T]he physical stance is generally reserved for instances of breakdown,
where the conditions preventing normal operation is generalized
and easily locatable...»
[Dennet 1971:222, quoted from AAI:22,23].
|
| |
|
Design stance. Here predications
«are defined as being generated by assuming each functional component
will perform as designed. The design includes the arrangement of the
functions to fulfil their pruposes. This use of `function'
highlights the purpose-relative defniition of the term, which tends to be forgotten
in computer science lingo» [AAI:23]
«[T]he design here includes the design of the particular machine» [AAI:23].
«If one knows exactly how the computer is designed
(including the impermanent part of its design: its program
[U: he must mean `machine program']), one can predict its designed response
to any move one makes by following the computation instructions of the program»
[Dennet 1971:221, quoted from AAI:23].
|
| |
|
Intentional stance. «The emphasis at the top level, or `intentional stance',
is placed on predication of output from input, without necessarily explaining
anything about how the actual mechanisms of this particular system
serve to bring about the predicted resutls or what states the system goes through»
[AAI:22].
«[In "The Intentional Stance" MIT Press 1987, Dennett]
explicitly calls the intentional stance an idealization,
such as the computational level of Marr and the notion of competence of Chomsky.
Unlike Marr, however, Dennett clearly allows for the possibility that a good
idealization may have little to do with the correct theory at a lower level:
The fact about competence models that provoked my `instrumentalism'
is that the decomposition of one's competence model into parts, phases, states,
steps, or whatever
need sheed no light at all on the decomposition of actual
mechanical parts, phases, states, or steps of the system being modelled--even
when the competence model is, as a competence model, excellent.
(pp. 76-76)» [AAI:23f]
|
|
D Marr: Artificial Intelligence - A Personal View; 37-48: Artificial Intelligence 9; 1977.
D Marr: Vision: A Computational Investigation into the Human Representation and Processing of Visual Information; W H Freeman 1982.
|
«For a system that solves an information-processing problem,
we may distinguish four important levels of description.
At the lowest, there is basic component and circuit analysis--how
do transistors, neurons, diodes, and synapses work?
The second level is that of particular mechanisms:
adders, multipliers, and memories accessed by address or by content.
The third level is that of the algorithm,
and the top level contains the theory of the overall computation»
[D Marr, T Poggio: From Understanding Computation to Understanding Neural Circuitry;
470-488: Neurosciences Research Progress Bulletin 15 1977: p. 470, quote from AAI 34].
|
|
Hardware implementation level.
«This is just the level of explanation of the physical device
in which an algorithm is implemented, be it person or computer.
... [This level] places constraints on [the repr. & algo. level],
restricting the representations and operations that can be used
at the algorithmic level»
[AAI:11].
|
| |
Representation and algorithm level.
«The distinction between process (algorithm) and representation is crucial,
and the choice of representation comes first and restricts the choice of process.»
«The representation is itself a system, much like a grammar: it is symbolic and compositional.
`A representation', as Marr (1982:20) defines it,
`is a formal system for making explicit certain entities or types of information,
together with a specification of how the system does this'.
he gives as examples number systems, such as binary and Roman numerals,
pointing out that particular representations aid of impede various operations ...» [AAI 11].
|
| |
Computational level.
There is «an element of abstraction and idealization in this level:
it is independent of any particular representation, as addition is independent
of the numeral system» [AAI:13].
This level «is critically important from an information- processing point of view."
[Marr:27] ... An information processing problem [is] one such as perception
(according to Marr), for which
"an algorithm is likely to be understood more readily by understanding
the nature of the problem being solved than by examining
the mechanism (and the hardware) in which it is embodied. (p. 27)» [AAI:14].
«While a description at the representation and algorithm level
is meant to answer the question how?,
the computational level description is intended to answer the questions
what? and why?» [AAI:11].
The «important features are
(1) that it contains separate arguments about what is computed and why and
(2) that the resulting operation is defined uniquely by the constraints it has to satisfy».
For example, the cash register's computational theory:
«If you but nothing, it should cost you nothing;
and buying nothing and something should cost the same as buying just the something»
[Marr 1982:23 and 22, quote from AAI:12].
|
|
A Newell: The Knowledge Level; 87-127 in: Artificial Intelligence 18; 1982.
|
|
|
Configuration level (processor-memory-switch level).
«`lies directly above both the symbol level and the register-transfer level' (p. 95)»
Eg. «the whole VAX with peripherals, reading in data and writing out data, is the configuration level»
| |
| |
I did not show the logic-level above the electronic circuit level, because:
«There is no way to abstract from an arbitrary electronic circuit
to obtain a logic-level system» [Newell 97, cited from AAI 17].
|
|
Logic level (medium: bits):
Register-transfer sublevel (architectural sublevel). Medium: bit vectors
| | Symbol level (program level). Medium: symbolic expressions.
It «is supposed to be at the same hight as the register-transfer level» [AAI 16].
|
The symbol level cannot be above the register-transfer level, because:
«There is no way to abstract from an arbitrary register-transfer system
to obtain a symbol-level system» [Newell 97, cited from AAI 17].
«On closer inspection, there is no clear boundary between the symbolic level and the logic level.
A description in machine language, for example, might be viewed as either» [AAI 32].
Logic level (medium: bits):
Logic circuit sublevel. Medium: single bits
|
Electronic circuit level. Medium: current and voltage (for electric circuit, but could also be fluid)
|
Device level. Medium: electrons and magnetic domains.
This level «is (p. 97) `used only to devise components at the circuit level'»
| | | | | | | | | | | | | | | | |
MODELING
CSys (where the parts are of certain materials, have different colors, etc.).
As a (non-trivial) concrete system, S has the following kinds of properties Prop(S):
[S]sys