We have been studying language, both natural and formal. Formal languages are languages that have completely specified syntax and semantics. What we believe at this point is that programming languages are not all that different from natural languages in their overall concepts. We should expect that programming languages have the same parts (Figure 7.2): although syntax deals with the overall appearance of the language, the meaning of the words is the purview of semantics; informally semantics has taken on the meaning of “meaning of a phrase or sentence.” Regardless, there must be a lexicon and a vocabulary. The lexicon is the entire set of words, whereas the vocabulary is words and definitions. We also have studied semantics in terms of its relationship to the deep structure of a statement.

From a project management standpoint there are some questions: who, what, when, where, why, and how are each of these different parts defined?

Write a story about how the sentence, “The cat ate the hat.” is understood using the phases listed in Figure 7.1. In linguistics and logic, we speak of the binding time of a word. The binding time is the moment when the definition of a word is assigned. In an abuse of language, we can extend this concept to relate to the assignment of meaning for any element: word, phrase, sentence, paragraph, …. When are the meanings of the five words bound? When is the meaning of the sentence bound?

Meaning is not something that just happens: it occurs as we read the sentence. We can only understand the meaning of the sentence when we understand the meaning of the underlying words, phrases, etc. The same must happen in the compiler.

Develop a time line representation of the translation of a C statement x = 1*2+3 into the Forth statement 1 2 3 * +. Annotate the time line with the phases in Figure 7.1. When is the lexicon consulted? How is the vocabulary used?

When you study the assembly language for a computer (not just the chip) it is apparent that the vast majority of instructions manipulate various data types: integers, floating point numbers, information to and from devices, among others. It would be difficult to move a program from one computer to another if there were not some organization to this data and some agreement on what various operations are called. This organization is called data types or just types.

In order to explain types, let’s look at the quintessential type: integers. Everyone knows about integers; everyone knows that “+” is read “plus” and stands for the operation “take two integers and sum them giving an integer as a result.” Everyone also knows that “<” is read “is less than” and stands for the condition “one number is less than another number, giving a true or false answer.” Everyone also knows that “if a is less than b and b is less than c, then a is less than c.”

For our purposes, we can start by defining a type as a triple of the form 〈S, F, R〉, where S is a set of constants, F is a set of function symbols, and R is a set of relation symbols.

$\text{Integers}=\langle intergers,\{+,-,\dots \},\{=,\ne ,<,\dots \}\rangle$

It should be clear that S, F, and R determine the lexicon for integer expressions (without variables). The harder part is to develop algorithms for each element in F and R.

Develop a type definition for each of the standard types: booleans, integer, floating point, and strings.

In this chapter we have laid the groundwork for the project. We have a time line of who, what, when, where, and why elements of a statement are processed and given meaning. This is the fundamental step in any project. We are missing the how for many of these steps. The purpose of the Milestone chapters in Part I is to fill in the how and to implement a simple compiler that takes simple statements to Forth.

In order to understand the requirements in the milestones, we need to understand the overall issues in a programming language.

Use the form given in Figure 7.4 to develop the details needed. Some language elements may have entries in all columns, some may not. Note: The semantics column must reference a Forth word in the table and that word must be defined below the table.

Each symbol with semantic meaning must be in the table. From a practical standpoint, it is probably best to start with the various primitive data types and operations.