Skip to content

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

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' togobbledegook`, 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.]