Contents Previous Next Index
Internal Representation
The table below lists the structures that are currently implemented in Maple.
Each structure, along with the constraints on its length and contents, is described in the sections that follow.
AND
ASSIGN
BINARY
BREAK
CATENATE
COMPLEX
CONTROL
DCOLON
DEBUG
EQUATION
ERROR
EXPSEQ
FLOAT
FOR
FOREIGN
FUNCTION
GARBAGE
HASH
HASHTAB
HFLOAT
IF
IMPLIES
INEQUAT
INTNEG
INTPOS
LESSEQ
LESSTHAN
LEXICAL
LIST
LOCAL
MEMBER
MODDEF
MODULE
NAME
NEXT
NOT
OR
PARAM
POLY
POWER
PROC
PROD
RANGE
RATIONAL
READ
RETURN
RTABLE
SAVE
SDPOLY
SERIES
SET
STATSEQ
STOP
STRING
SUM
TABLE
TABLEREF
TRY
UNEVAL
USE
XOR
ZPPOLY
Internal Functions
The internal functions in Maple are divided into five groups:
Evaluators
The evaluators are the main functions responsible for evaluation. There are six types of evaluations: statements, algebraic expressions, Boolean expressions, name forming, arbitrary precision floating-point arithmetic, and hardware floating-point arithmetic. The user interface calls only the statement evaluator, but thereafter there are many interactions between evaluators. For example, the statement
if a > 0 then b||i := 3.14/a end if;
is first analyzed by the statement evaluator, which calls the Boolean evaluator to resolve the if condition. Once completed (for example, a true result is returned), the statement evaluator is invoked again to perform the assignment, for which the name-forming evaluator is invoked with the left-hand side of the assignment, and the expression evaluator with the right-hand side. Since the right-hand side involves floating-point values, the expression evaluator calls the arbitrary precision floating-point evaluator.
Normally, you do not specifically call any of the evaluators. However, in some circumstances, when a nondefault type of evaluation is needed, you can directly call evalb (the Boolean evaluator), evaln (the name-forming evaluator), evalf (the arbitrary precision floating-point evaluator), or evalhf (the hardware floating-point evaluator).
Algebraic Functions
Algebraic functions are commonly called basic functions. Some examples are taking derivatives (diff), dividing polynomials (divide), finding coefficients of polynomials (coeff), computing series (series), mapping a function (map), expanding expressions (expand), and finding indeterminates (indets).
Algebraic Service Functions
These functions are algebraic in nature, but serve as subordinates of the functions in the previous group. In most cases, these functions cannot be explicitly called. Examples of such functions are the internal arithmetic packages, the basic simplifier, and retrieval of library functions.
Data Structure Manipulation Functions
These are similar to the algebraic functions, but instead of working on mathematical objects, such as polynomials or sets, they work on data structures, such as expression sequences, sums, products, or lists. Examples of such functions are operand selection (op), operand substitution (subsop), searching (has), and length determination (length).
General Service Functions
Functions in this group are at the lowest hierarchical level. That is, they can be called by any other function in the system. They are general purpose functions, and not necessarily specific to symbolic or numeric computation. Some examples are storage allocation and garbage collection, table manipulation, internal I/O, and exception handling.
Flow of Control
The flow of control does not need to remain internal to the Maple kernel. In many cases, where appropriate, a decision is made to call functions that are written in Maple and are a part of the Maple library. For example, many uses of the expand function are handled in the kernel. However, if an expansion of a sum to a large power is required, the internal expand function calls the external Maple library function 'expand/bigpow' to resolve it. Functions such as diff, evalf, series, and type make extensive use of this feature.
Therefore, for example, the basic function diff cannot differentiate any function. All of that functionality is included in the Maple library in procedures named 'diff/functionName'. This is a fundamental feature of Maple since it permits:
Flexibility (the ability to change the Maple library)
Customization (by defining your refined handling functions)
Readability (much of the Maple functionality is visible at the user level)
Maple allows the kernel to remain small by offloading nonessential functions to the library.
Internal Representations of Data Types
The parser and some internal functions build all of the data structures used internally by Maple. All of the internal data structures have the same general format:
Header
Data1
...
Datan
The header field, stored in one or more machine words, encodes the length of the structure and its type. Additional bits are used to record simplification status, garbage collection information, persistent store status, and various information about specific data structures (for example, whether a for loop contains a break or next statement).
The length is encoded in 26 bits on 32-bit architectures, resulting in a maximum single object size of 67,108,863 words (268,435,452 bytes, or 256 megabytes). On 64-bit architectures, the length is stored in 32 bits, for a maximum object size of 4,294,967,295 words (34,359,738,360 bytes or 32 gigabytes).
Every structure is created with its own length, and that length does not change during the existence of the structure. Furthermore, the contents of most (but not all) data structures are never changed during execution because it is unpredictable how many other data structures are referring to them and relying on them not to change. The normal process for modifying a structure is to copy it and then to modify the copy. Structures that are no longer used are eventually reclaimed by the garbage collector.
The following sections describe each of the structures currently implemented in Maple, along with the constraints on their lengths and contents. The 6-bit numeric value identifying the type of structure is of little interest, so symbolic names will be used.
The notation ^something in the data structure depictions indicates that the value stored in that field of the structure is a pointer to the value (something), rather than being the something itself.
AND: Logical AND
^expr1
^expr2
Maple syntax: expr1 and expr2
Length: 3
ASSIGN: Assignment Statement or Expression
^name-seq
^expr-seq
Maple syntax: name1, name2, ... := expr1, expr2, ...
The left-hand side name entries must evaluate to assignable objects: NAME, FUNCTION, MEMBER or TABLEREF structures, or a sequence thereof. If the left-hand side is a sequence, the right-hand side must be a sequence of the same length.
BINARY: Binary Object
data
Maple syntax: none
Length: arbitrary
The BINARY structure can hold any arbitrary data. It is not used directly as a Maple object, but is used as storage for large blocks of data within other Maple objects (currently only RTABLE structures). It is also sometimes used as temporary storage space during various kernel operations.
BREAK: Break Statement
Maple syntax: break
Length: 1
CATENATE: Name Concatenation
^name
^expr
Maple syntax: name || expr
If the name entry is one of NAME, CATENATE, LOCAL, or PARAM, and if the expr entry evaluates to an integer, NAME, or STRING, the result is a NAME.
If the name entry is a STRING or CATENATE that resolves to a STRING, and if the expr entry evaluates to an integer, NAME, or STRING, the result is a STRING.
If expr is a RANGE, the result is to generate an EXPSEQ of the NAME or STRING structures.
COMPLEX: Complex Value
^re
^im
Maple syntax: Complex(re,im), Complex(im), re + im * I or im * I
Length: 2 or 3
The re and im fields must point to INTPOS, INTNEG, RATIONAL, or FLOAT structures, one of the NAMEs infinity or undefined, or a SUM structure representing -infinity. In the length 3 case, if either re or im is a FLOAT, the other must be a FLOAT as well.
CONTROL: Communications Control Structure
^integer
Length: 2
This is an internal structure used for communication between the kernel and user interface. Such a structure never reaches the user level, or even the mathematical parts of the kernel.
DCOLON: Type Specification or Test
^type-expr
Maple syntax: expr :: typeExpr
This structure has three interpretations depending on the context in which it is used. When it appears in the header of a procedure definition, it is a parameter declaration that has a type. When it appears in the local section of a procedure or on the left-hand side of an assignment, it is a type assertion. When it appears elsewhere (specifically, in a conditional expression), it is a type test.
DEBUG: Debug
Length: 2 or more
This is another structure that is only used internally. It is used by the kernel when printing error traceback information to transmit that information up the call stack.
EQUATION: Equation or Test for Equality
Maple syntax: expr1 = expr2
This structure has two interpretations depending on the context in which it is used. It can be either a test for equality, or a statement of equality (not to be confused with an assignment).
ERROR: Error Statement
Maple syntax: error "msg", arg, ... arg
This structure represents the Maple error statement. The expr is either a single expression (if only a message is specified in the error statement), or an expression sequence (if arguments are also specified). The actual internal tag used for the ERROR structure is MERROR to prevent a conflict with a macro defined by some C compilers.
EXPSEQ: Expression Sequence
Maple syntax: expr1, expr2, ...
Length: 1 or more
An expression sequence is an ordered sequence of expressions. It is most commonly used to construct lists, sets, and function calls. Extracting an expression sequence from a list or set L can be done by using the command op(L). This operation is very efficient as it does not involve creation of a new structure. Similarly, if E is an expression sequence, then constructing a list using [E] involves almost no work and is also very efficient. Constructing a set using {E} requires E to be sorted. A function call data structure is made up of the function name plus the expression sequence of arguments. During evaluation of a function call, the argument sequence gets flattened into one expression sequence. That is, f(E1,E2) is turned into f(e11,e12,...e1n,e21,e22,...e2m) where e1i constitutes the members of the expression sequence E1, and e2i constitutes the members of the expression sequence E2. Thus it is not possible to pass raw expression sequences as arguments to functions. Typically sequences are wrapped in lists, as f([E1],[E2]) in order to keep the element groupings intact. The special value NULL is represented by an empty expression sequence. Thus, [NULL] is equivalent to [], and f(NULL) is equivalent to f().
FLOAT: Software Floating-Point Number
^integer1
^integer2
^attrib-expr
Maple syntax: 1.2, 1.2e3, Float(12,34), Float(infinity)
Length: 2 (or 3 with attributes)
A floating-point number is interpreted as integer1 * 10^integer2. A floating-point number can optionally have attributes, in which case, the length of the structure is 3 and the third word points to a Maple expression. This means that several floating-point numbers with the same value but different attributes can exist simultaneously.
The integer2 field can optionally be one of the names, undefined or infinity, in which case the FLOAT structure represents an undefined floating-point value (not-a-number, or NaN, in IEEE terminology), or a floating-point infinity. When integer2 is undefined, integer1 can accept different small integer values, allowing different NaN values to exist. When integer2 is infinity, integer1 must be 1 or -1.
FOR: For/While Loop Statement
^from-expr
^by-expr
^to-expr
^while-expr
^stat-seq
^until-expr
Maple syntax:
for name from fromExpr by byExpr to toExpr while whileExpr do statSeq end do
for name from fromExpr by byExpr to toExpr while whileExpr do statSeq until untilExpr
^in-expr
for name in inExpr while whileExpr do statSeq end do
for name in inExpr while whileExpr do statSeq until untilExpr
Length: 8 or 6
The name follows the same rules as the name field of the ASSIGN structure, except that it can also be the empty expression sequence (NULL), indicating that there is no controlling variable for the loop.
The from-expr, by-expr, to-expr, while-expr, and until-expr entries are general expressions. All are optional in the syntax of for loops and are therefore be replaced with default values (1, 1, NULL, true, and false respectively) by the parser if omitted.
The stat-seq entry can be a single Maple statement or expression, a STATSEQ structure, or NULL indicating an empty loop body. An additional bit in the header of the FOR structure is used to indicate whether the stat-seq entry contains any break or next statements.
FOREIGN: Foreign Data
This structure is similar to the BINARY structure, except that it is for use by Maple components outside the kernel, such as the user interface. A FOREIGN structure is exempt from garbage collection, and the external component is responsible for freeing this structure when it is finished using it.
FOREIGN data structures can be created and managed in external code by using the MaplePointer API functions. For more information, refer to the OpenMaple,C,MaplePointer help page.
FUNCTION: Function Call
Maple syntax: name( exprSeq )
This structure represents a function invocation (as distinct from a procedure definition that is represented by the PROC structure). The name entry follows the same rules as in ASSIGN, or it can be a PROC structure. The expr-seq entry gives the list of actual parameters; this entry is always an expression sequence (possibly of length 1, which indicates that no parameters are present).
GARBAGE: Garbage
This structure is used internally by the Maple garbage collector as a temporary object type for free space.
HFLOAT: Hardware Float
floatword
Length: 2 on 64-bit architectures; 3 on 32-bit architectures
This structure is used to store a hardware floating-point value. The one or two words (always 8 bytes) after the header store the actual double-precision floating-point value. HFLOAT objects can appear as the result of floating-point computations, I/O operations, or by extracting elements from hardware floating-point RTABLE structures. They look like and are treated as indistinguishable from software FLOAT objects.
IF: If Statement
^cond-expr1
^stat-seq1
^cond-expr2
^stat-seq2
^stat-seqN
if condExpr1 then statSeq1 elif condExpr2 then statSeq2 ... else statSeqN end if
Length: 3 or more
This structure represents the if ... then ... elif ... else ... end if statements in Maple. If the length is even, the last entry is the body of an else clause. The remaining entries are interpreted in pairs, where each pair is a condition of the if or elif clause, followed by the associated body.
IMPLIES: Logical IMPLIES
Maple syntax: expr1 implies expr2
INEQUAT: Not Equal or Test for Inequality
Maple syntax: expr1 < > expr2
This structure has two interpretations, depending on the context in which it is used. It can be either a test for inequality or an inequality statement.
INTNEG: Negative Integer
GMP-integer
Maple syntax: -123
This data structure represents a negative integer of arbitrary precision. For a complete description of the integer representation, including positive integers, see the following section.
INTPOS: Positive Integer
Maple syntax: 123
This data structure represents a positive integer of arbitrary precision. Integers are represented internally in a base equal to the full word size of the host machine. On 32-bit architectures, this base is 4294967296. On 64-bit architectures, the base is 2^64. Integers in this range use the GNU Multiple Precision Arithmetic (GMP) library for integer arithmetic.
Small integers are not represented by data structures. Instead of a pointer to an INTPOS or INTNEG structure, a small integer is represented by the bits of what would normally be a pointer. The least significant bit is 1, which makes the value an invalid pointer (since pointers must be word-aligned). Such an integer is called an immediate integer.
The range of integers that can be represented in this way is -1,073,741,823 to 1,073,741,823 (that is, about +-10^9) on 32-bit architectures, and -4,611,686,018,427,387,903 to 4,611,686,018,427,387,903 (that is, about +-410^18) on 64-bit architectures. (Note that the maximum (non-immediate) integer magnitude in Maple is about 2^2,147,483,488 on 32-bit architectures and 2^274,877,906,688 on 64-bit architectures.)
LESSEQ: Less Than or Equal
Maple syntax: expr1 <= expr2, expr2 >= expr1
This structure has two interpretations, depending on the context. It can be interpreted as a relation (that is, an inequation) or as a comparison (for example, in the condition of an if statement, or the argument to a call to evalb). Maple does not have a greater-than-or-equal structure. Any input of that form is stored as a LESSEQ structure.
LESSTHAN: Less Than
Maple syntax: expr1 < expr2, expr2 > expr1
Similar to the LESSEQ structure above, this structure has two interpretations, depending on the context. It can be interpreted as a relation (that is, an inequation), or as a comparison (for example, in the condition of an if statement, or the argument to a call to evalb).
Maple does not have a greater-than structure. Any input of that form is stored as a LESS structure.
LEXICAL: Lexically Scoped Variable within an Expression
integer
Maple syntax: name
This represents an identifier within an expression in a procedure or module that is not local to that procedure, but is instead declared in a surrounding procedure or module scope. The integer field identifies which lexically scoped variable of the current procedure is being referred to. The integer, multiplied by 2, is an index into the lexical-seq structure referred to by the PROC DAG of the procedure. Specifically, |integer| * 2 - 1 is the index to the NAME of the identifier, and |integer| * 2 is the index to a description (LOCAL, PARAM, or LEXICAL) relative to the surrounding scope. The value of integer can be positive or negative. If integer is a positive value, the original identifier is a local variable of a surrounding procedure; if integer is a negative value, it is a parameter of a surrounding procedure.
LIST: List
Maple syntax: [ expr, expr, ... ]
The elements of the expr-seq are the elements of the list. The list can optionally have attributes.
LOCAL: Local Variable within an Expression
This structure indicates a local variable when it appears within an expression in a procedure or module. The integer is an index into the procedure local-seq. At procedure execution time, it is also an index into the internal data structure storing the active locals on the procedure activation stack, and stores private copies of the NAMEs of the local variables (private copies in the sense that these NAMEs are not the same as the global NAMEs of the same name).
MEMBER: Module Member
^module
Maple syntax: module:-name
This structure represents a module member access in an expression. MEMBER objects typically do not persist when a statement is simplified. Instead, they are replaced by the actual member that they refer to (an instance of a NAME).
MODDEF: Module Definition
param-seq
local-seq
option-seq
export-seq
stat-seq
desc-seq
global-seq
lexical-seq
mod-name
static local-seq
static export-seq
static name-seq
module modName ( ) description d1, d2, ...; local l1, l2, ...; local sl1::static, sl2::static, ...; export e1, e2, ...; export se1::static, se2::static, ...; global g1, g2, ...; option o1, o2, ...; statSeq end module
Length: 13
The parameter sequence (param-seq), which occurs between the parentheses after modName, points to an expression sequence describing the formal parameters of the module. Currently, Maple does not support parameterized modules, so this field always points to the sequence containing only an instance of the name thismodule.
The local sequence (local-seq) points to an expression sequence listing the explicitly and implicitly declared local variables. Each entry is a NAME. The explicitly declared variables appear first. Within the module, locals are referred to by LOCAL structures, the local variable number being the index into the local sequence. The instances of these names appear in the MODULE structure.
The export sequence (export-seq) points to an expression sequence listing the exported module members. Each entry is a NAME. Within the module, exports are referred to by LOCAL structures, the local variable number being the number of elements in the local sequence, plus the index into the export sequence. The instances of these names appear in the MODULE structure.
The option sequence (option-seq) points to an expression sequence of options to the module (for modules, options are the same as attributes). Each entry is a NAME or EQUATION specifying an option. Typical options are package, load=... and unload=...
The statement sequence (stat-seq) field points to a single statement or a statement sequence (STATSEQ). If the module has an empty body, this is a pointer to NULL instead.
The description sequence (desc-seq) field points to an expression sequence of NAMEs or STRINGs. These sequences are meant to provide a brief description of what the module does and are displayed even when the value of interface(verboseproc) is less than 2.
The global sequence (global-seq) field points to a list of the explicitly declared global variables in the module (those that appeared in the global statement). This information is never used at run time, but is used when simplifying nested modules and procedures to determine the binding of lexically scoped identifiers (for example, an identifier on the left-hand side of an assignment in a nested procedure can be global if it appears in the global statement of a surrounding context). This information is also used at printing time, so that the global statement contains exactly the global identifiers that were declared originally.
The lexical sequence (lexical-seq) field points to an expression sequence of links to identifiers in the surrounding scope, if any. The sequence consists of pairs of pointers. The first pointer of each pair is to the globally unique NAME of the identifier; this is needed at simplification and printing time. The second pointer is a pointer to a LOCAL, PARAM, or LEXICAL structure which is understood to be relative to the surrounding scope. When a module definition is evaluated, the lexical sequence is updated by replacing each of the second pointers with a pointer to the actual object represented. The name pointers are not modified, so that the actual identifier names are still available. The lexical-seq for a module contains entries for any surrounding-scope identifiers used by that module or by any procedures or modules contained within it.
The module name (mod-name) field points to the optional name of the module. If a module name is specified when the module is declared, the name appears there. If no module name is specified, this field will contain a value of NULL.
The static local-seq points to an expression sequence listing the local variables that were explicitly declared as :static. Each entry is a NAME. Within the module, static locals are referred to by LOCAL structures, the local variable number being the index into the static local-seq minus the number of nonstatic locals and exports. A static local shares its value among all instances of a class.
The static export-seq points to an expression sequence listing the exported module members declared as static. Each entry is a NAME. Within the module, exports are referred to by LOCAL structures, the local variable number being the number of elements in the local-seq, static local-seq, and export-seq, plus the index into the static export-seq.
The static name-seq stores the instances of the static locals and exports. It appears in the MODDEF structure as these static variables are shared among all modules with the same definition.
MODULE: Module Instance
^export-seq
^mod-def
^local-seq
Length: 4
Executing a module definition (MODDEF) results in a module instance. Each local or exported member of the module is instantiated and belongs to that instance of the module. The export-seq field points to an expression sequence of names of the instantiated exports (as opposed to the global names, as stored in the module definition). The mod-def field points back to the original module definition. The local-seq field points to an expression sequence of names of the instantiated local variables of the module.
NAME: Identifier
^assigned-expr
characters
Length: 4 or more
The assigned-expr field points to the assigned value of the name. If the name has no assigned value, this field is a null pointer (not a pointer to NULL). The next field points to an expression sequence of attributes of the name. If there are no attributes, this field points to the empty expression sequence (NULL). The remaining fields contain the characters that form the name, stored 4 or 8 for each machine word (for 32-bit and 64-bit architectures respectively). The last character is followed by a zero-byte. Any unused bytes in the last machine word are also zero. The maximum length of a name is 268,435,447 characters on 32-bit architectures and 34,359,738,351 characters on 64-bit architectures.
NEXT: Next Statement
Maple syntax: next
NOT: Logical NOT
Maple syntax: not expr
OR: Logical OR
Maple syntax: expr1 or expr2
PARAM: Procedure Parameter in an Expression
This structure indicates a parameter when it appears in a procedure. The integer is an index into the procedure param-seq. Several special PARAM structures exist:
0
This structure represents the Maple symbol _npassed (formerly nargs), the number of arguments passed when the procedure was called.
-1
This structure represents the Maple symbol _passed (formerly args), the entire sequence of arguments passed when the procedure was called.
-2
This structure represents the Maple symbol procname, referring to the currently active procedure.
-3
This structure represents the Maple symbol _nresults, the number of results expected to be returned from the procedure.
-4
This structure represents the Maple symbol _params, the sequence of declared positional arguments passed when the procedure was called.
-5
This structure represents the Maple symbol _nparams, the number of declared positional arguments passed when the procedure was called.
-6
This structure represents the Maple symbol _rest, the sequence of undeclared arguments passed when the procedure was called.
-7
This structure represents the Maple symbol _nrest, the number of undeclared arguments passed when the procedure was called.
