Contract grading is a simple concept: the exact criteria for a certain level of grade is spelled out beforehand. This course has milestones, participation, and a final exam. For a one-semester course, the contract matrix is shown in Figure 3.1. This contract scheme is dictated by the highest milestone completed. That is, if a student completes Milestone VI, attends every class, and gets 100 percent on the final, the student still can make no better than a C. Notice that there are no in-term exams; the milestones are those exams.

The milestones must be completed in order. The final grade on the milestones for final grade computation is predicated on the highest milestone completed. The milestone grading scheme is the following:

The purpose of the design information is to convince the instructor that the student wasn’t just lucky. By this, I mean that the student designed the milestone solution using some rational approach to solving the problem. Because the work breakdown structure (WBS) is an immediate requirement, at a minimum the student’s report should include a sequence of WBS sheets. As these sheets are in Microsoft® Excel, there is no particular burden to upgrading them; however, the student needs to show the progression of the design.

The second set of data is that pertaining to the management of the software development process using the spreadsheets provided and described in Chapter 11.

When we set about assessing the level of thinking that a student is using, we first think about knowledge. However, there is more to learning than knowledge—there’s general cognitive use. The levels of application are (lowest to highest) comprehension, application, analysis, synthesis, and evaluation. These levels are collectively known as “Bloom’s Taxonomy” (Bloom 1956). Higher-order thinking skills refer to the three highest levels; metacognition refers to higher-order thinking that involves active control over the cognitive processes engaged in learning.

Metacognition plays an important role in learning. Activities such as planning how to approach a given task, monitoring comprehension, and evaluating progress toward the completion of a task are metacognitive in nature. Because metacognition plays a critical role in successful learning, learn how to use metacognition in your professional life. While it sounds difficult, metacognition is just “thinking about thinking.”

In the milestone report, the student describes the processes that were used in developing the milestone. This includes saying what the student did right and what the student did wrong, or at least could have done better. If the student feels that he or she did something innovative, then the student should analyze that activity in the report. During grading, I look for the student’s discussion of “what I learned in this milestone.”

Part 1. Evaluate the arithmetic statements in Figure I.2. Caution: these statements are presented as someone might write them in a mathematics class and not in a computer science class. This introduces the concept of context or frame of reference. In particular, carefully consider the values of the last two expressions before you compute.

Part 2. Run the resulting code in Gforth.

Part 3. On one page only, write the algorithm that takes any infix statement into a postfix statement.

In Chapter 6 we introduce the concept of the metalanguage that enables us to talk about a language. We make use of that concept here. In Forth, words are defined in terms of a sequence of words and constants.

In order to discuss a language, for example Gforth, using another language, for example English, we must use the idea of metalanguage and object language. In our case, Gforth is the object language and English is the metalanguage. This gives rise to a convention concerning meta notation. We will use the angle brackets around a symbol to indicate meta-names. In this case, 〈Statements〉 means “zero or more statements.”

We use the term 〈ForthCompilableExpresssion〉 to mean any legitimate sequence of Forth words except a colon and a semicolon and 〈New Word〉 to indicate the word being defined. The syntax for a user-defined word in Forth is

Remember that you need blanks surrounding the colon (:) and the semicolon (;).

Now we’re able to use if and while statements as they normally appear in the C family. Using metavariables in the obvious way, we can define if and while as follows:

This case explores the two control structures, if and while. Here the postfix regime breaks down even further. We still can put the expressions into a tree, but we cannot evaluate everything: we can only evaluate the proper statements.

Before beginning this milestone, read Chapter 11. This chapter describes elementary project management processes for this project. The central focus should be the development of the WBS spreadsheet. Before attempting any milestone, the WBS relevant to that milestone should be included in the project management portfolio.

In order to start at a common place, Figure II.1 contains a skeleton WBS. Using this WBS, develop your own based on the cases in each milestone.

This milestone is the first of two that use formal language theory to specify the program to be written. In particular, scanners rely heavily on the finite state machine (FSM) formalism.

Because the formalism allows for complete specification of the lexicon, test case development is relatively easy. The grading points for this milestone are based on the fact that you should be able to test all cases.

The purpose of this milestone is to develop a working scanner from the lexical definitions. Scanners are supported by over 50 years of development; these techniques were used by engineers in the 1960s to design circuits. Sections entitled “Scanner Design” and “Scanner Design Extended” provide details.

This is the proper time to start the symbol table development. The only requirement is that the lookup routine be an open list hash table: the lookup must work in O(1). See the section entitled “Symbol Tables” for details.

Starting with this milestone, each milestone report will be accompanied by all design documentation along with your PDSP0, WBS, and time recording template (TRT) forms. The milestone report must include your FSM design, as well as your metacognitive reflection on what you did in the milestone and what you learned.

The lexical scanner rules are the same as C whenever a specific rule is not stated. For example:

The scanner reads in the program text and accumulates characters into words that are then converted into tokens. The scanner operates as a subroutine to the parser. The communication between the two is in terms of instances of tokens. The purpose of the token structure is to inform the parser of the terminal type of the token and the value associated with the token.

Conventionally, the scanner is designed using FSM concepts. The work of the cases is to design that machine. The possible tokens are defined by the lexical rules of the language defined in Chapter 5.

Read the specification documents and the parser and determine the various token classes that are required. Now develop a data structure for these tokens. Tokens are a data structure that contain both the “word” read from the input and an encoding of the terminal type. The word must be stored in its proper machine representation; that is, integers are not stored as strings of characters but in their 32-bit representation. Requirement: If you are using C, then you must define a union; in object-oriented systems you will need an inheritance hierarchy. You will develop some of the information for this case in Case 47.

Realize that the scanner is required to check constants for validity. As an example, a sequence of digits 20 digits long cannot be converted to internal representation in 32 bits. Therefore, this 20 digit number is illegal. Hence, the words are converted to their proper memory format for integers and floating point numbers.

Scanner Design

Finite State Automata

The finite state automata (FSA) (sing. automaton) paradigm is the basis for the design of the scanner. The FSA paradigm as described in theory texts has two registers (or memory locations) that hold the current character and current state. The program for the machine can be displayed in several standard ways. The graphical representation is easier to modify during design. The implementation program that is the scanner is written using the graph as a guide.

The graph in Figure II.2 represents a program that recognizes a subset of C variables. State N0 is the start state. If the machine is in the start state and it reads any upper- or lower-case alphabetic chararacter, the machine moves to state N1; the notation used in the diagram is consistent with Unix and editor notations used for regular expressions. As long as the machine is in state N1 and the current input is any alphabetic letter, a digit, or an underscore, the machine remains in state N1. The second arrow out of state N1 is the terminating condition. It should be clear with a moment’s reflection that the self-loop on N1 is characteristic of a while statement. With that observation in mind, the C code in Figure II.3 can be used to recognize variable names. By convention, the empty string symbol ϵ means that no character is needed for this transition.

To understand the programs, we must first understand the machine execution cycle. This is actually not much different from the cycle used in a standard computer.

MC1: The machine is in a state as indicated by the current state register. If that state is a valid state, then continue; otherwise go to step 5.

MC2: Read the next character from the input. If there is no next character, halt and go to MC5.

MC3: The program of the machine is a set of pairs (state, character). Search the list of valid pairs for a match with the contents of the current state, current input registers.

MC4: If there is a match, set the current state to the value associated with (current state, current input) and go to MC1. If there is no match, set the current state to an invalid value and go to MC5.

MC5: The machine has a list of special state names called final states. If, upon halting, the current state value is in the final state list, then the input is accepted; otherwise, it is rejected.

The theory of FSA describes what inputs are acceptable to finite state automata. To develop the theory, consider a formalization by asking what the various parts are. There are five:

1.  The set of possible characters in the input (Programming-wise, this is the type of input and of the current input register.)

2.  The set of possible state values in the current state register

3.  The full set of pairings of (state, character)

4.  The list of final states

5.  The start state

Part of the difficulty of studying such abstractions is that the formulations can be quite different and yet the actual outcomes are the same. For example, this same set of concepts can be captured by regular expressions, regular production systems, and state transition graphs. The regular expressions used in editors like vi and pattern matching programs like grep are implemented by an automaton based on the above definition.

For design purposes, the preferred graphical representation is that of a state-transition graph (ST graph). A state-transition graph is a representation of a function. In its simplest incarnation, an ST graph has circles representing states and arrows indicating transitions on inputs. Each of the circles contains a state name that is used in the current state. The tail of the arrow represents a current state, the character represents current input, and the head of the arrow names the new state.

ST graphs are representations of functions. Recall that a function has a domain and a range. In the ST graph, the domain and range are circles and we draw an arrow from the domain to the range. The arrow is weighted by information relating to the function. The ST graph is directed from the domain to the range. It is customary in finite state automata work to have an arrow with no domain as the start state and double circles as final states. If every arrow emitting from the domain circle is unique, then the transition is deterministic; on the other hand, if two arrows weighted the same go to different ranges, then the transition is non-deterministic. It is possible to write a program that emulates either a deterministic or non-deterministic automaton; for this milestone, let’s think deterministically.

The weight of the arc captures the functioning of the transition. Since FSA only need to indicate which character is involved, the graphs in texts are very simple.

Develop a finite state automaton for each class of lexical input specifications.

Modify your output of Case 9 to reflect the processing to save and convert characters to form tokens.

We now have a first design of our scanner. We need to now consider whether or not the design is worth anything. We will do this with two exercises.

For each of your ST graphs, annotate the nodes with predicates concerning the computation. Write down a list of test cases that can be used to show that your ST graph is correct. Using the predicates, choose representative test cases and interpret the ST graph and show that this test case is correct. Keep it Simple!

We have designed the scanner and we have seen that it can be used to design tests for the complete scanner. But this is only part of the milestone because we must translate the design into a program in your favorite programming language. To this point, we have been focusing on logical sequence of flow; but there are other issues, such as

This is where the WBS exercise is crucial.

In the WBS form (see Chapter 11), the critical exercise is to name every possible task that must be accomplished for the scanner to function. The more complete the decomposition (breakdown), the better. Ultimately, we must be able to estimate the number of lines of code that we will have to write. The hours needed to code a function is the number of lines of code divided by 2.5.

Produce a work breakdown structure for the scanner. Keep a record of how much time (earned value) you actually spend. Turn the work breakdown structure in with the milestone report.

Symbol tables are the heart of the information management functions in a compiler. At their core, symbol tables are database management systems. We will address the design of symbol tables in this manner.

Database Management 101

A database is a collection of data facts stored in a computer in a systematic way so that a program can consult the database to answer questions, called queries. Therefore, there are three fundamental issues in the design:

1.  What are the queries that the database is meant to provide information about?

2.  How is the data retrieved by a query?

3.  What is the actual data in the database and how is it turned into information?

A typical database has a basic layout as shown in Figure II.5.

Many different design disciplines have been proposed over the years based on underlying data organization (trees or directed graphs) or query formation, such as the relational approach. These disciplines are often suggested by the principal uses of the database system, the so-called “enterprise” model that must satisfy a divergent user population. We don’t have that problem: the compiler is the sole user, so we can design the system to be responsive to a limited set of data and queries.

The generic symbol table has three basic considerations: (1) a hash function to convert keys to integers; (2) a collision maintenance system; and (3) a variety of data structures, one for each use. A given key may have more than one data structure associated with it.

Design and implement a symbol table system for this milestone. The symbol table for this milestone must identify keywords such as let as keywords.

You are to develop the following:

The trees will be used eventually to fulfill future milestones. For this project, you are to demonstrate that your parser can (1) properly process correct inputs and (2) reject incorrect inputs. You want to keep the print subroutine as a debugging aid for later in the project.

The project grammar is given in the specifications.

The motivation for formal languages is natural language, so the initial concepts are all borrowed from natural language. Grammars describe sentences made out of words or symbols. Both V and T are sets of such words or symbols.

A language would be all the sentences that are judged correct by the grammar: this is called parsing. Technically, we define the Kleene closure operator A* to mean zero or more occurrences of a string A. This notation is probably familiar to you from the use of regular expressions and as the “wildcard” operator in denoting file names. If A is a set, then A* is every possible combination of any length. If T is the set of all possible terminal symbols, then T* is the set of all possible strings that could appear to a language, but not all may be grammatically correct.

Which strings of T* are the “legitimate” ones? Only those that are allowed by the rules of P. So how does this particular description work?

A sentence is structured correctly if there is a derivation from the starting symbol to the sentence in question. Derivations work as shown in this example. Productions are rewriting rules. The algorithm works as follows:

This certainly is not very efficient, nor easy to program for that matter, but we will address that later.

We use the ‘⇒’ symbol to symbolize the statement “derives.” That is, read “A ⇒ B” as “A derives B.”

Now for an example. Is “1+2*3” grammatically correct? See Figure III.3

After studying the rules we can find a direct path. See Figure III.4. So, yes: “1+2*3” is grammatically correct. But I made some lucky guesses along the way. But programs can’t guess; they must be programmed.

Notice that the parse given in Figure III.5 is not the only one. For example, we could have done the following:

$\begin{array}{l}E\Rightarrow T+E\\ \Rightarrow T+F*T\\ \Rightarrow T+F*F\\ \Rightarrow T+F*3\\ \Rightarrow T+2*3\\ \Rightarrow F+2*3\\ \Rightarrow 1+2*3\end{array}$

In order to keep such extra derivations out of contention, we impose a rule. We call this the leftmost canonical derivation rule (LCDR): expand the leftmost nonterminal symbol first.

We could describe the FSA representation lexical rules by productions developed by the following rules:

The second requirement is to move the functions from the ST graphs. The convention that has evolved is that we write the productions as above, then enclose the semantic actions in braces.

In effect, we have laid the foundations for a very important theorem in formal languages: every language that is specifiable by an ST graph is specifiable by a grammar. The content of the theorem is that many apparently different ways of specifying computations are in fact the same.

Remember the idea of a derivation:

$\begin{array}{l}E\Rightarrow T+E\\ \Rightarrow T+F*T\\ \Rightarrow T+F*F\\ \Rightarrow T+F*3\\ \Rightarrow T+2*3\\ \Rightarrow F+2*3\\ \Rightarrow 1+2*3\end{array}$

The derivation induces a tree structure called a parse tree. When thought of as an automaton, the tree is the justification for accepting any sequence of tokens. Thought of as a machine, however, the tree is not the whole story.

The productions define a function that does two things: it recognizes syntactically correct inputs and it can compute with the inputs. Instead of the simple derivation above, we can think about tokens for the terminals and values for the categorical symbols. For this discussion to make sense, follow the LCDR. The LCDR requires that the parse be done by always expanding the leftmost categorical symbol. We do this in a top-down manner. Such a parser is called a predictive parser or, if it never has to backtrack, a recursive descent parser. Let’s try this idea on 1 + 2 * 3. In order to make it clear that this is a production system parse, we enclose the nonterminal symbols in angular braces 〈·〉. The symbolic name is on the left and the semantic values are on the right. The symbol ⊥ read “bottom,” stands for the phrase “no semantic value defined.” See Figure III.6. Line 3 contains the first terminal symbol that is not an operator. The relevant production is

$F\to \text{any}\text{integer}I\{\$\$=atoi(\$1)\}$

In words, it says, “the next input is an integer. Recognize it. If the integer is recognized syntactically, then perform the function atoi on the token $1. If the conversion works, assign the result to $$.”

The parser returns to the previous level, so we have the F replaced by T. The parser now predicts that the atom 〈atom, +〉 is next. When the parser sees the ‘+’, it reads on.

Repeating the same reasoning, we end up with a final string of

$\langle T,\langle \mathit{int},\text{1}\rangle \rangle \langle \mathit{atom},+\rangle \langle F,\langle \mathit{int},\text{2}\rangle \rangle \langle \mathit{atom},\text{*}\rangle \langle F,\langle \mathit{int},\text{1}\rangle \rangle$

and we start returning. We return to a level that has the ‘*’ in it. The correct computation takes the 2 and 3 and multiplies them. So we get

$\langle T,\langle int,\text{1}\rangle \rangle \langle atom,+\rangle \langle T,\langle int,\text{6}\rangle \rangle$

We can now compute the last operation and get 7. So

$\langle E,\langle int,\text{7}\rangle \rangle$

is the final value.

The conversion (compilation if you will) we want to make is between the production system and a typical programming language. The background is based on work on the Chomsky Hierarchy. The Chomsky Hierarchy is a sub-theory of the theory of computation that indicates what abstract computing models are equivalent in the sense that programs in one model produce the same outputs as a particular algorithm specified in other models. In this case, we are interested in two models: production systems and recursive functions. All current programming languages are examples of recursive function systems. Therefore, we will make the task one of going from the formal definition of production systems to some sort of programming language.

We know that there are four parameters in the grammar: N, T, G, S. Consider now trying to write a program. What is being specified by N, T, G, and S ? The key to Subtask 1 is to understand that the categorical symbols (symbols in N) are really the names for programs and that the programs implement the rules in G.

Type checking is the first step in semantic processing. We can again use a production system schema, but this time we will pattern match on node content. Designing the type checker requires that we enumerate all the possible legitimate patterns we might see; other patterns encountered constitute type errors.

If we had only constants and primitive operations in SOL, then we could easily generate the Forth input by traversing the tree in postorder. However, this would not be very usable because we would not have variables or user-defined functions. Once we introduce variables and functions, we introduce the need to know what types of values can be stored in variables and what types of values can be used with functions. These points introduce the need for types and type checking. If this were a language like C, then we would now have to do several things:

The first two are not necessary in SOL because the syntax of the language is so simple, but we will have to elaborate the symbol table information.

The type checker produces (possibly) new trees based on decisions made due to overloading of primitive operators and polymorphism in user-defined functions. This decision logically goes here since the type checker has the correct information in hand at the time of the decision.

The milestone report should concentrate on the development of the program. It must include a copy of your formal design documents.

The importance of types was not appreciated in assembler or early programming languages. Starting in the late 1960s and early 1970s, programming languages included formal mechanisms for inventing user-defined types. ML was the first language to emphasize types and its initial proposal is attributed to Robin Milner. The extensive use of types is now a hallmark of functional languages, whereas the C-based languages are somewhere in-between.

The concept of types originated with Bertrand Russell (1908) as a way out of his famous paradox in set theory. Various uses of type theory have evolved since then, with its use in logic being the most like that of programming languages. A type T is a triple (T, F, R) where T is a set of objects, F is a set of functions defined on T, and R is a set of relations defined on T. In what is known as an “abuse of language,” the name of the type T is the same as the name of the set in the definition. This abuse is often confusing to people first learning programming.

We shall not be interested in the theory of how such types are developed and justified. However, since we are developing a functional language, we must understand how to tell whether or not an expression is well formed with respect to types. For example, we would normally say that an expression such as 5 + “abcd” is incorrectly typed primarily because we cannot conceive of a sensible answer to the expression. When all is said and done, that is the purpose of types: to guarantee sensible outcomes to expressions.

Types come naturally from the problem that the program is supposed to solve. Types in programming are conceptually the same as units in science and engineering. A recent mistake by NASA illustrates the importance of each of these ideas.

The Mars Climate Orbiter was destroyed when a navigation error caused the spacecraft to miss its intended 140–150 km altitude above Mars during orbit insertion, instead entering the Martian atmosphere at about 57 km. The spacecraft would have been destroyed by atmospheric stresses and friction at this low altitude. A review board found that some data was calculated on the ground in English units (pound-seconds) and reported that way to the navigation team, who were expecting the data in metric units (newton-seconds). Wikipedia.

In this case, units play the same role as types.

As data structures become more complex, the type system becomes more important. Early programming languages had little or no support for types. Early Fortran and C compilers assumed that undeclared variables were integers and that undeclared functions returned integers. In fact, Fortran had a complicated system of default types based on the first letter of the name.

The programming language ML was originally developed in about 1973 at Edinburgh University for the research community as part of a theoremproving package called LCF (Logic of Computable Functions). Syntactically, ML looks very much like an earlier language, Algol. The Algol language may have had more impact on programming languages than perhaps any other. Two versions of Algol came out close to one another, in 1958 and 1960. A third came out in 1968 that would be the last, but even Algol 68 (as it was known) had a lasting impact on Unix: the Bourne shell. ML demonstrated that a strongly typed programming language was practical and efficient.

Using the resources available to you, develop a short history of Algol and ML. Also, develop a list of areas these languages impacted and continue to impact today.

Like SOL, ML allows the programmer to define types that are combinations of primitive types, user-defined types, and type constructors. ML does not require the user to type declare user names because the compiler is able to infer the correct type—a good reason to use languages such as ML.

ML is a strongly typed language, meaning that the compiler type checks at compile time and can reliably infer correct types of undeclared names. This is decidedly different from languages such as Fortran and C that require the user to declare types for all names. Eventually, SOL will be strongly typed, but our project does not require us to develop the algorithm to produce the correct inferences. For this milestone, we will consider type coercion but not polymorphism. (Ah, but coercion is a type of polymorphism.)

ML supports polymorphic functions and data types, meaning that you need only define a type or function once to use it for many different data or argument types, avoiding needless duplication of code. This gain in production is from the use of type variables; C++ templates are a poor substitute for type variables. C has no such capability: each such need requires that you write the code and that you name the code uniquely. Java’s polymorphism would require many methods, each taking different data types and performing similar operations. In other words, C-type polymorphism (C, C++, Java, among others) provides no help in development, requiring the programmer to design, develop, and manage many different aspects that the compiler should be doing.

ML also provides support for abstract data types, allowing the programmer to create new data types as well as constructs that restrict access to objects of a certain type, so that all access must take place through a fixed set of operations. ML also allows for type variables, variables that take on types as their values. ML achieves this through the development of modules and functors.

The original development of ML was spurred by the need to have a complete type system that could infer correctly undeclared names. This type system is completely checked at compile time, guaranteeing that no type errors exist in the resultant code.

Research the ML type system using resources at your disposal. Report on three aspects of the system:

The first version of SOL must imitate the type checking used by C. Since C is so common, we leave it up to the designers to find the detailed rules. Detailed information on designing rule-based systems is given in Chapter 8.

The metalanguage for type checking is that of logic. Type checking is about inference, which is inherently rule-based. Modern expositions in logic use a tree presentation. The presentation of the rules follows a simple pattern. You know that logic revolves around the if-then schema: if A then B. This would be displayed as

$\frac{A}{B}MP$

In the context of type and type rules, an example would be for plus.

$\frac{\text{integer}\text{integer}}{\text{integer}}+\text{integer}$

Every possible combination of types for any given operator must be considered. Every legitimate combination of types must have a rule and every illegitmate combination must have a rule describing the error action or correction.

A simple approach to analyzing and developing these rules is to develop a matrix of types. We have a very simple type system to consider initially: bool, integer, float, string, and file. Every unary operator must be considered with each type; every binary operator must be considered with each pair of operators.

Develop a matrix of types as described above. In each element of the matrix, write the correct Forth conversion statement. For incompatible elements, write a Forth throw statement.

In SOL, the standard operators are overloaded, meaning they automatically convert differing types into a consistent—and defined—type, which is then operated on. This feature follows mathematical practice but has long been debated in programming languages. Pascal did not support automatic type conversion, called mixed-mode arithmetic at the time. SOL does support mixed-mode expressions (just like C); therefore, the design must include type checking and automatic conversion. Because of overloading, there are implicit rules for conversions. The design issue is to make these implicit rules explicit.

Standard typography in textbooks as described above does not have a standard symbology for this automatic conversion. Therefore, we’ll just invent one. It seems appropriate to simply use functional notation. All the type names are lower case, so upper-case type names will be the coercion function. This doesn’t solve the whole problem, since it must still be the case that some conversions are not allowed.

As an example,

$\frac{\text{FLOAT}\text{(integer)}\text{float}}{\text{float}}+\text{integer-float}\text{conversion}$

Such a rule is interpreted as follows. An example to work from is [+ 1 3.2]. The implicit rule requires that the integer be converted to a float. We note that by having FLOAT(integer).

An example of something that should not be allowed would be

$\frac{\text{FLOAT}\text{(integer)}\text{float}}{\text{float}}+\text{integer-float}\text{conversion}$

Because the SOL language is a functional language, virtually every construct returns a value: the if statement, for example. Therefore, the entire expression must be checked, starting with the let and the type statements. Did you notice that there is no return statement? Type checking SOL is far more complicated than checking simple arithmetic statements because the if statement can only return one type. Therefore, [if condition 1 2.0] is improperly typed.

In order to design the whole type checker, you will have to resort to a design technique known as structural induction. Structural induction requires that we develop a tree of all the subexpressions that make up an expression. For example, what are all possible expressions that can start with a let? Here is a partial analysis.

There could be no, one, or many arguments, of course.

The point here is that you must develop a recursive function that can traverse any proper input: this is the reason to develop the printer program in the parser milestone. This printer program is the scheme for all the other milestone programs.

It is simple to read the input if you do not try to put any semantic meaning onto the result. Such processing will not work for type checking because the type checking rules are driven by the form and content of the structures. In order to design the type checker, you must first describe the possible structures through structural induction.

Using the grammar from Milestone III, and using substitution, develop a design of the type checker, making each “nonterminal” a recursive function.

The algorithm for the type checker is more complicated than the parser. The parser is not comparing the structure to another structure, whereas the type checker is checking an expression against a rule. For example, consider the question of whether or not [+ 1 2.5] is correctly typed.

In order to discuss the problem, we first have to realize that there are different addition routines, one for each possible combination of allowed arguments. Say there are three allowed arguments: bool, integer, and float. This means there are nine possible combinations of arguments for ‘+’.

While we may want to consider bools in the arithmetic expressions, should they be allowed? Mathematical convention would argue for inclusion.

Regardless of the outcome of the above case, there is more than one possible legitimate argument type situation. Suppose we decide that bools should not be used; then there are still four separate possibilities, given in Figure IV.1. We can take advantage of Forth’s flexibility in word names by defining a unique operator for each pair. For example:

This is simple enough for each element in the type conversion matrix.

Let’s consider how the full type checking algorithm should proceed.

This algorithm is a simplifed form of the unification algorithm, the fundamental evaluation algorithm used in Prolog. The above algorithm is much simpler because we do not have type variables as do ML and the other functional languages.

The type checker will rely on the symbol table to produce the list of possible functions that can be substituted for a₀. This case and the next should be completed together, because the two solutions must be able to work together.

For the symbol table, develop a data structure for the operators. Keep in mind that when we introduce user-defined functions, they will have the same capabilities as the primitive operators.

Along with the data structure, you must develop a process to load the symbol table initially. For hints, consider how the SOL type definition process works by consulting the specification.

On approach to developing the unification algorithm, you need really only consider a few cases. One specific case is

Based on these cases, develop the search algorithm and complete the design of the symbol table.

The principal formal concept in this milestone is the use of structural induction, discussed in Chapter 6. As with the parser and type checker, the general principle is the production system schema: pattern match to guarantee consistency, then application of a transformation.

We are now ready to produce a minimal compiler. We have developed the parse tree and we can print that tree; the outline of the printer routine is the basis for this milestone. We now finish the first development cycle by adding a code generator.

The type checker has constructed a tree that is type correct. In the previous milestone, the type checker chose the correct polymorphic routine name.

For this milestone, you generate Forth code and run that code to demonstrate the correctness of the result. Your tests must show that the operations correctly implemented based on their customary definitions in boolean, integer, floating point, string and file operations. A basic approach for testing these primitive operators is to choose simple values that you can calculate easily. It is not a valid test case if you can’t predict the result ahead of time. Therefore, you should keep the following in mind: keep the test statements short.

For the most part, this milestone is a straightforward binding exercise: choosing which word to bind to the SOL operator of a given type. This is primarily an exercise in loading the symbol table with correct information.

The details of the primitive operators are given in Figures V.1, to V.5. The special values are listed at the bottom of Figure V.5.

One nontrivial issue is the full development of string support. The formal concept here is CRUD: creating, reading, updating, and destroying strings. Creating and destroying string constants introduces two storage management issues: (1) obtaining and releasing memory and (2) knowing when it is safe to destroy the string.

This is the appropriate place to implement if and while statements. Admittedly, the testing is fairly trivial, except for the while; complete testing of the while must wait.

The milestone report should concentrate on the development of the program. It must include any design decisions that you make that are not also made in class; all such decisions should be documented by explaining why the decision was made.

The concept of scope is intimately connected to the concept of visibility of names and with storage management. Storage management issues are discussed in detail in Chapter 10. Scope rules determine how long a name is bound to a value.

Specifically in SOL, there are several types of scoping environments inherited from most block-structured languages such as C. For this milestone, we have the following scope protocols:

The function header scope is discussed separately because it is a composite of file scope and body scope.

Consideration of scope comes from considering the binding time of a name with its definition. In the simple programming language context, a name can only have one active binding at a time: otherwise, there is ambiguity. We should note that multiple inheritance in object-oriented languages such as C++ introduces ambiguity. Therefore, binding time requirements lead to the need for scoping. What properties should scope have?

The original idea of scope and binding time came from logic. The introduction of quantifiers by Pierce, Frege, and others in the 1880s introduced the problem of name-definition ambiguity. The basic issue in logic is the nesting and duration of definitions. Programming adds another dimension: storage. Whenever a name is defined, there is some consequence for memory management. Although individual routines are accounted for at compile time, variables have other issues, such as access and duration of a value. All nonpersistent, local storage must be reclaimed when the execution leaves the scope.

For each of the scope protocols listed above, determine the consequences for memory management. Do this by displaying a table (as shown in Figure VI.1) that lists the rules for each possibility.

Two different approaches come to mind on how to handle the nesting of scopes. One would be to have a separate symbol table for each scope. The second approach would be to make the symbol table more complicated by keeping track of the scopes through some sort of list mechanism. One such mechanism would be to assign a number to each different scope and use the number to disambiguate the definitions. This approach keeps a stack of numbers. When a scope opens, the next number is placed on the stack; when the scope closes the current number is popped and discarded. Every definition takes as its scope the number at the top of the stack.

Use each of these approaches in a design and determine the running time (“Big O”) and the space requirements for each. From this, make a decision on which approach you will use in this milestone.

Develop a simple SOL program that is comprised only of integer arguments and integer variables; three of each should be sufficient. Now write several arithmetic operations that compute values and store them in local variables. Write the equivalent Gforth program. Use this experience to develop the “simulator” needed to compile code.

The basic issue facing the compiler in this milestone, then, is the simulation of the stack. In order to simulate the stack, you must have a list of rules of the effect of each operation on the stack. This is actually a straightforward exercise: develop a table that lists the operations on the rows and stacks information across the columns.

Develop a stack effect table using the following outline as a starting point:

$\text{Operation}|\begin{array}{l}\text{Input}\\ \text{Argument Floating}\end{array}|\begin{array}{l}\text{Output}\\ \text{Argument Floating}\end{array}$

Your design should designate operations for all defined operations, including those you may have introduced to simplify type checking.

Once the table is complete, study the resulting pattern of operations. There are relatively few unique patterns. A simple approach to the problem of looking up what pattern to use is to extend the information in the symbol table to include the stack information.

The principles invoked in this milestone are the relationship of the λ-calculus and program evaluation.

We now have a complete compiler, but not a very usable one because we do not have functions. You must now include the headers for functions, arguments, and return types. We use the specification for the syntax and use your understanding of programming to produce the semantics.

The milestone report should concentrate on the development of the program. It must include a copy of your formal design documents.

Chapter 9 describes the fundamental theoretical understanding of functions and function evaluation: the λ-calculus. Some languages, such as ML and OCAML, use the descriptive term anonymous function to describe the role of the λ-calculus: to describe function bodies. But how does one bind the λ-expression to a name?

This actually brings up a deeper issue: How do we think about binding any name to its definition? The basic approach is not unlike normal assignment in a program. For example, in the C statement int a = 5; we think of the location denoted by a as naming the location of integer 5. Does this work for functions? For example, how can one rename a function? How about

If we then write newsin(M_PI/4) do we compute sin π/4? Of course.

We’re almost there. Suppose we don’t want the value of newsin to be changeable. Again in C, the way to do that is to use const in the right place.

The purpose of this exercise is to demonstrate function names are nothing special, but before we finish this investigation, what is happening in terms of the λ-calculus? What is sin in terms of λ-calculus? Without investigating algorithms to compute the sine function, we can at least speculate that the name sin is a λ-expression of one argument. In other words, the assignment of sin to newsin is simply the assignment of the λ-expression.

The problem is type. Chapter 9 does not explore the issue of types, leaving it intuitive. The λ-calculus was introduced to explore issues in the natural numbers and integers. The development of the expanded theory came later but, for our purposes, can be seen in such languages as Lisp, ML, and OCAML. Types are bound to names using the colon ‘:’. Thus,

directs that the argument x is an integer and that the result also be an integer.

Early in the history of computer science, special status was accorded to recursive functions. Generally, recursive functions were treated as something to avoid, and often were required to have special syntax. C went a long way to change that since it has no “adornments” on the functions header. We take this approach in SOL: all functions are by nature recursive.

This approach works fine for the naïve approach, but is not suitable to the theoretical underpinnings. In the theoretical literature, the following issue raises its head:

$\begin{array}{l}letfibonacci\text{(}n\text{)}=\lambda n\text{.}\\ ifn<\text{2 }then1elsefibonacci\text{(}n-\text{1)}+fibonacci\text{(}n-\text{2)}\end{array}$

Notice that there are three instances of the word fibonacci, one on the left and two on the right. Question: How do we know that the one on the left is invoked on the right? Answer: Nothing stops us from the following:

$\begin{array}{l}letfoobar\text{(}n\text{)}=\lambda n\text{.}\\ ifn<\text{2 }then1elsefibonacci\text{(}n-\text{1)}+fibonacci\text{(}n-\text{2)}\end{array}$

in which case foobar(2) is undefined. For this reason, languages based on the λ-calculus have a second let statement. This second statement is written letrec; the letrec guarantees that the recursive name is properly bound. In keeping with this convention, extend SOL to include letrec.

Functions add three issues to the implementation: (1) passing of arguments, (2) the return of computed values, and (3) storage management. It should be clear that the stack is the communications medium.

The protocol for passing arguments is not particularly intricate for a simple implementation such as ours. Because of the ability to type arguments, there should be no type mistakes. You will have to develop rules for arguments that must reside on different stacks, such as the argument and float stacks.

Write down the rules for passing arguments of the primitive types. One issue to address is the question of what the stack state(s) should be and when the final states are assumed.

Returning values is more complicated than passing because the calling routine must retrieve those values and dispose of them properly, leaving the stacks in their correct state. Potentially, there could be many return values for a given call. However, if you think about it carefully, you can see that returning values is not completely unlike passing arguments.

Modify the protocol for passing arguments to include the return protocol. For this initial compiler, assume that only one return value is possible.

What will you do if there is no return value?

The methods and values of this milestone harken back to the days when assembler languages were all we had. In assembler language, all processing is carried out by the programmer. Designing, implementing, and manipulating complex data structures at the assembler level are fraught with issues requiring complete concentration. Users of modern programming languages have extensive libraries for manipulating standard data structures (such as C’s stdlib). However, such libraries cannot fulfill all contingencies; therefore, compilers must support user-defined complex structures.

We now have a complete compiler, including functions, but we do not have facilities for user-defined complex data. We use the specification for the syntax and now use your understanding of programming to produce the semantics, primarily the semantics of pointers and pointer manipulation.

The milestone report should concentrate on the development of the program. It must include a copy of your formal design documents.The metacognitive portion should address your understanding of the semantics of the constructs.

Chapter 10 describes the fundamental operations for defining and accessing complex storage structures. The concepts are

In Chapter 10, we develop formulas to calculate the location of an element within an array. The ideas are encapsulated in the C program (shown in Figure VIII.3) with output shown in Figure VIII.1.

The same schema works for structures, except that the computation of the offset is more complicated. As an example, look at the C program shown in Figure VIII.2. From this, we can infer that the offsets computed and then added to the base pointer (char*)(&blspace) is the same as using the more familiar “dot” notation.

The SOL syntax makes it easy to develop support for complex data. We can use the type checker to ensure we have the right number of indices as well as taking an interesting view of complex data. To do that, we must make arrays fully functional. First, recall the CRUD acronym for developing data.

Array Development

1.  Creation. The creation of an array requires (a) computing the size of the array as discussed in Chapter 10 and (b) allocating the space through the operating system. A straightforward function for this would be [createarray type dimension₁ … dimension_n].

2.  Reading a value from an array. We have illustrated the concepts of reading a value in both Chapter 10 and earlier in this milestone. Reading a value means (a) computing the offset, (b) computing the address from the base address, and (c) moving the data from the array. The following syntax suffices: [getarray array dimension₁ … dimension_n.

3.  Writing a value into an array. Writing (“putting”) a value into a location of an array is almost identical to reading, except that the new value must be part of the function [putarray array value dimension₁ … dimension_n.

4.  Destroying an array. Since we use the operating system to allocate the space for the array, it is only natural to use the operating system to deallocate (“destroy”) the data—something like [destroyarray array].

However, far more interesting is the question of when it is safe to destroy such a structure. Java has one answer: garbage collection. We do not pursue garbage collection here, but the serious reader should consider the subject (Jones and Lins 1996). For our application, we leave this decision to the programmer.

Read the ANS specification for Forth. Using this as a guide, develop the semantics of SOL’s support for structures.

We now have a complete compiler with functions and complex data. All of the development so far makes it possible to implement classes.

The milestone report should concentrate on the development of the program. It must include a copy of your formal design documents.

In software engineering, encapsulation means to enclose programming elements inside a larger, more abstract entity. Encapsulation is often taken as a synonym for information hiding and separation of concerns.

Information hiding refers to a design discipline that hides those design decisions that are most likely to change, protecting them should the program be changed. This protection of a design decision involves providing a stable interface that shields the remainder of the program from the implementation details. The most familiar form of encapsulation is seen in C++ and Java; however, polymorphism is a form of information hiding, also. Separation of concerns is the process of partitioning a program into distinct features. Typically, concerns are synonymous with features or behaviors.

Until the advent of structures, and especially structured programming, in programming languages, all names visible in a scope were visible everywhere in that scope. Structures altered that by making field names invisible within a scope and requiring a special dereferencing operator (the “dot”) required. The next step was taken when classes encapsulated names, meaning that some names could only be referenced from within the class. In this sense, encapsulation is a form of information hiding because private names (they could be functions or variables) are a form of design decision that could change if the algorithms change. One step toward objects is easy—make the symbol table associated with a structure unusable outside the structure.

In the programming language context, inheritance is a mechanism for forming new classes of data using previously defined classes and primitive data types. The “previously defined” classes are called base classes and the newly formed classes are called derived classes. Derived classes inherit fields (attributes) from the base classes. The attributes include data definitions, sometimes called state variables, and functional definitions, often referred to as methods. An unfortunate asymmetry exists in many object-oriented languages in that primitive data types such as C ints do not participate unchanged in inheritance. In these cases, the primitive type is “wrapped” with a class definition.

Inheritance is a method of providing context to state variables and methods. This context is always a rooted, directed acyclic graph (DAG). If only single inheritance is allowed, then the rooted DAG becomes a rooted tree. Examples are obviously Java (single) and C++ (multiple).

A consequence of the inheritance hierarchy is that the same method name can occur in many different classes. If all these definitions were in the same visible definition frame, then there would be chaos; one would never know which definition would be used.

This sort of problem actually does exist: overloaded arithmetic operators. Overloading allows multiple functions taking different types to be defined with the same name; the compiler or interpreter “automagically” calls the right one. The “magic” part means that the compiler has a rule for choosing; unfortunately, overloading falls apart quickly. Parametric polymorphism, on the other hand, works by matching the function based directly on the types of the inputs. How this works requires an excursion into types.

The type checker, Milestone IV, is not very interesting as type systems go. In adding arrays and structures in Milestone VIII, we still had not deviated much from the C type system. We gain a hint of what is desired by looking at C++’s templates. Actually, the concept of parametric types is quite old, going back to the 1930s. The problem we want to solve notationally is illustrated by the concept of lists. In direct manipulation of lists, the actual internal structure of the elements is irrelevant because we do not—and do not want—to manipulate the information of the elements. Therefore, the actual type of the element is irrelevant and can be anything. This suggests that the type of the elements can be a variable.

This stronger (than C) type theory goes by several names: intuitionistic type theory, constructive type theory, Martin-Löf type theory, or just Type Theory (with capital letters). Type Theory is at once (1) a functional programming language, (2) a logic, and (3) a set theory.

The notation used in the literature is based on the λ-calculus, except the arguments precede the type name. In the theoretical literature, type variables are written as lower-case Greek letters. Using ML, array is a type; since we don’t have Greek letters on English keyboards, arguments are names preceded by the reverse apostrophe. Here are some ML examples:

In ML, arrays do not carry their dimension as part of the type, which is determined at runtime. ML does not have a separate notation for array indexing, either. Despite this, ML arrays are useful data structures just as C.

The useful nature of type variables allows us to express data structure types algebraically, leading to work in category theory and algebraic specifications.