text:pl-reddy-mckeeman
Computer Programming: An Introduction to PL
A paper by D. R. Reddy and W. M. McKeeman, 1970. Taken from MTS distribution D2.0: http://bitsavers.org/bits/univOfMichigan/mts/
From preface: “PL, a dialect of PL/1, is specifically designed for teaching beginning programming students. This system was developed at Stanford University as a result of a student programming language project initiated by Professors McKeeman and Reddy.”
(pre-formatted two pages per page)
1 1 COMPUTER PROGRAMMING: AN INTRODUCTION TO PL D. R. Reddy and W. M. McKeeman 1 2 TABLE OF CONTENTS 3.4.3. Mixed String Expressions 3.5. Logical Expressions 3.5.1. Precedence of Operations in a Logical Preface Expression 3.5.2. Assignment of Logical Expressions and 1. ALGORITHMS AND COMPUTERS the = Confusion 1.1. Algorithms 3.6. The Conditional Statement 1.1.1. An Algorithm for Grading 3.6.1. Control Statements 1.1.2. The Euclidean Algorithm 3.6.2. Conditional Statements 1.1.3. Hand Simulation of Algorithms 3.7. Group Statements 1.2. Computers 3.7.1. DO ... END Statements 1.2.1. Input 3.7.2. Paragraphing for Control Statements 1.2.2. Output 3.7.3. Repetition: the DO WHILE Statement 1.3. Formulation of Algorithms 3.7.4. The DO Statement with an Iteration 1.3.1. Efficient Algorithms Control 1.3.2. Impractical Algorithms 3.7.5. The DO CASE Statement 1.3.3. As Yet Undiscovered Algorithms 3.8. Subscripted Variables 1.3.4. Unsolvable Problems 3.8.1. Subscripts 1.3.5. Historical Notes 3.8.2. Input and Output Using Subscripted Variables 2. LANGUAGES 3.8.3. Multiple Subscripts 2.1. Languages and Communication 3.9. Group Statements: Additional Constructs 2.1.1. Ambiguity of Languages 3.9.1. Repetitions within Repetitions: 2.1.2. Redundancy of Languages Nested Loops 2.2. Structure of Languages 3.9.2. The DO Statement with a Variable 2.2.1. Parse Trees Increment 2.2.2. Backus Naur Form - BNF 3.9.3. The DO WHILE Statement with a Control 2.2.3. Recursive Definitions in BNF Clause 2.3. The Language PL 3.10. The GO TO Statement 2.3.1. History of Programming Languages 3.10.1. Restrictions on GO TO Statements 2.3.2. Structure of PL 3.10.2. Table Search 2.3.3. Style of Programming in PL 3.10.3. Binary Search 2.3.4. Paragraphing in PL 3.11. Block Structure 2.4. Elements of PL 3.11.1. Scope of a Variable 2.4.1. The Alphabet 3.11.2. Dynamic Storage and the Allocation 2.4.2. Constants Statement 2.4.3. The Reserved Vocabulary 3.11.3. The FREE Statement 2.4.5. Variables 3.12. Procedures 3.13. Array Arithmetic 3. STATEMENTS IN PL 3.1. Declarations 5. ERROR DETECTION AND CORRECTION 3.1.1. Factoring of Attributes 5.1. Errors During Program Translation 3.2. Assignment statements 5.1.1. Error Recovery by the Translator 3.2.1. Expressions 5.1.2. Some Common Errors with Misleading 3.2.2. Temporary Variables Error Messages 3.2.3. Input, Output, and Assignment 5.1.3. Correction of Syntactic Errors 3.2.4. Input Data 5.2. Errors Due to System Limitations 3.3. Arithmetic Expressions 5.2.1. Error Correction 3.3.1. Arithmetic Functions 5.2.2. Additional System Errors 3.3.2. Hierarchy of Operations in Arithmetic 5.3. Errors During Program Execution Expressions 5.4. Run-Time Errors Due to System Limitations 3.3.3. Arithmetic in PL 5.5. Errors in Problem Solution 3.4. String Expressions 3.4.1. Character String Operations 3.4.2. Precedence of Catenation 1 3 PREFACE using the syntax of the language so that he can discover for himself the structure, the hierarchy of operations, and how to PL, a dialect of PL/1, is specifically designed for locate and correct errors. Thus, one will see several examples teaching beginning programming students. This system was of parsing of statements in the text. developed at Stanford University as a result of a student programming language project initiated by Professors McKeeman It is not the intent of the authors that the students begin and Reddy. The aim of the project was to develop a language on page 1 and read straight through the book as a novel. which is of minimal complexity yet rich in concepts and a system Although the text was organized in its present form for which has good diagnostic aids and is inexpensive to use. Drs. conceptual reasons, the authors themselves have found it J. J. Horning, D. B. Wortman, and Mr. E. C. Nelson helped in necessary to skip from chapter to chapter and section to section formulating a consistent and formally describable language. Dr. during the course of teaching basic programming courses using D. B. Wortman wrote the present Translator-Interpreter for the these notes. The following lesson plan was found to be IBM-360 which was used in generating the examples used in this satisfactory for a ten week (three hours a week) course for book. We would like to thank Ellen Gruenbaum and Steven Newberry senior and graduate students. for their help in proof-reading the manuscipt and in programming the examples used in this text, Mrs. Phyllis Winkler for her Week 1: Sentence Diagramming; Problem Solving (4.1); Algorithms excellent typing, and Drs. Wortman and Horning for their (1.1); Backus-Naur Form and the definition of PL (2.3). valuable comments on the manuscript. Week 2: Elements of PL (2.4); Assignment Statement, Input-output (3.2); First Problem: read, sum, write; Conditional The language PL is a dialect of PL/1. For the most part it statement (3.6); Simple DO loops (3.7.1). is a proper subset of PL/1 including recursive procedures and Week 3: Computer Translation and Execution of Programs (1.2); string manipulation. The main departures from PL/1 are in input Error detection and correction (Chapter 5); Second problem: and output statements, which have been made special cases of the mean and variance calculation. assignment statement, and format statements, which are reduced Week 4: Problem Solving (4.1); Progressive Flowcharting (4.2); A to special cases of string operations. The net effect for a Case Study of the Calculation of Prime Numbers (4.3). beginning student in programming is to remove several ad hoc Week 5: Expressions: Arithmetic expressions (3.3), String developments in languages and to re-express these as special expressions (3.4), Logical expressions (3.5); Parsing & cases of familiar concepts. Other differences from PL/1 include detection of hierarchy of operators (3.3.2); Third Problem: variable length strings, extension of certain types of group non-trivial problem (matrix inversion). statements, and simplified interaction between declarations and Week 6: Block Structure (3.12); Go to Statement (3.10). other statements in blocks. Week 7: Procedures (3.13); Forth Problem: using blocks & procedures. The implementation of PL on the IBM-360 (available through Week 8: Advanced expressions (3.3.7). SHARE) is known as the SPL translator. The SPL system is Week 9: Advanced loops and complex Input- output (3.8 and 3.9). specially designed for fast compilation and execution. On an Week 10: Advanced Procedures; Conclusion (1.3). IBM-360 small student exercises take less than a second to compile and execute. Typical compilation rates are around 3000 cards per minute. Programs are translated into special PL For freshmen the same course is covered over a two quarter machine language which is at present interpreted on an IBM-360. (or one semester) period at a slower pace and with the inclusion For all but a few computed bound programs, most student programs of a large number of case studies in problem solving. execute in less than a second. The translator uses precedence tables and was written in a small subset of PL/1. (A specially written efficient compiler called XPL is available for this subset through SHARE.) This permits easy addition and modification of constructs depending on the needs of the course. The SPL system provides extensive diagnostic aids to the student usually making it unnecessary for him to seek expert help. The use of compile-time errors and the precise BNF syntax of the PL language make it easy to locate and correct syntactic errors. A special diagnostic dump of the values of all the variables visible from the block simplifies location and correction of run-time and logic errors. Chapter 5 of this text provides many illustrations of this feature. The emphasis is on teaching the student proper sentence diagramming (hand-parsing) 1 4 CHAPTER I equation are complex numbers. In a computer one must calculate the real and imaginary parts of complex numbers separately. The ALGORITHMS AND COMPUTERS reader may be interested in attempting to discover some other difficulties presented in this example. 1.1 ALGORITHMS Well thought out and error-free algorithms are essential for solving problems on a computer. With the rapidly increasing During the course of the day most of us perform a number of acceptance of computers there has been a corresponding increase well defined and predictable sequences of steps in solving in the demand for persons capable of preparing such algorithms. routine problems. We may look up a number in the telephone book A program is an algorithm written in a language understood by or a word in the dictionary, make change or perform arithmetic computers. This has resulted in the evolution of a new operations on numbers. Some of us may solve equations or predict profession known as programming . Construction of algorithms, weather or calculate the orbit of a satellite. Even though we (especially the construction of efficient ones), usually perform some of these tasks intuitively, we can usually state requires a high degree of ingenuity and knowledge. A programmer the instructions necessary to tell another person or a machine must not only have complete grasp of the problem to be solved how to solve these problems. An algorithm is defined to be a set but also must be well versed in the techniques of algorithm of instructions specifying the operations which will lead to the formulation and specification. Specification of algorithms in a solution of any problem of a given class. Once an algorithm is language understood by computers is an acquired ability less formulated it can be used by a person who does not even know its difficult than learning a language such as French. Formulation purpose. Proceeding quite mechanically he can solve any problem of an algorithm from a vague or incomplete problem description of the type for which the algorithm is designed. requires special aptitude and training. The main purpose of this book is to introduce the reader to the basic concepts, methods, Why all this interest in algorithms? Because we would like and techniques involved in the formulation of algorithms drawn to have machines solve our routine problems for us. A computer from a number of the basic fields of Computer Science. is such a machine; given an appropriate algorithm it will operate on the data to produce the desired results. To be suitable for use with a computer, the sequence of steps must be 1.1.1 An Algorithm for Grading + ________________________ well defined; i.e., the desired solution should result even if the steps are performed mechanically without any understanding Suppose we wish to write an algorithm for grading test of the processes involved. Given an algorithm a computer can papers. Let us assume that the test is of a true/false type and solve many routine problems more quickly than a person, and once that the grader has a key of correct answers to make the an algorithm is prepared in a machine-readable form it can be necessary comparisons. Then the grader can use the following used any number of times. It is not uncommon, at present, to use algorithm to grade the papers: a computer to determine what to feed the cows, to keep track of the condition of a patient and sound alarm when he needs attention, to produce patterns for textiles, or to produce a symphony in the style of Beethoven. With such varied and accelerated activity in the development of algorithms it is essential for us to have a good understanding of the nature of algorithms. An algorithm is more than a mere statement of a mathematical formula. Consider some of the problems that can arise in attempting to solve the deceptively simple quadratic equation. For example, it is not sufficient to say that the 2 2 -b*square root(b -4ac) solutions of ax +bx+c = 0 are given by ----------------------. 2a An algorithm must state the sequence in which all the operations are to be performed. We first specify what to do if 'a' equals 0 since division by 0 is undefined. We next specify what to do if the radicand is negative, since the resulting roots of the 1 1 102 5 ┌-------------------------------------------------------┐ What must one do to represent the above process in an |Repeat steps 1 to 4 in sequence | algorithmic form? On careful examination one will find that | 1. Select the test paper. | making up a sequence is not essential to the problem. Indeed, we | 2. Set the student grade to 0. | are only interested in the last number of the sequence. The | ┌-------------------------------------------┐ | concept central to the whole algorithm is that the gcd of any | 3. |Repeat the following step: | | two numbers can be expressed in the form of the gcd of two | | ┌---------------------------------------┐ | | smaller numbers. By repeating the process we will eventually end | | |if the question has been answered then | | | up with a pair of numbers, one of which will be divisible by the | | | ┌-----------------------------------┐ | | | other, and then we have the required answer. For example, the | | | |if the answer matches the key then | | | | gcd of 35 and 25 is the same as the gcd of 25 and 10. (Why?) | | | | increase the student grade by 1; | | | | | | | |otherwise | | | | The analysis has led us to a better understanding of the | | | |decrease the student grade by 1; | | | | problem and we can now formulate an algorithm for its solution. | | | └-----------------------------------┘ | | | | | |otherwise do nothing; | | | ┌---------------------------------------------------------┐ | | └---------------------------------------┘ | | |Do the following 5 steps in sequence. | | |for each question in the paper. | | |1. Select two positive integers and assign them to | | └-------------------------------------------┘ | | variables 'a' and 'b'. | | 4. Record the student grade. | |2. If the value of 'a' is less than that of 'b', | |for each student in the class. | | interchange the values. | └-------------------------------------------------------┘ |3. Let the value of a variable 'c' be any non-zero | Figure 1.1.1. The Grading Algorithm | number. | | ┌---------------------------------------------------┐ | The grading algorithm is sufficiently precise that it can |4. |Repeat the following 3 steps in sequence: | | be used by any grader (be it man or machine) without even being | |4.1 replace the value 'c' by the remainder of 'a' | | aware that he (or it) is grading test papers. This algorithm | | divided by 'b'; | | introduces several concepts which will become more familiar to | |4.2 replace the value of 'a' by the value of 'b'; | | us in later chapters. For example, we see that it is desirable | |4.3 replace the value of 'b' by the value of 'c'; | | to be able to repeat a computation over and over again until a | |until the value of 'c' equals 0 . | | certain condition is satisfied. Note also that the statements to | └---------------------------------------------------┘ | be repeated are indented; this is known as paragraphing or |5. Record the value 'a' as the answer. | grouping together of statements that are conceptually related. └---------------------------------------------------------┘ Figure 1.1.2 The Euclidean Algorithm 1.1.2 The Euclidean Algorithm Many different concepts, some so natural that we often use + _______________________ them without realizing it, are introduced in the above Consider another concrete example, the Euclidean algorithm algorithm. The control statement 'Do ... in sequence' is usually for finding the greatest common divisor (gcd) of any two omitted as obviously being the normal mode of operation. (It is positive integers. The problem can be solved by constructing a not always necessary for the steps to be performed in sequence descending sequence of numbers S , where S is the larger of and often one finds situations when several steps can be done in i 1 parallel, i.e., the operations can be performed in any order whatsoever or simultaneously without affecting the final result. the two integers and S is the smaller. Successive elements, (Most matrix operations belong to this category.) Another 2 control statement 'Repeat ... until c equals 0 ' indicates that certain steps are to be repeated over and over again until the S , are given by the remainder of S divided by S until given condition is satisfied. Repetitive (or iterative) i i-2 i-1 processes occur often in algorithm formulation. Later we shall see many different ways of controlling repetitive processes. there is no remainder. The last number of the sequence is the answer. For example, the gcd of 25 and 35 is the last number of Variables which take on different values during different the sequence stages of computation provide one of the basic concepts used in 35, 25, 10, 5. the definition of algorithms. Variables provide a convenient way The gcd of 13 and 9 is 1 as can be seen from the sequence of keeping track of values of interest and getting rid of the 13, 9, 4, 1. rest. Variables are represented by names such as 'x', 'y', 'a', 'b', etc., and can be assigned values. In pencil-and-paper 1 102 201 6 computation, one can change the value of a variable by rubbing 1.1.3 Hand Simulation of Algorithms + _____________________________ out the old value and writing in the new one. In computers, values of variables are changed similarly (analogous to Proper understanding and appreciation of an algorithm can overwriting old songs by new ones on a tape recorder). Various be achieved only if we ourselves perform the sequence of steps arithmetic operations can be performed on the variables and the that are to be performed by a computer. This process of manual results can replace the value of other variables. Note in the imitation of computer operation is (usually) called hand above algorithm only "compare" and "remainder" operations are simulation. The steps of an algorithm cause changes in the performed on the values of the variables. Operations such as values of the variables of the program. It is necessary to keep remainder can be expanded into separate algorithms in terms of a running record of the variables as the effect of each more basic operations such as subtract and compare (Figure statement is simulated. The simplest method is to write the name 1.1.3). (Most present day computers are powerful enough to of each variable above a column on ruled paper and add the perform such operations without explicit instructions from the latest value each time the variable is changed. At the end of user.) Statement number 4.1 of Figure 1.1.2 can be rewritten as the process, you will have a complete record of the values of follows: the variables of the program during execution. Figure 1.1.3 gives an example which reflects the successive ┌---------------------------------------------------------┐ values of variables named 'a', 'b', and 'c' during the execution |Replace the value of 'c' by the value of 'a' | of a remainder algorithm. Other properties, such as what value | ┌-----------------------------------------------------┐ | was found for a test, are usually best retained mentally but can | |Repeat the following step: | | also be recorded in a column. How much to record is a matter of | | ┌---------------------------------------------┐ | | good sense; write just enough so that you understand what is | | |Replace the value of 'c' by the result of | | | going on and be able to retrace your work. | | |subtracting the value of 'b' from the value | | | | | |of 'c' | | | a b c | | └---------------------------------------------┘ | | --- --- --- | |until the value of 'c' is less than the value of 'b'.| | 0: 52 12 | └-----------------------------------------------------┘ | 1: 52 12 52 └---------------------------------------------------------┘ 2: 52 12 40 Figure 1.1.3. A Remainder Algorithm 3: 52 12 28 4: 52 12 16 To a casual reader the definition of the Euclidean 5: 52 12 4 algorithm might appear to be unnecessarily pedantic. It takes 12 > 4 -> Stop but one or two attempts to solve a problem on a computer to find Remainder = 4. out that it indeed pays to be precise and unambiguous. The English language being what it is, it takes a great deal of Figure 1.1.3. Hand simulation of algorithm painstaking effort and many words to be unambiguous. One look at of Figure 1.1.2 for values a = 52, b = 12 a legal document will prove this point, e.g., Exercise 1.1.1 In consideration of the representation in the policy To test your understanding of the concept of hand application (copy attached and made part hereof), the simulation and of the Euclidean algorithm, prepare a payment in advance of the Initial Term Premium, and subject history sheet for the algorithm given in Figure 1.1.2 and to all the exclusions, limitations, reductions on account hand simulate the algorithm for the initial arguments 35 of age, provisions and other terms of this policy, the and 25. Company hereby insures the person named above (herein called the Insured), against described loss resulting directly and independently of all other causes from bodily 1.2 COMPUTERS injuries (herein called "such injuries") caused by accident occurring while this policy is in force and arising out of A computer is a device capable of accepting information, the following hazards. performing specified operations on the information and supplying the results of these operations. Given an algorithm and data, A number of algorithmic or programming languages have been the computer processes the data as specified by the algorithm developed to provide the precision essential for communication and produces the desired results (see Figure 1.2.1). Whether it with a computer. An example of the GCD algorithm expressed in a is a mechanical device with spinning wheels or an electronic programming language appears in Chapter 2 (Figure 2.3.2). device with blinking lights, the computer serves the same function. Turing has shown that, given enough time and storage, 1 201 290 7 any computation that can be performed by one computer can in computer and the computer can respond quickly to any errors in principle be performed by another. It is just a matter of how the input. Normally however the keyboard is connected to a long it takes to do the job. device which punches holes in a card or papertape (see Figure 1.2.5 and 1.2.6). The information we wish to convey to the Algorithm computer is coded in the form of holes on the card which can | later be read by a mechanical card reader attached to the v computer. Computer --> Results 7 Figures: | 1.2.2 Card Reader Data 1.2.3 Teletype 1.2.4 CRT display and keyboard Figure 1.2.1 Computing Process 1.2.5 A card with all the characters punched on it 1.2.6 Paper tape with holes Figure 1.2.1 shows algorithm and data in separate boxes. Does this mean that algorithms are somehow different from the Computer systems which primarily use a card reader for data they operate upon? The answer is yes and no. While it might input are called card-oriented systems ; those that use be easier for us conceptually to differentiate between typewriters or display keyboards are called terminal-oriented algorithms and data, for a computer they are merely different systems . flavors of the same thing: information. Exercise 1.2.1 Until the late 1940's calculating machines required special Using an input device available at your computer wiring to specify the algorithm. This special wiring would then installation, prepare as input the following information: control the sequence of operations to be performed on data. In your last name, first name, initial; department, phone 1945 John von Neumann in the now classic paper called number. "Preliminary Discussion of the Logical Design of an Electronic Computing Instrument" suggested that special wiring to solve individual problems can be eliminated by representing the 1.2.2 Output + ______ instructions to the computer as numerals, which can then be stored in the computer memory along with the data. A machine A computer may have different output devices to print or could be designed to interpret the numeral as an instruction display the results of computation to the user. The output might code and perform the appropriate operation, e.g., add two be printed at 1000 lines per minute on a printer (2000 numbers, or test to see if the result of an operation is zero. characters per second) or typed at 15 characters per second on a typewriter or displayed at electronic speeds on a CRT (Cathode The idea of storing the program (the sequence of Ray Tube) display unit (see Figures 1.2.7 and 1.2.8). Exactly instructions that operate on the data) in memory is known as the what will be printed or displayed will depend on what was "stored program" concept. Computing machines that use this specified in the algorithm (see Figures 1.2.9 and 1.2.10). One concept are called "general purpose computers" because the can also punch the results on cards or paper-tape or write it on design of the machine (and therefore the wiring) is not some magnetic medium such as tape, disk, or drum. This provides dependent on any special problem. Further, unlike wiring, the facility for using the output of one program as input to instructions in the memory can be easily modified. That is, a another. program could make changes in another program or, in fact, in itself. Figures: 1.2.7 Printer 1.2.8 Display Unit 1.2.1 Input 1.2.9 A Printout from a Program + _____ 1.2.10 A Picture of a Display A computer may have one or more input devices to accept the 1.2.3 Processing algorithm and the data. Input devices attached to the computer (see Figures 1.2.2 to 1.2.4) might consist of card readers, The information collected by the input devices must be paper tape readers, typewriters, and keyboards associated with stored, operated upon in accordance with the instructions of the the display units (similar to TV tubes). No matter what device algorithm, and the results sent to the output devices. The set one uses for an input, (at some point) one sits at a keyboard of functional units and memories involved in the storing, (similar to a typewriter keyboard) and types the program and the transformation, and transmission of information is called the data. In some cases the keyboard is connected directly to the computer (although one sometimes also sees that word used to 1 290 386 8 include the input and output (i/o) devices). Figure 1.2.11 is a Figure 1.2.11 of a real computer to which you have access. diagram depicting the main units of a typical computer. ┌-------------------------------------------┐ 1.3 FORMULATION OF ALGORITHMS |┌------┐ ┌-------┐ ┌------┐ ┌-------┐ | ||bulk |->|i/o |->|main |->|i/o |-> |.... i/o This section might not be very meaningful to a reader who ||memory|<-|channel|<-|memory|<-|channel|<- |.... devices has never used computers before. We suggest that a beginning |└------┘ └-------┘ └------┘ └-------┘ | . ┌---┐ programming student skip this section and proceed to Chapter 2. | |7 | 7 7| | . |...| | || | | || | ....|. .| | v| v | |v | .---|...| 1.3.1 Efficient Algorithms + ____________________ | ┌----------------┐ | . └---┘ | | control | | . The solution to a problem can usually be achieved by | | unit | | . ┌---┐ various methods. Even if the concepts underlying the solution | └----------------┘ | . |...| are identical, the algorithmic definitions of the problem can be | 7 | | ....|. .| written in a number of different ways. Of these, some algorithms | | | | .---|...| are better than the others. For instance, they might require | | v | . └---┘ fewer operations, or less time, or less storage space to solve | ┌----------------┐ | . the problem. It is this ability to produce efficient algorithms | | arithmetic | | . ....... that characterizes a good programmer. One learns to produce good | | unit | | . .| |. algorithms by studying how other people solved similar problems, | └----------------┘ | ....| |. by a clear understanding of the problems to be solved, and by a | | ---.| |. familiarity with the capabilities and limitations of the | | .└---┘. computer to be used. | | ....... └-------------------------------------------┘ Let us illustrate how a slight reorganization of an The overall structure of a typical computer algorithm can help to reduce the computation time. Consider the Figure 1.2.2 problem of polynomial evaluation. Given the value of 'x' and the values of the coefficients a , a , ... to a , we are The large box denotes the boundary of the computer. The arrows n n-1 0 indicate the paths over which data can be transmitted. The main memory holds both the instructions and the data (when possible required to calculate the value of the polynomial -- if there is too much of either, some may be placed in bulk memory). The control unit keeps everything synchronized. It n n-1 fetches its instructions from main memory, obeys them causing a x + a x + ... + a . The direct evaluation of the the i/o channels or arithmetic unit to function, waits if n n-1 0 necessary, then repeats the cycle. An i/o channel is responsible for transferring relatively large amounts of data to or from formula requires 'n' additions and n(n+1)/2 multiplications. main memory. Once set in motion by the control unit, an i/o channel may continue to function for some time while the control i unit goes on to other duties. The arithmetic unit performs The number of multiplications can be reduced to 2n-1 , if x addition, subtraction, multiplication, division and the like. It is generally fast enough so that the control unit can afford to i-1 wait for it (thus the arithmetic unit needs no direct is computed by using the previously saved value of x . By communication with memory). rewriting the polynomial in the form (Horner's Method) ((..(a x + a )x + a )x + ...)x + a )x + a we can further The reader should not assume that all computers are n n-1 n-2 1 0 organized this way. In fact, various engineering considerations usually cause somewhat more elaborate schemes to be adopted. We reduce the number of operations to 'n' additions and 'n' simply wish to establish a conceptual understanding of the multiplications; hence by a slight reorganization we are able to functions and units of real machines. save yet another n-1 multiplications. Exercise 1.2.2 Without disturbing the machine or its operator, locate and describe the parts that correspond to the units depicted in 1 386 476 9 n(n+1)/2 2n-1 n n n-1 _____________________ Using a x + a x + ... a notation, write 5050 199 100 n n-1 0 ---- --- --- 28 13 7 an algorithm for converting this form to nested form. 21 11 6 Assume that the terms are ordered by exponent, but allow 15 9 5 for the case a = 0 . 10 7 4 j 6 5 3 3 3 2 1 1 1 Exercise 1.3.5 Hand simulate this algorithm for The number of multiplications in some polynomial evaluation scheme 3 2 Figure 1.3.1 a) 2x + 3x + 5x + 7; 3 2 There are many such efficient variants of algorithms available b) 2x + 3x + 7 . in literature. Some of the more basic and interesting of these will be presented in the following chapters. Exercise 1.3.6 Reorganization of a suggested solution may not merely be What algorithm do you use in looking up telephone numbers? advantageous but essential in cases when the capabilities of the computer are exceeded. Consider the problem of looking up a number in the telephone book. One could suggest a "brute force" 1.3.2 Impractical Algorithms + ______________________ algorithm of starting with the first name and going down the list until the appropriate name is found. This algorithm clearly There are algorithms which, using the present day would work, but it is highly inefficient and thus would take a computers, may take millions of years for completion. Consider lot of time. the problem of playing chess with a computer. The computer must have knowledge of the legal moves and a basis for determining Exercise 1.3.1 its move in any given situation. Can one decide whether a given 5 4 3 2 move is the best? Clearly a move is acceptable if it is Express 2x + 3x + 5x + 7x + 11x + 13 for x = 2 guaranteed to lead to a win, no matter what the opponent does. in nested form. One way to guarantee success is to evaluate, for each move, all the possible replies of the opponent. In principle this process can be continued until finally the game ends in a win, a loss, Exercise 1.3.2 or a draw, at which time one knows all the necessary moves that 5 4 3 2 guarantees a win. Such a search procedure can be specified as an Evaluate 2x + 3x + 5x + 7x + 11x + 13 for x = 2 algorithm for a computer. Why, then, does chess remain a game and x = 3 . Does it matter much which of the three which demands great skill and ingenuity? algorithms suggested above you use? Here we encounter the impracticability of certain Exercise 1.3.3 algorithms. No computer can beat a chess champion using such an Horner's method is not always the best way to evaluate a algorithm because it would take too long to make a move. At the start, white can make any one of twenty possible moves. The 23 number of possible moves availiable to either player in the polynomial. For example, show that x needs only six subsequent stages is comparable. It is estimated that there are 4 2 120 multiplications and 16x + 32x + 8x + 1 can be done in about 10 possible move-countermove sequences in chess. Any four multiplications and one addition. 120 algorithm that requires the evaluation of 10 paths to decide Exercise 1.3.4 on the best move is clearly impractical. Let us illustrate the magnitude of the task by comparison with some accepted facts 1 476 566 10 -10 distinguish between the image of a man and that of a woman, about our universe. Suppose we take 10 (tenth of a entities such as dress, shape and hairstyle should be defined billionth) of a second as an average time for an atomic event. precisely. In addition, one must define the differing Then it is stated that the total number of atomic events that characteristics of these entities that will make discrimination have occurred anywhere in the whole universe, in all time, is possible. At present we do not know how to represent the problem within the computer, even as a "brute-force" algorithm. 100 about 10 . Thus we are beyond the practical limit when we There are many similar problem areas which can be solved by people without much conscious effort but which have proved to be 120 extremely difficult for machines. Consider the problem of talk about 10 operations, and any attempt to use a straight- reading a newspaper. A computer can now be programmed to 'read' forward "brute force" algorithm to teach the computer to play the individual letters and even to compile crude dictionaries of chess is doomed to failure. the words, but this does not carry with it any 'comprehension' of the meaning of the sentences. The information about the Does it mean that computers cannot hope to play a language and the environment -- a trivial matter for people -- respectable game of chess? Indeed, no! There are already some is as yet too complex for the machine. Another problem requiring programs in existence which play a good game even against the ability to understand languages is automatic translation of champions. It does mean that we have to discover better than languages. There are computer programs which can translate from "brute-force" algorithms to solve some problems. The discovery Russian to English, but the poor quality of the resulting of new algorithms (or rediscovering old ones) is a rewarding and translations have been the cause of a bitter controversy exhilarating intellectual experience similar to that of regarding the capabilities of computers. Then there is the discovering a new theorem or inventing a new machine (which problem of "world-modelling", i.e., the ability to look at the perhaps explains why one often finds programmers working round picture(s) of a room and say, "There is a table in the middle of the clock without any complaint). the room. There are four chairs around it," and so on. The logical and mathematical problem involved in making such Exercise 1.3.7 statements from a visual input to the computer are immense. A startling and perhaps challenging fact emerges from the above 120 examples: there are many previously unrecognized difficult Write 10 in the usual decimal notation. problems. How, then, are we to formulate appropriate algorithms? At present, the tendency is to solve specific sub-problems Exercise 1.3.8 by writing programs which consider many different special cases that can occur. It is hoped, as has often been the case in the 10 evolution of science, that after solving a number of specific At 10 operations a second, how many years will it take cases there will come a time and a person who will abstract and generalize the concepts so that a larger class of problems can 120 be solved using a single algorithm. Until then, special and to do 10 operations? specific algorithms have to be developed to solve specific and even apparently trivial problems. 1.3.3 As Yet Undiscovered Algorithms 1.3.4 Unsolvable Problems + ______________________________ ___________________ Formulating algorithms for activities which many of us Ideally we would like to generalize algorithms so that they perform without any conscious effort has proved to be as can be used to solve larger and larger classes of problems. difficult as discovering algorithms for new problems. Consider However this generalization of algorithms cannot go on the formulation of an algorithm by which a computer can indefinitely. For example, it is easy to write an algorithm for distinguish between a man and a woman. We usually make this bisecting an angle using a compass and a straightedge. Now one distinction without effort but often we are unable to state how might ask the question whether there is a similar algorithm for we made that decision. When asked, one often makes vague and trisecting an arbitrary angle by means of a compass and a ambiguous statements such as "Oh, by the dress, by the shape, by straightedge. The ancient Greeks tried in vain to discover such the sound of the voice, by the hair style, etc." While these are an algorithm. Much later a more sophisticated mathematics was perfectly logical and understandable clues for another person, used to show that they could not have succeeded -- that the set for a machine they are too imprecise. Let us assume that the of all angles they could generate with a compasss and computer is provided with some form of visual input. To straightedge simply did not include the answer they sought. (But 1 566 657 11 let us assume that we need to trisect some angles and have only 'i'), but it is surely not in the list since the number it a compass and straightedge; must we give up? Not necessarily: we generates is different in at least one digit from any other in can also show that arbitrarily close to the given angle there the list. Therefore our assumption is wrong, and thus there must exists an angle that we can trisect exactly. We can state be a number we cannot conceivably describe. iterative algorithms that will get us an angle as close to the answer as we desire.) Should the fact that certain classes of problems are algorithmically unsolvable be a cause of despair? Certainly not. Algorithmic unsolvability is not simply a statement that no The fact that there exists no algorithm for determining the algorithm has yet been found to solve a class of problems but convergence of every arbitrary sequence does not mean that there rather that it can never be found within the limitations we have is no algorithm for determining the convergence of certain set. There are several examples of problem classes which can subclasses of sequences. Unsolvability usually means that the never be solved by the use of a single algorithm. What is more, class of problems in question is too large, and that there is no the proofs of algorithmic unsolvability are characterized by the single algorithm capable of handling the entire class. It does same mathematical rigor as proofs in other branches of not mean that no sub-class of problems can be solved mathematics. algorithmically. The problem is both more serious and less serious than the In a practical sense, it is well to determine whether or example would indicate. It is less serious because truly not a problem is solvable before we expend much effort on it. In unsolvable problems are very rare and certainly never bother the the latter case we can usually find a similar problem for a beginning programmer. It is, however, more serious because there smaller, but still adequate, number of cases which will be are problems which are beyond reach of any conceivable method. solvable. Thus, theorems on unsolvability help the programmer to To establish a feeling for this concept, we will give a brief determine what can be achieved and to set his goals example. appropriately. The set of real numbers between 0.0 and 1.0 can be represented by the set of all strings of digits of the form 1.3.5 Historical Notes + ________________ .d d d d ... 1 2 3 4 The word algorithm comes from the name of a ninth century Arab mathematician, Al Khowarizmi. His writings were where each d is between 0 and 9 inclusive and no string is instrumental in introducing the present methods of numeration i into the western world. Mathematicians from the times of the ancient Greeks and Egyptians have been interested in algorithmic allowed to terminate in a string of all nines. We have described processes. Their progress in discovering algorithms was hindered an infinite set of infinitely long strings of digits with no by the problems of number representation. For example, they did trouble. (The key word was "all".) We now wish to demonstrate not have the concept of positional notation used in Arabic that there is at least one number between 0.0 and 1.0 that numerals nor the concept of logarithms. The representation cannot be described in English (or PL, or any other language). problem is by no means completely solved. Even today we are still concerned about the representation of numbers in computers By a description we will mean any finite set of finite so that we may perform arithmetic operations without sacrificing rules that will eventually allow us to write down as many digits potential speed to essential accuracy. of the described number as we might desire. Assume that we can describe all of the numbers between zero and one and consider Many mathematicians had dreamed of discovering an all- the set of all such descriptions. Since the descriptions are inclusive method for solving any problem. Leibnitz (1646-1716) finite, we may assume that the set of them is ordered with the attempted to find such a solution in vain, but felt that the shortest description first, and that among descriptions of the time would come when it would be discovered and that any same length they are ordered alphabetically. We can then talk argument among mathematicians could then be settled with paper about the i-th description and the i-th number described. The and pencil. Despite the long and persistent efforts of many description: great men, the difficulties in finding such an algorithm have remained insurmountable. Further, similar difficulties were "Let the i-th digit of this number be zero if the i-th encountered in trying to find algorithms for certain problems of digit of the i-th number is one, otherwise let the i-th a far less general nature. After many fruitless attempts to digit of this number be one." discover such algorithms, it became apparent that the difficulties involved were basic and it came to be suspected is surely a valid description (using the list of descriptions we that it is not possible to construct an algorithm for every assumed we already had, we can compute the i-th digit for any class of problems. One of the first to prove the algorithmic 1 657 724 12 unsolvability of certain classes of problems was the famous CHAPTER II logician A. Church. In 1936, he published a paper called "An Unsolvable Problem in Elementary Number Theory". LANGUAGES With the development of electronic computers, interest in theory and formulation of algorithms has increased considerably. 2.1 LANGUAGES AND COMMUNICATION However, the emphasis has shifted from the negative to the positive results. Instead of a preoccupation with proving the Man's development and the growth of civilization have been algorithmic unsolvability of certain classes of problems, people intimately involved with the evolution of language. Language is are now more concerned with the explicit formulation of an aspect of culture which is common to all human societies and algorithms for the classes of problems that are solvable. enables us to receive, communicate, and record our knowledge. Furthermore, with the ever-increasing usage of computers, more But there is no single language which can be used for universal and more people are involved in developing new algorithms for communication. Indeed, from time to time, one language may be problems which were not, until now, considered machine solvable more widely used than others, but attempts to find a "lingua problems. franca" have thus far proved unsuccessful. Exercise 1.3.9 Whatever the explanation for the existence of so many Read "From Numbers to Numerals and From Numerals to different languages, it is interesting to study the growth and Computation" by D. E. Smith and J. Ginsburg in James R. change of languages. Languages are continually in a state of Newman's "The World of Mathematics", Volume 1, page 442 flux, and the changes are neither systematic nor rational. As a (Simon and Schuster, 1956). result of such erratic (or irregular) development, natural languages are imprecise, ambiguous, and redundant. The first two Exercise 1.3.10 attributes, imprecision and ambiguity, concern the meaning of Read "Goedel's Proof" by E. Nagel and J. R. Newman on page statements in natural languages. The last attribute, redundancy, 1668, Volume 3 of the book above. concerns the "wordiness" of natural languages, i.e., the number of characters one needs to communicate a concept. Let us consider these aspects in some detail since they are also important for communication with a computer. 2.1.1 Ambiguity of Languages + ______________________ Ambiguity of languages arises, in general, from the use of the same word to serve different purposes, e.g. pen (play pen or ink pen), ward (a hospital room or a dependent child), pool (swimming pool or the game pool), etc. When you say "He is playing pool" and "He is playing in a pool" the intended meaning is clear from the presence or absence of the preposition "in". As a result of different meanings, a word may be used as different parts of speech, e.g., "Time flies like an arrow" and "Fruit flies like fruit". The term 'flies' is used as a verb and a noun. The term 'like' is used as an adverb and a verb. The term 'fruit' is used as an adjective and a noun. Thus one will obtain quite different sentence diagrams from the above sentences (see Section 2.2). There are many phrases, idioms, and cliches in the English language, the meaning of which is clear to us only because we adhere to standard forms of expression in ordinary situations; e.g., "The bride wore a white satin dress and carried a bouquet of roses; the bridegroom wore a happy smile and carried himself well." Ambiguity of this type can only be resolved by knowledge of the usage of the language. 1 724 815 13 2.1.2 Redundancy of Languages structure of a language. These notations prove to be convenient + _______________________ tools for learning programming languages; we introduce the Redundancy is a property of languages which arises from a commonest and most convenient of them here. superfluity of rules. It facilitates communication in spite of all the factors acting against successful communication and is essential for resolving the ambiguity of natural languages. 2.2.1 Parse Trees + ___________ Because of redundancy we can break some of the rules of the grammar without serious harm; but the more we break them, the Consider the statement "The tall nasty boy ate an apple." lower are our chances of successful communication. Our knowledge of the English language tells us that it is a sentence of the language and this fact can be illustrated by We can strip off all grammatical clues and still tell a diagramming the sentence according to the rules of the grammar simple story: Woman, street, crowd, traffic, noise, haste, as shown in Figure 2.2.1. Sentence diagramming is also called thief, bag, loss, scream, police. . . . The reader's past parsing of a sentence and the resulting diagram is called a experience of the language is sufficient to restore the missing parse-tree or syntax tree. elements with sufficient accuracy for the purpose. Why then do we need the complex syntactic rules for a language? Try reading The tall nasty boy ate an apple this book with as little redundancy. | | | | | | | <adj> <adj> <adj> <noun> <verb> <adj> <noun> The syntactical constraints of a language ensure that, to | | | | | | | some extent, we know already what will be said. We do not know | | | <noun phrase> | | <noun phrase> exactly what, but we know something about it. A linguist | | | | | | | referred to syntax as the "traffic rules of the language". | | └-------| | | | Various affixes, spelling rules, conjugation rules, etc., | | | | | | perform this function. | | <noun phrase> | | | | | | | | <direct object> Redundancy also helps us to overcome uncertainties | └-------------| | | | resulting from accent or handwriting. Because of inadequacies of | | | | | a language or of the speaker we may need to express the same | <noun phrase> | └----------| thought in several different ways to make sure that we have | | | | conveyed our meaning. "Repeating oneself" is another source of └-------------------| | <direct object> redundancy in languages. In fact, direct repetitions are often | | | used when we communicate under difficulties, as when conversing <noun phrase> └-----------------| over a noisy telephone line. | | <subject> <predicate> Ideally we would like to be able to communicate with | | computers in the same manner as we communicate with people, └----------------------------┘ e.g., in a natural language that we already understand. While we | are able to understand ambiguous sentences we do not yet know <sentence> how to specify an algorithm, i.e., a sequence of well-defined steps for resolving ambiguity. We do not yet know how to use Figure 2.2.1 A Sentence Diagram redundancy systematically to resolve English ambiguity. (This falls into the category of as yet undiscovered algorithms of How can one learn the rules for determining whether a given Chapter I.) Further we would like the language for communication string of characters is a valid sentence of a language? Either with computers to be concise with as little redundancy as is by unsystematic methods as taught in elementary schools or by consistent with reliable operation. This implies that such a formal methods where the rules are given as precise definitions. language should also be unambiguous because one cannot resolve Of the many attempts to formalize the rules of the English ambiguity without redundancy. grammar, one proposed by Chomsky has proved to be very useful. It is a simple and precise notation for describing the structure of languages. In this text we shall use a slight variation of 2.2 STRUCTURE OF LANGUAGES that notation as formulated by Backus and Naur. Since the 1950's there has been considerable interest in the formal aspects of communication, languages and structure of 2.2.2 Backus Naur Form - BNF + ______________________ languages. There have been many developments, one of which is the development of notations for precise description of the 1 815 902 14 How does one describe the structure of a language? For adjectives the above production would essentially be unending. example, we might want to state that a sentence is defined to be In a formal and precise system for describing languages such a a subject followed by a predicate and that the terms subject and construct would be unacceptable. This difficulty can be overcome predicate themselves have a predetermined structure. One can by the use of a recursive definition in which a term appears in write the description in English itself as we have done in the its own definition. E.g., preceding sentence. This can be long-winded. In BNF we would state the same fact this way: <noun phrase> ::= <noun> | <adjective> <noun phrase> <sentence> ::= <subject><predicate> Thus the noun 'boy' is a noun phrase. The phrase 'nasty boy' is an adjective followed by a noun phrase and, therefore, a noun Definitions in BNF, such as the above, are called productions. phrase itself. Similarly the term 'tall nasty boy' is again a The above production introduces much of the symbolism of BNF. noun phrase. Using a recursive definition, one can specify all Instead of writing 'is defined to be' every time, we use the the possible constructs of a noun phrase. Note that in any symbol '::=' . Instead of writing 'the structure of the term recursive BNF production, there must be at least one alternative "sentence" of the language' we write <sentence>. Juxtaposition rule that does not contain the term being defined. This of the terms <subject> <predicate> means that <subject> is particular construct provides the necessary starting point in followed by <predicate>. Whenever the term appears within the sentence diagramming. angular brackets <...> it is defined elsewhere, i.e., it appears on the left hand side of some BNF production. Such terms are A simplified grammar of English in Backus Naur Form is called non-terminal symbols of the language. Terms such as given in Figure 2.2.2. 'boy', 'apple', and 'ate' which only appear on the right hand side of the productions are called terminal symbols of the <sentence> ::= <subject> <predicate> language. <subject> ::= <noun phrase> <noun phrase> ::= <noun> | <adjective> <noun phrase> Consider the sentences 'The boy ate' and 'The boy ate an <noun> ::= boy | apple | ... apple'. In the first sentence the predicate is the verb 'ate'. <adjective> ::= a | an | the | nasty | tall | ... In the second, the predicate is 'ate an apple', i.e., a verb <predicate> ::= <verb> | <verb> <direct object> followed by a direct object. Thus, in English, a predicate can <verb> ::= ate | ... mean either a verb or a verb followed by a direct object. In BNF <direct object> ::= <noun phrase> one would state this fact as Figure 2.2.2 Backus-Naur Form Grammar for a Set <predicate> ::= <verb> | <verb> <direct object> of English Sentences. The vertical slash symbol '|' is used in BNF to define Exercise 2.2.1 alternative constructs of a language. One could of course write Parse (construct a BNF diagram of) the following sentence. this as two productions, without using the vertical slash '|': "Parsing is tedious work." <predicate> ::= <verb> Exercise 2.2.2 <predicate> ::= <verb> <direct object> Extend the grammar to include adverbs, compound subjects, compound predicates, and compound sentences. Then parse: "both men and machines parse sentences but machines do it 2.2.3 Recursive Definitions in BNF quickly and seldom make mistakes." + ____________________________ In English a noun can be qualified by any number of Exercise 2.2.3 adjectives. Thus 'The boy', 'The nasty boy', 'The tall nasty We are going to use the grammar in Exercise 2.2.2 to boy' would all be valid noun phrases. How can one define all the generate a sentence. Write <sentence> on a piece of paper. possible constructs for a noun phrase? One can state: Then roll a die and use the value to pick an alternative from the defining rules for <sentence>. (If there is only <noun phrase> ::= <noun> | <adjective> <noun> one, the choice is easy.) Substitute the right side of the | <adjective> <adjective> <noun> rule for <sentence>. Now there are other bracketed symbols. | <adjective> <adjective> <adjective> Pick one and repeat the process, etc. Will the process <noun> ... and so on. necessarily terminate? Will it usually terminate? Thus one writes out a separate construct for each case of 0, 1, Exercise 2.2.4 2, 3, 4 ... adjectives. Since there can be any number of Add an interesting set of nouns, verbs, adjectives, etc. to 1 902 995 15 the English grammar (for example: donkey, elephant, party, they could not conveniently express some concept in FORTRAN they vote, mad, chew, love, Republican, Democrat, agree) and added new constructs to the language. In this way, the number of repeat Exercise 2.2.3 several times. Be imaginative. different "dialects" of FORTRAN increased to the point that it is difficult to keep track of all the variations. 2.3 THE LANGUAGE PL A group of computer scientists from Europe and the U.S.A. met together in 1958 and in 1960 to develop a language more There have been many different languages developed for powerful and better defined than FORTRAN. The resulting communication with computers. As the problems to be solved language, ALGOL 60 (ALGOrithmic Language), was another important increased in difficulty and complexity, programmers found that step in the evolution of programming languages. ALGOL 60 there was no single language which could be used to solve the significantly extended and improved the constructs of the wide variety of problems. So while users solving mathematical language (block-structure, recursion, etc.). It also provided a problems used languages like FORTRAN and ALGOL, users with means for precisely defining the syntax of a language (see business problems used COBOL or RPG, and so on. Other languages Section 2.2). like LISP and SNOBOL were developed for symbol manipulation (more like algebra than arithmetic). There are a host of problem Another development, similar to the ALGOL 60 effort, was oriented languages like SIMSCRIPT, GPSS, AED, and so forth. Why initiated by the users interested in the commercial applications are there so many different languages? It is very simple. of computers. They found that FORTRAN did not provide the Languages, natural or programming, evolve and develop flexibility required for commercial applications. CODASYL, continuously. New words are added to the vocabulary and new (COnference on DAta SYstems Languages), a committee composed of constructs to the language. Such modifications and additions to several large users, the Federal Government, and computer a language are necessary because the sum total of human manufacturers developed COBOL (COmmon Business Oriented knowledge increases every day and, as it becomes necessary to Language), primarily for use in commercial applications. communicate and understand the new concepts, new words and phrases are coined. In natural languages these additions result After several years of use of FORTRAN, ALGOL, and COBOL, in somewhat haphazard development of the language. The same is many users realized that the differences between commercial and true of programming languages: programmers added new constructs scientific applications are mainly superficial. As problems to the languages as they saw fit, resulting in a bewildering increased in complexity, the users found that many features in number of dialects of the languages. the other languages would have been useful. This sentiment brought about the development of the language PL/I (Programming Language / I). 2.3.1 History of Programming Languages + ________________________________ PL/I was developed through a cooperative effort undertaken Many languages have been developed for communication with by IBM and two computer user groups, SHARE and GUIDE. A team of computers. Here we will describe the evolution of a few widely experts representing these groups attempted to unify the used computer languages: FORTRAN, ALGOL, COBOL, and PL/I. fundamental concepts underlying the other higher level languages so that a single language could be used to write both scientific FORTRAN is an abbreviation for FORmula TRANslator . It was and commercial programs. Did they succeed? Almost. The resulting developed by John Backus and his colleagues at IBM around 1956. language, while basically very good, has a few ad hoc and, at It was widely accepted because it was easier to learn and use times, conflicting features. While these features may be useful than any other programming language then in use. Prior to the for some specific applications, the resulting language is development of FORTRAN, a programmer had to specify each sometimes incoherent and lacks a unified structure. These short- individual machine operation, by writing the corresponding comings are but passing difficulties; it is hoped that many of operation code, either as a sequence of numbers (machine the annoying features will disappear in time. In any case, PL/I language) or as a mnemonic code (symbolic assembly language). is the best language generally available and is the obvious Conceptually simple operations (such as those of ordinary choice for this book. arithmetic) may require from two to half a dozen of these operation codes, and a machine language or symbolic assembly In this book we will introduce the reader to those language program bears very little resemblance to English. In constructs of the language which we consider essential for FORTRAN, some of the commoner constructs (arithmetic operations, communication with the machine. Certain constructs of the if-then, etc.,) were written in a form more or less language are simplified and a few new ones are introduced. Such corresponding to ordinary mathematical notation, and the machine deviations from the original language specification are few and translated these expressions into the appropriate sequences of are introduced only when they are considered to be significant machine instructions. Its development and growth have improvements to the language. Appendix II contains a precise understandably been somewhat haphazard. As people found that statement of all the additions to, modifications of, and 1 995 1077 16 omissions from the original language specification. After ┌--------------------------------------------------------------┐ understanding the contents of this book, the student should have | /* This program executes the Euclidean algorithm for finding | little trouble applying his skill in other dialects of PL/I. | the greatest common divisor of any two positive integers */ | Henceforth, we will refer to this language by the letters PL. | | |DECLARE (a,b,c) FIXED; | Exercise 2.3.1 |a = INPUT; | Write a brief resume of the history of ALGOL 60. See the |b = INPUT; /* get a,b from cards */ | Revised Report on the Algorithmic Language ALGOL 60, Naur |IF a < b THEN /* interchange the values */ | et al, Comm. ACM, Vol. 6 (January 1963), pp. 1-17. | DO; | | c = a; /* save a temporarily */ | | a = b; b = c; | 2.3.2 Structure of PL | END; | + _______________ |ELSE c = a; /* in case a already was >= b */ | Whether we write a note in English or a program in PL we |DO WHILE c ^= 0; | must follow certain rules and adhere to a certain overall | c = MOD(a,b); /* remainder of a/b */ | structure. When one writes a passage in English, a certain | a = b; /* g.c.d. when c = 0 */ | predetermined format is followed: the passage would consist of a | b = c; | sequence of sentences; sentences would be delimited by periods; |END; | sentences may be either simple sentences or compound sentences; |OUTPUT = a; | one may add footnotes to explain certain statements; and so └--------------------------------------------------------------┘ forth. Figure 2.3.2 The Euclidean algorithm in PL. A PL program has an analogous structure. A program is a sequence of statements; statements are delimited by semicolons; A program might consist of a single statement or a sequence of statements may be basic statements or compound statements; statements. This follows from the recursive definition in BNF: special paragraphing rules must be followed; comments are added to explain the function of various statements. Table 2.3.1 <program> ::= <statement list> summarizes these similarities. <statement list> ::= <statement> | <statement list> <statement> English PL --------------------------------------------------- The gcd algorithm given in Figure 2.3.2 illustrates the use structural element sentence statement of several different statements. (The reader is not expected to delimiter . ; understand the precise significance of each of these statements types of statements simple and basic and at this time. We shall discuss them in the next few chapters. compound compound However, one can deduce the function of each of these statements explanations footnotes comments from the comments and by looking at the corresponding algorithm paragraphing applicable applicable given in English in Figure 1.1.2.) Figure 2.3.1 Analogy between a passage in Statements in PL must follow grammatical rules, as do English and a program in PL. sentences in English; the only difference is that the rules of PL must be followed to the letter. These rules form the syntax Let us illustrate the structure of programs by a concrete of the language. Figure 2.3.3 gives a simplified version of the example. Figure 2.3.2 shows the GCD algorithm given in Section syntax of PL. This syntax is sufficient to introduce many of the 1.1.2 written in PL. basic concepts in the language. Figure 2.3.3 STUDENT PROGRAMMING LANGUAGE REFERENCE SYNTAX <PROGRAM> ::= <STATEMENT LIST> <STATEMENT LIST> ::= <STATEMENT> | <STATEMENT LIST><STATEMENT> <STATEMENT> ::= <BASIC STATEMENT> | <CONDITIONAL STATEMENT> <BASIC STATEMENT> ::= <ASSIGNMENT STATEMENT> ; 1 1077 1187 17 | <GO TO STATEMENT> ; <GO TO STATEMENT> ::= GO TO <VARIABLE> ; | <RETURN STATEMENT> ; | GOTO <VARIABLE> ; | <CALL STATEMENT> ; <RETURN STATEMENT> ::= RETURN | <DECLARATION STATEMENT> ; | RETURN <EXPRESSION> | <BLOCK> ; <CALL STATEMENT> ::= CALL <VARIABLE> | <GROUP> ; <ALLOCATION STATEMENT> ::= ALLOCATE <ALLOCATION LIST> | <PROCEDURE DEFINITION> ; <ALLOCATION LIST> ::= <ALLOCATION ELEMENT> | <ALLOCATION STATEMENT> ; | <ALLOCATION LIST> , <ALLOCATION ELEMENT> | <FREE STATEMENT> ; <ALLOCATION ELEMENT> ::= <IDENTIFIER> ( <BOUNDS LIST> ) | ; <BOUNDS LIST> ::= <BOUND> | <LABEL DEFINITION><BASIC STATEMENT> | <BOUNDS LIST> , <BOUND> <CONDITIONAL STATEMENT> ::= <IF CLAUSE> then <STATEMENT> <BOUND> ::= <EXPRESSION> | <IF CLAUSE> then <BASIC STATEMENT> | <EXPRESSION> : <EXPRESSION> else <STATEMENT> <FREE STATEMENT> ::= FREE <FREE LIST> | <LABEL DEFINITIONS> <FREE LIST> ::= <IDENTIFIER> <CONDITIONAL STATEMENT> | <FREE LIST>,<IDENTIFIER> <IF CLAUSE> ::= IF <EXPRESSION> <GROUP HEAD> ::= <CONTROL CLAUSE>; <BLOCK> ::= <BLOCK HEAD><STATEMENT LIST><ENDING> <CONTROL CLAUSE> ::= <REPETITION CONTROL> <BLOCK HEAD> ::= BEGIN; | <CONTROL CLAUSE><CASE SELECTOR> <GROUP> ::= <GROUP HEAD><STATEMENT LIST><ENDING> <CASE SELECTOR> ::= CASE <ARITHMETIC EXPRESSION> <LABEL DEFINITION> ::= <IDENTIFIER> : <REPETITION CONTROL> ::= <WHILE LIST> <ENDING> ::= END | <ITERATION LIST> | END <IDENTIFIER> <WHILE CLAUSE> ::= WHILE <EXPRESSION> | <LABEL DEFINITION><ENDING> <WHILE LIST> ::= DO <PROCEDURE DEFINITION> ::= <PROCEDURE HEAD><STATEMENT LIST> | <WHILE LIST><WHILE CLAUSE> <ENDING> <ITERATION LIST> ::= DO <VARIABLE>=<ITERATION ELEMENT> <PROCEDURE HEAD> ::= <LABEL DEFINITION> PROCEDURE ; | <EXPRESSION><INCREMENTATION CONTROL> | <LABEL DEFINITION> PROCEDURE <ATTRIBUTE LIST>; | <ITERATION ELEMENT><WHILE CLAUSE> | <LABEL DEFINITION> PROCEDURE <FORMAL PARAMETERS>; <INCREMENTATION CONTROL> ::= TO <ARITHMETIC EXPRESSION> | <LABEL DEFINITION> PROCEDURE <FORMAL PARAMETERS> | BY <ARITHMETIC EXPRESSION> <ATTRIBUTE LIST>; | TO <ARITHMETIC EXPRESSION> <FORMAL PARAMETERS> ::= ( <PARAMETER LIST> ) BY <ARITHMETIC EXPRESSION> <PARAMETER LIST> ::= <IDENTIFIER> | BY <ARITHMETIC EXPRESSION> | <PARAMETER LIST>,<IDENTIFIER> TO <ARITHMETIC EXPRESSION> <ATTRIBUTE LIST> ::= <ATTRIBUTE> <EXPRESSION> ::= <LOGICAL FACTOR> | <ATTRIBUTE LIST><ATTRIBUTE> | <EXPRESSION>|<LOGICAL FACTOR> <ATTRIBUTE> ::= (<ASTERISK LIST>) <LOGICAL FACTOR> ::= <LOGICAL SECONDARY> | <TYPE> | <LOGICAL FACTOR>&<LOGICAL SECONDARY> | ENTRY <LOGICAL SECONDARY> ::= <LOGICAL PRIMARY> | LABEL | ^ <LOGICAL SECONDARY> <DECLARATION STATEMENT> ::= DECLARE <DECLARATION LIST> <LOGICAL PRIMARY> ::= <STRING EXPRESSION> <DECLARATION LIST> ::= <DECLARATION ELEMENT> | <STRING EXPRESSION><RELATION><STRING EXPRESSION> | <DECLARATION LIST> , <DECLARATION ELEMENT> <RELATION> ::= < <DECLARATION ELEMENT> ::= <DECLARATION PRIMARY> | > | <DECLARATION PRIMARY><ATTRIBUTE LIST> | = <DECLARATION PRIMARY> ::= <IDENTIFIER> | <= | ( <DECLARATION LIST> ) | >= <ASTERISK LIST> ::= * | ^< | <ASTERISK LIST> , * | ^> <TYPE> ::= BIT | ^= | FIXED <STRING EXPRESSION> ::= <ARITHMETIC EXPRESSION> | FLOAT | <STRING EXPRESSION> || <ARITHMETIC EXPRESSION> | CHARACTER <ARITHMETIC EXPRESSION> ::= <TERM> <ASSIGNMENT STATEMENT> ::= <VARIABLE> = <EXPRESSION> | <ARITHMETIC EXPRESSION>+<TERM> | <VARIABLE> , <ASSIGNMENT STATEMENT> | <ARITHMETIC EXPRESSION>-<TERM> 1 1187 1276 18 <TERM> ::= <FACTOR> Compare, for example, the following program (Figure 2.3.4) | <TERM>*<FACTOR> with Figure 2.3.2. | <TERMS>/<FACTOR> <FACTOR> ::= <PRIMARY> ┌-------------------------------------------------------┐ | <PRIMARY>**<FACTOR> |DECLARE afuz FIXED; afuz = | | +<FACTOR> |INPUT; DECLARE (bfoo, c12c9) FIXED; | | -<FACTOR> |bfoo = INPUT; IF afuz < bfoo THEN DO; | <PRIMARY> ::= <CONSTANT> |c12c9 = afuz; /* sec? */ afuz = bfoo; | | <VARIABLE> |bfoo = c12c9; END; ELSE | | (<EXPRESSION>) |c12c9 = afuz; DO WHILE c12c9 ^= | <VARIABLE> ::= <IDENTIFIER> |0 | | <IDENTIFIER>(<SUBSCRIPT LIST>) |; | <SUBSCRIPT LIST> ::= <SUBSCRIPT> |c12c9 = MOD( | | <SUBSCRIPT LIST>,<SUBSCRIPT> |afuz, bfoo); afuz = bfoo; bfoo = c12c9; END; | <SUBSCRIPT> ::= <EXPRESSION> | OUTPUT = afuz; | | * └-------------------------------------------------------┘ Figure 2.3.4 A messy program Even without knowing the language, it is clear that this 2.3.3 Style of Programming in PL example is much less readable and clear. This is no joke. An + __________________________ experienced programmer can be much more obscure. Consider a Statements in PL are separated by the symbol ";" and by program of 3000 lines written this way. convention a new statement normally begins a new line. The first is a requirement of the language; the second is a matter of style. On card-oriented systems, each line of the program is 2.3.4 Paragraphing in PL + __________________ punched on a separate card. The convention facilitates the removal or modification of any statement without affecting any The paragraphing of a set of sentences is a means of other statement. This consideration becomes less important when grouping together all the sentences that are intended to convey one has a small set of very short statements. Thus a particular concept. Paragraphing of a set of sentences in English is indicated by starting the first sentence of the c = a; paragraph on a new line and indenting it by a few spaces. In PL a = b; conceptually related statements are indented by (say) three b = c; spaces as a group. The following two examples drawn from the gcd algorithm illustrate the use of paragraphing. might reasonably be placed on one line: ┌---------------┐ ┌-------------------┐ c = a; a = b; b = c; | IF a < b THEN | | DO WHILE c ^= 0; | | DO; | | c <- MOD(a,b); | If a statement is too long to fit on a single card, it may be | c = a; | | a <- b; | continued on succeeding cards; the end of the card is not | a = b; | | b <- c; | significant. | b = c; | | END; | | END; | | | Primarily, programs are used as instructions to the └---------------┘ └-------------------┘ computer. Often, however, it may be necessary for another person Figure 2.3.5 An illustration of paragraphing. (or yourself several weeks later) to follow through such programs and make additions or modifications. Even for an expert The first rule of paragraphing has to do with groups of it requires considerable effort to comprehend someone else's statements bracketed by one of the pairs: program. This process may be facilitated by the addition of comments or explanatory notes, comparable to footnotes in DO; ... END; English. In PL these notes may consist of ordinary sentences or BEGIN; ... END; anything else the programmer may choose, placed between the PROCEDURE; ... END; bracketing symbol pairs /*...*/. Comments make the programs readable, and they are useful to the programmer himself in In order to make absolutely clear which two symbols form a pair, understanding previously written parts of the program while more they must start in the same column of the program (e.g., DO and is being written. END in the previous examples). The statements enclosed by the 1 1276 1366 19 pair are related, thus are indented. Constants have a fixed meaning which is defined by the very same characters used in denoting them. For example: Similarly, the symbol IF denotes a condition that applies to the following statements only. To make it visually obvious 179, 393.69, 'ABRA KA DABRA' which statement is affected, the whole statement is indented (again, see the previous example). are constants. The meaning of the first two elements is obvious to anyone familiar with decimal notation. The element 'ABRA KA Paragraphing conventions will become clearer as we DABRA' is also a constant. It represents a fixed unchanging introduce the basic constructs of PL. All that we wish to convey sequence of characters contained within the quote marks. at this point is that there are paragraphing conventions which are essential in preserving programming style. Consistent There are four types of constants which are particularly indentations of (say) three spaces as indicated above are the useful in programming: integer and real numbers, logical values, most important. The machine, of course, does not use this and strings of characters. These primitives are chosen for a indentation information and will obey Figure 2.3.4 as readily as variety of reasons. Most important, they are quantities that are Figure 2.3.2. directly meaningful to people. We count with integers, measure with real numbers, record the truth or falseness of a proposition as a binary digit (1 = true, 0 = false), and read 2.4 ELEMENTS OF PL and write text. Some examples of numbers that we use day to day are: Like other languages, PL has an alphabet, a vocabulary of 30 words formed using the alphabet, and a set of rules (syntax) for 77, -539, 10 , forming statements using the vocabulary. We have already seen -319.83, .5894, 0158, 009.423, the syntax (Figure 2.3.3) in connection with the overall -7 structure of the language. In this section we will describe the -156000000, 0.00000000000357, 10 , etc. basic building blocks used in making up the statements. One writes constant numbers in PL in almost the same way one normally writes them for arithmetic calculations, except for 2.4.1 The Alphabet + ____________ 6 The alphabet of PL is similar to that of the English numbers of the form 156 x 10 . Because computers usually do not language. Note that PL is a contrived language specifically accept off-the-line notation (exponents, fractions), we use an designed for human communication with the computers. Since we are already familiar with the alphabet of English, it is 6 reasonable to have the machine recognize the same alphabet. This in-line notation. For example, 156 x 10 is written as 156E6 . alphabet usually consists of the letters Thus in PL, 77, -539, -319.83, .5894, 156E6, and .3E-7 are all A B C D ... Z and a b c d ... z; 5 -12 the digits valid constants. 3/2, 9 , 156 x 10 are not. How does one 0 1 2 ... 9 recognize what is a valid number and what is not? Here is where and some special symbols a precise BNF definition is useful. + - * / . ; . : <- ( ) = > < ^ & | $ _ # @ <number> ::= <unsigned number> On card-oriented systems the lower case letters are usually | + <unsigned number> omitted. In terminal-oriented systems many other special symbols | - <unsigned number> such as ≥, ≤, #, brackets, etc., may be included. Exactly what <unsigned number> ::= <decimal number> the alphabet is will be dependent upon the computer system | <decimal number> <exponent part> available for use. For the purposes of this book we will attempt <decimal number> ::= <unsigned integer> to use an alphabet which will make the example programs and | <decimal fraction> exercises most readable. Our readers will have to determine the | <unsigned integer> <decimal fraction> association of characters on their equipment and those used <exponent part> ::= E<integer> here. <decimal fraction> ::= .<unsigned integer> <integer> ::= <unsigned integer> | + <unsigned integer> 2.4.2 Constants | - <unsigned integer> + _________ <unsigned integer> ::= <digit> 1 1366 1445 20 | <unsigned integer> <digit> . 3 1 4 1 6 E + 1 <digit> ::= 0 | 1 | 2 | 3 | 5 | 6 | 7 | 8 | 9 | | | | | | | | | | <digit> <digit><digit><digit><digit>| | <digit> For example, let us parse the following: | | | | | | | | | | <unsigned integer> | | | | | | <unsigned int> 5 4 2 | | | | | | | | | | | | | |----------┘ | | | | └-------| <digit> <digit> <digit> | | | | | | | | | | | <unsigned integer> | | | | <integer> <unsigned integer> | | | | | | | | | | | | | |-----------------┘ | | └---------| |-----------------┘ | | | | | | | | | <unsigned integer> | <exponent part> <unsigned integer> | | | | | | | | | |------------------------┘ | | |-----------------------------┘ | | | | | | <unsigned integer> | | <unsigned integer> | | | | | | |-------------------------------┘ | <decimal number> | | | | | <unsigned integer> | <unsigned number> | | | | └---------| | <number> | | <decimal fraction> | Example 1. Parse of the <number> 542 | | <decimal number> | | | └--------------------|------------------------┘ | <unsigned number> | <number> Example 2. Parse of the number .31416E+1 Exercise 2.3.1 Which of the following are valid numbers in PL? -5 7 -317, 0.0000317, 3.17*10 , 2E-14, 3/7, 3 , -317.893, -317.-893 Although we are perhaps less familiar with logical values and strings of characters, they are nevertheless as important as numeric constants in problem solving with a computer. There are only two logical constants, true and false. Statements such as "you are a girl", "John is taller than Steve", and "A is less than B" can only have one or two values, true or false. (Instead of writing true and false one may use the digits 1 and 0 to represent these constants. This representation is merely a notational convenience (but it will cause type conversions); many other representations are used in the scientific notation in other fields: zero and non-zero, positive and negative, etc.) 1 1445 1534 21 A string constant is any string of characters within quote 2.4.4 Identifiers + ___________ marks, e.g., 'KHAN KUBLA KHAN', 'My name is Tom Dick Harry', 'A3B7C6', '123.76'. Any valid character of the alphabet may be In English we are constantly modifying, adding, and coining included in the string. The one exception is a quotation mark new words, e.g., pundit, nitwit, debugging, etc. Even in PL we since it is used to signify the end of the string constants. You coin new words: while writing a program we coin words to denote may, however, specify a quotation mark in the string by placing entities which we wish to deal with in the program. A main two quote marks one after the other, e.g., difference between natural and programming languages is that 'JOHN SAID ''I AM FINE''.' when we coin a new word in English it usually becomes a which will be stored in the computer as permanent addition to the language with its own special meaning. JOHN SAID 'I AM FINE'. In programming languages when we coin a new word it is only meaningful within the program in which it exists. The usage is similar to that of mathematics where one commonly introduces 2.4.3 The Reserved Vocabulary symbols with a new meaning which is to be valid only in a local + _______________________ context. In mathematics, however, the tradition is to use a In English, certain words serve the function of single hieroglyphic instead of a word. connectives: in, of, to (prepositions); and (conjunctions); a, an, the, (articles); etc. While the meaning of a sentence may be There is a predetermined format in PL for the coining of clear even without the use of these words, they permit us to new words. These new words are called identifiers. An identifier anticipate what might be said next. (See Section 2.1.2 on must begin with a letter and may be followed by any number of redundancy). In PL we have similar sets of words, the reserved letters or digits or <break character>s. Using the recursive words, which have special meanings when used in a program. These definition of BNF we can state this fact formally. are given in Figure 2.4.1. <identifier> ::= <letter> The meaning and usage of the reserved words will become | <identifier> <letter> clear during the next few chapters. All that we wish to | <identifier> <digit> emphasize at this point is that these reserved words serve some | <identifier> <break character> predetermined functions and may not be used otherwise. One might <break character> ::= # | _ | @ argue that in English 'And is the subject of the sentence' is a perfectly valid sentence and that 'and' need not always be used Let us parse 'BIG', 'B2/N', and '5_BNF' to discover which of as a conjunction. In PL one does not have that flexibility. these are acceptable as identifiers. In this text, we will distinguish reserved words from the 1. Parse BIG rest by printing them in bold face. Such a distinction makes for more readable programs. (Most computers have no provision for B I G reading bold face and therefore do not distinguish between bold | | | face type and regular type.) <letter> | | | | | ALLOCATE FLOAT <identifier> | | BEGIN FREE | <letter> | BIT GO | | | BY GOTO |__________| | CALL IF | | CASE INITIAL <identifier> | CHARACTER LABEL | | DECLARE PROCEDURE |_____________| DO RETURN | ELSE THEN <identifier> END TO ENTRY WHILE FIXED Figure 2.4.1 List of Reserved Words 1 1534 1600 22 2. Parse B2/N D.C. There are many similar terms in English: "The-Queen-of- England", "Baseball-pitcher-of-the-year", "Wimbledon-champion", B 2 / N "Senior-Senator-from-California", etc. Such terms may be | | | | collectively called abstract nouns. <letter> | | | | | | | The analogous term in programming languages is the <identifier> <digit> | | variable. A variable has three terms associated with it: a name | | | | (the President of the U.S.), an address (White House), and a |_________| | | value (Abraham Lincoln). A variable can take on different values | | | at different times and is stored in the computer memory at a <identifier> neither <letter> nor <number> location given by the address and it is referred to in the hence not an <identifier> higher level languages by its name. The name and the value of a variable are two different entities. However, the name is sometimes used imprecisely to denote the value associated with 3. Parse 5_BNF the name just as "The President of U.S." without any qualification usually refers to the person holding the office at 5 _ B N F the present time. In contrast, the name of a constant denotes | . . . the value and the concept of address is irrelevant. <number> . . . not an <identifier> We coin variable names as we need them while writing a program. Any valid identifier can be used as the name of a variable. In this text we will distinguish names from the rest by printing them in small letters. 2.4.5 Variables + _________ In PL, identifiers are mainly used as names of variables to be used in a program. Thus you may coin any names that you consider appropriate for the problem at hand, e.g., 'root', 'prime', 'president', etc. A variable is an entity which can take different values at different points in the computation and is stored in a specific location(s) in the computer memory. We have seen in Chapter I that every computer has a memory or storage unit. This memory is divided into chunks (or bits) called words that we can refer to all at once. Each word has a preassigned address, say for example, a number between 0 and 65,535 (i.e., assuming that the memory is in fact divided into 65,536 words). A computer word is a place to store information. The information we wish to store may be an instruction of the algorithm or an item of data to be operated upon by the algorithm. One can uniquely refer to or alter the information stored in a word in a single operation. Whenever new information is stored in a word, the previous information is lost. This is called destructive read-in and is analogous to overwriting old songs by new ones on a tape recorder. One can, however, refer to the information any number of times just as one can listen to the tape recorder any number of times without destroying the song on the tape. This is called non-destructive read-out . We can illustrate the role of a variable by an analogy. Consider the term "The-President-of-United States". Depending on the era he may have been Washington or Lincoln or Taft or Roosevelt or ... His address is the White House, Washington, 1 1600 1687 23 CHAPTER III DECLARE mean FLOAT; DECLARE variance FLOAT; STATEMENTS IN PL Every declaration statement begins with the reserved word DECLARE and is followed by the name to be introduced and its We have already seen the basic building blocks of PL: data type. If we wish to introduce a lot of names it would be alphabet, arithmetic expressions, constants, variables, reserved tedious to repeat DECLARE each time, and therefore PL has words, etc. In this chapter we will learn how one can use these facilities for introducing several names in one declaration basic elements to construct statements and how one can use these statement. For example, the above statements can be combined to statements in formulating algorithms. The statements of PL must form a single declaration statement: follow certain grammatical rules, as must statements in a natural language such as English (see Figure 2.3.3). DECLARE mean FLOAT, variance FLOAT; We have seen that a variable is an entity which can assume Suppose we also wish to use 'a', 'b', and 'c' as names for different values, is stored at a unique address in memory, and integer valued variables and 'text' as a string variable. We can be referred to by its name. Thus the first thing we should could extend the previous declaration statement to read: learn is how to inform the machine of the names we wish to use in our program. DECLARE mean FLOAT, variance FLOAT, a FIXED, b FIXED, c FIXED, text CHARACTER; 3.1 DECLARATIONS Now we can give a formal definition of the facts we know about a We introduce the names we wish to use by means of a declaration statement. declaration statement. It is not enough to merely declare the names; we must qualify the names by specifying one or more <declaration statement> ::= DECLARE <declaration list>; attributes for them. We have learned that there are four <declaration list> ::= <declaration element> different types of constants: integers to count with, real | <declaration list> , <declaration element> numbers to measure with, logical constants to indicate the truth <declaration element> ::= <identifier><type> and falsity of statements, and character strings with which to <type> ::= FIXED | FLOAT | CHARACTER | BIT read and write. A particular variable may hold any of the values of just one of these four types, so when we introduce a variable Example: name we must also give it the appropriate attribute, viz., DECLARE x1 FLOAT ; either FIXED, FLOAT, BIT, or CHARACTER. | | | | | <identifier> <type> | ┌----------------------------------------┐ | | | | | attribute value type and use | | |__________________| | |----------------------------------------| | | | | BIT logical; true and false | | <declaration element> | | FIXED integer; counting | | | | | FLOAT real; measuring | | <declaration list> | | CHARACTER text; communicating | | | | └----------------------------------------┘ |_____________________|______________| Figure 3.1.1 Correspondence between | data types and attributes in PL <declaration statement> The terms used for the attributes are indicative (as we will This declaration statement informs the machine that it later see) of the computer representation of the corresponding should expect to encounter something called 'x1', and that a data types, and that correspondence should be clearly memory location suitable for real numbers should be set aside understood. for 'x1' to occupy -- rather like an advance reservation at a hotel: "Smith, Mr. and Mrs.", meaning "hold a double room in the Let us consider some examples of declaration statements name of Smith". Declaration statements are thus in a special before giving a formal definition. We can indicate our intention category in that they do not do anything to the variables but to use the names 'mean' and 'variance' to represent two real- rather are a preliminary to doing something. The real action valued variables by the statements: begins when 'x1' (or Smith) arrives on the scene. At that point we encounter the subject of Section 3.2. 1 1687 1754 24 3.1.1 Factoring of Attributes DECLARE ( mean , variance ) FLOAT , text CHARACTER ; + _______________________ | | | | | | | | | | | Consider the declaration statement: | |<identifier> |<identifier> |<type> | <ident.> <type> | | | | | | | | | | | | DECLARE mean FLOAT, variance FLOAT, a FIXED, b FIXED, | |<decl. prim.>|<decl. prim.>| | |<decl.prim.>| | c FIXED, d FIXED, text CHARACTER; | | | | | | | | | | | | |<decl. elem.>|<decl. elem.>| | | |_______| | | | | | | | | | | | Several of the names in this declaration statement have the same | |<decl. list> | | | | | | | attributes. Could we not avoid repeating types like a broken | | | | | | | | <decl. elem.> | record? Indeed we can, by factoring the types. In the example | | | | | | | | | | above we can group together 'mean' and 'variance', both of which | | |______|______| | | | | | have the type FLOAT, and 'a', 'b', 'c', and 'd', all of which | | | | | | | | have the type FIXED. By placing all the names with the same type | | <decl. list> | | | | | within parentheses we can avoid repeating ourselves. | | | | | | | | | |_____________|_____________| | | | | DECLARE (mean, variance) FLOAT, (a,b,c,d) FIXED, | | | | | | text CHARACTER; | <decl. prim.> | | | | | | | | | | | |_________________| | | | We must modify the formal definition to accommodate factoring. | | | | | We do this by rewriting the definition of declaration element as | <decl. elem.> | | | follows: | | | | | | <decl. list> | | | <declaration element> ::= <declaration primary> | | | | | |<declaration primary><type> | |____________|________| | <declaration primary> ::= <identifier> | | | | ( <declaration list> ) | <declaration list> | | | | |________________________________________|__________________| Let us parse DECLARE (mean, variance) FLOAT, text CHARACTER | according to the above definition and discover if the statement <declaration statement> is syntactically correct. Exercise 3.1.1 Verify in detail the parse tree in the preceding diagram. Exercise 3.1.2 Parse DECLARE (mean, variance) FLOAT, (a,b,c) FIXED, text CHARACTER; 3.2 ASSIGNMENT STATEMENTS An assignment statement is a command to the computer to perform some operations on data and assign the result as the value of a variable. <assignment statement> ::= <variable> = <expression>; The expression on the right side of the 'equals' sign is evaluated and the result is stored in the computer memory at the address corresponding to a variable name. The previous value of the variable is erased. 1 1754 1840 25 Let us illustrate the function of the assignment statement tom = dick / tom; by means of a post-office-box analogy. Suppose we have boxes tom = tom + dick - harry; labeled 'tom', 'dick', and 'harry'. Let each of the boxes harry = harry / 2 contain a card with a number written on it, say, 4, 2, and 9 respectively. If you have performed the above exercise correctly, the boxes 'tom', 'dick', and 'harry' should contain 26, 25, and 2 ┌---------┐ ┌----------┐ ┌---------┐ respectively. The statement tom = tom + 1 might appear to be a | tom | | dick | | harry | contradiction. But note that the assignment statement is a | ┌-┐ | | ┌-┐ | | ┌-┐ | command, not a statement of algebraic equality. While a = b and | |4| | | |2| | | |9| | b = a imply the same fact in algebra it is not so in an | └-┘ | | └-┘ | | └-┘ | assignment statement. a = b commands the computer to replace the └---------┘ └----------┘ └---------┘ value of 'a' by that of 'b', and b = a, the opposite. While the values of 'a' and 'b' will be equal after the execution of the Now the effect of the assignment statement command, the common value will be the prior value of 'b' in the case of a = b, and that of 'a' in the case of b = a. dick = 12; will be to open the box labeled 'dick', erase the number 2 on 3.2.1 Expressions + ___________ the card and write the number 12 in its place. So the new numbers in the boxes will then be 4, 12, and 9. There are three types of expressions that may appear on the right side of the assignment statement: arithmetic expressions, ┌---------┐ ┌----------┐ ┌---------┐ string expressions, and logical expressions. An expression | tom | | dick | | harry | describes an algorithm for computing a value. If the value of | ┌-┐ | | ┌--┐ | | ┌-┐ | the expression is a number (either integer or real) then the | |4| | | |12| | | |9| | expression is called an arithmetic expression; if the value is a | └-┘ | | └--┘ | | └-┘ | string of characters then the expression is called a string └---------┘ └----------┘ └---------┘ expression; if the value is either TRUE or FALSE then it is a logical expression. Now suppose we say harry = tom + 3. The machine knows how to do arithmetic, so the effect will be to add 3 to the number An expression may consist simply of a constant or a contained in 'tom' (4 + 3 = 7) and store the result in 'harry', variable as on the right of the assignments "dick = 12;", "harry i.e., erase the old number (9) and store the new one (7). The = tom;", and "name = 'John Smith';". In such cases the value of contents of the boxes will then be as follows: the expression is that of the constant or the variable. An expression may also consist of a succession of operators and ┌---------┐ ┌----------┐ ┌---------┐ operands; in this case it is a command to perform the specified | tom | | dick | | harry | operations on the specified operands, and the result is taken to | ┌-┐ | | ┌--┐ | | ┌-┐ | be the value of the expression. | |4| | | |12| | | |7| | | └-┘ | | └--┘ | | └-┘ | The operators that may appear in expressions can be grouped └---------┘ └----------┘ └---------┘ into three classes as shown below. Thus, one can perform various operations on the number contained resulting value | operators in any of the boxes and store the result back in any box. -----------------┼---------------------------------- arithmetic | +, -, * (multiplication), /, Exercise 3.2.1. | ** (exponentiation) Suppose the boxes 'tom', 'dick', and 'harry' have the string | || (catenation) attribute FIXED and contain numbers 4, 7, and 9, and we logical | <, <=, =, >=, >, ^ (not), ^=, perform in succession the following assignment statements | | (or), & (and) using them. Fill in the new contents of the boxes after performing each of these statements. The following examples illustrate the use of the operators in expressions: dick = tom + harry - 3; tom = tom + 1; harry = harry - tom; dick = tom * tom; /* multiplication */ 1 1840 1936 26 Expression Remarks precedence levels and mixed expressions. ---------- ------- 1. a + b/c - 4.7 Add the value of 'b' divided by The variable on the left side of the assignment statement 'c' to the value of 'a' and should normally be of the same data type (FIXED, FLOAT, subtract 4.7 from the result. CHARACTER, or BIT) as the value of the expression on the right. 2. (a + b)/c Divide the value of 'a' plus 'b' If the data types are different, then the value of the by the value of 'c'. expression is converted to the data type of the variable before 3. 'MY NAME IS ' || 'JOHN' Value is 'MY NAME IS JOHN' storing. However, if the conversion is meaningless, an error 4. 'MEAN = ' || a + b If the value of a + b is 3.7, then indication will be printed. The following example illustrates the value of the expression is various type conversions. 'MEAN = 3.7'. 5. a + b < c + d TRUE if a + b is less than c + d; ┌---------------------------------------------┐ FALSE otherwise. | DECLARE a FLOAT, b FIXED, c CHARACTER; | 6. name ^= 'Smith' TRUE if name is not equal to | a = 5.4; | 'Smith'; otherwise FALSE. | b = 3; | | c = 'nothing'; | Arithmetic operations are performed before string operations, | c = a; /* result is '5.40000' */ | and logical operations are performed last (see examples 4 and | a = c; /* result is 5.40000 */ | 5). Even within each class certain operations are performed | b = a; /* result is 5 */ | before others (see example 1 where division is performed before | a = b; /* result is 5.00000 */ | addition and subtraction). Figure 3.2.1 gives the precedence └---------------------------------------------┘ levels for all the operators indicating the sequence in which various operations are performed. This precedence of operations Exercise 3.2.2. can be superseded by enclosing any expression within Why are the following assignment statements syntactically parentheses. In such cases the parenthesized expression is incorrect? evaluated before it is used as an operand. 2 = 2; b*b-4*a*c = discriminant; ┌--------------------------------------------------------------┐ | level symbol | Exercise 3.2.3. |--------------------------------------------------------------| Determine which of the following are syntactically |first | prefix + and -, exponentiation: ** | correct. If incorrect, what are the errors? |second | multiply and divide: *, / | (a) DECLARE 2.3a CHARACTER; |third | infix + and - | (b) DECLARE a FIXED; |fourth | || | (c) Suppose 'a' has been declared as in (b) above. |fifth | relational operators: <, <=, =, >=, >, ^<, ^=, ^> | a = 2.3; |sixth | not operator: ^ | |seventh | and operator> & | Exercise 3.2.4. |eighth | or operator: | | What is the value of 'a' as the result of the following |________|_____________________________________________________| sequence of statements? Table 3.2.1 Precedence levels of operators DECLARE a FIXED; a = 0; a = 1; a = a + 1; a = 2 * (a + 1); a = 3 * a - 1; A prefix + or - precedes a constant or variable, showing the (answer: 17) value to be either positive or negative as in the expressions -a, +b. An infix + or - is an arithmetic operation symbol denoting addition or subtraction as in the expression a + b. 3.2.2 Temporary Variables + ___________________ If an expression contains operands of different data types, Sometimes we need to exchange the values of two variables then the operands are converted to an appropriate data type (see GCD algorithm, Figure 1.1.2). Suppose we wish to store the before the operation takes place. Since unnecessary use of mixed value of 'a' in 'b' and the value of 'b' in 'a'. Consider the data types in an expression leads to inefficient use of the effect of the following statement sequence. computer, in some systems a warning message is printed on every occurrence of a mixed expression. b = a; /* store the value of 'a' in 'b' */ a = b; /* store the value of 'b' in 'a' */ Sections 3.3, 3.4, and 3.5 provide a precise definition of various types of expressions, and a more detailed discussion of Let us do a hand simulation of the above sequence using 10.5 and 1 1936 2019 27 3.6 as values of 'a' and 'b'. We may not store any result into INPUT, i.e., the variable INPUT may not appear on the left side of an assignment Initial statement. Similarly we may not refer to the value of the Value after b = a after a = b variable OUTPUT, i.e., OUTPUT may not appear in expressions. ------- ----------- ----------- This restriction will be clearly understood if one considers the a 10.5 10.5 10.5 possibility that variables may have addresses in read-only, b 3.6 10.5 10.5 write-only, and read-write memories. INPUT is a variable stored in read-only memory and, therefore, one must not try to change Note that we have not achieved our objective of exchanging the its value by letting INPUT appear on the left side of an values of 'a' and 'b'. assignment statement. Similarly OUTPUT is in write-only memory and, while one may change its value, one may not try to refer to The difficulty arises from the sequential execution of the value (in an expression). All the user-declared variables statements. What we need is simultaneous assignment of 'a' to are stored in read-write memories. 'b' and 'b' to 'a', but there is no such facility in PL. The next best thing is to save the value of 'b' (in the above hand Exercise 3.2.6 simulation example) in a temporary variable to make it available Write a program to read four numbers and store them in for later computations. The following statement sequence will variables 'a', 'b', 'c', and 'd', add them and store the exchange the values of 'a' and 'b' as desired. result in 'sum', and print the result 'sum'. (At this point the reader should be able to start writing and running temp = a; /* save the value of 'a' in temp */ simple programs on a computer. Before doing so he should a = b; /* overwrite 'a' by the value of 'b' */ read Sections 4.1 and 5.1.) b = temp; /* store the former value of 'a' (in 'temp') in 'b' */ 3.2.4 Input Data + __________ We must save the value of a variable in a temporary variable if we need it for some future computation and if it will be We have stated that if the variable INPUT occurs within an destroyed in an intermediate step. expression the next data item in the queue at the standard input device is used as its value. Data might be punched in cards or entered from the keyboard. Data items are separated by one or 3.2.3 Input, Output, and Assignment more blank spaces or a comma. Integers and real numbers are + _____________________________ punched (or typed) in the form similar to the constants and may In PL there are two special variables 'INPUT' and 'OUTPUT' also have a sign associated with them: 5.3, 6, 7.893E-9, -0.008, which are not declared. Like other variable names these also etc. Logical data are punched as TRUE or FALSE. String data are have both an address and a value associated with them. However, enclosed within quote marks, e.g., 'I am Foyt'. unlike other variables, the address is not a specific location in the computer memory. The address of the variable INPUT is the When we say standard input device attached to the computer (card reader or a = INPUT; terminal). The address of the variable OUTPUT is the standard the next data item from the input device is obtained and stored output device attached to the computer (line printer or in 'a'. A check is made to see if a type conversion is required, typewriter). The value of INPUT is the next data item available and if so, it is done. from the input device. The variables INPUT and OUTPUT are used to read data from 3.2.5 Multiple Assignments + ____________________ the input device and print results on the output device, i.e., for communication between man and computer. When we want to read It is possible to assign the value of an expression to more a data item from the input device and put it in a variable than one variable. For example, 'height', we say a, b, c = 0; sets the value of the variables 'a', 'b', and 'c' to 0. Thus we height = INPUT; must modify the definition of an assignment statement: When we want to print the result stored in a variable <assignment statement> ::= <variable> = <expression>; 'mean_height', we write | <left part><assignment statement> <left part> ::= <variable> , OUTPUT = mean_height; Exercise 3.2.9. 1 2019 2108 28 Parse a, b, c = (a + b + c)/3 . multiplication causes confusion. This expression can denote either |a| x b x |c| or |a x |b| x c|. A less serious source of In the above exercise, if 'a', 'b', and 'c' were of different confusion is the letter 'x' and the multiplication sign 'x'. In data types, then the values 'a', 'b', and 'c' may not be the PL we avoid these possible ambiguities by allowing neither same. For example juxtaposition nor the use of 'x' to denote multiplication. We use instead only the symbol '*'. DECLARE (a, c) FLOAT, b FIXED; a, b, c = 3.7; Another source of difficulty is the use of off-the-line notation, e.g., subscripts, superscripts, and prescripts. The will result in terms ┌---------┐ ┌---------┐ ┌---------┐ d | a | | b | | c | c | ┌---┐ | | ┌---┐ | | ┌---┐ | a + bx b | |3.7| | | | 3 | | | |3.7| | ------------ and a provide an indication of the problems | └---┘ | | └---┘ | | └---┘ | d + ex i └---------┘ └---------┘ └---------┘ c + ------ j f + gx k This is because the statement involved. Computers do not usually have facilities for input and a, b, c = 3.7; output using off-the-line notation. In PL we will use '/' to is equivalent to denote division and '**' to denote exponentiation. Subscript a = 3.7; b = 3.7; c = 3.7; notation will be introduced in a later section. with all the assignments taking place simultaneously. The right side is evaluated only once. As in mathematical notation, expressions in PL can contain certain functional forms (to be described below). For example, Exercise 3.2.10. the following are valid arithmetic expressions in PL. Punch a card according to the following grammar: a + SIN(b) <student card> ::= <name><address><class><major> a * SIN(b) + c <name> ::= <last name><first name> LOG(a) + SIN(b) * EXP(c) - 10 <address> ::= <number><street> ABS(a) * SQRT(a + b) | <room number><building> <class> ::= 13 | 14 | 15 | 16 There are two important differences. One may not use special functional symbols such as the square root sign and '| |' where <last name>, <first name>, <street>, <building>, and (absolute value), and one must always enclose function arguments <major> are character strings describing you, and <number> in parentheses. and <room number> are the appropriate integers. Spaces should separate the items. Write a program to read the The following table indicates the correspondences between card, then print it in a readable form. mathematical notation and PL notation. ________________________________________________________________ | Mathematical Notation | PL 3.3 ARITHMETIC EXPRESSIONS |---------------------------┼--------------------- Operation |Operator |Example |Operator|Example A number-valued expression is called an arithmetic --------------┼-----------┼---------------┼--------┼------------ expression (see 3.2.1). The notation used to represent addition | + |a + b | + |a + b arithmetic expressions resembles ordinary mathematical notation, subtraction | - |x - y | - |x - y but with certain restrictions which we shall now consider. multiplication|x,.,nothing|axx+b.y+cz | * |a*x+b*y+c*z | | b | | Mathematical notation can be ambiguous. Consider the division |/ , -, |a/x + - + c / z| / |a/x+b/y+c/z expression seven/ten. What is its value? It can be 0.7 or sev/t | | y | | depending on whether you are doing arithmetic or algebra. (Why?) | | 2 | | Use of juxtaposition to denote multiplication can lead to exponentiation| |(b - 4ac) | ** |(b**2-4*a*c) ambiguity. Consider another expression '|a|b|c|', where the ______________|___________|_______________|________|____________ combination of the absolute value operation and implicit 1 2108 2192 29 Exercise 3.3.1. FUNCTION FUNCTION VALUE Which of the following expressions are valid in PL? Write -------- -------------- down a correct form for those that are not. ABS(x) absolute value of the argument ATAN(x) arctangent(x), 'x' must be in radians (a+bx)/(c+dx) COS(x) cosine(x), 'x' must be in radians x 2 EXP(x) e a+b*x FIXED(x) 'x', converted to an integer number by truncating ------ the fractional part 2 FLOAT(x) 'x', converted to a real number c+d*x INDEX(t,s) the starting position of string 's' when imbedded in string 't' 1.12c * (r*sin(x))/(s*cos(x)) LENGTH(x) number of characters in the string 'x' LOG(x) ln(x) (Error if x <= 0 .) a**b**c MAX(x,y,...) maximum of all the arguments MIN(x,y,...) minimum of all the arguments MOD(x,y) remainder after division of 'x' by 'y' to yield 3.3.1 Arithmetic Functions an integer quotient + ____________________ RANDOM a random number uniformly distributed In mathematical notation a function is defined to be a between 0 and 1 relation of the form y = f(x) in which 'y' is uniquely defined SIGN(x) 1, 0, or -1 depending on whether 'x' is given 'x'. In PL the statement y = f(x) is a command to positive, zero, or negative calculate the function 'f' of the current value of the variable SIN(x) sine(x), 'x' must be in radians 'x' and store the result in 'y'. The function 'f' is evaluated SQRT(x) the non-negative square root of 'x' (Error before any arithmetic operations are performed using it. if x < 0 .) Further, an argument of the function need not be a variable; it can be any valid expression. Of course, a function may have any (If 'r' is the radius of a circle, then the angle at the number of arguments (including none at all). All the function center of the circle subtended by an arc of length 'r' is called names must be valid identifiers and one usually avoids using a radian. An angle can be converted to radians by using the long function names such as 'square-root' and abbreviates to a name like 'sqrt'. We can formalize some of the above facts by n x 3.14159265 the following definition: formula ------------------ where 'n' is the number of degrees 180 <function designator> ::= <identifier> |<identifier>(<argument list>) in the angle and 3.14159265 is the approximation of pi.) <argument list> ::= <argument> |<argument list> , <argument> The functions we have specified here are mainly used to <argument> ::= <expression> perform operations on numeric data (integers and real numbers). There are other built-in functions in PL which will be Exercise 3.3.2. introduced in Sections 3.4 and 3.5. A complete list of built-in Determine which of these are valid function designators: functions is given in Appendix III. RANDOM, x, SQRT(x), |x|, MAX(x*x,4*a*c). Exercise 3.3.3. The following built-in (implicitly defined) arithmetic valued Write a program to spot-check the built-in functions SQRT, functions are available in PL. SIN, and COS for accuracy. Be sufficiently clever so that you do not have to look up any values in a table. 3.3.2. Hierarchy of Operations in Arithmetic Expressions + _________________________________________________ We have illustrated the structure of arithmetic expressions by means of examples and by showing that they are almost like algebraic expressions except for a few notational differences. The fact that arithmetic expressions are similar to algebraic expressions does not obviate the need for a precise definition. 1 2192 2278 30 Consider the simple expression a + b/c. Does it mean (a+b)/c 2. In an expression without parentheses the precedence is implicitly defined. b or a + (-) ? Attempt 1 c a + b * c | | | | | Arithmetic operations can be defined so that the order of <variable> | <variable> | <variable> operations is implicit within the definition. We have been | | | | | taught that in an expression such as a + b * c, multiplication <primary> | <primary> | <primary> is to be performed before addition (see also Section 3.2.1). We | | | | | then say that mulitplication has precedence over addition. We <factor> | <factor> | <factor> can order the arithmetic operations in the sequence in which | | | | | they must be performed: exponentiation, multiplication and <term> | <term> | <term> division, addition and subtraction. This hierarchy is implicit | | | | | in the following BNF definition of arithmetic statements. └-------┼------┘ | | | | | <arithmetic expression> ::= <term> <arith.exp.> | | |<arithmetic expression> + <term> | | | |<arithmetic expression> - <term> └--------------┼------┘ <term> ::= <factor>|<term> * <factor>|<term> / <factor> | <factor> ::= <primary>|<primary> ** <factor> ? | + <factor>| - <factor> FAILURE <primary> ::= <constant>|<variable>|<function designator> |(<arithmetic expression>) Attempt 2 a + b * c The above definition provides for various possible forms of | | | | | arithmetic expressions. <variable> | <variable> | <variable> | | | | | 1. A constant or a variable by itself is an arithmetic <primary> | <primary> | <primary> expression. | | | | | <factor> | <factor> | <factor> 2.47 sum | | | | | | | <term> | <term> | | <constant> <variable> | | | | | | | | | └-------┼------┘ <primary> <primary> | | | | | | | <term> <factor> <factor> | | | | | └-------┼--------------┘ <term> <term> | | | <arith.exp.> <arith.exp.> <arith.exp.> The first attempt fails because there is no production in the definition above which has '*' following an arithmetic expression. In the second attempt we have been able to parse the expression a+b*c into an arithmetic expression. How does this define the sequence in which operations are performed? Consider the condensed parse tree of Attempt 2 without any of the labels used in parsing; the structure 1 2278 2365 31 a + b * c a + b * c + d * e / f parse tree 3 | | | | | | | | | | | | | | | | | | └--┼--┘ | | └--┼--┘ | | | └--┼--┘ | | | | | | | | | | | | b*c └--┼-----┘ | |--┘ | | | | | | | | └--┼-----┘ | | |--------┘ | | | | a+b*c └-----------┼--┘ | indicates that multiplication is performed between 'b' and 'c' a + b * c + d * e / f parse tree 4 and the result is added to 'a'. By similarly considering other | | | | | | | | | | | examples we can show that exponentiation has precedence over | | └--┼--┘ | | | └--┼--┘ multiplication and division which in turn have precedence over | | | | | | | addition and subtraction. (See also Figure 3.2.1.) | | | | |--┘ | | | | | | | 3. Consider the expression a + b * c + d * e / f. There are | | | | |--------┘ several different parse trees all which are mathematically | | | | | equivalent, i.e., one can perform the operations in any of the | | └-----┼--┘ four sequences indicated by the following four parse trees and | | | still obtain the same result. (In a computer the results may not └--┼-----------┘ be identical because of errors resulting from rounding after | each operation or from the different interpretations of "/".) But only one of them satisfies our definition. Which one? If you parse the expression you will find that all except parse tree 1 are impossible to obtain within the framework of our a + b * c + d * e / f parse tree 1 formal definition. This is because the BNF definition ensures | | | | | | | | | | | that operations of equal hierarchy are performed from left to | | └--┼--┘ | └--┼--┘ | | right in the case of infix operators +, -, *, and /. | | | | | | | └--┼-----┘ | └-----┼--┘ For exponentiation, prefix +, and prefix -, the operations | | | of equal hierarchy are performed from right to left as └-----------┼-----------┘ illustrated by forming parse trees for terms a**b**c and x---5 : | a ** b ** c a + b * c + d * e / f parse tree 2 | | | | | | | | | | | | | | | | <variable> | <variable> | <variable> | | └--┼--┘ | └--┼--┘ | | | | | | | | | | | | | | <primary> | <primary> | <primary> | | | | └-----┼--┘ | | | | | | | | | | | | | | <factor> | | └-----┼-----------┘ | | └------┼------┘ | | | | | | └--┼-----------┘ | | <factor> | └------┼-------------┘ | <factor> 1 2365 2467 32 x - - - 5 3.3.3. Arithmetic in PL + ________________ | | | | | <variable> | | | <constant> It is not merely the notation of arithmetic which must be | | | | | modified in PL, but also the concepts of addition, subtraction, <primary> | | | <primary> multiplication, and division themselves. Would you believe that: | | | | | <factor> | | | <factor> 0.1 + 0.1 < 0.2 | | | └------| <term> | | | 20 -20 20 | | | <factor> 10 + 10 = 10 <arith.exp.> | | | | | |------------┘ 20 -20 20 | | | 10 - 10 = 10 | | <factor> | | | 40 40 | | <term> 10 * 10 is undefined | | | └--------┼------┘ -40 -40 | 10 * 10 is undefined <arith.exp.> 1/3 = 0 10 * 75/50 is not equal to 10/50 * 75 4. When an expression is enclosed within parentheses it is 3.1 / 5 is not equal to 31/50 evaluated first before the adjacent operations are performed. and 3.0 * 17/15 is not equal to 3 * 17/5 ? ( a + b ) * c | | | | | | | Some of these features are not matters of life or death in day | <var.> | <var.> | | <var.> to day computation; others can be avoided by being careful. They | | | | | | | result from the difficulties involved in representing numbers in | <prim.> | <prim.> | | <prim.> finite word-length machines. Without going into the intricacies | | | | | | | of computer organization, we will discuss the source of these | <factor> | <factor> | | <factor> errors. | | | | | | | | <term> | <term> | | | Errors of the type, 0.1 + 0.1 < 0.2, result from the | | | | | | | inability to represent most decimal real numbers exactly in | <arith.exp.> | | | | | binary notation. This is a round-off error similar to the errors | | | | | | | that result when we just take the first few digits of irrational | └---------┼---------┘ | | | numbers 'e' and 'pi' and the repeating fraction 0.33333 (to | | | | | represent 1/3). In binary notation, 1/10 is also a repeating | <arith.exp.> | | | fraction; therefore any finite representation will be in error. | | | | | └------------------┼----------------┘ | | 20 -20 20 | | | Errors of the type, 10 + 10 = 10 and <primary> | | | | | 20 -20 20 <factor> | | 10 - 10 = 10 result from rounding-off numbers and | | | keeping only those significant digits that will fit in a <term> | | computer word. Most of us also perform such rounding operations | | | in day-to-day computation; these errors are not usually serious. └--------------------┼-----┘ | 40 40 <term> Errors of the type, "10 * 10 is undefined" and | ? -40 -40 "10 * 10 is undefined" concern the range of numbers that can be represented in a computer. The range depends on the data 1 2467 2563 33 type and differs from computer to computer. For an IBM 360, the subsequent paragraph. 31 31 Our efforts to preserve closure leads to another range of valid integer numbers is -2 to +2 difficulty. In PL, (a*b)/c is not equal to (a/c)*b, and we have lost the associativity of arithmetic. Let a = 10, b = 75, and 9 c = 50. Then a*b = 750, a/c = 0, and b/c = 75/50 = 1. Thus (approximately *2 * 10 ), and the range of valid real numbers (a*b)/c = 15 is not equal to (a/c)*b = 0 and neither is equal to a*(b/c) = 10. All this leads to an important hint: be very 75 75 careful when performing integer arithmetic with division! One is approximately -10 to +10 . Thus the result of the can predict exactly what the result will be knowing the sequence in which the operations will be performed. One can determine the 40 40 80 sequence of operations by parsing the expression. When in doubt computation 10 * 10 (= 10 ) is too large to be one can always use parentheses to override the implicit represented on an IBM 360. precedence. While one can exactly represent every integer in the range Until now we have considered operations between elements having the same data type. What happens when operands are of 31 different data types? It is meaningless to add numbers to a *2 , one cannot exactly represent all the real numbers in the string, e.g., 'Jones' + 10. On the other hand, it is reasonable to attempt to add a real number and an integer, e.g., 2 + 3.141; 75 in this case 2 is converted to the real number 2.0 and the range *10 . The reason is simple; there are infinitely many result is also a real number: 5.141. real numbers in that range and we are dealing with finite machines. On an IBM 360, we can refer to only about 4 billion If one or both of the operands of an arithmetic operation different points on the real axis. In fact, it turns out that is of type BIT or CHARACTER, an attempt is made to convert them after '0', the smallest absolute number we can refer to is into the appropriate arithmetic type (FIXED or FLOAT). TRUE is converted to 1 and FALSE to 0. A character string is converted -78 to a number only if it is a digit string with, perhaps, a period approximately 10 . Thus the result of the computation embedded in it. With a period, it is converted to a number of type FLOAT, otherwise to type FIXED. Given that both the -40 -40 operands have been converted to either FIXED or FLOAT if 10 * 10 is smaller than the smallest non-zero number we necessary, then the desired arithmetic operation can take place. can represent and is therefore undefined. When by mistake we The data type of the result is given by the following table: attempt to use numbers which are too large or too small to be represented, the machine detects these errors and prints an ┌-------------------┐ error indication ("overflow" or "underflow"). The accuracy and 2nd Operand | | | the range are satisfactory for most problems and need not | FIXED | FLOAT | concern the beginning programmer. 1st Operand | | | ┌---------------┼---------┼---------| Given that both the operands of an arithmetic operation are | FIXED | FIXED | FLOAT | of the same data type (say integer or real), we would like the |---------------┼---------┼---------| result also to be of the same data type. This property, known as | FLOAT | FLOAT | FLOAT | "closure", is desirable for number systems; that is, we would |_______________|_________|_________| like the domain and the range of an arithmetic operation to be the same data set. For real numbers we have this property. In Note that conversion from a character string to a number takes the case of integers, the result of addition, subtraction, and place only if the conversion is meaningful. Any attempt to add 3 multiplication of two integers is again an integer; but when an + 'Jones' would result in an error indication. integer is divided by another the result need not be an integer; an example is 1/3. In PL, we define the result of division In the case of 3.1/5, 5 is converted to 5.0 and the result between two integers to be the integral quotient and we ignore is .62 . In the case of 31/50, there is no conversion and the the remainder, thus preserving the property of closure. That is result is 0. Thus, if we wanted to calculate the exact result in why the result of 1/3 = 0. Languages like Algol use two the case of 1/3 we should write 1.0/3.0 or 1.0/3 . (Note 1.0/3 operators, / and :-, the result of '/' being an approximate real will require converting 3 into real number representation and is number and the result of ':-' being the integral quotient. We therefore inefficient.) Why is 3.0 * 17/5 ^= 3 * 17/5 ? will see how we can obtain a similar result using PL in a 1 2563 2647 34 Suppose we have division involving two integer variables little numeric computation; what is required is the ability to 'a' and 'b' and we wish to get an exact answer. How do we do it? look at and/or compare character strings, either as a whole or The basic idea is first to force conversion of one of the in part, and the ability to create new strings by catenating operands into a real number and then to perform the operation. (linking together) other strings. We have to learn other Let 'x' be a variable of type FLOAT; we store the quotient of constructs in PL before we can perform many of the above tasks. two integers ('a','b') in 'x' in either of the following ways: A basic but important use of string expressions is in DECLARE a FIXED, b FIXED; | DECLARE a FIXED, b FIXED; producing a meaningful output of the results of a problem. DECLARE x FLOAT; | DECLARE x FLOAT; Consider the following program for determining the length of the x = a; | x = FLOAT(a)/b; diagonal of a rectangle. x = x/b; | ┌--------------------------------------------------------┐ In the first an automatic type conversion occurs when the | /* let 'a' and 'b' be the sides and 'd' the diagonal */| integer value of 'a' is stored at the address of real variable | DECLARE (a,b,d) FLOAT; | 'x', and the result of the mixed expression x/b is real. The | a = INPUT; /* get a value for 'a' from the data */ | second uses a type conversion function FLOAT which converts the | b = INPUT; /* ....... and 'b' */ | integer into a real number. In some systems a warning message is | d = SQRT(a*a + b*b); | printed every time an expression requiring a type conversion | OUTPUT = d; /* print the result */ | appears in the program. └--------------------------------------------------------┘ Exercise 3.3.4. The result printed would be a single number, which when viewed Write a program to check each of the difficulties with after a few days would be a meaningless piece of information. computer arithmetic noted in this section. Replacing the single OUTPUT statement by the following statements: 3.4 STRING EXPRESSIONS ┌----------------------------------------------------------┐ | OUTPUT = 'Calculation of the diagonal of a rectangle'; | An expression whose value is a character string is called a | OUTPUT = 'Lengths of the sides are ' ||a|| ' and ' ||b; | string expression. The following assignment statements | OUTPUT = 'Length of the diagonal is ' ||d; | illustrate the use of some simple string expressions. └----------------------------------------------------------┘ DECLARE (name, address, city, zip) CHARACTER; would result in a more meaningful output: name = 'John Smith'; address = '52 Campus Drive' ┌---------------------------------------------┐ city = 'Stanford,Calif.'; | Calculation of the diagonal of a rectangle | zip = '94305'; | Lengths of the sides are 3.6 and 4.8 | | Length of the diagonal is 6.0 | All these are perfectly valid assignment statements. If we go └---------------------------------------------┘ back to our post-office-box analogy, the contents of the labeled boxes would be as follows: The string expressions on the right hand side of the 'OUTPUT' statements use the catenation operator || . The ┌------------┐ ┌-----------------┐ ┌-----------------┐ ┌-------┐ operator || is used to combine two strings to form another | name | | address | | city | | zip | string; the expression |┌----------┐| |┌---------------┐| |┌---------------┐| |┌-----┐| ||John Smith|| ||52 Campus Drive|| ||Stanford,Calif.|| ||94305|| 'My name is' || 'John' |└----------┘| |└---------------┘| |└---------------┘| |└-----┘| └------------┘ └-----------------┘ └-----------------┘ └-------┘ would result in the string String expressions are used mainly for symbol manipulation. 'My name isJohn'. By symbol manipulation we mean tasks such as arranging a list of names in alphabetical order, determining whether a given name is If we wish to have a space between 'is' and 'John' we must present in the list, analysis of the literary style of a poet, include a space in one of the operands, e.g., 'My name is ' || compiling statistics on the frequency of usage of various words 'John' or 'My name is' || ' John'. in a language, language translation, simplification of algebraic formulae, producing output, and so on. Such tasks involve very Exercise 3.4.1 1 2647 2724 35 Using catenation and the multiplication operator, write a 'Length of the sides are ' || a || ' and ' || b program to print out a 4 by 4 multiplication table. Columns | | | | | | | and rows may be labeled and the numbers separated by spaces <constant> |<variable> | <constant> |<variable> as shown below. | | | | | | | <primary> | <primary> | <primary> |<primary> * | 1 2 3 4 | | | | | | | ----┼---------------------- <factor> | <factor> | <factor> | <factor> 1 | 1 2 3 4 | | | | | | | 2 | 2 4 6 8 <term> | <term> | <term> | <term> 3 | 3 6 9 12 | | | | | | | 4 | 4 8 12 16 <arith.exp.> |<arith.exp>|<arith.exp.>|<arith.exp> | | | | | | Exercise 3.4.2. <string exp.> | | | | | | Write a program to read four character strings, catenate | | | | | | | them, catenate a '.' on the end and print the result. For └-------------┼-----┘ | | | | example, strings 'the', ' cat', ' is', and ' red' should | | | | | result in 'the cat is red.' └-----------┼------┘ | | | | | We can now give a formal definition of the term <string exp> | | <expression> to include string expressions and arithmetic | | | expressions. └------------┼-----┘ | <string expression> ::= <arithmetic expression> <string exp> |<expression> || <arithmetic expression> | <arithmetic expression> ::= <term> <expression> |<arithmetic expression> + <term> |<arithmetic expression> - <term> <term> ::= <factor> 3.4.1 Character String Operations + ___________________________ | <term> * <factor> |<term> / <factor> The operation || is the only operator that has a string- <factor> ::= <primary> valued result. However, there are also string-valued functions |<primary> ** <factor> (SUBSTR, E-FORMAT, and CHARACTER) which are useful in operating | + <factor> | - <factor> with strings. <primary> := <constant> | <variable> |<function designator> | (<expression>) The function SUBSTR(x,i,j) is used to obtain a substring of a character string 'x'. The result is a substring of 'x', 'j' Let us parse an expression as an exercise. characters long, beginning with the i-th character. Thus SUBSTR ('My name is John', 4, 5) is the string 'name '. The function SUBSTR can also be used within a string expression. The value of SUBSTR ('My name is John', 1, 11) || 'Peter' is the string 'My name is Peter'. If the last argument, 'j', is omitted, then the value is the string from the i-th character to the end of 'x'. For example, SUBSTR ('The quick brown fox', 11) yields 'brown fox'. SUBSTR can also be used on the left side of an assignment statement to replace part of an existing string with another string. For example, DECLARE s CHARACTER; s = 'A dog flew by.'; SUBSTR(s,3,3) = 'cat'; 1 2724 2790 36 INDEX('eucalyptus','cal') yields 3 would result in the string 'A cat flew by.' INDEX('science','ense') yields 0 INDEX('abcdef','d') yields 4 If the new string being assigned is shorter than the a = 'water'; substring it is replacing, it is padded with blanks to make up b = 'wat'; the difference. If it is too long, characters are truncated from INDEX(a,b) yields 1 the end of the new substring before it is inserted. Thus, The value of the function LENGTH is the number of s = 'abczzzghi'; characters in the string specified by the argument. SUBSTR(s,4,3) = 'defwww'; LENGTH('mariposa') yields 8 would result in the string 'abcdefghi', and LENGTH('''a''') yields 3 LENGTH('') yields 0 s = 'abczzzghi'; a = 'short'; SUBSTR(s,4,3) = 'd'; LENGTH(a) yields 5 becomes 'abcd ghi' . 3.4.2. Precedence of Catenation + ________________________ E-FORMAT and CHARACTER are used primarily for converting numbers to character strings in producing output. CHARACTER The BNF definition in Section 3.4.1 automatically defines takes one of two forms depending on the type of its argument. the precedence of the || operation. Let us parse the expression For example, 'mean = ' || (a+b+c+d)/4 , which could be used to print out the average of four variables 'a', 'b', 'c', and 'd'. CHARACTER (1) has the value '1' CHARACTER (321/3) has the value '107' CHARACTER (-1) has the value '-1' CHARACTER (1.0) has the value '1.0' CHARACTER (1.0/3.0) has the value '0.333333' E-FORMAT uses only the exponential notation. For example, E-FORMAT (1) has the value '1.00000E1' E-FORMAT (107) has the value '1.07000E2' E-FORMAT (1.0/3.0) has the value '3.33333E-1' Exercise 3.4.3. Write a program to print the value 1/3 in as many ways as possible. Exercise 3.4.4. Write a program to read a character string, move the first character to the end and delete it from the front, then print the result. Also useful in manipulation of string expressions are the arithmetic functions INDEX and LENGTH. Expressions of the form INDEX(s,b) check to see whether the string corresponding to the value of 'b' is a substring of the string 's'. If it is, the value of the function will be an integer denoting the position within 's' of the first character of 'b'. If 'b' is not a substring of 's', the value of the expression is 0. Examples: 1 2790 2884 37 'mean = ' || ( a + b + c + d ) / 4 'mean = ' || ( a + b + c + d ) / 4 | | | | | | | | | | | | | | | | | | | | | | | | | | <const.> | | <var.> | <var.> | <var.> | <var.> | |<const.> | | | └-┼-┘ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | <prim.> | | <prim.> | <prim.> | <prim.> | <prim.> | | <prim.> | | | └---┼--┘ | | | | | | | | | | | | | | | | | | | | | | | | | | | <factor> | |<factor> |<factor> |<factor> |<factor> | |<factor> | | | └----┼--┘ | | | | | | | | | | | | | | | | | | | | | | | <term> | | <term> | <term> | <term> | <term> | | | | | └------------┼-----┘ | | | | | | | | | | | | | | | | | | | | <ar.exp.> | |<ar.exp> | | | | | | | | | | | └--------┼--┘ | | | | | | | | | | | | | | | | <str.exp> | | └----┼----┘ | | | | | | | └-----┼------------------------┘ | | | | | | | | | | | | | | | <arith.exp.> | | | | | | | | | | | | | | | | | | The precedence of || should be clear after working through this | | | └---------┼----┘ | | | | | diagram. (If not, the reader should reread the section on | | | | | | | | | precedence of arithmetic operations.) All the arithmetic | | | <arith.exp.> | | | | | operations have precedence over || , i.e., they are performed | | | | | | | | | before catenation can take place. | | | └---------┼----┘ | | | | | | | | | | | | | <arith.exp.> | | | 3.4.3. Mixed String Expressions + ________________________ | | | | | | | | | └-----------------------------┼---------┘ | | Note that when we write the expression | | | | | 'The length of the diagonal is ' || d | | | | | the operand on the right is a number (declared as FLOAT). Since | | | | | the || operation is only defined for strings, the real number | | <primary> | | 'd' must first be converted to its equivalent string | | | | | representation before the operation can take place. We have | | <factor> | | already seen that in arithmetic operations, the operands were | | | | | first converted to integers and/or real numbers before the | | <term> | | operations could take place. The necessity for such conversion | | | | | of data types should be clear by now. However, we will reiterate | | └-----------┼----┘ for emphasis: the representation is different for different data | | | types; for example '2', 2.0, and 2 are different. Before the | | <term> specified operations can take place, all the operands must be | | | converted to the same type. The conversion that takes place is | | <arith.exp.> dependent on the operation. For || the operands are converted to | | | strings, and for arithmetic operations the operands are └-----┼--------------------------------------------┘ converted according to FIXED or FLOAT data types. Conversion of | a logical value to a string results in either 'TRUE' or 'FALSE'. <string expression> | Exercise 3.4.5. <expression> Which of the following expressions are incorrect? 2 + 'two' Omitting all the labels at the nodes, the condensed parse tree '2' * '3' is: 'John' - 'Adams' 'John is' || TRUE Exercise 3.4.6. What is the value of SUBSTR('AABABCABCD',INDEX('BA'),6)||'XYZ' 1 2884 2971 38 3.5 LOGICAL EXPRESSIONS Note that ^< is equivalent to >=, and ^> to <=. While there is no need to have such equivalent symbols, they sometimes make We have already seen some examples of logical expressions, programs more readable. e.g., name ^= 'A. Jones', a + b < c + d, next ^= 99999999, etc. We will see in Sections 3.6 and 3.7 how they can be used for It is not always possible to express conditions as simple conditional or repetitive execution of statements. Logical relations. A football coach might be interested only in players expressions that we have seen have been of the form whose weight is between 180 and 300 lbs. This requirement is expressed in mathematical notation as <logical expression> ::= <string expression> 180 < weight < 300 <relational operator><string expression> But this expression has two relational operators and is not a <relational operator> ::= < | <= | = | >= | > | ^< | ^= | ^> valid logical expression. It is in fact a combination of two simple relations: 180 is less than 'weight' and 'weight' is less (You may recall that <arithmetic expression> is but a special than 300. In PL we state this compound condition using the 'and' case of a <string expression>.) A logical expression of this operator '&'. form is a command to evaluate the expressions on either side of 180 < weight & weight < 300 the relational operator and to make a comparison to see if the This '&' operator requires that both conditions be met in order relation is satisfied. The value of a logical expression is TRUE for the expression to have the value TRUE. if the relation is satisfied; otherwise it is FALSE. There are other forms of compound conditions: the motor Many computers cannot print all the symbols that can be vehicle department might state that a person is ineligible to used as relational operators. The following multiple character drive a car either if the age is less than 16 or if the number symbols are often used as substitutions. of traffic violations is over a prescribed limit (say 6). In PL this condition is expressed using the 'or' operator '|' , as ___________________________________________ follows: |relation |symbol| variation | age < 16 | violations > 6 |----------------------┼------┼-----------| If either condition is met, the value of the expression is TRUE. |less than | < | < | |less than or equal | ≤ | <= | A 'not' operator, ^ , permits us to state whether a person |equal | = | = | is eligible to drive a car in terms of the above expression, |greater than or equal | ≥ | >= | viz., |greater than | > | > | ^(age < 16 | violations > 6) |not less than | /< | ^< | I.e., the 'not' operator changes the value of a logical |not equal | # | ^= | expression. |not greater than | /> | ^> | |______________________|______|___________| Depending on the character set available and individual Figure 3.5.1. Equivalent relational operators preference, the following symbols are often used as substitutes for & , | , and ^. If the values of expressions on both sides of the ____________________________________________________ relational operator are numbers (either FIXED or FLOAT) then the |logical operation |symbol|variation I|variation II| meaning of the operators is clear. What if they are strings or |------------------┼------┼-----------┼------------| logical valued expressions? The relational operators are still | or | | | V | OR | well defined. In the case of strings, the < , = , and > | and | & |circumflex | AND | operators are defined according to the alphabetic collating | not | ^ | ^ | NOT | sequence. For example, the following expressions are all true: |__________________|______|___________|____________| 'a' < 'b', 'axyz' < 'b', 'xyz' > 'byz', The triangle test program given in Section 3.7 illustrates 'abc' < 'abcd', 'x' < 'xaxy', 'x' = 'x ' the use of 'and', 'or', and 'not' operators. When the logical values are converted to their numerical equivalents, FALSE is less than TRUE, e.g., the following 3.5.1. Precedence of Operations in a Logical Expression + ________________________________________________ nonsense expression has the value TRUE: Until now we have talked about operators or (|) , and (&) , FIXED (a ^= a) < FIXED (a = a) and not (^) by means of examples. A precise description of these operators can be given by means of a truth table. Using this truth table one can determine the value of a logical expression 1 2971 3068 39 containing these operators. Let 'a' and 'b' be logical <primary> ::= <variable> | <constant> | <function designator> expressions which can take the values TRUE or FALSE. Then we can | (<expression>) form other logical expressions using 'a', 'b', and the operators | , & , and ^ , e.g., a|b , a&b , ^a , etc. The following truth Let us parse the following expression as an example table gives values of these expressions in terms of the value of (leaving out the parsing up to <arithmetic expression>). 'a' and 'b'. _________________________________________ a + b < c + d | a + c < b + d & married | a | b || a|b | a&b | ^a | | | | | | | | | | |------|-------||-------|-------|-------| <ar.exp.> | <ar.exp.> |<ar.exp.> | <ar.exp.>| <variable> |TRUE | TRUE || TRUE | TRUE | FALSE | | | | | | | | | | |TRUE | FALSE || TRUE | FALSE | FALSE | <str.exp.>| <str.exp.>|<str.exp.>|<str.exp.>|<arith. expression> |FALSE | TRUE || TRUE | FALSE | TRUE | | | | | | | | | | |TRUE | FALSE || FALSE | FALSE | TRUE | └-----┼-----┘ | └-----┼-----┘ |<string expression> |______|_______||_______|_______|_______| | | | | | <logical primary> | <logical primary> | <logical primary> A logical variable or a relational expression by itself is | | | | | a logical expression. If 'a' is a logical expression, then ^a is <logical secondary> | <logical secondary> | <logical secondary again a logical expression. If 'a' and 'b' are logical | | | | | expressions then a|b and a&b are also logical expressions. <logical factor> | <logical factor> | | Consider the expression a | b & c . Does it mean (a | b) & c or | | | | | a|(b & c)? Either way it is still a logical expression; but the <logical expression> | └----------┼---------┘ value can be different. Let 'a' and 'b' be TRUE and let 'c' be | | | FALSE; then from the truth table we have | | <logical factor> | | | a | b is TRUE b & c is FALSE └-----------┼---------------------┘ (a | b) & c is FALSE a | (b & c) is TRUE | <logical expression> Thus we note that the sequence in which operations are performed is as important as in the case of arithmetic expressions. It is If we suppress the labels, the condensed parse tree looks like not sufficient to define precedence for | , & , and ^ , because this: a logical expression may contain arithmetic operators, relational operators, and logical operators: a + b < c + d | a + c < b + d & married a + b < c + d | a + c < b + d . | | | | | | | | | | | | | | | | | We will redefine the term <expression> to include logical └-┼-┘ | └-┼-┘ | └-┼-┘ | └-┼-┘ | | expressions and at the same time provide an implicit definition | | | | | | | | | of precedence of operators. └---┼---┘ | └---┼---┘ | | | | | | | <expression> ::= <logical factor> | | └--------┼----┘ | <expression> <or symbol> <logical factor> | | | <or symbol> ::= | └-------┼----------------┘ <logical factor> ::= <logical secondary> | | <logical factor> & <logical secondary> <logical secondary> ::= <logical primary> The above diagram shows that arithmetic operations are performed | ^ <logical secondary> before relational operations which in turn are performed before <logical primary> ::= <string expression> '&' and finally '|' . Table 3.2.1 gives the precedence levels | <string expression><relational operator><string expression> for all the operators we have encountered so far. As you are <relational operator> ::= < | <= | ^ | >= | > | ^= | ^> | ^< already aware, these precedences of operations can be superseded <string expression> ::= <arithmetic expression> by enclosing any expression within parentheses. When this is | <string expression> || <arithmetic expression> done the parenthesized expression becomes a primary and is <arithmetic expression> ::= <term> therefore evaluated before it is used as an operand. | <arithmetic expression> + <term> | <arithmetic expression> - <term> . 3.5.2. Assignment of Logical Expressions and the = Confusion + _____________________________________________________ . (same as in Section 3.4) . 1 3068 3158 40 The value of a logical expression (which can only be TRUE A statement is usually a command to the computer to perform or FALSE) can be stored in a logical variable and used in future certain operations. Unless we explicitly instruct it to do computation any number of times. For example, the expression otherwise, the computer will execute these statements IF weight < 180 | weight > 300 THEN sequentially (one after another) starting with the first. There can be rewritten as follows: are facilities in PL to instruct the computer to perform a statement only if a certain condition is satisfied, to perform DECLARE (underweight, overweight) BIT, weight FIXED; one of several alternatives depending on which condition is ... satisfied, and to execute a group of statements repetitively underweight = weight < 180; until a certain condition is satisfied. Note that the phrase "a overweight = weight > 300; certain condition is satisfied" is common to all the IF underweight | overweight THEN alternatives; 'IF a + b < c + d THEN' is an example of a ... conditional construct. Here we are instructing the computer to calculate the value of expressions a + b and c + d, and to compare the results to see if a + b is less than c + d. This treatment of logical values has several advantages. Expressions of this form (see Section 3.5) are often used to Firstly, one can reduce complicated logical expressions to control the execution of statements conditionally or readable and more meaningful expressions. Secondly, if the same repetitively. expression is to be used in several places in a program (and the values appearing in the expression are not changed) it need not There are many problems in which one wants to perform a be evaluated over and over again. computation conditionally. For example, in an algorithm for tax computation a rule for a deduction might be as follows: "If your Note that the = symbol serves two purposes. It is used in contributions to charity are less than 20% of your gross an assignment statement to store the value of an expression and adjusted income, then subtract the total amount of such in a logical expression as a command to compare the operands to contributions from the gross adjusted income, otherwise subtract see if they are equal. Thus one may have an odd-looking only 20% of your gross adjusted income." statement like a = b = c; There are other problems where one might wish to repeat a This confusion can be resolved in PL from context. A partial computation until a given condition is satisfied. For example, parse tree for this statement is given below. we know that integer multiplication can be expressed as a repeated addition. Or, if we were trying to determine the a = b = c ; favorite presidential candidate by using the data of a public | | | | | | opinion poll, we would accumulate statistics by repeating the <variable> | └--------┼---------┘ | same calculations on every set of data until all the data are | | | | exhausted. | | <logical expression> | | | | | There are two main constructs in PL which permit us to | |------------┘ | perform computation conditionally or repetitively: conditional └------┼-------------------------┘ statements and group statements. These two important constructs | can take many different forms and are discussed in the next two <assignment statement> sections. (Languages like Algol avoid this confusion by using '<-' (left arrow) or ':=' as the assignment symbols.) 3.6.2. Conditional Statements + ______________________ Exercise 3.5.1. Suppose, in the middle of a program, we wish to determine Is the expression the larger of the two variables 'a' and 'b' and store the result SQRT (MAX (1, RANDOM) - SIN (7)**2) = COS (7) in 'maximum'. This can be achieved by the following statements true or false? What would you expect the program OUTPUT = SQRT (MAX (1, RANDOM) - SIN (7)**2) = COS (7); . to print? Try it, then explain your results. . maximum = a; IF maximum < b THEN maximum = b; 3.6 THE CONDITIONAL STATEMENT . . 3.6.1. Control Statements + __________________ 1 3158 3238 41 We are already familiar with the first statement; after it has difference is that the statement maximum = a; has been included been executed the variable 'maximum' will have the same value as in the compound statement as an alternate (ELSE) clause. If the 'a'. The second statement is a command to compare the current condition is satisfied then 'maximum = b;' is executed, value of 'maximum' with that of 'b' and, if 'maximum' is less otherwise 'maximum = a;' is executed.Both types of conditional than 'b', to change the value of 'maximum' to that of 'b', statement can be defined as follows: otherwise to do nothing. <statement> ::= <basic statement> | <conditional statement> Exercise 3.6.1. <conditional statement> ::= IF <expr> THEN <statement> Hand simulate the operation of the above statements for the | IF <expr> THEN <basic statement> ELSE <statement> following sets of values of 'a' and 'b'. <basic statement> ::= <assignment statement> ________________________________________________________________ | <group> |Before the first|After execution of the|After execution of the| | statement | first statement | second statement | There are a few other forms of basic statements which need not |----------------┼----------------------┼----------------------| concern us here. We will learn about groups in the following | a | b | a | b | maximum | a | b | maximum | section. The important point is that a <basic statement> and |--------┼-------┼-----┼-----┼----------┼-----┼------┼---------| <statement> are different entities. The <statement> includes | 10.7 | 3.1 | | | | | | | both the <basic statement> and the <conditional statement>. This | 4.5 | 4.5 | | | | | | | distinction is essential because one of the constructs of | 4.5 | 7.5 | | | | | | | <conditional statement> is of the form |________|_______|_____|_____|__________|_____|______|_________| IF <expression> THEN <basic statement> ELSE <statement> . If you have done the above exercise correctly, you will note that the value of 'maximum' is the greater of the two While the construct following ELSE can be any statement, values 'a' and 'b' (whenever such a distinction is possible). including another conditional statement, the construct following The technique used here is simple: we assume that the value of THEN must be a basic statement, i.e., it must not be a statement 'a' is the larger and store it in 'maximum'; if our assumption starting with an IF. turns out to be false, we correct ourselves by storing the value of 'b' in 'maximum'. One may wonder why there are two different forms of the conditional statement. It might appear that the 'IF ... THEN' The conditional statement introduced above is described by statement is only a special case of the 'IF ... THEN ... ELSE' the rule: statement. Sometimes it is more convenient to leave things alone if the condition is not satisfied. Suppose we wish to compute <conditional statement> ::= IF <expression> THEN <statement> the absolute value of a variable 'a' and wish the result to be stored back in 'a'. It is more convenient and efficient to write The term <expression> refers to a logical expression (see Section 3.5). Some examples of logical expressions are IF a < 0 THEN a = -a; than height + width <= 20 IF a < 0 THEN a = -a; ELSE a = a; name ^= 'Henry P. Jones' (Why?) a + b > c + d Exercise 3.6.2. They are commands to evaluate the expressions on each side of Parse the following statement: the relational operator and perform a comparison to see if the IF x < 20 THEN a = a+1; specified relation is satisfied. If the relation is true (i.e., ELSE IF x < 40 THEN b = b+1; satisfied), then the statement following THEN is executed, ELSE c = c+1; otherwise it is ignored. As an example of a compound statement with multiple IF ... There is another construct in PL which permits us to THEN ... ELSE, let us consider a problem in census statistics. compute the maximum of 'a' and 'b' with a single compound Suppose we wish to determine the number of people in different statement. The statement age groups in a country. Then the following statement can be used in a repetitive algorithm: IF a < b THEN maximum = b; ELSE maximum = a; has the same effect as the two statements used earlier. The main 1 3238 3322 42 IF age < 20 THEN under_20 = under_20 + 1; The preceding example using groups illustrates typical ELSE IF age < 40 THEN twenty_to_39 = twenty_to_39 + 1; paragraphing conventions for control statements. In the case of ELSE IF age < 60 THEN forty_to_59 = forty_to_59 + 1; conditonal statements, the statements following THEN and ELSE ELSE over_59 = over_59 + 1; (if any) should be started on a new line and indented (about 3 spaces) as follows Given the age of a person, the above statement will add 1 to the appropriate age-group counter. IF <expression> THEN (or) IF <expression> THEN <statement> <basic statement> Exercise 3.6.3. ELSE IF <expression> THEN Write a program that reads a character string and prints it <basic statement> unless it is a four letter word. ELSE <statement> 3.7 GROUP STATEMENTS Note that 'IF' and 'ELSE' are lined up and the associated statements are indented. An exception to this convention is when 3.7.1. DO ... END statements the statements are so small that they can conveniently be placed + _____________________ on the same line as the condition, e.g., Suppose we wanted to calculate both the maximum and the minimum of two variables 'a' and 'b'. We could do this by using IF a >= b THEN maximum = a; ELSE maximum = b; two conditional statements. or IF a >= b THEN maximum = a; IF a < b THEN maximum = b; ELSE maximum = a; ELSE maximum = b; IF a < b THEN minimum = a; ELSE minimum = b; In such simple cases paragraphing need not be used. While the above statements will do the task note that the condition 'a < b' has to be evaluated twice. We can avoid this Statements within the DO ... END brackets of group inefficiency by grouping corresponding statements together using statements should also be indented as follows. a 'DO ... END' symbol pair as follows: DO; IF a < b THEN <statement> DO; <statement> maximum = b; . minimum = a; . END; . ELSE <statement> DO; END; maximum = a; minimum = b; The term DO may be followed by an expression on the same line. END; (A formal definition of groups is given in Section 3.9.) One can occasionally alter the paragraphing convention for groups as in The symbol pair 'DO ... END' can be used to group together any the following example. number of statements to form a single basic statement called a 'group'. In the above example all the statements of the group IF a < b THEN following THEN, namely 'DO; maximum = b; minimum = a; END;' are DO; maximum = b; minimum = a; END; performed only if the condition is satisfied; otherwise all the ELSE statements of the group following ELSE are performed. DO; maximum = a, minimum = b; END; Exercise 3.7.1. Consistent paragraphing produces readable programs and reduces Verify by hand simulation that the statement using groups programming errors. (above) is equivalent to the statements without grouping by considering three typical pairs of values for 'a' and 'b'. 3.7.3. Repetition: The DO WHILE Statement + __________________________________ 3.7.2. Paragraphing for Control Statements Let us consider the problem of calculating the maximum of + ___________________________________ more than two numbers: assume that these numbers are to be read 1 3322 3417 43 from the input device. The program of Figure 3.7.1 can be a simple extension of that for the computation of the maximum of The indented statements within the DO ... END symbol pair are two numbers (see Section 3.6.2). repetitively executed until the number 9999 is encountered. The set of statements which are repetitively performed is often ┌----------------------------------------------------------┐ called a loop. The statement | DECLARE (next, maximum) FLOAT; | 'DO WHILE <expression>; <statement list>; END;' | maximum = INPUT; /* read the first number from input */ | is a command to the computer to evaluate a logical expression; | next = INPUT; /* read the second number from input */ | then, if it is TRUE, to execute the <statement list> and re- | IF maximum < next THEN maximum = next; | evaluate the expression, continuing in this manner as long as | next = INPUT; /* read the third number from input */ | the value of the <expression> is TRUE. Upon termination of this | IF maximum < next THEN maximum = next; | process (when <expression> = FALSE) the computer proceeds to the | next = INPUT; /* read the fourth number from input */ | next statement following END; . Note that in the above example | IF maximum < next THEN maximum = next; | we have to initialize 'maximum' and 'next' with the first two | OUTPUT = maximum; | data items so that the repetitive part may function as desired. └----------------------------------------------------------┘ Note that the paragraphing permits us to determine at a glance Figure 3.7.1. Maximum of four numbers those statements which will be repeated. As you can see we repeatedly use the pair of statements Exercise 3.7.2. Why is the sequence of statements next = INPUT; next = INPUT; IF maximum < next THEN maximum = next; IF maximum < next THEN maximum = next; reversed in the repetitive part of the above program? until we have read and processed all the numbers. Now suppose we wanted to calculate the maximum of ten numbers instead of four. Let us consider another example which illustrates the use Then we would have to extend the program (in Figure 3.7.1) by of the DO WHILE statement and the use of the & , | , and ^ adding six more pairs of the above statements. In general, if we operators in logical expressions. Given three numbers, suppose wished to calculate the maximum of 'n' numbers the program would we are required to determine if it is possible for them to need n-1 pairs of these statements. This process of adding more represent the lengths of the sides of a triangle. A well-known statements becomes cumbersome as 'n' becomes large. Moreover theorem of geometry tells us that the sum of any two sides of a such a program will be only useful for calculating the maximum triangle is greater than the third, i.e., if the lengths of the of exactly 'n' numbers, neither more nor less. sides are 'a', 'b', 'c', then a + b > c and b + c > a and c + a > b . For example, 1.5, 2.0, and 4.5 cannot be the sides What we really need is a construct for instructing the of a triangle while 1.5, 2.0, and 2.5 can. computer to perform the same calculation over and over until all the data is exhausted. How can one decide whether all the data The PL program of Figure 3.7.3 reads three numbers from the is exhausted or not? There are many ways of doing this; a common input device, tests to see if they can be the sides of a technique is to add a spurious item at the end of the data queue triangle, and prints an appropriate message. The process is and to repeat the process until we encounter it. This spurious repeated until at least one of the three numbers is less than or item must be such that it is certain not to appear within the equal to zero. Thus to terminate the program a spurious last set regular data, say a very large number. In PL, the 'DO WHILE' of data must be introduced which contains a negative number. statement can be used for repetitively executing a group of statements as illustrated by the program of Figure 3.7.2. ┌-------------------------------------------------------┐ | DECLARE (a, b, c) FLOAT; | ┌-------------------------------------------------------------┐ | a = INPUT; b = INPUT; c = INPUT; | | DECLARE (next, maximum) FLOAT; | | DO WHILE ^ (a <= 0 | b <= 0 | c <= 0); | | maximum = INPUT; /* read the first number */ | | IF a + b > c & b + c > a & c + a > b THEN | | next = INPUT; | | OUTPUT = a || ' ' || b || ' ' || c || | | DO WHILE next ^= 9999; /* 9999 indicates the end of data */ | | ' can be the sides of a triangle '; | | IF maximum < next THEN maximum = next; | | ELSE | | next = INPUT; | | OUTPUT = a || ' ' || b || ' ' || c || | | END; | | ' cannot be the sides of a triangle '; | | OUTPUT = maximum; | | a = INPUT; b = INPUT; c = INPUT; | └-------------------------------------------------------------┘ | END; | Figure 3.7.2. Use of the DO WHILE statement └-------------------------------------------------------┘ in calculation of maximum Figure 3.7.3. Triangle test program 1 3417 3499 44 Write a program that reads a series of singular English The following examples show typical input and results of the nouns, pluralizes them, and prints both forms of each program. ________________________________________________________________ Exercise 3.7.6. | INPUT | output | Write a program that reads and prints a string, then |---------------|----------------------------------------------| reverses the string and prints the result. | 1.5, 2.0, 4.5 | 1.5 3.0 4.5 cannot be the sides of a triangle| | 1.5, 2.0, 2.5 | 1.5 2.0 2.5 can be the sides of a triangle | Exercise 3.7.7. | 9 , 1 , 2 | 9.0 1.0 2.0 cannot be the sides of a triangle| Write a program that reads a sentence, then prints the |-5 , 0 , 0 | | words, one to a line. |_______________|______________________________________________| Exercise 3.7.8. The <while clause> in Write a program that reads a series of sentences, counts DO WHILE ^ (a <= 0 | b <= 0 | c <= 0) the occurrences of each letter and prints the letter is a command to repeat the following statements (within the DO frequencies so discovered. ... END symbols) while a <= 0 | b <= 0 | c <= 0 Exercise 3.7.9. is FALSE, i.e., while 'a', 'b', and 'c' are not less than or Write a program that reads a character string, then equal to zero. This <while clause> is equivalent to generates and prints all permutations of it. DO WHILE a > 0 & b > 0 & c > 0; i.e., if 'a' is positive and 'b' is positive and 'c' is positive Exercise 3.7.10. then repeat the process. Similarly the logical expression of the Do the above but print only unique permutations. conditional statement in the above example can be rewritten as follows using '|' instead of '&'. Exercise 3.7.11. ^ (a + b <= c | b + c <= a | c + a <= b) Write a program to make a pretty picture on the printer. If you do not wish to use the ^ operator you can still use '|' instead of '&' but the conditional statement must be rewritten Exercise 3.7.12. as follows (by exchanging the statements following THEN and Write a program to read a character string, then block ELSE). print it as a banner, one character to a printer page. IF a + b <= c | b + c >= a | c + a <= b THEN OUTPUT = a || ' ' || b || ' ' || c || 3.7.4. The DO Statement with an Iteration Control. + __________________________________________ ' cannot be the sides of a triangle '; ELSE Suppose we wanted to read 100 numbers and calculate their OUTPUT = a || ' ' || b || ' ' || c || sum; this can be done using the DO WHILE statement as follows: ' can be the sides of a triangle '; ┌--------------------------------------------┐ Repetition of a group of statements until all the data is | DECLARE sum FLOAT, i FIXED; | exhausted is but a single example of the use of a DO WHILE | sum = 0.0; | statement. One can use this construct to calculate the remainder | i = 1; | of a/b as follows: | DO WHILE i <= 100; | | sum = sum + INPUT; | c = a; | i = i + 1; | DO WHILE c >= b; c = c - b; END; | END; | | OUTPUT = sum; | Exercise 3.7.3. └--------------------------------------------┘ Hand simulate the remainder algorithm for a = 17, b = 5 . Figure 3.7.4. Calculation of the sum of 100 numbers Exercise 3.7.4. Recall the <student card> you prepared for Section 3.2.4. There are many problems in which one wants to repeat a set of Write a program that reads and prints all of the student statements a predetermined number of times. This requires the cards for your class. Remember that you will have to dummy use of a loop control variable (also called loop variable, index up an end card to stop your loop. variable, etc.) which keeps track of the number of repetitions performed. In the above example, the loop variable is 'i'; it is Exercise 3.7.5. first set to 1, incremented by 1 each time around the loop, and 1 3499 3591 45 tested to determine whether the number of repetitions is less a = a + a , k < i , j < i . than or equal to 10. Since this type of repetition is very i k j useful in problem solving, there is a special construct in PL which takes care of the initialization, incrementing, and e.g., 1 , 2 , 3 , 6 , 9 ... testing of the loop variable automatically. This construct is called an iteration control and is of the form In the above example we see that 9 is reachable in four steps. (Can you do better?) Write a program to read an DO <variable> = <expression> TO <expression>; integer, compute and print an addition chain of minimal <statement list> length for that integer. Here are some examples for END; checking purposes: The statement 1 , 2 , 4 , 8 DO i = j to k; 1 , 2 , 3 , 5 , 10 , 13 . <statement list> END; is equivalent to 3.7.5. The DO CASE Statement. + _____________________ i = j; DO WHILE i <= k; The 'DO ... END' statement permits us to group several <statement list> statements into a single basic statement. The 'DO WHILE' i = i + 1; statement permits us to execute repetitively a group of END; statements as long as the given condition is satisfied. The 'DO CASE' statement is used to execute selectively a single We can now rewrite the summation example as shown in Figure statement out of a group of statements. The statement to be 3.7.5. executed is specified by the value of the expression following DO CASE. The census problem of determining the number of people ┌--------------------------------------------------┐ in each 20-year age group can be stated as follows (assume age | DECLARE sum FLOAT, i FIXED; | is a FIXED variable): | sum = 0.0; | | DO i = 1 TO 100; | DO CASE age/20 + 1; | sum = sum + INPUT; | under_20 = under_20 + 1; | END; | twenty_to_39 = twenty_to_39 + 1; | OUTPUT = sum; | forty_to_59 = forty_to_59 + 1; └--------------------------------------------------┘ sixty_to_79 = sixty_to_79 + 1; Figure 3.7.5 Sum of 100 numbers using over_79 = over_79 + 1; an iteration control END; We will see other examples of this construct in Sections 3.8 and Let age be 36. Then age/20 + 1 is equal to 2 (why not 2.8 ?). 3.9. Then the DO CASE statement is a command to execute the second statement of the group, i.e., to count another person in the 20- Exercise 3.7.13. 39 age group, which is what we desire in this case. The m m individual statements can themselves be groups (including The binomial coefficient ( ) is defined as -------- . another DO CASE statement). n n (m-n) Write an efficient program to read 'm' and 'n' and compute 3.8 SUBSCRIPTED VARIABLES and print the corresponding binomial coefficient. (Watch out for integer division.) How many multiples (or divides) A variable has a name, a value, and an address. The name does your algorithm take as a function of 'm' and 'n'? can be used either to refer to the value of the variable (as in an expression) or to refer to the address of the variable (when Exercise 3.7.14. it occurs on the left hand side of an assignment statement). We An addition chain is a sequence of integers a , such that use a declaration statement to introduce the variable and to i indicate whether it represents an integer (FIXED), a real number (FLOAT), a truth value (BIT), or text (CHARACTER). each new member is the sum of two (perhaps identical) predecessors: 1 3591 3687 46 We coin new identifiers, as needed, to represent the names of variables. Making up names and declaring them can often be a 2 3 n tedious process. Let us illustrate this point by considering a A + A X + A X + A X + ... + A X grading problem. One way to rank the students in the class is by 0 1 2 3 n expressing the points obtained by every student in the class as a percentage of the maximum score. (The process of computing One can also represent this polynomial as the relative values by dividing the actual values by a base value (often the maximum of all the values) is usually known as i normalization. Normalized values are often more meaningful than summation (i=0 to n) A X , which demonstrates the power of the actual value.) The program of Figure 3.8.1 illustrates the i computation of relative grade in a class with three students. subscript notation. This suggests that if we can somehow ┌--------------------------------------------------------------┐ represent 'grade1', 'grade2', and 'grade3' as subscripted | /* A program for converting grades as a percentage of the | variables, we may be able to formulate the algorithm for | maximum score */ | calculating the relative grades as a repetitive process. | DECLARE (grade1, grade2, grade3, maximum) FLOAT; | | /* read in grades of 3 students */ | Don't despair if you are not familiar with the subscript | grade1 = INPUT; | notations of mathematics. Suppose we represent grades in the | grade2 = INPUT; | form of a table as follows: | grade3 = INPUT; | | /* determination of the maximum grade */ | ______________________________ | maximum = grade1; | | Student No. | 1 | 2 | 3 | | IF maximum < grade2 THEN maximum = grade2; | |-------------┼----┼----┼----| | IF maximum < grade3 THEN maximum = grade3; | | Grade | 67 | 85 | 70 | | /* calculate relative grades as a percentage of maximum | |_____________|____|____|____| | grade */ | | maximum = maximum/100.0; | Then given a student number, we can look up the value of his | grade1 = grade1/maximum; | grade in the table. If we name the whole table 'grade', then the | grade2 = grade2/maximum; | grade of the i-th student can be referred to as grade . | grade3 = grade3/maximum; | i | OUTPUT = ' Relative grades are ' || | | grade1 || ' ' || | Note that the term grade uses off-the-line notation. We | grade2 || ' ' || | i | grade3; | └--------------------------------------------------------------┘ have seen, in connection with the exponential operator, that Figure 3.8.1 Relative Grade Calculation computers cannot usually handle off-the-line notation. Therefore, in PL, we enclose the subscript within parentheses, Note that writing a similar program for a class of twenty e.g., grade(i). A subscripted variable of this form can be used instead of just three would have been a tedious and boring job. in any place a simple variable can be used, e.g., expressions, What is needed is a careful evaluation and reformulation of the assignment statements, etc. algorithm. One can do much better by using the subscripted variable facility of PL. Just as we declare simple variables, we also have to declare subscripted variables. In addition to the type, one must also state the dimensionality of the array (a synonym for a 3.8.1 Subscripts table) and set aside space for it as follows: + __________ If you examine the algorithm for relative grade computation DECLARE grade (*) FLOAT; (Figure 3.8.1) you will note that the same computation is ALLOCATE grade (3); repeated over and over again, but each time using a different variable. Note further that all the variables have the same We interpret these statements to demand that 'grade' be a table attribute (FLOAT). In mathematics one collects such variables containing a single row of three numbers of type FLOAT. (The together and refers to them as a single entity, an entity with declaration and allocation of subscripted variables will be several components. You may be familiar with the following discussed in greater detail in section 3.8.3.) representation of a polynomial using subscripted coefficients: 1 3687 3772 47 Once the grades have been read in as data, the maximum ┌--------------------------------------------------------------┐ computation and the relative grade computation can be specified | DECLARE (grade(*), maximum) FLOAT, i FIXED, | as follows: | (ln, line) CHARACTER; | | ALLOCATE grade(3); | ┌---------------------------------------------------┐ | DO i = 1 TO 3; | | /* determine maximum grade */ | | grade(i) = INPUT; | | maximum = grade(1); | | END; | | DO i = 2 TO 3; | | /* determine the maximum grade */ | | IF maximum < grade(i) THEN maximum = grade(i); | | maximum = grade(1); | | END; | | DO i = 2 TO 3; | | /* relative grade computation */ | | IF maximum < grade(i) THEN maximum = grade(i); | | DO i = 1 TO 3; | | END; | | grade(i) = grade(i)/maximum; | | /* calculate relative grades */ | | END; | | DO i = 1 TO 3; | └---------------------------------------------------┘ | grade(i) = grade(i)/maximum; | | END; | If there were 20 students in the class instead of 3 we need only | /* Print the results */ | to change 3 to 20 in the two group statements. | line, ln = ''; /* initialize to null string */ | | DO i = 1 TO 3; | Using the post office box analogy, the array 'grade' can be | line = line || ' ' || grade(i); | thought of as a row of boxes. The 'DO i = 1 TO 3; ...; END;' | IF length (line) > 132 THEN | statement is a command to repeat the following process: open the | DO; | i-th box in the row, divide the actual grade by the maximum | OUTPUT = ln; /* print the line formed so far */ | grade, and replace the actual grade of box 'i' by the relative | line = grade(i); | value, where 'i' assumes the values 1, 2, and 3 in succession. | END; | | ln = line; /* save the string for possible print out */ | The relative grade program can now be rewritten using | END; | subscripted variables (Figure 3.8.2). Study the INPUT and OUTPUT | OUTPUT = line; /* print the last line */ | parts of the algorithm carefully. └--------------------------------------------------------------┘ Figure 3.8.2 Relative Grade Calculation Using Subscripts 3.8.2 Input and Output Using Subscripted Variables + ____________________________________________ The advantage of the output statements used in Figure 3.8.2 The program for relative grade computation (Figure 3.8.2) is less obvious. A simple output statement could have been also illustrates the flexibility and convenience provided by the analogous to the input statement as follows: subscripted variable for the input and output of data and results. Instead of laboriously writing out 'grade1 = INPUT', DO i = 1 TO 3; 'grade2 = INPUT', and so on, one can read in data under the OUTPUT = grade(i); repetitive control of a group statement. The statement END; DO i = 1 TO 3; grade(i) = INPUT; Since the effect of 'OUTPUT = ...' is to print a new line, in END; this case the result would have been to print 3 lines with one number per line. If there were 100 students in the class then this would mean printing 100 lines with just one number per repetitively reads the next data item in the input queue and line. Since a printed line may contain as many as 132 characters stores it in the i-th box (the second if i = 2) and increments (about 80 for typewritten output), one could print many numbers the value of 'i' by 1 (so that the next time around the i-th box on each line. If we can print all the results on 10 lines will be the third box). instead of 100, the time for printing would be reduced from 5 seconds to 1/2 second on a 100 lines-per-minute printer, thus making a better use of the printer. We could print all the numbers on one line using the statement 1 3772 3861 48 OUTPUT = grade(1) || '_' || ___________________________ grade(2) || '_' || | To| | | | | grade(3); | | 1 | 2 | 3 | 4 | |From | | | | | However, such a statement is not easily extendible if we want to |-----┼----┼----┼----┼----| print a larger number of grades. What is desirable is a | 1 | 0 | 51 | 95 | 55 | convenient way to print as many grades as possible on each line | 2 | 53 | 0 | 57 | 89 | without exceeding the total number of characters permitted per | 3 | 99 | 57 | 0 | 47 | line. | 4 | 55 | 89 | 47 | 0 | |_____|____|____|____|____| In Figure 3.8.2 we repetitively catenate data items to be printed and store the resulting string in a variable named line. Figure 3.8.3 Distance Table 'd' between Four Points If the length of line exceeds 132 characters after any catenation then the string that existed before the last Suppose we let 'd' represent the distance table. Then we catenation is printed and the variable line is initialized to can use double subscripts to talk about individual entries in grade(i) which is the first item to be printed on the following the table. d indicates the distance from point 'i' to point line. The last line being formed will not be printed within the ij group statement and is printed at the end. The output part of Figure 3.8.2 is repeated below for a careful study by the 'j'. In general, d stands for the entry in the i-th row and reader. ij /* Print the results */ j-th column, the first subscript referring to the row and the line, ln = ''; /* initialize to null string */ second to the column. Thus, d is 89 while d is 0. DO i = 1 TO 3; 24 22 line = line || '_' || grade(i); IF LENGTH (line) > 132 THEN A rectangular table, such as the distance table, is often DO; called a 'matrix' or simple 'array'. Let us consider an example OUTPUT = ln; /* print the line formed so far */ in Linear Algebra where matrix notation is very useful. Suppose line = grade(i); we have a system of linear equations as follows: END; ln = line; /* save the string for possible print out */ 1.2x + 2.3y + 0.7z = 1.9 END; 8.5x + 19.3y + 1.4z = 17.5 OUTPUT = line; /* print the last line */ 0.9x + 4.5y + 6.5z = 6.5 3.8.3 Multiple Subscripts This system of equations can be expressed using matrix notation + ___________________ as follows: Until now we have been mainly concerned with single subscripted variables. Of course, there is no need to restrict ┌- -┐ ┌- -┐ ┌- -┐ ourselves to single subscripts. Multiple subscripts occur in a | 1.2 2.3 0.7 | | x | | 1.9 | natural way in many problems we have to deal with. Consider the | 8.5 19.3 1.4 | | y | = | 17.5 | problem of representing the distances between a number of | 0.9 4.5 6.5 | | z | | 6.5 | points. The distances between points can be represented by the └- -┘ └- -┘ └- -┘ table in Figure 3.8.3. The table would be symmetric about the diagonal if the distance from point 'i' to point 'j' were the where the coefficients are represented as a matrix. Matrix same as the distance from 'j' to 'i'. (Note that the distances representation provides many conceptual and theoretical need not be the same if they are separated by one-way highways.) advantages in the solution of a system of linear equations. In PL, variables can have any number of subscripts. Very few routine problems require the use of more than two or three subscripts. Subscripts are enclosed within parentheses and separated by commas. For example, the variables a , b , and i ij 1 3861 3960 49 c are represented in PL as a(i), b(i,j), and c(i,j,k). All variables, simple and subscripted, must be declared. We ijk already know how to declare simple variables. For subscripted variables, the declaration must include, in addition to name and Further, a subscript can be any valid expression, e.g., a type, the number of dimensions. For example, the distance table constant, a variable, or any expression yielding an arithmetic 'd' could be declared as follows: value. If the value of the expression is not an integer then an attempt will be made to convert it to an integer and an error DECLARE d (*,*) FIXED; indication will occur if the conversion is not valid. Now we can ALLOCATE d (4, i + 4); precisely define a variable. Consider the above pair of statements: the declaration <variable> ::= <identifier> statement commands the machine to set aside, in the name of 'd', | <identifier> (<subscript list>) a two-dimensional array of unknown size. (Referring back to the <subscript list> ::= <subscript> hotel analogy of section 3.1 we might say "set aside a block of | <subscript list> , <subscript> rooms for a group of people who will be coming to attend the <subscript> ::= <expression> | * Fall Joint Computer Conference!") The second statement, ALLOCATE d (4, i + 4); , defines the size of the array, e.g., 4 rows and i + 4 columns. In our analogy, allocation of space must precede The following examples illustrate the parsing of subscripted the arrival of delegates. Note that the value of 'i' must variables. already be defined. a ( i + 5 ) Suppose you declare an array 'cost' using the following | | | | pair of statements: <identifier> | <expression> | | | | | DECLARE cost (*) FLOAT; | | <subscript> | ALLOCATE cost (10); | | | | | | <subscript list> | Implicit within the definition is the fact that the first | | | | element is referred to by the subscript 1, i.e., ALLOCATE cost | | | | (10) specifies that the range of the subscript values is from 1 |________|_________|__________| to 10. Suppose we wish the range to be from 1951 to 1960 instead | of 1 to 10. This might be more meaningful if cost (1951) refers <variable> to the cost of an item in the year 1951. Thus DECLARE cost (*) FLOAT; d ( 5 , j*i+k , i+8 ) ALLOCATE cost (1951:1960); | | | | | | | | <identifier> | <expression> | <expression> | <expression> | declares a one-dimensional array 'cost', and then allocates to | | | | | | | | 'cost' 10 elements with subscripts ranging from 1951 to 1960 | | <subscript> | <subscript> | <subscript> | instead of from 1 to 10. If the lower bound of a subscript is to | | | | | | | | be other than 1 then both the lower bound and the upper bound of | | <subscript list> | | | | | the range of the subscript must be given and the two numbers | | | | | | | | must be separated by a colon. | | └---------┼------┘ | | | | | | | | | In the ALLOCATE statement, then, the array size is given | | <subscript list> | | | within parentheses, the number of rows as the first entry and | | | | | | the number of columns as the second. A constant row or column | | └--------------┼------┘ | number can, in fact, be replaced by an expression. A precise and | | | | more general form of declaration is given below: | | <subscript list> | | | | | <declaration statement> ::= DECLARE <declaration list> ; |_______|_________________________________|______________| <declaration list> ::= <declaration element> | | <declaration list> , <declaration element> <variable> <declaration element> ::= <declaration primary> | <declaration primary> <attribute list> <declaration primary> ::= <identifier> 1 3960 4060 50 | (<declaration list>) values in each of the ranges <attribute list> ::= <attribute> (0, 1/a), (1/a, 2/a) ... (a-1/a, 1) | <attribute list> <attribute> for any integer 'a'. Write a program to test the built-in <attribute> ::= (<asterisk list>) function RANDOM for 1000 values and a = 10. Print the | <type> result as a bar graph. I.e., | ENTRY .0 - .1 xxxxxxxxxx | LABEL .1 - .2 xxxx <type> ::= BIT .2 - .3 | FIXED .3 - .4 | FLOAT ... | CHARACTER <asterisk list> ::= * | <asterisk list> , * Exercise 3.8.2. <allocation statement> ::= ALLOCATE <allocation list>; A correctly uniform random number generator may <allocation list> ::= <allocation element> nevertheless have higher order correlations (e.g., the | <allocation list> , <allocation element> difference between pairs might be constant). Write a <allocation element> ::= <identifier> (<bounds list>) program to test the second order randomness of the built-in <bounds list> ::= <bound> function RANDOM by allocating an array t(0:9,0:9) and | <bounds list> , <bound> counting up each position by one for each pair of calls to <bound> ::= <expression> RANDOM. A failure in second order randomness will show up | <expression> : <expression> as a pattern in 't'. Example: 3.9 GROUP STATEMENT: Additional Constructs DECLARE d ( *,* ) FIXED, cost ( * ) FLOAT ; | | | | | | | | | | | | | | <iden.> |<ast.list>|<type>| <iden.> |<ast.list>| <type>| 3.9.1. Repetitions within Repetitions: Nested Loops + ____________________________________________ | | | | | | | | | | | | | |<decl.pri.>|____|_____|<att.>|<decl.pri.>|____|_____| <att.>| Suppose we have a matrix representing a tax table which has | | | | | | | | | to be modified to reflect a 10% increase in taxes. A program for | | <attribute> | | | <attribute> | | modifying the table must multiply every element of the table by | | | | | | | | | 1.1 (why?) to produce a new tax table. How does one specify 'for | | <att. list> | | | <att. list> | | every element of the matrix' in PL? If the table happened to be | | | | | | | | | one dimensional (i.e., requiring only a single subscript), then | | |_________| | | |_________| | the solution is similar to the calculation of the relative cost | | | | | | | of living indices. If the table is two dimensional, then we need | | <att. list> | | <att. list> | two subscripts to refer to an element, e.g., tax(i,j). | | | | | | | | |_______________| | |_______________| | Thus we need a mechanism for permitting 'i' to vary over | | | | | all the possible row numbers and 'j' to vary over all the | <decl. elem.> | | | possible column numbers. One way to do this is to let 'j' vary | | | <decl. elem.> | over all the possible column numbers for each value 'i'. | <decl. list> | | | | | | | | The program would be as follows: | |_______________|_____________| | | | | DECLARE tax (*,*) FLOAT; | <decl. list> | DECLARE (i,j) FIXED; | | | ALLOCATE tax (100,10); /* say the table is 100 x 10 */ |_____________________________|______________________________| DO i = 1 TO 100; | DO j = 1 TO 10; <declaration statement> tax (i,j) = 1.1 * tax (i,j); END; Exercise 3.8.1. END; A random number generator with a uniform distribution between 0.0 and 1.0 should yield about the same number of The statement 1 4060 4158 51 DO i = 1 TO 100; ┌----------------------------------------------------------┐ is a command to perform the statement following it 100 times for | DECLARE (w, x, y, z) FIXED; | 'i' taking values 1 to 100. The following statement is another | DO w = 1 TO 20; | group statement which is a command to repeat | DO x = 1 TO 20; | tax (i,j) = 1.1 * tax (i,j); | DO y = 1 TO 20; | 10 times for 'j' taking values 1 to 10. Therefore, for every | DO z = 1 TO 20; | value of 'i', 'j' varies over the values 1 to 10, thus modifying | IF x**3 + y**3 + z**3 = w**3 THEN | all of the i-th row of the tax table. | OUTPUT = x || ' ' || | | y || ' ' || | Such repeated execution of a computation is usually called | z || ' ' || w; | a loop. When the loop itself is within a loop, it is called a | END; | nested loop. Nesting of loops can go to any number of levels-- | END; | loops, loops within loops, loops within loops within loops, and | END; | so on. Let us illustrate by an example in number theory. Most of | END; | us are familiar with the Pythagorean equation: └----------------------------------------------------------┘ 3 3 3 3 2 2 2 Figure 3.9.1. Solutions of x + y + z = w x + y = z . What are all the triples of integers that satisfy this simple The program in its present form is inefficient and can be improved in many ways. Writing efficient programs requires 2 2 2 careful analysis of the problem at hand. We will see later how algebraic equation? We know 3 + 4 = 5 is one. Any multiple this program can be improved. of (3,4,5) is also a solution; (5, 12, and 13) is another, and so on. 3.9.2 The Do Statement with a Variable Increment + __________________________________________ n n n Equations of the form x + y = z are known as the The statement 'DO i = 1 TO 6; ... ; END;' is equivalent to 2 2 2 i = 1; Diophantine equations of which x + y = z is a special case. DO WHILE i <= 6; Are there solutions in integers for n > 2 ? Fermat's conjecture . states that there are no integer solutions for n > 2. While this . conjecture is generally believed to be true, many generations of . mathematicians have not succeeded in proving or disproving this i = i + 1; conjecture. However, the conjecture has been proved for a large END; number of specific values of 'n'. For 3 3 3 Thus, each time around the loop, the value of 'i' is incremented example, one can prove that x + y = z cannot be satisfied by by 1. Sometimes it is desirable to be able to change this fixed positive integers 'x', 'y', and 'z'. increment, 1, to some other (positive or negative) increment. This can be done in PL by adding a new construct of the form However, there are infinitely many solutions in integers of 'DO i = 1 TO 6 BY 2' which specifies an increment of 2. 3 3 3 3 We will illustrate the use of these constructs by the equation x + y + z = w . Our problem is to find all the considering a sorting problem. Sorting is the process of 4-tuples 'x', 'y', 'z', and 'w' which satisfy this equation and rearranging data items in sequence according to some specific also satisfy the condition that w <= 20. While this would be a rules. A dictionary is a typical example of a sorted list of tedious job to do by hand, writing a program to do the same task items. Sorting can be in alphabetic or numeric order, depending is relatively simple. One solution is to let the value of all on the data items in question. the variables vary over the range 1 to 20 and print out those that satisfy the equation. This requires the use of a four-level Suppose we wish to rearrange a list of numbers in nested loop as follows: increasing order. Let 'a' be a one-dimensional array with the following initial values: 1 4158 4248 52 __________________________________________________ can repeat the process again; this time considering only the | a(1) | a(2) | a(3) | a(4) | a(5) | a(6) | a(7) | first 5 pairs of elements of 'a' so as to move the largest of |------┼------┼------┼------┼------┼------┼------| the first 6 elements to a(6). | 39 | 3 | 15 | 6 | 10 | 8 | 34 | |______|______|______|______|______|______|______| Exercise 3.9.1. Write down the values of elements of 'a' after the second repetition. After rearranging, the array 'a' should have the following values: If we repeat this process 6 times, each time reducing the number of pairs considered by one, we shall have rearranged the __________________________________________________ values of 'a' in increasing order. We can reduce the number of | a(1) | a(2) | a(3) | a(4) | a(5) | a(6) | a(7) | pairs considered by changing the statement 'DO i = 1 TO 6' |------┼------┼------┼------┼------┼------┼------| (Figure 3.9.2) to 'DO i = 1 TO k' and insuring that 'k' takes | 3 | 6 | 8 | 10 | 15 | 34 | 39 | the values 6, 5, 4, 3, 2, and 1. We can do this as follows: |______|______|______|______|______|______|______| DO j = 1 TO 6; DO i = 1 TO 7-j; There are many different algorithms for obtaining this final IF a(i) > a(i+1) THEN result. One of these is known as Bubble Sort. It is an extension DO; of the solution for finding the maximum of an array. For temp = a(i); example, the statement of Figure 3.9.2. rearranges the array 'a' a(i) = a(i+1); so that the largest element is in a(7). a(i+1) = temp; END; ┌---------------------------------------┐ END; | DO i = 1 TO 6; | END; | IF a(i) > a(i+1) THEN | | DO; | | temp = a(i); | Note that we have replaced 'DO i = 1 TO 6' by 'DO i = 1 TO 7-j' | a(i) = a(i+1); | to insure that the number of repetitions decreases by 1 each | a(i+1) = temp; | time. This is the first time we have used the full generality of | END; | the incrementation control by replacing the constant 6 by the | END; | expression '7-j'. └---------------------------------------┘ Figure 3.9.2 Maximum of an array More generally, it would be desirable to be able to specify increments in PL by a simple addition of BY <expression> to the group control. The value of the <expression> indicates the How? We first consider the values of a(1) and a(2). If a(1) is increment to the variable each time around the loop. If it is larger than a(2), we swap the values of a(1) and a(2) using a omitted then the increment is taken to be 1. Neither the temporary variable (see Section 3.2). After the swap the value increment nor the bound can be changed once the loop is begun. of a(1) will be 3 and the value of a(2) will be 39. We repeat Thus the statement the process 6 times, each time considering the successive pairs DO i = j TO k BY m; of numbers a(2) a(3), a(3) a(4), a(4) a(5), a(5) a(6), and a(6) is equivalent to a(7). Each time around, the largest value 39, bubbles one position towards the last element of the array and, after the i = j; sixth repetition, the array 'a' will have the following values: DO WHILE SIGN (m) * i <= SIGN(i) * k . __________________________________________________ . | a(1) | a(2) | a(3) | a(4) | a(5) | a(6) | a(7) | . |------┼------┼------┼------┼------┼------┼------| i = i+m; | 3 | 15 | 6 | 10 | 8 | 34 | 39 | END; |______|______|______|______|______|______|______| so long as neither 'm' nor 'k' appears on the left of an Thus, the above statement has the effect of moving the largest assignment in the second form. Note the SIGN(m) is 1 if the value to a(7) without destroying the other elements of 'a'. We value of 'm' is positive and -1 if the value of 'm' is negative. 1 4248 4341 53 While i <= k is the proper test to make when the increment is previous section can be programmed more efficiently. Let the positive, one has to use i >= k when the increment is negative. elements of the array 'a' be as follows: That is why we need the above form of the DO WHILE statement. Now we can rewrite the sort routine without using the expression __________________________________________________ 7-j. | a(1) | a(2) | a(3) | a(4) | a(5) | a(6) | a(7) | |------┼------┼------┼------┼------┼------┼------| ┌---------------------------------------------------┐ | 3 | 6 | 8 | 15 | 10 | 39 | 34 | | DECLARE (a(*), i, j, temp) FIXED; | |______|______|______|______|______|______|______| | ALLOCATE a(7); | | DO i = 1 TO 7; a(i) = INPUT; END; | | DO j = 6 TO 1 BY -1; | This list is almost in sequence and after the first execution of | DO i = 1 TO j; | the inner loop of the sorting algorithm (Figure 3.9.3) all the | IF a(i) > a(i+1) THEN | elements of 'a' will be in sequence. (Exercise. Verify the | DO; | validity of the above statement by hand simulation.) Thus it | temp = a(i); | would be desirable to terminate the repetition of the inner loop | a(i) = a(i+1); | as soon as we know that the elements are in sequence. How can we | a(i+1) = temp; | determine whether or not the elements of 'a' are in sequence? | END; | Note that if the elements get to be in sequence during the i-th | END; | iteration (repetition), then no swapping will take place during | END; | the (i+1)-th iteration. One can use a logical variable, | DO i = 1 TO 7; OUTPUT = a(i); END; | 'swapping', to remember whether swapping has taken place and └---------------------------------------------------┘ test it either to continue or terminate processing. A sorting Figure 3.9.3 The Sorting Algorithm algorithm with test for swapping is given in Figure 3.9.4. ┌------------------------------------------------------------┐ Exercise 3.9.2. | DECLARE (a(*), i, j) FIXED, swapping BIT; | Let skin be a 10 x 10 patch of healthy skin cells with one | ALLOCATE a(7); | infected cell near the center. Each time-step an infected | DO i = 1 TO 7; a(i) = INPUT; END; /* read in array */ | cell has 0.5 probability of infecting each of its healthy | swapping = TRUE; | neighbors. After 6 time steps an infected cell becomes | DO j = 6 TO 1 BY -1 WHILE swapping; /* i.e., while | immune for 4 more steps, then becomes healthy once again. | swapping is true */ | Simulate this situation on the computer, printing the skin | swapping = FALSE /* initialize swapping to FALSE each | at each step. | time */ | | DO i = 1 TO j; | Exercise 3.9.3. (Forsythe) | IF a(i) >= a(i+1) THEN | Given a finite initial sequence of a power series, | DO; | summation (i = 0 to infinity) a(i)*x**i, we wish to compute | temp = a(i); a(i) = a(i+1); a(i+1) = temp; | the initial sequences of two more series, the reciprocal | swapping = TRUE; /* record a swap */ | and the inverse. | END; | | END; | [summation (1 = 0 to infinity) a(i)*x**i] * | END; | [summation (i = 0 to infinity) b(i)*x**i] = 1. | DO i = 1 TO 7; OUTPUT = a(i); END; /* print results */ | summation (i = 0 to infinity) a(i)*x**i = f*(x), └------------------------------------------------------------┘ summation (i = 0 to infinity) c(i)*x**i = f**-1*(x). Figure 3.9.4 The Sorting Algorithm with Swap Test The statement 'DO j = 6 TO 1 BY -1 while swapping;' is a Given the initial coefficients in an array 'a', write a command to repeat the following statements (and of course to program to compute the new series in arrays 'b' and 'c'. decrease the value of 'j') while j >= 1 and while 'swapping' is TRUE. The variable 'swapping' is set to TRUE every time a swap takes place in the inner loop. Thus the inner loop will be 3.9.3 The DO WHILE statement with a Control Clause repeated only as many times as necessary, but never more than + ____________________________________________ the maximum of 6 times. Until now we have seen statements which use either a 'WHILE <expression>' or a control clause but not both. Often it is desirable to use both. For example, the sorting problem of the 3.9.4. The DO CASE Statement with a Control Clause + ___________________________________________ 1 4341 4426 54 One can include a control clause in a 'DO CASE' statement Like variables, statements can also be referred to by also. The statement 'DO i = 1 TO n CASE a(i);' is interpreted as names; a name for a statement is called a label. A labeled follows: statement has the form <identifier>:<statement> DO i = 1 TO n; Examples: DO CASE a(i); next: OUTPUT = french (i) ; . start: a,b,c = 0 ; /* initialize */ . . A label is usually used in conjunction with the GO TO END; statement. The GO TO statement is one of the constructs in PL END; which can alter the normal sequential execution of statements within a program. This statement causes control to be An example of the use of the DO CASE statement with control transferred to a specified statement within the program; it is clause is in writing crypto programs. Normally statements are useful only where the conditional statement or the group executed sequentially, starting with the first. But occasionally statement cannot be used conveniently. The form of the GO TO one may wish to disguise a program so that no one else can use statement is given by the rule: it, to preserve the secrecy of some industrial process for example. In such a case, the statements of the program would be <GO TO statement> ::= GO TO <identifier>; rearranged in some random sequence, and spurious statements | GOTO <identifier>; might even be introduced. In order to use the program one must have a key, a list of numbers indicating the sequence in which A GO TO statement, say 'GO TO next;', causes the program to the statements must be executed. The following overall structure interrupt the sequential execution and transfer control to the of the program can be used to execute the statements according statement labeled 'next'. Thus it is the next statement to the key. executed. ┌---------------------------------------------------------┐ Any valid identifier can be used as a label and we coin | DECLARE (key(*), n) FIXED; | them as we need them while writing programs. A label (a name) | ALLOCATE key (1000); | can be given to any statement in the program. One usually labels | n = INPUT; /* read in the number of statements to be | a statement only when it is necessary to transfer control to the | executed */ | statement from some other part of the program. Meaningful labels | DO i = 1 TO n; key (i) = INPUT; END; | can enhance the readability of a program. | DO i = 1 TO n CASE key (i); | | . | | . | 3.10.1 Restrictions on GO TO statements + ________________________________ | . | | <randomly arranged statements> | In languages like Fortran, which has but a few primitive | . | forms of the conditional statement and group statement, the GO | . | TO statement is indispensable. For example, the conditional | . | statement | END; | | OUTPUT = 'End of program'; | IF a < b THEN maximum = b; └---------------------------------------------------------┘ ELSE maximum = a; Figure 3.9.5 Structure of an Encripted Program Given a rearranged program and the key, one can insert the can be rewritten using the GO TO statement as follows: above statements before and after the program, read in the number of elements in the key and then the key itself, and IF a < b THEN GO TO maxb; execute the statements according to the key. maximum = a; GO TO next; Exercise 3.9.4. maxb: maximum = b; Make a rearranged version of the GCD algorithm (2.3.2) and next: ... a key for it. Hand simulate the function of Figure 3.9.5. Similarly the group statement 3.10 THE GO TO STATEMENT 1 4426 4520 55 DO i = 1 TO n; Figure 3.10.1 shows some typical entries in four different sum = sum + x(i); types of tables we deal with: a sales tax table, a logarithm END; table, an income tax table, and a telephone directory. We will illustrate various schemes for computer table search by means of can be rewritten as these four examples. i = 1; ________________ _______________________ loop: IF i > n THEN GO TO next; | total | tax | | number | logarithm | sum = sum + x(i); |-------┼------| |---------┼-----------| i = i+1; | . | . | | . | | GO TO loop; | . | . | | . | | next: ... | . | . | | . | | | 5.40 | 0.27 | | 26.0000 | 1.41497 | In PL, the conditional statement and the group statement | 5.60 | 0.28 | | 26.0001 | 1.41499 | obviate the need for such uses of the GO TO statement. A GO TO | 5.80 | 0.29 | | 26.0002 | 1.41500 | statement is mainly useful for transferring control from the | 6.00 | 0.30 | | . | . | middle of a conditional statement or a loop (see 3.10.2). | . | . | | . | . | | . | . | | . | . | Unnecessary use of the GO TO statements makes programs |_______|______| | 27.0000 | 1.43136 | unreadable and difficult to follow and should be avoided. A GO | . | . | TO statement may not transfer control from outside of a group | . | . | statement to a statement within the DO ... END symbols. | . | . | |_________|___________| 3.10.2 Table Search (a) A sales tax table (b) A logarithm table + ____________ Consider the functional relation y = f*(x). If 'f' is a _______________________ _______________________ complicated function (like sine, log, etc., which may require |gross income| tax | | name | number | the use of mathematical tables) or if 'f' cannot conveniently be |------------┼--------| |__________┼__________| expressed as a mathematical formula in terms of 'x' (telephone | . | | | . | . | directories, dictionaries, etc.) then we make up a table with | . | | | . | . | entries for 'x' and 'y'. To find the value of 'f' for a given | . | | | . | . | 'x', we scan through the table until we find the desired entry. | 2050 | 280.00 | | Hardy | 3244237 | This process is known as table look-up or table search. | 2060 | 281.10 | | Harmon | 3644297 | | 2070 | 282.75 | | Hastings | 3327800 | Arrays provide a convenient means for storing tables in a | 2080 | 284.35 | | Hoffman | 9678300 | computer. However, large tables can quickly use up the limited | . | | | . | . | computer memory. Thus many common mathematical functions are | . | | | . | . | calculated, in a computer, using the formulas instead of tables. | . | | | . | . | However, if a particular function, say sine, is used a large |____________|________| |__________|__________| number of times within a program (as in the case of Fourier analysis) it may be efficient to use a table of sine values. (c) An income tax table (d) A telephone directory Exercise 3.10.1. Figure 3.10.1 Different types of tables Suppose you are given a sine table of 91 values (0 to 90 degrees). Given an angle rounded to the nearest degree you Suppose we want to write an algorithm for sales tax have to find the value of the corresponding sine by looking computation. In our example (Figure 3.10.1a) the tax can be it up in a table. Write a program to read the table of expressed by a simple function of the total; viz., sines into an array called 'sine', read an angle between 0 tax = 0.05 * total; and 90 and print out the sine of the angle. How would you While people may find it convenient to use tax tables, such modify the program if the angle can be between 0 and 360? calculations can be performed with ease by a computer and there What if the angle can be any integral value, positive or is no need to use a table. negative? What if it is not integral? All the solutions must use the sine table above. In the case of the income tax table, however, it may be difficult to make up a formula which can be used to calculate 1 4520 4606 56 taxes for every possible income. Thus we observe a case where it ┌--------------------------------------------------------------┐ is indeed useful to have a table of tax values, i.e., an array | DECLARE (i, income, quotient, remainder) FIXED; | containing the taxes for various incomes. Suppose we are asked | DECLARE (tax(*), incometax) FLOAT; ALLOCATE tax (10000); | to find the tax for $2070. We can scan through the table until | /* read in the tax table for 10 to 100,000 dollars in | we find 2070 and look up the corresponding tax. In PL, this | increments of $10 */ | table would require an array with two columns, one for the | DO i = 1 TO 1000; tax(i) = INPUT; END; | income and the other for the tax. Note, however, that the income | . | entries vary by a fixed value, 10. The table array can be | . | reduced from two columns to one column if we can compute a | . | subscript based on the income which would then point to the | income = INPUT; /* read in the gross income to the nearest | appropriate tax for that income. In this case, the rule should | dollar | be obvious, namely, divide the income by 10 and use the quotient | quotient = income/10; /* calculate the subscript to the | as a subscript. | appropriate entry */ | | remainder = income-10 * quotient; /* this is same as | income subscript tax | MOD (income, 10) */ | ------ --------- ------ | incometax = tax (quotient) + remainder * (tax (quotient + 1) | 10 1 0 | - tax (quotient))/10; | 20 2 0 | OUTPUT = 'income tax for $' || income || ' is $' ||incometax;| . . . └--------------------------------------------------------------┘ . . . Figure 3.10.3 Income Tax Calculation . . . 2050 205 280.00 Suppose you are given a name and asked to find the 2060 206 281.10 telephone number by looking it up in a table. In this case there 2070 207 282.75 is no convenient way of computing a subscript from the name as 2080 208 284.35 in the case of the income tax table; this means we must store . . . both the columns of Table 3.10.1d in an array form. Let us . . . assume that these are declared as . . . DECLARE name (*) CHARACTER, number (*) FIXED; Figure 3.10.2 Subscripts Associated with Income ALLOCATE name (10000), number (10000); providing for a table with a maximum of 1000 entries. Since the Now if we declare an array 'tax' of 10,000 elements (to store a actual number of entries in any given case can vary, let us make tax table from 10 to 100,000 dollars) then the tax for $2070 this a variable, say 'n', which is also specified as data. Let will be given by 'tax(207)'. us also assume that these 'n' entries (names and numbers) have been read and stored in 'name' and 'number'. The table (Figure 3.10.2) gives taxes in 10 dollar increments. What if we are required to compute taxes to the Given a name, we must first look through the name table nearest dollar? One can do this by linear interpolation. For until we find the name we are looking for, and use the example, the tax for $2074 can be calculated by the following corresponding entry (one with the same subscript) in the number expression: table. We do not know how far we have to search through the tax (207) + 4*(tax (208) - tax (207))/10 'name' array before we find the desired entry. Therefore, we use i.e., 282.75 + 0.4*(284.35 - 282.75) = $283.39. Figure 3.10.3 a group statement capable of comparing the names repetitively gives an algorithm for computing taxes for a given income using until the last, but interrupt the repetition, by means of a GO interpolation. TO statement, as soon as we find an equal, viz., DO i = 1 TO n; IF name (i) = person THEN GO TO found; END; found: /* 'i' now is the desired index unless i > n */ The execution of the 'DO ... END;' statement is completely interrupted and control is transferred to the label 'found' as soon as the entry in the table matches the given name. The control variable 'i' retains its last assigned value when the 1 4606 4703 57 loop is left prematurely. If the loop is terminated according to Figure 3.10.5). The group statement of Figure 3.10.5 illustrates its regular course, the value of 'i' would be greater than 'n' how one can isolate that part of the table which will contain (why?). the desired entry (if it is in the table at all). The variables 'lowindex' and 'highindex' keep track of which protion of the ┌--------------------------------------------------------------┐ table we are interested in. They are set at the beginning to 1 | /* Look up a telehpne number */ | and 'n' and modified each time we do not find an equal. The | /* Number (i) contains the telephone number of name (i) */ | repetition is terminated when the desired entry is found or when | DECLARE (person, name (*)) CHARACTER, | we know that it is not in the table (lowindex > highindex). | (i, n, number (*)) FIXED; | | n = INPUT; /* read in the number of elements in the table */ | Note that the binary search routine is more complex and | ALLOCATE name (n); | will therefore take more time for each repetition. Even if it | ALLOCATE number (n); | takes twice as much time per repetition, it is still far more | DO i = 1 TO n; | efficient than a linear search of a large table. | name (i) = INPUT; /* assume name and number | | are together */ | ┌--------------------------------------------------------------┐ | number (i) = INPUT; | | . | | END; | | . | | . | | . | | . | | person = INPUT; /* read the name of the person */ | | . | | DECLARE (lowindex, highindex) FIXED; | | person = INPUT; /* read in the name of the person whose | | lowindex = 1; | | telephone number is desired */ | | highindex = n; | | DO i = 1 TO n; | | i = (lowindex + highindex)/2; | | IF name (i) = person THEN GO TO found; | | DO WHILE (name (i) ^= person) & (lowindex <= highindex); | | END; | | IF name (i) > person THEN highindex = i-1; | | found: IF i <= n THEN | | ELSE lowindex = i+1; | | OUTPUT = name (i) || ' ' || number (i); | | i = (lowindex + highindex)/2; | | ELSE OUTPUT = 'no such name in the table'; | | END; | | . | | IF lowindex > highindex THEN OUTPUT = 'no such person in the | | . | | table'; | | . | | ELSE OUTPUT = name (i)|| ' '|| number (i); | └--------------------------------------------------------------┘ | . | Figure 3.10.4 Search for a telephone number | . | | . | └--------------------------------------------------------------┘ 3.10.3. Binary Search Figure 3.10.5 A binary search routine for Figure 3.10.4 + _____________ The algorithm given in Figure 3.10.4 uses a linear search throughout the table, i.e., it attempts to look at the elements 3.11 BLOCK STRUCTURE one after the other until it gets to the end or finds an equal. On the average it would look at n/2 elements to locate a So far we have declared variables as we needed them in a particular name. If the table is ordered (in our case, program. Each variable requires a unique name and uses one or alphabetically), then by using a binary search procedure the more memory cells to store its value. As we write larger and number of comparisons can be reduced to about log(2) n. In a larger programs using more and more variables, we will soon come million-word table this can mean a reduction from 500,000 to 24 against practical limitations: computers have limited storage comparisons. and people have a limited willingness to invent names. We will illustrate the principle of binary search by It is easy to exceed the memory capacity of a computer. considering the way we look up a number in a telephone book. We Most present-day computers can't even hold a single 1000 * 1000 certainly do not start at the beginning and look at each element matrix in their main mamory. Since every declaration statement in the telephone book until we find the desired entry. What we uses up some more of this valuable resource, one would like to do is to split the book somewhere in the middle and decide which organize programs so as to minimize the storage requirement. A half of the table the name is in. Then we look at that half and variable needs to be allocated storage only when it is being repeat the process. An algorithm for the computer can use an used. So it would be desirable to have a facility in the analogous process in searching through an ordered table (see language which would allocate storage when necessary and release 1 4703 4787 58 storage after it has served its purpose. statements. This leads to a hierarchy of blocks within blocks within blocks, or nested blocks. The following diagram Every time a new variable is used in a program we have to illustrates the structure of a program with nested blocks. It is invent a new name for it. Since every new variable uses up a good programming practice to paragraph all the statements additional storage space and requires a new name, one can often within the BEGIN ... END brackets by indenting (see Section use the same variable to serve different purposes at different 2.3.4). points in a program. In large programs this can lead to unintended modification of the value of a variable. An example ┌--------- of a common error in programs is the inadvertent modification of | S; the index variable of a DO loop. | S; | ┌-- Exercise 3.11.1. | |BEGIN; What is the output of this program? | | S; |block | S; ┌-----------------------------------┐ | 1 < S; | count = 0; | | | S; | DO i = 1 TO 10; | | |END; | DO i = 1 TO 10; | | └-- | count = count + 1; | | S; | END; | | ┌-- | END; | program < |BEGIN; | OUTPUT = count; | | | S; └-----------------------------------┘ | | S; | | ┌-- Block structure in PL provides a convenient mechanism for |block |block |BEGIN; delineating parts of a program so that the programmer can decide | 2 < 3 < S; S; when he wants to declare a variable and when to release it. One | | |END; can delineate a part of a program by enclosing it with a BEGIN | | └-- ... END or PROCEDURE ... END symbol pair. The main virtue of | | S; block structure is that a declaration appearing within one of | |END; these symbol pairs is only valid for those statements within. | └-- | S; Referring to the BNF definition of PL in Chapter 2, we note └--------- that In the above diagram block 1 and block 2 are said to be <basic statement> ::= ...| <block> parallel. Block 2 is dominant to block 3 and block 3 is | <procedure definition> | ... subordinate to block 2. <block> ::= <block head> <statement list> <ending>; <procedure definition> ::= <procedure head> <statement list> <ending>; 3.11.1. Scope of a Variable + ___________________ <block head> ::= BEGIN; <procedure head> ::= <label definition> PROCEDURE; | ... Blocks are mainly used to restrict the sphere of <ending> ::= END | ... effectiveness of declarations. A variable declared in a block is only valid within that block. Upon exit from a block the In this section we will restrict ourselves to the discussion of resources (mainly memory) used by the variables declared in that blocks. (See Section 3.12 for procedures). Note that a block is block are released and the names cease to be meaningful. As an a basic statement. Therefore, like other basic statements it is example, consider the following piece of a program. executed in the sequence in which it appears in a program (unless the sequence is altered by a control statement). For a block this means that all the statements within the BEGIN ... END pair are executed once (as in the case of a group statement). Since a block is just another basic statement, the statement list of one block may contain other blocks as 1 4787 4874 59 ┌-------------------------------------------┐ Let us, for now, assume that the same name is not used in | DECLARE hours (*) FIXED, total (*) FLOAT; | different declarations of the program. A variable declared in a | ALLOCATE hours (10000), total (10000); | block is valid for all the statements in that block. In | ┌---------------------------------┐ | particular, it is valid for all the subordinate blocks. Thus, in | |/* hours only used in the first | | the following program, | | part of the program */ | | | |S; | | ┌--------------------------------------┐ | |S; | | | BEGIN; | | |S; | | | DECLARE a FIXED; | | └---------------------------------┘ | | a = 2; | | | | BEGIN; | | ┌---------------------------------┐ | | DECLARE b FIXED; | | |/* total only used in the second | | | a = 1; b = 2; | | | part of the program */ | | | OUTPUT = a; | | |S; | | | END; | | |S; | | | OUTPUT = a; | | |S; | | | END; | | └---------------------------------┘ | └--------------------------------------┘ | | └-------------------------------------------┘ although only 'b' is declared within the subordinate block, both 'a' and 'b' are valid. 'a' is valid because it is declared in a dominant block. Upon exit from the subordinate block all The arrays 'hours' and 'total' together require 20,000 locations information about 'b' is lost (including its value) but 'a' of storage. Suppose we know that the array 'hours' is only used retains its value. Thus the number 1 will be printed twice by in the first part of the program and 'total' only in the second the above program. part. By reorganizing the program using block structure as shown below, one can reduce the storage requirement by 10,000 The variable 'a' is said to be global and 'b' local with locations. respect to the subordinate block. The concept of global vs. local is important and should be clearly understood; in ┌------------------------------┐ particular, note that changes to the global variables are | S; | retained and changes to the local variable are lost upon exit ┌--| BEGIN; | from the block. | | DECLARE hours (*) FIXED; | block | | ALLOCATE hours (10000); | Let us now remove the restriction of not using the same 1 < | S; | name in different declarations. When the same name appears in | | S; | two different blocks it is referring to two different entitites. | | S; | Since this may sometimes lead to confusion, it is desirable not └--| END; | to use the same name unless there is a good reason for doing so. | | If the same name is declared in two parallel blocks, the first ┌--| BEGIN; | declaration is nullified by the time the execution of the second | | DECLARE total (*) FLOAT; | block begins and so there is no possibility of a conflict. block | | ALLOCATE total (10000); | 2 < | S; | When the same name is declared in both a dominant and a | | S; | subordinate block, as in the following program, there arises a | | S; | potential conflict between the two uses of the same name. └--| END; | └------------------------------┘ Upon exit from block 1, storage required by 'hours' is automatically released, making it available for use with 'total' in block 2. (The same effect could have also been achieved using the FREE statement (section 3.11.1) under explicit program control.) The program may now be able to run on a smaller computer. 1 4874 4964 60 ┌------------------------------┐ with any computation within that block. There is no way one can | DECLARE a FIXED; | refer to it directly from within the inner block. Upon exit from | a = 2; | the inner block, however, the local 'a' ceases to exist and the | BEGIN; | potential conflict is removed. Now the global 'a' becomes | DECLARE (a,b) FIXED; | accessible for use again. Thus the output from the above program | a = 1; b = 2; | consists of the numbers 1 and 2. The essential concepts of the | OUTPUT = a; | scope of a variable may be summarized as follows: | END; | | OUTPUT = a; | There is a set of statements in a block that are not part └------------------------------┘ of any other subordinate block. If a declaration is contained in the set of statements, then the 'range' of its With respect to the suboridinate block, the name 'a' appears effect is all the statements in the block, including both as a global variable and as a local variable. The following suboridinate blocks. questions arise: The 'scope' of a name is the range of its declaration less the range of any other declaration of that name in a 1. Are they referring to one and the same entity? subordinate block. 2. If they are two separate entities, are we referring to the global 'a' or the local 'a' when we say 'a = 1;' in the Exercise 3.11.1. inner block? Close the book and then write a definition for the scope of 3. If we say the local variable has precedence over the a name. Does your definition have the same meaning as the global variable, what happens to the global variable? Is it one just given? lost forever? The answers to the first two questions were implied in the 3.11.2. Dynamic Storage and the Allocation Statement + ____________________________________________ questions following them. Each block introduces a new nomenclature. It is as though each time a new block is entered, In PL, the dimensionality and the attributes of an array a unique block number is assigned to it and this number is are specified using a declaration statement. The size of each affixed to every variable declared in that block, thus making dimension of the array is specified using an allocation them different from other variables with the same name but statement. Until now, all the examples of the allocation declared in different blocks. The following rewritten version of statement used constants to specify the array size. However, the the previous program illustrates this concept. BNF definition of the allocation statement shows that the size specification is not restricted to a constant, but can indeed be ┌------------------------------┐ any expression. | DECLARE a000 FIXED; | | a000 = 2; | <allocation statement> ::= ALLOCATE <allocation list>; | BEGIN; | <allocation list> ::= <allocation element> | DECLARE (a001,b001) FIXED;| | <allocation list> , <allocation element> | a001 = 1; b001 = 2; | <allocation element> ::= <identifier> (<bounds list>) | OUTPUT = a001; | <bounds list> ::= <bounds> | <bounds list> , <bounds> | END; | <bounds> ::= <expression> | <expression> : <expression> | OUTPUT = a000; | └------------------------------┘ This section illustrates how one can utilize the added generality to write effective programs. Therefore, in the original program, the name 'a' refers to two different entities when used in the inner block and the outer If we are writing a program to look-up telephone numbers, block. we would not always know the size of the directory. The size will vary from day to day and from city to city. If the bounds With respect to the inner block the name 'a' occurs both as of the allocate statement for the array 'directory' were a a local variable and a global variable. When the statement 'a = constant, one would have to modify the program each time the 1;' appears in the inner block the local variable 'a' has directory changed or else make a directory so large that any precedence over the global 'a'. Thus, from the inner block there city could use it without modification. Then a city like Lone exists no other 'a' but the one declared within. Pine, California, would need as large a computer (memory) as Los Angeles. This suggests the desirability of having the size of The value of the global variable 'a' is not lost upon entry the array as an expression. into the inner block, but merely becomes inaccessible for use 1 4964 5052 61 The allocation statement is a command to set aside storage To a casual observer the need for a new block may not be for an array according to the bounds. If the bounds are constant obvious. In ALGOL 60 the declaration of an array is coupled with then the amount of storage allocated remains constant in every allocation of storage for the array, and appears together as in use of the program. If the bounds is an expression (whose value 'INTEGER ARRAY a [2 * k + 3, k]'. The definition of ALGOL 60 may be different each time the program is used) then the amount requires that all declaration statements precede all executable of storage allocated is equal to the value specified by the statements of the block. However, before the storage can be expression. This value can be dependent on data supplied to the allocated 'k' must be defined. For 'k' to be defined this program at the time of execution. declaration must follow an assignment statement. This conflict is resolved by introducing a new level of block structure. To allocate storage based on the value of an expression it is necessary that the values of the variable occurring in the Now you may ask the question why it is necessary in ALGOL expression be defined prior to the execution of the allocation 60 for all the declarations to precede all executable statement. A variable is defined if it previously appears on the statements. In a block, unless variables are declared before left hand side of an assignment statement. In the following they are used, it will not be possible to determine at the first program segment the size of the array 'a' will depend on the appearance of a name whether there is a conflict between a input data. If the input string started with a 2, then 'a' will global variable and a local variable with that same name, as have the dimensions 7 * 2, and if the input started with a 7, illustrated by the following program!: then the dimensions will be 17 * 7. ┌-------------------------------------------------------┐ ┌-----------------------------┐ | DECLARE a FIXED; | | DECLARE (k, a (*,*)) FIXED; | | a = 1; | | k = input; | | BEGIN; | | ALLOCATE a (2 * k + 3, k); | | a = 2; /* here we cannot tell which a is | | . | | intended */ | | . | | DECLARE a FIXED; | | . | | a = 3; | └-----------------------------┘ | END; | | output = a; | └-------------------------------------------------------┘ Historical Notes +________________ The solution adopted for ALGOL 60 was to require that the Many early programming languages like FORTRAN did not have programmer put all his declarations before any executable facilities for dynamic storage allocation. Thus one had to statements in the block. change the program and recompile or just waste a lot of storage by providing for the maximum possible array size. ALGOL 60 was One way PL/I (the parent language of PL) avoids the above the first major language to introduce dynamic storage requirement is by allowing declarations to appear anywhere in a allocation. However, dynamic declarations were complicated in block but specifying that they are executed first. Allowing ALGOL 60 by the requirement that all the declarations must declarations to appear anywhere in the block does not avoid the precede the executable statements in a block (or program). This need to introduce new blocks to declare dynamic arrays. means one had to start a new block just so that one can have dynamic declarations, as in the following program. There is another construct in PL/I, the allocation statement, which permits us to allocate storage based on the ┌--------------------------------------┐ value of an expression without starting a new block. You have | COMMENT Algol 60 program; | seen an example of its use at the beginning of this section. A | BEGIN; | declaration statement corresponding to the allocation statement, | INTEGER k; | specifying the dimensionality and the attributes, must also | k <-- insymbol; | appear within the block. The following pieces of program | BEGIN | illustrate the two ways of obtaining dynamic storage allocation | INTEGER ARRAY a[2 * k + 3, k]; | in PL/I. | S; | | S | | END | | END; | └--------------------------------------┘ Figure 3.11.1. An ALGOL 60 Program 1 5052 5139 62 ┌----------------------------┐ ┌---------------------------┐ 3.11.3. The Free Statement + __________________ | /* PL/I: OPTION 1 */ | | /* PL/I: OPTION 2 */ | | | | | We have seen how a BEGIN ... END block serves to release |DECLARE k FIXED; | |DECLARE (k,a(*,*)) FIXED; | the storage after it has served its purpose. Another way to |k = INPUT; | |k = INPUT; | release the storage used by a variable is by the use of the FREE |BEGIN; | |ALLOCATE a(2*k+3,k) FIXED; | statement. | DECLARE a(2*k+3,k) FIXED;| | . | | . | | . | <free statement> ::= FREE <free list>; | . | | . | <free list> ::= <identifier> | . | | . | | <free list> , <identifier> |END; | | | └----------------------------┘ └---------------------------┘ The free statement is the opposite of the allocate statement. It releases the storage occupied by the variables in Of the two options, the second one is more satisfactory. the variable list but it does not nullify the declaration, i.e., Not only does it avoid the need to introduce new blocks to the attributes of the variables are not lost. In contrast, upon declare dynamic arrays, but also separates the declaration of exit from a block not only the storage is released but also the attributes from the allocation of storage. This decoupling has declarations are nullified. The free statement requires explicit the advantage that a declaration statement then becomes a purely programmer specification of which storage should be released; descriptive statement without any execution significance. but upon exiting from a block, storage used by all the variables declared in a block is released automatically. A statement in PL/I may be either descriptive or executable Example of a FREE statement: or both. A declaration statement is an example where a statement can be part descriptive and part executable. By providing DECLARE cost (*) FLOAT, i FIXED; several different constructs which serve the same purpose, PL/I ALLOCATE cost (1951:1955); attempts to be moderately flexible. Too much flexibility can DO i = 1951 to 1955; result in unwieldy languages which defy attempts at concise cost (i) = INPUT; formal description leading to inefficient compilers, impossible END; manuals, and bewildered programmers. . . In PL, a statement can be either descriptive or executable . but not both. Thus a PL/I statement 'DECLARE a (k, 100) FIXED;' FREE cost; must be replaced by two equivalent PL statements 'DECLARE a(*,*) ALLOCATE cost (1956:1960); FIXED;' and 'ALLOCATE a (k,100);'. By this separation, we avoid . the need for starting a new block to declare dynamic arrays, . because the array size is always specified by the allocation . statement which is an executable statement. Exercise 3.11.3. PL does not require the separation of executable and What is the output of the following program if the input descriptive statements only to be able to declare dynamic data is: arrays. There are other pedagogical reasons for doing so. As a 3, result of the above separation, PL is more amenable to formal 40, 2, 4.26, manipulations than PL/I, has fewer basic concepts and restores 38, 0, 2.21, the aesthetically satisfying property of executing statements in 40, 0, /* THE PRESIDENT */ 11.46, the sequence in which they appear. 'RICK', 10, 'TAYLOR', 20, Declaration statements have no execution significance and 'GARRETT', IOU may appear anywhere in the block prior to the first use of the declared variables. It is a good programming practice to declare a variable before using it, just as it is a good practice to be introduced to someone before going out on a date with him. Otherwise the results might be just as unexpected. The allocation statement need not appear ahead of the first use of a variable but must be executed ahead of the first use of that variable. 1 5139 5230 63 ┌--------------------------------------------------------------┐ <procedure head> ::= <label definition> PROCEDURE; | DECLARE (i,j,joe) FIXED, wage(*) FLOAT; 1 | | <label definition> PROCEDURE <attribute list>; | i = 2; j = 7; joe = 2; 2 | | <label definition> PROCEDURE <formal parameters>; | BEGIN; 3 | | <label definition> PROCEDURE | DECLARE (i, k, hours(*), overtime(*)) FIXED; 4 | <formal parameters> <attribute list>; | k = INPUT; j = k; 5 | <formal parameters> ::= (<parameter list>) | ALLOCATE hours(k), overtime(k), wage(k); 6 | <parameter list> ::= <identifier> | DO i = 1 TO k; 7 | | <parameter list> , <identifier> | hours(*) = INPUT; overtime(i) = INPUT; 8 | <attribute list> ::= <attribute> | wages(i) = INPUT * (hours(i)+1.5 * overtime(i)); 9 | | <attribute list> <attribute> | hours(i) = hours(i) + overtime(i); 10 | <label definition> ::= <identifier>: | END; 11 | | OUTPUT = i || ' ' || j; /* the number i printed = k+1, 12 | The procedure body is given by the statement list, the | why? */ 13 | procedure name by the label definition, and the formal | IF wages (joe) < 600 THEN wages (joe) = 600; 14 | parameters in the parameter list. A procedure is invoked either | END; 15 | as a function (see Section 3.3.1) or in a call statement: | OUTPUT = i || ' ' || j; 16 | | BEGIN; 17 | <basic statement> ::= <call statement> | DECLARE k FIXED, total(*) FLOAT, name(*) CHARACTER| 18 | <call statement> ::= CALL <function designator>; | ALLOCATE total(j), name(j); 19 | <function designator> ::= <identifier> (<argument list>) | DO i = 1 TO j; 20 | | <identifier> | name(i) = INPUT; 21 | <argument list> ::= <argument> | total(i) = INPUT + wage(i); 22 | | <argument list> , <argument> | END; 23 | <argument> ::= <expression> | BEGIN; 24 | | DECLARE i FIXED; 25 | We associate a particular procedure definition with a | DO i = 1 TO j; 26 | particular procedure call by the name of the procedure (which | OUTPUT = name(i) || ' ' || wages(i) || ' ' 27 | appears in both). The argument list of the call and the formal | || total(i); 28 | parameter list of the definition must have the same number of | END; 29 | entries. At the time of call the arguments (if any) are | END; 30 | associated, one by one in order, with the formal parameters to | OUTPUT = i || ' ' || j; 31 | the procedure, and then the procedure body is executed. Upon | END; 32 | completion of the statements in the procedure body, control is | OUTPUT = i || ' ' || j; 33 | returned to the statement following the invoking call of the └--------------------------------------------------------------┘ procedure. Note that one procedure may call others, and so forth to an arbitrary depth. The novice may find this "hopping around" somewhat confusing at first. 3.12 PROCEDURES We will demonstrate the concept of a procedure by a series The most elaborate construct in PL is the procedure; it of changes to the "maximum" algorithm of Section 3.8.1: combines all of the features of the BEGIN ... END block with the ability to be invoked from many places within a program, and maximum = grade(1); with different parameters. A procedure constitutes a separate DO i = 2 TO 20; programmatic action which may modify variables elsewhere in the IF maximum < grade(i) THEN maximum = grade(i); program or compute and return a value, or both. Our use of the END; procedure construct may be a matter of style--to express, name, and set aside a part of a program--or it may be a matter of To procedurize this computation we merely need to turn it into a efficiency where we wish to avoid repeating a particular part of procedure body and then call it. the program, or it may be a necessity when an action is recursively defined (i.e., in terms of itself). A procedure definition is one form of a basic statement: <basic statement> ::= ... | <procedure definition> | ... <procedure definition> ::= <procedure head> <statement list> <ending>; 1 5230 5323 64 maximum_grade: procedure body. After entry the formal parameters act just like PROCEDURE; any other variable. maximum = grade(1); DO i = 2 TO 20; We now would like the procedure to work on any array IF maximum < grade(i) THEN maximum = grade(i); instead of just 'grade'. Thus we rewrite (and rename) it as END; follows: END maximum_grade; . general_maximum: . PROCEDURE (first, last, a) FLOAT; . DECLARE (first, last, i) FIXED, CALL maximum_grade; (a(*), maximum) FLOAT; maximum = a(first); The procedure definition itself has no effect during execution DO i = first + 1 TO last; and therefore may be placed in any convenient part of the IF maximum < a(i) THEN maximum = a(i); program before its call. Style usually demands that procedures END; be grouped together at the head of the program. Note also the RETURN maximum; typography: the label sticks out of the program for easy END general_maximum; visibility and the PROCEDURE...END pair are aligned one above the other to delineate clearly the scope of the procedure body and then the call: which is uniformly indented. Finally, note that the procedure name follows the matching END which permits the compiler itself maximum = general_maximum (1, 20, grade); to check that the intended PROCEDURE ... END match was indeed found (which it would not have been if, for instance, the other This will cause the procedure to search the array 'grade' and END had been erroneously omitted). return the maximum as a function value. Note in the procedure definition that we have specified a type of FLOAT for the The call has precisely the same effect as executing the procedure and have produced a value of type FLOAT via the return procedure body in its place would have had. Now, of course, we statement. If a type is specified for a procedure, a value must can reinvoke 'maximum_grade' at other places within the same be returned. program if the need arises. The parameter 'grade' exemplifies the single special case Perhaps we would like to have the maximum_grade action but for arguments. If the argument of a call is a <variable> and has be able to specify at each call which grades to examine. The exactly the same attributes as the formal parameter, then during definition and call: execution of the procedure body the formal parameter will be identical to the argument, i.e., any change made in the formal maximum_grade: parameter from within the procedure will also change the value PROCEDURE (first, last); on the outside. DECLARE (first, last) FIXED; maximum = grade (first); The final example above is an example of a 'pure DO i = first + 1 TO last; procedure'; that is, one which affects its environment only IF maximum < grade(i) THEN maximum = grade(i); through its parameters. If a procedure is not pure and affects END; the values of variables outside the procedure, it is said to END maximum_grade; have 'side effects'. Programming style generally favors pure . procedures since they are usually easier to understand. . . We will now tackle a somewhat more elaborate example. In CALL maximum_grade(1,20); expressions such as a + b * (c - d) have precisely the same effect as before but now we have the parentheses are necessary to indicate that the normal order provided the additional facility to search only part of the of operations is to be superseded. The program given below array 'grade' for a maximum as in: transforms such expressions into the notation of Lukasewich (so- called "Polish" notation), where the order of operations is CALL maximum_grade(10,15); explicitly defined requiring neither parentheses nor the hierarchy of operations. For example, the above expression would The effect of the arguments is to give an initial value of 10 become and 15 to the local variables 'first' and 'last' of the abcd-*+ 1 5323 5386 65 This can be understood as a sequence of values and operators DECLARE (text, c, Polish) CHARACTER, (t, p) ENTRY; read from left to right. Whenever an operator is reached, the scan: indicated operation is performed on the two values preceding it PROCEDURE; which then become a single value. Thus, this expression c = SUBSTR (text, 1, 1); indicates that we should subtract the value of 'd' from the text = SUBSTR (text, 2); value of 'c', multiply the result by 'b', and add that result to IF c = ' ' THEN CALL scan; /* deblank */ the value of 'a'. Similarly END scan; e: a + b * c - d yields abc*+d- PROCEDURE; /* expression */ (a - b) * c + d yields ab-c*d+ DECLARE op CHARACTER; CALL t; /* t1 */ DO WHILE c = '+' | c = '-'; op = c; CALL scan; CALL t; /* t2 */ Polish = Polish || op; END; END e; t: PROCEDURE; /* term */ DECLARE op CHARACTER; CALL p; /* p1 */ DO WHILE c = '*' | c = '/'; op = c; CALL scan; CALL p; /* p2 */ Polish = Polish || op; END; END t; p: PROCEDURE; /* primary */ IF c = '(' THEN DO; /* parenthesized expression */ CALL scan; CALL e; /* e1 */ END; ELSE Polish = Polish || c; CALL scan; END p; text = INPUT; OUTPUT = 'The expression is: ' || text; text = text || '??'; Polish = ''; CALL scan; CALL e; /* e2 */ OUTPUT = 'The Polish equivalent is: ' || Polish; The grammar of the input is: <E> ::= <E> + <T> | <E> - <T> | <T> <T> ::= <T> * <P> | <T> / <P> | <P> <P> ::= (<E>) | a | b | c | d ... and the grammar of the output is: <L> ::= <L> <L> <O> | a | b | c | d ... <O> ::= + | - | * | / 1 5386 5484 66 Exercise 3.12.1. ')??' 'd' 'abc' e '-' aft call scan Show that " 'd' 'abc' t t2 into t again 'a + b * (c - d)' is an <E> and " 'd' 'abc' p p1 and p ... 'abcd*-+' is an <L> " 'd' 'abcd' p bef call scan according to the grammars above. '??' ')' 'abcd' p aft call scan " ')' 'abcd' t homestretch Our problem is to trace through the actions of the " ')' 'abcd' e '-' out of t at procedures. We will use hand simulation with the following t2 table: " ')' 'abcd-' e '-' add saved '-' " ')' 'abcd-' p at e1 out of recursion text c Polish in op called comments '?' '?' 'abcd-' p aft call scan from " '?' 'abcd-' t '*' out of p at ---- - ------ -- -- ------ -------- p2 undef. undef. undef. - program start " '?' 'abcd-*' t '*' add saved '*' 'a+b*(c-d)' undef. undef. - after input " '?' 'abcd-*' e '+' out of t at 'a+b*(c-d)??' undef. " - pad t2 expression " '?' 'abcd-*+' e '+' add saved '+' '+b*(c-d)??' 'a' " - after first " '?' 'abcd-*+ - and out of e. scan " 'a' " e e2 after call e " 'a' " t t1 after call t Exercise 3.12.2. " 'a' " p p1 after call p Verify the hand simulation above, paying particular " 'a' 'a' p bef call scan attention to the two local variables named 'op'. 'b*(c-d)??' '+' 'a' p aft call scan " '+' 'a' t while fails, Exercise 3.12.3. out to t Hand simulate the algorithm for the expression '((a*b-c))' " '+' 'a' e '+' while works, to get 'ab*c-'. save '+' '*(c-d)??' 'b' 'a' e '+' aft call scan Exercise 3.12.4. " 'b' 'a' t t2 in t again Run the algorithm on the computer, adding enough output to " 'b' 'a' p p1 in p again verify the hand simulation. " 'b' 'ab' p bef call scan '(c-d)??' '*' 'ab' p aft call scan Exercise 3.12.5. " '*' 'ab' t out of p at Extend the algorithm to handle the prefix '+' and '-'. /* p1 */ Assume the rules: " '*' 'ab' t '*' while works, <P> ::= +<P> | -<P> save '*' <L> ::= <L># 'c-d)??' '(' 'ab' t '*' after scan Prefix '+' may be discarded when detected, prefix '-' must " '(' 'ab' p p2 in p again be turned into '#' to avoid confusion with infix '-'. (Does '-d)??' 'c' 'ab' p is '(', after 'ab--' come from '-(a-b)' or 'a-(-b)'?) scan ... " 'c' 'ab' e e1 recursive Exercise 3.12.6. call on e Write a character-valued procedure with one character- " 'c' 'ab' t t1 recursive valued argument such that when a singular English noun is call on t given the result is the same noun in plural form. For " 'c' 'ab' p p1 recursive example, call on p plural ('mouse') = 'mice' " 'c' 'abc' p bef call scan plural ('house') = 'hice' 'd)??' '-' 'abc' p aft call scan " '-' 'abc' t out of p at Exercise 3.12.7. p1 The volume of an n-dimensional sphere, v(n), is given by " '-' 'abc' e out of t at the recursion (where 'r' is the radius of the sphere): t1 " '-' 'abc' e '-' save '-' 1 5484 5561 67 v = ((2*pi/n)*r**2)*v(n-2) ______________________ where | 1 2 | 3 | 4 | v(o) = 1 |-----| | | | v(1) = 2r | 5 | 6 | 7 8 | What are v(2) and v(3) according to the formula? Does it | | |---- | check with the area of a circle and volume of a sphere? | 9 10 | 11 12 | What are v(0) and v(1)? Write a recursive procedure | -----| | | 'volume' so that | 13 14 15 | 16 | OUTPUT = volume(n); |_______________|____| will print the volume of the n-sphere. with a starting and an ending box, say 1 and 16. Between Exercise 3.12.8. each pair of boxes either there is a direct connection or A simple substitution cipher replaces each letter in a there is not. We can represent this structure by message by some other letter. Write a procedure constructing a two-dimensional, bit-valued truth table called 'maze' for the set of numbered boxes, the subscripts encrypt: of each dimension corresponding to the sequence of boxes PROCEDURE (message, key) CHARACTER; from lowest to highest (e.g., a 16 by 16 array for this DECLARE (message, key) CHARACTER; example). . . DECLARE maze (*,*) BIT; . ALLOCATE maze (n**2, n**2); END encrypt; We set maze(i,j) to TRUE only if we can go directly from whose result is the same length as 'message' but with each the box numbered 'i' to the box numbered 'j'. Write a letter of the message replaced by finding the position of program to define a maze, solve it, then print the solution the letter in the 'key' and substituting the letter in the path as a sequence of integers. corresponding position in the English alphabet. Test it with some messages and keys. What happens if you try to Exercise 3.12.13. encrypt your key with itself? Can the same procedure be If, in the preceding exercise, we change the type of maze used to decrypt the message? to FIXED, we can compute a distance matrix (in steps) between all pairs of boxes. Resolve the problem using this Exercise 3.12.9. extra information. Which solution is more efficient? Redo the preceding exercise but, within the body of the (Recall Section 3.8.3.) procedure, after each letter is encrypted, change the key by Exercise 3.12.14. key = substr (key, 2) || substr (key, 1, 1); Divide and conquer sort-merge. A sort can be described recursively as sorting the first half, sorting the second Exercise 3.12.10. half, then merging the result. Write a procedure 'sort' Referring to the preceding exercises, we note that it is a using this algorithm. nuisance to create a 26 (or more) character key and nearly impossible to remember one. "Good" spies remember a key Exercise 3.12.15. phrase (such as "How are you") and construct a key by first Divide and conquer quadrature. A definite integral can be removing duplicate letters ('howareyu') and then appending described recursively as the integral of the left half plus the rest of the alphabet in order the integral of the right half of the interval, unless the ('howareyubcdfgijklmnpqstvxz'). Write a procedure interval is so small that the function value on the left 'new_key(key_phrase)' to do this for your favorite spy. times the interval width is a sufficiently accurate estimate of the integral over the interval. Write and test Exercise 3.12.11. a procedure using this algorithm. Write a character valued procedure 'reverse' which reverses its character string argument without using a DO or GO TO in its body. Now do it without using the built-in function LENGTH. Exercise 3.12.12. A maze can be thought of as a set of numbered boxes: 1 5561 5646 68 integral: Find some of the 31 errors in the following program: PROCEDURE (f, a, b, eps) FLOAT; DECLARE f ENTRY, (a, b, eps) FLOAT; DECLARE (FIXED, foxed, ohoh) FLOAT; . (11,i,2j) FIXED (*); . j = j = j = j; . IF j ^= j DO; j = j END; ELSE j ^= j: RETURN ...; CALL RANDOM ('george' + 7.06) END integral; THEN GO TO m; ELSE INPUT = INPUT + OUTPUT; Exercise 3.12.16. q : PROCEDURE (p,q,0.1)(*); The function parameter to 'integral' has itself a single DECLARE (p,q) FIXED ENTRY BIT; parameter of type FLOAT. Suppose, however, we wished to RETURN (q(*)). double integrate the function 1/SQRT(ABS(x)+ABS(y)) over END; p; the unit circle. The procedure CALL q (q,q,q(0,1,1)); f: PROCEDURE (x, y) FLOAT; 3.13 ARRAY ARITHMETIC IF x = 0 & y = 0 THEN RETURN 1.0E30; ELSE RETURN 1.0/SQRT(ABS(x) + ABS(y)); Expressions involve constants, variables, or function END f; designators as primary building blocks. If both the operands to an arithmetic operator are array-valued and of like dimension describes the function well enough but cannot be directly and size, then the result is an array where each element is the used. Suggest a solution not requiring changes in the result of the operation on the corresponding elements in the procedure integral. Hint: define a procedure g(x) = operands. For example: integral (h, -SQRT (1.0-x**2), SQRT (1.0-x**2), eps). DECLARE (a,b,c)(*) FIXED; Exercise 3.12.17. ALLOCATE a(5), b(5), c(5); Wolf Island is a 20 by 20 plot populated by rabbits, male DO i = 1 TO 5; wolves, and female wolves, all acting wild. In the a(i) = i; beginning a few of each kind of the inhabitants are b(i) = i*i; scattered about the island. Rabbits are rather stupid; at END; each time step they move with equal probability to one of c = a + b; the eight squares in their neighborhood (excepting as restricted by the coastline). 1/9 of the time they leaves 'c' with the values: therefore simply sit still. Each rabbit also has a probability of 0.2 of becoming two rabbits. Female wolves ____________________________________ also move randomly unless there is a rabbit on one of the | c(1) | c(2) | c(3) | c(4) | c(5) | eight neighboring squares in which case she gives chase. If |------┼------┼------┼------┼------| she and the rabbit end up on the same square, she eats it | 2 | 6 | 12 | 20 | 30 | and gains one "fat". Otherwise she loses 0.1 "fat". Zero- |______|______|______|______|______| fat wolves are dead. Male wolves are just like females unless there are no rabbits nearby but there is a female on The language feature corresponding to constant arrays is given one of the eight neighboring squares in which case he gives by the built-in function ROW. chase. If a male and female end up on the same square with c = ROW (2, 6, 12, 20, 30); no rabbits to eat, they produce an offspring with a random also leaves 'c' with the values as above. For several sex. dimensions, ROW takes more complex arguments. Program the ecological simulation suggested and watch the population counts over several time periods. DECLARE (b(*,*), c(*)) FIXED; ALLOCATE b(5,5), c(5); Exercise 3.12.18. c = ROW (1, 2, 3, 4, 5); The previous simulation is inherently unstable (Wolf Island b = ROW (c, ROW (0, 0, 0, 0, 0), c*c, c+c, c-c); is destined to be a desert). Add a hedgerow (an area forbidden to wolves) and observe the results. leaves 'b' with the values: Exercise 3.12.20. 1 5646 5724 69 __________________________ Test it by computing a matrix product | 1 | 2 | 3 | 4 | 5 | c(i,j) = summation k=1 to n a(i,k)*b(k,j). | 0 | 0 | 0 | 0 | 0 | | 1 | 4 | 9 | 16 | 25 | Exercise 3.13.2. | 1 | 4 | 6 | 8 | 10 | Write a procedure | 0 | 0 | 0 | 0 | 0 | |____|____|____|____|____| fixed_to_bit: PROCEDURE (n)(*) BIT; e.g., b(4,3) = 6, etc. DECLARE n FIXED; . Partial arrays can be specified by placing an asterisk in . the corresponding subscript. For example, . c = b(*,2); END fixed_to_bit; leaves 'c' with the new values which decodes an integer 'n' into the binary representation ____________________________________ 5(base 10) = 101(base 2) = TRUE, FALSE, TRUE. Hint: | c(1) | c(2) | c(3) | c(4) | c(5) | MOD(n,2) = 1 is TRUE and 5/2 = 2(base 10) = 10(base 2). |------|------|------|------|------| | 2 | 0 | 4 | 4 | 0 | When the array-valued operands fail to match in dimension |______|______|______|______|______| or type, a conversion is attempted to make them correspond. The general rule is that we attempt to avoid losing information. The from the second column of 'b'. most important case is where a simple constant and an array are b(*,3) = b(4,*); mixed. The constant is exploded into an array of identical would cause the new 'b' to be elements matching the other operand in size and dimension. __________________________ Thus the assignments | 1 | 2 | 1 | 4 | 5 | c = ROW (1,2,3); | 0 | 0 | 4 | 0 | 0 | c = c+1; | 1 | 4 | 6 | 16 | 25 | result in 'c' having the value | 1 | 4 | 8 | 8 | 10 | ROW (2,3,4). | 0 | 0 | 10 | 0 | 0 | A popular use is to initialize an array to zero |____|____|____|____|____| c = 0; or It is possible to return an array as the value of a procedure if c(*) = 0; the attribute (*) is applied to the procedure definition as well as a type. When an array (or a partial array) is passed as an Exercise 3.13.3. argument to a procedure, it may be either as an evaluated We want to do 900-digit integer arithmetic, but are limited parameter (thus the outside world is protected) or by to about 9 integer digits on the IBM System/360. We propose 'identifying' the argument and formal parameter when all to store 9 digits per word in arrays with 100 elements and attributes and sizes match. use procedures to do the arithmetic. We need 'plus(a,b)', 'minus(a)', 'times(a,b)', 'quotient(a,b)', and Exercise 3.13.1. 'remainder(a,b)'. We give 'plus' and 'minus' below: Write a procedure to compute and return the inner product of two arrays. inner_product: PROCEDURE (n, a, b) FLOAT; DECLARE n FIXED; (a,b)(*) FLOAT; . . . RETURN ...; END inner_product; 1 5724 5802 70 plus: /* go-moku referee */ PROCEDURE (a,b)(*) FIXED; catenate: DECLARE (a,b)(*) FIXED; PROCEDURE (a) CHARACTER; DECLARE i FIXED, carrying BIT; DECLARE (a(*), t) CHARACTER, i FIXED; carrying = TRUE; t = ''; DO WHILE carrying; DO i = 1 TO 19; carrying = FALSE; t = t || a(i); DO i = 1 TO 100; END; IF a(i)+b(i) > 1000000000 THEN RETURN t; DO; a(i) = a(i)-1000000000; END catenate; a(i+1) = a(i+1)+1; DECLARE playing BIT; carrying = TRUE; /* place player procedures here */ END; DECLARE board (*,*) CHARACTER; END; ALLOCATE board (19,19); END; board = ' '; /* empty board */ RETURN a+b; playing = TRUE; END plus; DO WHILE playing; CALL player1 ((board),i,j); minus: IF board (i,j) ^= '' THEN PROCEDURE (a)(*) FIXED; OUTPUT = 'illegal move by X'; RETURN - a; ELSE board (i,j) = 'X'; END minus; CALL player2 ((board),i,j); IF board (i,j) ^= '' THEN The procedure 'plus' works as written for positive numbers OUTPUT = 'illegal move by O'; that do not exceed 900 digits, but it does not always work ELSE board (i,j) = 'O'; for negative numbers. (Why?) Fix it by adding an ELSE. Is DO i = 1 TO 19; the assignment to the parameter 'a' dangerous? Implement OUTPUT = catenate (board (i,*)); one or more of the remaining procedures. END; OUTPUT, OUTPUT = ''; Exercise 3.13.4. END; In order to print the numbers we must do some editing. In particular, we may find that some elements of an array are Exercise 3.13.6. negative and some positive. Write a procedure 'longprint' Make up an interesting problem using array valued which will print the number in the form expressions and send it to the authors of this book. *ddd..........d. Exercise 3.13.5. Go-moku is played by two players on a 19 by 19 board. Each + _______ plays alternately with the objective of getting 5 in a row (as contrasted to 3 in a row in tic-tac-toe). Assume a board: DECLARE board (*,*) CHARACTER; ALLOCATE board (19,19); board = ' '; on which 'X' and 'O' can be placed. Write a procedure 'player1(board,i,j)' which analyzes the board, decides on its move and returns the position to be taken in 'i' and 'j'. Have a friend write a procedure 'player2'. Then place them in the head of the following program and watch the action. Either player can terminate the game by setting 'playing = FALSE;'. 1 5802 5901 71 CHAPTER V paragraphs we will illustrate error recovery by means of some examples. ERROR DECTECTION AND CORRECTION The error "undeclared identifier" is corrected by default attributes to the variables. All the identifiers that begin with 5.1 ERRORS DURING PROGRAM TRANSLATION letters 'i', 'j', 'k', 'l', 'm', or 'n' are given the default attribute FIXED and the rest are given the default attribute Errors that occur during program translation usually result FLOAT. Thus the program in Figure 5.1.3 translates and computes from failing to state the algorithm in a form acceptable to the the expected results. PL translator. The unacceptability may take one of many forms. Table 5.1.1 presents a few typical error messages that may ┌-------------------------------┐ result when part of the program is syntactically incorrect. | DECLARE (a,b) FIXED; | Table 5.1.2 presents some errors that result when the | a = INPUT; | interpretation of a name is inconsistent with an earlier | b = INPUT; | definition or usage. | average = (a+b)/2; | | OUTPUT = average; | ┌----------------------------------------------------------┐ └-------------------------------┘ | 1. Illegal symbol pair | Figure 5.1.3. Error recovery for | 2. Illegal character | undeclared identifiers | 3. Undeclared identifier | | 4. Incorrect case statement structure | Although such a program might provide the desired results, | 5. More than one decimal point in number | undeclared variables should be considered a poor programming └----------------------------------------------------------┘ practice. Table 5.1.1. Errors due to Syntactically Incorrect Statements Perhaps the most common syntactic error is the message "Illegal Symbol Pair". This error occurs when two (terminal or ┌----------------------------------------------------------┐ non-terminal) symbols which may never occur adjacent to one | 1. Non-executable statement appears in an illogical | another according to the syntax of the language appear as a pair | place | in a program. (Such an error is often caused simply by omission | 2. Duplicate attributes | of some word or symbol in a statement.) When this error occurs | 3. Conflicting attributes | the partial parse is given with the error message, and the | 4. Multiple declaration of an identifier | translator recovers by ignoring the statement which caused the | 5. Subscript not legal for this identifier | error. Figures 5.1.4 to 5.1.6 illustrate this type of error. | 6. Incorrect number of subscripts | | 7. The procedure ---- cannot be used as a function | ┌--------------------------------------------------------------┐ | 8. The function procedure ---- cannot be used in a call | |STUDENT PL | | statement | | | | 9. In a function procedure RETURN must be followed by | | DECLARE (a, b) FLOAT, i FIXED; 1 | | an expression | | DO i = 1 TO 5; 2 | |10. In a non-function procedure RETURN may not be | | a = INPUT; 3 | | followed by an expression | | b = INPUT; 4 | └----------------------------------------------------------┘ | OUTPUT = SQRT (a+b) 5 | Table 5.1.2. Errors due to Inconsistent Programming | END; 6 | | | | |*** ERROR, ILLEGAL SYMBOL PAIR --------------- ) END | 5.1.1 Error Recovery by the Translator |PARTIAL PARSE IS: <STATEMENT LIST> <GROUP HEAD> | + ________________________________ | <STATEMENT LIST> <VARIABLE> = <IDENTIFIER> (<SUBSCRIPT LIST>)| When an error occurs during the translation of a program, | | the translator is usually able to proceed with the translation |END OF COMPILATION. | and execution unless the errors detected were severe. In most |ONE SEVERE ERROR WAS DETECTED. | cases an attempt is made to correct the error. If the error | | cannot be corrected, that part of the program which is in error |*** EXECUTION HAS BEEN SUPPRESSED | is ignored and the translation proceeds. If the error is severe, └--------------------------------------------------------------┘ the translation is terminated. The errors given in Tables 5.1.1 Figure 5.1.4. Error caused by a missing semicolon and 5.1.2 belong to the former two categories. In the following 1 5901 5976 72 ┌--------------------------------------------------------------┐ ┌--------------------------------------------------------------┐ |STUDENT PL | |STUDENT PL | | | | | | DECLARE (old, new) FLOAT; 1 | | DECLARE a CHARACTER, (b, c) FIXED; 1 | | old = INPUT; 2 | | b = INPUT; 2 | | IF old>300 THEN 3 | | c = INPUT; 3 | | new = .75 old; 4 | | a = 'Occupants of offices '||b||' to '||c; 4 | | | | | OUTPUT = a; 5 | |*** ERROR, ILLEGAL SYMBOL PAIR ------ <CONSTANT> <IDENTIFIER>| | BEGIN 6 | |PARTIAL PARSE IS: <STATEMENT LIST> <IF CLAUSE> THEN | | OUTPUT = ''; 7 | | <VARIABLE> = <CONSTANT> | | | | | ELSE new = old; 5 | |*** ERROR, ILLEGAL SYMBOL PAIR --------- BEGIN <IDENTIFIER> | | OUTPUT = new; 6 | |PARTIAL PARSE IS: <STATEMENT LIST> BEGIN | | | | DECLARE (a, b) CHARACTER, i FIXED; 8 | |END OF COMPILATION. | | | | |ONE SEVERE ERROR WAS DETECTED. | |*** WARNING, MULTIPLE DECLARATION FOR: a | | | | | | |*** EXECUTION HAS BEEN SUPPRESSED | |*** WARNING, MULTIPLE DECLARATION FOR: b | └--------------------------------------------------------------┘ | | | Figure 5.1.5. Error caused by a missing operator |*** WARNING, CONFLICTING OR DUPLICATE ATTRIBUTES FOR: a | | | | Figure 5.1.6 illustrates how a number of spurious errors might |*** WARNING, CONFLICTING OR DUPLICATE ATTRIBUTES FOR: b | result from a single error. | DO i = 1 TO 5; 9 | | a = INPUT; 10 | | b = INPUT; 11 | | OUTPUT = a||' '||b; 12 | | END; 13 | | END; 14 | | | | |*** ERROR, IMPOSSIBLE TO CONTINUE PARSE OF PROGRAM | |INPUT SYMBOL IS: ; | |PARTIAL PARSE IS: <STATEMENT LIST> <ENDING> | | OUTPUT = 'End list of occupants of '||b||' to '||c; 15 | | /* DATA: 111 151 '111' 'Myers' '123B' 16 | | 'Charnow' '134' 'Breckenridge' '141' 17 | | 'McDonald' '151' 'Jenkins' */ 18 | | | |END OF COMPILATION. | |6 ERRORS (2 SEVERE) WERE DETECTED. | | | |*** EXECUTION HAS BEEN SUPPRESSED | └--------------------------------------------------------------┘ Figure 5.1.6. Cascading of Errors Resulting from Error Recovery Errors resulting from inconsistent programming are handled in various ways. With "multiple attributes" and "conflicting attributes" the first attribute is used. Incorrect use of subscripts or procedures results in an undefined value for that term. 5.1.2 Some Common Errors with Misleading Error Messages + _________________________________________________ Sometimes the nature of the error may be such that it is difficult for the translator to provide a meaningful error 1 5976 6073 73 message. Figures 5.1.7 and 5.1.8 illustrate some of these The following steps are useful in discovering the cause of errors. an obscure error. ┌--------------------------------------------------------------┐ 1. Look for the position of the vertical bar to determine the |STUDENT PL | symbol just scanned. In Figure 5.1.7 the last symbol scanned is | | 'THIS'. | DECLARE a CHARACTER; 1 | 2. Look at the partial parse. In Figure 5.1.7 the partial parse | a = 'Did you forget something? 2 | is | OUTPUT = 'This will never be printed.'; 3 | <statement list> <variable> = <constant> | | | This should suggest, to those readers who have diagrammed some |*** ERROR, ILLEGAL SYMBOL PAIR ------ <CONSTANT> <IDENTIFIER>| statements and programs, that the difficulty occurred after the |PARTIAL PARSE IS: <STATEMENT LIST> <VARIABLE> = <CONSTANT> | symbol 'This' followed the sequence | | <variable> = <constant>. |END OF COMPILATION. | 3. Look at the parse of the symbol pair that is causing the |ONE SEVERE ERROR WAS DETECTED. | trouble. In Figure 5.1.7 it is | | <constant> <identifier>. |*** EXECUTION HAS BEEN SUPPRESSED | This is not as it should be since there is no production in the └--------------------------------------------------------------┘ grammar of PL (see Section 2.3.2) in which a <constant> may be Figure 5.1.7. Missing Quotation Mark followed by an <identifier>. 4. Work backwards from the vertical bar to identify the strings ┌--------------------------------------------------------------┐ corresponding to the trouble-causing symbol pair. In Figure |STUDENT PL | 5.1.7 the syntax for an <identifier> should tell us that the | | corresponding string is 'This'. Then the ' quote character | DECLARE age FIXED, name CHARACTER; 1 | preceding the 'T' should signal us to look for a string | name = INPUT; 2 | constant. The beginning of the string constant is then found to | age = INPUT; 3 | be on the preceding line. At this point the error, namely the | IF age>14 THEN /* minimum age is 15. 4 | missing semicolon on line 2 should be obvious. | OUTPUT = name || ' is old enough.'; 5 | | | | |*** ERROR, ILLEGAL SYMBOL PAIR --------------- THEN EOF | 5.2 ERRORS DUE TO SYSTEM LIMITATIONS |PARTIAL PARSE IS: <STATEMENT LIST> <IF CLAUSE> THEN | | | Many of the errors of this type result from machine |END OF COMPILATION. | limitations, in particular the core memory available to |ONE SEVERE ERROR WAS DETECTED. | translate and execute PL programs. Memory limitations restrict | | the size of the tables used by the translator to keep track of |*** EXECUTION HAS BEEN SUPPRESSED | various identifiers, constants, blocks and procedures, labels, └--------------------------------------------------------------┘ number of cases in a case statement, and so on. The following Figure 5.1.8. Missing Comment Bracket table gives some common error messages of this type. In Figure 5.1.7 a missing quote mark on line 2 causes an ┌------------------------------------------------┐ illegal symbol pair through a complex interaction with the | 1. Program generates too much code | following statement. (How?) In Figure 5.1.8 a missing comment | 2. Too many character strings | bracket */ on line 4 causes the translator to read past the end | 3. Character string too long | of the program and the data in search of a closing bracket. | 4. Too many identifiers | ("EOF" means "end of file".) | 5. Too many constants | | 6. Too many blocks and procedures | | 7. Too many cases in a case statement | 5.1.3. Correction of Syntactic Errors | 8. Program segment too long | + ______________________________ | 9. Too many labels | Identification and correction of syntactic errors is simple |10. Compile stack overflow | and straightforward except in cases such as those illustrated in └------------------------------------------------┘ Section 5.1.2 when only the symptom is given and the cause must Table 5.2.1 Some Common Error Messages Due to be discovered by careful examination. In all cases error System Limitations messages are chosen to provide maximum information. 1 6073 6171 74 Translator limitations usually vary from machine to machine variable names, one should attempt to use block structure to depending on the memory space available. A typical student PL declare and release variables as required. If there are too many translator might have the following limitations: 24,000 bytes of cases in a case statement, one should attempt to use nested case code and character string space (approximately 8000 statements), statements or otherwise reduce the number of cases in the a maximum of 99 identifiers, 4095 constants, 20 forward label problem definition. references at a time, 19 blocks and procedures, and 99 cases in a case statement. A character string may not be longer than 4095 The following example illustrates a special case of characters. Integers cannot be represented to more than 8 correction of an error resulting from system limitations. Figure significant digits. The exponent part of real numbers cannot be 5.2.1 shows a program with an error "program too large for the outside the range -75 < x < 75. The mantissa part of a real compiler". (The code space was artificially reduced to generate number can only be stored to 7 digits of accuracy. (A real this error without using a large program.) number is usually represented in a computer in the form exponent ┌--------------------------------------------------------------┐ mantissa * base . | STUDENT PL | The mantissa is a normalized number, i.e., the first digit is | | non-zero, and the decimal point is in a prespecified position. | /* PALM */ 1 | The exponent is an integer-valued number. For the student PL | DECLARE (bl,fr,co,tr) CHARACTER, i FIXED; 2 | system on the IBM 360 the base is 16, the exponent has the range | bl = INPUT; 3 | -128 to +128, and the mantissa has 6 hexadecimal (base 16) | fr = INPUT; 4 | digits.) | co = INPUT; 5 | | tr = INPUT; 6 | | OUTPUT = ''; 7 | 5.2.1 Error Correction | OUTPUT = SUBSTR(bl,1,35)||'##'; 8 | + ________________ | OUTPUT = SUBSTR(bl,1,32)||SUBSTR(fr,1,4); 9 | Errors due to system limitations are perhaps the hardest to | OUTPUT = SUBSTR(bl,1,30)||SUBSTR(fr,1,4)||SUBSTR 10 | correct and usually require substantial reprogramming of the | (bl,1,10)||SUBSTR(fr,1,13); /* 4 */ 11 | problem. This is one instance in which the limitations of | OUTPUT = SUBSTR(bl,1,28)||SUBSTR(fr,1,5)|| 12 | computers become clearly noticeable. | SUBSTR(bl,1,8)||SUBSTR(fr,1,10); /* 5 */ 13 | | OUTPUT = SUBSTR(bl,1,27)||SUBSTR(fr,1,6)|| 14 | Programs written in PL are translated to a language | SUBSTR(bl,1,6)||SUBSTR(fr,1,10); /* 6 */ 15 | analogous to Polish machine language. To do this, the translator | OUTPUT = SUBSTR(bl,1,3)||SUBSTR(fr,1,10)|| 16 | has to keep track of the names and attributes of all the | SUBSTR(bl,1,13)||SUBSTR(fr,1,6)||SUBSTR 17 | variables, values of constants, and the structure of the program | (bl,1,5)||SUBSTR(fr,1,9); /* 7 */ 18 | being generated. This is done by means of tables. As the program | OUTPUT = ' '||SUBSTR(fr,1,15)||SUBSTR(bl,1,10)|| 19 | is being translated these tables might get filled leaving no | SUBSTR(fr,1,6)||SUBSTR(bl,1,4)||SUBSTR 20 | space for further entries. Most of the errors of Table 5.2.1 are | (fr,1,8); /* 8 */ 21 | of this type. | OUTPUT = SUBSTR(fr,1,19)||SUBSTR(bl,1,6)||SUBSTR 22 | | (fr,1,7)||SUBSTR(bl,1,3)||SUBSTR(fr,1,8); 23 | Errors due to the translator limitations may be corrected | OUTPUT = '#'||SUBSTR(bl,1,11)||SUBSTR(fr,1,9)|| 24 | in several ways. If a larger computer were available, the tables | SUBSTR(bl,1,4)||SUBSTR(fr,1,7)||' '||SUBSTR 25 | could be enlarged to accommodate the program. (This can only be | (fr,1,8); /* 10 */ 26 | done by a systems expert.) Another method would be to divide the | OUTPUT = SUBSTR(bl,1,14)||SUBSTR(fr,1,9)||' '|| 27 | main program into several subprograms each of which uses the | SUBSTR(fr,1,7)||' '||SUBSTR(fr,1,7); /* 11 */ 28 | results of the preceding program as input, performs part of the | OUTPUT = SUBSTR(bl,1,16)||SUBSTR(fr,1,8)||' '|| 29 | computation, and provides results for use by the following | SUBSTR(fr,1,14); /* 12 */ 30 | program. On computer systems with randomly accessible secondary | OUTPUT = SUBSTR(bl,1,18)||SUBSTR(fr,1,7)||' '|| 31 | storage, such as disk, drum, or bulk core, intermediate results | SUBSTR(fr,1,13); /* 13 */ 32 | could be stored and used from the secondary storage giving the | OUTPUT = SUBSTR(bl,1,4)||SUBSTR(fr,1,47); /* 14 */ 33 | illusion that all the subprograms are working together as a | OUTPUT = SUBSTR(bl,1,2)||SUBSTR(fr,1,53); /* 15 */ 34 | single program. A third method (the one most desirable for | OUTPUT = ' '||SUBSTR(fr,1,56); /* 16 */ 35 | students) is to reformulate the algorithm so that it will not | OUTPUT = SUBSTR(fr,1,4)||SUBSTR(bl,1,9)||SUBSTR 36 | exceed the limitations of the system. Unfortunately there is no | (fr,1,45); /* 17 */ 37 | standard technique for reformulation of algorithms. This usually | OUTPUT = '###'||SUBSTR(bl,1,13)||SUBSTR(fr,1,33) 38 | depends on the nature of the errors. A good rule of thumb is to | ||' '||SUBSTR(fr,1,9); /* 18 */ 39 | use less of that resource which is scarce. If there are too many | OUTPUT = '##'||SUBSTR(bl,1,16)||SUBSTR(fr,1,32) 40 | 1 6171 6252 75 | ||' '||SUBSTR(fr,1,8); /* 19 */ 41 | | OUTPUT = SUBSTR(bl,1,29)||SUBSTR(tr,1,6); /* 50 */ 96 | | OUTPUT = '#'||SUBSTR(bl,1,14)||SUBSTR(fr,1,36)|| 42 | | OUTPUT = SUBSTR(bl,1,28)||SUBSTR(tr,1,7); /* 51 */ 97 | | ' '||SUBSTR(fr,1,6); /* 20 */ 43 | | OUTPUT = SUBSTR(bl,1,27)||SUBSTR(tr,1,8); /* 52 */ 98 | | OUTPUT = SUBSTR(bl,1,13)||SUBSTR(fr,1,22)||' ' 44 | | OUTPUT = SUBSTR(bl,1,26)||SUBSTR(tr,1,9); /* 53 */ 99 | | ||SUBSTR(fr,1,13)||' '||SUBSTR(fr,1,5); 45 | | OUTPUT = SUBSTR(bl,1,25)||SUBSTR(tr,1,10);/* 54 */ 100 | | OUTPUT = SUBSTR(bl,1,10)||SUBSTR(fr,1,13)||SUBSTR 46 | | OUTPUT = SUBSTR(bl,1,24)||SUBSTR(tr,1,12);/* 55 */ 101 | | (co,1,4)||SUBSTR(tr,1,8)||SUBSTR(bl,1,5)|| 47 | | 102 | | SUBSTR(fr,1,13)||' '||'###'; /* 22 */ 48 | | /* Data: ' ' 103 | | OUTPUT = SUBSTR(bl,1,9)||SUBSTR(fr,1,11)||' '|| 49 | | '####################################### 104 | | SUBSTR(co,1,7)||SUBSTR(tr,1,7)||SUBSTR(bl,1,6) 50 | | ###################' 105 | | ||SUBSTR(fr,1,12)||SUBSTR(bl,1,6)||'#';/* 23 */ 51 | | '$$$$$$$$' 106 | | OUTPUT = SUBSTR(bl,1,8)||SUBSTR(fr,1,11)||' '|| 52 | | '&&&&&&&&&&&&&&' */ 107 | | SUBSTR(co,1,8)||' '||SUBSTR(tr,1,7)||SUBSTR 53 | | | | | (bl,1,7)||SUBSTR(fr,1,11); /* 24 */ 54 | | *** ERROR, PROGRAM TOO LARGE FOR THE COMPILER | | OUTPUT = SUBSTR(bl,1,7)||SUBSTR(fr,1,10)||SUBSTR 55 | | *** COMPILATION ABANDONED DUE TO FATAL ERROR NOTED ABOVE | | (bl,1,4)||SUBSTR(co,1,6)||' '||SUBSTR(tr,1,7) 56 | | | | ||SUBSTR(bl,1,8)||SUBSTR(fr,1,10); /* 25 */ 57 | | END OF COMPILATION | | OUTPUT = SUBSTR(bl,1,7)||SUBSTR(fr,1,9)||SUBSTR 58 | | ONE SEVERE ERROR WAS DETECTED. | | (bl,1,6)||SUBSTR(co,1,4)||SUBSTR(bl,1,4)|| 59 | | | | SUBSTR(tr,1,6)||SUBSTR(bl,1,9)||SUBSTR(fr,1,9); 60 | | *** EXECUTION HAS BEEN SUPPRESSED | | OUTPUT = SUBSTR(bl,1,6)||SUBSTR(fr,1,9)||SUBSTR 61 | └______________________________________________________________┘ | (bl,1,15)||SUBSTR(tr,1,6)||SUBSTR(bl,1,10)|| 62 | Figure 5.2.1. Example of an error due to System Limitation. | SUBSTR(fr,1,8); /* 27 */ 63 | | OUTPUT = SUBSTR(bl,1,6)||SUBSTR(fr,1,8)||SUBSTR 64 | Figure 5.2.2 illustrates the correction of the error in | (bl,1,16)||SUBSTR(tr,1,7)||SUBSTR(bl,1,10)|| 65 | Figure 5.2.1 by using block structure to divide the program into | SUBSTR(fr,1,7); /* 28 */ 66 | two separate blocks. The code generated in each block is less | OUTPUT = SUBSTR(bl,1,6)||SUBSTR(fr,1,7)||SUBSTR 67 | than the maximum code space available, thereby eliminating the | (bl,1,18)||SUBSTR(tr,1,6)||SUBSTR(bl,1,11)|| 68 | error. | SUBSTR(fr,1,6); /* 29 */ 69 | | OUTPUT = SUBSTR(bl,1,6)||SUBSTR(fr,1,6)||SUBSTR 70 | | (bl,1,19)||SUBSTR(tr,1,6)||SUBSTR(bl,1,11)|| 71 | | SUBSTR(fr,1,5); /* 30 */ 72 | | OUTPUT = SUBSTR(bl,1,6)||SUBSTR(fr,1,5)||SUBSTR 73 | | (bl,1,21)||SUBSTR(tr,1,6)||SUBSTR(bl,1,11)|| 74 | | SUBSTR(fr,1,4); /* 31 */ 75 | | OUTPUT = SUBSTR(bl,1,6)||SUBSTR(fr,1,5)||SUBSTR 76 | | (bl,1,21)||SUBSTR(tr,1,6)||SUBSTR(bl,1,12)|| 77 | | '##'; /* 32 */ 78 | | OUTPUT = SUBSTR(bl,1,7)||'####'||SUBSTR(bl,1,22)|| 79 | | SUBSTR(tr,1,6)||SUBSTR(bl,1,11)||'#'; /* 33 */ 80 | | OUTPUT = SUBSTR(bl,1,8)||'###'||SUBSTR(bl,1,22)|| 81 | | SUBSTR(tr,1,6); /* 34 */ 82 | | OUTPUT = SUBSTR(bl,1,9)||'##'||SUBSTR(bl,1,22)|| 83 | | SUBSTR(tr,1,6); /* 35 */ 84 | | OUTPUT = SUBSTR(bl,1,10)||'##'||SUBSTR(bl,1,21)|| 85 | | SUBSTR(tr,1,6); /* 36 */ 86 | | OUTPUT = SUBSTR(bl,1,11)||'#'||SUBSTR(bl,1,21)|| 87 | | SUBSTR(tr,1,6); /* 37 */ 88 | | DO i = 38 TO 45; 89 | | OUTPUT = SUBSTR(bl,1,33)||SUBSTR(tr,1,6); 90 | | END; /* 38 - 45 */ 91 | | OUTPUT = SUBSTR(bl,1,32)||SUBSTR(tr,1,6); /* 46 */ 92 | | OUTPUT = SUBSTR(bl,1,31)||SUBSTR(tr,1,6); /* 47 */ 93 | | OUTPUT = SUBSTR(bl,1,30)||SUBSTR(tr,1,6); /* 48 */ 94 | | OUTPUT = SUBSTR(bl,1,30)||SUBSTR(tr,1,6); /* 49 */ 95 | 1 6252 6344 76 ┌--------------------------------------------------------------┐ | ## | | STUDENT PL | | #### | | | | #### ############# | | /* PALM */ 1 | | ##### ########## | | DECLARE (bl,fr,co,tr) CHARACTER, i FIXED; 2 | | ###### ########## | | bl = INPUT; 3 | | ########## ###### ######### | | fr = INPUT; 4 | | ############### ###### ######## | | co = INPUT; 5 | | ################### ####### ######## | | tr = INPUT; 6 | | # ######### ####### ######## | | BEGIN; 7 | | ######### ####### ####### | | OUTPUT = ''; /* 1 */ 8 | | ######## ############## | | OUTPUT = SUBSTR(bl,1,35)||'##'; /* 2 */ 9 | | ####### ############# | | . | | ############################################### | | . | | ##################################################### | | . | | ######################################################## | | OUTPUT = SUBSTR(bl,1,7)||'####'||SUBSTR(bl,1,22)|| 80 | | #### ############################################# | | SUBSTR(tr,1,6)||SUBSTR(bl,1,11)||'#'; /* 33 */ 81 | | ### ################################# ######### | | END; 82 | | ## ################################ ######## | | BEGIN; 83 | | # #################################### ###### | | OUTPUT = SUBSTR(bl,1,8)||'###'||SUBSTR(bl,1,22)|| 84 | | ###################### ############# ##### | | SUBSTR(tr,1,6); /* 34 */ 85 | | #############$$$$&&&&&&&& ############# ### | | . | | ########### $$$$$$$&&&&&&& ############ # | | . | | ########### $$$$$$$$ &&&&&&& ########### | | . | | ########## $$$$$$ &&&&&&& ########## | | OUTPUT = SUBSTR(bl,1,25)||SUBSTR(tr,1,10);/* 54 */ 103 | | ######### $$$$ &&&&&& ######### | | OUTPUT = SUBSTR(bl,1,24)||SUBSTR(tr,1,12);/* 55 */ 104 | | ######### &&&&&& ######## | | END; 105 | | ######## &&&&&&& ####### | | 106 | | ####### &&&&&& ###### | | /* Data: ' ' 107 | | ###### &&&&&& ##### | | '####################################### 108 | | ##### &&&&&& #### | | ###################' 109 | | ##### &&&&&& ## | | '$$$$$$$$' 110 | | #### &&&&&& # | | '&&&&&&&&&&&&&&' */ 111 | | ### &&&&&& | | | | ## &&&&&& | | END OF COMPILATION. | | ## &&&&&& | | NO ERRORS WERE DETECTED. | | # &&&&&& | | &&&&&& | | &&&&&& | | &&&&&& | | &&&&&& | | &&&&&& | | &&&&&& | | &&&&&& | | &&&&&& | | &&&&&& | | &&&&&& | | &&&&&& | | &&&&&& | | &&&&&& | | &&&&&&& | | &&&&&&&& | | &&&&&&&&& | | &&&&&&&&&& | | &&&&&&&&&&&& | | EXECUTION TERMINATED NORMALLY | 1 6344 6448 77 | END OF EXECUTION | |' ###### &&&&&& #####' | | NO ERRORS WERE DETECTED | |' ##### &&&&&& ####' | └--------------------------------------------------------------┘ |' ##### &&&&&& ##' | Figure 5.2.2. Correction of the Error by Using Block Structure |' #### &&&&&& #' | |' ### &&&&&&' | Figure 5.2.3 illustrates the correction of the error in |' ## &&&&&&' | Figure 5.2.1 by reformulation of the algorithm. A study of the |' ## &&&&&&' | program in Figure 5.2.1 will show that it is an attempt to |' # &&&&&&' | generate and print a picture of a tree. By making the |' &&&&&&' | information about the shape of the tree part of the data, the |' &&&&&&' | program is greatly simplified requiring only six statements. |' &&&&&&' | This figure shows the program and data before it is run. The |' &&&&&&' | print-out for it will be the same as in Figure 5.2.2. (In |' &&&&&&' | general, programs are written to solve a whole class of problems |' &&&&&&' | rather than a specific problem. Thus it is desirable to provide |' &&&&&&' | problem specific information as data for the program.) |' &&&&&&' | |' &&&&&&' | ┌--------------------------------------------------------------┐ |' &&&&&&' | |%PL | |' &&&&&&' | | DECLARE line CHARACTER; | |' &&&&&&' | | line = INPUT; | |' &&&&&&' | | DO WHILE line ^= ''; | |' &&&&&&&' | | OUTPUT = line; | |' &&&&&&&&' | | line = INPUT; | |' &&&&&&&&&' | | END; | |' &&&&&&&&&&' | | | |' &&&&&&&&&&&&' | |%DATA | |/* | |' ##' | └--------------------------------------------------------------┘ |' ####' | Figure 5.2.3. Correction of the Error by Reformulation of |' #### #############' | the Algorithm. |' ##### ##########' | |' ###### ##########' | |' ########## ###### #########' | 5.2.2 Additional System Errors + ________________________ |' ############### ###### ########' | |'################### ####### ########' | Occasionally, error messages appear which indicate that the |'# ######### ####### ########' | system is either confused or destroyed. These are more serious |' ######### ####### #######' | errors, and correction of them will probably require assistance |' ######## ##############' | from your instructor. Such errors are rare, however, and should |' ####### #############' | not occur in the final version of the translator. |' ###############################################' | |' #####################################################' | The message received with such errors is "System |' ########################################################' | interrupt". These interrupts are of many types, and an interrupt |'#### #############################################' | type (most of which are self-explanatory) will be printed with |'### ################################# #########' | the message. Table 5.2.2 lists some of these types. |'## ################################ ########'| |'# #################################### ######'| ┌--------------------------------------┐ |' ###################### ############# #####'| | System interrupt | |' #############$$$$&&&&&&&& ############# ###'| | 1. Illegal operation | |' ########### $$$$$$$&&&&&&& ############ #'| | 2. Addressing | |' ########### $$$$$$$$ &&&&&&& ###########' | | 3. Priviledged instruction | |' ########## $$$$$$ &&&&&&& ##########' | | 4. Memory protection | |' ######### $$$$ &&&&&& #########' | └--------------------------------------┘ |' ######### &&&&&& ########' | Table 5.2.2. Some System Interrupt |' ######## &&&&&&& #######' | Error Messages. |' ####### &&&&&& ######' | 1 6448 6552 78 5.3 ERRORS DURING PROGRAM EXECUTION undefined value". How would you correct this program? When the statements of a program are grammatically correct, ┌--------------------------------------------------------------┐ the translator returns the message "END OF COMPILATION" after | STUDENT PL | translating the last statement of the program and informs the | | interpreter to begin execution of the translated program. The | DECLARE i FIXED, sum FLOAT; 1 | interpreter program may be unable to execute certain commands of | DO i = 1 TO 4; 2 | the user program resulting in an execution-time (or run-time) | sum = sum + INPUT; 3 | error. These errors may be grouped into two categories: (a) | END; 4 | language and logic errors and (b) system errors. In this section | OUTPUT = sum; 5 | we will discuss the detection and correction of language and | | logic errors that occur during program execution. | END OF COMPILATION. | | NO ERRORS WERE DETECTED. | Some typical run-time errors are given in Table 5.3.1. | | | *** ERROR, ATTEMPT TO USE UNDEFINED VALUE | ┌----------------------------------------------------┐ | *** WHILE EXECUTING LINE: 3 OF THE PROGRAM | | 1. Attempt to use an undefined value | | | | 2. Attempt to read beyond end of data | | THE VALUES OF THE VARIABLES IN THE MAIN PROGRAM ARE: | | 3. Attempt to divide by zero | | i = 1 | | 4. Attempt to take a square root of a negative | | sum = UNDEFINED | | number | | | | 5. Subscript less than lower bound | | *** ERROR, ATTEMPT TO USE UNDEFINED VALUE | | 6. Subscript greater than upper bound | | *** WHILE EXECUTING LINE: 3 OF THE PROGRAM | | 7. Illegal input item | | *** ERROR, ATTEMPT TO USE UNDEFINED VALUE | | 8. Attempt to allocate -- with the wrong number | | *** WHILE EXECUTING LINE: 3 OF THE PROGRAM | | of dimensions | | *** ERROR, ATTEMPT TO USE UNDEFINED VALUE | | 9. Inappropriate Parameter types, e.g., | | *** WHILE EXECUTING LINE: 3 OF THE PROGRAM | | a. Actual parameter cannot be an array | | *** ERROR, ATTEMPT TO USE UNDEFINED VALUE | | b. Actual parameter requires illegal type | | *** WHILE EXECUTING LINE: 5 OF THE PROGRAM | | conversion | | *** ERROR, ATTEMPT TO USE UNDEFINED VALUE | | c. Actual parameter must be a function | | *** WHILE EXECUTING LINE: 5 OF THE PROGRAM | | procedure | | EXECUTION TERMINATED NORMALLY | | 10. Attempt to allocate a non-array | | | └----------------------------------------------------┘ | END OF EXECUTION. | Table 5.3.1. Some typical run-time errors | 6 ERRORS (6 SEVERE) WERE DETECTED | └--------------------------------------------------------------┘ The first time one of these errors occurs during the execution Figure 5.3.1. "Attempt to use an undefined value" of a program, the interpreter types out the values of all the variables which are either local or global to the block in which Note that the values of the variables are printed only once, the the error occurs. First, the values of all the local variables first time the error occurs. After that, each time around the are printed, then the values of the variables in the next loop and for the output, just the error indication is given. containing block, and so on. We shall see several instances of this type of diagnostic print-out in the following examples. A The program in Figure 5.3.2 provides an instance where an careful look at the values of the variables in conjunction with attempt to divide by zero results in two errors. The first error the error message is almost always sufficient to detect and is caused by attempting to divide 'k' (value 8) by 'j' (value correct the error. After printing the error message and the 0). This error makes the value of the expression 'k/j' values of the variables in the scope the system attempts to undefined. When an attempt is made to 'output' the undefined continue the execution of the program unless the nature of the value the second error results. error is such that it is impossible to do so (e.g., "Attempt to read beyond end of data"). The program in Figure 5.3.1 attempts to calculate the sum of 4 numbers. However, since the value of the variable 'sum' is not initialized to any value, use of 'sum' in an expression (line 3) results in an error message "Attempt to use an 1 6552 6655 79 ┌--------------------------------------------------------------┐ ┌--------------------------------------------------------------┐ | STUDENT PL | | STUDENT PL | | | | | | DECLARE (j, k) FLOAT; 1 | | | | k = INPUT; 2 | | DECLARE (a, b) FIXED; 1 | | j = INPUT; 3 | | a = 0; 2 | | DO WHILE k<10; 4 | | b = 20; 3 | | OUTPUT = k/j; 5 | | DO WHILE a+b<100; 4 | | k = k+1; 6 | | a = a + INPUT; 5 | | j = j-1; 7 | | b = b-1; 6 | | END; 8 | | END; 7 | | /* DATA: 2 6 */ 9 | | OUTPUT = a; 8 | | | | OUTPUT = b; 9 | | END OF COMPILATION. | | /* DATA: 20 17 8 3 14 12 */ 10 | | NO ERRORS WERE DETECTED. | | | | | | END OF COMPILATION. | | 0.333333 | | NO ERRORS WERE DETECTED. | | 0.600000 | | | | 1.00000 | | *** WARNING, ATTEMPT TO READ BEYOND END OF DATA | | 1.66667 | | *** WHILE EXECUTING LINE: 5 OF THE PROGRAM | | 3.00000 | | | | 7.00000 | | END OF EXECUTION. | | *** ERROR, ATTEMPT TO DIVIDE BY ZERO | | 1 ERROR WAS DETECTED | | *** WHILE EXECUTING LINE: 5 OF THE PROGRAM | └--------------------------------------------------------------┘ | | Figure 5.3.3 "Attempt to read beyond the end of data" | THE VALUES OF THE VARIABLES IN THE MAIN PROGRAM ARE: | | j = 0.00000 | By far the most common, and usually unanticipated error is | k = 8.00000 | caused by the use of an invalid subscript in array addressing. | | When the subscript value is less than the lower bound or greater | *** ERROR, ATTEMPT TO USE UNDEFINED VALUE | than the upper bound assigned during array allocation the | *** WHILE EXECUTING LINE: 5 OF THE PROGRAM | corresponding error message results. The program in Figure 5.3.4 | -9.00000 | illustrates this type of error. When a value of 10 (which is the | EXECUTION TERMINATED NORMALLY | upper bound) is read in for 'i', the expression 'i+1' in line 13 | | exceeds the maximum bound and causes the error. | END OF EXECUTION. | | 2 ERRORS (2 SEVERE) WERE DETECTED | ┌--------------------------------------------------------------┐ └--------------------------------------------------------------┘ |STUDENT PL | Figure 5.3.2. "Attempt to divide by zero" | | | DECLARE (a(*,*),ln,line) CHARACTER, (i,j) FIXED; 1 | The program in Figure 5.3.3 illustrates a programmer error | ALLOCATE a(10,10); 2 | leading to an improper termination of the program. The data used | a(*,*) = 'O'; 3 | by the program is given within the comment brackets on line 10. | i = INPUT; j = INPUT; 4 | Since the condition A + B >= 100 is not satisfied with the data | DO WHILE i ^= 99; 5 | given, an attempt is made to read the next card for more data. | a(i,j) = 'X'; 6 | In batch systems the next card is usually the first card of the | i = INPUT; j = INPUT; 7 | following program which is also an indicator for the operating | END; 8 | system to terminate the present program. | DO i = 1 TO 10; 9 | | DO j = 1 TO 10; 10 | | IF a(i,j) = 'X' THEN 11 | | DO; 12 | | IF a(i+1,j) ^= 'X' THEN a(i+1,j) = 'N'; 13 | | IF a(i-1,j) ^= 'X' THEN a(i-1,j) = 'N'; 14 | | END; 15 | | END; 16 | | END; 17 | 1 6655 6746 80 | /* print array */ 18 | Correction of various errors presented in this section is | DO j = 1 TO 10; 19 | usually straightforward and often represents a programmer error. | line = a(1,j); 20 | A careful look at the values of the variables is often | DO i = 2 TO 10; 21 | sufficient to discover the source of error. | ln = line || ' ' || a(i,j); 22 | | line = ln; 23 | | END; 24 | 5.4 RUN-TIME ERRORS DUE TO SYSTEM LIMITATIONS | OUTPUT = line; 25 | | END; 26 | In Section 5.2 we discussed the translator errors that can | /* DATA: 5 6 6 5 2 8 10 7 3 2 99 99 */ 27 | result from system limitations, and the difficulties involved in | | correcting for these errors. Run-time errors due to system |END OF COMPILATION. | limitations are usually just as hard to correct. Errors of this |NO ERRORS WERE DETECTED. | type represent either the limitations of the computer or the | | limitations of the interpreter program. Some typical error |*** ERROR, SUBSCRIPT GREATER THAN UPPER BOUND FOR THE ARRAY: a| messages of this type are given in Figure 5.4.1. |***SUBSCRIPT: 1 HAS THE VALUE: 11 WHILE THE UPPER BOUND IS: 10| |*** WHILE EXECUTING LINE: 13 OF THE PROGRAM | ┌----------------------------------------------------┐ | | | 1. Underflow | |THE VALUES OF THE VARIABLES IN THE MAIN PROGRAM ARE: | | 2. Overflow | | a(1,1) = 'O' | | 3. Result of concatenation exceeds maximum string | | a(1,2) = 'O' | | length | | . | | 4. Space requested for array allocation exceeds | | . | | available space | | (gives entire array) | | 5. Execution time exceeds maximum allowable time | | . | | 6. Too many actual parameters | | . | | 7. String space exhausted during input | | a(10,7) = 'X' | | 8. Input character string too long | | a(10,8) = 'O' | └----------------------------------------------------┘ | a(10,9) = 'O' | Table 5.4.1. Typical run-time errors due to system | a(10,10) = 'O' | limitations | ln = UNDEFINED | | line = UNDEFINED | The program in Figure 5.4.2 illustrates how repeated | i = 10 | division of a non-zero number (in this case 1) by a larger | j = 7 | number can in a finite number of steps produce a quotient of | | zero leading to the error message of "underflow". |*** ERROR, ATTEMPT TO USE UNDEFINED VALUE | |*** WHILE EXECUTING LINE: 13 OF THE PROGRAM | |*** ERROR, ATTEMPT TO USE UNDEFINED VALUE | |*** WHILE EXECUTING LINE: 13 OF THE PROGRAM | | O O O O O O O O O O | | O N X N O O O O O O | | O O O O O O O O O O | | O O O O O O O O O O | | O O O O N X N O O O | | O O O N X N O O O O | | O O O O O O O O N X | | N X N O O O O O O O | | O O O O O O O O O O | | O O O O O O O O O O | |EXECUTION TERMINATED NORMALLY | | | |END OF EXECUTION. | |3 ERRORS (3 SEVERE) WERE DETECTED | └--------------------------------------------------------------┘ Figure 5.3.4. Invalid Subscript Error 1 6746 6818 81 ┌--------------------------------------------------------------┐ ┌--------------------------------------------------------------┐ | STUDENT PL | | STUDENT PL | | | | | | DECLARE i FIXED, a FLOAT; 1 | | DECLARE (q,z) FLOAT; 1 | | a = 1.0; 2 | | q = INPUT; 2 | | DO i = 1 TO 29; 3 | | z = q**35; 3 | | a = a/978; 4 | | OUTPUT = z; 4 | | END; 5 | | /* DATA: 723 */ 5 | | OUTPUT = a; 6 | | | | | | END OF COMPILATION. | | END OF COMPILATION. | | NO ERRORS WERE DETECTED. | | NO ERRORS WERE DETECTED. | | | | | | *** ERROR, SYSTEM INTERRUPT #12 | | *** ERROR, SYSTEM INTERRUPT #13 | | *** (FLOATING POINT EXPONENT OVERFLOW) | | *** (FLOATING POINT EXPONENT UNDERFLOW) | | *** WHILE EXECUTING LINE: 4 OF THE PROGRAM | | *** WHILE EXECUTING LINE: 5 OF THE PROGRAM | | | | | | THE VALUES OF THE VARIABLES IN THE MAIN PROGRAM ARE: | | THE VALUES OF THE VARIABLES IN THE MAIN PROGRAM ARE: | | q = 723.000 | | i = 27 | | z = UNDEFINED | | a = 1.78315E-78 | | | | | | *** EXECUTION TERMINATED DUE TO FATAL ERROR NOTED ABOVE. | | *** EXECUTION TERMINATED DUE TO FATAL ERROR NOTED ABOVE. | | | | | | END OF EXECUTION. | | END OF EXECUTION. | | 1 SEVERE ERROR WAS DETECTED | | 1 SEVERE ERROR WAS DETECTED | └--------------------------------------------------------------┘ └--------------------------------------------------------------┘ Figure 5.4.2 Overflow Error Figure 5.4.1. Underflow Error The program in Figure 5.4.2 is an example of the overflow Theoretically the quotient in Figure 5.4.1, while getting error illustrating the fact that numbers larger than a certain increasingly smaller, is not supposed to take the value zero in magnitude cannot be represented accurately in the computer and a finite number of steps. However, computer representations of can only be approximated by the largest number. numbers is of necessity limited to a finite subset of all the real numbers (usually a function of the number of bits in a The program in Figure 5.4.3 shows that strings larger than memory word). Thus, numbers smaller than a certain limit can 4095 characters in length cannot be handled in one only be approximated by zero. implementation of the PL language. Thus, during the twelvth time around the loop, the two 2048-character strings cannot be catenated since the result would be longer than the maximum allowable string length. 1 6818 6920 82 ┌--------------------------------------------------------------┐ million word core storage) results in the indicated error | STUDENT PL | message. | | | DECLARE i FIXED, line CHARACTER; 1 | ┌--------------------------------------------------------------┐ | line = '?'; 2 | | STUDENT PL | | DO i = 1 TO 13; 3 | | | | line = line||line; 4 | | DECLARE table (*,*) FIXED; 1 | | END; 5 | | ALLOCATE table (1000,1000); 2 | | OUTPUT = line; 6 | | table (105,678) = 7; 3 | | | | table (968,999) = 3; 4 | | END OF COMPILATION. | | | | NO ERRORS WERE DETECTED. | | END OF COMPILATION. | | | | NO ERRORS WERE DETECTED. | | *** ERROR, RESULT OF CONCATENATION EXCEEDS MAXIMUM STRING | | | | *** LENGTH | | *** ERROR, SPACE REQUESTED FOR ARRAY ALLOCATION EXCEEDS | | *** WHILE EXECUTING LINE: 4 OF THE PROGRAM | | *** AVAILABLE SPACE | | | | *** WHILE EXECUTING LINE: 3 OF THE PROGRAM | | THE VALUES OF THE VARIABLES IN THE MAIN PROGRAM ARE: | | | | i = 12 | | THE VALUES OF THE VARIABLES IN THE MAIN PROGRAM ARE: | | line = '???????????????????????????????????????????????? | | table = UNDEFINED | | ??????????????????????????????? . . . | | | | (2048 characters total) | | *** EXECUTION TERMINATED DUE TO FATAL ERROR NOTED ABOVE. | | . . . ?????????????????????????????????????????????? | | | | ????????????' | | END OF EXECUTION. | | | | 1 SEVERE ERROR WAS DETECTED | | FIRST OPERAND BEGINS ON NEXT LINE | | TOTAL EXECUTION TIME WAS 0:0:0.04. | | ???????????????????????????????????????????????????????????? | └--------------------------------------------------------------┘ | ??????????????????????????????? . . . | Figure 5.4.4 "Array allocation exceeds available space" | (2048 characters total) | | . . . ?????????????????????????????????????????????? | | ???????????????????????????????????????????????????????????? | 5.5 ERRORS IN PROBLEM SOLUTION | SECOND OPERAND STARTS ON NEXT LINE | | ???????????????????????????????????????????????????????????? | It is not uncommon for a program to be in error even though | ??????????????????????????????? . . . | the translation and execution may have terminated normally. | (2048 characters total) | Often the resulting output may bear no resemblance to the | . . . ?????????????????????????????????????????????? | expected output and occasionally there may be no output at all. | ???????????????????????????????????????????????????????????? | | *** ERROR, ATTEMPT TO USE UNDEFINED VALUE | There are many commonly used solutions to this problem. | *** WHILE EXECUTING LINE: 4 OF THE PROGRAM | Which one is used will depend on how obvious the error is and on | *** ERROR, ATTEMPT TO USE UNDEFINED VALUE | the ability of the programmer. Often the output itself is | *** WHILE EXECUTING LINE: 4 OF THE PROGRAM | sufficient to indicate the nature of the error and the required | *** ERROR, ATTEMPT TO USE UNDEFINED VALUE | correction. If not, the insertion of a few carefully chosen | *** WHILE EXECUTING LINE: 6 OF THE PROGRAM | output statements into the program will usually point out the | *** ERROR, ATTEMPT TO USE UNDEFINED VALUE | part of the program which is in error. If it is not obvious what | *** WHILE EXECUTING LINE: 6 OF THE PROGRAM | type of output statement to use, one can use the DUMP function | EXECUTION TERMINATED NORMALLY | to print out the values of all the variables within the scope of | | a given block. The following problem solution indicates how each | END OF EXECUTION. | of the above steps helps to reduce the mystery. | 5 ERRORS (5 SEVERE) WERE DETECTED | └--------------------------------------------------------------┘ The program in Figure 5.5.1a is intended to read in an Figure 5.4.3. String Length Limitation array and then search through it for a given number. Any attempt to allocate large arrays beyond the storage capacity of the computer results in an error message. In Figure 5.4.4, an attempt to allocate a 1000 by 1000 array (requiring a 1 6920 6978 83 ┌--------------------------------------------------------------┐ statement later on. We ought to concentrate on the main DO loop | STUDENT PL | then. An output of all the variables during each iteration would | | be clearly impractical, particularly if the array were very | DECLARE (n, i, q) FIXED, (a, b(*)) FLOAT, found BIT; 1 | large. A better place for an output statement would be following | n = INPUT; 2 | the DO loop, and since the source of the error is not known, we | ALLOCATE b(1:n); 3 | should get a list of the values of all the variables. This is | DO i = 1 TO n; 4 | most easily done with the use of the DUMP function as shown in | b(i) = INPUT; 5 | Figure 5.5.1b. | END; 6 | | a = INPUT; 7 | | i = 1; 8 | | found = FALSE; 9 | | DO q = 1 TO n; 10 | | IF b(i) = a THEN 11 | | DO; 12 | | q = n; 13 | | OUTPUT = 'b('||i||')'||' is equal to a'; 14 | | OUTPUT = 'The value of a is '||a; 15 | | found = TRUE; 16 | | END; 17 | | END; 18 | | IF found = FALSE THEN 19 | | OUTPUT = 'None of the elements of b is equal to a.'; 20 | | /* DATA: 10 6.21 5.70 9.33 8.10 18.70 14.0 21 | | 3.85 9.73 4.47 12.60 9.73 */ 22 | | | | END OF COMPILATION. | | NO ERRORS WERE DETECTED. | | | | None of the elements of b is equal to a. | | EXECUTION TERMINATED NORMALLY | | | | END OF EXECUTION. | | NO ERRORS WERE DETECTED | └--------------------------------------------------------------┘ Figure 5.5.1a. Program for array search The computer has identified no errors in this program, yet it has not performed the desired operation. The first step in attempting to discover what has gone wrong is to look at the output. One might assume that this output is a true statement of the situation and that the program had functioned as expected. But since the data is given here, we can clearly see that the value of 'a' (9.73) should be found in the eighth element of the array 'b'. The output should lead us to believe that either the values were not successfully assigned to the array 'b' or that, since 'found' is apparently still FALSE, something must have gone wrong in the main DO loop. The next thing to be done would be to insert OUTPUT statements into the program where they might help reveal the source of error. One could test the assignment of the array 'b' immediately following the INPUT loop, but if that were the error it would be easily identifiable if 'b' were used in an output 1 6978 7077 84 ┌--------------------------------------------------------------┐ A glance at the values of the variables reveals that the | STUDENT PL | error is caused by the fact that no provision is made for | | incrementing 'i' each time around the loop. The program is | DECLARE (n, i, q) FIXED, (a, b(*)) FLOAT, found BIT; 1 | easily corrected as in Figure 5.5.1c. | n = INPUT; 2 | | ALLOCATE b(1:n); 3 | ┌--------------------------------------------------------------┐ | DO i = 1 TO n; 4 | | STUDENT PL | | b(i) = INPUT; 5 | | | | END; 6 | | DECLARE (n, i, q) FIXED, (a, b(*)) FLOAT, found BIT; 1 | | a = INPUT; 7 | | n = INPUT; 2 | | i = 1; 8 | | ALLOCATE b(1:n); 3 | | found = FALSE; 9 | | DO i = 1 TO n; 4 | | DO q = 1 TO n; 10 | | b(i) = INPUT; 5 | | IF b(i) = a THEN 11 | | END; 6 | | DO; 12 | | a = INPUT; 7 | | q = n; 13 | | i = 1; 8 | | OUTPUT = 'b('||i||')'||' is equal to a'; 14 | | found = FALSE; 9 | | OUTPUT = 'The value of a is '||a; 15 | | DO q = 1 TO n; 10 | | found = TRUE; 16 | | IF b(i) = a THEN 11 | | END; 17 | | DO; 12 | | END; 18 | | q = n; 13 | | IF found = FALSE THEN 19 | | OUTPUT = 'b('||i||')'||' is equal to a'; 14 | | OUTPUT = 'None of the elements of b is equal to a.'; 20 | | OUTPUT = 'The value of a is '||a; 15 | | CALL DUMP; 21 | | found = TRUE; 16 | | /* DATA: 10 6.21 5.70 9.33 8.10 18.70 14.0 22 | | END; 17 | | 3.85 9.73 4.47 12.60 9.73 */ 23 | | i = i + 1; 18 | | | | END; 19 | | END OF COMPILATION. | | IF found = FALSE THEN 20 | | NO ERRORS WERE DETECTED. | | OUTPUT = 'None of the elements of b is equal to a.'; 21 | | | | /* DATA: 10 6.21 5.70 9.33 8.10 18.70 14.0 22 | | None of the elements of b is equal to a. | | 3.85 9.73 4.47 12.60 9.73 */ 23 | | | | | | THE VALUES OF THE VARIABLES IN THE MAIN PROGRAM ARE: | | END OF COMPILATION. | | n = 10 | | NO ERRORS WERE DETECTED. | | i = 1 | | | | q = 11 | | b(8) is equal to a | | a = 9.73000 | | The value of a is 9.73000 | | b(1) = 6.21000 | | EXECUTION TERMINATED NORMALLY | | b(2) = 5.70000 | | | | b(3) = 9.33000 | | END OF EXECUTION. | | b(4) = 8.10000 | | NO ERRORS WERE DETECTED | | b(5) = 18.7000 | └--------------------------------------------------------------┘ | b(6) = 14.0000 | Figure 5.5.1c. Corrected program | b(7) = 3.85000 | | b(8) = 9.73000 | | b(9) = 4.47000 | | b(10) = 12.6000 | | found = FALSE | | | | EXECUTION TERMINATED NORMALLY | | | | END OF EXECUTION. | | NO ERRORS WERE DETECTED | └--------------------------------------------------------------┘ Figure 5.5.1b. Program with DUMP function added 1 7077 7107 85 PL, A STUDENT PROGRAMMING LANGUAGE TABLE OF CONTENTS REFERENCE MANUAL Section 0. BNF Definition of Language Section 1. Basic Elements PL, a dialect of PL/I, is specifically designed for Section 2. Specification, Activation and Termination teaching beginning programming students. This system is a direct of Data Elements result of a Student Programming Language project initiated by Section 3. Data Processes Professors W. M. McKeeman and D. R. Reddy with a view to Section 4. Modification of a Data Element by a Process developing a language which is of minimal complexity yet rich in Section 5. Modification of a Process by a Data Element concepts, and a system which has good diagnostic aids and is or by Another Process inexpensive to use. Messrs. J. J. Horning, E. C. Nelson, and D. Section 6. Specification, Activation, and Termination B. Wortman helped in formulating a consistent and formally of Processes describable language. Mr. Nelson wrote an experimental compiler Appendix A. Keywords for PL and Mr. Wortman wrote the present PL Translator- Appendix B. Predefined Functions Interpreter for the IBM 360 on which this manual is based. Mr. Appendix C. PL Reference Syntax A. T. Cathcart and Mr. Lee Erman helped in preparing this manual. The research and development of this system was supported in part by the Stanford University Computation Center (Campus Facility). 1 7107 7160 86 Section 0 Section 1 BNF DEFINITION OF LANGUAGE BASIC ELEMENTS The syntax of the language is defined using the Backus Naur PL is an artificial language whose structure is very Form. Definitions in BNF are called productions and make use of rigidly defined. This section will describe the basic syntactic two kinds of symbols of the language. Symbols which are defined elements. somewhere in the language description are called non-terminal symbols; symbols whose definitions do not occur in the language description are called terminal symbols. Non-terminal symbols 1.1 SYMBOLS consist of a descriptive term enclosed in angular brackets, e.g., <decimal number>. Terminal symbols are not enclosed in The PL alphabet or character set is similar to the English brackets. In addition, BNF uses two connective symbols, "::=" alphabet. Its complete description in BNF is: and "|". "::=" is read "is defined as", "|" is read "or". Examples of definitions in BNF are: <character> ::= <letter>|<digit>|<special symbol> |<punctuation mark>|<blank> (1) <PROGRAM> ::= <STATEMENT LIST> <letter> ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V (2) <DIGIT> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |W|X|Y|Z (3) <IF CLAUSE> ::= IF <EXPRESSION>. |a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v |w|x|y|z |$|@|#|_ Note that in (3), the IF on the right-hand side is a terminal <digit> ::= 0|1|2|3|4|5|6|7|8|9 symbol of the language. The juxtaposition of two symbols as <special symbol> ::= +|-|*|/|>|<|^|&|<vertical bar> occurs in (3) indicates that in the structure of the symbol <punctuation mark> ::= .|,|:|;|(|)|' being defined, the constituent parts occur in the order in which <vertical bar> ::= | they are named in the definition. <blank> ::= 1.2 DATA ELEMENTS There are two basic modes of referring to data elements: constants and identifiers (names). 1.2.1 Constants + _________ A constant is a word of the language which is a name for the particular value it represents. There are four types of constants: <constant> ::= <fixed constant>|<float constant> |<character constant>|<bit constant> Fixed constants are the usual decimal notations for the positive integers and zero, which are their corresponding values: <fixed constant> ::= <digit string> <digit string> ::= <digit>|<digit string><digit> Note the recursive nature of the definition, allowing digit strings of any length. Note also that extra zeroes may precede the significant digits and that there is no provision for commas 1 7160 7241 87 or decimal points. Examples are: null string and has a length of zero. A null string is represented by two adjacent apostrophes. 0 Examples of character constants: 1 21 Name Value Length 0021 'ABC' ABC 3 2000000 'A_C' A_C 3 'A C' A C 3 Float constants differ from fixed constants in two ways: ' B' B 2 they include a decimal point, and they may include an indication ' ' 3 that the decimal value designated is to be multiplied by some 'A+C' A+C 3 power of ten to obtain the value of the constant. Syntactically, 'A' A 1 '' 0 <float constant> ::= <decimal number> 'NOW IS THE TIME.' NOW IS THE TIME. 16 |<decimal number>E<power of ten> 'I''M' I'M 3 <decimal number> ::= .<digit string> '''' ' 1 |<digit string>.<digit string> '''A''' 'A' 3 |<digit string>. <power of ten> ::= <digit string> Character constants are important in the processing of |+<digit string> text, such as preparing indexes. They are also used in numerical |-<digit string> programming to make printed output more readable. Float constants are the ordinary numbers used in scientific There are two bit constants, representing logical values: notation. Examples: <bit constant> ::= TRUE|FALSE .5 While the syntax permits arbitrarily large (or small) 0.5 values and arbitrarily long names for all but bit constants, 3.1416 machine storage limitations set practical limits on these .31416E1 attributes. Integers (fixed values) are limited to the range .0043 -2147483648 <= X <= 2147483647 0.0 and non-zero real numbers (float values) are restricted in 1. magnitude to the approximate range 1.3712E-12 5.4E-79 <= |X| <= 7.2E+75 . 6.02E+23 6.01E23 1.2.2 Identifiers + ___________ Character constants are strings of zero or more characters, viz.: Identifiers serve many purposes in PL. Their BNF description is: <character constant> ::= ''|'<character string>' <character string> ::= <character> <identifier> ::= <letter> |<character string><character> |<identifier><letter> |<character string>'' |<identifier><digit> The value of a character constant is simply a string of Identifiers may not contain blanks. The underscore (_), characters. The apostrophes used to separate the constant from called a break character, is used primarily in place of a blank. the text are not a part of its value. The length of a character Examples: constant is the number of characters in the string. Any machine- printable character may be used in a character constant. If an apostrophe is desired as a part of the value of the constant, something must be done to differentiate it from the apostrophes which delimit the string. A pair of consecutive apostrophes in the string represents a single apostrophe in the value stored by the machine. A string containing no characters is called the 1 7241 7303 88 x /*....*/ x1 Comments will be ignored in the execution of the program, but #lbs they contribute immeasurably to the understanding of a program, xyz especially a complicated one. It can be very frustrating to try seven to deduce the purpose and workings of a program with kinetic_energy insufficient comments -- even if the program is one's own. (For us$ programs running under the IBM 360 Operating System, the /* of where_am_i comments may not begin in column 1.) There are three uses of identifiers. Two of these are as Characters are always grouped in the longest possible reserved words, a special form of punctuation, and as predefined words. Although the triplet 'abc' could be recognized as three functions, standard operations without special symbols. These separate words -- 'a', 'b', and 'c' -- it is always read as a are summarized in the appendices. Reserved words may not be single word. Thus every identifier or constant must be followed redefined by the programmer; predefined functions should not be. by a special symbol, a punctuation mark, or a blank or comment. The third and main use of identifiers is as names for data Because successive lines of program text are treated as elements and processes. consecutive parts of a single sequence of characters, hyphens are not used to continue a word from one line to the next. Conversely, when a line ends with the end of a word, the next 1.2.3. Blanks and Comments line may have to begin with one or more blanks. + ___________________ Blanks have two purposes in PL programming. They are syntactically necessary between words, so that the computer can tell where one word begins and another leaves off. Blanks which are not required by the syntax -- i.e., more than one blank where one would do -- are ignored by the computer but are essential to writing a readable program. Proper programming procedure dictates the use of a clear paragraphing style in program text, for the convenience of both the programmer and anyone else who might want to read his program. A clear style is one which indicates clearly the algorithmic structure of the program. Statements are usually made one to a line, which means one to a card in punch-card programming. When this is done, it is easy to group conceptually related subjects by indenting them (say) three spaces as a group. For example: DO WHILE c ^= 0; IF a < b THEN DO; c = a; a = b; b = c; END; ELSE DO; a = b; b = c; END; END; Another way of introducing clarity to a program is by the use of frequent comments. A comment may be inserted parenthetically at any point in the program text where blanks may occur by surrounding it with the special symbol pairs, 1 7303 7383 89 Section 2 Activation is the process by which prespecified variables are made available for use (but with an undefined value). A non- SPECIFICATION, ACTIVATION AND TERMINATION OF DATA ELEMENTS subscripted variable is activated, during execution, at the beginning of the block in which it occurs (see 2.5 BLOCKS). A subscripted variable (or array) is activated, in a block, only 2.1 VARIABLES after the execution of an allocation statement to fix the bounds of the array: A variable is defined by the programmer; it is a name by which various values are temporarily known. Like constants, <allocation statement> ::= ALLOCATE <allocation list>; variables are of the four types FIXED, FLOAT, BIT, and <allocation list> ::= <allocation element> CHARACTER. |<allocation list> , <allocation element> <allocation element> ::= <identifier>(<bounds list>) <variable> ::= <identifier> <bounds list> ::= <bounds> |<identifier><subscript list> |<bounds list>,<bounds> <bounds> ::= <expression> A subscripted variable provides a means for selection of an |<expression>:<expression> element out of a set of elements referred to by the same name (not unlike A(i,j) in mathematics). For example, the statements DECLARE wow (*,*) FLOAT; 2.2 SPECIFICATION OF VARIABLES ALLOCATE wow (7,2:7); Before it may be used as a part of an expression, a specify a seven-by-six array of FLOAT variables. When a single variable must be specified. Specification of variables is bound is specified, as for the first bound in the above accomplished by means of the declaration statement: statement, a lower bound of 1 is implied. <declaration statement> ::= DECLARE <declaration list>; More than one allocation may be made for a single array. <declaration list> ::= <declaration element> Each allocation supercedes the previous one. All current values |<declaration list> , <declaration element> of the array are (temporarily) hidden at the time of re- <declaration element> ::= <declaration primary> allocation, even those that lie within the new bounds. |<declaration primary><attribute list> <declaration primary> ::= <identifier> | ( <declaration list> ) 2.4 TERMINATION OF VARIABLES <attribute list> ::= <attribute> |<attribute list><attribute> Termination is the process by which the most recent <attribute> ::= (<asterisk list>) activation of a variable is nullified. A non-subscripted |<type> variable is terminated at the end of the block (see 2.5) in |ENTRY which it occurs. An array may be terminated implicitly at the |LABEL end of the block or explicitly by the use of a FREE statement. <asterisk list> ::= * Upon termination of a variable, any other variable with the same |<asterisk list> , * name which became inaccessible or hidden (at the activation) <type> = BIT becomes accessible again. |FIXED |FLOAT <free statement> ::= FREE <free list>; |CHARACTER <free list> ::= <identifier> |<free list> , <identifier> Examples of declaration statements: The current allocation of the arrays named in the FREE list DECLARE a FIXED; is cancelled and the stored values corresponding to it are DECLARE b1 FLOAT, zzzgp CHARACTER; permanently lost. If, however, several allocations were made DECLARE (a,b,c) BIT; without freeing, then the last previous allocation becomes DECLARE ugh (*,*) FLOAT, zap (*) BIT, rat BIT; accessible again and the values it contained are restored. Example: 2.3 ACTIVATION OF SUBSCRIPTED VARIABLES 1 7383 7433 90 DECLARE (x(*),y(*)) FLOAT, a(*,*) FIXED; valid in the larger block. 'b' is terminated when the program ALLOCATE x(32),a(5,10); emerges from the subordinate block. . . The variable 'a', which is declared in the outer block, is <process> valid for all the subordinate blocks (global variable) and . therefore can be used in the inner block. It still retains the . value upon exiting from the inner block and can be printed by ALLOCATE x(10),y(2:20),a(5:15,6:10); the OUTPUT = A; statement. . . FREE a,y; . . The FREE statement in the above example nullifies the most recent activations of arrays 'a' and 'y'. This means values of the first activation of 'a' become available again; 'y' must have a new allocation to be useful; 'x' still retains the values of the second allocation. Loss of access through reallocation and freeing are both examples of termination of variables; one is temporary, the other is permanent. 2.5 BLOCKS The syntax for <block> is as follows: <block> ::= <block head><statement list><ending>; <block head> ::= BEGIN; <ending> ::= END |END <identifier> |<label definition><ending> Variables declared within a block, but outside any blocks subordinate to (contained within) it, are local in scope with respect to that block; that is, they are specified and available to be activated only during the execution of the block. Variables declared in a superior block are global in scope with respect to the first block, and are valid throughout it. For example, the program segment BEGIN; DECLARE a FIXED; BEGIN; DECLARE b FIXED; a = INPUT; b = a; END; OUTPUT = a; OUTPUT = b; /* THIS STATEMENT CAUSES AN ERROR MESSAGE */ END; will produce an error message, because the variable 'b' is not 1 7433 7514 91 Section 3 The length of a string is the number of characters it contains, and there is a predefined function of that name: DATA PROCESSES LENGTH('ABC') yields 3 LENGTH(' ') yields 3 3.1 OPERATIONS LENGTH('''') yields 1 LENGTH('') yields 0 3.1.1 Arithmetic operations + _____________________ The function SUBSTR enables the programmer to handle The simplest arithmetic operation is negation, denoted by substrings of character strings. (For example, 'ABC' is a the minus sign "-". For example, -6 denotes the application of substring of 'ZABCD'.) The value of the expression SUBSTR(c,n,m) the negation operation to the positive constant 6; its value is is the string of 'm' characters, beginning with the n-th -6. Addition and subtraction operations are indicated by "+" and character, of the string which is the value of the variable 'c'. "-" respectively. Multiplication, division, and exponentiation Example of a substring with three arguments: are indicated by "*", "/", and "**" respectively. Standard mathematical notations such as the horizontal bar for division, DECLARE (a,b) CHARACTER; superscription for exponentiation, the multiplication cross, and a = 'MY DOG HAS FLEAS'; the division sign are not available in PL. b = SUBSTR(a,5,4); Examples: OUTPUT = b; would produce the printed result 2*3 yields 2x3 OG H 2 Omitting the third argument as in SUBSTR(c,n) yields a substring 2/3 yields --- or 2 3 of 'c' beginning with the n-th character and continuing to the 3 end of the string. Thus, from the above example, 3 SUBSTR(a,5) yields OG HAS FLEAS 2**3 yields 2 SUBSTR(a,LENGTH(a)-7) yields AS FLEAS Care should be exercised in performing division with The function INDEX checks to see if one string is a integer operands. The value of the expression obtained is that substring of another, and, if so, where the first character of of the quotient without the remainder. Therefore, these are true the substring occurs in the larger string. The value of the statements: 2/5 yields 0; 26/12 yields 2; -5/3 yields ?? function is the number which denotes the position of the first character in the substring, unless no appropriate substring is Many of the predefined functions of PL are considered to be found, in which case the value of the function is zero. For arithmetic operations. They are summarized in Appendix B; some example, common ones are: INDEX('CHARLIE','CHA') yields 1 Name Notation Effect INDEX('A&B&C|D','B&C') yields 3 ---- -------- ------ INDEX('HUZAT','HUHU') yields 0 absolute value ABS(n) |n| INDEX('ABCABC', 'BC') yields 2 square root SQRT(x) square root of x natural logarithm LOG(x) log(e)x 3.1.3 Logic Operations + ________________ 3.1.2 Character-String Operations (Editing) There are three basic operations on BIT values. The + ____________________________________ simplest is inversion, denoted by the not sign "^". Its result The most important operation on character strings is is the BIT value which its single operand does not have. catenation (or concatenation), i.e., chaining together. The Conjunction, denoted by the ampersand "&" requires two operands operation symbol is two vertical bars: and gives the resultant value of TRUE only when both operands have the value TRUE; otherwise, the resultant value is FALSE. 'ABC'||'DEF' yields 'ABCDEF' Disjunction is denoted by the or sign, "|". Its result is FALSE 'AB '||'DEF' yields 'AB DEF' only when both operands are FALSE; otherwise, the result is 'AB'||'' yields 'AB' TRUE. Examples: 1 7514 7599 92 ^ TRUE yields FALSE 3.1.5 Overflow and Truncation + _______________________ TRUE & TRUE yields TRUE TRUE & FALSE yields FALSE The type of the result of an operation sets limits on the TRUE|FALSE yields TRUE value of that result; when the result should actually lie FALSE|FALSE yields FALSE outside the limits, an error condition or overflow is caused. Anytime the sum of two numbers (or difference, product, or 3.1.4 Relational Operations (Comparisons) quotient) exceeds in magnitude the maximum storeable value, an + __________________________________ overflow is caused. The computer does not complete the The relations are binary (two-operand) operations. The operation, but prints an error message. operations may be of various types, but the resultant value is always BIT type -- i.e., TRUE or FALSE. Operations on FLOAT type operands frequently produce results with more significant digits than the machine can store. Equality is denoted by the equal sign "=". The resultant (example: 300000.+.0004). When this situation occurs, the extra value is TRUE if the operands are equal, FALSE if they are not. digits are always deleted from the low-order end of the number Strings of unequal length are considered equal if the shorter (in the example, the truncated result would again be 300000.) No string can become equivalent to the longer string by being error message is given. padded with blanks on either end. Examples: Division of FIXED numbers produces both a quotient, which is stored as the resultant value, and a remainder, which is not 1 = 1 yields TRUE recorded and is therefore inaccessible. 1 = 2 yields FALSE 3.E0 = .3E1 yields TRUE Overflow also occurs with catenation whenever the result 3.E1 = .3E0 yields FALSE would exceed 4095 characters in length; it causes an error 'ABC' = 'ABC' yields TRUE message and the loss of the result. 'AB' = 'AB ' yields TRUE 'A_C' = 'A C' yields FALSE ' ' = '' yields TRUE 3.1.6 Conversion + __________ TRUE = FALSE yields FALSE The existence of four types of values in PL permits four The greater-than sign and the less-than sign denote the types of computation to be used, each appropriate to a corresponding relations. These comparisons are understood particular class of problems. On occasion, however, the algebraically for numerical operands, alphabetically for programmer may want to use the same information in more than one character operands. way. Consider the four constants: Examples: 2 2.0 '2' '2.0' 1 > 0 yields TRUE 0 < 1 yields TRUE They are of three different types, and the character constants 1 > -2 yields TRUE are not equivalent (i.e., '2' = '2.0' gives the result FALSE). 1.0 < -2.0 yields FALSE In general, none of the four may be freely substituted for any 3.E0 > .3E1 yields FALSE of the others. It is important -- and frequently essential -- 'A' < 'Z' yields TRUE that the right type of name be used each time a reference is ' ' < 'A' yields TRUE made to the value, since each is treated differently by the '' < ' ' yields FALSE computer. 'A' < 'AB' yields TRUE 'B' < 'AB' yields FALSE The four predefined functions FIXED, FLOAT, CHARACTER, and BIT allow the programmer to find the value of one type that most These three operations are combined with inversion and with closely corresponds to a value of another type. (Both the each other to produce five more useful operations, which are: compiler and the programmer must distinguish between the uses of "^<", "^>", "^=", ">=", "<=". Their meanings are, respectively, these names as types and as functions.) not less than, not greater than, not equal to, greater than or equal to, and less than or equal to. The resultant values are The function FIXED gives, for a FLOAT value, the greatest TRUE if the indicated relation between the operands holds; integer whose magnitude is no greater than the argument of the otherwise, the result is FALSE. function. If the absolute value is less than 1.0, it will always be truncated to 0. If the value is greater than the maximum 1 7599 7685 93 FIXED value, an error results. For BIT values of TRUE and FALSE |+<factor> the results are 1 and 0, respectively. |-<factor> <primary> ::= <constant> The function FLOAT gives a six-digit approximation to the |<variable> value of a FIXED operand; for BIT operands, TRUE becomes 1.0 and |(<expression>) FALSE becomes 0.0. <variable> ::= <identifier> |<identifier>(<subscript list>) The function BIT gives TRUE if a FIXED operand is not equal <subscript list> ::= <subscript> to zero, FALSE if it is. For a FLOAT operand 'v', it gives |<subscript list>,<subscript> BIT(FIXED(v)). <subscript> ::= <expression>|* The function CHARACTER gives the shortest character string In short, an expression is a sequence of constants and/or which satisfies the definition for constants of the same type, variable names, operators, and parentheses. The result of except that for FLOAT operands, the scale factor (i.e., the evaluating an expression may be reported as an answer, saved for E<power of ten> notation) is not used. further combination, and/or tested to control the course of further computation. The function E_FORMAT converts the operand to FLOAT, then to CHARACTER in scientific notation. Questions of operator precedence are solved according to the following table, with the lowest numbered level being If the wrong data type does appear as an operand, the resolved first: system will attempt to convert it to the appropriate type before performing the operation. Usually it will be able to convert Level Symbol FLOAT values to FIXED, FIXED and FLOAT to BIT, and all three to ----- ------ CHARACTER. If no conversion is possible, an error message will zeroeth parenthesized expressions are always evaluated be printed. The use of mixed operand types in a single operation before being used as operands. without explicit conversion is not encouraged and should be first prefix + and -, exponentiation: ** considered poor practice. second multiply and divide: *,/ third infix + and - fourth catenation: || 3.2 EXPRESSIONS fifth relationals: <, <=, =, >=, >, ^<, ^>, >= sixth not operator: ^ Expressions are rules to obtain values of different kinds seventh and operator: & and types; they are basic to any computational processes. The eighth or operator: | syntactical definition of <expression> is heavily recursive: <expression> ::= <logical factor> 3.2.1 String Expression + _________________ |<string expression><vertical bar><logical factor> <logical factor> ::= <logical secondary> An expression whose value is a character string is called a |<logical factor>&<logical secondary> string expression. The following assignment statements <logical secondary> ::= <logical primary> illustrate the use of some simple string expressions. | ^ <logical primary> <logical primary> ::= <string expression> DECLARE (name,address,city,zip) CHARACTER; |<string expression><relation><string expression> name = 'JOHN SMITH'; <relation> ::= < | > | = | <= | >= | ^< | ^> | ^= address = '52 CAMPUS DRIVE'; <string expression> ::= <arithmetic expression> city = 'STANFORD,CALIF.'; |<string expression>||<arithmetic expression> zip = '94305'; OUTPUT = city||'_'||zip; <arithmetic expression> ::= <term> |<arithmetic expression>+<term> Strings are used mostly for symbol manipulation, e.g., |<arithmetic expression>-<term> alphabetizing. They may also be used to make printed machine <term> ::= <factor> output more meaningful. |<term>*<factor> |<term>/<factor> <vertical bar> ::= | 3.2.2 Arithmetic Expressions + ______________________ <factor> ::= <primary> |<primary>**<factor> 1 7685 7767 94 An expression with a numerical value is called an a = ROW (1,2,3,4,5) arithmetic expression. We repeat part of the syntax for <arithmetic expression>: assigns the indicated values to the first five allocated elements of a one-dimensional array 'a'; if 'a' has more than <arithmetic expression> ::= <term> one dimension, the values are put into the first row. ROW may |<arithmetic expression>+<term> have any number of arguments, not exceeding the bounds allocated |<arithmetic expression>-<term> to the array to which the values are being assigned. ROW may <term> ::= <factor> also appear as an argument to itself, e.g., |<term>*<factor> |<term>/<factor> a = ROW(ROW(1,2,3),ROW(4,3,2),ROW(17,21,x*y)); <factor> ::= <primary> |<primary>**<factor> In this case, each appearance of ROW as an argument causes its |+<factor> own arguments to be inserted as the values of the next row of |-<factor> the array; the example above could be used to assign all values <primary> ::= <constant> to a 3 x 3 array. |<variable> |(<expression>) It is possible to use subarrays consisting of entire rows or columns, or both, of existing arrays. The notation for this The simplest arithmetic expressions are individual is constants and variables. Others are built up from these by means of the arithmetic operators. Examples: <identifier>(<subscript list>) where a+b**x*y <subscript list> ::= <subscript> b/a |<subscript list><subscript> -arthur <subscript> ::= <expression> +(-arthur) |* The first example might appear to be ambiguous; but These are expressions of the form remembering the prescribed order in which the operations are executed, we know that it will be evaluated as array (1,*,x) a+((b**x)*y) The appearance of an asterisk in the subscript list means that the values included in the expression range over the entire allocation of rows or columns corresponding to that dimension, 3.2.3 Logical Expressions subject to the restriction that only those elements are included + ___________________ which have subscripts equal to the included expressions in the Expressions with BIT (TRUE/FALSE) values are called logical positions in which those expressions occur. For example, a(1,*) expressions: and b(*,1) refer to the first column of array 'a' and the first row of array 'b', respectively. In an expression of the form <logical expression> ::= <string expression><relation> <string expression> b(*,1) = a(1,*); <relation> ::= < | = | > | <= | >= | ^< | ^> | ^= the values of the first row of 'a' are placed, in order, in the The value of a logical expression is determined by first column of 'b'. The respective allocations of the arrays evaluating the expressions on either side of the relation symbol concerned must coincide in statements of this type. and testing whether the relation holds. If it does hold, the total expression has the value TRUE; if it does not, the value To set a particular row or set of rows or columns to a is FALSE. particular value it is possible to write a(1,*) = <expression>; 3.2.4 Vector Valued Constants + _______________________ and the value of the expression will be assigned to all the There are two types of expressions which take the values of variables included in the range of the asterisk. To assign an entire arrays, rather than individual variables. The predefined entire array at once, it is permissible to write function ROW is one. The statement 1 7767 7808 95 a = <expression>; Section 4 with the result that every allocated element of 'a' is set to MODIFICATION OF A DATA ELEMENT BY A PROCESS the value of the expression. 4.1 THE ASSIGNMENT STATEMENT An assignment statement is a command to the computer to perform some operations on data and assign the result as the value of a variable. The syntactical definition is: <assignment statement> ::= <variable> = <expression>; |<variable>,<assignment statement> The expression on the right hand side of the "=" is evaluated and the result is stored in the variable. The previous value(s) of the variable(s) is (are) lost. For example, suppose we have made the following statements: DECLARE(A,B,C) FIXED; a = 1; b = 12; c = 2; the variables 'a', 'b', and 'c' now have associated values of 1, 12, and 2, respectively. These values are stored in the computer's memory, at locations which the system now associates with the respective names. From now on the variables 'a' 'b', and 'c' may be used in expressions in the program text, and the computer will automatically substitute the proper value. To change the value of the variable 'a', we could write a = b+3; The value of the expression on the right would be computed (b = 12; 12+3 = 15) and stored at the address associated with 'a'. The value 1, stored there previously, would be lost. More examples, with their results: b = a+c-3; /* 14+2-3 = 13; new value of 'b' is 14 */ a = a+1; /* 15+1 = 16; new value of 'a' is 16 */ c = c/2+b; /* 2/2 = 1; 1+14 = 15; new value of 'c' is 15 */ Note that a = a+1; , like all assignment statements, is a command and not a statement of algebraic equality. While a = b and b = a imply the same fact in algebra, the assignment statement a = b; commands the computer to replace the value of 'a' by that of 'b', and b = a; does the opposite. 4.2 INPUT/OUTPUT OPERATIONS PL contains special variables with the names INPUT and OUTPUT. These are used for communication between the programmer 1 7808 7880 96 and the machine. The statement the string of five characters beginning with the sixth character of 'c'. In assigning values to FIXED variables, these values are a = INPUT; converted automatically from CHARACTER to the corresponding FIXED values. assigns to the variable 'a' the value of the next data element available from the computer's input device (for example, the The same operation for FLOAT constants is more complicated, number punched on the next card in a stack read in through a but similar in principle. If the input string does not include a card reader). The statement decimal point, there may be some uncertainty over where it is to be placed. OUTPUT = a; Suppose we wanted to read in eight-character FLOAT numbers, causes the computer to print the value of the variable 'a' on and suppose we wanted to arrange the input so that every string the output device. of eight characters containing a decimal point is assigned with its corresponding FLOAT value and every string containing no It is not possible to assign a value to the variable INPUT; decimal point is read as if it had three significant digits i.e., INPUT may not appear on the left-hand side of an after the decimal point. We can accomplish this with the assignment statement. Similarly, OUTPUT may not appear on the following program segment: right-hand side. DECLARE c CHARACTER, a FLOAT; The type of the variable INPUT is the type of the next data c = INPUT; element available on the input device; suitable precautions IF INDEX (SUBSTR(c,1,8),'.') = 0 THEN should be made to avoid mixing data types in the assignment a = SUBSTR(c,1,5)||'.'||SUBSTR(c,6,3); statements. /* if no decimal point, insert one. */ ELSE As can be seen from the syntax, statements of the form a = SUBSTR(c,1,8); /* otherwise just perform appropriate type transfer. */ a,b,c = <expression>; (For definition of INDEX, see Section 3.2.2.) are permissible. This statement is equivalent to the series of statements Output can be formatted very simply. Suppose we have calculated the mean and median of a particular data set; and q = <expression>; that we want to print these values out, along with the largest | and smallest values in the data set. Suppose further that these ┌----------------┼----------------┐ four values are assigned to the variables 'mean', 'median', | | | 'large', and 'small' respectively; then the output commands a = q; b = q; c = q; might be made in this way: The assignment is considered to take place in parallel. PL does OUTPUT = ' RESULTS OF CALCULATIONS '; not have special provisions for formatted input and output, such OUTPUT = ' MEAN VALUE IS ' ||mean; as are found in PL/I, ALGOL, and FORTRAN. It is possible to OUTPUT = ' MEDIAN VALUE IS ' ||median; achieve the same effect, however, by treating input and output OUTPUT = ' LARGEST AND SMALLEST VALUES ARE ' ||large|| as character strings. For example, suppose we wanted to read ' AND '||small||' RESPECTIVELY' ; three five-digit integer constants from a data card. We would treat them as a single character constant in punching the card, e.g., '12345678901112'. We might then write the following program segment: DECLARE c CHARACTER, (f1,f2,f3) FIXED; c = INPUT; f1 = SUBSTR(c,1,5);/* VALUE Of f1 IS 12345 */ f2 = SUBSTR(c,6,5);/* VALUE Of f1 IS 67891 */ f3 = SUBSTR(c,11,5);/* VALUE Of f3 IS 01112 */ SUBSTR is a predefined function which selects substrings from character strings; the value of SUBSTR(c,6,5), for example, is 1 7880 7967 97 Section 5 This causes two data items to be read and their value to be printed if they are equal. If they are not equal, there is no MODIFICATION OF A PROCESS BY A DATA ELEMENT, OR BY ANOTHER output. PROCESS IF ... THEN ... ELSE ... specifies that when the value of the expression in the IF clause is TRUE, the statement following 5.1 PROGRAM: SEQUENTIAL EXECUTION THEN will be executed; otherwise the statement following ELSE will be executed. The syntactic definition of a program is, in part: Example: <program> ::= <statement list> a = INPUT; <statement list> ::= <statement> b = INPUT; |<statement list><statement> IF a = b THEN <statement> ::= <basic statement> OUTPUT = a; |<conditional statement> ELSE <basic statement> ::= <assignment statement> DO; |<go to statement> OUTPUT = a; |<return statement> OUTPUT = b; |<call statement> OUTPUT = ABS(a-b); |<declaration statement> END; |<block> |<group> This does the same thing as the preceding example, except that |<procedure definition> when 'a' does not equal 'b' both values are printed along with |<allocation statement> their absolute difference. When 'a' does equal 'b', the |<free statement> statement following ELSE is ignored. |<empty statement> |<label definition><basic statement> 5.3 REPETITION: GROUP STRUCTURE A program is usually executed sequentially, one statement at a time, in the order of the statement list. There are certain A group, like a block, is a collection of statements which commands, however, which cause the computer to skip or repeat is syntactically treated as a single basic statement. statements, or to choose between alternative statements Declaration statements are not meaningful within a group. The depending on whether or not a given condition is met. purpose of a group is to permit a statement or statements to be repeated a specified number of times, or to be treated as a single unit, or to select one process out of many possible 5.2 CONDITIONAL EXECUTION processes. <conditional statement> ::= <IF clause> THEN <statement> <group> ::= <group head><statement list><ending>; |<IF clause> THEN <basic statement> ELSE <statement> <group head> ::= <control clause>; |<label definition><conditional statement> <control clause> ::= <repetition control> <IF clause> ::= IF <expression> |<control clause><case selector> <case selector> ::= CASE <arithmetic expression> The expression in the IF clause should have a logical <repetition control> ::= <while list> value. The effect of an IF ... THEN ... statement is to cause |<iteration list> the statement following THEN to be executed only when the <while list> ::= DO expression in the IF clause has the value TRUE. Otherwise the |<while list><while clause> statement is skipped and normal sequential execution continues <while clause> ::= WHILE <expression> with the next statement in the program. <iteration list> ::= DO <variable> = <iteration element> Example: |<iteration list> , <iteration element> <iteration element> ::= <expression> a = INPUT; |<expression><incrementation contro b = INPUT; |<iteration element><while clause> IF a = b THEN <incrementation control> ::= TO <arithmetic expression> OUTPUT = a; |BY <arithmetic expression> |TO <arithmetic expression> BY 1 7967 8048 98 <arithmetic expression> The words TO and BY may be included to specify the limit |BY <arithmetic expression> TO for values of the iteration control variable and the size of the <arithmetic expression> increment to be used. Thus, the construction DO i = a TO b bY c; 5.3.1 The DO WHILE Statement . + ______________________ . In a group of the form DO WHILE ... END, the entire group . is executed repeatedly as long as the expression following WHILE END; has the logical value TRUE. For example, does the following: i = 0; j = 10; 1. Sets the value of 'i' equal to the value of 'a'. DO WHILE i < j; 2. If i <= b, executes the statements in the group, returns i = i+1; to the start; adds the value of 'c' to 'i'; repeats from j = j-1; step 2. END; 3. If i > b, skips to the first statement following END. would execute five times, then cause program execution to skip Example: to the first statement following END;. The mechanics of execution are: test i < j; if false, then skip to next statement DO i = 1 TO 100 BY 1; after END; if true, then increment 'i' and decrement 'j'; return OUTPUT = SQRT (FLOAT(i)); to the control clause after reading the ending; and start again. END; /* PRINTS SQUARE ROOTS OF FIRST 100 INTEGERS */ Another example: When the BY clause is omitted, it is assumed to be BY 1. x,a,c = 1; Reversal of the BY and TO clauses does not affect execution. It DO WHILE c ^= 0; is also possible to write, for example, x = a/c; c = INPUT; DO j = 1 BY j WHILE x > 0; END; . . This performs one dummy division, then reads in values for 'c' . and performs the indicated division until a value read in for x = INPUT; 'c' is zero, at which time it stops. . . . 5.3.2 The DO Statement with Iteration Control END; + _______________________________________ The construction where the increment is controlled but the precise number of steps necessary is not explicitly stated. Execution of the group DO i = a,b,c,16,5; will terminate when a value for 'x' of zero or less is read in . from the data. . . END; 5.3.3 The CASE Selector + _________________ commands that the group be executed five times; and that 'i' In a group of several statements, it is possible to choose take the values of the expressions 'a', 'b', 'c', 16, and 5 on just one statement to be executed (just as the IF ... THEN ... successive repetitions ELSE ... statement chooses one of two statements to be Another example: executed.) This is done with the DO CASE ... END construction. The statements in the group are considered to be numbered DO i = 1,2,3,4,5; sequentially from top to bottom; the value of the expression OUTPUT = SQRT (FLOAT(i)); following CASE is the number of the statement to be executed. END; /* CALCULATES SQUARE ROOT OF FiRST FiVE iNTEGERS */ Examples: 1 8048 8125 99 DO CASE i; the scope in which it is defined. A branch statement is OUTPUT = 'CASE 1'; meaningful only when the identifier appearing within it is a OUTPUT = 'CASE 2'; label. OUTPUT = 'CASE 3'; END; When a branch statement is encountered during normal sequential execution, it signifies that the next statement executed is to be the one with the specified label, and that 5.3.4 Combinations sequential execution is then to resume at the new location. + ____________ The CASE selector can be combined with any of the group Labels, like all other identifiers, are subject to the heads. Thus it is also possible to write constructions like: limitations of the scope of their declarations. A branch may not be made into a block or procedure from outside of it. The label DO i = 1 TO 100 WHILE i <= J; on a block is, of course, declared outside the block, so it is possible to branch to the head of a block. The label on a DO i = 1,2,3,4,5 WHILE X ^= Y; procedure block (i.e., the procedure name) cannot be used as the destination of a branch. A label global to a block may be used DO i = 2 BY 2 WHILE i*i < 150 CASE MOD(i,3)+1; to branch out of the block. OUTPUT = 'CASE 1'; OUTPUT = 'CASE 2'; A branch may be made to one statement of a group from OUTPUT = 'CASE 3'; outside the group only if the group head does not specify any END; repetition or selection. From within a group, it is always possible to branch out. Branches within a group are allowed (For a definition of the MOD function, see Appendix B.) except when the group head includes a CASE phrase. Finally, a branch may not be made to a consequence of a conditional, or The group execution will terminate when either the within one, unless the branch statement itself is inside the incrementation control or the while clause would cause it to do same statement. so if operating independently. For example: The last example of Section 5.3.4 may be written using a i = 1; branch statement. DO p = 1 BY 4 TO 21 WHILE i ^= 0; OUTPUT = p*i; i = 1; i = iNPUT; DO p = 1 BY 4 TO 21; END; OUTPUT = P*i; i = INPUT; This will perform five iterations, unless a value of 0 is read iF i = 0 THEN GO TO out; in for 'i' at any point. END; out: ... 5.4 SEQUENCE INTERRUPTION 5.4.2 Label Variables + _______________ 5.4.1 The GO TO Statement + ___________________ It is possible to declare variables whose values are the The GO TO (or branch) statement is used to transfer control same as those of labels, i.e., program points. They are declared permanently and unconditionally within a program. Its syntax is: in this manner: <GO TO statement> ::= GO TO <variable> ; <label declaration> ::= DECLARE <identifier> LABEL; |GOTO <variable> ; and called by: Any statement in a program may be preceded by one or more label definitions. GO TO <identifier>; <label definition> ::= <identifier> : They are assigned values by the usual assignment statement. An identifier used in this way is called a label for that particular statement, and may not be used anywhere else within 1 8125 8178 100 out: Section 6 . . PROCEDURES: SPECIFICATION, ACTIVATION, AND TERMINATION OF DECLARE exit LABEL; PROCESSES . . exit = out; 6.1 SPECIFICATION . . Programming frequently requires that some process be used GO TO exit; repeatedly at various points in a program. Such repetition is facilitated by the use of procedures. In this example, 'out' is the program point and 'exit' is a <procedure definition> ::= variable which takes on the value of the label 'out'. <procedure head><statement list><ending>; <procedure head> ::= <label definition> PROCEDURE; |<label definition> PROCEDURE <attribute list>; |<label definition> PROCEDURE <formal parameters>; |<label definition> PROCEDURE <formal parameters> <attribute list>; <formal parameters> ::= (<parameter list>) <parameter list> ::= <identifier> |<parameter list> , <identifier> A procedure definition constitutes only the specification of a process, represented by the statement list which constitutes the body of the procedure. These statements are not executed at the time of the definition. A procedure is activated by the appearance of its name in an appropriate statement in the program text. The name of a procedure is the identifier in the label definition at its head. The name is followed by the keyword PROCEDURE and two optional features: the formal parameter list and the result value type (these are optional in the sense that they may or may not appear, depending on the statements that follow in the definition, and on the purpose of the procedure.) Examples of procedure heads: figure_it_out: PROCEDURE; no_you_do_it: PROCEDURE FLOAT; i_will_not: PROCEDURE (par1, par2, par3, par4); yes_you_will: PROCEDURE (p1,p2) FIXED; The statement lists with procedures, like blocks, may contain declarations of local variables and may share variables with their containing block(s). The procedure name is local to the containing block. 6.2 ACTIVATION Execution of a procedure is begun when it is activated or called by a statement in the program text. At this time, storage is allocated for local variables as in any block. Local variables which appear in the formal parameters are assigned a 1 8178 8259 101 value determined from the activating statement. The execution of a procedure is terminated by the use of the RETURN statement. When the procedure definition includes a result type, (<attribute list> with the <procedure head>), the procedure is <return statement> ::= RETURN ; | RETURN <expression> ; treated like a predefined function -- the expression in which its name appears tells how the value is to be used. If a In a function procedure the return statement must include parameter list is included, the activating reference must be an expression which gives the value associated with the followed by a parenthesized argument list which gives meaning to function. The first execution of a return statement in a the corresponding formal parameters. Examples of function procedure terminates the procedure, including freeing local references: variables and cancelling the identification of formal parameters and arguments. median = middle (a,b,c); sum = p(x1,x2)+q(y1,y2); In a subroutine, the return statement consists of RETURN; only. This accomplishes the termination. Using the one-word Note that function references look just like array elements. return or no return in a function procedure, or returning a They can only be distinguished by referring to their respective value from a subroutine, results in an error. declarations. Examples of return statements: When a procedure is not a function, it does not return a RETURN; /* SUBROUTINES ONLY */ value and cannot be used meaningfully in an expression. Such a RETURN FLOAT; /* FUNCTION PROCEDURES ONLY */ procedure is activated by a call statement: RETURN 1; /* DITTO */ <call statement> ::= CALL <variable>; Example of a function procedure to calculate a weighted mean of four elements 'a', 'b', 'c', and 'd' whose weights are stored in A procedure which is activated in this way is termed a called a four-element array: procedure, or a subroutine. Examples of subroutine calls: cm: PROCEDURE (v1,v2,v3,v4,wt) FLOAT; CALL arthur(a,x,term1); DECLARE (v1,v2,v3,v4) FLOAT; CALL noarg; DECLARE wt(*) FLOAT; RETURN (v1*wt(1)+v2*wt(2)+v3*wt(3)+v4*wt(4))/4; Procedure arguments are matched up with their corresponding END; formal parameters. Arguments may be expressions or constants, in DECLARE (a,b,c,d,weight(*)) FIXED, mean FLOAT; which case the matching consists of assigning the values of the ALLOCATE weight(4); expressions or constants to the appropriate formal parameters, . or arguments may be the names of variables or arrays. If a . variable or array name is associated with a formal parameter, . and is of the same type, it becomes identical to that parameter /* assign values to a,b,c,d,weight */ while the procedure is executing. Not only are their initial mean = cm(a,b,c,d,weight); values identified, but values assigned to the formal parameter are also assigned to the corresponding argument. 6.4 RECURSION Note that an "array" is different from an "array element". An array element behaves just like an individual variable, and A procedure which calls itself either directly or may be assigned to a formal parameter which is a simple indirectly is called a recursive procedure. Each time a variable. An array can only be assigned to a formal parameter procedure is called while it is still activated, new allocations which is an array with the same number of dimensions. and assignments of local variables and parameters are made, and Allocations for array parameters are not normally made within a the old ones are set aside; when the new call is again de- procedure, since an allocation should already exist for the activated, the old assignments return to effect. It is important corresponding array argument in the calling block. Other locally to provide some method of returning without recursion, though, declared arrays must, of course, be allocated, and the procedure to prevent unlimited recursion. should free them after each execution. Two procedures declared with the same scope may call each other. 6.3 TERMINATION 1 8259 8290 102 Nesting of procedure definitions is permitted; procedures Appendix A: Reserved Words may be defined within other procedures, with appropriate scope restrictions. Example of recursive procedure calls: These identifiers have reserved meanings, which are the same in every program; they may not be defined by the factorial: PROCEDURE(m) FIXED; programmer. DECLARE m FIXED; . ALLOCATE FIXED . BEGIN FLOAT /* calculate m factorial */ BIT FREE IF m = 0 THEN RETURN 1; BY GO ELSE RETURN m*factorial(m-1); CALL GOTO END factorial; CASE IF . CHARACTER LABEL . DECLARE PROCEDURE . DO RETURN OUTPUT = factorial(12); ELSE THEN END TO ENTRY WHILE 1 8290 8357 103 Appendix B: Predefined Functions arguments MOD FIXED | FLOAT, FIXED or FLOAT remainder FIXED | FLOAT of division of the These identifiers have the indicated meanings: first argument by the second (Between mixed Name Argument(s) Value types, appropriate ---- ----------- ----- conversion is made.) ABS FIXED FIXED absolute value of RANDOM none FLOAT pseudo-random value argument between 0.0 and 1.0 FLOAT FLOAT absolute value of ROUND FLOAT | FIXED | BIT FIXED nearest to argument argument SIGN FIXED | FLOAT FIXED +1 if argument > 0 ATAN FLOAT (radians) FLOAT arctangent of FIXED 0 if argument = 0 argument FIXED -1 if argument < 0 BIT FIXED | FLOAT BIT value corresponding SIN FLOAT (radians) FLOAT sine of argument CHARACTER FIXED | FLOAT | BIT CHARACTER value ROW CHARACTER | BIT An array with the corresponding | FIXED | FLOAT arguments as array COS FLOAT (radians) FLOAT cosine of argument elements (See 3.2.4) DUMP none Value is undefined. Causes SQRT FLOAT >= 0.0 FLOAT square root of a print-out of current argument values of all SUBSTR CHARACTER,FIXED,FIXED CHARACTER substring of variables first argument, E_FORMAT FLOAT | FIXED | BIT CHARACTER equivalent in starting at character scientific notation numbered by second END_OF_DATA none TRUE if there is no more argument, and of data left to read length given by third before a control card, argument FALSE when more data TAN FLOAT (radians) FLOAT tangent of argument is available. If UNDEFINED Variable of any type TRUE if argument is tested when TRUE, it undefined; otherwise, is reset to FALSE and FALSE. the data following the control card is made available. If there is no more data to be read, value remains TRUE. EXP FLOAT FLOAT 2.718283**argument FIXED FLOAT | BIT FIXED value corresponding FLOAT FIXED | BIT FLOAT value corresponding INDEX CHARACTER,CHARACTER FIXED location of first character of second argument if it is a substring of the first; otherwise, 0 LENGTH CHARACTER FIXED number of characters in value of argument LOG FLOAT > 0.0 FLOAT natural logarithm of argument MAX FLOAT,... FLOAT maximum of all arguments FIXED,... FIXED maximum of all arguments MIN FLOAT,... FLOAT minimum of all arguments FIXED,... FIXED minimum of all
text/pl-reddy-mckeeman.txt · Last modified: 2011/12/25 22:29 by 127.0.0.1