Congratulations on being named to the company’s secret compiler project. Alternative Arithmetics is pleased to have developed a stack-based processor that achieves five petaflops. Such processor speeds make many heretofore impossible computations possible.

In order to make use of this speed, we must develop a new compiler. We have considered the three types of languages: imperative, functional, and logical. We believe our best chance for success lies in developing a functional language that we are tentatively calling Errett after the mathematician Errett Bishop. Functional languages generally allow for very powerful type systems (ML, for example) and very clean semantics.

In order to proceed on parallel development paths, AA’s research has developed a simple version of the language design that can produce information in the appropriate form for you. We have decided to take the same tack as the GNU gcc compilers by separating the syntactic processing from the semantics and code generation segments. Your group will be developing the second phase: the semantics processing and code generation aspects. There are not enough chips available for you to work with a live chip, but the new petaflop chip uses a Forth-like input language. Therefore, you will be converting the syntax trees developed for Errett into Forth code. Because of its stable nature, we have decided to use the GNU Gforth system as the emulator. We have also provided a prototype syntactic processor so you can experiment with the interface.

Other memos are in preparation that outline the specific trees that you will have to process and the semantics of each of the operators or constructs.

Best of luck. We’re happy to have you here at Alternative Arithmetics and we’re counting on you to develop the prototype compiler necessary to our success.

Best regards,

Socrates Polyglot

President

The Simple Object Language (SOL), pronounced “soul,” is the primitive language for the new Simple Object Action Processor (SOAP). The SOAP processor is under development but we can have software emulation by using the Gforth system. Some features of Gforth may not be available in the SOAP.

2.2.2    A Note on Notation

When describing the syntax below, we use two forms of notation. Atoms that appear like-this are written exactly as shown. Atoms that appear like-this can be thought of as variables. For example,

[let variable value]

should be read as follows: The [ and the word let are written as shown; variable can be replaced by any allowed variable and value can be replaced by any valid expressions. The last statement represents the tree shown in Figure 2.2.

In Cambridge Polish the first element is considered to be the function name and the other elements are arguments.

SOL is a cross between an assembler language and a higher-level language. Languges such as SOL were in vogue in the late 1960s and early 1970s (PL360, for example). It adopts a simple syntactic structure, but it also adopts simple statements such as expressions and assignments and the use of higher-level control statements such as if and while.

The current state of the SOL syntactic processing is described here. The output of the syntactic program is in Cambridge Polish, and the semantic intent is described in this memo. All statements begin with an atom that designates the function to be applied. So, for example,

is the Cambridge Polish rendition of the tree for 1 + 2 * 3. Some functions such as let are pseudo-functions because they take their meaning at compile time, not run time.

Generally, labels, function names, and type names can be any valid C variable name but without the underscore (‘_’). Primitive operations use conventional symbols. Operands can be variable names, C integers, C floating point numbers, or C strings. Operands can also be array and pointer expressions. The variable names true and false are reserved for Boolean values and hence cannot be used as function or variable names.

The language is primarily functional in orientation: every primitive operator returns a value except the function definition; and while. if statements are a bit different than the standard C one: if can return a value and therefore when used functionally, both branches of the if must return the same value. See, too, the comment above on the use of names that begin with the number sign.

Comments do not appear in the Cambridge Polish version.

The elements of the SOL are much like C: booleans, integers, floating point numbers, strings, and files. The language also allows for variables and function symbols.

Each of the primitive data types comes equipped with pre-defined operations. The tables shown in Figures 2.5 to 2.12 later in the chapter list the primitive operations.

There are three basic control structures: sequential, selection, and repetition.

SOL is a functional language. This means that virtually all constructs return a value, the major exception being the while. Expressions are written in prefix notation and this is the major reason Cambridge Polish is used as the intermediate notation. In general, then, expressions are written as

The list of operations and their attributes is provided later in this chapter starting with Figure 2.5.

One major difference in SOL from C is the fact that if and select statements must return consistent values because the body of a function might be only a select statement.

With regard to stacks, because SOL will work with a stack-based environment, special notation is invented to address the two stacks: the argument-integer stack and the floating point stack. These are represented by $integer and $Finteger, respectively. Reading a stack location does not alter its value; assigning to a stack location does alter the value.

Because SOL is a numerically oriented language, arrays are first-class citizens. Array constants are represented as

Functions are defined using let statements. The form of a definition requires some thinking about the Cambridge Polish syntax. In Cambridge Polish, functions are written in prefix Polish: the function symbol comes first, followed by the arguments. For example, a(b, c) would be written [a b c]. Therefore, a function definition would look like

Local variables in functions (in fact, anywhere) are a special form of the let function.

Notice that this version of the let has three elements exactly; the functional definition has only two.

A file may contain multiple function definitions. A file may also contain variable statements. Variable statements outside a function are considered to have global scope outside the file but local scope in the file: a variable is not known until it is defined and it is known from that point to the end of the file.

Files may have executable statements outside function or module definitions. These are taken to be statements to be executed at the time the file is loaded by Gforth.

SOL provides for derived types by the type statement typename: type.

The type-expression is a sublanguage in its own right (Figure 2.3).

Classes are derived types with inheritance, information hiding, and polymorphism. Objects are instances of classes (Figure 2.4). Various conventions based on Java are assumed. As usual, constructors take on the class name and are polymorphic.

Dynamic allocation is provided using allocate and deallocate, precisely like “malloc” and “free” in C. A pointer value is dereferenced using the “dot” notation outlined above. allocate has one argument, a type name from which the space needs are created. allocate returns a valid pointer if space is available and 0 if space is not available. The built-in function isnull returns true if a pointer is 0 and false if the value is a non-zero pointer.

There are two scope types in SOL: file scope and function/compound statement scope. In general, definitions in either scope are considered known from the end of the definition statement until the end of the file (in file scope), function (in function scope), or immediately after the begin (in compound statement scope).

Variables defined in file scope are considered static and persist throughout the lifetime of the program. Variables defined in functions local in scope and transient (on the stack). Function names are always considered static.

2.10.2  Scoping within Functions and Compound Statements

Scoping in functions and compound statements is lexical. This means that there can be nesting of scoping (functions within functions and compound statements within functions within compound statements, ad nauseam). Such nesting leads to the “nearest definition” use, as in C (Figure 2.5).

The intent is that SOL will strongly become a type language. Unfortunately, development schedules for the early versions of the parser will not allow us to produce the code necessary to do type inference. Therefore, we will fall back on the C-type languages and require every user name to be defined using primitive or user-defined types. The type system should act like C.

The normal precedence conventions hold as shown in the tables below (Figure 2.6 and Figure 2.7).

2.13  BUILT-IN VALUES, FUNCTIONS, AND PSEUDO-FUNCTIONS

sin cos tan open close endoffile readbool

readint readfloat readstring writebool

writeint writefloat writestring allocate free

deallocate

2.13.1  Reads, Writes, and File Operations

There are three standard files: stdin, stdout, and stderr. Following Unix convention, these three are always considered opened when the program begins. Attempts to open or close any of the three are ignored.

1.  open. open has one argument, a string. This string designates the file to be opened and is interpreted as a Unix path. open returns one or two elements on the stack.

a.  If the top of the argument stack is true, then the next element on the argument stack is the file.

b.  If the top of the argument is false, the file failed to open; there is nothing else placed on the stack by open.

2.  close. close closes the file, its single argument, and leaves nothing on the stack.

3.  endoffile. endoffile takes a file as its argument and leaves as a Boolean value on the stack: true if the file is at its end; false otherwise.

4.  Read. The four read functions (readint, for example) have a file name as their argument; the result is left on the appropriate stack.

5.  Write. The four write statements take a file as their first argument and a value of the appropriate type as the second argument and returns the status (true if the write is successful; false otherwise) on the stack.