RED is a programming language designed, in accordance with the DoD "Steelman" requirements, for DoD embedded computer applications. The language combines features common to most existing high-level languages with new capabilities for abstract data types, exception handling, multitasking, generic definitions, and access to machine-dependent facilities.

1.1  DESIGN GOALS

The RED language has been designed to reduce the total life cycle cost of designing, implementing, testing, and maintaining programs. For small and medium size programs, most modern high level languages are similar. However, for large programs, such as those commonly developed for embedded applications, the facilities provided by a language become crucial. What distinguishes the RED language is that it makes it easy to express solutions to the problems encountered when developing large programs.

Although many factors are involved in judging program quality, four key properties that will enhance the production of high quality programs have been specifically addressed in the design:

1. Modularity -- The program structure must be clearly modularized so as to facilitate design and maintenance.

2. Abstraction -- It must be possible to write programs in terms of a variety of abstractions that are appropriate to the application area, and in a notation that is in keeping with the style of the notation used for language-provided abstractions.

3. Reliability -- Coding and integration errors must be minimized either by elimination of whole classes of errors or by early detection

4. Effectiveness -- The program must address the real problem and provide an effective solution. Use of assembly language should not be necessary.

Modularity

Cost effective program development and maintenance requires a modular design. The RED language provides a rich set of features for creating modules. Some of the kinds of modules supported are:

procedures
functions
tasks
data structures
abstract data types
schedulers
multitasking synchronization schemes
common data pools

The RED language also permits modules to be generalized by the use of its generic facility. For example, a sort procedure that sorts arrays with integer components can easily be generalized to sort arrays with components of any type.

Abstraction

The RED language allows existing language notations (e.g., operators) and features (e.g., the case statement) to be extended to encompass application specific abstractions. Once an abstraction has been written, it may be used as if it were a built-in feature of the language. Although application programmers may define their own abstractions (e.g., procedures and abstract data types), many centrally defined facilities (e.g., libraries, common routines and data, real time schedulers) will be written by system programmers. For these kinds of abstractions, the language provides an extensive set of advanced features intended mainly for use by systems programmers. Once an abstraction is defined by a systems programmer, application programmers can use the abstraction without having to understand the advanced features used in its implementation.

Although the presence of advanced facilities in RED increases the apparent complexity of the language, it actually decreases the complexity of the overall programming process. Application programmers will be able to use more appropriate abstractions rather than having to work out less effective and less maintainable solutions to their problems.

Reliability

The RED language is designed to aid the programmer in the production of reliable programs. Particularly dangerous language features have been avoided. The language is fully type checked including the interfaces between separately translated modules. Extensive checking for error conditions is included; whenever possible, the checking is done during translation rather than at run time. Facilities are also provided for detecting and handling run-time errors. Assertions may be specified at any point in a program, as an aid to program verification and as a way of detecting run-time errors. For cases where efficiency is an overriding consideration, users can suppress the generation of code for detecting run-time errors. The scope rules, together with the capsule and expose declarations, allow users to completely control the regions of a program over which names are known.

Effectiveness

The RED language provides direct and convenient ways of dealing with real problems that have traditionally been either difficult or impossible to handle within a high level language. This means that users will not have to resort to assembly language to solve these problems. The RED language provides:

1. Access to machine-dependent features -- Facilities include the ability to specify physical representations, to access special memory addresses, to do hardware level I/O, and to handle hardware interrupts.

2. Control over all aspects of multitasking -- Users can define their own scedulers and synchronization schemes. Both multiprocessor systems with shared memory, as well as distributed systems, can be supported.

3. Control over storage management -- Users can select a dynamic storage management strategy that is appropriate to their application. In particular, applications which require dynamic storage management are not forced to pay the price of garbage collection, but can choose alternative methods.

1.2  SEMANTIC FRAMEWORK

This section discusses some of the key concepts which form the semantic framework for the RED language.

Scope Rules

A program consists of a nested set of scopes. When a name is used, a local definition is referenced if one exists; otherwise, a definition is sought for in enclosing scopes. There are two basic kinds of scopes: open scopes and closed scopes. Closed scopes differ from open scopes in that names of variable definitions in enclosing scopes may not be used unless they are explicitly imported.

A capsule is a scope with special properties. Definitions within a capsule are explicitly exported to those scopes which expose the capsule. Capsules are also the unit of separate translation. Definitions exported from one translation unit can be exposed in other translation units.

Immediate and Deferred Declarations

Declarations are divided into two groups: immediate declarations (e.g., a variable declaration) and deferred declarations (e.g., a procedure). Immediate declarations are elaborated when they are encountered, while deferred declarations are elaborated only when they are explicitly invoked. Deferred declarations may have parameters, may be overloaded, and may be generic; immediate declarations may not.

Deferred declarations are closed scopes; immediate declarations are not scopes at all. A body can contain declarations as well as statements. In a body, any declaration can appear before the statements; deferred declarations are also permitted to appear after the statements. All compound declarations (i.e., those containing bodies) are deferred declarations.

Types and Subtypes

Data items (e.g., variables) have two kinds of properties: those which must be known during translation (type properties) and those which must be known when a data item is created (constraint properties). A type consists of a type name and the type properties. A subtype consists of a type plus the constraint properties. The following are types:

INT
STRING [ASCII]
RECORD [c : INT, b : STRING[ASCII]]

The following are subtypes:

INT (1..10)
STRING [ASCII] (5)
RECORD [a : INT (0..1), b:STRING [ASCII] (j)]

Note that type properties are always enclosed in [ ], while constraint properties are always enclosed in ( ).

Subtypes are always specified for declared variables. For formal parameters and function results, either a type or a subtype is specified. A formal parameter which specifies a type can have actual parameters with any subtype of that type.

Since types consist only of information known at translation time, all type checking (e.g., checking that the type of an actual parameter is the same as the type of the corresponding format parameter) is done during translation. Types are compared by comparing their "extended name" (i.e., their identifier plus their type properties). Type checking does not involve structural equivalence (l.e., comparison of types which are recursive). In addition to the rich set of built-in types, users can also define their own types in one of two ways: as "data structures" or as "abstract types". A data structure is an abbreviation for a composition of language types. For example,

ABBREV r : RECORD [a : INT (1..10),
                   b : STRING [ASCII] (5) ];
VAR x : r;                   

is equivalent to

VAR x : RECORD [a : INT (1..10),
                b : STRING [ASCII] (5) ];

An abstract type is a user-defined type (which is different from all other types) together with a set of procedures and functions which operate upon data items of the type. For example, a user can define a STACK type together with the PUSH and POP operations.

Multitasking

Concurrent elaborations are achieved via the multitasking facilities. Tasks are like procedures except they are invoked by a task invocation statement to produce a task activation. Activations of the task are elaborated concurrently with the invoker. Each activation of a task is named by a unique activation variable.

The elaboration of multiple tasks is under the control of a scheduler. In addition to a language defined priority scheduler, users can also define their own schedulers. The particular scheduler that is used for a task activation is selected based on the type of its activation variable.

Task activations can communicate in two basic ways: via shared memory or via message passing. Mutual exclusion over shared memory is achieved by datalocks (which are basically boolean semaphores) and a region statement. Message passing is supported by mailboxes (which are basically a queue of messages). A multiway wait statement is available which permits users to receive a message from any one of several mailboxes. Multiway waits on sending of messages are also provided. If there are several activations waiting to enter a region with some data lock, or to send a message to a mailbox, or to receive a message from a mailbox, they are queued in first-in first-out order.

Users can define their own synchronization schemes. This can be achieved either by defining these schemes based on datalocks or mailboxes or by way of the low-level multitasking facilities. Low-level multitasking facilities include latches (which are basically spin-locks) together with a standard set of low-level operations which are used to describe scheduling, region statements, and multiway waits. One important property of user-defined synchronization is that a particular scheme can be defined independent of any particular scheduler (i.e., it can be used without modification with any scheduler). Timing facilities are also available for measuring times or delaying based upon either real time or activation times (i.e., the total time some activation has actually been running).

Generics

Any deferred declaration can be generic. A generic declaration is a generalized form from which a collection of different instances of the declaration can be derived. These instances are produced during translation. Instances differ in the values of a set of generic parameters. Generic parameters may be types, functions, procedures, tasks, or manifest values.

Generics are used to generalize a particular deferred declaration. For example, a generic sort procedure can sort arrays with components of any type. A generic stack type includes stack types which can have a component type (eg., STACK [INT], STACK [STRING [ASCII]]). A generic integrate procedure can integrate any function, for example, from floats to floats.

Generic declarations allow the user to write a single definition which is specialized during translation for several specific uses, rather than having to write a separate definition for each of the separate uses.

1.3  PROGRAMMING CONSIDERATIONS

The characteristics of the RED language discussed above represent a solution to the problem of providing a standard language for military software production, one that can serve all applications without ignoring the special requirements of each. The solution presented here is based heavily on the data abstraction capabilities that permit the same language to be specialized as needed, but in a form that is invisible to the applications programmer and, perhaps more importantly, to the maintenance programmer. Changes required can be implemented in terms of underlying definitions so that most often programs need not be changed at all in order to operate differently. Such underlying modifications can, further, affect many applications programs, so that the maintenance effort is substantially reduced along with maintenance costs.

In order to provide comprehensive support within the context of one high-level language, the RED language necessarily includes complex features that will neither be needed or necessarily understood by all programmers. By separating out these complex features, it has been possible to retain a core of basic programming facilities that are similar to most other languages and, thus, easy to learn and use, yet flexible enough so that sophisticated applications can be expressed using only these basic facilities.

1.4  OVERVIEW OF THE LANGUAGE REFERENCE MANUAL

This LRM is divided into four major parts:

GREEN (Chapters 1-7)	Basic Language Features. The features described here will be needed by all users. This part of the language is roughly equivalent to the PASCAL language. Simple programs can be written using only these features.
YELLOW (Chapters 8-11)	Intermediate Language Features. The features described here will be needed by most users.
RED (Chapters 12-14)	Advanced Language Features. The features described here are provided mainly for use by systems programmers, rather than by application programmers.
BLUE Appendices, lndex.	.

The division into basic, intermediate, and advanced parts is only approximate. Although most features described in a chapter belong in the part in which the chapter is placed, some features discussed may conceptually belong in some other part. For example, the type declaration is intermediate rather than basic, some aspects of the use of generics are advanced rather than intermediate, and definition of operators is intermediate rather than advanced.

1.5  MANUAL LAYOUT

This document is a language reference manual, designed to provide the user with a complete description of the format, usage and effects of all language features. Basic lexical elements of the language are described first (Chapter 2). Subsequent chapters present the various language constructs.

Each section of the manual follows the same basic five-part form given below, although any of the five parts may be omitted when it is not applicable.

1. Diagrams -- A flow diagram format (described in Section 1.6) is used to specify the form for lexical elements and the syntax for language constructs.

2. Informal Description -- The text immediately following the diagrams informally describes the purpose, use and meaning of the lexical element or language construct.

3. Rules -- The heading RULES indicates that the following text gives rules completely defining the meaning of the lexical element or language construct, that are not already given by the syntax.

4. Notes -- The heading NOTES indicates that the following text describes how the lexical element or construct interacts with other parts of the language. Rules from other sections, which are relevant to this lexical element or construct, may be summarized.

5. Examples -- The heading EXAMPLES precedes sample coding sequences that illustrate the various valid forms of lexical elements or the use of language constructs.

RULES

1. Each diagram defines the forms for a particular lexical element (see Chapter 2). The name of the element being defined appears in the oval, (1), at the upper left of the diagram.

2. The diagram identifier, the letter in the upper right hand corner, (2), is associated with this specific diagram. An index of diagram identifiers may be found in Appendix F. In the example illustrated, the syntax diagram defines all possible forms of an identifier token.

3. Boxes with circular ends, (3), represent lexical elements or characters from which they are constructed.

4. If the rounded box represents an element defined in another syntax diagram, a letter above the rounded box is the diagram identifier associated with that element.

5. To generate forms of the element, the diagram is followed from left to right, from box to box, startin at the point of the junction of the definition box, (4), and ending when the end of the path, (5), is reached.

6. When, in following _a diagram, a black dot, (6), is reached, any of the paths leaving the dot may be followed.

7. lt is not legal to "back up" along a convergent path, (7)

8. When a box is encountered, the element it contains is added to the right of the preceding element. For example, the path shown by the dotted line, (8) , generates the sequence "letter letter underscore letter" (e.g., AB_C).

RULES

1. The name of the language construct being defined appears in a rectangular box, (1), in the upper left-hand corner. The illustrated example defines the syntax of a statement.

2. The diagram identifier, (2), for language construct diagrams is an integer. An index of diagram identifiers may be found in Appendix F.

3. Boxes with circular ends, such as (3), represent lexical elements; reserved words appear in capital letters. A letter above the box, (4), identifies the diagram in which the element is defined.

4. Rectangular boxes within the diagram, such as (5), represent language constructs defined elsewhere. lf a number appears above the box, the construct is defined in the diagram identified by that number.

5. Following a path through a grammar syntax diagram produces an instance of the construct.