History
This post hatched from a chicken or egg problem that I encountered while trying to teach students about computer programming at Valley Catholic High School.
In the first quarter of VCHS’s 2018-2019 offering of the two-semester AP Computer Science X courses, where X ∈ {A, Principles}, we studied the notion of an algorithm and got acquainted with some basic programming techniques via a simulated mythical computer called TOY. Although I can’t speak for my students, I will say that I enjoyed introducing them to programming using TOY’s low-level machine language. Bits, number bases, memory, addresses, objects, references — these are challenging concepts for beginners to grasp. Trying to comprehend them and appreciate why they matter is especially difficult when one has no idea what a computer is doing when it executes a computer program written in a high level programming language. And those things do matter — a lot!
Sadly, the time had come to stop playing around with TOY so we could focus primarily on learning to program using some serious(ly) high-level languages. Our new mission was Java (foisted mainly upon those of us in AP Computer Science A by the College Board) and/or JavaScript (foisted upon my students by me).
It was still early in the second quarter. We had just wrapped up a programming project, surreptitiously nested inside of which was a survey of the reserved words of a few popular programming languages including Java and JavaScript. That seemed like something worth crossing off the bucket list sooner rather than later, since we need to know which words are off-limits as we go about choosing names for things like variables, functions, classes, and methods. (Naming a newborn Fire or certain other four-letter words would be a very bad idea and might even be illegal in some states.) In the process, we gained more experience using the fundamental flow-control mechanisms provided by the frequently used keywords if and else.
ASIDE: Our study ofifandelsehad so far been neither very formal nor complete. Breaking out of the body of a labeledifstatement, for example, was something that would not be discussed until we got around to breaking out of loops.
Besides trying to promote practical procedural/imperative knowledge that programmers require to practice their craft, I also try to dish up nutritious servings of descriptive (or declarative/propositional) knowledge about the art of computer programming so that we can not only do but also understand what we are doing and talk about it intelligently using good terminology. Doing leads to understanding. On the other hand, a solid understanding of the facts can lead to better doing. Which should come first: students practicing procedures, or teachers declaring propositions? I could go either way. More important than which comes first, it seems to me, is that the practice and preaching (and reading!) alternate at a nice frequency.
We had arrived at a point, just before the annual Thanksgiving break, where I felt like it was my duty to do a little preaching. The sermon du jour: Expressions. No, not the look on students’ faces when I administer an exam. The other kind. You know — the kind involving operations, operators, prefix, infix, postfix, operands, terms, evaluating, types of, order of operations, precedence, etc. After evaluating where we were at and thinking about where we should go next, I figured it was time to have a serious talk about and get some good practice with expressions, which if statements and loops pivot around.
The Road to Ruin is Paved with Bad Expressions
A meaning of the other phrase* is that “individuals may have the intention to undertake good actions but nevertheless fail to take action.”
Under particular conditions, a programmer may (or may not) intend for a statement or block of statements to be executed. But if the expression that determines which course of action the program will take under those conditions is formed incorrectly, then the program might not behave as intended. And it’s not just conditionals that are at stake. Any value — the value of a variable, an argument passed to a subroutine, the value returned by a subroutine — may be represented by an expression. In fact, all values are expressions, since an expression may consist of nothing more than a single literal value. It’s imperative, therefore, that programmers learn how to read and form expressions correctly.
In the same way that programmers must be familiar with the keywords of a language, programmers must also be familiar with the build-in operators provided by the language. Programmers must know things like which symbols denote which operations; whether the same symbol may refer to different operations depending on the values of operands; the “airity” of the operators (how many operands they operate on); where the terms or operands (the operator’s “arguments”) are expected to appear: are they on the left-hand side of a postfix operator? on the right-hand side of a prefix operator? on both sides of an infix operator?
Furthermore, programmers must understand the precedence rules that determine the order in which the operations that make up an expression will be performed when the expression is evaluated. And, of course, programmers are expected to know at least what type of value, if not the actual value itself, that each operation will return for a given a set of inputs.
In isolation, the various facts that a programmer needs to know about operations, operators, and expressions are not too difficult to understand. But there are several rules, several operators, and innumerable ways of combining them to form expressions. It’s easy for programmers to get tripped up by expressions, even very short ones.
The Scheme That Went Askew
Silly as it seems now, I thought my plan was simple enough at first. Although I would not have been able to articulate all of the details this clearly in the beginning, it is evident, in hind sight, that this is where I was headed:- I would write a program that would take a sequence of tokens representing a valid expression as input.
- Each token would be either an operator or a term (an operand).
- Tokens would be strings separated by a space.
- Operators would operate on zero, one or two operands.
- Operators could be prefix (one operand on the right), postfix (one operand on the left), or infix (an operand on the left and right).
- Order of operations would be determined by a precedence value assigned to each operation.
- All operations would be user-defined, but most would be the familiar ones: addition, subtraction, multiplication, division, negation, logical and, logical or, etc.
- A subroutine would generate random expressions.
- A subroutine would take an expression (with no parentheses) as input and return an equivalent expression in Polish notation in the form of a stack with the operators on top of their operands. (This would be a chance to demonstrate a nice, fairly simple recursive algorithm, I figured.)
- A subroutine would take a stack of operators and operands arranged in Polish notation and return the value of the expression represented by the stack. (Another very nice recursive routine that could be morphed, as an exercise, into a routine that “parenthesizes” the original expression.)
Somehow, I imagined, I would then develop a set of exercises that would accompany source code corresponding to some or all of the above bullet points. At the very least, the exercises would make it clear to my students:
- The meaning of terms like expression, operator, operand, prefix, infix, postfix, precedence, order of operations, evaluation, etc.
- The importance of understanding how to form and read expressions.
- The power and beauty of recursion.
- How a stack works and can be implemented.
The icing on the cake would be a little initial exposure to object-oriented programming. As much as possible, I wanted to stick to basic features of the JavaScript and/or Java programming languages. I didn’t want to introduce new programming constructs like user-defined types and their constructors any more than necessary, because I didn't want students to feel overwhelmed by new language patterns. I wanted most of the focus to be on expressions, operators, order of operations, recursion, stacks, algorithms, examples of good code layout and judicious use of comments, functions and static methods, if-else statements, for and while loops, arrays, and primitive types of data — just “a few” basic topics.
After several days of coding and revising,* I had a collection of JavaScript objects (constructor functions and static objects/methods) that I was pretty pleased with. But after stepping away from the code for a few days, I started, once again, to feel differently about it. I regretted my decision to limit the terms and operations that may appear in a given expression to ones that either are or return the same, single type of data. I felt like that was a mistake, since expressions often contain multiple types of data. For example, the JavaScript expression
typeof r === "number" && r > 0 & 2 * Math.PI * r > LOWER
involves a variety of data types.
Moreover, I began to think I was about to throw too much too soon at some if not all of my students. My primary goal was to go just one step beyond the reserved words of a programming language and study carefully the next simplest, most fundamental thing possible — expressions — so that we would really know what we were doing in the Boolean expressions portions of our if statements and loops. Instead, I found myself staring at a program that seemed to be begging for a more gentle introduction to objects and constructors; without that, I feared, my attempt to highlight the nature of expressions and the thrill of using of stacks, Polish notation, and recursion to evaluate them, might all be for naught. I was feeling more and more like Don Quixote mounting a charge against a windmill than Professor Spurgeon elucidating expressions. And the clock was ticking.
How do I break this program down into more manageable sized pieces? What parts should I try to explain first? These were questions I was asking myself when Stack finally caught my eye.
Information Structures
A reading from the apostle Donald E. Knuth’s The Art of Computer Programming, Volume 1, 2nd edition (Addison Wesley, 1973), Chapter 2, “Information Structures”, pages 228-229.
Computer programs usually operate on tables of information. In most cases these tables are not simply amorphous masses of numerical values; they involve important structural relationships between the data elements.In its simplest form, a table might be a linear list of elements, when its relevant structural properties might include the answers to such questions as: which element is the first in the list? which is the last? which elements precede and follow a given one? how many elements are there in the list? There is a lot to be said about structures even in this apparently simple case (see Section 2.2).
In more complicated situations, the table might be a two-dimensional array (i.e., a matrix or grid, having both a row and a column structure), or it might be an n-dimensional array for higher values of n; it might be a tree structure, representing hierarchical or branching relationships; or it might be a complex multilinked structure with a great many interconnections, such as we might find in a human brain.
In order to use a computer properly, it is important to acquire a good understanding of the structural relationships present within data, and of the techniques for representing and manipulating such structure within a computer.
The present chapter summarizes the most important facts about information structures: the static and dynamic properties of different kinds of structure; means for storage allocation and representation of structured data; and efficient algorithms for creating, altering, accessing, and destroying structural information. In the course of this study, we will also work out several important examples, which illustrate the application of these methods to a wide variety of problems. The examples include topological sorting, polynomial arithmetic, discrete system simulation, operations on sparce matricies, algebraic formula manipulation, and applications to the writing of compilers and operating systems. Our concern will be almost entirely with structure as represented inside a computer; the conversion from external to internal representations is the subject of Chapters 9 and 10.
Much of the material we will discuss is often called “List processing,” since a number of programming systems (e.g. IPL-V, LISP, and SLIP) have been designed to facilitate working with certain general kinds of structures called Lists. (When the word “list” is capitalized in this chapter, it is being used in a technical sense to denote a particular type of structure that is studied in detail in Section 2.3.5.) Although List processing systems are useful in a large number of situations, they impose constraints on the programmer that are often unnecessary; it is usually better to use the methods of this chapter directly in one’s own programs, tailoring the data format and the processing algorithms to the particular application. Too many people unfortunately still feel that List processing techniques are quite complicated (so that it is necessary to use someone else’s carefully written interpretive system or set of subroutines), and that List processing must be done only in a certain fixed way. We will see that there is nothing magic, mysterious, or difficult about the methods for dealing with complex structures; these techniques are an important part of every programmer’s repertoire, and he can use them easily whether he is writing a program in assembly language or in a compiler language like FORTRAN or ALGOL.
We will illustrate methods of dealing with information structures in terms of the MIX computer. A reader who does not care to look through detailed MIX programs should at least study the ways in which structural information is represented in MIX’s memory.
It is important to define at this point several terms and notations which we will be using frequently from now on. The information table consists of a set of nodes (called “records,” “entities,” or “beads” by some authors); we will occasionally say “item” or “element” instead of “node” Each node consists of one or more consecutive words of the computer memory, divided into named parts called fields. In the simplest case, a node is just one word of memory, and it has just one field comprising that whole word.
So sayeth Knuth.
Stacks, Queues, and Deques
Okay! We’re making progress. Now that we have a firm handle on what a node is, we’s almost ready to talk carefully about stacks.
NOTE: Abstractly speaking, a node is the fundamental data structure or building block needed to construct stacks and many other interesting information structures. Don’t forget that we are interested in stacks because they appear in Mr. Spurgeon’s program that processes expressions, and we need to understand how expressions are evaluated and how to form them. (Now might be a good time to take a break and start compiling a list of synonyms of “circuitous,” not to be confused with cirqueitous, which is a cute way of describing something that resembles or behaves like a circular queue.)
Knuth tells us what stacks are and says why we should care about them on pages 234 and 235 (ibid.), but first he needs to talk about linear lists. (Hang in there!)
A linear list is a set of n ≥ 0 nodes X[1], X[2], . . . , X[n] whose structural properties essentially involve only the linear (one-dimensional) relative position of the nodes: the facts that, if n ≥ 0, X[1] is the first node; when 1 < k < n the kth node X[k] is prceded by X[k − 1] and followd by X[k + 1]; and X[n] is the last node.The operations we might want to perform on linear lists include, for example, the following.
- Gain access to the kth node of the list to examine and/or to change the elements of its fields.
- Insert a new node just before the kth node.
- Delete the kth node.
- Combine two or more linear lists into a single list.
- Split a linear list into two or more lists.
- Make a copy of a linear list.
- Determine the number of nodes in a list.
- Sort the nodes of the list into ascending order based on certain fields of the nodes.
- Search the list for the occurrence of a node with a particular value in some field.
In operations (i), (ii), and (iii) the special cases of k − 1 and k − n are of principal importance since the first and last items of a linear list may be easier to get at than a general element is. We will not discuss operations (viii) and (ix) in t his chapter, since these topics are the subjects of Chapters 5 and 6 respectively.
A computer application rarely calls for all nine of the above operations in their full generality, so we find there are many ways to represent linear lists depending on the class of operations which are to be done most frequently. It is difficult to design a single representation method for linear lists in which all of the operations are efficient; for example, the ability to gain access to the kth node of a long list for random k is comparatively hard to do if at the same time we are inserting and deleting items in the middle of the list. Therefore, we distinguish between types of linear lists depending on the principal operations to be performed, just as we have noted that computer memories are distinguished by their intended applications.
Linear lists in which insertions, deletions, and accesses to values occur almost always at the first or the last node are very frequently encountered, and we give them special names:
- A stack is a linear list for which all insertions and deletions (and usually all accesses) are made at one end of the list.
- A queue is a linear list for which all insertions are made at one end of the list; all deletions (and usually all accesses) are made at the other end.
- A deque (“doubled-ended queue”) is a linear list for which all insertions and deletions (and usually all accesses) are made at the ends of the list.
A deque is therefore more general than a stack or a queue; it has some properties in common with a deck of cards, and it is pronounced the same way.
Literal Values
Now that we have the descriptive knowledge needed to understand nodes, linear lists, and stacks, its almost time to start acquiring the procedural knowledge needed to create and work with them.
In one interesting sense, it’s easier to create nodes using JavaScript than it is using Java: JavaScript allows us to create literal nodes (objects) without using a constructor function, which is something we’ll talk about after we practice working with object literals. And since we like to keep things as simple as possible to begin with, we need to make sure we know what a “literal” is. (This brief detour is certainly worth taking. It’s imperative that we understand literals, regardless of the programming language we are using.)
A literal value, or simply a literal, is a representation of a single, actual value.
A literal is literally a value.
A variable, on the other hand, is a name that may refer to one of many possible values.
At any moment in time, a variable refers to a single value, but a non-constant variable may refer to different values at different times during the execution of a program.
In contrast, a (Java or JavaScript) literal always represents the same value. The literal 2, for example, cannot be changed to represent the value three; it always represents the value two — the one and only value it is intended to represent.
In Java and JavaScript we can assign the value ten to a variable called, say, x in a variety of ways.
For example, in JavaScript, we can introduce the variable x and initialize its value to ten using the literal 10.0 in a single statement like this:
let x = 10.0;
The JavaScript code shown immediately above can be performed by providing the code itself as the input to a JavaScript interpreter. The code is literally the input to the interpreter. An analogous Java code fragment looks like this:
double x = 10.0;This Java code snippet or code fragment cannot be executed directly. It must be part of more involved Java program. Typically, Java programs must be compiled, and the output files produced by a Java compiler must form the input to an interpreter known as a Java Virtual Machine or JVM, which performs the instructions of intermediate code (also known as portable byte code) that produced by a Java compiler and stored in one or more files.
Here is a Java program that contains the code snippet shown above:
public class Foo { public static void main(String[] bar) { double x = 10.0; } }
Here’s the same program, formatted differently:
public class Foo {
public static void main(String[] bar) {
double x = 10.0;
}
}
Here’s yet another variation of the same program:
public class Foo
{
public static void main(String[] bar)
{
double x = 10.0;
}
}
In Java and JavaScript it often doesn’t matter to the machine where we break lines or whether a single space or multiple space characters are present. Sometimes it matters, but often this sort of formatting has no bearing on how a program functions. However, formatting does have a big impact on how human readers of our code perceive it. For the sake of their fellow coders, good programmers strive to write code that looks pleasing to the eye and is easy to read and understand.
The literal values 10, 10.0, 10.00, 0xA, 0x10, and 010are all different literals, some of which may refer to the same conceptual value and may therefore be represented in memory by the same pattern of bits.
10, 10.0, 10.00, and 0xA all represent the conceptual floating point number we refer to using the word ten or the digits 10.
All numbers in JavaScript are 64-bit floating point numbers, so each of the aforementioned literals
that represent the number ten are represented in memory by the same pattern of 64 bits.
The null Object Literal
In Java and JavaScript, the value null is a token (a string of characters) that denotes a literal value that can be used anywhere a reference to an object is expected.
The value null signifies the absence of an object. Attempts to access a member of the object null via the dot operator (e.g. null.foobar) fail,
because the value null has no members, being the object that is “no object”.
JavaScript Object Literals
In a JavaScript program we can create object literals. For example, we can create an object that has a value field and a link field as follows.
{ value: undefined, link: null }
In JavaScript undefined is a literal value similar to null. The value undefined is, for example, the default value of variables that have not been initialized; undefined is also the value returned by functions that do not explicitly return some of type of value. There is no literal value in Java that is analogous to JavaScript’s undefined value. Instead, Java compilers will not compile programs with variables that it deems might not have been initialized, and methods that do not return a value — methods declared to “have a return type” of void — do not return any value at all.
Below is a JavaScript program (an immediately-invoked function expression) called HelloWorld1.
- The first statement of the program introduces a constant variable named
sentineland sets its value equal to the address of an object literal that has two fields (variables): the field namedvalueand the field namedlinkare both initially set to the literal valuenull. - The second statement is like the first, except its
valuefield is set to the address of a string literal, and itslinkfield is set to the value ofsentinel. - The third statement is like the previous one.
- The fourth statements introduces a variable named
phraseand sets its value equal to an empty string. - The next two lines define a loop, which behaves as follows:
- A variable (local in scope to the loop) named
nodeis introduced, and its value is set to the value ofnode1. - The conditional expression
node.link !== nullis evaluated. If the expression evaluates to true, then the body of the loop (in this case, the single statement following the right parenthesis character) is executed; the assignment statementnode = node.linkis executed; and this step repeats. If the expression does not evaluate to true, then the body of the loop is not executed and the statement executed next is the one immediately following the body of the loop.
- A variable (local in scope to the loop) named
- Finally, if the loop‘s conditional expression does not evaluate to true at some point, the value of the variable named
phraseis passed to the subroutine calledalertand the subroutine performs its function; namely, it outputs the value ofphrase.
(function HelloWorld1() {
const sentinel = { value: null, link: null };
const node2 = { value: "world\n", link: sentinel };
const node1 = { value: "hello, ", link: node2 };
let phrase = "";
for (let node = node1; node.link !== null; node = node.link)
phrase += node.value;
alert(phrase);
})();
Exercises
- What is a sentinel node?
- Rewrite only the conditional expression of the for loop and nothing else without affecting the output of the program
HelloWorld1. - Reverse the order of the first three assignment statements of the program
HelloWorld1; then modify the program so that it produces the same output as the original program. - Change the first statement to
const sentinel = null; then modify the program so that it functions the same as before.