An Evaluation of Simple Procedural - Block Structured Computer Programming LanguagesComparison with Procedural Programming LanguagesBy Natalie Alleman, Brock Boyd, Coi van Bui, Pattie G. Dickerson, and Allani Giridhar Rao |
|
An Introduction to and History of Procedural and Simple Procedural Block Structured Languages:FORTRAN was the first of the Simple Procedural Languages (SPLs). It was a language designed by IBM for use on the IBM 704 system. Prior to the design of FORTRAN, computers used hand-coded machine language or interpretive systems. At the time, the utility of any high-level language was open to question by programmers schooled in assembly language programming. Their most serious complaint concerned the efficiency of the execution of code compiled from high-level language programs. As a result, the design of the SPLs was oriented heavily toward providing execution efficiency B is a descendant of the programming language BCPL. B was first designed and implemented by D. W. Ritchie and K. L. Thompson of Bell Telephone Laboratories, Inc., Murray Hill, N.J. S.C. Johnson, also of Bell Labs, did the original implementation of the run-time package. The development of B began in the late 1960s. It was to be used in conjunction with the UNIX operating system. The goal was to use a higher-level language, B, to build UNIX. PL/I was rejected for this purpose because it was deemed too cumbersome. Thompson had some previous experience with the BCPL systems language. He ruled out BCPL for use in UNIX development because he considered the language too low level and because it lacked run-time support. Thompson designed the language B as a minimal subset of BCPL for systems programming. The small space in which a compiler had to fit influenced the formation of B, and B was considered "BCPL squeezed into 8K bytes of memory." It is hard today to realize how strong a constraint limited memory size was only a few years ago. The Simple Procedural Block Structured Languages (SPBSLs) began with Pascal, invented by Niklaus Wirth. The SPLs, while inelegant, were popular due to run-time efficiency. Call-by-name parameters used by the SPLs were hard to implement, there was no input-output statement, since those were considered "implementation dependent" at the time, and own static storage was also difficult to implement. In addition, more modern practices like data types and structured programming were developing during the 1960s. Wirth's goal was to design a language that could be compiled in one pass, and a recursive descent parsing algorithm was used to develop the initial Pascal compiler. Pascal’s block structure was able to utilize sub-programs, enabling programs to run in a non-linear order. Wirth also later invented the MODULA series of programming languages, the next step in block-structured languages. SPLs were designed to execute programs efficiently. Computers, costing in the millions of dollars, were the critical resource, whereas programmers, earning perhaps $10,000 annually, were a minor cost. Any high-level language had to be competitive with the execution behavior of hand-coded assembly language. They attempted to optimize the object program, the running time, because most people at that time believed you really couldn't do that kind of thing. They believed that machine-coded programs would be so terribly inefficient that it would be impractical for vary many applications. SPBSLs were designed more for programmer flexibility than absolute run-time performance. These languages have activation records, but employ scope rules and nested block structure for storing and accessing data. In the SPLs, activation records and scope rules are minimal, and run-time descriptors for structured data are not necessary. SPBSLs may require partial run-time descriptors for structured data. While SPBSLs execute efficiently, there is some run-time penalty for using these languages. An Overview of Procedural and Simple Procedural Block Structured Languages:Simple Procedural Languages were used for mathematics, by researchers, and by mathematicians. FORTRAN utilized the IBM 704’s floating-point hardware, which increased the speed of these operations dramatically. Before the development of FORTRAN, floating-point operations had to be simulated in software. Algol60 became the standard for the publication of algorithms in written text. SPLs such as B and FORTRAN, were originally designed to handle complex mathematical functions and arrays and were targeted primarily to the scientific and developer community. Because SPBSLs emphasize good and verifiable programming structure and reliability of algorithms, the SPBSLs are widely used in business applications. COBAL was designed specifically for the business community. Additionally, SPBSLs like Pascal and Modula have been extensively used in the area of teaching computer science and programming. Pascal was the preferred language in the academic world, and was the most widely used language for teaching programming until recently. Like SPLs, SPBSLs have an overall “block” structure with subprograms to extend a main program. SPBSLs were introduced as an attempt to extend the SPL standard during the 1960s when computer hardware was increasing in speed and decreasing in cost. SPLs and SPBSLs are generally implemented using traditional compiler technology. A text editor is used to create the program, a compiler translates the program into executable form, a linker is used to merge subprograms, the main program, and run-time library routines into one executable program, and an execution step executes the translated program. How Procedural and Simple Procedural Block Structured Languages Handle Data Objects:Both SPBSLs and SPLs handle data objects in essentially the same manner. Primitive data types such as character, integer, floating point numbers and arrays are used by both sets of languages. Several individual languages of the SPBSLs introduce additional data types, such as record and set, but these are not common to the families in general. User-defined types are also available in the latter versions of the SPBSLs. B and BCPL are both typeless languages. There is only one type in both languages, the machine word, and the programmer is responsible for applying to a variable only the operators that make sense. B has no structs, no arrays of arrays, no enums, no unions, but the programmer can simulate all of them. There are also none of the char/short/int/long hierarchy, and no unsigned operations. If the character strings are needed, the programmer can either store one character per word in an array and index them directly, or store one character per byte and access them with library functions. More specifically, both B and BCPL are particularly suited for non-numeric computations. Neither language originally supported floating point data types and, since both languages are typeless, arithmetic on characters is legal. Sequential file structures are provided for in Pascal, one of the SPBSLs. The components of a file may be arrays, records, or other structured data objects, in addition to data objects of elementary types. How Procedural and Simple Procedural Block Structured Languages handle Sequence ControlSimple Procedurals Languages execute statements in the order in which they are encountered in the program, while SPBSLs allow programs to execute instructions from various sources. The ability to execute different modules of code at various points in a program enhances the reliability and readability of a language but the sacrifice is the speed of execution. The general standard for both SPBSLs and SPLs it a “top-down”
block structure. Both
families provide looping mechanisms (while, for, do, etc..) and
conditional branching (if, case, switch.)
Unconditional branching (GOTO) while still supported in many SPBSLs
is discouraged. As a general rule in B, anywhere one can use a simple statement, one can use any compound statement, which is just a number of simple or compound ones enclosed in { }. The ability to replace single statements by complex ones at will is one thing that makes B much more pleasant to use than FORTRAN. Logic which requires several GOTOs and labels in FORTRAN can be done in a simple, clear, natural way using the compound statements of B. This convention is the same in the SPBSLs by bracketing compound statements with "begin" and "end", or BCPL's $( and $). The entire statement sequence, including the "begin" and "end", becomes a single statement that may be nested within other statements. In BCPL, a Simple Procedural Block Structured Language, any number of open-block markers may be closed with a single close-block marker. BCPL "relies on the syntax of the various block-structuring commands to provide the context to determine where one statement ends and the next begins. However, when this is not adequate, sequential commands are separated by semicolons if they appear on different lines of source code. When the separation between statements is clear from context, semicolons are inserted (if necessary) by the compiler." In B, semicolons are not used to separate compound statements. How Procedural and Simple Procedural Block Structured Languages Handle Subprograms and Storage ManagementThese two types of language groups are similar in the way that they pass parameters to their respective functions. Static scope rules are used to determine the meaning of non-local references to names. Parameters are passed by value or reference in SPBSLs, whereas all parameters were passed by value in the SPLs, until the development of FORTRAN. Implementation of SPBSLs requires a static storage area for procedure code segments and various items of system-defined data. A central stack is required for allocation of subprogram activation records at the time each subprogram is called. A heap storage area is also required for storage of data objects constructed dynamically. The stack and the heap areas are set up in a single large statically allocated block of storage. The stack grows from one end toward the middle in response to subprogram calls. The heap grows from the other end toward the middle in response to invocations of dynamically constructed data. The stack shrinks as storage for activation records is recovered automatically on subprogram exit. However, if the stack and heap ever meet, then execution of the subprogram must be aborted on the next request for either stack or heap allocation because in general, it is impossible with this implementation scheme to add storage to either area. Freeing of storage is programmer controlled, using a predefined procedure. The potential for generation of dangling references or garbage is present. While a garbage collection method might be implemented to manage storage in the SPBSL and SPL heaps, these mechanisms are not generally used because of their extra cost in storage and execution efficiency. B specifically provides for the use of external variables, variables which are rather like FORTRAN COMMON, in that they exist external to all functions, and are potentially available to all functions. Any function that wishes to access an external variable must contain an extrn declaration for it. Furthermore, all external variables must be defined outside of any function. External storage is static, and always remains in existence, so it can be initialized. Initialization is accomplished by placing the initial value after the variable name, as a constant. SPBSLs provide for the use of subprograms with their own variables defined within separate scopes. When passing variables between procedures in a block-structured language, the values are generally pushed onto the stack before the procedure is called. In B, the statement "auto..." is used to declare local variables, variables which exist only within their own function. The auto variables of B are different from FORTRAN, another of the SPLs, in that they appear when the function is entered and disappear when it is left. They cannot be initialized at compile time and they have no memory from one call to the next. Most of the SPBSLs are designed for a straightforward batch-processing operating environment containing only sequential files. No provision is made for more complex file structures or for direct access to user terminals or external devices. However, the simple, regular, and generally elegant structure of the languages makes the addition of new predefined procedures and data types for special purposes rather easy. Neither SPLs or SPBSLs contain special provisions for separate compilation of subprograms or for any other special characteristics of a programming environment. Programs are assumed to be assembled into complete units that include all subprograms, type definitions, and other components before compilation begins. Thus, merging of separately written program components is done at the source language level, before compilation, rather than through linking of separately compiled components before execution. The rationale for this aspect of the design is that a compiler may be made efficient enough that recompilation of an entire program is no more expensive than re-linking a set of separately compiled program components, and the compiler provides much more extensive checking and error correction. Both language types have some form of type checking between the actual and formal parameters, although B and BCPL specifically have no need for type checking, since they are both typeless languages. It is permissible for procedures to call themselves to enable recursion by both languages groups and they have statically allocated variables. Storage management is handled in both language types in a similar manner. When calls to subprograms occur, memory is allocated by using heap generators. The languages handle storage deallocation explicitly when the heap generators are no longer in use. Both SPLs and SPBSLs support the concept of subprograms through the procedure (does not return a value) and the function (returns a value) construct. Recursion is permitted in some languages of each group. Procedures/functions may also return values by a pass by reference mechanism facilitated by the use of pointers. Neither of these types of languages support abstract data types directly, but simulation through to use of modules emulates this. The B-type languages allow organization of programs by nesting subprograms into larger subprograms. This method, however, provides for poor encapsulation constructs. Encapsulation occurs in procedures where local data is not available to the global program. Later languages such as FORTRAN 77 do allow subprograms to be compiled separately and stored into libraries. All components of records are visible within all procedures that have access to the type of the record in both types of languages. It is the responsibility of the programmer to use the information hiding rules appropriately, since the languages have no automatic checks on violation of these principles.
|