V Programming Basics🔗

What is programming to a software developer?

In the context of software development, programming refers to the creation of code that realizes the planned components. And, critically, the artifact that many other people will look at again and again. These people will have to read the code, and they will have to understand how it achieves its purpose, meaning both its functionality and its basic performance.

Sometimes all of this is easy to infer from code. Equally often, some aspects remain hidden because programming is the result of turning invisible thoughts into written code. The creator of some code may recall why a variable contains values of a certain shape; the problem is that some distant piece of code in a large module or class creates these values—and there is no manifest relationship between these pieces of code. Similarly, a creator may know that a call to one method is only valid if some other method on the same object has returned a certain kind of value; yet, most languages don’t even have a mechanism for expressing or checking such constraints directly. In short, comprehending code often means reconstructing the thoughts that went into its creation, including those that are not locally visible or those that aren’t written down anywhere.

Given this situation, the goal is to create code that allows maintainers to reconstruct the original thoughts quickly. Positively put, code must express a creator’s thoughts as directly, as clearly, and as comprehensively as possible in the chosen programming language. As the preceding three chapters suggest, the clarity Over time, programming languages improve or new languages come about that allow developers to express more of their thinking directly. But this change is slow, and so we must focus on improving code per se. of code depends on a developer’s proper understanding of the nature of software as the sum of proper mindset, plans, and code, plus an awareness of the “big picture” surrounding a software project. This chapter presents ideas on how systematic programming can create easily comprehensible code and how inspections may help programmers recognize problems before they become a big cost factor.

18 Clarity of Code🔗

When panelists consider some piece of code incomprehensible during an inspection, a common reaction is to promise explanatory comments. This reaction completely ignores the nature of comments. As a language construct, they are just a mechanism for adding unchecked words to code. As unchecked words, comments are often out of sync with the surrounding code. The cure is to use comments in a limited number of cases, where they are truly needed and where they tend to remain partially valid.

As for code itself, a range of factors affects its nature as an expression of thoughts. One truly basic factor is the naming of classes, fields, methods, parameters, and even local variables. At the large-scale level, individual developers may be able to influence the design of classes and relationships among classes or the partitioning of a sub-system into modules.

Experience also tells us that choosing a well-suited data representation is a key factor in clarifying the purpose of code. At almost every level of programming, a developer must make a choice, namely, how to represent domain information in the data sub-language of the chosen programming language. Once the choice is made, the respective code must convey how a piece of data is to be interpreted in the domain and how any piece of information is to be represented as data. Indeed, to get this part right, a comment next to data definition is almost always necessary.

The chosen data representation should induce the organization of methods, This is often called encapsulation.specifically their allocation to specific components. Conversely, the design of functions should mirror the data representation. Imagine a function that consumes a union data type with n variants; if the function’s body consists of a conditional with n corresponding branches, a maintainer can easy connect a branch with a variant and make changes accordingly.

Next, code benefits from some abstraction but not too much. Repetitions of code call for the creation of an abstraction and a good name that tells a future reader what the abstraction accomplishes. Then again, a developer should notComplex protocols indicate a gap in a language’s expressive power. abstract in anticipation of repetitions or abstract in ways that call for complex call-back protocols or deep inheritance chains.

Finally, as explained in Principles, in-person inspections are an amazing tool for simulating the hand-over of code from one developer to another. In the spirit of social responsibility, presenting and inspecting code aren’t chores but ways to simplify the lives of others—including older versions of the current team members. Getting code inspections right isn’t easy; but practice makes perfect or at least good enough.

19 Comments are Needed in a Small Number of Places🔗

Every programming language supplies a mechanism for adding informal, natural-language phrases to code. The idea is that comments can expose relationships among pieces of code that are difficult or impossible to express in the programming language itself. Sadly, due to their informal nature, commenting isn’t often practiced in university courses, and, as a result, students tend to think of them as a nuisance to be added once the coding is done. Comments have thus become the most abused language construct in the world of software, yielding over-commented, mis-commented, and under-commented software repositories.

Useless Comments The main problem with comments is that they are often out of sync with the code and thus misleading to a reader. When a comment is first added, it probably describes the code under consideration in a correct or close to correct manner. But, as others—including older versions of the original developer—modify the code, they forget to change the comments in accordance with the code changes. If this happens repeatedly, the comments become worthless.

Exercise 12. In this problem domain, a thermometer may measure a temperature at 17.1C. How is this temperature represented given the above data representation? Conversely, if current is 781, what temperature does the thermometer display?

What this exercise points out is that a developer tasked with updating this code gets no clue from reading it as to how information about temperatures is represented. The exercise also reminds us that some countries want thermostats that use Celsius while the United States is still using the Fahrenheit scale.

This simple example is illustrative of why data definitions—the result of choosing a data representation—deserve a comment. In general, representing information as data is a far more complex affair than this example indicates. See Developing Data Representations for Information for some additional examples.

Now consider a maintainer reading this code. Even though this code is somewhat simple, question yourself whether it controls all of the thermostat, that is, the thermometer, the actuator, and the external connectivity to the A/C and heater. Or, take a look at decide. What does this method compute? It consists of merely nine lines of code, so it is easy to read. But, should a developer read nine lines to understand a method’s purpose? If a developer has to understand the purpose of ten methods, it means reading and comprehending 90 lines of code.

Once again, this example is simple, and a developer with some understand of the context may have figured out the purpose of either unit with a single glance. In reality, software is large and developers don’t always have the context at their finger tips. These one-liners cost the creator of the program unit little, but create the focus needed to realize a unit properly and help readers quite a bit. Designing Functions, Systematically presents some additional examples and explains a bit more how such purpose statements help.

Recursive methods, complex loops demand explanations. While many methods are straightforward, some implement complex algorithms that rely on intricate logical invariants. Sorting algorithms, graph traversals, and context-sensitive tree traversals are some examples. They may use generative recursion or loop-based worklist designs. In both cases, it may not be obvious how the algorithm computes its result or why it terminates. Hence, both kinds of recursive functions deserve one-line comments, explaining the how and the why in addition to the what. In case the developer avoids recursion in favor of a worklist, the comment is best placed with the looping construct (while, repeat), and it is best formulated as an accumulator property or a loop invariant. Finally, if an algorithm demands deep insights into the domain—think Simplex for solving linear programming problems in applied mathematics—a comment pointing to a journal paper or an on-line tutorial serves as a good warning to a maintainer; additionally, some in-lined comments should connect pieces of the implementation to the key ideas of the algorithm description.

20 The Very Basics🔗

20.1 Names Matter🔗

Names matter in many contexts. First, literal constants need names. Second, the names of classes help navigate a code base. Third, good names for methods and functions, plus their parameters, can summarize many lines of code as a single line. Finally, introducing well-named, local variables for intermediate results helps readers comprehend the underlying computational process.

In addition to conveying meaning, names for constants also facilitate the adjustment of values. For example, nowadays end-users sit in front of significantly larger monitors than a decade ago. It’s therefore acceptable to increase the width and height of the imagined window. Doing so with named constants is easy; finding all occurrences of 100 and 200 makes such an adjustment extremely difficult.

Exercise 13. List some constants that don’t need names no matter where they show up in code. What do they have in common?

Exercise 14. Reformulate the moveRight method header imagining that it is all about confirming a reaction to a distance measurement. Ask a peer to review your reformulation and comment on it.

Like in the case of plain names, a sense of compromise is needed here. Some formulas are so well known that breaking them up is unnecessary. Some operations, say division by 2, are so obvious that they don’t need a separate name. Worse, breaking up expressions inside of a function may lengthen it so much that it is no longer an easy read. And that brings us to the next important basic point about code: keeping units of code sufficiently small.

20.2 The Size of Functions and Methods🔗

Functions and methods are the fundamental building blocks of programs, similar to the bricks and two-by-fours of houses. When developers must comprehend code with the goal of modifying it, they must comprehend functions and methods above all. Keeping functions and methods comprehensive is thus imperative, and this usually means keeping them short.

Squeak is a great example of a large system with short, clean methods. It is a modern version of Smalltalk, the first major object-oriented programming language. A reasonably recent inspection counted between 500,000 and 600,000 lines of code. The number of methods came in at around 100,000. In other words, the developers kept the average method to about six (yes, 6) lines of code. If these methods also come with sensible and meaningful names, a developer can comprehend the essence of each with a single quick reading. Each of these methods can be understood in a short time and with little cost.

The question is how developers keep methods and functions so small.

Figure 33: Recognizing separate functionality

The ideas say “break up any large function” and turn it into a composition of several small functions, that is, a composite function. The performance cost is negligible. And the gains in comprehensibility are large. Creating a composite function means recognizing blocks of code in an existing function as a separate, meaningful task. The second step is to move this code into a function by itself, to give this function a name that describes the task properly, and to replace the code with a call to this function.

Figure 33 displays a somewhat longish function. It certainly exceeds the already-mentioned six lines per method metric of Squeak. The key is to recognize the lack of balance in the three branches of the (match) conditional. Specifically, the second, boxed branch consists of six lines while the first one requires two and the last on is just a function call. These counts alone suggest that the method is a mix of atomic computation and a composition of helper functions.

The next step calls for factoring out pieces of code as separate functions or methods. This means identifying all those variables that are defined in the existing function and needed in the code block. These variables become the arguments and parameters, respectively, to the factored-out functions. When a developer considers factoring out one branch of a conditional, it is often best to factor out all other branches that consist of more than a line.

#; {World Message -> World}

;; process `msg` from server in `current` state of the world

(define (receive-update current msg)

(match msg

[(posn-msg posn dir opponents)

(deal-with-positioning-msg current posn dir opponents)]

[(fight-msg updated-fighters outcomes)

(deal-with-fight-msg current updated-fighters outcomes)]

[_  (stop-with (format "can't deal with ~v yet" msg))]))

Figure 34: Breaking up the function in figure 33

In the running example, the existing function pattern-matches the received msg against structs named posn-msg and fight-msg, respectively. This matching defines several variables locally. Since the code in the two branches also refers to current—the first parameter of receive-update—it also becomes an argument to the factored-out functions.

Figure 34 displays the result of this re-factoring step. The re-factored variant consists of a conditional with three branches, each a singe function call. Comparing the two variants should immediately clarify how the re-factoring and the choice of function names helps a developer navigate this code base. If, for example, a glitch is visible during the set-up phase of the game—when each player receives information about where its fighter is located and going—the name of the function in the first branch directs the developer to the correct code. Nothing else is needed. Likewise, if the result of fights is broken, the second branch calls for attention.

The factored-out deal-with-posn-msg function is an example of an atomic function. Atomic because it use nothing by struct operations (e.g. world-I, fighter-update) and imported functions (e.g. map).

20.3 A Short Note on Conditionals and Loops🔗

After identifier references, conditionals and loops are the most frequently used forms in methods. They deserve some basic care.

A conditional identifies distinct cases of computation, and it sets up distinct blocks of code for each case. Distinguishing cases helps developers focus. By subjecting a statement to a condition, a developer can focus on just this special one form of data and ignore all others.

Take a second look at the code in figure 33, specifically at the conditional in the function body. It distinguishes three input cases for msg. The conditions are formulated in a uniform style. While the first two pattern-match and deconstruct a struct into its pieces, clearly distinguishing two cases, the last one is a catch-all clause. By contrast, and as the preceding section points out, the branches themselves violate the first and third guideline with the second one standing out by size alone. The second branch also contains sophisticated pattern-matching definitions, (simple) function calls, and a nested conditional (distinguishing two different result situations). The refactoring of the preceding section creates a function whose conditional satisfies the guidelines.

/* @param `dir` the desired direction of an action

* @param `ind` the row or column to be shifted

* @return whether `ind` is a valid index given `dir` */

private static validIndex(Direction dir, Index ind) {

if (dir.isVertical()) {

if (!state.getBoard().isMovableCol(ind)) {

return false;

}

} else if (!state.getBoard().isMovableRow(ind)) {

return false;

}

}

Figure 35: Comprehending conditionals

Exercise 15. Figure 35 displays a snippet from a rule-checking class for a game whose board comes with movable rows and columns. Does the conditional satisfy all guidelines? Why? If so, explain. Why not? If not, rewrite the method. Work with a partner.

A for loop combines a conditional with a function. In its most basic form, the purpose of a for loop is to traverse some data structure and apply the body to each component of the data structure. In some languages, the enumeration of elements is an explicit process, and in this case, a termination condition is stated explicitly. As for the function part, nobody ever speaks of a loop body as a function, but that’s what it is. A while loop is similar to a for loop. It differs in two ways. First, the components of a data structure are computed explicitly, step by step. Second, the generation of components—and the termination of the loop—is governed by an explicit condition.

The key is to write clear conditions (if needed) and to keep the loop body comprehensible. Like for an ordinary function, the loop body should not exceed an easily comprehensible size, about the same size as a function. Conversely, if the loop body gets too large, identify atomic tasks and factor them out into functions; if necessary, turn the entire loop body into a function with a suggestive name.

Consider the following two code snippets. Read the one on the left first:

Now look at the code on the right. It uses a ready method to bring across that the termination condition is about finding the end of the readable input. The loop body is just a function call to a well-named function: echoChar. Every code reader can immediately discern what this loop body computes.

21 Code Inspections, the Basics🔗

A code inspection calls for the discovery of three kinds of problems: coding flaws, errors, and design mistakes.

Coding flaws make the code difficult to understand. These flaws are common, easily spotted, and equally easily corrected. The most basic coding flaws violate the basic suggestions of the preceding section. Others conflict with specific coding rules that a team has adopted but aren’t enforced with linting tools.

Errors make code inconsistent with expected behavior. Most pieces of code come with informal specifications. The panelists must understand these specifications and what the reviewed functionality is to accomplish, though they may not see how to realize it. When panelists discover discrepancies between the code and the specification, everyone involved must rejoice; it is a bug not deployed. One way to search for errors is to inspect the unit tests for a piece of functionality. Panelists may notice that the tests don’t cover some aspects of the desired functionality; they may then propose that a test case be added and pay close attention to the uncovered aspects.

Design mistakes may make the code useless. In some cases, developers choose a code organization—a division of functionality—that overlooks essential aspects of the problem or specification: functionality specifications, performance constraints, contextual peculiarities, etc. Spotting such design flaws requires a good amount of experience, because they are about relationships of the reviewed code to other parts of the system or they call for a radically different choice of data representation and algorithm.

Panelists can discover design flaws at two stages: during an inspection of the specification architecture or during an inspection of the code itself. For the first kind, review the discussion in Interface Inspections, Systematically; it illustrates how panelists can question a relationship between different system components, specifically the choice of one communication protocol over another between two components. This early discovery avoids the creation of code with serious design flaws, but not all design flaws manifest themselves at this stage. For the second kind, panelists must continuously question whether they are agreeing to a presenter’s explanations of the code too easily. In many cases, they must insist that the present explicate implicit assumptions about the context of the presented code—and when this is done, they may see where the development went off the rails.

Using the guidelines from the previous section, an inspection targeting coding flaws is straightforward. Simple instances of the other two are also quite easy to spot.

Figure 36: Inspecting for coding flaws

21.1 Inspecting Code for Coding Flaws🔗

Imagine yourself as a panelist that is about to review the code in figure 36. This function is an extract from a QOI library. For our purposes, it does not matter what QOI is about other than that the figure displays a single function from this library. The question is where and how this code violates the basic guidelines from the preceding section. Stop! List those violations before reading on. Thanks to Guillaume Savanton who wrote most of this code originally and who gave permission to use it for this illustration here. The imaginary dialog is loosely based on a conversation between the creator and the author.

But, note how the panelists also veer from the prescription for inspections. Instead of focusing on finding flaws, the second question implies suggestions of how to improve the presented code.

Is it acceptable to weave in suggestions?

Generally speaking, it is not the task of a code inspection to make suggestions on how to fix problems. The intent of the review is to understand how the function accomplishes its purpose and to uncover problems. Keep in mind that the developer of the code has studied the problem in gory detail and has figured out how to tackle it with code. Once a problem is pointed out, the developer may come up with several solutions and, if needed, can ask for advice if a trade-off is to be made.

Once exception to this rule concerns “developers in training.” In the specific situation when a mentor reviews code with someone who is considered “in training,” weaving in potential fixes is acceptable. But even then it is best to extract the fixes from the mentored person rather than stating them directly. This furthers the learning process.

The panelist once again made a suggestion—and the presenter pushed back. Here the interaction demonstrates that presenters must know when to accept criticism and when to tell the panelist(s) why a remark is wrong. An inspection must be a give-and-take.

21.2 A Code Inspection Memo🔗

The product of a code inspection is a memo that details the criticism that come up and aren’t immediately resolved. It is not the task of the presenter to take notes, unless given time to do so. Indeed, during a code inspection, the Taking Notes presenter should focus on just three points: explaining the code; understanding the questions and criticism; answering those properly or pushing back when panelists’ criticism are addressed in the code—just like during a design inspection. A formal code inspection allocates one person—the secretary—to this one task; the presenter’s partner, if present, may take additional notes.

To: Guillaume S.

From: Matthias F.

Date: 31 Feb. 1981

Subject: your img-write-qoi function

An inspection of the QOI library revealed the following problems:

1. The function is too long.

SUGGESTION It might be possible to break it up into three

functions: one for the file header, one for the body of

the image, and one for the remaining bytes.

2. The initialization expression for the variable last is too long.

SUGGESTION Turn the loop into a function that returns how many

bytes of remain to be written at the end.

3. The code comes with too many comments, many of which add

nothing to the code. The first one is in the loop header:

(for/fold ([pixel-prev qoi-pixel-init]

[run-length 0]

; The loop will return the length of the last run.

#:result run-length)

...)

This comment merely repeats the #:result clause and adds nothing.

Figure 37: A code inspection memo

#; {Image [OutputPort] -> Void}

;; save `img` in the QOI format to the `out` port

(define (image-write-qoi img [out (current-output-port)])

(write-qoi-head img out)

(define last-run-length (write-qoi-body img out))

(write-qoi-op-runs last-run-length out)

(write-bytes QOI-END-MARKER out))

#; {Image OutputPort -> Void}

(define (write-qoi-head img out)

(define width  (integer->integer-bytes (image-width  img) 4 #f #t))

(define height (integer->integer-bytes (image-height img) 4 #f #t))

(define header (bytes (image-channels img) (image-colorspace img)))

(write-bytes (bytes-append QOI-MAGIC width height header) out))

#; {Image OutputPort -> Void}

(define (write-qoi-body img out)

(define pixels (image-pixels img))

(define LENGTH (bytes-length pixels))

(define INDEX  (make-vector 64 (make-bytes 4)))

;; Process pixels in raster-scan order:

(for/fold ([prev qoi-pixel-init] [run-length 0] #:result run-length) ([n (in-range 0 LENGTH 4)])

(define pixel (subbytes pixels n (+ 4 n)))

(cond

[(equal? pixel prev)

(values pixel (add1 run-length))]

[else

(write-qoi-op-runs run-length out)

(write-piece pixel INDEX prev run-length out)

(values pixel 0)])))

#; {Bytes [Vector Bytes] N OutputPort -> Void}

(define (write-piece pixel INDEX prev out)

[define pos (qoi-index-position pixel)]

(cond

[(equal? pixel (vector-ref INDEX pos))

(write-qoi-op-index pos out)]

[else

(define-values (dr dg db da dr-dg db-dg) (pixel-diff pixel prev))

(vector-set! INDEX pos pixel)

(cond [(not (zero? da))

(write-qoi-op-rgba pixel out)]

[(and (<= -2 dr 1) (<= -2 dg 1) (<= -2 db 1))

(write-qoi-op-diff dr dg db out)]

[(and (<= -32 dg 31) (<= -8 dr-dg 7) (<= -8 db-dg 7))

(write-qoi-op-luma dg dr-dg db-dg out)]

[else (write-qoi-op-rgb pixel out)])]))

Figure 38: Reacting to a code inspection memo

21.3 Reacting to a Code Inspection🔗

Figure 38 shows how the presenter(s) could react to the criticisms from the code walk. The main function—image-write-qoi—consists of four lines of code: the first one writes the file header; the next two deal with the main body of the image file; and the last line writes an end-of-image marker.

Consider write-qoi-head, the function that writes the file header. The corresponding expression in the original version of image-write-qoi is deeply nested. This new auxiliary function consists of three variable definitions and one expression: write-bytes. The names of the variables makes it abundantly clear which role each piece plays and which order the pieces are computed. No comments are needed to explain any of this computation.

Similarly, write-qoi-body consists of three variable definitions and the main shape of the large loop in the original image-qoi-write function. It contains one comment, concerning the order in which the loop traverses the image’s bytes. The author clearly considered this remark critical and its content difficult to discern at one glance from the loop’s body. Also note how the author split out the non-trivial, atomic step of writing pixels to the file. Doing so keeps both auxiliary functions to a reasonable size and creates comprehensible units of code.

21.4 Inspecting Code for Errors and Test Coverage Problems🔗

Spotting errors in code is challenging. To claim an error, a panelist must fully understand the specification—informal, rigorous, or formal—and the presented code. Understanding the specification means being able to imagine how the program should behave for a large part of its input spectrum or in a range of situations. Understanding the code might mean grokking one function or it might demand seeing how several methods jointly compute the desired result.

Balancing the two aspects is a challenge for every panelist. Some highly experienced developers may be able to accomplish it in some situations, perhaps because it resembles problems they have encountered before. But, for the sake of keeping the conversation productive and for the sake of egoless programming, it might be best for both to simply ask standard questions about test coverage. If the tests cover the imagined inputs or situation, there might not be a problem; otherwise, the presenter and the panelists may wish to work through such the imagined scenario together.

Let’s make this concrete. Figure 39 displays a class fragment for a game called “Three in a Row.” Two players place tokens on a square board of size n x n. The first player to connect three tokens along a row, a column, or a diagonal wins.

Figure 39: Inspecting for errors and test coverage problems

As the data-representation comment in BoardState says, the developer has chosen to represent the state of the game board with a String array. Each one-character String in this array represents an open slot or a slot taken by one of the players. To decide whether it is a winning board state, the developer has added methods for extracting rows, columns, and diagonals, each represented with a String array.

So far, so good. The presenter and the panelist discuss how the code computes the diagonal, avoiding all mention of “how you, the presenter” would do it. The first interaction also illustrates how a panelist—usually the head—directs the code inspection to an interesting point, here, the diagonal-extraction method.

21.5 Pushing Back During a Code Inspection🔗

Several aspects of this exchange are worth nothing. First, a presenter should not just listen to criticism and accept it. It is perfectly reasonable to reject a criticism. Second, in this case, the calling context establishes a critical pre-condition, which implies the next two points. Third, the presenter should explain this class in a top-down fashion, starting from the public entry points, and ask the panelists to pay attention to the logical relationship with drDiagonalFrom when the definition of winning is visible. Fourth, the panelists may not rely on the word of the presenter alone here. They must re-direct the code inspection to the winning method so that they can convince themselves that the pre-condition is properly establised—and also governs calls to similar methods. Finally, the presenter understands that expanding the purpose statement with an appropriate remark about the pre-condition is an act of socially responsible software development.

class Server:

"""

a server for signing up remote players for a Train game

"""

host:          str = "0.0.0.0"

server_socket: socket.socket

port:          int

index:         int = 0

proxies:       \underline{\texttt{Set[AbstractPlayer]}} = set()

def __init__(self, port: int):

self.port = port

def sign_up_step():

"""

EFFECT tracks signed-up player-clients and their age

"""

...

self.index = self.index + 1

self._handle_1_client(client_socket, self.index)

...

... Referee(\underline{self.sort_proxies()}).run() ...

...

def _handle_1_client(self, client: socket.socket, i: int):

"""

EFFECT adds a single player-client to `proxies`

"""

...

with Timeout(CLIENT_NAME_WAIT, ...):

player_name  = client.recv(RECV_SIZE).decode("utf-8")

proxy_player = ProxyPlayer(player_name, client, i)

\underline{self.proxies.add(proxy_player)}

...

Figure 40: Inspecting for design mistakes

21.6 Inspecting Code for Design Mistakes🔗

Generally speaking, design mistakes are the most difficult-to-spot, and yet, they may have the worst impact on all aspects of the overall product. Their source varies but here are some common places to check out: the choice of data representation; the division of functionality into separate tasks; the choice of intermediate data structures for composing helpers; a mismatch between the data representation and the processing functions; premature and probably useless abstraction or optimization. The effects, as mentioned at the beginning of this section, are equally varied: opaque code; complex logical errors; and more.

The code inspection starts well, with a quick look at the information the class represents and a directive from the panelists at what to look next. By the fourth interaction, the panelists seem confused about the role of index and its value. While the presenter can temporarily diffuse the challenge, the panelists keep questioning the code with a direction.

The presenter and panelists jointly figure out a design problem. Even though the code is correct, the use of set signals to a reader that the proxies are collected in an unordered manner. A future reader of this code would have to reconstruct the relationship between index and sort_proxies to understand what is going on. By using an ordered data structure such as a list to represent the information about the connections the code signals up front that an ordering is needed. The use of a list also directly echoes the age-order part of the specification, which may also help future readers.

This simple design mistake causes only minor problems. It misdirects a reader, and it consumes a bit of extra time to perform the sorting step. It is easy to imagine though that such small mistakes pile up and cost maintainers extra time to wrap their head around the code. Similarly, a lot of small performance losses add up to a large one. It is therefore good to catch and eliminate even such small mistakes as early as possible.

Exercise 16. Write a code inspection memo like the one in figure 37 for this code inspection.

22 Systematic Design, the Basics🔗

Given that functions and methods are the fundamental building blocks, their development deserve special care. While “programming a function” might have served as a phrase in the early days of computing, here we use “designing a function” instead to bring across the importance of acting carefully and systematically at this level. The word “programming” encompasses just too many sloppy ways of creating code.

22.1 Developing Data Representations for Information🔗

Software systems interact with their context by absorbing and injecting information. This context comes with many forms of information that the system must consume: names, distances, temperatures, pressure, touch, and so on. A device turns this information into plain bytes inside a computer, e.g., a keyboard, a mouse, a thermometer, a touch screen, and so on. These devices deliver sequences of bytes, and the software system reads these bytes. The act of reading turns information-as-bytes into data—specifically data in the chosen programming language. Conversely, a software system turns data into bytes, usually through some act of writing. The computer hardware delivers these bytes to devices, as pictures on screens, sounds on a speaker, directions to an A/C system, and so on.

Figure 41: Information and data

A concrete example should help. Take a look at figure 41. It depicts a software system—the bottom box—for predicting the weather. The system relies on weather stations to measure the current temperature and the air pressure at specific locations. These weather stations contain some simple software that capture the measurements and send them across the network to the prediction software as a sequence of bytes; these days, the bytes comprise a JSON JSON is the currently popular choice. Tastes for such notations changes over time. object with appropriate attributes. The modeling software reads this sequence of bytes—via some JSON library—and turns them into a data representation suitable for further processing.

In most cases, developer may ignore the byte-level layer and may instead focus on information and data. Turning one into the other is thought of as a direct, instantaneous step for the purpose of developing a data representation. In the context of the running example, the developer has chosen a class with three fields as a data representation (bottom) for the information (top right). What happens in between does not matter. Concretely, the fromJSON function in the Readings class translates this information into the internal data representation, and the implementation is usually just a use of some library plus an optional check that the resulting data meets some conditions. The important choice is the Reading class, which for this simple example, makes objects with three relevant attributes.

22.1.1 Information that is Considered Atomic🔗

For complex information—often called structured—developers have often made mistakes such as using strings for what looks like plain text. So let’s start with a negative rule.

22.1.2 Structured Information: Don’t Use Strings to Represent It🔗

22.1.3 Structured Information: Use Structs, Records, Objects🔗

Structured information comes in many forms, but all of them share the principle of relating pieces of information to each other. Indeed, this is the definition of the word “structured” in the phrase “structured information.”

Exercise 17. Pick one case and figure out the rationale for the recommendation on the right-hand side of the table.

The above table mentions lists, trees, graphs, and so on. In many cases, these forms of data are ideas that developers inject into the conversation about information. The “graph of people” does not exist in the real world; individual pieces of information make up the collection of these links. In the world of data—in whatever chosen language people work—this collection is turned into a single piece of data so that developers can have an effective conversation about the code, and the execution of the code satisfies basic efficiency requirements.

22.1.4 From Information to Data Representations, And Back🔗

Stepping back, the structure of information tends to guide the design of data representations. Basic information maps to atomic data. For structured information, contemporary languages come with an extensive collection of data-structure libraries. These libraries many representation choices straightforward. If a developer must represent a sequence of information—say the names of athletes in the order in which they finished a competition—then it is natural to use a built-in list type. Even for structured information as complex as a graph, a language’s ecosystem may supply a suitable form of data structure—in this concrete case, a directed graph. Many problems still call for bespoke data representations, however.

In case the structure of the information does not easily map to a supported data collection, it remains imperative to proceed systematically with the development of a data representation. A systematic development tends to be reflected in the resulting choices and code elements. It is thus likely to convey the intention of the creator.

The Representation Statement Once a developer understands the pieces of information that need representation, there are two key preparation steps to take. First, the developer must identify the relationships among the pieces of information. Second, the developer must articulate representation statements—something akin to thesis statements for paragraphs in an essay—for the various kinds of data involved. Identifying the relationships among pieces of data helps with stating a purpose for each kind of data. The goal of the representation statement is to delineate what is—and what isn’t—represented. The importance of a clear thesis grows exponentially with the number of relationships among pieces of information.

Consider the following example. Suppose we wish to construct a software system that allows people to explore the biological ancestor relationships among people. Perhaps they want to make sure that a newborn gets the name of some ancestor—as is common in some Western traditions—or that the newborn’s name does not coincide with the name of any ancestor—as is common in some Eastern traditions. This short description of information clearly identifies person with name as one kind of information and ancestor-relationship as a second one.

Note The word “every” is missing from the above guideline. Formulating a data representation determines a set of values in the chosen programming language. Due to the nature of contemporary programming languages, it is often extremely difficult or even impossible to describe this set in such a way that every piece of data has an interpretation.

Exercise 18. For each example in the table, explain why an interpretation is needed and/or make up some example data to illustrate the interpretation. How does the data definition of Coordinate differ from the Cartesian coordinates you know from middle school? Does this data definition need the interpretations of the two fields?

In summary, developing a data representation calls for two comments: (1) one that explains how information is represented as data and (2) another one that explains how a piece of data is interpreted as information. A data representation must come with some examples to illustrate these comments.

Representing Relationships While a named person is a concrete, single piece of information, some data lacks such concrete counterpart in the world of information. Recall sample domain in this subsection calls for the representation of ancestor relationships. People tend to refer to the ancestor tree. But, obviously, there is no such tree in the domain of the scenario. It is an imagined, abstract piece of element of our analysis of the domain.

22.1.5 From Information to Classes via Doodling🔗

Since the proper development of data representations lays the foundation for the systematic design of software, let us take a close look. We do so in the context of class-based, objected-oriented programming, which still dominates many parts of the software development field. The following list of scenarios is not exhaustive but covers many cases. It simultaneously articulates some basic principles and suggests a sketching notation for “doodling” data representations (on a napkin or a black board). You may have encountered both in a prior course on programming , so consider this list a concise summary.

Combining Several Simple Pieces into One Bundling several pieces of information into one piece of data is the most basic choice of a data representation. Doing so signals to the reader of this code that these pieces belong together and that functions and methods should deal with them together.

The preceding subsection introduces such an example: the first and last name of a person always belong together. Other examples are the coordinates of a point in space; an amount of money and its denomination; or the measurements of a single piece of furniture.

Combining Simple and Complex Pieces into One As mentioned, the structure of information should drive the development of a data representation. if a piece of information refers to other forms of information, a class-based representation should consist of classes that refer to each other.

The explanation in geometry books clearly identifies two distinct pieces of information: lines vs points. Given this context, it is clear that a nested representation mirrors these textbook explanations. By contrast, a flattened representation imposes a small, but non-trivial cognitive load on the reader, namely, to realize that (x0,y0) determines one point and (x1,y1) the other. Since the domain of geometry also comes with distinct operations on points and lines, which occasionally depend on each other, a separate representation has the advantage of offering natural places for these operations.

Actions are Information, Too Functional programmers understand that actions are information and occasionally deserve a direct representation. Consider the somewhat abstract and mathematical example of infinite sets, which a logician may represent with a characteristic function from elements to Booleans; if the result is true, the element is in the set and otherwise not.

Viewing Distinct Pieces Uniformly When a form of information comes in distinct flavors, the rest of the program should use all pieces uniformly. In a class-based language that supports interfaces, we can think of this case as a type—the interface—with several variants—the flavors. A developer who must use a language without interfaces, a class with dummy methods can serve the same purpose.

Arbitrarily Large Pieces of Information The final form of information to be represented is the most interesting one: when there is no limit on the size of an individual piece. While this idea may surprise you at first, it is actually the case that all interesting computations involve such forms of unlimited information. Keep in mind that “no limit” does not mean “infinite.”

Simple examples from the real world are sequences of pieces of information: a grocery receipt; tables of stock prices; listings of home for sales; and so on. Most such listings are of variable length, and there is no predetermined limit on the length of such sequences. You never know how many pop tarts a father has to buy for a growing family. Companies come and go; few companies from 100 years ago are still listed on the stock market yet many more companies are public now. Similarly, homes are added to sales listings and removed all the time.

While diagrams with cycles look complex at first glance, a second take tends to The axioms of Pressburger arithmetic generate a decidable theory. Pressburger expressions are common in code and therefore play a role in compiler optimizations. produce insights into what the data representation encodes. Consider the problem of representing arithmetic expressions, specifically expressions in what is dubbed Pressburger arithmetic. Roughly speaking, expressions in Pressburger arithmetic consists of variables, constants, and additions; practical extensions allow multiplication by constants. (Why?)

Like all data, arithmetic expressions are likely to be sent as sequences of characters—essentially, strings. Since only some strings are valid expressions and of those only a (strict) subset are Pressburger expressions, a software system must traverse these strings and turn Turning such strings into the data representation presented here is dubbed parsing in the study of natural and artificial languages. them into a proper data representation. Well-designed programs turn such expressions into trees, an idea that research on programming languages has confirmed time and again over five decades. Even though there is a natural limit on the size of such expressions, it is much better to choose a tree representation that does not impose any limits upfront.

Exercise 19. Represent the valid Pressburger expression from above as a tree, using notation from a class-based language. Why is it impossible to represent the valid Peano expression? Sketch methods that (1) find the set of all Variables in such expressions; (2) replace variables with numbers; and (3) determine the value of such expressions, given a table that maps each Variable to a number.

22.1.6 Choosing from Several Alternatives🔗

Performance, Profiling

In many cases, answers to the above questions are discovered once developers implement the functionality and measure it. The chosen representation may miss an access capability. For example, the implementation may clarify that the rest of the program needs random access to pieces of a sequence but the chosen form of data allows only sequential access. No matter what, it is then time for a developer to backtrack and revise the choice of data representation. Once again, well stated representation and interpretation statements help the older version of the developer understand the younger version’s choices and make changes to it. Without these comments, modification may all too easily mess up unstated assumptions.

Recall the two data representations for a test-field editor’s state: one just uses two strings and the other two lists of characters. A developer is likely to observe that the implementation of cursor-based editing operations demands repeated access to individual characters. Indeed, these methods always access the last character of the prefix and the first of the suffix. Hence it is also the case that the prefix is best represented as the reverse of the sequence of visible characters.

Now compare this choice with the two alternative representations of geometric lines (see above). The “flattened” alternative represents lines with a single object that has four fields; the “nested” one follows geometry books and thus prescribes objects with two fields, each of which is another object. While the brief comparison of these two alternatives suggests the nested representation offers a good organization, coding to this data representation may reveal that accessing the x and y coordinates are the most frequently run operations. In this (extremely rare) case, a developer may wish to go with a flattened data representation of lines to avoid the indirect lookup. If so, this choice deserves a representation statement that includes a rationale for this choice.

22.2 Developing Data Representations for Composition🔗

While the structure of external information may dictate the representation for the input to some function that interacts with the software system’s context—such as f—the development of its output is dictated by concerns related to internal pieces of functionality—such as g in the above diagram. Hence developing a data representation for the result of f is about reconciling two sets of constraints: keeping f simple and making its output a good input for g. This need for reconciliation is what makes this part of developing data representations difficult—meaning it demands the full and special attention of developers.

If possible, developers should still pay attention to the structure of input information. In many cases, a data representation of information that must explicate implied information is a good first example of an intermediate result. Recall the trees of ancestors and graphs of friendships that the preceding section mentions. Such pieces of data are often the result of a function that connects the software system to its environment. The challenge is to think through possible future uses of these forms of data so that internal functions benefit from the work of the first function.

Let’s make this idea concrete. Imagine a subway information system. Every morning, the system is booted with information about the currently operating stations and connections. Customers walk up to public information kiosks—or open an app on a mobile device—and query the system how to get from one station to another. One possible response could be “board the red line, direction Alewife; switch at Park to the green D line, direction Reservoir; the Fenway stop is the sixth stop on this line.” Finding a route from one place to another is a graph-search problem but the input to the software system is unlikely to be a graph.

In this example, some form of graph representation is implied by the external information—and yet, even this much insight isn’t enough to determine the full data representation. In other cases, a developer may have to explore what the best intermediate data representation is. Exploring means decide, design functionality, observe, measure, and backtrack to try something else. No matter what, however, a developer cannot design a piece of functionality without knowing the shape of the input data (and sometimes the output data). Indeed, in most cases these shapes dictate the organization of the function and greatly facilitates backtracking. A proper documentation (representation and interpretation statements) of the data representation clearly facilitates this process.

22.3 Methods vs Functions🔗

Once a developer has developed data representations, it is time to systematically design functionality, that is, functions and/or methods. Thus far, we have acted as if the two concepts are the same. Although they are closely related, they differ and the difference deserves an explanation.

Almost all programming languages support the definition of functions and methods. In a class-based, object-oriented language such as Java, a function is a static method. In a functional language such as Racket, a method is either a function stored in a struct or a function in a class, which is really just a notation for structs with special kinds of functions.

It usually takes several methods to implement a complete function. This idea is best illustrated with an example. Consider the case of processing lists. Let’s start with the task of adding 1 to every item on a list of numbers.

This example is contrived to keep this section short. Experienced developers would use libraries.

As pointed out in the passage on doodling data representations, a list represents sequences of arbitrary size. In a diagram, this relationship needs a description that points back to itself and comes with (at least) two variants: empty and a combination of an existing list with another element. In Java, this arrangement is best represented with an interface and two implementing classes. See figure 42 for the “doodle” diagram and the methods.

To implement the functionality, a systematically proceeding designer would add a method to every “box” in this class diagram. The method in the interface Java currently undermines this form of systematic design to some extent, due to its failure to manage the stack properly. specifies the header of the functionality; that is, it represents the specification of the function. The other two methods are implementation pieces of the functionality. Meaning, the two methods implement the part of the functionality that is relevant to the data represented by the two classes, respectively: the empty list or the extended list.

interface IListN {     // add 1 to each int on `this`     IListN add1()   }      class EmptyN      implements IListN {    IListN add1() {     return this; }   }      class CombineN      implements IListN {    int first;    IListN rest;    IListN add1() {     return new CombineN(first + 1, rest.add1())    }   }

Figure 42: Integer Lists in Java, implemented by hand

Generally speaking, the design of a function is orthogonal to the design of the same piece of functionality with methods. A functional design uses a conditional to separate the various forms of input data from each other and to deal with each separately. By comparison, an object-oriented design places a method with each relevant form of data; the dynamic dispatch behind method calls realizes the conditional of the function design.

Note An object-oriented developer should use conditionals only to distinguish distinct result situations; in a functional language, such conditionals are nested within the dominant conditional in a function.

Unsurprisingly, each approach has different advantages and disadvantages. Roughly speaking, object-oriented program design facilitates the addition of new variants of data. A developer just adds yet another class that implements the specification interface including its methods. By contrast, functional design makes it easier to add another piece of functionality; it suffices to design a function. Most modern programming languages lead developers to favor one design over another but still accommodate the other one. Developers must keep these different style and their implications in mind as they move from the data development stage to the functionality design stage.

Exercise 20. Use your favorite IDE to run the program from figure 42 in your preferred object-oriented programming language.

Design and add the product functionality, following the same object-oriented recipe used to produce the program in figure 42. The purpose of the functionality is to compute the product of all numbers.

Now add CombineN2, another implementation of IListN. It is variant class that adds two ints to an existing list.

If you know the basics of a functional programming language, use it to solve the same problems.

22.4 Designing Functions, Systematically🔗

The design of a piece of functionality starts with a problem statement. It should be save to assume that whoever will maintain the resulting code will also access to, and be able to read, the problem statement. The developer studies this problem statement and identifies distinct computational tasks, which yields a worklist. Each such task should eventually correspond to a function in the code base:

Simple tasks correspond to atomic functions. Complex tasks correspond to composite functions.

Designing any kind function demands discipline. Assuming a data representation has been chosen, a developer should—at a minimum—stick to the following steps. How to Design Programs

The Purpose Statement A developer must first articulate a clear and concise purpose of the functionality: what it computes. If it is possible to convey the purpose with a well-chosen function name, great; otherwise, a comment should supplement the definition and state the purpose explicitly.

The Type Signature Next a function needs a type signature. As the start of this section explains, it is the first code-like idea that a developer understands before the function exists; revisit the diagram on see first page of this section. Without understanding what kind of data flows into and out of the function, it is simply impossible to describe the desired computation.

Typed languages enforce this. If the chosen language does not come with type notation, the developer must still write down a type-like signature as a comment and program to this type-like signature, not the function’s internals. The key is that some other comments should define—again with a type-like notation—all the terms used in such an informal signature.

Working Through Behavioral Examples Using the purpose statement and the signature, the developer can work through behavioral examples. The data definition for the inputs should suggest representative inputs as well as corner cases. Working through the examples yields an understanding of how the function computes its results. Of course, working through examples also produces unit tests—see below.

If the goal is to design an atomic function, the developer should be able to imagine how every step of the work can be implemented with built-in language constructs, basic functions, or library functions. The function itself is also fair game, because recursive functions are atomic. By contrast, working through the examples for a composite function may appeal to existing functionality in the project, other functions on the worklist, or functions yet to be specified. Examples for composite methods yield basic integration tests.

The Outline & Programming For many cases of input and/or output types, the type itself suggests how to organize the function. The analogy to writing is laying out all the ideas and organizing them into an outline.

The outline for an atomic function differs a lot from the one for a composite function. For an atomic function, the outline often involves distinguishing distinct forms of inputs or choosing an iteration form to match the processed data. For a composite function, outlining means dividing the given data among the helper functions identified in the previous steps and figuring out how to compose these functions.

At this point, defining the function is essentially filling in gaps between the ideas. Each piece of the outline delivers some intermediate result. The final task is to combine these intermediate results into the result that the function is supposed to compute.

Unit Tests The creation of a function is not finished until it has been equipped with unit tests, and they all pass. This may happen during step 2 or at the end, by translating worked examples into tests. If the language permits placing some unit tests with a function definition, a developer should do so to illustrate uses.

22.5 Atomic vs Composite: A Tiny Case Study🔗

Let’s take another look at the already-mentioned game program in which a referee component interacts with player components. When it is a player component’s turn, the referee shares the current, publicly visible state of the game. In response, the player requests the execution of some action on this state on its behalf. Naturally, the referee must check the legality of this action according to the rules.

In a game such as Ticket to Ride, the game is played on a game map, which consists of connections between places. A player’s goal is to collect connections. To do so, the player trades assets in its possession for connections during a turn.

#; {GameMap State Connection -> Boolean}

;; can the active player collect the given connection

(define (legal-action? gmap gs conn)

(cond

[(not (set-member? (available-connections gmap gs) conn))

#false]

[else

(define active (state-active-player gs))

(define seg#   (connection-seg# conn))

(and

(<= seg# (pstate-cards active (connection-color conn)))

(<= seg# (pstate-rails active)))]))

Figure 43: An atomic version of legal-action?

As for the desired functionality, a developer can now say that the referee component must come with a function that determines whether a player may acquire and occupy a connection in the current state of the game, given a fixed game map. Since the problem description is relatively compact, a developer might wish to write an equally compact function definition. Figure 43 shows the result. The function computes the set of available connections; makes sure the requested connection is a member; and then evaluates the conditions about acquiring and occupying the connection.

Exercise 21. According to the preceding section, a reader must be able to connect each task in the problem statement with elements of the implemented functionality. In this spirit, circle in red the pieces of legal-action? in figure 43 that correspond to the act of acquiring the connection. Then circle in green the pieces relevant to occupying a connection.

#; {GameMap State Connection -> Boolean}

;; can the active player collect the given connection

(define (legal-action? gmap gs conn)

(and

(set-member? (available-connections gmap gs) conn)

(can-acquire-and-occupy? (state-active-player gs) conn)))

#; {PlayersState Connection -> Boolean}

(define (can-acquire-and-occupy? active conn)

(and (can-acquire? active conn)

(can-occupy? active conn)))

#; {PlayersState Connection -> Boolean}

(define (can-acquire? active conn)

(define color     (connection-color conn))

(define needed    (connection-seg# conn))

(define available (pstate-cards active color))

(<= needed available))

#; {PlayersState Connection -> Boolean}

(define (can-occupy? active conn)

(define needed    (connection-seg# conn))

(define available (pstate-rails active))

(<= needed available))

Figure 44: A composite view of legal-action?

The code of figure 44 presents this alternative. Each identified task is its own function. As a result, the functions completely align with the sentences in the rule description. Better still, each function can be understood and unit-tested in isolation, because its code is formulated in precisely the terms of the rule description.

Exercise 22. Re-do exercise 21 for figure 44. That is, circle the pieces of functionality corresponding to acquisition and occupation, respectively, in two different colors. Are they as easy to find in figure 43 as in figure 44?

Let’s step back to look at the big picture. Working through this example drives home a key insight. Although it is possible to formulate a short, seemingly simple function in response to the problem statement, a bit of reflection reveals that this organization is not in one-to-one correspondence with the listed tasks. Even if splitting up the function means adding a few extra lines of code, it looks like a socially responsible action.

Exercise 23. Let’s change the rule. A player may occupy a connection of n segments only if it has 2 * n rails in its possession.—Even this tiny exercise indicates how much easier it is to find the relevant place if the creator of the code has organized the code so that it corresponds one-to-one to the tasks mentioned in the problem statement, especially if the functions come with suggestive names. Imagine how such small differences add up for a code base with tens of thousands of lines.

22.6 Designing Methods, Systematically🔗

The design process for a method differs from the one for functions just a bit. Since both realize a piece of functionality on data representations, a large How to Design Classes overlap should not surprise. Conversely, the wording “on data representations” should suggest where the differences come from.

Given this setup, the design of methods should follow the same five essential steps spelled out in Designing Functions, Systematically: (1) understanding and formulating the purpose; (2) adding a type signature; (3) working through examples; (4) making an outline and filling its gaps; and (5) running the unit tests that come from the third step.

The fourth step differs a bit due to the mechanics of object-oriented languages. Recall from Methods vs Functions that these languages eliminate the need for conditionals that distinguish the variants of a union representation. The dynamic dispatch of method calls automatically directs a computation to the proper method. Or as stated in the referenced section, it takes several methods to realize a single function. Hence outlining a piece of functionality with methods means outlining several methods when a union type with an interface is involved.

22.6.1 Favor Functions, Favor Immutability🔗

The title of this section is a slogan, due to Josh Bloch, the designer of Java’s API. Many years of experience with this API led Bloch to critique his own design as too imperative (stateful) and to propose this slogan in his book on programming effectively in Java.

A slogan like this one does not surprise people who know the history of object-oriented languages. Alan Kay, the architect of Smalltalk—arguably the first object-oriented programming language—writes in his recollection of the design process that “assignment statements ... express very low-level goals, and more of them will be needed to get anything done. Generally, we don’t want the programmer to be messing around with state.”

In other words, the idea of reducing the use of assignment statements to fields and even local variables goes back to the very beginning of programming language design. To be clear, the slogan does not say “never use assignment statement.” It merely tells developers to think twice before using them.

Unit testing has become the most important tool for developers to confirm that methods work properly. Over the past couple of decades, the mechanism has proven its value so clearly that some companies and some teams demand at least one unit test for each and every method in a code base. Setting up a unit test for a functional method of an immutable object is straightforward: apply the method to input values and compare the results to expected output values. By contrast, testing an imperative method properly takes three steps: (1) setting up a context; (2) apply the method, checking its outcome, and making sure it doesn’t accidentally mutate fields whose value should remain the same; and (3) tearing down the context. It is easy to see why developers should prefer functional methods.

While ordinary English usage of “semantics” has a negative connotation, (programming) language researchers use the word to talk about the precise meaning of phrases. In this sense, direct semantics means that developers can understand the method’s functionality in isolation and, essentially, as an application of middle-school pre-algebra. Practically put, a developer can comprehend some method M based on some basic knowledge about the fields, plus the methods that M calls.

Always programming with immutable objects may reduce the algorithmic efficient of a method. Concretely, a functional method may run logarithmicly slower than an equivalent imperative method (measured according to the size of the input). The good news is that logarithmic factors are usually discounted by algorithm researchers. But developers must nevertheless be aware of this potential problem.

Finally, using immutable objects and functional methods pervasively tends to force programmers to occasionally use some boilerplate patterns. Roughly speaking, code may exhibit patterns such as the repeated decomposition of structured data and re-composition with one new piece on place. Or, functional methods may have to return an object when equivalent imperative, stateful methods return a base value. When such patterns appear frequently, developers should reconsider the use of immutable objects.

Let us briefly return to the automated player components mentioned several times in this book. As mentioned, such a component typically employs strategies to make decisions when it is granted a turn. These strategies use the current public game state as the basis for these decisions. Every game player knows that “decision” really means weighing options, comparing (at least) two different game states after applying two distinct actions to the current one.

Readings

Joshua Bloch. Effective Java. Pearson Education, Limited. 2001.—Bloch designed Java’s API. In the first edition of his book, he dedicates an entire chapter with this title to the idea of “functional” programming in an object-oriented language. At first glance, this advice may contradict many college-level and K-12 courses on object-oriented programming, but Bloch’s experience clearly informs him, and he tells us of the significant advantages of this approach.

Alan Kay. The Early History Of Smalltalk. Association for Computing Machinery. 1996.—Kay is the key architect of the first major object-oriented language, Smalltalk. In this article, he describes the design of Smalltalk, a project that started in 1972 and spanned the decade. Reading Kay’s design rationales and comparing them to contemporary teachings is also an exercise worth every student’s time.

Figure 45: Designing methods

22.7 A Second Look at the Tiny Case Study🔗

The guideline of following the arrows in a diagram has two consequences. First, the relationships of interfaces and classes essentially dictate how one method call others and, due to dynamic dispatch, this leads to small methods. Second, representing all forms of information with classes tends to make for easy decisions concerning atomic vs composite methods.

Let’s return to the example from Atomic vs Composite: A Tiny Case Study; seeing both designs should help you understand the fundamental differences easily. The design of the legality check of a player’s action starts again with the development of a data representation.

// N is short for Natural (numbers)

class State:

List<PlayerState> allStates = ..

Set<Connection> available = ..

Boolean legalAction(Connection c):

PlayerState active = this.allStates.getActivePlayer()

c in available && active.legalAction(c)

PlayerState getActivePlayer():

..

class PlayerState:

Rails rails = ..

Cards cards = ..

Boolean legalAction(Connection conn):

Natural n = conn.segments()

Color   c = conn.color()

this.rails.has(n) && this.cards.has(n,c);

class Rails:

N count = ..

Boolean has(N n):

this.count >= n

class Cards:

HashMap[Color, N] count = ...

Boolean has(N n, Color c)

this.count[c] >= n

Figure 46: A composite view of legalAction as a method

Instead of diving right into the formal description of classes, we start with a class diagram sketch. Take a look at figure 45. The diagram’s entry point is the State class, which—for the purpose at hand—comes with a single field: state. The arrow from this field to the PlayerState with annotated with * tells us that a state consists of many instances of PlayerState, a class that represents the information about an individual player. Now, this second class has two fields: rails and cards. They hold on to single instances of Rails and Cards, respectively. Finally, these last two classes contain fields whose type comes with the imagined language: N for natural number, Map for an association of Color with N.

The idea is of course that the referee component keeps track of the game state. When a player requests to acquire and occupy a particular connection on the game map, the referee’s legality-checking method delegates this task to the state object. The two arrows from the State object to PlayerState and Connection, respectively, suggest two helper methods: one for checking whether the player has what it takes to acquire and occupy a connection, and another one for checking whether the connection is available. Pushing forward, this pattern is repeated with the two arrows from PlayerState to Rails and Cards. Again, the legality-checking method in PlayerState delegates to two auxiliary methods and combines their results. Figure 46 displays the resulting methods. Take a close look and reflect on how much it resembles the function design and where it differs.

22.8 Why Systematic Design is Socially Responsible🔗

Systematically designing helps both the creator of code and its future reader. It starts with focused theses statements for both the development of a data representation and pieces of functionality. If we accept that code is a message from one developer to a future developer—that also runs—then the clarity of the message demands focus, meaning a delineating thesis.

The last sentence intentionally substitutes “thesis” for “purpose statement.” You have likely written essays in response to some prompt. You know that paragraphs are the basic building blocks of essays, just like functions are the brick and mortar of code. Now imagine writing an essay or even a paragraph without first determining the focus of this unit of writing. The result will be convoluted prose. One sentence will present one idea, followed by a sentence that presented an unrelated idea. It will be prose that jumps from one thought to another, prose that makes readers lose their trains of thought. They will probably re-read pieces and re-read them again just to make some sense out of it. Eventually they may give up.

The thesis statement for data representations consists of two parts: a representation and an interpretation. The former conveys how a piece of information becomes a piece of data, the latter tells a developer what a piece of data means as information. Consider the following examples: int distance, int weight, and int temperature. All three entities are integers; for all three kinds of information, there many ways of measuring them and turning them into data; and given some integers in whatever programming language, interpreting them properly needs help.

Exercise 24. Imagine two different ways to measure a distance and turning it into an integer. Make up two different interpretations of an integer as a weight. Research how many different ways different people use to converse about temperature.

Let’s next look at each step for designing functionality and how each helps readers understand code.

The purpose statement for pieces of functionality concisely describe what is computed; occasionally it describes how the result is computed, namely when the underlying algorithm is complex; and it should explain to which task in the problem statement it is linked. Many times a well-chosen method or function name accomplishes all three goals. But, it is also true that too often developers conflate tasks, have overlapping computations, and complicate ways to express a computation—without explanation. A reader must then wonder whether the complexity is intrinsic—or bad coding. If a creator starts the development with a clear focus—a goal of addressing just one (major) task—a lot of these problems are avoided.

In many cases, a type signature tells readers almost everything they need to know about calling a method or function if it comes with a good name (and possibly a purpose statement). The combination saves time because a reader can skip the actual definition during a first pass over some component. This point holds especially in settings where programmers favor immutability; a basic method must compute its results from the values of its inputs and the object’s fields. In addition, a type signature is critical for someone who wishes to use the function for some other code; type signatures enable IDEs to make up essential hints, say, in what order arguments are passed. While adding a type signature is mandatory in statically typed programming languages, it is also important to write them down in untyped (or optionally typed) languages. They play the same role in these contexts, and some IDEs look for properly shaped comments that look like type signatures.

Yes, programming to a type signature in a language without type checking takes mental discipline. The word “untyped” implies that the language comes without a pre-defined notation for formulating types and, hence, it cannot check the consistency of type annotations with code. Then again, the lack of a pre-defined Maintaining mental discipline is hard, which is the primary reason why many developers prefer typed languages. Types aren’t necessarily checked properly, though. Worse, typed-checked programs may still go wrong in ways that are essentially type errors. type notation gives the developer the freedom to superimpose a rigorous notation that fits the problem. Writing down signatures in this notation; defining all their elements; and programming to all these is then the equivalent of mentally declaring and checking types—and readers of untyped code will be grateful if both are done properly. While it is not a perfect substitute for types, it will be helpful.

Working through examples either leaves behind a “paper trail” of thoughts behind a complicated design and, at a minimum, yields unit tests. Both are extremely useful. Leaving behind a paper trail is imperative when a method implements a complicated algorithm. It illustrates how the method works with a concrete example, which gets the reader started. When combined with a look at the data representation, such worked examples also illuminate how the function takes care of other cases or corner cases.

A unit test serves a future reader and maintainer both as an illustration of what the function computes and what its calling protocols are. For both aspects, it is ideal if a programming languages allows developers to place short unit tests next to a function in the code. Here is an example of how this works, specifically how it works for a Racket version of the onTarget method from Names Matter:

Even in Java, where unit tests cannot be placed next to a signature in an interface, developers follow a particular system of creating parallel directories and placing unit tests there. Everybody in this ecosystem knows about this system and can find examples (if not as conveniently as in Racket). IDEs help with this task; their attached testing framework look for the tests in these places and runs them on demand. Again, it is all about systematic development, protocols that programmers follow so that their successors can benefit.

The outline of a definition seems to become invisible once a developer fills in the gap to complete the code.—Stop! Think back to reading essays. Does the outline truly disappear? Can you tell whether the author had an outline in mind or just started writing?—While an outline might be unimportant for some simple functions—atomic or composite—an experienced developer can actually see it as soon as it comes to data-structure traversals. Suppose that a function’s input is a list, that is, a linear data structure. Depending on the chosen language, a reader will expect to find a comprehension, a loop, or a structurally recursive function—three equivalent ways to traverse a list and process each item. Code that processes the list in a non-structural way causes cognitive dissonance in the reader; colloquially, the reader is likely to be stumped. In this case, the creator made one of two possible mistakes: the outline is done wrong or the definition is missing a concise comment that explains the workings of the algorithm with a how statement and worked examples.

Again, systematic development is about both creating and comprehending code. When developers follow such guidelines, they make themselves productive. A developer who knows about these guidelines can then easily comprehend the code weeks, months, or even years later,

23 Code Inspections, Systematically🔗

If developers design code systematically, they can also present it using the design system. Starting from the problem statement, they can show how their data representation mirrors the concepts of information found there. The problem statement also dictates the pieces of functionality needed, so it should justify the entry-point functions and methods. When it comes to composite pieces of functionality, the developer may need to explain the design of the data that flows from one piece to another. Finally, the design steps for methods provide the scaffolding for presenting those.

Conversely, when developers review the code of their peers, they can use the principles of systematic design to understand and critique the product. They can check whether the data representation matches the description of the information in the problem statement. They can request a purpose statement if a function looks incomprehensible and its name doesn’t help understanding it.

The ideas presented in the preceding section make up one particular system of design principles. This section demonstrates how these principles help with code inspections. To make this concrete, we first introduce a variant of the Ticket to Ride problem from A Sample Project: Analysis, Discovery, Planning: the Labyrinth game.

23.1 The Labyrinth Game: A Problem Statement🔗

A Sample Project: Analysis, Discovery, Planning presents the analysis of a games-for-hackers project. A company provides game servers to which hackers can connect automated player components. The company’s idea is to use variants of board games, initially Ticket to Ride. Another game under consideration is Labyrinth.

The game description implies the existence of at least two pieces of functionality that participating hackers must implement for a data representation of the board:

23.2 Presenting Systematically Designed Code🔗

If a milestone involves the development of a data representation, a presenter starts with an overview of the chosen data structures. For complex choices, it is best to include a justification and examples; for simple ones, a presenter may skip those.

// board representation for a game of Labyrinth

public class Board {

private Tile[][] grid; // row major

public Board(Tile[][] grid) {

\underline{this.checkDimensions(grid);}

\underline{this.checkGemUniqueness(grid);}

this.grid = grid;

}

// raise an exn if the dimensions don't satisfy the spec

private void checkDimensions(Tile[][] grid) {

...

}

...

}

// tile representation: gems plus path segments

public class Tile {

private UnorderedPair<Gems> gems;

private Char segments;

}

Figure 47: A Java data representation for the game of Labyrinth

... in the Board class ...

// raise an exn if any two tile display the same pair of gems

private void checkGemUniqueness(Tile[][] grid) {

Set<UnorderedPair<Gem, Gem>> seenGems = new HashSet<>();

for (Tile[] tileRow : grid) {

for (Tile cell : tileRow) {

if (seenGems.contains(cell.getGems()))

throw new IllegalArgumentException("duplicate gems");

seenGems.add(cell.getGems());

}

}

}

Figure 48: A Java constructor “contract” for the game of Labyrinth

Figure 49: Doodling for the development of the board representation

The presenter could have shown this diagram at the very beginning of the code inspection but injecting it into the inspection now is also a good choice. For the first part of the inspection, Board and Tile are the most relevant classes; the diagram for their relationship is trivial. By delaying the diagram to this point, it provides a good overview of the data needed to design the requested functionality.

class Board {

...

// effect: slide column `n` of this board if `d` is vertical;

// otherwise slide row `n` in direction `d`---by inserting `in`

// return the tile that's pushed out

public Tile insertAndSlide(Tile in, int n, Direction d) {

\underline{this.checkConsistency(n,d);}

Tile newSpare;

if (d.isVertical()) {

Tile[] seq = this.extractColumn(n);

newSpare = slide(seq,in,d);

replaceColumn(n,seq);

}

else {

Tile[] seq = this.extractRow(n);

newSpare = slide(seq,in,d);

replaceRow(n,seq);

}

return newSpare;

}

// raise an exn if `n` and `d` are incompatible

private void checkConsistency(int n, Direction d) {

... this.grid ...

}

...

}

Figure 50: Java method for sliding a row or column

class Board {

...

// slide `seq` of this board in direction `d` by inserting `in`

// return the tile that's pushed `out`

private Tile slide(ArrayList<Tile> seq, Tile in, Direction d) {

Tile out = null;

for(int i = d.start(); d.hasNext(i); i = d.next(i)) {

out = seq.get(i);

rowN.set(i,in);

in = out;

}

return out;

}

private ArrayList<Tile> extractRow(int n) {

... this.grid ...

}

private void replaceRow(int n, Tile[] seq) {

... this.grid ...

}

private ArrayList<Tile> extractColumn(int n) {

... this.grid ...

}

private void replaceColumn(int n, Tile[] seq) {

... this.grid ...

}

}

Figure 51: Auxiliary Java methods for sliding a row or column

23.3 Inspecting Systematically Designed Code🔗

class Board:

""" Represents the game Board, a matrix of Tiles

Args:

rows (int): its height

cols (int): its width

"""

def __init__(self, rows: int, cols: int, spare: Tile):

self.rows = rows

self.cols = cols

\underline{self-spare: Tile = spare}

self.board: List[List[Tile]] = self.__randomized_board()

\underline{self.last_slide_move: Optional[Slide] = None}

Figure 52: A Python data representation for the game of Labyrinth

So let’s take a look at how these problems may show up in a code walk and how a (head) panelist can use the design principles to re-direct the presenter and make the inspection a success. To keep things familiar and yet inject some variety, the inspection covers the board design combined with the reachability functionality for the Labyrinth game; ssee the first page The Labyrinth Game: A Problem Statement.

In sum, this conversation shows how a panelist can use the planning and the representation statement to inspect the actual code. The planning process separates the representation of the game state from the representation of a game board; the latter should really just mirror the physical reality of the board. While the representation statement seems to suggest that the code implements this mirroring, going through the five lines of the constructor reveals that this is not the case. Finally, by keeping the remaining design principles in mind—especially unit testing for the requested functionality—the panelists exposed another weakness of the code base.

import collections

class Board:

...

def __horizontal(self, side, row, column, accessable_tiles): ...

def __vertical(self, side, row, column, accessable_tiles): ...

def __adjacent(self,row,column):

tile = self.grid[row][column]

accessible_tiles = []

for s in tile.accessible_sides:

if s == "left" or s == "right":

self.__horizontal(s, row, column, accessible_tiles)

else:

self.__vertical(s, row, column, accessible_tiles)

return accessible_tiles

def reachable_tiles(self, row, column):

"""

returns list of all accessible locations

"""

queue = collections.deque()

queue.append((row,column))

accessible_tiles = set()

path = []

while queue:

row, column = queue.popleft()

if (row, column) in accessible_tiles

or self.grid[row][column] == 0:

continue

accessible_tiles.add((row, column))

path.append((row, column))

for neighbor in self.__adjacent(row, column):

queue.append(neighbor)

path.remove((row,column))

return path

Figure 53: Python board functionality for the game of Labyrinth

class Board:

...

def reachable_tiles(self, row, column) -> Set[Tuple[int,int]]:

"""

returns the set of of locations reachable from (row,column)

uses a worklist algorithm of positions-still-to-visit

"""

reachables = set()

worklist   = collections.deque()

worklist.append((row,column))

while worklist:

row, column = worklist.popleft()

if (row, column) in reachables

continue

reachables.add((row, column))

self.__add_adjacents(row, column, worklist)

return reachables

Figure 54: Reacting to the code walk

23.4 A General Guide to Code Inspections🔗

As the preceding subsections show, presenting and inspecting code make up two sides of the same coin. The same principles apply to both: the presenter uses them to guide a reader through a code (re)design; the panelists uses them to question the design of the code (base). While the preceding subsections illustrate this idea with examples, this section presents a general guide to both sides of code inspections. The key recommendation is to create README files that serve both as outlines for a code inspection and as guides for future readers of the code base.

23.4.1 README Files🔗

Documents: Start the README, Before the Coding Begins suggests that software developers should place the design ideas into a README file at the top-level of a code repository. Once developers turn to the creation of code, they should update this README file with comments about the code. That way it can serve as a living explanation of the design rationale and a navigation document for future maintainers. As the code base grows, the README file may grow too large for a structured document. The simplest way to break it up into manageable chunks is to equip each folder with a README file and to link these files with each other like the chapters of a book.

A top-level README file may contain a brief overview of the specification, with links to other documents and readings; download and installation instructions; links to a user guide if needed; instructions for running the program(s), the integration tests, or the complete set of unit tests; a table of contents pointing to the READMEs in various folder; and diagrams that explain the most important static and dynamic relationships among the components of the code base.

The README files in subdirectories have a local focus: the code in the files and its purpose. Assuming each subdirectory corresponds to a distinct component of the project, its README starts with a purpose statement for the component and comes with a table of contents that lists all the files in the folder and their purposes. If the code uses a class-based language, the files may contain classes, and the explanations in the README file clarify how they relate to each other statically and dynamically.

Context

|

| new

o = | ---> Observer

|          |

|          |

|          |

|          |

|          |

|          |  new(O)

|          | ----------------------> Referee

|          |                            |

|          |                            |

|          |   update(State s)          |

|          | <------------------------- |

.          .                            .

.          .                            .

%% before each legal turn                     .

.          .                            .

.          .                            .

.          .                            .

|          |                            |

|          |   update(State s)          |

|          | <------------------------- |

|          |                            |

%% until the game ends:                       |

|          |                            |

|          |   game_over(State S)       | (last State)

|          | <------------------------- |

|          |                            |

|         ---- the observer shuts down  |

|                                       |

Figure 55: An example of a README diagram of dynamic relationships

While tools may exist to generate such diagrams from code, the results tend to be uninformative, containing too much or too little detail. Developers are better off drawing such diagrams on boards and placing scanned copies into the folders. With mark-down formats, it is easy to include such diagrams in README files.

23.4.2 Presenting🔗

If the README files are kept up-to-date every time, a developer can use them to get a code presentation started. As a matter of fact, with such READMEs the presentation almost runs itself. To start with, the developer should point to the problem statement (link) in the README and remind the panelists of the role of the component in this context. Even if a developer presents just a change to a component, it is good practice to begin the code walk with such a reminder.

Before going into any details, the developer next provides an overview. If the READMEs include diagrams for the static and dynamic relationships, the developer should use them, focusing on those parts that are relevant to the goal of the code walk.

As a reminder, the general goals of a code presentation are to discover design flaws, errors, and comprehensibility problems. Given these goals and the general constraints on time for inspections, the developer must carefully choose what to present. That is, the presenter should explicitly state the goal(s) of the code walk, meaning those pieces of code that will be the focus of the presentation—and how to get there from the global overview:

An explanation of a path has two components: the static program text and the dynamic call chain. The first is needed because a future reader must start with text; the dynamic call chain(s) is needed to understand whether the calls are legitimate and the function works for all calls. For a concrete example of where both are needed, see Pushing Back During a Code Inspection, especially the sample dialog on see the second page.

As a developer presents a path from the entry point(s) of a component—for example, the public methods of a class; the calls from an integration test script—each unit of code deserves a basic high-level explanation. Once again, if the table of content of a corresponding README file can be generated, the developer knows that each module or class-level unit comes with a purpose statement and can leverage it for the presentation.

In sum, a presentation proceeds in a present top-down manner. The “top” is the big picture; the “down” is the path from the entry point(s) of a component to those pieces of code that deserve special attention. The “bottom” are those pieces of functionality with which the developer(s) had a hard time and that just need more pairs of eyes on them.

As for the interactions with the panelists, a presenter is usually confronted with three kinds of questions. The first and most basic kind is about the comprehensibility of what is written down. Since panelists are potential future readers, a presenter’s task is to recognize when such an issue requires a change and when not; when in doubt, take a note and improve. Perhaps a simple rule of thumb is that once a second presentation attempt has failed, it is time to think of a different way of writing this code.

The second kind of question is about bugs. In this case, the conversation proceeds until the developer has understood the mismatch between the specification and the code or has justified why there is no mismatch. For this latter case, the panel may wish to analyze the problem as a potential comprehensibility problem.

Finally, the third kind of conversation is about raise design concerns. In all likelihood, a developer has already considered design alternatives. Hence, presenting the chosen design as the best understood trade-off may pacify the panel; if not, the focus must be on understanding why the panel considers the design flawed so that the developer can go back and come up with an alternative or an improvement.

23.4.3 Inspecting🔗

Before a developer moves from the overview to the presentation of the code itself, it is important to ensure that all participants understand which pieces of the component deserve special attention. The head reader must make sure that the presenter stays on the path from the overview to these attention-worthy pieces of code. In other words, if the presenting developer spends time on obvious or irrelevant code, the head can re-direct.

While the preceding items explain the mechanics of how to follow a presentation of a software component, they leave open when to raise design questions, how to expose bugs (mismatches with the specification), or where to point out readability questions. Let’s tackle these questions, one at a time.

Developers design at several levels. They design components and interactions between components, after getting at least a preliminary understanding of a software system’s requirements. Project focuses on this level. This high-level design spells out coarse specifications for components. For example, it may come with a request for a referee component with a game observer. The details of this component—how to represent the referee’s game knowledge, how to interact with the observer—are left to the designer(s) of the component, which brings us to the second level of design, the one likely to be presented at the beginning of a code inspection. Finally, as the introduction to this part spells out, developers should also bring a “design attitude” to the creation of data representations and functionality.

Based on this summary of design levels, the answer to the first question is straightforward. Assuming that the specifications have been inspected (see Interface Inspections, Systematically), panelists encounter the refinement of a component specification into a design near the beginning of a well-organized presentation. If they see something unusual or spot a gap in the explanation of purpose statements for pieces (classes, modules) and static or dynamic relationships, they must question the presenter there and then while the relevant information is on the screen. In contrast, questions concerning the systematic design of data representations and pieces of functionality are much more naturally discussed while the actual code is on the screen.

Lastly, panelists represent future readers of code, meaning they should be able to comprehend code in a reasonable amount of time. If any piece of code is difficult to read, the panelists stop the code walk, state the code’s purpose, and read it aloud. Doing so, slows down the presentation and may eliminate the comprehension obstacle. If it doesn’t, the presenter can request a description of what the obstacle is so that any corrective action addresses it directly.

In all cases, the conversation should not continue until the presenter and the panelists have agreed on an issue, be that a design issue, a correctness problem, or a comprehensibility obstacle. It is a good practice for the head panelists to have the presenter re-state what the issue is as the last step before the presentation continues. Also, in no case should a panelist push a re-solution of any issue—unless the entire team agrees that the severity of the issue demands it. Inspection time is too restricted and too valuable to try to resolve problems on the spot.