Contact us Heritage collections Image license terms
HOME ACL Associates Technology Literature Applications Society Software revisited
Further reading □ Overview □ Main papers □ ManualIntroductionIR MacCallum (thesis)RosenTrees/Routines □ Implementation □ Listing: OverviewSection 1Section 2Section 3Section 4IndexFlow diagramsSyntax analysis in compilers □ CC and Autocodes □ AutocodesMercury Autocode (MA) facilitiesMA in CCTwo-level storageAtlas Autocode (AA) featuresCC in AAIndex-directed □ Other papers □ Compiler SystemAssemblerRealisationTranslation programExperience with CCCC re-examinedThird-order compilerUseful subsetsLavingtonCoulourisReview of Rohl book □ CC on Bendix G21 □ G21 manualG21 flow diagrams □ Translator Writing Systems (TWS) □ Early TWSMetcalfe paperComputer Assoc. Inc paper
ACD C&A INF CCD CISD Archives Contact us Heritage archives Image license terms

Search

   
ACLApplicationsCompiler Compiler
ACLApplicationsCompiler Compiler
ACL ACD C&A INF CCD CISD Archives
Further reading

Overview
Main papers
ManualIntroductionIR MacCallum (thesis)RosenTrees/Routines
Implementation
Listing: OverviewSection 1Section 2Section 3Section 4IndexFlow diagramsSyntax analysis in compilers
CC and Autocodes
AutocodesMercury Autocode (MA) facilitiesMA in CCTwo-level storageAtlas Autocode (AA) featuresCC in AAIndex-directed
Other papers
Compiler SystemAssemblerRealisationTranslation programExperience with CCCC re-examinedThird-order compilerUseful subsetsLavingtonCoulourisReview of Rohl book
CC on Bendix G21
G21 manualG21 flow diagrams
Translator Writing Systems (TWS)
Early TWSMetcalfe paperComputer Assoc. Inc paper

Principles for Implementing Useful Subsets of Advanced Programming Languages

G F Coulouris

Machine Intelligence 1 Workshop, September 1965

University of London

1. Introduction

The author has been concerned with the implementation of a subset of the CPL programming language (Barren et al. 1963) for use in a university (Coulouris & Goodey 1965). This paper describes the results of efforts to isolate those features of the language which may be implemented by relatively simple techniques. The subset eventually arrived at contains few limitations of importance in general programming. The techniques adopted generally result in a more efficient object code than would be possible with more sophisticated methods.

The implementation makes use of the compiler-compiler system (Brooker, MacCallum, Morris & Rohl 1963) and this paper contains some comments on the relative importance of the various features of that system in the implementation of syntactically complex block-structure languages such as CPL.

Although the discussion in this paper is largely in terms of the specific problems of the CPL language, the techniques adopted can be extended in a fairly obvious manner to other languages containing features which are semantically equivalent. The author apologises for any inadvertent use of local jargon; despite recent developments in the formalisation of programming languages, the discussion of implementation problems seems to be largely restricted to specific systems.

2. The Choice of a Subset

Practical limitations on time and programming resources suggested a corresponding restriction of aims to the implementation of a useful and consistent subset of CPL. The following factors were considered relevant in the design of the subset (listed in order of decreasing importance); speed of the object code, efficient use of store in the object code, efficiency of the compiler and the ease with which later extensions could be made to the subset.

It was accepted as an ad hoc basic principle that the use of interpretive techniques in the object code increased both the complexity of the translation problem and the time of execution of the object code.

For the purposes of this paper the term interpretive technique includes those techniques which produce an object code containing references to data other than the explicit operands in the source code, or in which the flow of control does not necessarily correspond to that in the source program. One example of the latter would be an entry to a store allocation routine. Conversely, a non-interpretive code is one in which no reference is made to information other than explicit operands, and in which the logical flow of the object code is isomorphic with the flow implicit in the source program.

An added incentive for the acceptance of a principle of non-interpretation was that the facilities of the compiler-compiler are not easily adapted to the implementation of routines for interpretation.

As we shall see in a later section, strict adherence to the principle would lead to hopelessly inefficient use of storage by the object program. Nevertheless, a compromise was reached by which it was possible to implement a very powerful subset of the language using object code less complex than that of many Algol implementations.

It is interesting to note that nearly all the omissions from the subset are semantic features of CPL. The many convenient syntactic features were easily handled by the very powerful syntactic classification facilities of the compiler-compiler.

In the following sections, the consequences of including various semantic features in programming languages are discussed.

3. The Store Allocation Problem

In terms of our principle of non-interpretation, there are at least three levels of complexity in schemes that may be used for the allocation of absolutely addressed storage to the operands in a source code:

  1. the allocation of an absolutely addressed location to each element at translation time;
  2. the allocation of storage relative to one or more pointers varied at execution time (often known as a dynamic stack system (cf. Randell & Russell 1964));
  3. the allocation of storage on an available space basis at execution time. A store map is used and all references to the store are via the map. This technique is known as the Codeword system (Iliffe & Jodeit 1963).

We will now investigate the potentialities of each of these schemes for the implementation of various features of CPL.

First, it is necessary to distinguish between simple items, namely those whose size and structure does not vary at execution time, and compound items which may change in size and structure. In CPL, the first category includes all items of types index, integer, real, Boolean, logical, long logical, label, complex, etc., while the second contains all array and string items. In Algol, a similar distinction can be made between items of types integer, real and Boolean on the one hand, and array on the other. The status of items of types function and routine in CPL is dependent on other factors and is discussed in a later section.

Consider the consequence of using store allocation scheme (i) for simple items. The scheme implies that each item uses a fixed store element, and that object code may be compiled containing direct references (without B-modification) to the absolute address corresponding to an item. Any resultant gain in speed of object code will derive from the fact that in many hardware systems the speed of absolute store referencing is appreciably greater than that for relative referencing. However, the allocation of a fixed store element to each item may produce inefficiency in the use of storage in some situations in comparison with the dynamic stack technique.

Unless sophisticated store optimising procedures are to be used we may take the following rule to characterise scheme (i):

Every store element allocated to an item remains associated with that item throughout all portions of program during which the item may be activated (1)

We shall call the portions of program mentioned the potential scope of the item.

To understand the application of the rule, consider the following segments of a CPL program.

§ 1 let a, b be real 
    let F[x] be value of § 1.1          let y be real
                                      Input [y]
                                      result is x↑2+y↑2 $ 1.1 
    Input [a, b]
    .
    .
    .
    
§ 1.2 let z=3a ↑ 2 + 2b ↑ 2
    Output [F[z] + 2F[z ↑ 3]]    $ 1.2
    .
    .
    .
    
§ 1.3 let Z=3a ↑ 3 - 2b ↑ 2
    Output [F[Z] + F[Z ↑ 2]]     $ 1.3
    .
    .
    .
    finish                         $ 1

CPL uses the symbol § with a vertical line through it to represent the end symbol. A $ has been used here.

Consider first the variables z, Z declared in § 1.2 and § 1.3 respectively. The actual scope of z is § 1.2. It may only be activated by normal entry to the block through the heading. Accordingly, the potential scope of z is the same as its actual scope. Similar reasoning applies to Z. Thus z and Z may share the same store element under rule (1).

Now consider the variable y. The actual scope of y is § 1.1 (i.e., the block expression defining F[x]). Each application of F causes a reference to y. Thus the potential scope of y must be the entire actual scope of F. By (1) the store allocated to y is unavailable for other purposes throughout the remainder of § 1.

The rule corresponding to (1) which characterises the dynamic stack scheme (ii) can be stated :

Every store element allocated to an item remains associated with that item throughout the actual scope of the item (2)

A near optimal use of storage is achieved if scheme (ii) is used for simple items. (Still greater optimisation might be achieved by flow analysis methods.) For example, the variable y in the last example would now require a store element only during each application of the function F. The additional cost incurred by scheme (ii) derives from the need to make all store references relative to a stack pointer and to manipulate the stack pointer during execution.

We will now enumerate the ways in which simple items may be activated during the execution of a CPL program and consider the consequences of using a scheme such as (i) in each case. Items can be activated in the following situations:

  1. on entry to a block which is outside any routine or function body and which contains declarations. Each simple item is allocated a location for the scope of the block. The location is available for the other items outside that block;
  2. on a transfer from outside a block to a labelled command within the block. The case is equivalent to the last one, since a transfer into a block may be transformed into a normal entry to a similar block with a multi-way transfer inserted immediately after the declarations;
  3. on entering the scope of a where clause. Once again this may be transformed into case (a), this time by the introduction of a block. Thus
    Y:= ax+bx↑2 where x=F[y] 
    
    is equivalent to
    § let x= F[y]
        Y:=ax + bx↑2$
    
  4. the object program may need items as working space. These can be considered as concealed where clauses and obey the same rules as explicit where clauses;
  5. on a call for a routine or function whose body contains activations of simple items. This final case is the only one where the potential scope does not correspond to the actual scope. By rule (1) the locations allocated to all items used in a routine or function must be protected throughout the scope of the routine or function. This is analogous to the Algol treatment of own variables. Additional action is necessary if a routine or function is called recursively. This is discussed in a later section.

We conclude that inefficiency in the use of store resulting from allocation by scheme (i) occurs only in the case of local items of routines and functions. This is not usually important, since the number of non-compound items used in a program is roughly equivalent to the number of named variables, and is generally small in relation to the number of elements of compound items. For these reasons scheme (i) has been used for the allocation of store to all non-compound items.

4. Dynamic Arrays and Other Compund Structures

It is not feasible to deal with dynamic arrays of the sort contained in CPL by absolute store allocation methods like scheme (i), because the size of the array may change between one activation and the next. To make matters worse, the size of an array variable may vary during its activation. It turns out that an optimal implementation of this feature is not possible even by the dynamic stack technique which is adequate for the arrays of Algol.

Let us investigate to what extent a single dynamic stack is adequate, and where it fails in the implementation of the fully dynamic arrays of CPL.

Arrays in CPL may be assigned in the same way as items of fixed size. Thus a program segment such as:

§ 1 let a, b=Newarray [real, (1, 100)] 
    and c be real vector
     c:=a
     .
     .
     .
     c:=b   $ 1

is quite permissible, the assignments causing all the current values of the elements of a and b respectively to be copied and given the name c dynamically.

The problem is that such an assignment involves the provision of space for the copy, and the size of the space is unknown during compilation, or even at the time of entry to the block containing the assignment. If a single dynamic stack were used, we would make the copy appear at the next available space on the stack when the assignment occurs. On exit from a block all the space used during the execution of the block is made available again in the usual way. In the example given, the stack representations in Fig. 1 show that the result would be the one required, since the scope of c is precisely the smallest block containing the array assignments.

(i) after 'c:=a' a 100 b 200 c 300 free § 1 pointer current pointer (ii) after 'c:=b' a b anonymous space c free § 1 pointer current pointer
FIG 1.

But consider the following:

§ 1 let a, b = Newarray [real, (1, 100)] 
     and c, d be  real  vector
§ 2    .
       .
       .
       c:=a $ 2
       d:=b $ 1

We can see immediately from Fig. 2 that the result would be incorrect,

(i) after 'c:=a' a b c free § 1 pointer § 2 pointer current pointer (ii) after 'd:=b' a b d free § 1 pointer current pointer
FIG 2.

The space used in the assignment to c becomes available on exit from the inner block and thus is overwritten by the assignment to d. This difficulty might be alleviated in several ways, at the cost of some inefficiency in the use of store. One possibility is to protect the space used in a block if an assignment has occurred during the execution of the block. Unfortunately, this method is not effective unless each array variable contains information about its scope in order to determine when the space associated with it can be freed. Even then the use of store is not very economical, since all the stack space used in the block must be reserved until the assigned array is freed.

It is apparent that no method short of a full dynamic store allocation scheme of type (iii) is adequate for the implementation of the compound data structures of CPL. However, the overheads of such a scheme, both in implementation and in execution speeds, are great, so the limitations of a simple stack have been accepted. The restriction imposed might be worded: Any assignment to an array becomes invalid on leaving the innermost block containing the assignment. This is a restriction on entire arrays, not on the elements of arrays, which may be evaluated and assigned without restriction. A further penalty incurred by the adoption of a single stack is that on assignment to an array variable, the space containing the previous value of the array does not become available until the end of the array's scope.

5. Recursion

In our discussion of store allocation we have not so far considered the possibility that variables may be re-activated during their own activation. This occurs when a routine or function is called recursively. Fortunately it can be easily handled both for the absolute store allocation scheme adopted for simple items and the single stack system used for compound items. In fact the operation of the dynamic stack is such that no special action is required for compound items. When a block is recursively entered, the space for the new activations is obtained from the top of the stack in the same way as before, and on exit from each recursive level, the store used is automatically made available. This is the property of stack storage which makes it so attractive for the implementations of block structure languages containing recursion.

The absolute store allocation scheme adopted for simple items raises few additional difficulties. We have already noticed that the space allocated to items local to a routine or function must be protected throughout the scope of the routine or function. If the routine or function may be recursively entered, we must provide for the preservation of a copy of the values of all the local variables before a recursive entry and for the restoration of the values on exit. In practice this requires the copying of the portion of absolute store allocated to the items local to a routine or function on to the stack whenever the routine or function is entered with its recursive level marker greater than zero. All such vectors on the stack are linked in the form of a backward chain in chronological order of copying. Whenever we return from a recursive call we need only copy the last vector on the chain into its original position in the absolute store.

6. The Scope of Labels

In our discussion of store allocation schemes, we mentioned that a transfer to a labelled command is possible from a position outside the block containing it. This is a feature of CPL which is not contained in most block structure languages, but as we pointed out this inclusion does not raise further problems in store allocation. However the inclusion of variables and expressions of type label further complicates the position; the destination of a transfer command cannot be determined during compilation. This produces considerable implementation problems. Every transfer command must perform an analysis of the position of its destination in the block structure and initiate the necessary activations of the blocks entered. This interpretive feature is eliminated if the scope of a label is restricted to the block containing it.

7. Further Problems of Functions and Routines

In the implementation of the comprehensive facilities for the declaration and use of functions and routines within CPL, several features appear to demand some degree of interpretation. The problems of routines and functions are parallel so the discussion here is restricted to the case of functions for the sake of clarity.

CPL provides for the existence of functions as data items in their own right, appearing in any semantically meaningful context. We may, for example, construct and assign functions.

Functions may behave in one of two ways with respect to their free variables (i.e., variables referred to in the function body which are neither formal parameters of the function nor declared within the function body):

  1. A fixed function evaluates the free variables at the time of activation of the function and associates an unchangeable set of values with the function throughout its activation.
  2. A free function uses the values of the free variables current when they are referred to during the evaluation of a call of the function. The values may vary from one call to the next. This treatment is analogous to the treatment of free variables in Algol procedures.

Since the free variables may be arrays or even further functions, and since a function may be changed by assignment during its activation, the storage problems associated with fixed functions are at least as great as those of arrays. The implementation of free functions on the other hand requires no special handling of free variables and the amount of store required by the function is fixed at compile time. Free functions may be handled within the absolute store allocation scheme described for non-compound items. Fixed functions have been excluded from the subset for this reason and because some degree of interpretation is required in their activation.

The assignment of functions, and the use of functions with functional results, is still possible within the subset, but in order to avoid the interpretation of actual parameter types and modes of call on application, the types and modes of the formal parameters are considered a part of the type of a function. This permits type matching during compilation.

8. Conclusions

The outcome of the project from which this paper stems has been the construction of a translator for a restricted subset of the CPL language. The most important restrictions imposed by the subset are the following:

  1. The scope of labels does not extend outside the block in which they occur.
  2. The use of array assignments is restricted.
  3. Declarations of function and routine variables must include the types of all their parameters.
  4. All functions and routines are free.

The subset is nowhere less powerful than the full Algol language, and includes all the syntactic features of full CPL.

This paper does not do justice to the many powerful concepts behind the structure of the CPL language. Nor does it examine all the problems of implementing the subset selected. It is hoped that the essential features of the techniques used, and their relevance to the selection of a subset, have been made clear. It is interesting to note that some of the methods used are often considered inadequate even for Algol implementation.

The achievement of at least some measure of success was due in no small part to the availability of the very powerful compiler-compiler system. The suggestion has sometimes been made that this system is not suited to the implementation of syntactically complex block structure languages. In the author's opinion, the ease with which this can be achieved is quite surprising, and in particular the project would not have been possible without the facility for recursive use of routines controlled by syntax analysis records. The other advantages of the compiler-compiler include the more obvious ones such as automatic syntax checks of source program, ease of documentation and correction of the compiler and useful monitoring facilities. The total effort involved in the project, including the provision of a library of basic routines and functions, has been of the order of two programmer years. This figure would probably have been trebled if any other available system had been used.

9. References

Barren, D. W., Buxton, J. N., Hartley, D. F., Nixon, E., & Strachey, C. S. (1963). The main features of CPL. Comput. /., 6, 134-142. A fuller and more up-to-date description of CPL is available in The CPL Reference Manual (1966). Pergamon Research Group, Oxford.

Brooker, R. A., MacCallum, I. R., Morris, D., & Rohl, J. S. (1963). The Compiler Compiler. A. Rev. autom. Progmg, 3, 229-275.

Coulouris, G. F., & Goodey, T. J. (1965). The CPL 1 System Manual. ULICS Prog. Inf. Doc., 12.

Iliffe, J. K., & Jodeit, J. G. (1962). A dynamic storage allocation scheme. Comput. J., 5, 200.

Randell, B., & Russell, L. J. (1964). Algol 60 Implementation. London: Academic Press.

⇑ Top of page
© Chilton Computing and UKRI Science and Technology Facilities Council webmaster@chilton-computing.org.uk
Our thanks to UKRI Science and Technology Facilities Council for hosting this site