CSE 331: Software Design & Implementation

CSE 331: Topics

The course is organized into 10 topics, and we cover (roughly) one topic per week. Topics in the future are subject to change.

1. Intro to JavaScript

We start our journey to writing more complex, full-stack applications by learning a new programming language: JavaScript (JS). We will need JS to write code that runs in the browser (in Topic 2), but we can also use JS to write code that runs in the server.

We do not assume any prior JavaScript knowledge. We will cover all the parts we need in lecture. After learning the basics of the language, we will see how to write our own HTTP server in JS and then spend some time discussing how to debug the problems that we find in our code.

2. Intro to the Browser

In this topic, we switch to writing code that runs in the browser, presenting a User Interface (UI) that the user can interact with. We will discuss how UIs are written in modern web apps versus other settings and see how the code of modern web apps gets split up into manageable pieces.

3. Client-Server Interaction

Having written already clients and servers separately, in this topic, we see how to connect them together into full stack applications. In this setting, the potential for difficult debugging is substantial. Bugs in the server can show up as failures in the client and vice versa, in both cases requiring us to debug across multiple programs to find the bug.

4. Specifications

Before we can talk in detail about correctness of our code, we need a definition of what the code should do. This is called a “specification”. It is important that our specifications are precise. In addition, we would like our tools for writing specifications to work for any language, not just TypeScript. For those two reasons, we will use our own mathematical notation that is independent of programming language. (And we will find additional uses for this notation in subsequent topics.)

5. Reasoning

Now that we have a better understanding of the work required to write and debug more realistic applications, we can see that being a productive programmer requires another tool, reasoning, which allows us to find the bugs missed by type checkers and unit tests. In this topic, we will see how we can reason formally and prove the correctness of code that does not involve any mutation. (Code with mutation is harder to reason about and will be examined in future topics.)

6. Floyd Logic

In this topic, we continue our study of reasoning, now moving to slightly more complex (and more common) types of code. Previously we considered code without mutation, in which complex calculations are performed via recursion. Here, we will look at code that mutates local variables. In particular, this allows us to write loops instead of recursion. However, it also makes reasoning more complicated, necessitating new reasoning tools.

7. Abstraction

Now that we have learned our full set of tools for ensuring correctness, we turn our attention to the other properties of high quality code: understandability, changeability, and modularity. These properties are often provided by means of abstraction, which allows us to hide details of some parts of the code from other parts. This makes the code easier to understand and change, and allows multiple people to work on parts of the code simultaneously (modularity).

We will begin by studying how to hide the details of code via “procedural abstraction” and then see how to hide the details of data via “data abstraction”.

8. Tail Recursion

In prior topics, we have seen problems that can be solved either with recursion or with a loop, showing that these two are sometimes alternatives to one another. In this topic, we clear up the relationship between them by showing that loops are equivalent to “tail recursion”, a special case of general recursion, and demonstrate how to translate between the two, allowing us to use whichever is more convenient for the current setting.

Because summer quarter is shorter, we cannot cover every topic in as much depth as usual, so Tail Recursion was only covered briefly in lecture (8/8). The full slide deck and some written notes are linked for anyone interested, but only the content discussed in lecture is fair-game for the final exam.

9. Arrays

In Topic 7, we looked at ADTs and saw that they describe the interfaces of many well-known data structures. However, the most commonly used data structure in imperative languages — arrays — was notably missing. In this topic, we rectify that omission.

As we will see, arrays create new reasoning difficulties that do not occur for alternatives like lists and basic trees. Their use of indexing gives us extra power but comes at a cost of more complex reasoning, requiring the use of “for any” facts to describe their known state. These are inherently more complex, but we can mitigate some of that complexity by turning to pictures as a simpler way of describing them.

10. Object-Oriented Programming

In our last topic of the quarter, we look at some difficulties that arise in object-oriented programming, especially when trying to create subtypes. We then look at solutions (in the form of design patterns) for working around some of the sharp corners of these languages.