Some Notes on Internal Implementation

Introduction

General issues about the internal implementation of the Wolfram Language are discussed in "The Internals of the Wolfram System". Given here are brief notes on particular features.

It should be emphasized that these notes give only a rough indication of basic methods and algorithms used. The actual implementation usually involves many substantial additional elements.

Thus, for example, the notes simply say that (RefLink[DSolve, paclet:ref/DSolve]) solves second-order linear differential equations using the Kovacic algorithm. But the internal code that achieves this is over 60 pages long, includes a number of other algorithms, and involves a great many subtleties.

Data Structures and Memory Management

A Wolfram Language expression internally consists of a contiguous array of pointers, the first to the head, and the rest to its successive elements.

Each expression contains a special form of hash code that is used both in pattern matching and evaluation.

For every symbol there is a central symbolic table entry that stores all information about the symbol.

Most raw objects such as strings and numbers are allocated separately; however, unique copies are maintained of small integers and of certain approximate numbers generated in computations.

Every piece of memory used by the Wolfram Language maintains a count of how many times it is referenced. Memory is automatically freed when this count reaches zero.

The contiguous storage of elements in expressions reduces memory fragmentation and swapping. However, it can lead to the copying of a complete array of pointers when a single element in a long expression is modified. Many optimizations based on reference counts and pre-allocation are used to avoid such copying.

When appropriate, large lists and nested lists of numbers are automatically stored as packed arrays of machine-sized integers or real numbers. The Wolfram Language compiler is automatically used to compile complicated functions that will be repeatedly applied to such packed arrays. The Wolfram Symbolic Transfer Protocol (WSTP), (RefLink[DumpSave, paclet:ref/DumpSave]), and various (RefLink[Import, paclet:ref/Import]) and (RefLink[Export, paclet:ref/Export]) formats make external use of packed arrays.

Basic System Features

The Wolfram Language is fundamentally an interpreter that scans through expressions calling internal code pointed to by the symbol table entries of heads that it encounters.

Any transformation rule—whether given as x->y or in a definition—is automatically compiled into a form that allows for rapid pattern matching. Many different types of patterns are distinguished and are handled by special code.

A form of hashing that takes account of blanks and other features of patterns is used in pattern matching.

The internal code associated with pattern matching is approximately 250 pages long.

String patterns are implemented using a symbolic extension of the PCRE regular expression library.

When a large number of definitions is given for a particular symbol, a hash table is automatically built using a version of (RefLink[Dispatch, paclet:ref/Dispatch]) so that appropriate rules can quickly be found.

Numerical and Related Functions

Number Representation and Numerical Evaluation

Basic Arithmetic

Pseudorandom Numbers

Number Theoretic Functions

Combinatorial Functions

Elementary Transcendental Functions

Mathematical Constants

Special Functions

Numerical Integration

Numerical Sums and Products

Numerical Differential Equations

Approximate Equation Solving and Optimization

Data Manipulation

Approximate Numerical Linear Algebra

Exact Numerical Linear Algebra

Algebra and Calculus

Polynomial Manipulation

Symbolic Linear Algebra

Exact Equation Solving and Reduction

Exact Optimization

Simplification

Differentiation and Integration

Differential Equations

Sums and Products

Series and Limits

Recurrence Equations

Output and Interfacing

Graphics

Visualization

Front End

Notebooks

Dynamic Evaluation

WSTP

Expression Formatting