S*(ID:825/s::001)microprogramming language schemaDasgupta, Simon Fraser U, 1978. A microprogramming language schema, which instantiates to a complete language for any given micromachine. Has Pascal-like syntax, with pre- and post-conditions. Related languages
References: S* S* dates from 1978, it was developed by Suhrata Dasgupta at Simon Fraser University. Design goals. Three design goals are mentioned: "(i) the ability to construct control structures for designating clearly, and without ambiguity, both sequential and parallel flow of control; (2) the ability to describe and name arbitrarily, mieroprogrammable data objects or parts of such data objects; (3) the ability to construct microprograms whose structure and correctness can be determined and understood without reference tO any control store organization." Primitives. S* is described as a language schema, rather than a complete language. It consists of a framework providing a declaration structure and a set of compound statements with associated semantics in the form of pre- and postconditions. For a given machine M, S* is instantiated to a complete language S(M), the elementary statements of which are determined by the mlcrooperations of M. Registers: constants residing in read only memory and testable machine conditions must be declared explicitly by the user before they can be referenced. In order to complete the semantics of S(M), it may be necessary to declare additional pre- and postconditions. For instance, the increment operation of S* is defined on arbitrarily large integers: {X+l = v} INC X {x = v} In a specific instantiation S(M) allowance will have to be made for the possibility of overflow and the above rule will have to be modified accordingly. For a 16-bit twocomplement integer range it is modified as follows: {X+l = v & v < 32768} INC X {x = v}; {X+l = v & v = 32768} INC X {X = -32768 & OVERFLOW = i} These pre- and postconditions should be used by the programmer, to prove that her program is correct, i.e. that it conforms to a specification in the form of additional sets of pre- and post-conditions. Variables. In S*. declaration of a variable is meaningless. In an instantiation S(M), each variable must, in its declaration, he associated with one or more specific machine registers or main memory locations of M. This association can be quite complex. It is possible for example to declare an array consisting of five elements corresponding to the low order 4 bits of register R 1 through Rb. Parallelism. Parallelism is explicit, the programmer has to compose the microinstructions herself. This is a logical choice in view of the design goals, which emphasize verifiability and wellstructuredness of programs rather than simplification of microprogrammlng by raising the level of primitives. Three constructs to aid in mieroinstruction composition are provided in the language: cobegln SI; $2; ... ; Sn coend denotes that the (elementary) statements SI; ? ..; Sn should all be executed in the same microcycle. cocycle SI; $2; ... ; Sn coend is a construct which is meaningful in S(M) only if execution of a microinstructlon on M is split into n phases. It denotes that SI to Sn should all be placed in the same mlcroinstruction, and that SI should be executed in the first phase, $2 should be executed in the second phase, etc. The execution of the microoperations SI to Sn should not overlap. Si can be a cobegin-coend statement. du___/_r SO d_oo Sl; S2; ... ; Sn end specifies that SO runs concurrently with the sequence S1 to Sn. S0 takes a maximum of n mlcrocycles to complete. Control Structure. The syntax of S* is basically that of PASCAL. Parameterless procedures are allowed. In the declaration, the procedure name must be followed by a parenthesized list of the variables used in the body. Procedures and blocks may contain local declarations, but of course the variables must be linked to machine registers. Expressions can be arbitrarily complex. Statement forms provided are a cascaded ifstatement (if tl then SI elif t2 then $2 ... elif tn then Sn fi), while-do and repeat-until, call and return, sequential (begin-end) and parallel block structures (as specified above), and a region-end statement which delimits a hand-optimized section where the flow of control may not be changed by the compiler. Tests are elementary statements occurring only in an instantiation S(M); they must correspond to hardware testable conditions of M. Datatypes and datastructures. The only primitive datatype in S* is the bit. There are four ways to construct new datatypes: seq [!''J] bit denotes a bltstrlng with i and j as high and low order indices. Arithmetical, logical and shift operations have their standard meaning on bitstrings. array [i..J] of type denotes a sequence of elements of an arbitrary type. tuple fleldl: typel; ... fleldn: typen; end corresponds to the PASCAL record. Field selection is done as in PASCAL with one addition: if X is a tuple data-object and all fields in X are of type seq [] bit, then a reference to X without selection refers to the concatenation of all fields. This is very convenient; if IR is a variable of type "instr" with fields opcode, addr and index, then one can refer to the complete instruction (IR), as well as to separate fields (IR.opcode). stack [i] of type with ident {, ident} declares a stack of depth i, with staekpolnters denoted by the identifiers. Implementation. No S(M) has been implemented so far, but the level of the elementary statements suggests that writing a compiler is certainly feasible. Although not mentioned in [4], an automatic verifier to check the validity of the program proof provided by the user, would fit very well in an S(M) implementation. Conclusions. Instantlatlons of S* can be expected to be well structured languages with well defined semantics, which can be an important aid in the development of reliable mlcroprograms. Although a program written in any specific instantiation S(M) is highly machine dependent, the good structure of the S* schema will facilitate the transformation of programs from one instantiation to another. Because parallelism and timing are explicit the programmer must have intimate knowledge of the specific machine for which the program is written. in Proceedings of the 13th International Symposium on Microarchitecture Springs, Colorado, United States 1980 view details |