Abstract type definitions
These enable a new data type to be defined by data type abstraction from
an existing type. We give the classic example, that of defining `stack'
as an abstract data type (here based on lists)
abstype stack *
with empty::stack *
push::*->stack *->stack *
isempty::stack *->bool
top::stack *->*
pop::stack *->stack *
stack * == [*]
empty = []
push a x = a:x
isempty x = x=[]
top (a:x) = a
pop (a:x) = x
The information given after `with' is called the signature of the
abstract type - the definitions of the identifiers in the signature are
called the `implementation equations' (these are the six equations given
above). Outside of the implementation equations the information that
stacks are implemented as lists is not available - [] and empty for
example are incomparable objects of two different and unrelated types (
[*] and stack * respectively). Only inside the implementation equations
are the abstract objects treated as being equivalent to their
representations.
The implementation equations do not have to appear immediately after the
corresponding abstype declaration - they can occur anywhere in the
script. For readability, however, it is strongly recommended that the
implementation equations appear immediately after the abstype
declaration.
Note that in Miranda there is no runtime cost associated with
administering an abstract data type. The responsibility for enforcing
the distinction between stacks and lists, for example, is discharged
entirely at compile time (by the type checker). The runtime
representation of a stack does not require any extra bits to distinguish
it from a list. As a result the Miranda programmer can freely use
abstract data types to structure his programs without incurring any loss
of efficiency by doing so.
Notice that the mechanism used to introduce abstract data types in
Miranda does not depend on the hiding of identifiers, and in this
respect differs from the traditional approach. A fuller discussion of
the Miranda abstype mechanism can be found in [*Turner 85].
------------------------------------------------------------------------
(*) D. A. Turner ``Miranda: A Non-Strict Functional Language with
Polymorphic Types'', Proceedings IFIP Conference on Functional
Programming Languages and Computer Architecture, Nancy, France,
September 1985 (Springer Lecture Notes in Computer Science, vol. 201, pp
1-16).
------------------------------------------------------------------------
The print representation of abstract objects
("advanced feature" - omit on first reading)
Values belonging to an abstract type are not in general printable. If
the value of a command-level expression is of such a type it will
normally print simply as
<abstract ob>
This is because the special function show (which is actually a family of
functions, see elsewhere) has no general method for converting such
objects to a printable form. It is possible to extend the definition of
show to include the ability to print members of an abstract type, using
some appropriate format. The convention for doing this is to include in
the definition of the abstract type a function with the name `showfoo'
(where `foo' is the name of the abstract type involved).
We illustrate how this is done taking `stack' as the example. Suppose
we decide we wish stacks to print - using a syntax such that the output
could be read back in (e.g. by readvals - see elsewhere) to generate the
same stack.
empty is to print as "empty"
push 1 empty is to print as "(push 1 empty)"
and so on.
Note that we decide to fully parenthesise the output for safety - since
we do not know the larger context in which our stack output may be
embedded.
Because `stack' is a polymorphic abstraction, showstack will need to
take as a parameter the appropriate show function for the element type
(which is num in the above examples, but could have been any type). We
add to the signature of stack the following function.
showstack::(*->[char])->stack *->[char]
To obtain the output format illustrated above, an appropriate definition
of showstack would be,
showstack f [] = "empty"
showstack f (a:x) = "(push " ++ f a ++ " " ++ showstack f x ++ ")"
If this definition is included in the script, stacks become printable,
using the specified format. The effect is to extend the behaviour of
the special built-in function show to handle stacks, and all data
structures built using stacks (such as list of tree of stacks, stack of
stacks and so on).
The general rule is as follows. Let `foo' be an abstract type name. To
make foo's printable, we need to define a `showfoo' thus:
if foo is a simple type (not polymorphic)
showfoo :: foo -> [char]
if foo is polymorphic in one type variable (foo *)
showfoo :: (*->[char]) -> foo * -> [char]
if foo is polymorphic in two type variables (foo * **)
showfoo :: (*->[char]) -> (**->[char]) -> foo * ** -> [char]
and so on. Note that the show function must be declared in the
signature of the abstract type, and that the name of the function is
significant - if we change its name from `showfoo' to `gobbledegook',
its definition will cease to have any effect on the behaviour of show.
It also needs to have the right type, and if it does not, again its
presence will have no effect on the behaviour of show (in this case the
compiler prints a warning message).
[Note on library directives: If you %export an abstract type, foo say,
to another file, it is not necessary to %export the showfoo function
explicitly to preserve the correct printing behaviour - if an abstract
type comes into existence with a show function in its signature the
compiler will `remember' how to print objects of the type even in scopes
where the show function has no name.]