1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
_A_b_s_t_r_a_c_t_ _t_y_p_e_ _d_e_f_i_n_i_t_i_o_n_s
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)
_a_b_s_t_y_p_e stack *
_w_i_t_h 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 `_w_i_t_h' is called the _s_i_g_n_a_t_u_r_e 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 _a_b_s_t_y_p_e declaration - they can occur anywhere in the
script. For readability, however, it is strongly recommended that the
implementation equations appear immediately after the _a_b_s_t_y_p_e
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 _a_b_s_t_y_p_e 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).
------------------------------------------------------------------------
_T_h_e_ _p_r_i_n_t_ _r_e_p_r_e_s_e_n_t_a_t_i_o_n_ _o_f_ _a_b_s_t_r_a_c_t_ _o_b_j_e_c_t_s
("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 _s_h_o_w (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
_s_h_o_w 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 _s_h_o_w 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 _s_h_o_w.
It also needs to have the right type, and if it does not, again its
presence will have no effect on the behaviour of _s_h_o_w (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.]
|
