In computer science, run-time algorithm specialization is a methodology for creating efficient algorithms for costly computation tasks of certain kinds. The methodology originates in the field of automated theorem proving and, more specifically, in the Vampire theorem prover project.

The idea is inspired by the use of partial evaluation is fixed for potentially many different values of.

The specialized algorithm may be more efficient than the generic one, since it can exploit some particular properties, unroll loops and recursion, etc.

Difference from partial evaluation

is specialised are not known statically, so the specialization takes place at run-time.

. We only have to imagine when we program. An important advantage of doing so is that we can use some powerful ad hoc, which are beyond the reach of any universal specialization methods.

Specialization with compilation

The specialized algorithm has to be represented in a form that can be interpreted.

can be written as machine code instructions for a special abstract machine is compiled. The code itself can then be additionally optimized by answer-preserving transformations that rely only on the semantics of instructions of the abstract machine.

The instructions of the abstract machine can usually be represented as recordss. One field of such a record, an instruction identifier (or instruction tag), would identify the instruction type, e.g. an integer field may be used, with particular integer values corresponding to particular instructions. Other fields may be used for storing additional parameters of the instruction, e.g. a pointer field may point to another instruction representing a label, if the semantics of the instruction require a jump. All instructions of the code can be stored in a traversable data structure such as an array, linked list, or tree.

Interpretation (or execution) proceeds by fetching instructions in some order, identifying their type, and executing the actions associated with said type.

In many programming languages, such as C and C++, a simple switch statement may be used to associate actions with different instruction identifiers. Modern compilers usually compile a switch-th cell of a special array, as a means of efficient optimisation. This can be exploited by taking values for instruction identifiers from a small interval of values.

Data-and-algorithm specialization

, intended to do the same job faster.

See also

• Psyco, a specializing run-time compiler for Python

• multi-stage programming

References

• A. Voronkov, "The Anatomy of Vampire: Implementing Bottom-Up Procedures with Code Trees", (original idea)

Further reading

• A. Riazanov and A. Voronkov, "Efficient Checking of Term Ordering Constraints", Proc. IJCAR 2004, Lecture Notes in Artificial Intelligence 3097, 2004 (compact but self-contained illustration of the method)

• A. Riazanov and A. Voronkov, Efficient Instance Retrieval with Standard and Relational Path Indexing, Information and Computation, 199(1-2), 2005 (contains another illustration of the method)

• A. Riazanov, "Implementing an Efficient Theorem Prover", PhD thesis, The University of Manchester, 2003 (contains the most comprehensive description of the method and many examples)