Introduction

To allow the user to write programs which run on a system with a partitioned cache, a compiler is supplied which compiles a high level language into an assembly language suitable for the target machine.

This high level language, from here on refered to as PRE, is a provides an easy to understand syntax that combines elements from C and Occam. Aside from normal program operation, useful items of information, such as the type of accesses that will be made to a variable, are contained within a program written in PRE language. The compiler uses this information as a basis for its control policy for the partitioned cache.

Because the PRE language is very similar to C, it may be helpful to read a good book on C programming before this document if you have not encountered the language before.

Brian W Kernighan and Dennis M Ritchie
The ANSI C Programming Language (2nd edition)
Prentice Hall Software Series
ISBN 0-13-110362-8
1988
£ 29.95

A program written in the PRE language is made up from the following syntactic elements :

• Comments
• Data Types
• Expressions
• Statements
• Procedures

File Name Conventions

Files written in the PRE language are, by convention, appended with a suffix of .pre to distinguish them from other file types.

Comments

To provide the programmer with a means of documenting their source code, the PRE language supports C style comments within the program. These comments take the form of single line comments which start with // and continue to the end of the line, and multi line comments wich start with /* and continue until */. Note that unlike C, nested comments are not currently allowed.

Data Types

All user defined variables in the PRE language are of numeric, integer type although they can be either scalar or vector in terms of size. This reduces the complexity of the compiler and although it restricts the kind of programs that can be written in the PRE language, the facility to implement new types is left open.

To allocate storage space for user variables, the allocation statement is used. This statement tells the compiler the type and name of the variable and the size required by the variable ie. if it is a scalar or a vector of given size. Hence int x allocates a integer scalar variable called x and int[10] y allocates a 10 element integer vector varaible called y.

It is worth taking note that all variables must be allocated in this manner before they are used in any other program construct. Loop counters for bounded loops must be allocated in this same way but can not be assigned to inside the body of the loop.

Expressions

Although you can only have user defined variables of numeric type, there are two types of expression in the PRE language which are numeric and boolean. Both kinds of expressions are combinations, via operators, of constants and user defined variables and the results of function calls, which evaluate into a final value. A simple precedence system is employed while parsing the expressions which dictates which operator will be taken as being more important in the absence of any information conveyed via bracketing.

Precedence	Operator	Operand Type(s)	Operation Performed
1	+, -	numeric	unary plus and minus
1	~	numeric	bitwise NOT
1	!	boolean	logical NOT
2	*, /, %	numeric	multiplication, division and remainder (MOD)
2	&, ^	numeric	bitwise AND and XOR
3	+, -	numeric	addition and subtraction
3	|	numeric	bitwise OR
4	<<, >>	numeric	sign filled (signed) left and right shift
4	>>>	numeric	zero filled (unsigned) right shift
5	<, <=, >, >=	numeric	less than, less than or equals. greater than and greater than or equals
6	!=, ==	numeric	not equals and equals
7	&&	boolean	logical AND
8	||	boolean	logical OR

Basic Statements

Assignment

void main() { int a; int[ 10 ] b; int[ 10, 10 ] c; a = 2 + 3; b[ 0 ] = a * 5; c[ 0, 0 ] = 6 % 3; } Values can be assigned to user defined variables by using the assignment statement. This is the same as in any language and takes the form x = 5 * 3 which assigns the result of the right hand side expression, 5 * 3, to the variable on the left hand side, resulting in the value of x being set to 15. Note that it is not valid to assign to a variable that is being used as a loop counter within a bounded loop.

Bounded Loop

void main() { int a; a = 0 for 10 { println( a ); } } A bounded loop, or "for loop", is used to repeat a block of code when the number of times you wish to repeat the block is known either at runtime or, more preferably, at compile time. The bounded loop in the PRE language is similar to the mechanism of loops used in Occam. The loop counter will be incremented by one each on interation of the loop, there is presently no provision for non unit step sizes.

Using this syntax, the statement x = 0 for 5 { .. } would use the variable x as the loop counter, initialise it to 0 before executing the loop. Each time the loop is executed, the loop counter will be incremented by one with the final value on exit from the statement being calculated by the sum of the initial value and number of iterations.

Unbounded Loop

void main() { int a; a = 0; while( a < 10 ) { println( a ); a = a + 1; } } An unbounded loop, or "while loop", is used to repeat a block of code when the number of times you wish to repeat the block is never known and hence repetition will continue until some condition is broken. The unbounded loop statement in the PRE language is the same as the while statement in C.

An unbounded loop uses a booleanExpression as the condition for exiting the loop. Until this condition evaluates as false, the loop will continue to repeatedly execute. It should be noted that because of this, infinite loops can be written which may, under some circumstances, cause the machine to crash.

Conditional

void main() { int a; a = 0; if( a == 0 ) { println( "a is zero" ); } else { println( "a is not zero" ); } } A conditional statement is used to allow/deny execution of a block of code based on the result of some condition. The conditional statement in the PRE language is the same as the if statement in C except that only one if and else block are allowed per conditional ie. there is no provision for any else if. The semantics of the conditional statement dictate that if the booleanExpression used to control the condition evaluates to true then the first, if block of code is executed. If the condition evaluates to false and there is an else block then this is executed.

Inline Assembly Language

void main() { asm { LOADC 1, 10 LOADC 2, 20 ADD 3, 1, 2 PRINTR 3 HALT } } If you want hairs on your chest and program directly in the PREASM assembly language, you can inline your code within a PRE program. The PRE compiler spots the asm keyword and outputs the contents of the code block verbatim without checking the syntax of the contained assembly language. You must therefore be careful when using this construct as misuse will certainly result in incorrect program behaviour.

Procedures

void main() { int a; int[ 10 ] b; int[ 10, 10 ] c; p(); q( a ); r( b ); s( c[ 0 ] ); a = 10 * p(); return; } int p() { return 1; } void q( int d ) { return; } void r( int[] e ) { return; } void s( int[] f ) { return; } Firstly, some short answers to some straight forward questions :

• You must have one procedure with the prototype void main() to act as the entry point to the program.
• Procedures can be recursive.
• Procedures must be uniquely named, ie. all procedure identifiers are unique.
• All arguments are all passed in the same way as Occam. As far as the programmer is concerned this is the same as "by reference" in C, but implemented via a copy back mechanism.

Procedures in the PRE language are the building blocks of a program. You can have any number of procedures, which are defined in a similar way to in C, in your program as long as they are all uniquely named and there is at least one called main which takes no arguments.

Defining Procedures

To define a procedure the user needs to give a procedure prototype followed by a block of code that represents the procedure. The procedure prototype tells the compiler about the name of the procedure and the number, type and name of any parameters as well as the return type. This allows the procedure to be sucessfully referenced from elsewhere in the program. The block of code that represents the procedure is executed when the procedure is called. This block of code can make use of all the parameters by referencing them in the same way as a normal user defined variable.

Procedures may be declared external using the extern keyword. A prototype for an external procedure is given so that type checking can be performed but the implementation of the procedure is given else where.

The program can exit from anywhere in the procedure by using the return statement which will return control to where the procedure was called from. Note that if the procedure has a return value a value must be provided and that if no return statement is encountered, the procedure will return when encountering the end of the procedure.

It should be noted that although scalars and one dimensional vectors can be declared as parameters to a procedure, two dimensional vectors can not.

Calling Procedures

A procedure can either be called as a basic statement or as part of an expression, in which case the return type of the procedure can not be void. In either case the calling syntax is the same as C. Type checking is performed on the arguments the users types to pass via the procedure call against the parameters defined in the procedure prototype so that it is not possible to call a procedure with the wrong number or type of arguments or include a function with a void return type in an expression.

Arguments passes to a procedure are all passed, as far as the programmer is concerned, "by reference" and so assignments to parameters within the called procedure will effect the value of the arguments in the calling procedure.

Example Programs

As a more complete demonstration of the PRE language, a number of test programs have been produced that utilise most of the features of the language.

• Bubble sort
• Insertion sort
• Quick sort
• Selection sort
• Multiplication tables
• Tree search and traversal
• Bresenham's line and circle drawing algorithms
• GIF87a decoder
• CCITT G.721 and G.723 voice compression decoder