What is Expressiveness in a Computer Language

[rossberg at ps.uni-sb.de]

Darren New schrieb:
> Andreas Rossberg wrote:
> > AFAICT, ADT describes a type whose values can only be accessed by a
> > certain fixed set of operations.
>
> No. AFAIU, an ADT defines the type based on the operations. The stack
> holding the integers 1 and 2 is the value (push(2, push(1, empty()))).
> There's no "internal" representation. The values and operations are
> defined by preconditions and postconditions.

Are you sure that you aren't confusing *abstract* with *algebraic* data
types? In my book, abstract types usually have an internal
representation, and that can even be stateful. I don't remember having
encountered definitions of ADT as restrictive as you describe it.

> Both a stack and a queue could be written in most languages as "values
> that can only be accessed by a fixed set of operations" having the same
> possible internal representations and the same function signatures.
> They're far from the same type, because they're not abstract.

Different abstract types can have the same signature. That does not
make them the same type. The types are distinguished by their identity.

Likewise, two classes can have the same set of methods, without being
the same class (at least in languages that have nominal typing, which
includes almost all typed OOPLs).

> I'm pretty sure in Pascal you could say
>
> Type Apple = Integer; Orange = Integer;
> and then vars of type apple and orange were not interchangable.

No, the following compiles perfectly fine (using GNU Pascal):

  program bla;
  type
    apple = integer;
    orange = integer;
  var
    a : apple;
    o : orange;
  begin
    a := o
  end.

- Andreas