type safety (was Re: FAQ terminology harmonisation)

[C.Reinke]

> > [...]
> > The basic idea is that if there is one abstract type in the 
> > language, we might be able to build other abstractions on top
> > of that. Functions fit that bill wonderfully (the only thing
> > you can do with a function is to apply it). In particular, 
> > there is no need for a module implementing an abstract type
> > to expose anything but the API functions.
> 
> I'm not sure that solves the problem - it just moves it from one
> existing type to another 

It doesn't protect you from trying to misuse a data abstraction, but
it severely limits the kinds of misuse you can try, and it makes it
nearly impossible to discover the internal representation. That is
good enough for most purposes, and a big improvement in the case of
the queue example (no disagreement that Erlang's typing could be
improved, though;).

> (or, I don't follow you and you'll have to give me an example.)

oh, but I did!-) After the commented example quoted from the
programming rules, I added a variant of the queue based on this
idea. Obviously too well hidden, sorry. If that example doesn't
clarify the idea, please let me know..

> [..pattern matching and is_sometype(X) expose internal structure ..]

Yes, procedural data structures as used in the example would still
visibly give you tuples of functions, but they would do so for _all_
data abstractions. The _only_ meaningful way to distinguish between
such abstractions (short of reflecting the erlang functions into
some other representation) is by their API functions, which is the
way it should be. In particular, the internal representation of
queues as lists, trees or whatever is no longer visible.

Cheers,
Claus

PS

While the idea is nice and understandable without historic context,
I'd still like to point to some references to indicate how those
tricks relate to "proper" abstract data types, and how long they
have been around, even though they depend on the ability to pass
functions around (often, this is combined with local references,
only accessible from the API functions). 

1 Procedural encapsulation: A linguistic protection technique 
  Stephen N. Zilles, 1973 , Proceeding of ACM SIGPLAN - SIGOPS
  interface meeting on Programming languages - operating systems 

  http://doi.acm.org/10.1145/800021.808305
  (text not online:-(

2 Protection in programming languages 
  James H. Morris, Jr.  Univ. of California, Berkeley 
  Communications of the ACM, Volume 16 ,  Issue 1  (January 1973) 

  http://doi.acm.org/10.1145/361932.361937
  (don't let the erroneous abstract there fool you..)

3 User-Defined Types and Procedural Data Structures as
    Complementary Approaches to Data Abstraction,
  John C.~Reynolds,  reprinted in: Theoretical Aspects of
  Object-Oriented Programming, The MIT Press, 1994, ed.  Carl A.Gunter
  and John C.Mitchell, (first appeared in 1975)

  preprint at ftp://ftp.cs.cmu.edu/user/jcr/compdataabstr.pdf

The relation between procedural data structures and modern
abstract data types is explored in 

4 On understanding types, data abstraction, and polymorphism.
  Luca Cardelli and Peter Wegner. 
  Computing Surveys, 17(4):471-522, 1985. 
  http://research.microsoft.com/Users/luca/Papers/OnUnderstanding.A4.pdf
  (see section 5)

5 Mitchell, J.C. and Plotkin, G.D., Abstract types have existential
  type, ACM Trans. Programming Languages and Systems, 10, 3 (1988)
  470--502. 

  http://doi.acm.org/10.1145/44501.45065

The main difference being that, since the representation type
is hidden by the type system, the representation no longer has
to be hidden, because clients of the data abstraction can't do
anything with the representation but apply API functions to it.