Virtual Programming

Abstract

What is the most natural way of composing an algorithm to solve a problem: A number of recent articles advocate: dividing the original problem into subproblems, supposing that we have algorithms for solving the subproblems, describing how these algorithms can be combined into an algorithm for solving the original problem, and repeating this process for the subproblems. For this approach to be feasible we must have powerful ways of describing an algorithm as a combination of other algorithms. We need a powerful algorithmic language. In the first part of this paper we gradually develop such a language SAGA, not intended as a realistic alternative to other algorithmic languages, but rather as a specification of the kind of mechanism a virtual machine should be able to handle efficiently. In the second part we sketch the design of a virtual machine ODIN, in which the mechanisms of SAGA can be implemented efficiently.