|
Modeling Objects with Modules
|
|
Introduction
|
|
This worksheet demonstrates the basic ideas involved in using modules to implement abstract data structures as objects. An object is an expression that has both state and behavior. An object is represented (here) by a module expression that is instantiated by a constructor procedure that contains a prototypical module definition for objects of the same "class". An object's state is represented by local variables of the module that represent the object. An object is captured by the semantics of exported module members of its representation, typically of type procedure.
Maple, of course, does not have a class system as found in some object oriented languages such as Smalltalk or C++. Class-based object systems present problems that are particularly acute in languages that, like Maple, are intended for programming mathematical concepts.
To design an object, you must first determine what behavior you are trying to model. Each aspect of the object's behavior will, typically, be manifested as an exported procedure (or other data) of the module that implements the object. To implement the correct behavior, your objects will often have to maintain internal state. Typical behaviors associated with objects include the means by which a "client" (or user) of the object can query or modify the state of the object in a controlled way. It is this aspect of control that modules deliver, by allowing you to specify precisely the access to the state of an object to be had by its clients.
Several examples of fairly simple objects are presented here to acquaint you with the technique. Some of the code examples in this worksheet are available separately as sample source code. You will find them in the "samples" directory of your Maple installation.
|
|
|
Registers (Boxes)
|
|
Registers are the simplest nontrivial data structures. They are sometimes called "boxes". A register (or a box) is a very simple container into which values may be placed. The state of the data structure is represented by a single local variable that is assigned the current value of the register. The behavior of the register is very simple. You can do only two things with a register: retrieve the current value, and modify the current value. The first behavior is implemented by an exported procedure get. Modification of a register value is accomplished by means of the exported procedure set, which takes a single argument--the value to be stored in the register.
It is convenient to write a trivial procedure to generate registers on demand. Such a procedure is called a constructor. Here is a constructor for registering data structures.
|
>
|
MakeRegister := proc()
module()
local val; # state
export set,# behaviour
get;# behaviour
get := () -> val;
set := proc( v ) val := v end;
end module
end proc:
|
Exported procedures that implement the behavior of an object are sometimes called methods. Here, the register objects created by the constructor MakeRegister support two methods: get and set.
|
>
|
type( reg, '`module`' );
|
Instantiations of the modules that represent registers are independent over calls to the constructor. Creating another register by a subsequent call to MakeRegister does not affect the already instantiated register.
|
>
|
reg2 := MakeRegister();
|
You may find it convenient to associate a Maple type with an object data structure. When the objects are represented by modules, the most appropriate way to do this is to use a structured module type. Here, define a type register that may be used to recognize objects that implement the specified "interface" (in this example, those that export the set and get procedures).
|
>
|
`type/register` := '`module`( set, get )':
|
|
>
|
type( reg, 'register' );
|
It is now possible to write a procedure that will accept any register as an argument, regardless of how it is implemented. The procedure relies only upon the "contract'' satisfied by the register object.
|
>
|
IncrementRegister := proc( r::register ) r:-set( 1 + r:-get() ); eval( r, 1 ) end;
|
|
>
|
IncrementRegister( reg );
|
Another implementation of the register may be used provided only that it implements the expected exports get and set.
|
>
|
reg := module()
export get, set, double;
local value;
value := NULL;
get := () -> value;
set := proc( v ) value := v end;
double := proc() value := 2 * value end;
end module:
|
|
>
|
IncrementRegister( reg2 );
|
|
|
|
Pairs (Cons Cells)
|
|
A pair data structure is just slightly more complicated than the register data structure shown above. Instead of holding a single value, a pair holds (naturally enough) a pair of values. It is, in effect, two registers coupled together. Pairs can be used to implement efficient linked lists.
The two values stored in a pair are called, traditionally, the "car" and "cdr" of the pair.
|
>
|
MakePair := proc( first, rest )
module()
local theCar, theCdr;
export car, cdr, setcar, setcdr;
theCar := first;
theCdr := rest;
car := () -> theCar;
cdr := () -> theCdr;
setcar := proc( v ) theCar := v end;
setcdr := proc( v ) theCdr := v end;
end module
end proc:
|
Next, define some generic functions.
|
>
|
car := proc( obj::`module` )
if member( 'car', obj ) then
obj:-car()
else
error "no applicable method: %1", procname
end if
end proc:
|
|
>
|
cdr := proc( obj::`module` )
if member( 'cdr', obj ) then
obj:-cdr()
else
error "no applicable method: %1", procname
end if
end proc:
|
|
>
|
setcar := proc( obj::`module`, v )
if member( 'setcar', obj ) then
obj:-setcar( v )
else
error "no applicable method: %1", procname
end if
end proc:
|
|
>
|
setcdr := proc( obj::`module`, v )
if member( 'setcdr', obj ) then
obj:-setcdr( v )
else
error "no applicable method: %1", procname
end if
end proc:
|
By using the pair type in the parameter specification for these routines, you ensure that only modules that export correctly named methods are accepted.
|
>
|
Nil := MakePair(false,false):
|
|
>
|
p := MakePair( 1, Nil ):
|
|
>
|
for i from 2 to 10 do p := MakePair( i, eval( p ) ) end:
|
The procedures above can be simplified somewhat if you let Maple do the argument type-checking for us. To this end, define here a type pair for recognizing pair data structures. The empty list [] is used as a sentinel object.
|
>
|
`type/pair` := '{ identical([]), `module`( car, cdr, setcar, setcdr ) }':
|
|
>
|
Car := ( p::pair ) -> p:-car();
|
|
>
|
Cdr := ( p::pair ) -> p:-cdr();
|
|
>
|
SetCar := ( p::pair, v::anything ) -> p:-setcar( v );
|
|
>
|
SetCdr := ( p::pair, v::anything ) -> p:-setcdr( v );
|
|
|
|
Records
|
|
Modules can be used as simple records (or "structures"). A record is a mutable data structure in which a fixed set of named members can hold arbitrary Maple expressions. For example, members of a record are accessed by name, rather than by position; this is how records differ from lists. Records are constructed by using the record constructor, as follows.
|
>
|
r := Record( 'a', 'b' );
|
Unlike the examples in the previous two sections, the "data" members of a record are accessed directly, rather than through exported procedures controlling that access. This approach is faster (because accessing and modifying the data does not incur the overhead of a procedure call), but does not offer the opacity for the data type that is achieved by using accessor methods.
Records are primarily useful as an aggregate data type. By grouping a number of data items together in a record, you can access them as a whole. The type of a record may be specified as a structured type, similar to those for modules. (Since "record'' is not a Maple language keyword, backquotes are not required.)
|
>
|
`type/quaternion` := 'record( re::algebraic, i::algebraic, j::algebraic, k::algebraic )';
|
|
>
|
q := Record( 're' = sqrt( 2 ), 'i' = 1, 'j' = -1, 'k' = sqrt( 1 - x^2 ) );
|
|
>
|
type( q, 'quaternion');
|
|
>
|
QuaternionNorm := proc( q::quaternion )
radnormal(
sqrt(
q:-re*q:-re
+ q:-i*q:-i
+ q:-j * q:-j
+ q:-k * q:-k ) )
end proc:
|
|
|
|
A Clock
|
|
A clock data structure is handy for passing around as a timer. Clock objects have state that expresses whether the clock is currently "running" (as a timer) and, if it is, how much time has elapsed since it was started. The behavior of a clock is expressed through its API in the methods that allow you to make queries against its internal state, to start the clock as a timer, to sample it at any time afterward, and to stop the clock, measuring the total elapsed time.
|
>
|
Clock := proc()
module()
export start, halt, now, reset, sample, elapsed;
local checkpoint, running;
description "a clock object";
# an internal state variable; assigned when clock is running.
checkpoint := 'checkpoint';
# Test whether the clock is running at the point of call.
running := proc()
not type( checkpoint, 'symbol' )
end proc;
# Return the current time
now := () -> iolib( 25 );
# Start the clock as a timer
start := proc()
checkpoint := now()
end proc;
# Reset a clock that is already running.
reset := proc()
if running() then
checkpoint := now()
else
error "clock is not running"
end if
end proc;
# Stop the clock (as a stopwatch).
halt := proc()
checkpoint := 'checkpoint'
end proc;
# Sample the current running time since the clock
# was last started or reset.
sample := proc()
if type( checkpoint, 'symbol' ) then
error "clock is not running"
else
now() - checkpoint
end if
end proc;
# Return the time (in seconds) that has elapsed since
# the clock was started.
elapsed := proc()
local t;
t := sample();
halt();
t
end proc;
end module
end proc:
|
The current time can always be queried, even if the clock is running as a timer.
|
>
|
clock:-start(): int( sin(m*x)^2 * cos(n*x)^(1/3), x ): clock:-sample();
|
|
|
|
A Stack
|
|
The essential features of modules that are used here are:
the fact that modules are first-class expressions in Maple
the ability to encapsulate mutable state
the ability to keep an objects' mutable state "hidden" (or "private")
A stack is a compound data structure that is capable of holding an ordered collection of objects. Stacks are characterized by the behavior that objects can be placed into the stack at only one "end", and may only be removed from that same end. Inserting an item onto the stack is called "pushing", while removing the topmost item on the stack is called "popping" the stack. You can specify an abstract interface for stacks by using a structured module type, as follows.
|
>
|
`type/Stack` := '`module`( push, pop, empty, top )':
|
The push method pushes an item onto the top of the stack. You can remove the topmost item on the stack by calling the pop method; an exception is raised if the stack is empty. You can test for an empty stack by using the empty method. Finally, the topmost item on a nonempty stack can be examined (without removing it) by calling the top method.
Our stacks will be constructed to satisfy this interface definition. The advantage of specifying an abstract interface, and of using modules to hide the implementation of an object data structure, is that it allows you to change the implementation without breaking client code. Presented below are two distinct stack implementations, both of which satisfy the abstract interface described above.
|
|
A List Implementation
|
|
Since access to items on a stack is constrained to the topmost element, it is easy to use linked lists to implement the stack API. The following constructor, lStack, offers an implementation that uses linked lists as the underlying storage mechanism for the stack. This implementation relies on the pair data structure discussed above.
|
>
|
lStack := proc()
module()
description "a stack";
local data; # linked list holding the stacked data items
export top, # return the top item on the stack
empty, # test for an empty stack
init, # initialise the stack for use
push, # push an item onto the top of the stack
pop; # remove the top item on the stack
# Initialise the stack to the empty list
init := proc() data := Nil end;
# Test whether the stack is empty.
empty := () -> evalb( data = Nil );
# Query the top of the stack.
top := proc()
if empty() then
error "empty stack"
else
Car( data )
end if
end proc;
# Push an item onto the top of the stack.
push := proc( item )
data := MakePair( item, data )
end proc;
# Pop the top item on the stack, or raise an exception if the
# stack is empty.
pop := proc()
local t;
if empty() then
error "stack is empty"
else
t := top();
data := Cdr( data );
t
end if
end proc;
# Call the initialisation routine.
init();
end module
end proc:
|
|
>
|
s:-push( a ); s:-push( b ); s:-push( c );
|
|
>
|
s:-pop(); s:-pop(); s:-pop();
|
|
|
|
A Table Implementation
|
|
Here is another constructor for stacks. The implementation offered here uses a table as the underlying data storage mechanism, so the constructor is called tStack.
|
>
|
tStack := proc()
module()
local data, # table in which the data is stored
ptr; # pointer to the top of the stack
export top, empty, init, push, pop;
description "a stack";
init := proc()
data := table();
ptr := 0
end proc;
empty := () -> evalb( ptr = 0 );
top := proc()
if empty() then
error "empty stack"
else
data[ ptr ]
end if
end proc;
push := proc( e )
if not assigned( ptr ) then
ptr := 0
end if;
ptr := 1 + ptr;
data[ ptr ] := e
end proc;
pop := proc()
local t;
if empty() then
error "empty stack"
else
t := top();
data[ ptr ] := evaln( data[ ptr ] );
ptr := ptr - 1;
t
end if
end proc;
end module
end proc:
|
|
>
|
s:-push( a ); s:-push( b ); s:-push( c );
|
|
>
|
while not s:-empty() do s:-pop() end do;
|
|
The fact that both the list- and table-based stacks implement the same abstract interface allows you to write generic code that uses either implementation (or both). For example, here is a very simple routine that can be used to compare the performance of the two stack implementations. It accepts a stack s as a parameter, and a positive integer n, and inserts n items onto the stack, after which it pops the stack after calling the top and empty methods until it is empty.
|
>
|
ExerciseStack := proc( s::Stack, n::posint )
|
|
>
|
while not s:-empty() do
|
|
>
|
time( ExerciseStack( ls, 100 ) );
|
|
>
|
time( ExerciseStack( ts, 100 ) );
|
|
Return to Index for Example Worksheets
|
