PROSE modeling language

From Wikipedia, the free encyclopedia
Jump to: navigation, search

PROSE[1][2][3][4] was the mathematical 4GL virtual machine which established the holistic modeling paradigm known as Synthetic Calculus[5][6][7] (AKA MetaCalculus). A successor to the SLANG[8]/CUE[9] simulation and optimization language developed at TRW Systems, it was introduced in 1974 on Control Data supercomputers. It was the first commercial language[10][11][12][13] to employ automatic differentiation (AD), which was optimized to loop in the instruction-stack of the CDC 6600 CPU.

Although PROSE was a rich block-structured procedural language, its focus was the blending of simultaneous-variable mathematical systems such as:

  • implicit non-linear equations systems,
  • ordinary differential-equations systems, and
  • multidimensional optimization.

Each of these kinds of system models were distinct and had operator templates to automate and solve them, added to the procedural syntax. These automated system problems were considered "holistic" because their unknowns were simultaneous, and they could not be reduced in formulation to solve piecewise, or by algebra manipulation (e.g. substitution), but had to be solved as wholes. And wholeness also pertained to algorithmic determinacy or mathematical "closure", which made solution convergence possible and certain in principle, if not corrupted by numerical instability.

Holarchies of Differential Propagation[edit]

Since these holistic problem models could be independently automated and solved due to this closure, they could be blended into higher wholes by nesting one inside of another, in the manner of subroutines. And users could regard them as if they were ordinary subroutines.

Yet semantically, this mathematical blending was considerably more complex than the mechanics of subroutines, because an iterative solution engine was attached to each problem model by its calling operator template above it in the program hierarchy. In its numerical solution process, this engine would take control and would call the problem model subroutine iteratively, not returning to the calling template until its system problem was solved. During some or maybe all of the iterative model-subroutine calls the engine would invoke automatic differentiation of the formulas in the model holarchy with respect to the model's input-unknowns (arguments) defined in the calling template. Additional mechanisms were performed in the semantics to accommodate ubiquitous nesting of these holistic models.

Differentiation of Prediction Processes[edit]

If the nested solution was a prediction (e.g. numerical integration), then its solution algorithm, in addition to the model formulas, would also be automatically differentiated. Since this differentiation propagated (via the chain rule) throughout the integration from initial conditions to boundary conditions, the differentiation of boundary conditions with respect to initial conditions (so called Frechet derivatives) would be performed. This enabled the routine solution of boundary-value problems by iterative "shooting" methods using Newton-method engines. Of course, at the same time this propagated differentiation could also be performed with respect to arbitrary parameters of the differential equations to further shape the integrated functions. And these parameters could be solved for as unknowns of any nest in the holarchy above the integration process, a significant convenience in overall problem formulation.

Differentiation of Search Processes[edit]

If the inner nested problem was a search, and the outer problem was also a search (e.g. optimization), then the partial derivatives produced with respect to the inner-search unknowns had to be converted into partial derivatives of the outer search via a differential-geometry coordinate transformation. This was also an iterative process involving higher order differentiation and sometimes different independent variables.

Yet these extended and iterative differential-arithmetic processes were totally hidden from the user, and were hardly more significant in his modeling task than if only ordinary subroutines and their calls were involved. The fact that they were iterative and the number and kind of iterations were indefinite, because a whole sub-problem was being solved which was also a part of a higher problem, it was natural to call each problem nest a "holon", as this dynamic entity perfectly fitted the theory of Arthur Koestler who coined that term. This was not done in the original PROSE documentation, because in those years, Koestler's theory was new, and somewhat controversial. This term was later used after Ken Wilber had ratified Koestler's holon concepts.

Automation Operator Templates[edit]

The complete modeling paradigm consisted of only three classes of holons, as distinguished by their operator templates below.

Optimization[edit]

FIND simultaneous-unknowns IN model-subroutine BY solver-engine
[HOLDING inequality-constraint-variables]
[MATCHING equality-constraint-variables]
TO MAXIMIZE|MINIMIZE objective-variable

Correlation[edit]

FIND simultaneous-unknowns IN model-subroutine BY solver-engine
TO MATCH equality-constraint-variables

Simulation[edit]

INITIATE solver-engine FOR model-subroutine EQUATIONS rate-variables/level-variables
OF independent-variable STEP increment-variable TO limit-variable
INTEGRATE model-subroutine BY solver-engine

These three operator templates created dynamic holons encapsulating an equations model subroutine hierarchy which could contain other nested holons, because the model subroutines could contain any of the operator templates encapsulating sub-problems. Each holon in the holarchy had a solver algorithm engine, which could be interchanged with others in its holon class. The extended arithmetic of automatic differentiation and its ability to dynamically differentiate numerical integration gave rise to the unique mode of holarchy modeling illustrated in Figure 1.

Figure 1. Calculus of Variations Application[14]

This example problem was originally a FORTRAN application from a RAND report about an algorithm used for optimization of boundary-value problem applications. This report, also published as a textbook,[14] described Quasilinearization, an alternative to "dynamic programming", invented by the same author, Richard Bellman. The FORTRAN program in Appendix Two of the textbook contains over five times the amount of code as the 25-line PROSE program, entirely embedded in the white boxes (visible syntax) of Figure 1. More significant in this modeling versus programming discussion is that the FORTRAN program contains 14 DO loops, whereas the PROSE program contains no loops. Another point to make about program simplification is that dynamic memory management could be taken for granted by the user. At the return from a holon to its calling operator template, the holon was destroyed and its memory was freed for other use.

This application is actually trivial in the amount of code required to state the problem. That is why the PROSE program is so small. All of its iterative solution methodology is under the hood in the solver engines (ellipses in Figure 1). Models seldom need loops. This is why spreadsheets, which are modeling tools, don't even have them.

This example problem provides a full encapsulation of the holon paradigm in a single application. All three of its holon types are employed: optimization searching at the highest level of the holarchy, correlation searching (a restricted subset of optimization searching) as the middle holon, and system dynamics simulation as the innermost holon. Another PROSE program with this same anatomy is illustrated in Figure 2. This is a somewhat larger application of the optimization of a cantilevered wing structure to maximize lift, subject to structure and weight constraints. In this case there are ten coordinate dimensions of the optimization unknowns that are being searched by the outer holon solver.

Figure 2. Wing Design Optimization Problem[7]

The two outer holons each has a hidden coordinate system of unknowns that its search engine solves for. And these engines require partial derivatives of all downstream variables dependent upon those unknowns, which are evaluated by automatic differentiation arithmetic. The derivatives of the outer coordinate system must be computed from the derivatives of the inner coordinate system, after the inner search engine has converged (found a local solution). This is where a differential-geometry coordinate transformation is applied. The wing problem of Figure 2 has more downstream subprograms, not shown, including an integral quadrature function.

As these subprograms include the numerical integration of the system dynamics (differential equations) model, the automatic differentiation arithmetic includes differentiation of the integration algorithm of the simulation engine (and the quadrature solver), to evaluate derivatives of the boundary (end-point of the integrated curves) conditions with respect to the initial conditions. This calculation is not possible via formal symbolic differentiation. Nor is it feasible with finite difference approximation. Only automatic differentiation, with its exact chain-rule propagation is feasible.

Automated Holon Architecture[edit]

Figure 3. Generalized Holon Architecture[2]

Figure 3 shows the generalized architecture of a holon in profile, showing the visible modeling syntax and the invisible semantics architecture with its characteristic 5-step iteration process. A holon is a calculus problem-solving unit, mathematically associated with a coordinate system dynamically created by the operation template. Its operator is a solver engine, either a numerical predictor in the case of simulation, or a search engine in the case of correlation and optimization. Its operand is a model procedure (which may itself be a holarchy of subordinated holons).

In essence a holon is a metaphoric computation container like a spreadsheet, but allowing procedural looping like an ordinary algebraic language. Yet its purpose is to frame algebraic formulas that represent higher mathematics (e.g. differential equations are algebraic formulas, in which some of their variables are rates).

Figures 4-7 show how the different holon classes of simulation, correlation, and optimization reflect this architecture, separating modeling (science equations) from algorithmic solver engines of the art of numerical approximation mathematics.

Figure 4. Simulation Holon[2]
Figure 5. Correlation Holon[2]
Figure 6. Unconstrained Optimization Holon[2]
Figure 7. Constrained Optimization Holon[2]

Holons are formula-system solution processes[edit]

As mentioned above, a Holon is a computation container like a spreadsheet that encapsulates a set of input algebraic formulas. But unlike a spreadsheet, these formulas are parts of an irreducible whole which can only be solved together as a unit, involving a succession of approximations (iterations). A spreadsheet, which only involves a single pass of formula calculations, may therefore be thought of as a "degenerate" or "reduced" holon, one that only involves single-pass calculations.

A holon model elevates an encapsulated system of algebraic formulas to a higher problem archetype relating simultaneous unknowns to a definable solution condition other than a single pass through the set of formulas. Iterative calculus "under the hood" is required to "converge" multiple-pass approximations to the solution condition.

Metaphoric Problem Archetypes[edit]

Each holon automates one of the three system-problem archetypes that have emerged from higher math with a distinct class of solution methods, applicable as interchangeable operators. These methods operate on the input formulas and their calculations, to guide the successive approximations to the holon solution. These problem archetypes easily precipitate out of the formula collections that represent modeling of natural phenomena, and can be used as building blocks to synthesize whole computation programs as holarchies of sequential or nested holons. Used together as an alphabet these archetypal problems become a topology of higher math modeling within an algebraic programming language containing special semantic "glue" methodologies which propagate calculus "influence" through the collections of holons.

As the holons combine to form greater wholes via alphabetic combination, such holarchies also tend to become problem archetypes, which often precipitate out of natural phenomena modeling. Examples are boundary-value problems, solved by the combination of correlation and simulation holons.

PROSE Pantheon[edit]

PROSE introduced a pantheon of interchangeable solvers named for mythical gods in the three engine categories:

Optimization[edit]

  • HERA - an advanced version of Newton's second-order gradient method with special logic to recognize and avoid unwanted extrema during its search process;
  • HERCULES - a special constrained optimization solver for linear, integer, and mixed-integer problems;
  • JOVE - a sequential unconstrained optimization technique applying Newton's second-order gradient search;
  • JUPITER - a moving exterior truncations penalty-function method applying a Davidon-Fletcher-Powell (DFP) variable-metric search;
  • THOR - a "sectionally linearized" linear programming technique; and
  • ZEUS - a sequential unconstrained optimization technique applying a Davidon-Fletcher-Powell (DFP) variable-metric search.

Correlation[edit]

  • AJAX - a damped Newton-Raphson and Newton-Gauss pseudo-inverse root finder; and
  • MARS - a damped Newton-Raphson and Newton-Householder pseudo-inverse root finder.

System-Dynamics Simulation[edit]

  • ATHENA - multi-order Runge-Kutta with differential propagation and optional limiting of any output dependent variables;
  • GEMINI - self-starting technique of rational function extrapolation from Gragg, Bulirsch, and Stoer with differential propagation or not according to context;
  • ISIS - Runge-Kutta-Gill with differential propagation;
  • JANISIS - ISIS or JANUS, depending on differential or non-differential-propagating contexts;
  • JANUS - Adams-Moulton predictor-corrector for non-differential-propagating contexts;
  • MERCURY - Gears rate/state differentiating stiff and step-size optimizing method for non-differential-propagating contexts;
  • MERLIN - self-starting technique of rational function extrapolation from Gragg, Bulirsch, and Stoer with differential propagation;
  • MINERVA - multi-order Runge-Kutta without differential propagation and optional limiting of any output dependent variables;
  • NEPTUNE - self-starting technique of rational function extrapolation from Gragg, Bulirsch, and Stoer without differential propagation; and
  • PEGASUS - a special 5th order Runge-Kutta technique known as Sarafyan Embedding, in which a 4th order result is obtained at the same time plus optional limiting of any output dependent variables in non-differential propagating contexts.

Nesting Contexts[edit]

These solvers applied different numerical methods in the three engine categories, depending upon the nesting context in which they were applied. Some simulation solvers (JANUS, MERCURY, MINERVA, MERLIN and PEGASUS) could not be nested in automatic differentiation contexts of correlation and optimization because they were not overloaded for automatic-differentiation arithmetic. Thus hybrid versions, JANISIS (ISIS or JANUS) and GEMINI (MERLIN or NEPTUNE) were introduced, which would work efficiently in automatic differentiation mode or ordinary arithmetic mode (differentiation internally turned off). This greatly speeded up the iterative searches of solvers like AJAX, MARS, JOVE, ZEUS, and JUPITER, which iteratively called their models many more times in non-differentation mode, when various modes of non-derivative search sub-steps were applied.

References[edit]

  1. ^ PROSE – A General Purpose Higher Level Language, Procedure Manual, Control Data Corp. Pub No. 840003000 Rev. B (Jan 1977)
  2. ^ a b c d e f PROSE – A general Purpose Higher Level Language, Calculus Operations Manual, Control Data Corp. Pub. No 840003200 Rev B (Jan. 1977)
  3. ^ PROSE – A general Purpose Higher Level Language, Calculus Applications Guide, Control Data Corp. Pub No. 84000170 Rev. A (Jan 1977)
  4. ^ PROSE – A general Purpose Higher Level Language, Time Sharing System Guide, Control Data Corp. Pub. No 84000160 Rev A (Jan. 1977)
  5. ^ J.M. Thames, The Evolution of Synthetic Calculus: A Mathematical Technology for Advanced Architecture, in Proc. of the International Workshop on High-Level Language Computer Architecture, University of Maryland, 1982
  6. ^ B. Krinsky and J. Thames, The Structure of Synthetic Calculus, A Programming Paradigm of Mathematical Design, in Proc. of the International Workshop on High Level Computer Architecture, University of Maryland, 1984
  7. ^ a b J.M. Thames, Synthetic Calculus – A Paradigm of Mathematical Program Synthesis, in A. Griewank and G.F. Corliss, eds., Automatic Differentiation of Algorithms: Theory, Implementations, and Applications, SIAM, Philadelphia (1991)
  8. ^ J.M. Thames, “SLANG—A Problem-Solving Language of Continuous Model Simulation and Optimization", ACM National Conference, San Francisco, 1969.
  9. ^ J.D. McCully, “The Q Approach to Problem Solving”, Proceedings of the Fall Joint Computer Conference, 1969.
  10. ^ R.N. Nilsen and W.J. Karplus, "Continuous-System Simulation Languages: State of the Art Survey" Annales de l'Association Internationale pour le Calcul analogique - No 1, Jan, 1974, p. 20
  11. ^ J.M. Thames, Computing in calculus, Research/Development, (1975), pp. 24–30
  12. ^ F.W. Pfeiffer, Some Advances Related to Nonlinear Programming, ACM Sigmap Bulletin, Issue 28, Jan 1980, pp. 15-21
  13. ^ F.W. Pfeiffer, Automatic differentiation in PROSE, ACM SIGNUM Newsletter, 22 (1987), pp. 1–8
  14. ^ a b R.E. Bellman and R.E. Kalaba, Quasilinearization and Nonlinear Boundary-Value Problems, The RAND Corporation, American Elsevier Publishing Co., New York, 1965, p. 125, p. 168