[FOM] Sorry, yet another historical question

[Roger Bishop Jones]

On Sunday 01 Apr 2012 09:31, T.Forster at dpmms.cam.ac.uk 
wrote:

> (i) Is there a decent historical article anywhere
> outlining the emergence of the idea of the *Abstract
> data Type* (aka ADT)?

The idea of abstract data type is important both in object 
oriented and in functional programming languages.

As far as the object oriented paradigm is concerned the idea 
is said to originate with Barbara Liskov:

^ Barbara Liskov, Programming with Abstract Data Types, in 
Proceedings of the ACM SIGPLAN Symposium on Very High Level 
Languages, pp. 50--59, 1974, Santa Monica, California

In 1973 Robin Milner started work on what would become 
Edinburgh LCF, an important aspect of which was the idea of 
using a typed functional programming language as a "meta-
language" for programming proof search and checking, and the 
use of an abstract data type of theorems to ensure that any 
computation of a theorem would indeed yield a theorem of 
LCF.
As far as I am aware this was not published until 1978.
Some of the history here was written up by Mike Gordon in a 
paper with which you must already be familiar (obtainable 
from his web site).

There is a general survey paper by Cardelli and Wegner:

On understanding types, data abstraction, and polymorphism. 
Luca Cardelli and Peter Wegner. 
©1985  Computing Surveys, 17(4):471-522, 1985. [US.pdf] 
available on Cardelli's web site.

It might be that looking back to philosophers and logicians 
is better for your purposes, in which case one thinks of the 
type systems of Martin Lof in which dependent types appear 
prominently, or even further back to the work of Haskell 
Curry (both of whose names have been appropriated in various 
ways by functional programmers) whose work on the illative 
combinatory work anticipated dependent types in a type-free 
environment (though I don't know whether he had the 
existential types or dependent sums which correspond to 
ADTs).

However, all of this is overkill for the Julius Caesar 
problem.
Anyone who is thinking about that problem will probably be 
aware of the conflict between Frege and Hilbert on whether 
axiom systems should have specific interpretations or should 
be treated (as it were) as abstract structure descriptions.
So for this purpose the notion of "abstract data type" which 
is most relevant is probably Hilbert's.

Roger Jones
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20120404/e721f418/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/png
Size: 0 bytes
Desc: not available
URL: </pipermail/fom/attachments/20120404/e721f418/attachment.png>