2021.7.21..8.19: news.adda/lang/
pioneers of the abstract data type or object-oriented modularization/
Wirth 1979`founders of abstract data type were C.A.R. Hoare, P. Brinch Hansen:
. I had recently heard prof Liskov 2013
explaining how she was the origin of the ADT
(abstract data type) back in 1971
when she was working on the Venus system;
http://amerdreamdocs.blogspot.com/2021/07/drbarbara-liskovthe-software-crisis.html
but prof Wirth 1979 claims the idea came from
C.A.R. Hoare and P. Brinch Hansen;
however, he gives no details or a date.
. about the same time that Liskov was working on Venus
David L. Parnas was mentioning "information hiding"
referring to object-oriented modules
being preferred to functional decomposition.
. here is Wirth 1979
https://link.springer.com/content/pdf/10.1007/3-540-09745-7_1.pdf
explaining the origin of
the idea of the abstract data type:
"The gradual process of disentangling
these distinct [computer science] concepts
led to one definitely remarkable discovery.
C.A.R. Hoare and P. Brinch Hansen recognised
that the association of data and procedure declaration
as embodied in the class concept in Simula
would be an ideal frame for promoting the idea of
program design with various levels of abstraction.
If the class body is regarded as an
initialization statement of local data
instead of as a coroutine,
and if the procedures are made globally accessible
instead of local to the coroutine body,
and if the associated variables are local,
i.e. hidden from the environment
of the class declaration,
then such a structure would be an ideal tool
for representing abstract objects in terms of
more concrete details.
This was the origin of the idea of
the abstract data type."
. Wirth does reference Liskov to mention
her 1978 CLU Reference Manual:
"Once postulated,
the concept of the abstract data type led to
a considerable amount of research activities.
Only a few matured into implemented systems
[Liskov's CLU,
H. Lienhard. The real-time programming language PORTAL.
R. Schild. Parallel processes in PORTAL, exemplified in a group project.
Landis & Gyr Review 25, 2, 2-16 (1978)].
. here are other early mentions of ADT...
Mathematical Foundations of Computer Science 1980
https://link.springer.com/chapter/10.1007/BFb0022497
Abstract data types: A retrospective and prospective view.
Wm. A. Wulf
"This paper presents a retrospective view of the
last decade's research in a number of related areas:
programming methodology, formal semantics,
program specification and verification,
and programming languages.
The synergistic effect of these threads of research
is especially evident in the area called
abstract data types, ..."
. I show the references of that Wulf 1980 paper,
in chronological order, that are relating ADTs to
Simula, Hoare, Wirth, and Liskov & Zilles;
also interesting are the many references to
David L. Parnas 1971..1976.
https://en.wikipedia.org/wiki/David_Parnas
. Parnas 1972's "On the Criteria to Be Used
in Decomposing Systems into Modules",
https://apps.dtic.mil/sti/pdfs/AD0773837.pdf
emphasized information hiding,
which is the key feature of the ADT:
"The major progress in the area of modular programming
has been the development of coding techniques ...
which (1) allow one module to be written with
little knowledge of the code used in another module ..."
but decomposition using "information hiding"
[as defined in Parnas 1971]
is to be preferred to functional decomposition.
Parnas 1971:
Information Distribution Aspects of Design Methodology,
Technical Report, Dept of CS, Carnegie-Mellon University.
see also:
M. Broy, E. Denert (Springer-Verlag Eds.) 2002:
Software Pioneers/David L. Parnas:
The Secret History of Information Hiding.
the references of the Wulf 1980 paper:
O.-J. Dahl. Simula 67 Common Base Language.
Norwegian Computing Center, Oslo, 1968.
David L. Parnas.
Information Distribution Aspects of Design Methodology.
Proceedings of IFIP Congress, IFIP, 1971, pp. 26–30. Booklet TA-3
C. A. R. Hoare.
“Proof of Correctness of Data Representations.”
Acta Informatica 1, 4 (1972).
David L. Parnas.
“A Technique for Software Module Specification with Examples.”
Communications of the ACM 15 (May 1972)
David L. Parnas.
“On the Criteria to be Used in Decomposing Systems into Modules.”
Communications of the ACM 15, 12 (December 1972).
C. A. R. Hoare and N. Wirth.
“An Axiomatic Definition of the Programming Language Pascal.”
Acta Informatica 2, 4 (1973).
D. L. Parnas, J. E. Shore and Elliott.
On the Need for Fewer Restrictions in Changing Compile-time Environments.
NRL Report 7847, Naval Research Lab, November, 1974
Barbara H. Liskov and Stephen N. Zilles.
“Specification Techniques for Data Abstractions.”
IEEE Transactions on Software Engineering SE-1 (March 1975).
Per Brinch Hansen.
“The Programming Language Concurrent Pascal.”
IEEE Transactions on Software Engineering SE-1 (June 1975).
https://authors.library.caltech.edu/34677/1/06312840.pdf
"A process executes a sequential program
- it is an active component.
A monitor is just a collection of procedures
that do nothing until they are called by processes
- it is a passive component.
But there are strong similarities between
a process and a monitor: both define
a data structure (private or shared)
and the meaningful operations on it. ...
It seems natural therefore to regard [both]
as abstract data types defined in terms of
the operations one can perform on them.
If a compiler can check that these operations are
the only ones carried out on the data structures,
then we may be able to build very reliable,
concurrent programs in which controlled access to
data and physical resources is guaranteed
before these programs are put into operation.
We have then to some extent solved the
resource protection problem
in the cheapest possible manner (without
hardware mechanisms and run time overhead)."
David L. Parnas.
Some Hypotheses about the “Uses” Hierarchy for Operating Systems.
Technische Hochschule Darmstadteich Informatik, 1976
A. K. Jones and B. H. Liskov.
“A Language Extension for Controlling Access to Shared Data.”
IEEE Transactions on Software Engineering SE-2, 4 (December 1976), 277–285.
Barbara Liskov, Alan Snyder, Russell Atkinson and Craig Schaffert.
“Abstraction Mechanisms in CLU.”
Communications of the ACM 20, 8 (August 1977)
Niklaus Wirth.
“Modula: A Language for Modular Programming.”
Software — Practice and Experience 7, 1 (January 1977).
B. Liskov, E. Moss, C. Schaffert, R. Scheifler and A. Snyder.
The CLU Reference Manual.
Laboratory for Comp Sci, Mass. Institute of Tech, 1978.
Computation Structures Group Memo No. 161
John V. Guttag, Ellis Horowitz and David R. Musser.
“Abstract Data Types and Software Validation.”
Communications of the ACM 21, 12 (December 1978).
. another survey of abstract data types:
ACM SIGPLAN Notices 1976
https://dl.acm.org/doi/10.1145/942574.807113
The use of abstract data types
to simplify program modifications.
Theodore A. Linden
"An abstract data type defines not only a
data representation for objects of the type
but also the set of operations that can be
performed on objects of the type.
Furthermore, the abstract data type can
protect the data representation from
direct access by other parts of the program."
. the Linden 1976 references:
Dahl, O.-J., Myhrhaug, B., and Nygaard, K.
The Simula 67 common base language,
Norwegian Computing Center, Oslo, 1968.
Liskov, B. and Zilles, S.
An approach to abstraction.
Proc. of a Symposium on Very High Level Languages,
SIGPLAN Notices, 9, 4 (April 1974).
[first seen in:
computation structures group Memo 88,
project MAC, MIT Sept 1973 ]
Brinch Hansen, P.
The Programming Language Concurrent Pascal.
IEEE Trans. of Software Engineering 1, 2 (June 1975).
Liskov, B. and Zilles, S.
Specification techniques for data abstractions.
International Conf. on Reliable Software,
SIGPLAN Notices, 10, 6, (June 1975) pp. 72-85.
from the above references I couldn't find:
( Liskov, B. and Zilles, S. April 1974:
An approach to abstraction.
) but I could find the same authors
writing the same month here:
( Barbara Liskov, Stephen Zilles April 1974
Programming with abstract data types
ACM SIGPLAN Notices
https://dl.acm.org/doi/10.1145/942572.807045
)
and
there are many papers that cite
Liskov's "An approach to abstraction":
https://scholar.google.com/scholar?cites=3833873370284844398&as_sdt=805&sciodt=0,3&hl=en
A history of CLU.
Barbara Liskov
History of programming languages January 1996,
https://dl.acm.org/doi/abs/10.1145/155360.155367
"The idea of a data abstraction has had a
significant impact on the development of
programming languages
and on programming methodology.
CLU was the first implemented programming language
to provide direct linguistic support
for data abstraction."
A survey of some issues concerning
abstract data types.
L Flon - 1974 - apps.dtic.mil
https://apps.dtic.mil/sti/pdfs/ADA004337.pdf
Towards a theory of type structure
JC Reynolds - Programming Symposium, 1974
https://link.springer.com/chapter/10.1007%2F3-540-06859-7_148
https://prl.ccs.neu.edu/img/r-cp-1974.pdf
Software engineering: Process, principles, and goals.
DT Ross, JB Goodenough, CA Irvine
Computer, 1975
https://ieeexplore.ieee.org/abstract/document/1649428/
https://www.academia.edu/download/48806359/c-m.1975.21895220160913-5432-1a4k09q.pdf
Operating system structures to support
security and reliable software.
TA Linden - ACM Computing Surveys (CSUR), 1976
https://dl.acm.org/doi/abs/10.1145/356678.356682
https://www.ojp.gov/pdffiles1/Digitization/40465NCJRS.pdf
Programming without pointer variables.
RB Kieburtz
Proceedings of the 1976 conference on Data …, 1976
https://dl.acm.org/doi/abs/10.1145/800237.807127
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.7746&rep=rep1&type=pdf
[ Liskov 2013 pointed out that CLU used pointers
despite them being seen as unsafe.]
Visibility and types.
CHA Koster
ACM SIGPLAN Notices, 1976
https://dl.acm.org/doi/abs/10.1145/942574.807136
A study of protection in programming languages.
AL Ambler, CG Hoch
ACM SIGOPS Operating Systems Review, 1977
https://dl.acm.org/doi/abs/10.1145/390018.808309
ACM LISP and functional programming August 1980
https://dl.acm.org/doi/10.1145/800087.802791
MODLISP
James H. Davenport, Richard D. Jenks
"MODLISP language differs from other
abstract data type languages such as CLU
[Liskov & Zilles, 1974; Liskov et al, 1977]
in that it allows dynamic construction of
new parameterised data types
and possesses a unified semantics covering
interpreted and compiled code,
which can call one another at will.
In short, it is LISP-like."
. more about MODLISP (lisp with modes)...
ACM SIGSAM Bulletin 1981
https://dl.acm.org/doi/abs/10.1145/1089242.1089244
MODLISP
James H. Davenport, Richard D. Jenks
"discusses the design and implementation of MODLISP,
a LISP-like language enhanced with the idea of MODes.
This extension permits, but does not require,
the user to declare the types of various variables,
and to compile functions with
the arguments declared to be of a particular type.
It is possible to declare several functions of the same name,
with arguments of different type
(e.g. PLUS could be declared for
Integer arguments, or Rational, or Real,
or even Polynomial arguments)
and the system will apply the correct function
for the types of the arguments."
ACM SIGSAM 1977
https://dl.acm.org/doi/10.1145/1088233.1088237
On the design of a mode-based symbolic system
Richard D. Jenks
"This paper is a preliminary report on
the design and implementation of a
mode-based symbolic programming system and compiler
which allows programming with rewrite rules and
[_]let and [_]is pattern-match constructs.
An important feature of this design is the provision for
mode-valued variables which allow
algebraic domains to be run-time parameters."
No comments:
Post a Comment