The internal data structures used to represent and manipulate symbolic data are crucial for efficiency. A straightforward data structure closely models the expression tree: ab+cd would be represented as in Figure 6(a).
Maple uses directed acyclic graphs (DAGs) to represent arbitrary expressions. While similar to the tree structure, they have the additional property that all common subexpressions are identified and stored only once. Thus, Figure 6(a) would be represented as Figure 6(b). Since subexpressions are shared, all expressions must now be nonmutable and changing an expression always involves a copy operation. Even so, the reduced memory consumption and the ability to apply recursive operations only once to each unique subexpression, make processing complex symbolic expressions a much more efficient operation. Maple uses DAGs to represent arbitrary-size integers, arbitrary-precision floating-point numbers, rational numbers, lists, sets, polynomials, matrices, and more. Even procedures written using Maple's programming language are stored as DAGs.
-- L.B.
Back to Article