Polyvariant mixed computation for analyzer programs (Q796970)

The two major characteristics of mixed computation - termination and depth - are, in general, conflicting. A class of low-level nonstructured programs with fixed partition of the memory into accessible and suspended parts is considered. The further assumption is that, for any fixed partial input data, all the variety of computation generates a finite set of accessible memory states. Under these assumptions a polyvariant mixed computation algorithm is presented which performs all nonsuspended computation and always terminates. The basic idea is to put into correspondence to every accessible memory state its own copy of the initial program. Then the control flow of this multiple program is rearranged in such a way that if a program instruction which corresponds to an accessible memory state S computes a memory state S' then it appoints its successor in the program copy which corresponds to the state S'. The huge resulting program is called a resultant. The residual program is obtained from the resultant through a sequence of abundant reductions which delete all computation over accessible memory and all unreachable instructions. An iterative version of the mixed computation algorithm is also offered when only reachable instructions over actually computed memory states emerge. The general treatment is supplemented by a series of examples demonstrating useful properties of the mixed computation algorithm. One of those is embedding a control structure into the residual program which is not explicitly presented in the initial program but is encoded in the input data.