Cardenas, A .F. A problem oriented language and a translator for partial differential equations. Ph.D. Diss., Dep. of Engineering, U. of California, Los Angeles, Calif., Dec., 1968 view details
Tam, Wing Cheung "Non-linear partial differential equations and equations with derivative boundary conditions: improvements to PDEL" M.S. Th. Dep. of Engineering, U. of California, Los Angeles, Mar. 1969. view details
Cardenas, A. F., and Karplus, W. J. "Design and organization of a translator for a partial differential equation language" pp513-523 view details
Extract: INTRODUCTION INTRODUCTION In recent years a variety of techniques for the design and implementation of translators for problem-oriented programming languages has been developed. A number of these employ a high-level programming language such as FORTRAN as the target language, rather than translating directly into assembly language or machine code. The purpose of the present paper is to demonstrate the unique advantages which ran be realized by making PL/1 the target language and by utilizing the so-called preprocessor (or compile-time) facilities of PL/1. This approach has been successfully used in the design of a translator for PDEL, a special-purpose language for the solution of the partial differential equations of classical physics. Details regarding the language and its application have been presented in an earlier paper and are, therefore, only briefly summarized in the next section. The overall structure and philosophy of the translator are described in the third section, while more detailed aspects of syntax analysis and code generation are described in the fourth section. In the final section a quantitative evaluation of the translator is presented.
Extract: REVIEW OF THE BASIC FEATURES OF PDEL REVIEW OF THE BASIC FEATURES OF PDEL PDEL was designed at the University of California at Los Angeles and implemented in its basic form in 1968. Its purpose is to facilitate the solution of those partial differential equations which are of particular importance to engineers. These include particularly the elliptic equations which characterize potential fields, the parabolic equations which Characterize heat transfer and diffusion, the hyperbolic equations which characterize wave phenomena, and the biharmonic equations which arise in elasticity problems. The classes of problems which could be handled by the original translator are shown in Table I. Subsequent extensions of the translator have been directed toward permitting the treatment of fields in three space-dimensions, the inclusion of a wider variety of boundary conditions, and the handling of singularities, moving boundaries, and other special features. The numerical treatment of such partial differential equations most often proceeds from finite difference approximations. The time-space continuum is replaced by an array of regularly-spaced points in one, two, three, or four dimensions, and sets of algebraic equations are solved simultaneously to provide solutions. In the case of elliptic equations, the solutions for all points are obtained simultaneously; in the case of transient field problems, solutions are obtained sequentially for successive steps in the time domain. A variety of algorithms are available for the solution of the difference equations. In order to obviate the problem of computational stability, the catastrophic accumulation of round-off errors, so-called implicit methods are usually preferred. Even so, the numerical analyst must make a judicious choice from among several practical algorithms, a choice which sometimes has a decisive effect upon computer execution time. This choice depends, of course, upon the specific type of equation under study, but is also influenced by the geometry (whether the field has regular boundaries), the parameter distribution (whether the field is linear or nonlinear, or constant or variable parameter), the required solution accuracy, and by the size of available fast memory. A language designed to solve partial differential equations must, therefore, provide various algorithms for the different types of equations; these algorithms may necessarily involve the construction of lengthy subroutines. To avoid waste of computer time, only the subroutine corresponding to the problem at hand should be produced and compiled. The preprocessor facilities of PL/1 are exceptionally well-suited to this end. Accordingly, PL/1 was selected as the target language of the translator, the translator was written in preprocessor PL/1, and all legal PDEL statements were designed so as to be legal PL/I preprocessor statements. A typical PDEL program may contain the following statements, expressed in a syntax chosen to be readily comprehensible to engineers: 1. Definition of the equation to be solved, i.e., the mathematical form of the equation including parameter identifiers, the order of the partial derivatives, Poissonian terms, etc.; 2. Parameter specification, which may be constants or functions of the dependent and independent problem variables; 3. Specifications of the finite difference grid spacing for the space and the time variables; 4. Description of the geometry of the field, that is the coordinates in the space domain of the field boundaries; 5. Boundary conditions, which may be of the Dirichlet, Neumann or Fourier types; 6. Selection of one of available algorithms to be employed; 7. Bounds on the number of iterations or the iteration error for iterative algorithms 8. Description of the type and nature of the printout desired. Default conditions are provided for most of these statements, so that the programmer may choose to omit certain specifications in the program; in this case the translator will make the selection for him. An example of a PDEL program for a simple partial differential equation is presented in Appendix 1, together with a typical print out. To date, over a hundred partial differential equations have been programmed and solved using PDEL.
Extract: GENERAL TRANSLATION APPROACH GENERAL TRANSLATION APPROACH As indicated in the preceding section a translator for a partial differential equations language must contain a selection of algorithms, each suitable for a different class of partial differential equations, different geometries, etc. A study of digital computer programs corresponding to a number of these algorithms indicated that for a given class of equations, approximately 70% to 95% of the total number of program statements was common to all programs. The other 5% to 30% of the statements dealt with the description of parameters, initial and boundary conditions, and geometries which vary from problem to problem. The greater the complexity of the geometry of the field, the greater number of special statements required for characterizing the particular boundary configuration. A key to the successful and economic translation of partial differential equations is the avoidance of the generation of unnecessary code. That is, it is important to assure that only those portions of the translator required for the specific problem to be solved is selected for compilation, and then combined with user-generated statements corresponding to the 5% to 30% of the program which is specific to the problem being solved. Among the major problem-oriented languages currently in wide use, only PL/1, by virtue of its compile-time facilities, permits full control over which portions of a program are to be compiled. The PL/1 preprocessor language is a subset of PL/1, with many significant features particularly suited for character-string manipulation and generation, and hence for language translation. As the name indicates, the preprocessing phase immediately precedes the actual PL/1 compilation. During this phase, the program is scanned for all statements which contain the % identifier; and only those .statements are executed. The PDEL translator is in effect a preprocessor program which automatically chooses groups or modules of fixed PL/1 statements corresponding to the equation to be solved and the algorithms to be employed. These modules of fixed PL/1 code are stored in secondary storage devices (e.g., disc, data cells), and constitute the 70% to 95% of the statements common to all programs of a given class. The other 5% to 30% of the code is generated during the preprocessing phase by specially designed code generation routines which are a part of the PDEL translator. If desired, the programmer may also include PL/1 statements (without the % identifier) in his PDEL program. These statements are unaffected by the preprocessing and proceed directly to the PL/1 compiler. The overall translation process proceeds as shown in Figure 1. The preprocessor phase, which results in the generation of a PL/1 program, is performed in two stages: Syntactic analysis and code generation. This permits the diagnosis of illegal statements, programming errors, and calls for modules not presently available, prior to generation of PL/1 code. The syntactic analysis in turn proceeds in two steps: 1. The standard PL/1 preprocessor analyzes the PDEL program to determine that it is a valid PL/1 preprocessor program. 2. The syntactic analyzers of the PDEL translator analyze the strings on the right hand side of each PDEL statement, so as to detect violations of PDEL syntax. Figure 2, is a generalized conceptual flow-chart of the PDEL translator. Syntactic analysis - represented by blocks Al and A2. Blocks B determine whether the required PL/1 modules are available in secondary storage, while block C contains all the PL/1 code generators. The approximate size of the PDEL program is illustrated in Figure 3, which also indicates the sequence of operations. The two INCLUDE statements appear in the original PDEL program and serve to call the PDEL translator.
Extract: DETAILED OPERATION OF THE TRANSLATOR DETAILED OPERATION OF THE TRANSLATOR The whole translator is a set of modules stored in external memory. Each module is a subroutine which may be retrieved from external storage if needed to process the PDEL program. The task of the modules retrieved and the order in which they act is shown in Figure 2. The order in which they are physically retrieved from external storage is shown in Figure 3. The main modules available are: (1) Three subroutines which perform the syntactic analysis of PDEL statements, stage A2 in Fig. 2. One of these is the master analysis routine which determines whether or not each PDEL statement is constructed according to the rules of syntax stored in the other two subroutines. (2) A monitor module which performs all of step B in Fig. 2, that is, it identifies the problem defined in the PDEL program and retrieves from external storage the module made up of the fixed PL/1 statements and PL/1 preprocessor statements corresponding to the problem. (3) A subroutine which when invoked examines the specification of the geometry of the field in the PDEL program and generates the appropriate set of PL/1 statements used to form the PL/1 program. (4) A subroutine which examines the boundary conditions specified in the PDEL program and generates the appropriate set of PL/1 statements used to form the PL/1 program. (5) A subroutine which examines the initial conditions specified in the PDEL program and generates the appropriate set of PL/1 statements used to form the PL/1 program. (6) A set of subroutines made up of fixed PL/1 code and preprocessor code. Each subroutine corresponds to a given type of equation, and, when processed by the preprocessor, produces the PL/1 program to solve the equation for the particular parameters, initial and boundary conditions, geometry of the field and by the numerical algorithm indicated in the PDEL program. A set of PL/1 subroutines which produce plots of the solution of the equation, e.g., contour plots.
Extract: EVALUATION OF THE PDEL TRANSLATOR EVALUATION OF THE PDEL TRANSLATOR As yet no generally accepted criteria for the evaluation and comparison of translators are available in the computer software area. Qualitative discussions generally center on: compatibility, diagnostic capability, and efficiency. Some comments as to the characteristics of the PDEL translator as far as these three qualities are concerned, appears in order. Compatibility with other computers The PDEL translator is compatible with any computer for which there exists a standard PL/1 compiler and sufficient external random access memory. The translator itself is written in preprocessor PL/1, a high-level language, and makes no reference to unique hardware features. Diagnostic capability The preprocessor PL/1 syntax analyzer (furnished with the PL/1 compiler) and the PDEL syntax analyzer function effectively to detect any programming errors involving the violation of syntactic rules. Errors which can be detected only at execution time (for example, overflow and requests for excessively large arrays) create difficulties, difficulties which arise in the use of most higher-level programming languages. Efficiency A working PDEL translator capable of solving the problems indicated in Table 1, has been in operation since 1968. It contains approximately 3,000 cards. The preprocessing, compilation, and execution time for four arbitrarily selected field problems are summarized in Table II together with the number of PDEL and PL/1 statements required in each case. Improvements in some of these figures have been effected recently by evolutionary changes in the translator.
in [AFIPS] Proceedings of the 1970 Spring Joint Computer Conference SJCC 36 view details
Cárdenas, Alfonso F. and Karplus, Walter J. "PDEL A Language for Partial Diferential Equations" view details
Abstract: Conventional computer methods available to solve continuous system problems characterized by partial differential equations are very time-consuming and cumbersome. A convenient, easy to learn and to use, high level problem oriented language to solve and study partial differential equation problems has been designed; a practical translator for the language has also been designed, and a working version of it has been constructed for a significant portion of the language. This Partial Differential Equation Language, PDEL, is outlined, and the highlights of the translator are briefly summarized.
Extract: PDEL Introduction The acceptance and popularity of digital simulation languages (problem oriented languages for systems) is exemplified by the successful ability of languages such as GPSS and SIMSCRIPT to solve and study discrete system problems, and MIMIC, DSL/90, and CSMP to solve continuous system problems characterized by ordinary differential equations [1]. However a need still exists for a convenient high level problem oriented language that can solve continuous system problems characterized by partial differential equations (field equations), since conventional methods to handle such problems on a computer are especially time-consuming and cumbersome. In the absence of such a language, it is necessary, first, to choose an appropriate algorithm from among the many proposed by numerical analysts and, then, to write and debug a program that will solve the equation. The main goals of the Partial Differential Equation Language, PDEL, described in this article, and of the translator only briefly discussed, are to ease problem solving and to reduce the total problem-solving time. PDEL significantly reduces the numerical analysis effort and avoids the effort involved in programming in ALGOL-like languages--usually the largest portion of total problem solving time. One of the earliest significant efforts to assist in the solution of field equations was the S~,ADE project in the late 1950's, whose aim was to produce a set of subroutines to solve certain elliptic and parabolic equations [2]. SPADE did not get very far, mainly because of the limited capabilities of second generation hardware and software and also because of the difficulties in coordinating the work of the seven large aerospace companies involved in the project. There are many working programs for partial differential equations throughout industry and universities [3], but their application is limited to one or at most, to only a few types of field equations and geometries. Much work has been conducted in the solution of field problems at the ILLIAC IV computer facility at the University of Illinois [4, 5, 6]; however, the main goal there is to reduce computer execution time and not so much the overall numerical analysis and programming effort. Two other recent efforts are of significance. Cea and Nivelet in France have been developing a large ALGOL program to solve automatically general one- and two dimensional elliptic equations for any type of boundary conditions and geometry [7, 8]. Morris has developed the SALEM programming system to solve automatically one dimensional parabolic and hyperbolic equations and two dimensional elliptic and parabolic equations under various conditions, but limited to simple regular geometries [9, 10]. In both cases the input format is algebraic and subroutine oriented. However, SALEM can be considered an elementary but significant simulation language. PDEL represents an extension of these efforts and is unique in that: (1) It is a flexible and practical formal language. (2) It has a much larger variety of field problems, including irregular boundary problems, that can be easily and conveniently defined and solved. (3) It does not require the user to know what numerical analysis subroutine to use. (4) It has a fast and practical machine-independent translator that was constructed for a large and significant subset of the language. PDEL can handle a large variety of fields. Time-dependent and time-independent fields can be defined. Any size of grid can be used to approximate regular and irregular geometries. Linear, nonlinear, uniform and nonuniform fields can be treated. A modular translator for a significant portion of the PDEL language has been implemented and is continually being enlarged. The problems that could be handled by hyperbolic fields with various types of parameters and conditions, and two-dimensional regular and irregular elliptic and parabolic fields with various types of parameters and conditions.
Extract: Functional Characteristics of PDEL 2. Functional Characteristics of the Language The following primary characteristics are essential for a language to be attractive to users desiring to solve partial differential equation problems. (1) The language must be applicable and suitable for the numerical solution of most partial differential equations of interest to the engineer and scientist. It must handle these equations in the presence of regular and irregular boundaries, linear and nonlinear parameters, Dirichlet and derivative boundary conditions, etc. Table I outlines some of the most common types of these equations. (2) The language must be easy to learn and to use. Guided by these two general requirements, the PDEL language was designed so as to permit the user: (1) To clearly and conveniently specify the equations(s) (single or simultaneous), geometry, parameters, boundary conditions, etc., in Cartesian coordinates, and automatically obtain a solution using finite difference equation algorithms. (2) To specify any grid size to approximate the field (size limited by computer memory capacity); grid spacings do not have to be equal in every direction. (3) To conveniently terminate and/or repeat a simulation run with new parameters. (4) To obtain a suitable tabular and/or discrete graphical printout of the solution. (5) To specify and input PDEL statements in the same form as PL/1 statements, and, furthermore, in any order. Recognizing the advantages of on-line, graphical man/ machine interaction, the language has been oriented toward both batch and on-line processing. PDEL may be considered an extension of PL/1, since it has been designed so that its syntax falls within the syntax of preprocessor or compile time PL/1. The language is compatible with PL/1 and capable of being mixed with it. This permits the experienced and sophisticated user faced with a major problem to build his own sophisticated logic, procedures, or subroutines, etc. Finite difference approximation methods and Cartesian coordinates are more frequently used and more universally applicable than any others, and consequently PDEL is designed to solve equations expressed in Cartesian coordinates by means of finite difference algorithms. The Volume 13 / Number 3 / March, 1970 Communications of the ACM 185 finite difference approximation of the partial differential equation at each grid point and the algorithm for solving the approximations must be chosen so that the overall complexity and, consequently, the computer time and memory requirements are not unattractive to the user of PDEL, and so that the task of translator implementation is not impractical. Table I summarizes the methods selected to solve the most common types of equations in PDEL; programs implemented as of June 1969 are identified by an asterisk. To use PDEL, irregular field boundaries must be approximated so that the boundaries fall on grid points and hence on grid lines. However, this does not usually constitute a disadvantage because irregular boundaries can be as closely approximated as desired by using finer grids.
Extract: Technical Characteristics: Syntax and Semantics of PDEL 3 Technical Characteristics: Syntax and Semantics of PDEL The syntax and semantics of the PDEL language is now outlined, but not rigorously defined--it is defined rigorously in a separate report [11]. Backus-Naur notation is used whenever helpful for syntax definitions. All nonterminal symbols used for the sole purpose of defining syntax are enclosed in brackets ( }. The terminal symbols are the symbols that make up the language and are not enclosed in brackets. The letters, digits, arithmetic operators, and other characters of the standard IBM 60 character set are the elementary units of the language. Integers and numbers are the values used in PDEL. A number may be an integer, or a signed or unsigned series of digits, with or without a decimal point, and followed or not followed by an exponential part. Numbers in PDEL follow the same syntax as numbers in PL/1. Identifiers are made up of any combination of letters, digits, break character, $, # and ~, and may be up to 31 characters long; the first character must be a letter. The dependent and independent variables of an equation are represented by the following reserved identifiers: