Example of a Maple Package
This example briefly introduces all of the concepts required to add your own package to Maple. In particular, the following topics are covered:
•

using unevaluated function calls to represent data structures

•

adding your own type procedures

•

customizing the printing of data structures represented with function calls

•

loading your package routines "on demand"

•

creating your own repository

•

creating the package module

•

updating the help system

To demonstrate these techniques, we will construct a Maple implementation of a simple dictionary structure that uses binary trees. This structure allows the insertion, deletion, and lookup of numeric keys and associated values. It could easily be extended to allow range queries or to print the sorted list of values.

The Data Structure


A binary search tree contains a series of keys  in our case, numeric keys  and associated values. Each nonempty tree node has a key, a value, and left and right children that are also trees. The distinguishing feature of a binary search tree is that all the key values in the left child of any node are less than the key value of the node (while all key values in the right child are greater than the key values in the node). This ordering property allows for very efficient insertion, deletion, and lookup operations.
To represent the trees, we use an unevaluated function call of the form BINARYTREE(key, value, left, right). The empty tree, a special case of a tree, is represented as BINARYTREE( ). For example, the tree
2 f(x)
/ \
/ \
/ \
1 e(x) 3 g(x)
is represented as
>

tree := BINARYTREE(2,f(x),
BINARYTREE(1,e(x),BINARYTREE(),BINARYTREE()),
BINARYTREE(3,g(x),BINARYTREE(),BINARYTREE())):

This is a form similar to the nested parenthesis used in LISP and other languages. Using function calls in this way is equivalent to records, except that our field names are referred to positionally as op(1,...) or op(2,...). By defining some simple utility procedures, we can regain this simple access, and we can also make the data structure more robust by adding error checking.
The advantages to using unevaluated function calls as opposed to records in this case are:
•

Unevaluated function calls are immutable, lowstorage data structures.

•

Testing equality is a simple pointer comparison, which is fast, while using records would require comparing all the fields.

•

We can extend the pretty printer to display unevaluated function calls nicely.

To make the programming and use of binary trees easier, we define a constant emptytree for the empty tree. Because of our choice of data structure, all empty trees are equal to this object.
>

emptytree := BINARYTREE();

${\mathrm{emptytree}}{\u2254}{\mathrm{BINARYTREE}}{}\left(\right)$
 (1.1) 
For now, define the leftchild and rightchild operations as:
>

rightchild := proc(tree)
if tree = emptytree then
error "rightchild operation is invalid on an empty tree";
end if;
op(4,tree)
end proc:
leftchild := proc(tree)
if tree = emptytree then
error "leftchild operation is invalid on an empty tree";
end if;
op(3,tree)
end proc:

Now we can simply refer to leftchild(tree) or rightchild(tree) without having to remember the operand numbers. More importantly, if we later decide to rearrange the order in which the various fields are stored, this need only change in this one place.


Updating the Type System


The Maple type procedure is used to test whether an object has a stated property. We must add a test for the property "is a binary tree?" We also want to be able to test whether a tree is empty. To define a new type, define a procedure or type expression `type/name`, where name is the name for the new type.
The following two definitions perform these tests:
>

`type/binarytree` := 'specfunc(anything,BINARYTREE)':
`type/emptytree` := proc(x) evalb(x = emptytree) end:

So now we can ask questions such as:
>

type( emptytree, 'binarytree' );

>

type( f(x), 'binarytree' );

For some applications, the definition of `type/binarytree` is too simplistic. In many cases, it does not suffice to check that an object is a binary tree; the type of the values in the tree are also required. In other words, we want to define a type binarytree(type) that checks whether an object is a binary tree with values of the correct type. The Maple structured types allow the specification of more complicated type tests. Structure arguments are passed as the second argument to a `type/...` procedure, so implementing a structured type requires that we check the number of arguments passed to the procedure by using nargs, and then perform any extra type tests.
A structured form of the binarytree type can be implemented by using:
>

`type/binarytree` := proc(x)
if type( x, 'specfunc(anything,BINARYTREE)' ) then
if (nargs = 1 or x = emptytree or (
type( leftchild(x), 'binarytree'(args[2]) ) and
type( rightchild(x), 'binarytree'(args[2]) ) and
type( op(2,x),args[2]))
) then
true
else
false
end if
else
false
end if
end proc:
`type/binarytree`( emptytree ) := true:

Note: When used as a structured type test, this procedure not only checks the toplevel node, but also verifies all of its descendents. The type "binarytree(anything)" can be used to test the complete structure of the tree without testing the types of the node values.
Using this version of `type/binarytree`, we can use a much stronger test, such as:
>

type( tree, 'binarytree(function)' );

We should upgrade our definitions of leftchild and rightchild to take advantage of these type tests. For now, we will restrict ourselves to updating the access procedures to check that their argument is a binary tree, although we could also replace the internal comparison to emptytree with a type test.
>

rightchild := proc(tree::binarytree)
if tree = emptytree then
error "rightchild operation is invalid on an empty tree"
end if;
op(4,tree)
end proc:
leftchild := proc(tree::binarytree)
if tree = emptytree then
error "rightchild operation is invalid on an empty tree"
end if;
op(3,tree)
end proc:



Binary Tree Operations


This section defines the insert, delete, and lookup operations on binary trees.
>

insert := proc(tree::binarytree, key::numeric, value::anything)
if tree = emptytree then
BINARYTREE(key,value,emptytree,emptytree)
elif key > op(1,tree) then
BINARYTREE(op(1..3,tree),procname(rightchild(tree),key,value))
elif key < op(1,tree) then
BINARYTREE(op(1..2,tree),procname(leftchild(tree),key,value),
rightchild(tree))
else
error "duplicate keys in binary tree"
end if
end proc:
lookup := proc(tree::binarytree, key::numeric)
if (tree = emptytree) then
error "key not found in binary tree"
elif (key < op(1,tree)) then
procname(leftchild(tree),key)
elif (key > op(1,tree)) then
procname(rightchild(tree),key)
else
op(2,tree)
end if
end proc:
delete := proc(tree::binarytree, key::numeric)
local child;
if tree = emptytree then
error "key not found in binary tree"
elif key < op(1,tree) then
BINARYTREE(op(1..2,tree),procname(leftchild(tree),key),
rightchild(tree))
elif key > op(1,tree) then
BINARYTREE(op(1..3,tree),procname(rightchild(tree),key));
elif leftchild(tree) = emptytree then
rightchild(tree)
elif rightchild(tree) = emptytree then
leftchild(tree)
else
child := leftchild(tree);
while rightchild(child) != emptytree do
child := rightchild(child)
end do;
BINARYTREE(op(1..2,child),
procname(leftchild(tree),op(1,child)),
rightchild(tree))
end if
end proc:

A short test session verifies that these routines perform the required operations:
>

insert(emptytree,5,f(x));

${\mathrm{BINARYTREE}}{}\left({5}{\,}{f}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left(\right)\right)$
 (3.1) 
${\mathrm{BINARYTREE}}{}\left({5}{\,}{f}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left({2}{\,}{g}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left(\right)\right){\,}{\mathrm{BINARYTREE}}{}\left(\right)\right)$
 (3.2) 
${\mathrm{BINARYTREE}}{}\left({5}{\,}{f}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left({2}{\,}{g}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left(\right)\right){\,}{\mathrm{BINARYTREE}}{}\left({7}{\,}{h}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left(\right)\right)\right)$
 (3.3) 
${\mathrm{BINARYTREE}}{}\left({5}{\,}{f}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left({2}{\,}{g}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left(\right)\right){\,}{\mathrm{BINARYTREE}}{}\left({7}{\,}{h}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left({8}{\,}{i}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left(\right)\right)\right)\right)$
 (3.4) 
${\mathrm{BINARYTREE}}{}\left({5}{\,}{f}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left({2}{\,}{g}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left(\right)\right){\,}{\mathrm{BINARYTREE}}{}\left({7}{\,}{h}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left({6}{\,}{j}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left(\right)\right){\,}{\mathrm{BINARYTREE}}{}\left({8}{\,}{i}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left(\right)\right)\right)\right)$
 (3.5) 
${h}{}\left({x}\right)$
 (3.6) 
>

tree := delete((3.5),7);

${\mathrm{tree}}{\u2254}{\mathrm{BINARYTREE}}{}\left({5}{\,}{f}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left({2}{\,}{g}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left(\right)\right){\,}{\mathrm{BINARYTREE}}{}\left({6}{\,}{j}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left({8}{\,}{i}{}\left({x}\right){\,}{\mathrm{BINARYTREE}}{}\left(\right){\,}{\mathrm{BINARYTREE}}{}\left(\right)\right)\right)\right)$
 (3.7) 


Alternate Print Formats


While the previous test demonstrated that the binary tree code appears to be functioning, it also clearly demonstrated that the BINARYTREE structure is quite large and hard to read. Maple provides a print preprocessing stage that gives programmers limited control over the printing of their data structures.
When printing a function call f(x), Maple first looks for a procedure `print/f `. If Maple finds `print/f `, it passes the arguments of the function to the `print/...` procedure. The result of this call is printed, instead of the original structure. In this way, a programmer can define a different print form for any function call data structure.
We can define a more compact printing form for BINARYTREE objects by using nested lists and suppressing the printing of the empty tree.
>

`print/BINARYTREE` := proc()
`if`( nargs > 0, [args], `` )
end proc:
tree;

$\left[{5}{\,}{f}{}\left({x}\right){\,}\left[{2}{\,}{g}{}\left({x}\right){\,}{\,}\right]{\,}\left[{6}{\,}{j}{}\left({x}\right){\,}{\,}\left[{8}{\,}{i}{}\left({x}\right){\,}{\,}\right]\right]\right]$
 (4.1) 


Creating a Package


The previous sections described a basic implementation of a binary tree, including extensions to the type system and printing. In this section, we turn this assortment of procedures into a Maple package.
A Maple package is a set of routines and data that is placed in a module with option package. Existing packages include LinearAlgebra, numapprox, and many others  for a complete list, see index/package. The distinguishing feature of a package is that all the package procedures are local to the module and exported (although the with command allows access by short names). Because of this, the same procedure name can exist in multiple packages without name collisions.
Note that, prior to the introduction of modules, packages were usually implemented as tables. All new packages should use modules.


Configuring a Private Repository


First you need to configure your Maple session to work with a private repository. While the directions vary from platform to platform, the following basic steps are needed.
1.

Create a directory or folder of any appropriate name. For this example, assume that the repository is called "bstlib.mla".

2.

Use savelib to create a Maple repository in the chosen directory or folder. On Windows and UNIX, this is accomplished by using the savelib command, for example, savelib( 'BinaryTree', "bstlib.mla" ).

3.

Add the directory or folder name to the end of the list of locations in the libname variable. In your Maple session, add the command libname := libname, "bstlib.mla";.

The last step has to be repeated for every Maple session, so you may want to place it in your Maple initialization file.
To protect against unintentional changes to the main Maple library, you should ensure that it is marked as readonly.


Building the Package Module


To actually construct the package, you must write a module and assign it to the name chosen for the package. In this case, the name BinaryTree will be used for the package name.
The names of all the useraccessible routines are listed as exports of the module. You should also include option package among the declarations for the module so that it can be distinguished from modules used for other purposes.
Since you will want to make your new types available to your users, you should install them when the package is read from the repository. This can be done by writing an initialization routine and using it in the load = option of the module. Here, the local routine setup is used to install the types for binarytree and emptytree and the pretty printer extension `print/BINARYTREE`.
The complete source code for BinaryTree appears below.
>

restart;
BinaryTree := module()
description "a package for manipulating binary trees";
export emptytree, leftchild, rightchild,
insert, delete, lookup;
local setup;
option package, load = setup;
setup := proc()
global `type/emptytree`, `type/binarytree`, `print/BINARYTREE`;
`type/emptytree` := e > evalb( e = emptytree );
`type/binarytree` := proc(x)
if type(x,'specfunc(anything,BINARYTREE)') then
if nargs = 1 or x = emptytree or (
type( leftchild(x), 'binarytree'(args[2]) ) and
type( rightchild(x), 'binarytree'(args[2]) ) and
type( op(2,x), args[2] )
) then
true
else
false
end if
else
false
end if
end proc:
`print/BINARYTREE` := proc()
`if`( nargs > 0, [args], `` )
end proc:
end proc;
setup(); # call it now
emptytree := 'BINARYTREE()';
ASSERT( type( emptytree, 'binarytree' ) );
rightchild := proc(tree::binarytree)
if tree = emptytree then
error "rightchild operation is invalid on an empty tree"
end if;
op(4,tree)
end proc;
leftchild := proc(tree::binarytree)
if tree = emptytree then
error "rightchild operation is invalid on an empty tree"
end if;
op(3,tree)
end proc;
insert := proc(tree::binarytree, key::numeric, value::anything)
if tree = emptytree then
'BINARYTREE'(key,value,emptytree,emptytree)
elif key > op(1,tree) then
'BINARYTREE'(op(1..3,tree),procname(rightchild(tree),key,value));
elif key < op(1,tree) then
'BINARYTREE'(op(1..2,tree),procname(leftchild(tree),key,value),
rightchild(tree))
else
error "duplicate keys in binary tree"
end if
end proc;
lookup := proc(tree::binarytree, key::numeric)
if tree = emptytree then
error "key not found in binary tree"
elif key < op(1,tree) then
procname(leftchild(tree),key)
elif key > op(1,tree) then
procname(rightchild(tree),key)
else
op(2,tree)
end if
end proc;
delete := proc(tree::binarytree, key::numeric)
local child;
if tree = emptytree then
error "key not found in binary tree";
elif key < op(1,tree) then
BINARYTREE(op(1..2,tree),procname(leftchild(tree),key),
rightchild(tree));
elif key > op(1,tree) then
BINARYTREE(op(1..3,tree),procname(rightchild(tree),key));
elif leftchild(tree) = emptytree then
rightchild(tree);
elif rightchild(tree) = emptytree then
leftchild(tree);
else
child := leftchild(tree);
while(rightchild(child) != emptytree) do
child := rightchild(child);
end do;
BINARYTREE(op(1..2,child),
procname(leftchild(tree),op(1,child)),
rightchild(tree));
end if;
end proc:
end module:

To save this package to your private Maple repository, ensure that the directory in which it is stored appears first among the paths listed in the global variable libname.
After first ensuring that the standard Maple repository is not writable, uncomment the next execution group and execute it. (To uncomment the line, remove the # character.)
>

#savelib( 'BinaryTree', "bsdlib.mla" );



Testing the Package


A short test of the loaded binary tree package shows that the package is still functioning. These commands will produce errors unless you have built the BinaryTree package and included its directory in your libname, as described in the previous sections.
Note that if you have not placed the directory in your initialization file, a restart; will remove it from your libname. To replace it, use:
>

libname := libname, "bsdlib.mla";

>

BinaryTree:insert(BinaryTree:emptytree,2,f(x));

$\left[{2}{\,}{f}{}\left({x}\right){\,}{\,}\right]$
 (8.1) 
>

BinaryTree:insert((8.1),1,g(x));

$\left[{2}{\,}{f}{}\left({x}\right){\,}\left[{1}{\,}{g}{}\left({x}\right){\,}{\,}\right]{\,}\right]$
 (8.2) 
>

BinaryTree:insert((8.2),3,h(x));

$\left[{2}{\,}{f}{}\left({x}\right){\,}\left[{1}{\,}{g}{}\left({x}\right){\,}{\,}\right]{\,}\left[{3}{\,}{h}{}\left({x}\right){\,}{\,}\right]\right]$
 (8.3) 
>

BinaryTree:lookup((8.3),1);

${g}{}\left({x}\right)$
 (8.4) 
$\left[{\mathrm{delete}}{\,}{\mathrm{emptytree}}{\,}{\mathrm{insert}}{\,}{\mathrm{leftchild}}{\,}{\mathrm{lookup}}{\,}{\mathrm{rightchild}}\right]$
 (8.5) 
>

type( emptytree, 'binarytree' );

>

eval(`type/binarytree`);

${\mathbf{proc}}\left({x}\right)\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{if}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathrm{type}}{}\left({x}{\,}{\'}{\mathrm{specfunc}}{}\left({\mathrm{anything}}{\,}{\mathrm{BINARYTREE}}\right){\'}\right)\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{if}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathrm{nargs}}{\=}{1}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{or}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{x}{\=}{\mathrm{emptytree}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{or}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathrm{type}}{}\left({\mathrm{leftchild}}{}\left({x}\right){\,}{\'}{\mathrm{binarytree}}{\'}{}\left({\mathrm{args}}{\[}{2}{\]}\right)\right)\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{and}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathrm{type}}{}\left({\mathrm{rightchild}}{}\left({x}\right){\,}{\'}{\mathrm{binarytree}}{\'}{}\left({\mathrm{args}}{\[}{2}{\]}\right)\right)\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{and}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathrm{type}}{}\left({\mathrm{op}}{}\left({2}{\,}{x}\right){\,}{\mathrm{args}}{\[}{2}{\]}\right)\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{then}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathrm{true}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{else}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathrm{false}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{end\; if}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{else}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathrm{false}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{end\; if}}\phantom{\rule[0.0ex]{0.5em}{0.0ex}}{\mathbf{end\; proc}}$
 (8.7) 
>

insert(emptytree,2,f(x));

$\left[{2}{\,}{f}{}\left({x}\right){\,}{\,}\right]$
 (8.8) 
$\left[{2}{\,}{f}{}\left({x}\right){\,}\left[{1}{\,}{g}{}\left({x}\right){\,}{\,}\right]{\,}\right]$
 (8.9) 
$\left[{2}{\,}{f}{}\left({x}\right){\,}\left[{1}{\,}{g}{}\left({x}\right){\,}{\,}\right]{\,}\left[{3}{\,}{h}{}\left({x}\right){\,}{\,}\right]\right]$
 (8.10) 
${g}{}\left({x}\right)$
 (8.11) 


Updating the Help System


Now that we have created the package, we must document the procedures and update the help browser with entries for the new procedures.
For the moment, assume that you have written five worksheets that document these routines: "lefttree.mw", "insert.mw", "delete.mw", "lookup.mw", and "binarytree.mw".
To create a new help database to store these files in, the HelpTools:Database:Create command is used:
>

HelpTools:Database:Create( "bst.help" ):

The help documentation files can be added to a help database using the makehelp command.
>

makehelp(binarytree[lefttree], "lefttree.mw", "bst.help",
aliases=["binarytree[righttree]"],
browser = ["binarytree,lefttree"]);
makehelp("binarytree[insert]", "insert.mw", "bst.help",
browser = ["binarytree,insert"]);
makehelp("binarytree[delete]", "delete.mw", "bst.help",
browser = ["binarytree,delete"]);
makehelp("binarytree[lookup]", "lookup.mw", "bst.help",
browser = ["binarytree,lookup"]);
makehelp("binarytree", "binarytree.mw", "bst.help",
browser = ["binarytree"]);

You could also use the GUI facilities to save these files into the help system.
Because the Maple help system uses caching, you might need to exit Maple and restart it before your new help pages become visible. Remember to reassign libname when you run Maple again.


Sending Your Package to Other Users


This section provides some brief notes about distributing your package to other users. You may want to share your code or demonstrations, for use by colleagues or students, or for submission to the Maple Application Center.
The easiest way to distribute your package is using a Maple Workbook. A workbook can store your package as well as any associated files. Also, if you have used savelib to save your package into the Workbook, the package workbook can be installed using the PackageTools:Install command  this unpacks the package and its documentation to a folder in Maple's library path.
Inside or outside of a package workbook, you have two main options for distributing your package materials as a collection of files: source form and archive form. Either of these should also work for legacy versions of Maple.
In a source form distribution, you distribute text files (.mpl) or worksheets that contain all of the executable procedures and data for the package. Each file or worksheet should include any savelib statements needed to store the package in a Maple repository. In addition, you should include any help worksheets and a text file or worksheet containing any makehelp commands needed to update the help system. This worksheet is itself an example of a source form distribution, because its execution installs the BinaryTree package. Source form distribution has the advantage, and disadvantage, of easily allowing the receiver of the package to modify it and upgrade it as required. The main disadvantage of a source form distribution is that the receiver must execute all the text files or worksheets before the package is usable.
In an archive distribution, you distribute the contents of the Maple repository directory created after you have loaded all the executable procedures and help pages into the repository. The receiver of such a package need only place the files in a directory and add that directory to libname for it to be usable. While installation is easier, the receiver of such a package has a more difficult time updating the package than if they had received a source distribution.
An important point to remember is that the Maple archive files are binary files, and care must be taken to ensure that they are not corrupted during an archive distribution. Maple source files and worksheets consist of simple ASCII text, and so they can be properly emailed by most systems.
In both cases, it is a good idea to include a simple test worksheet that the receiver can use to check whether the package is correctly installed.
For more information, refer to the following help pages: type, Definition of a structured type in Maple, nargs, index/package, with, savelib, march, libname, macro
, makehelp.

Return to Index for Example Worksheets
