Dr.Barbara Liskov`the software crisis averted with modularity based on data abstraction

21.6.10:  7.12: news.adda/lang/

Dr.Barbara Liskov`the software crisis averted with modularity based on data abstraction:

. the key to programming in the large 

is modularity based on data abstraction

and that was not obvious before her work,

but now her work is mainstream, so it now seems obvious.

AI Dr Barbara Liskov 2013`The Power of Abstraction:

https://www.infoq.com/presentations/programming-abstraction-liskov/

AI Dr Barbara Liskov is an Institute Professor at MIT, 

who has won an ACM Turing Award, 

the ACM SIGPLAN Programming Language Achievement Award, 

the IEEE Von Neumann medal, 

and the lifetime achievement award

from the Society of Women Engineers.

. the following are notes from her 2013 speech

and quotes from the literature she mentions.

. how to handle the software crisis;

we have big things to do with software,

and no way to get organized.

. we are spaghetti-coding with gotos,

and our procedures are not true modules

they are simply for code reuse

and are communicating via globals.

AFIPS 1972

https://dl.acm.org/doi/abs/10.1145/1479992.1480018

A design methodology for reliable software systems

B. H. Liskov

https://ckrybus.com/static/papers/liskov1972.pdf

"While system designers and implementers 

recognize the need for reliable software, 

they have been unable to produce it."

References to her prior works:

B H Liskov E Towster 1971

The proof of correctness approach to reliable systems

The MITRE Corporation MTR 2073 Bedford Massachusetts 

B H Liskov 1972

Guidelines for the design and implementation of reliable software systems 

The MITRE Corporation MTR 2345 Bedford Massachusetts 

B H Liskov 1972

The design of the Venus operating system

Comm ACM 15 3 pp 144--149 

https://dl.acm.org/doi/abs/10.1145/361268.361272

SOSP '71: Proceedings of the third ACM symposium on Operating systems principles

https://dl.acm.org/doi/abs/10.1145/800212.806493

based on a 1971 Mitre report

https://apps.dtic.mil/sti/pdfs/AD0733585.pdf

". Venus was built as a hierarch of levels of abstraction, 

defined by Dijkstra 

[Comm. ACM 11, 5 (May 1968), 341-346;

https://dl.acm.org/doi/abs/10.1145/363095.363143

the structure of 'THE' - multiprogramming system

Dijkstra, E.W. p343: "system hierarchy"]

http://courses.cs.washington.edu/courses/csep551/02wi/first.pdf

. a level is defined as not only the 

abstraction which it supports(eg virtual mem), 

but also by the resources which it uses 

in realizing that abstraction.

. lower levels (those closer to the machine)

are not aware of the resources of higher levels;

higher levels may apply or access the resources of lower levels 

only by calling functions provided by the lower level.

. this reduces the number of interactions among parts of a system

and makes them more explicit."

. see also Mitre report 1970:

https://apps.dtic.mil/sti/citations/AD0709717

principle of operation of the Venus microprogram.

. in 1972 Liskov wrote about a software architecture

she had designed for the Venus OS

where instead of subroutines communicating via globals, 

the variables would be in partitions,

and if you wanted to access one of them,

you would call one of the partition's procedures,

so that if you understood the partitions' procedures 

(its abstract interface)

then you understood all the ways 

that the partition state could change

(no surprises).

. then she saw how that was like the

abstract data type,

that are a close match to the modules

used in the design process.

Communications of the ACM 1973

https://dl.acm.org/doi/abs/10.1145/361932.361937

Protection in programming languages

James H. Morris

. Morris talks about the importance of encapsulation

[like the partition idea];

because when your program is run alongside others

good fences make good neighbors.

. he had the idea like the internet

that modules hide their details

not just with a trusted programming language,

but by separately encrypting each module.

Proc ACM SIGPLAN symposium on Very high level languages 1974

https://dl.acm.org/doi/abs/10.1145/800233.807045

Programming with abstract data types

Barbara Liskov, Stephen Zilles

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.3043&rep=rep1&type=pdf

. after Liskov and Zilles wrote that paper,

they got down to designing a programming language, 

CLU (named after "CLUster" that implemented 

their abstract data type idea.)

. CLU was heap-based (inherently pointer-based

when pointers were thought to be evil).

. it had separate compilation like lisp,

no concurrency, and no inheritance.

. here is an object-oriented binary operation:

obj1`operation(obj2);

CLU instead used type-orientation for binary operations:

type`operation(obj1, obj2),

so that the type tags of both obj1 and obj2

could be involved in selecting the method

that would be implementing that operation.

. when Liskov used the term "polymorphism",

it meant it had generics:

you could have set(T.type).type

defining a set of objects all of a given type T.

. notice that there are types of types;

eg, you might want only types that are ordered.

so they had a "where" constraint clause:

set(T.type).type where T is ordered.

. iterators: for all x in collection do statement.

. for doing iterators, they got an idea from

the generators of CMU's Alphard language;

then they invented something like C# generators.

. then when they studied oop (obj-oriented prog),

she found that inheritance was used for 2 things:

implementation reuse:

(defining one thing in terms of another),

and type hierarchy:

( like when (int, real, rational, complex) 

are all polymorphisms of type number ).

--type hierarchy reminded her of

CLU's "where" clauses

(constraint clause for filtering their 

the node type for generic data structures).

a simplified or clarifying definition of the

Liskov substitution principle:

. objects of subtypes, if used via supertype methods,

should behave like those of supertypes.

Addendum Proc of OOPSLA ’87, SIGPLAN Notices 1988

https://dl.acm.org/doi/10.1145/62139.62141

Keynote address

data abstraction and hierarchy

Barbara Liskov

cited by:

Thesis (Ph. D.)--MIT, Computer Science, 2010.

https://dspace.mit.edu/handle/1721.1/62439

Automating abstraction functions

Rayside, Derek F

https://dspace.mit.edu/bitstream/handle/1721.1/62439/711001803-MIT.pdf?sequence=2&isAllowed=y

"4.6 Object Equality and Observational Equivalence

Liskov, Guttag, Wing, and Leavens [60, 67-70] 

recommend that object equality should 

imply observational equivalence: 

i.e., that the two equal objects are indiscernible, 

and any computation would produce the same result with either one. 

The phrase 'observational equivalence' is also used in 

the formal semantics of programming languages with a similar meaning: 

any observationally equivalent terms compute the same result.

One could see this idea of observational equivalence

as a modern incarnation of Leibniz's Law [64], 

which has two parts: 

the Identity of Indiscernibles 

and the Indiscernibility of Identicals. 

In the notation of modern symbolic logic one might write for the first part [36]:

for all properties P(Px equiv Py) => x = y

meaning that if object y has every property P that object x has, and vice versa, 

then x is identical to y. 

The converse, the Indiscernibility of Identicals, might be written as [36]:

x = y implies  for all properties P(Px equiv Py)"

[69] BARBARA H. LISKOv. Data abstraction and hierarchy. 

In NORMAN K. MEYROWITZ, editor, Proceedings of the ACM/SIGPLAN Conference on

Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 

Orlando, FL, October 1987.  Keynote address.

"In the early 1970's researchers in specification languages 

became interested in separating the meaning of an abstract data type

from its concrete representation. 

For example, a set of integers could be represented by 

an array or a binary tree or some other concrete structure. 

It should be possible to specify a set of integers

independently of the choice of representation.

Two solutions to this challenge were developed, 

one in which the abstract values were represented as terms in an algebra, 

and one in which the abstract values were represented by sets and relations.

The algebraic approach was first presented by 

Steve Zilles on October 3, 1973, 

at a workshop at MIT organized by Barbara Liskov [40]. 

Zilles presented the algebraic specification of a set of integers

listed in Figure 1-1 (as recorded by Homing [48], 

who was in attendance at the talk). 

In the algebraic approach operations on the abstract datatype

are defined by equations that relate them to other ADT operations. 

The algebraic approach was developed by a number of people, 

including in the doctoral dissertations of Guttag 

[JOHN V. GUTTAG. 

The Specification and Application to Programming ofAbstract Data Types. 

PhD thesis, University of Toronto, Department of Computer Science, 1975.

see evolution of that thesis:

Communications of the ACM, 1977 

http://cecs.wright.edu/people/faculty/tkprasad/courses/cs784/guttag-cacm77.pdf

Abstract data types and the development of data structures] 

and Wing [JEANETTE M. WING. 

A two-tiered approach to specifying programs. 

PhD thesis, MIT Electrical Engineering and Computer Science, 1983], 

https://apps.dtic.mil/sti/pdfs/ADA133949.pdf

which eventually culminated in the Larch system [40]. 

Figure 1-1 Algebraic specification of a set of integers by Zilles [48]

Operators

Insert: Sets x Ints -> Sets

Remove: Sets x Ints -> Sets

Has: Sets x Ints -> Bools

Null: -> Sets

Relations

Has(Insert(s, i), j) = if i=j then True else Has(s, j)

Has(Remove(s, i), j) = if i=j then False else Has(s, j)

Has(Null , j) = False"

[40] JOHN V. GUTTAG, JAMES. J. HORNING, STEPHEN J. GARLAND, K. D. JONES, A. MODET, AND JEANETTE M. WING. 

Larch: Languages and Tools for Formal Specification. 

SpringerVerlag, 1993.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.2194

[48] JAMES J. HORNING. The Larch Shared Language: Some Open Problems. 

In MAGNE HAVERAAEN, OLAF OWE, AND OLE-JOHAN DAHL, editors, 

Recent Trends in Data Type Specification: 

11th Workshop on Specification of Abstract Data Types, 

volume 1130 of Lecture Notes in Computer Science, Oslo, Norway, September 1995. 

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.3507