Using the Open Maple application program interface (API), the ExternalCalling module, a C compiler, and some basic understanding of the Maple data structure format, you can create Maple utilities that run nearly as fast as Maple builtin procedures.
To show how this is done, I will start with a simple example and then proceed to a slightly more complex procedure that improves ?ListTools[SearchAll].
For the simple example, we create a procedure that returns the number of elements in a list. Because there is already a Maple builtin, nops, for this purpose, this is for demonstration only.
We will need to access the internal data structure used to represent a Maple list. Appendix A of the Maple Advanced Programming Guide describes this structure. A list has the representation
LIST ^expr-seq ^attr-seq
where LIST is a header that identifies this structure as a list, ^expr-seq is a pointer to a Maple expression sequence structure, and ^attr-seq is a pointer to Maple attribute sequence. An expression sequence has the structure
EXPSEQ ^expr1 ^expr2 ^expr3 ...
where EXPSEQ is a header that identifies this structure as an expression sequence, and ^expr1, ^expr2, etc, are pointers to the elements of the sequence. The header EXPSEQ, in addition to identifying the structure as an expression sequence, contains additional information about the structure, including how many expressions are in the sequence. We could extract that number from the header, however, there is an OpenMaple function, MapleNumArgs, that does that, so we will call it. Here is the C code for our first procedure. It is stored in a text file, ListToolBox.c
/*---- begin ListToolBox.c ---- */
#include <maplec.h>
#include <stdio.h>
#include <stdlib.h>
ALGEB NumElements( MKernelVector kv, ALGEB args )
{
ALGEB L;
if ( MapleNumArgs(kv, args) != 1 )
MapleRaiseError(kv, "expected exactly one argument");
L = (ALGEB) args[1];
if ( ! IsMapleList(kv, L) )
MapleRaiseError(kv, "argument is not a list");
return ToMapleInteger(kv, MapleNumArgs(kv, (ALGEB) L[1]));
}
/* ---- end ListToolBox.c --- */
A few comments are in order. The argument list of this function is typical. The kv argument is a pointer to a structure that permits accessing the Maple kernel; that is needed to access the various Open Maple function. The args argument is a pointer to the sequence of arguments passed to the function. Here we expect the sequence to contain one item, a list.
The first conditional verifies that args does, indeed, point to an expression sequence with one element. The next conditional verifies that that element is a list.
After verifying the arguments, we use MapleNumArgs to return the number of elements in the expression sequence, which is pointed to by L[1]. That call returns a machine integer. ToMapleInteger is used to convert that integer to a Maple integer, which is returned by the procedure.
The following Maple script, stored in ListToolBox.mpl, assigns a Maple package, ListToolBox, which is used to create the Maple archive ListToolBox.mla.
# ---- begin ListToolBox.mpl ---
$define EXPORTS NumElements, SearchAll
ListToolBox := module()
export EXPORTS;
local ModuleLoad;
option package;
ModuleLoad := proc()
local lib, ex;
uses ExternalCalling;
lib := ExternalLibraryName("ListToolBox");
for ex in [EXPORTS] do
proc(ex)
unprotect(ex);
ex := DefineExternal('ex',lib)
end proc(ex);
end do;
return NULL;
end proc;
end module:
LibraryTools:-Save('ListToolBox', "ListToolBox.mla");
done
# --- end ListToolBox.mpl ---
I'm a Linux user and use the following Makefile to both build and install the shared object file and the Maple archive.
# --- begin Makefile ---
#
# Makefile to build and install the shared library
# and Maple archive for ListToolBox
pkg := ListToolBox
shared_lib := lib$(pkg).so
# Maple tty executable
maple := maple
MAPLE_ROOT := $(shell $(maple) -q -c 'printf("%A\n",kernelopts(mapledir))' -cdone)
MAPLE_BIN := $(shell $(maple) -q -c 'printf("%A\n",kernelopts(bindir))' -cdone)
BIN_SYS := $(notdir $(MAPLE_BIN))
# Compile
CC := gcc
CPPFLAGS := -I . -I $(MAPLE_ROOT)/extern/include
CCOPT := -O
CCDEBUG :=
CCSHFLAGS := -fPIC
CFLAGS := $(CPPFLAGS) $(CCDEBUG) $(CCOPT)
%.o: %.c
$(CC) -c $(CCSHFLAGS) $(CFLAGS) $+ -lmaplec -L$(MAPLE_BIN)
# Link
LD := ld
LDSHFLAGS := -shared
LDFLAGS :=
LDLIBS := --library=maplec
OUTPUT := -o
LIBS := -L $(MAPLE_BIN)
DSO := $(shared_lib)
lib%.so: %.o
$(LD) $(LDSHFLAGS) $(LDFLAGS) $(OUTPUT) $(DSO) $+ $(LIBS) $(LDLIBS)
default: $(pkg).mla $(shared_lib)
install_dir := ${HOME}/maple/toolbox/$(pkg)
installed_so := $(install_dir)/$(BIN_SYS)/$(shared_lib)
installed_mla := $(install_dir)/lib/$(pkg).mla
install: $(installed_so) $(installed_mla)
$(installed_so): $(shared_lib)
$(RM) $@
install -d $(dir $@)
install -t $(dir $@) $+
$(pkg).mla: $(pkg).mpl
$(RM) $@
$(maple) -q $+
$(installed_mla): $(pkg).mla
install -d $(dir $@)
install -t $(dir $@) $+
# Clean up
clean:
$(RM) $(pkg).o
cleanall: clean
$(RM) lib$(pkg).so $(installed_so) $(installed_mla)
uninstall: cleanall
$(RM) -r $(install_dir)
.phony: clean cleanall check-syntax default install uninstall zip
check-syntax:
$(CC) -o nul -S ${CHK_SOURCES}
zip:
zip $(pkg).zip $(pkg).c $(pkg).mpl Makefile
# --- end Makefile ---
At a shell prompt,
$ make install
should do all the work. With that done, we can fire up Maple and test the procedure.
(**) with(ListToolBox);
[NumElements]
(**) NumElements([]);
0
(**) NumElements([1,2,3]);
3
# Now check the error messages
(**) NumElements(a,b);
Error, (in ListToolBox:-NumElements) expected exactly one argument
(**) NumElements(a);
Error, (in ListToolBox:-NumElements) argument is not a list
Success.
We now look at creating a useful tool, a more efficient implementation of the Maple package export ListTools[SearchAll], which returns all positions in a list whose corresponding element matches a given target element. As previously discussed, the SearchAll algorithm has a significant flaw: it is worst-case O(n^2) when all elements in the list match the target.
It is easy enough to rewrite the procedure so that is worst-case O(n), however, the resulting interpreted Maple code is slower for the typical case when the number of matching elements is small. To achieve substantially better performance, we need to use a compiled procedure.
What makes SearchAll interesting, besides being a useful procedure, is that we need to temporarily store all the matches found. Here I do so by inserting the matching positions into a linked list. After the search is complete, a Maple expression sequence is allocated and the elements in the linked list are transferred to the expression sequence. The memory allocated for the linked list is then freed.
Following is the additional C code that is appended to ListToolBox.c to assign SearchAll. You will note that a different calling convention is used for the Maple API functions. That is, rather than FunctionName(kv, arg1, arg2, ... ) I used kv->functionName(arg1, arg2, ... ). The function names are slightly different---the general rule is that an initial Maple is elided and the first character is lower case. There are exceptions; you should be able to figure out the equivalents by perusing the mplshlib.h file which is in your Maple distribution in the extern/include directory. The primary motivation for using this convention is that it allows access to the function allocALGEB, which, alas, is not included in the documented OpenMaple API. That function was used to allocate a Maple expression sequence for the returned argument. MapleListAlloc could have been used, but I prefer to return a sequence to be compatible with the existing ListTools:-SearchAll procedure. The reason for converting all the calls was that I hoped that would make the one case where it was necessary easier to understand.
/* --- begin addendum to ListToolBox.c ---*/
/* Define the linked-node structure */
struct node {
M_INT index;
struct node *next;
};
ALGEB SearchAll( MKernelVector kv, ALGEB args )
{
/*
A fast replacement for ListTools:-SearchAll.
*/
M_INT cnt,i,n;
ALGEB e,L,E,eseq;
struct node *root, *tmp;
if ( kv->numArgs(args) != 2)
kv->error("expected exactly two arguments");
e = (ALGEB)args[1];
L = (ALGEB)args[2];
if ( ! kv->isMapleList(L) )
kv->error("second argument must be a list");
E = (ALGEB)L[1];
/* The algorithm is simple, search E from beginning to end.
For each match, add a node to a linked list; the content
of the node is the index [of the list]. When complete, the
linked list consists of
root --> i[cnt] --> i[cnt-1] --> ... --> i[1].
*/
n = kv->numArgs(E);
root = NULL;
cnt = 0;
/* Search E, create and link a node for each match, and increment cnt */
for ( i = 1; i <= n; i++ ) {
if ((ALGEB)E[i] == e ) {
cnt++;
tmp = malloc(sizeof(struct node));
if ( tmp == NULL )
kv->error("could not allocate memory" );
tmp->index = i;
tmp->next = root;
root = tmp;
}
}
/* Allocate an exprseq that stores cnt indices */
eseq = kv->allocALGEB( 1+cnt, MAPLE_EXPSEQ );
/* Fill the exprseq and free the memory */
while ( root != NULL ) {
((ALGEB *)eseq)[cnt--] = kv->toMapleInteger( root->index );
tmp = root->next;
free( root );
root = tmp;
}
return eseq;
}
/* --- end addendum to ListToolBox.c --- */
The only modification needed for ListToolBox.mpl is to append this procedure name to the definition of EXPORTS:
$define EXPORTS NumElements, SearchAll
Now, after rerunning make install, we can test this procedure and compare its performance to ListTools:-SearchAll:
# Test ListToolBox:-SearchAll
(**) with(ListToolBox):
(**) kernelopts('printbytes'=false):
# Verify basic operation
(**) evalb(SearchAll(0, [1,2,3]) = NULL);
true
(**) evalb(SearchAll(1, [1,2,3,1,2,1]) = (1,4,6));
true
# Compare with ListTools:-Searchall:
# worst-case performance comparison (all matches)
(**) L := [1$10^4]:
(**) CodeTools:-Usage(SearchAll(1, L), 'output=[realtime]', 'quiet');
0.002
(**) CodeTools:-Usage(ListTools:-SearchAll(1, L), 'output=[realtime]', 'quiet');
1.193
# best-case performance comparison (no matches)
(**) L := [1$10^7]:
(**) CodeTools:-Usage(SearchAll(0, L), 'output=[realtime]', 'quiet');
0.120
(**) CodeTools:-Usage(ListTools:-SearchAll(0, L), 'output=[realtime]', 'quiet');
0.278
This demonstrates that the best-case performance is somewhat better than that of ListTools:-SearchAll, and the worst-case performance is substantially better.
Download this zipfile to get ListToolBox.c, ListToolBox.mpl, and the Makefile:
ListToolBox.zip
