[Lecture Notes by Prof Yuen and possibly others 2000-2001]


A SKETCH OF THE HISTORICAL DEVELOPMENT OF COMPUTER SCIENCE
----------------------------------------------------------

Computers are tools for information processing. Like other tools, they are
used by humans to turn ideas into actions, but the ideas and the actions
are for information processing purposes. For all the great changes that
have happened to computers and computer science, the fundamental position
has stayed the same. We have simply succeeded in implementing more ideas,
and more complex ones, in comparison with what computers initially were
made to do. In order to achieve this increase in complexity, the whole
subject of Computer Science had to be developed.

The Havard Mark 1 and the Hollerith cardsorting machine were the early
information processing machines. The former performed numerical computation
for ballistic applications. The problems involved quite complex but
repetitive computations with a small number of numerical input and a small
number of output. In contrast, the census application of the Hollerith
machine involved large amounts of data, using punched cards both as the
data storage medium and the processed data stream: cards were sorted into
different pigeon holes depending on what values were punched onto them,
and the number of cards in each category were counted to produce
statistical computation. The main activities were rearrangement of data
rather than complex computation.

When the same methods were applied to solve other problems, the idea of
computer programming came into being: a machine can be told what to do by
setting switches, but few varieties of processing can be introduced in this
arrangement. It can also have a person sitting at it pushing bottons, but
this is slow. If instead we pre-record all the button pushes on a machine
readable medium and construct the mechanism to control the machine through
this, then the sequence of operations can be fed to the machine more
quickly.         

While this was an important fundamental idea, it did not constitute a
technological breakthrough. Such methods were already used extensively,
for example in knitting and typesetting. But the next step certainly
was. To carry out more complex computation, more data had to be stored in
the computer, and the machinery for this was accordingly constructed. Now
it was realized that, instead of the computer fetching instructions from
the input medium, the instructions could be pre-stored into the data
storage unit and fed into the computer from there. Instruction fetches now
became much faster, and complex program execution/problem solving
capabilities went up tremendously.

Further, by putting a lot of data into the storage unit, record sorting
and similar data reorganizations could be performed at high speed in the
unit. Thus, the computer was now in the position to handle both Mark 1 and
Hollerith type applications, or new problems involving a combination of
both kinds of data processing. The general purpose computer was born.      

With the machine came its "science". Early computer science contained
three main components: Numercial analysis, Logic design and Programming, a
very odd combination to today's computer science students but perfectly
understandable for that time. Non-numerical applications were so simple at
the time that there was nothing to study, but the behaviour of numerical
algorithms, given the low sampling rate and digitization precision, needed
very careful analysis, and ingenious ways were found to obtain useful
results in a manageable number of iterations.

Since programming was in machine code, binary number representations and
other hardware dependent topics were closely studied. People were
constantly tinkering with hardware to make things go faster, and given the
small instruction set, clever implementations of arithmetic and logical
operations using the simple operations available were also
important. Hence the study of logic design. Programming, on the other
hand, usually meant learning the assembly or machine language, with
various tricks on how to do this or that. The design of the machine
instruction set itself was an ad hoc business, with operations that seemed
to be useful and implementable in hardware added in as one went
along. Computer Science in those days was a gimmicky subject, a craft
with, it seemed, almost no theoretical basis except for some numerical
mathematics and Boolean algebra, an impression which persists even today
among those with a limited view of the subject.

As computers were further developed, a new bottleneck soon became
obvious: The increased capability of computers to execute complex programs
on lots of data quickly surpassed our ablility to define programs and
debug them in the machine coding notation. Thus was born Fortran and
Cobol, which have notations that are closely related to the problems
people want to solve, and hence allow people to more efficiently describe
what they want the computer to do. Making the computer do it became quite
a separate problem, through the provision of macros (a shorthand for a
sequence of instructions), compilers (translator for high level languages
into machine instructions) and subroutine libraries.

As languages proliferated, the issues of their internal logical
structures and also methods for defining and describing languages became
important. Algol, with its Backus Normal Form definition, was a landmark
development in this area. The block structure, storage allocation,
procedure linkage including recursion, and parameter passing mechanisms of
Algol implement a model of program behaviour that is still highly relevant
today, and BNF continues to be the most successful meta language for
computer language definition. (The railroad diagrams used to define Pascal
are an alternative presentation.)   

A good meta language representation is not only important for people to
know and agree on what they are defining, it can also be easily
operationalized by incorporating it into the compiler. Since the compiler
uses exactly the same description to parse the language, what the compiler
would accept is exactly what we have defined. A simple and elegant
definition automatically produces an efficient and easily verifiable
compiler. The only question one needs to ask is whether the language is
also useful and for what purpose.            
   
Mathematics aims to invent notations and concepts that are concise and
general, to decribe logical relations that are found in many seemingly
unrelated contexts. A computer language is a set of notations to describe
the information processing we wish to perform; but it is also something to
be operationalized as part of the machinery: Like buttons on the console,
each construct of the language can be invoked to cause some machine
activity. A meta language definition of a computer language is a
description of what it is; the description has to be operationalized as
part of the compiler. The compiler/interpreter for the language is itself
a description of a sequence of machine activities required to implement
the language; the description, if operationalized, produces the language
processor. Here we have a number of languages related to each other
logically and operationally, and there is need to find some uniform
techniques capable of handling all the problems together, and able to
produce languages useful for real applications.

The compiler for a language can be written in that language itself, to
describe the process of compiling it. If the language is a complex and
unsystematically defined, the description of how to compile it would be
complex; but a language with a simple and regular structure, and with
features that are well matched to the needs of compiling, will have a
simple compiler written in itself. Such a simple compiler can be manually
re-written in assembly code, and a language processor is produced. It can
immediately re-compile the compiler to produce a new, and usually better,
version of the language processor. The best example of this bootstrapping
process is Lisp, whose own syntax is simple and list-like, and therefore
readily compiled (or more often, interpreted) using the list-processing
functions available in itself. Computer Science contains many other
examples of such circular processes, because programs must be represented
and stored, and are hence subject to processing by programs including
themselves.

Yet another angle to look at computer programs needs to be taken: A
program is intended to produce certain final conditions, given certain
initial conditions. This idea gives rise to the issue of program
verification - given the description of processing steps defined in a
program, can we prove that it would indeed produce the post-conditions
from the pre-conditions? - and that of program construction - is there a
generally workable and cost-effective method whereby, given descriptions
of the intended pre-conditions and desired post conditions, the processing
steps in between can be derived? Given two working code components with
known pre- and post-conditions, what is the behaviour of some combination
of the two? Further following upon the idea comes again the issue of
notation: in certain programming notations the above requirements cannot
be met, and therefore such notations may be regarded as bad.

Algol was never a practical language because its designers failed to
incorporate the main lesson of Cobol: that the description of data,
including in particular records and files, are as important as the
description of algorithms themselves. The attempt to remedy the situation
with Algol 68 was a botched up effort (just as Fortran 77 failed though
not so badly). However, the simpler and neater Pascal succeeded as an
instructional language, for teaching concepts of both algorithms and data
structures. By learning only the small number of constructs provided in
the language definition, one can already think very systematically about
general program and data structuring issues. Though Pascal was popular for
a period because of its availability (with Basic) on early microcomputers,
it did not succeed as a practical language because of poor numerical
computation and file processing facilities, despite attempts to extend it.

With programming languages came the environments in which they can be used.
Editors to input and change programs, online file systems to store them,
and interactive execution systems to test compile and execute them are all
needed. All these have to be integrated together into an operating system.
Communication between users and user programs with the operating system
became another topic for study. On large and expensive machines, operating
systems also have the job of maintaining a mix of concurrent execution
activities such that all the resources of the machine, CPU, memory and I/O
channels/devices, are maximally utilized. Sharing resources across
concurrent execution activities turns out to contain extremely difficult
theoretical as well as practical problems. Languages for defining complex
but reliable operating systems became yet another important topic. 

As circuit density goes higher, the internal structure of integrated circuit
components went beyond the realm of interest of computer science, which had
to busy itself just with the intervening layers, including the interface
between the hardware and the software, which is studied as the subject of
Computer Architecture. The machine instruction set and the CPU, memory
and I/O structure of a computer can be designed to support particular
operations that are important to operating systems or high level
languages, and parallel processing techniques are adopted to increase
machine throughput and make very large problems solvable in real time. New
forms of hardware in turn require redesigned algorithms to effectively
utilize its capabilities, and languages to describe operations on these
machines. Networking and distributed processing produce yet other problems
for study.

With better tools came greater ambition. People began to apply computers to
even more complex applications. This first encountered the problem of data
explosion: As organizations computerize all kinds of records and put them
on line to permit high speed retrievals and applications involving
multiple uses of the same data, and cross-interaction between different
data files, all kinds of trouble and strange results arose. A systematic
theoretical approach to databases resolved most of these 
difficulties. Then came the program explosion: programs became so complex
that nobody could understand them and maintenance became very labour
intensive and expensive. Some attempts to control the complexity by higher
levels of abstraction, enforcement of standards and methodologies, and
application of AI techniques, are not yet wholly successful.

There is as yet no agreed philosophy on further abstraction. The use of
pre-define program modules, which can be strung together to make a new
application program in accordance with a program generator specification
(fourth generation language program), while widely used, is actually a
bottom-up approach to program definition and not fully compatible with
top-down design methods. Declarative languages do away with any
specification of algorithms and processing steps, and provide only a
desciption of the desired final state (usually in terms of logical
relations between data entities) so that program definition is a simpler
and more reliable job, but there is no general technique to convert such
programs into efficiently executable machine code so that the desired
state can indeed be reached.

Functional languages, by defining execution in terms of sequences of
function calls, have notations which reduce our ability to define
intermediary data and produce side effects, hence eliminate many of the
obscuring effects of procedural programming. Object oriented languages, by
defining execution in terms of messages passed between interacting
objects, have a similar effect. However, the currently available
functional or object oriented systems are still highly restricted in their
notational and data structuring facilities, though this need not indicate
lack of such capability in general.

While Artificial intelligence, Automata theory and Computational complexity
look very "scientific", they are in fact not well integrated into Computer
Science, because they have quite independent systems of notations and
concepts from those needed in the mainstream problem of defining and
implementing computers, languages, operating systems, databases, programs,
etc., in a way that is logically consistent, operationally efficient, and
practically usable by the people who need them. In this sense they are in
fact closely analogous to Numercial analysis. A better integration will be
achieved only if notations and concepts they developed for their own
purpose also turn out to have general applicability elsewhere. 

So we have had progress. Can we say more about how progress takes place?
Advances are made when new methods or better hardware are used to
operationalize concepts which were previously not practical, or new ideas
are invented to conceptualize operations which previously looked
unsystematic or unrelated. These two directions of change stimulate each
other. Once something has been operationalized and becomes widely used,
certain problems tend to arise which initially look confusing and
difficult to solve, with piecemeal local solutions being adopted to cope
with them. But as experience is gained and analysed, common ideas to
improve things are identified. These then become widely adopted in various
operationalized forms, to produce an improvement everywhere and allow
everyone to move on to enter a new cycle of operationalization and
conceptualization.

For example, after everyone has written a lot of assembly code, someone
starts to use macro definitions and macro libraries on his machine. People
elsewhere soon realizes that they too can adopt the method on their
machines despite differences in hardware, language and applications, and
with more macro libraries around, people would start to invent methods to
re-use other people's macros. In due course, someone invents the idea of
restricting programming in certain contexts to only a set of pre-defined
macros; in other words, high level language programming. Others then
realize that they can adopt the same macros on their machines, and a
portable high level language comes into being. A large number of packages
are soon written, requiring methods to share and maintain the
libraries. As bigger high level programs are produced, new methodologies
to control complexity and efficiently perform operations not well
supported in the language also became necessary. 

To progress, a computer scientist must be constantly aware of this
continuing cycle of operationalization and conceptualization. While
complexity of keeping abreast of everything is likely to be too great, it
too can be controlled by applying the right methodology. Awareness of the
need to operationalize controls the scope of conceptualization as well as
forces new concepts to be related to existing ones because of physical as
well as logical considerations; awareness of the need to conceptualize
restraints practioners from engaging in too difficult and not yet fully
understood activities. From this both sides will benefit.