J. Michael Spivey

Combinatorial search strategies including depth-first, breadth-first and depth-bounded search are shown to be different implementations of a common algebraic specification that emphasizes the compositionality of the strategies. This specification is placed in a categorical setting that combines algebraic specifications and monads.

We show how combinatorial search strategies including depth-first, breadth-first and depth-bounded search can be viewed as different implementations of a common algebraic specification that emphasises the compositionality of the strategies. This specification is placed in a categorical setting that combines algebraic specifications and monads.

Existing methods for call graph profiling, such as that used by gprof, deal badly with programs that have shared subroutines, mutual recursion, higher‐order functions, or dynamic method binding. This article discusses a way of improving the accuracy of a call graph profile by collecting more information during execution, without significantly increasing the overhead of profiling. The method is based on keeping track of a context, consisting of the set of subroutines that are active at a particular moment during execution, together with the calling arcs between these subroutines. The profiler records the time spent in each context during execution of the program, and thus obtains an accurate measurement of the total time during which each subroutine was active. By recording arc information for only the most recent activation of each subroutine, it is possible to arrange that even recursive programs give rise to a finite number of these contexts, and in typical real programs, the number of distinct contexts remains manageably small. The data can be collected efficiently during execution by constructing a finite‐state machine whose states correspond to contexts, so that when a context is entered for a second or subsequent time, only a single access of a hash table is needed to update the state of the profiling monitor. Copyright © 2003 John Wiley & Sons, Ltd.