I’m still working on the project going through MIT’s Open CourseWare to figure out what I missed by not doing a Computer Science degree. Software Construction is course number eight and mostly focuses around programming using Java. Of all the courses so far, this one is the most related to actually writing software. Unfortunately, there weren’t any video lectures for this course and the core content was split up into 27 readings. Still, these contained a good amount of detail being able to get a pretty good deep dive of Java while also providing introductions to a lot of other categories in the field of programming.
This course talks about the basics of programming while going a bit further than Intro to CS, talking not only about writing programs, going into topics such as version control, networking, concurrency and regular expressions. The course focuses on writing code that is safe from bugs, easy to understand and ready for change and reading ties back into these three categories. Beyond writing classes and methods and testing them, this is the first course so far to talk about what happens when multiple clients are connecting to a program at once, going into techniques for avoiding bugs caused by concurrency and writing safer code. It also uses regular expressions to discuss writing parsers and using those to write languages.
MIT Courses #8 – Software Construction – 6.005 by Prof. Robert Miller and Dr. Max Goldman
Getting Started
The layout of this course is quite different from previous Open CourseWares and is all on a text based website. The core of the course content is 27 chapters of readings, along with 5 problem sets and a project to complete. Before this, there’s a getting started section which includes a step by step guide to installing Java and the Eclipse IDE. After this, the section shows the ls, cd, pwd, and mkdir command line arguments and shows you how to get started installing git, using git config to set colors and alias commands and a short introduction to git’s actual usage explaining how to clone, and add, commit, and push, pull, and merge, as well as check differences and the current status of a file or repository. The git introduction is a very basic introduction to the core commands.
The second part in the Getting Started section is MIT’s introduction to the basics of writing Java code via four powerpoint presentations seeming to correspond to the first four lectures from MIT’s Introduction to Java Programming course. The first of these starts by showing that input and output devices access the central processing unit (CPU) which accesses the memory, and that the CPU’s instructructions for z=x+y would be to read the locations of x and y, add them, and write the output to z. Programming languages are easier for us to understand, but need to be translated for the CPU to understand them. Java is apparently the “most popular” programming language and it runs in a virtual machine known as the JVM. It’s more complicated than Python but simpler than C++. Java source code (.java files) is compiled into bytecode (.class files) via a “javac” tool. The first program shown is
class Hello {
public static void main(String[] arguments) {
system.out.println(“Hello world.”);
}
}
Hello is a provided class name, and system.out.println is a command that will output the passed value to the console. Java can store and manipulate boolean, int, and string values, along with “double” values which are similar to floats. You need to specify a variable’s type when it’s set, so “double badPi=3.14” and “string intro=”Hello world” would create variables of the appropriate types and assign variables to them. These can be reassigned later, but only to the same type and the variable intro could replace “Hello world.” in the above code for the same effect if that line were in the function block. Some operators that can be used are “=”, “+”, “-”, “*”, and “/”, which assign values, add, subtract, multiply and divide respectively, following PEMDAS for order of operations (parenthesis work as well). “+” can also be used to combine two strings. If used with a string and a number, the number will be treated as a string.
The second shows that division acts differently when run on integers and doubles. For “double a = 5.0/2.0;”, “a” will equal 2.5, but for “int b = 5/2;”, b will only equal 2, and for “double c = 5/2;”, d will equal 2.0. Java verifies the type assigned to a variable matches its type, so “String five = 5;” will give an error, but “int a = 2;” will naturally work. Additionally, “double a = 2;” will be able to work automatically, setting a to 2.0. Trying to set a value with decimal points to an int won’t work unless called specifically casted with “double a = (int)18.7;” which would give 18. Since it rounds down, “double a = ⅔;” would normally be 0.0, but if cast “double a = (double) ⅔;”, a would correctly be 0.6666…. Methods are defined within a class and can be referenced directly by name within other methods in the same class.
For instance, a class square defines printSquare(int x) which prints x*x and main(String[] arguments) then calls it via a “printSquare(3);” line. These are both defined like Hello with “public static void” and only an int value can be passed to printSquare. A method can also take multiple inputs, such as “public static void times (double a, double b)”. The “void” seen so far means that no type of output is returned. A method could also output a return value by specifying the type where void is and including a return statement to output a value matching the type. If a method isn’t void, it has to return something. For instance, “public static double square(double x) { return x*x; }”. Variables are only accessible in the block where they are defined and a parameter sets the name of the input to the actual input in that scope (ex. x becomes 2).
Methods are building blocks for larger programming and abstraction is where the user of the method doesn’t need to know how it works. Some built in methods for math are “Math.sin(x)”, “Math.cos(Math.PI / 2)”, “Math.pow(2, 3)”, “Math.log(Math.log(x + y))”. Conditional statements also exist in java, in a block such as “if (x>5) { System.out.println(x + “ is > 5”); }” within a method, and “else if” and “else” blocks can also be used when the “if” statement isn’t true. Comparison operators in Java are usual “>”, “<”, “>=”, “<=”, and “==” and boolean operators are “&&” for logical AND and “||” for logical OR. Integers can be converted to strings with “String five = Integer.toString (5);” or via ‘String five = “” + 5;’. The other way around is also possible, with “int five = Integer.parseInt (“18”);”. The second powerpoint ends saying never to use “==” on doubles. An “already defined” error will occur if you try to redefine the same variable by specifying type.
The third powerpoint talks about good programming style, loops and arrays. To make code more readable, it’s important to use meaningful names such as “firstName” and “temperature” instead of a and b. Unlike Python, indentation isn’t required for Java to function, but it is still good practice to indent each block as it makes code more readable. Similarly, whitespace can be added between variables and operators to make code cleaner, and blank lines can be added. Lastly for style, avoid duplicating the same tests across if statements.
The next topic for the second powerpoint is loops. First up, the while operator runs a loop while a condition is true with “while (condition) { statement }”. It’s important to make sure that something in the statement will cause the condition to eventually finish. The other loop operator is “for” which takes 3 conditions, “for (initialization;condition;update;) { statement }”. For instance, “for (int i = 0; i < 3; i=i+1)” would set i’s initial value to 0 and run while it’s less than 3. After each run of the loop, it would then increase i by 1 (i++ would also work). The “break;” command can be inserted into an if, while, or for block to end it as well. Similarly, “continue;” will stop the current iteration of the loop and move to the next. Loops can also be nested.
An array in Java is an indexed list of values of any type, but all elements must be the same. An array starts at element 0 and goes to it’s length -1. It’s defined per type such as “int[] values = new int[5];” and items can be accessed by index “values[0] = 12;”. Accessing “values[5]” or higher in this case would cause an error at run time. Arrays are a type as well, so you could have an array of arrays, “int[][] values;”. You can also specify an array with “int[] values = { 12, 24, 36, -48 };”, but only when the variable is declared. Arrays also have a built-in length property. “values.length” would give value’s size. Loops are typically used to loop through array elements setting a while condition to be while i is less than values.length, for instance.
The fourth and final powerpoint in the Getting Started section starts off with a recap and briefly talking about debugging. Printing to the console is a good method for seeing what your system is doing. Formatting is also useful for helping debug your code and the find function can make sure variables are showing up where they’re supposed to. Next, is another introduction to object oriented programming, which can be used to represent the real world. Objects group primitives such as ints, doubles and chars, with objects such as strings. Classes are used to help avoid having a lot of repetition when defining the same type of objects. They are defined as seen before with “public class Name {“ along with properties initialized on the object and methods set, both only requiring “type name” to specify. For instance,
public class Baby {
String name;
int numPoops = 0;
Baby(String myname) {
name = myname;
}
void poop() {
numPoops += 1;
}
{
would define a baby class and “Baby john = new Baby(“John”); could be used to create a new instance. Class names are capitalized and one class is one file. The Baby method here would be used as a constructor to set the baby’s name. This should be named with the class name and shouldn’t return anything. An object’s properties can be accessed via name.parameter, such as “john.name” and method’s the same way, “john.eat(1)”.
Comparing primitive types to reference types, primitives are basic Java types where the actual value is directly stored in the variable. These include int, long, double, boolean, char, short, byte, and float. Reference types are arrays and objects such as String, int[], Baby, etc. Object’s are too big to directly be stored in a variable so the variable stores a pointer number called a reference to locate the object it stores elsewhere. When using “==” to compare two instantiated class objects, they won’t be equal as the references will be different. You can set a variable to one instance of an object to another to update the reference, but changing a property on a referenced object won’t update the reference.
The “static” seen in most declarations so far means the field or method is defined for the class declaration and isn’t unique per instance. Most fields and methods will be static. For instance, you could add the following to Baby,
Static int numBabiesMade = 0;
Baby() { numBabiesMade += 1; }
to keep track of how many babies have been created. Similarly, “static void cry(Baby thebaby)” is similar to “void cry()” and referencing “thebaby.name” in the former vs “name” in the latter. This is because non-static methods can access static methods, but not the other way around.
Reading 1: Static Checking
The first reading focuses on static typing and three main properties for writing good software. The hailstone sequence starts with a number n and the next number is n/2 if n is even or 3n+1 if its odd, ending when the sequence reaches 1. For instance, [2,1] or [5, 16, 8, 4, 2, 1]. Some can go on for a while. It’s assumed though unproven that it will eventually stop and named as hailstones bounce up and down in clouds before building weight to fall. This will be used as a running example.
int n = 3;
while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n = 3 * n + 1;
}
}
The most important difference between Java and Python code is that Java requires types to be specified. A type represents a set of variables and operations that can be used with them. Primitive types include int, which is for numbers between positive and negative 231, longs are used for larger integers going to positive or negative 263. Booleans are for true or false values, doubles are for floating point numbers, and chars represent single string characters. Object types exist such as Strings, representing a sequence of chars, and BigInteger representing an arbitrary size integer and acting like a Python integer. Primitive types are written in lowercase and object types start with a capital letter. Characters such as “+” or “-” invoke operations which are functions that act on objects and potentially create new ones. Operations can also be called directly as functions or as methods of other objects. For instance bigint1.add(bigint2) calls add which takes two BigIntegers and adds them to create a new one. Operations can sometimes be overloaded when the same operation name is used for difference types. For instance, “+” can add numbers or concatenate strings.
Java’s is a statically-typed language and variable types are known at compile time, allowing it to figure out what types expressions should result in. On the other hand, Python is a dynamically typed language, so checking is done while the program is running. Static typing is a kind of static checking, meaning checking for bugs is done at compile time. Static checking, dynamic checking, and no checking are the three options a language can provide for automatic checking with no checking being the least desirable option. Static checking can help find syntax errors, wrong method and property names, wrong number of arguments passed, or wrong argument or return types. Python still uses some dynamic typing for its syntax errors. Dynamic on the other hand, can check illegal argument values, such as dividing by 0 which would seem correct based on type but fail in practice. Incorrect return types, out of range indexes and calling methods on null values can also be caught at run time via dynamic checking. Static checking is about types and guarantees variables are from the proper sets, but the exact value isn’t known until runtime when index out of range or divide by zero can occur.
Java’s primitive types aren’t truly numbers and don’t behave like integers as we’d expect. For instance, dividing integers 5/2 will only give 2 since 2.5 can’t be represented by the data type. Integer overflow can occur since int and long have minimum and maximum values. Going too far in one direction can cause the value to overflow and wrap around giving an incorrect number in the range. Float and double can have data types that aren’t real numbers such as NaN, POSITIVE_INFINITY and NEGATIVE_INFINITY. These must be dynamically checked.
Java has both array and list data structures. Arrays in Java are created with a specified unchangeable length, such as “int[] a = new int[100];”. You can index, assign to an index and access its length property. The Hailstone code is shown adding the sequence to an array instead, but it creates a problem as using an array of fixed size won’t work if the sequence is longer. Overflowing a fixed length array is a common exploit in C and C++. Lists are a data type with a variable length sequence, created with “List list = new ArrayList();”. List’s are interacted with via “list.get(2)” or “list.set(2,0)” for indexing or setting the second element respectively. “list.size()” is used instead of “a.length” for getting the length of the list. “List” is an interface which is a type that can’t be constructed with new but specifies the operations it must provide. “ArrayList” is a class providing implementations for the interface’s required operations, and is the most commonly used list implementation, though others such as LinkedList exist. Lists can only be specified for object types and not primitives, but primitives have equivalent object types which are capitalized and spelled out such as Integer for int. These can be automatically converted between for calculations. Hailstone can be safely written out with an array list which will automatically grow to fit needed space.
Java statements are usually inside methods which are inside a class, so a hailstone class is created with a “public static List hailstone Sequence(int n)” is created which creates an ArrayList and adds the hailstone sequence and returns it. Public means any code in a program can refer to a class or method while private can be used for safety and immutability. Static means the method doesn’t take a self parameter and can’t be called on objects. So the “Hailstone.hailstoneSequence(3)” can be called anywhere.
When a variable is assigned you change where its arrow points. Assigning it to a mutable value means changing references. Arrays are examples of mutable types while strings are immutable. Immutability is a design principle and immutable types can’t change after creation. You can also force an immutable variable with a final keyword, such as “final int n = 5;”, giving static checking for immutable references. Final is useful for declaring method parameters and local variables as much as possible. Programs are written both for communicating with computers and other people and final’s can help document the code for readers as well. It’s encouraged to write, document and test as you go and to write to defend code against mistakes by writing it well. The course goal is to write correct, bug safe code that is easy to understand and ready for change which is applicable to all languages. Java is used despite students already knowing Python because of safety such as static checking, ubiquity since its widely used in research, industry, web and client programming and native Android programming. Python is still behind Java’s ecosystem in terms of tools and libraries.
Reading 2: Basic Java
The second reading starts by telling readers to go through Oracle’s Java tutorial or the Getting Started section, before moving on to snapshot diagrams which are used to represent the internal state of a program at run time, consisting of its stack (methods in progress and local variables) and heap (objects that exist). In this diagram a primitive is represented as a bare constant with an incoming arrow from a variable or object field. Object values are circled and labeled by type, field names can be written inside. These can help distinguish changing variables and values by crossing out and adding a pointer or crossing out and adding a new variable. Immutable types are drawn with a double border and an immutable reference to a mutable variable uses an arrow with two lines. In comparison to immutable strings, StringBuilder is a built-in Java class representing a string that can be appended to and changed.
The Java Collections Framework contains tools for managing collections of objects. A Java List acts similarly to Python’s growing and shrinking as items are added. In addition to methods seen before, “list.isEmpty()” will check if the list is empty. In the diagram, a list called cities would be represented as an arrow pointing from “cities” to a circle with “List” in it and variables 0, 1, and 2, pointing outside the circle to 3 city names. A set is an unordered collection of unique elements, with methods “s1.contains(element)” to check if a variable is present, “s1.containsAll(set)” for checking if a set is a subset and “s1.removeAll(s2)” for removing a subset. Python in comparison uses “e in s1”, “s1.issuperset(s2), s1>=s2” and “s1.difference_update(s2), s1 -= s2” for the same. A set’s diagram would have pointers to values outside the circle, not tied to variable names inside the circle. A Map in Java is similar to Python’s dictionary, including operations such as “map.put(key, val)”, “map.get(key)”, “map.containsKey(key)”, and “map.remove(key)”. In the snapshot diagram, each item in map’s circle points to a key and object it represents outside.
Java doesn’t allow you to create lists and maps with bracket notation, though you can create an Array with “String[] arr = { “a”, “b”, “c” };” and convert it with “Arrays.asList(new String[] { “a”, “b”, “c” })”, though the length created this way will have its length fixed. Unlike Python, these collections can be restricted to only contain the specified object type. List, Set and Maps are interfaces defining how types while leaving implementation to the users. ArrayList is the default implementation of List, HashSet for Set (though TreeSet is also provided for sorted sets) and HashMap is the default Map choice for the course. Similar to lists, the other two are defined “Set numbers = new HashSet<>();” and “Map turtles = new HashMap<>();”. Looping through collections can be done for list and set with “for (String city : cities) { … }” and maps with “for (String key : turtles.keySet()) { … }”. An iterator will be used under the hood.
A lot of the classes seen so far are part of the Java platform API (application programming interface) which is a large set of useful tools for programming just about anything. String is actually java.lang.String in the API, though the object can be created with double quotes. For “wrapper” classes representing primitives such as java.lang.Integer, Java can convert between them and primitive types. Lists and maps are from java.util.List and java.util.Map respectively and java.io contains File for representing a file on the disk, FileReader for reading text files, and BufferedReader for efficiently reading text line by line. Oracle’s documentation will show how to construct and use methods for each object as well as the parameters required and values returned.
Reading 3: Testing
Testing is part of a more general validation process to uncover bugs and increase confidence in a program’s correctness. Formal reasoning or verification constructs a proof that a program is correct. Usually crucial pieces will be formally verified. Code review is where someone else reads your code and looks for bugs, and testing runs the program on specific inputs to test results. It’s hard to assure perfect quality after testing and typically code will have 1 to 10 defects per kloc (thousand lines of source code). This is reduced to 0.1 to 1 with high quality validation such as in Java libraries and 0.01 to 0.1 in safety critical validation such as by NASA. Since large systems can have a million lines of code this can mean a lot of bugs are typically missed.
Exhaustive testing doesn’t usually work due to too large a set of possible test cases. Just haphazardly testing with radon inputs isn’t likely to catch unexpected errors. Random/statistical testing is less effective on software, where a system can seem to work on a broad range of inputs and fail at one point. Intel’s Pentium chip had a division bug affection 1 in 9 billion divisions and stack overflows or out of memory errors happen abruptly in the same way unlike in physical systems where evidence can show when a system is near failure. Test cases should be chosen carefully and systematically. As a test you want to make a system fail and find any vulnerabilities.
Testing early and often helps make debugging better and easier. Test-first-programming is one method where tests are written before code. First you write a function specification, then tests, and then the actual code which passes the tests. The specification will describe input and output behaviors and constraints on parameters. In code a specification will consist of the method signature and a comment describing what it does. Writing tests helps to understand the specification and can oncover problems in it before coding a buggy specification. An ideal test suite should be small enough to run quickly and large enough to test the program. Dividing tests into subdomains can help cover the input space and testing with one test from each subdomain can help vary tests, where different domains have different expected inputs and outputs (which can also be partitioned into subdomains). For example, BigInteger is a Java class that represents integers of any size and it’s multiply method can multiply two BigIntegers together. A specification would be.
/** * @param val another BigInteger * @return a BigInteger whose value is (this * val). */ public BigInteger multiply(BigInteger val)
The parameters expected and returned by the program are written in the comment above the definition to tell users what it does. In Java, “this” is used to refer to the current object rather than Python’s “self”. Multiply will effectively take the calling object and an additional BigInteger as parameters to produce a single product BigInteger. The input space consisting of all pairs of integers a and b can be partitioned so subdomains are made up of where both are positive, negative, or a is positive and b is negative, and vice versa. Special cases that could be checked are when a or b is 0, 1, or -1. Integers larger than the largest “long”should be tested in case int or long are used under the hood to see how it performs as opposed to smaller integers. Therefore, a and b values are chosen independently from each special case, small positives, small negatives, huge positives and huge negatives leading to 49 partitions. A test case would choose a pair from each of these partitions.
Bugs are often found at boundaries between subdomains such as zero between positive and negatives, maximum and minimum numeric types, empty collections and the first and last elements. Programmers can mistakes and often boundaries correspond to special cases in code. An example implementation of Math.max is also shown, which takes two parameters and is partitioned where a is greater than b, b is greater than a, and the two are equal. An example implementation of Math.max is also shown, which takes two parameters and is partitioned where a is greater than b, b is greater than a, and the two are equal. Additionally, the value of a and b are independently chosen from partitions where each is zero, positive, negative, a maximum, or a minimum integer. Partitions are created from the relationships between a and b, and each independent value category for a and b. After partitioning, you could cover every legal combination with one test case such as with multiply’s 49 test cases and 75 for max where possible (as a<b, a=0, b=0) wouldn’t work. Each part but not combination could also be covered separately to write less tests. Actual solutions are often somewhere between each part and a full cartesian product based on judgement.
Since the specification describes a function’s behaviors, blackbox testing choses test cases specifically based on the specification not related to the implementation. Max and multiply were examples of these. Whitebox testing (or glass box testing) choses cases related to the implementations, such as to hit different if/else cases or testing cache for repeated inputs. It’s important to avoid checking based on implementation as opposed to the spec, such as specifically checking for the current implementation’s NullPointerException if the spec allows for any exception for poorly formatted input. This will allow more freedom for the program to be implemented.
Documentation should be added for the expected behavior for edge cases and boundary values and comments explaining a test’s partition strategy and where to use an exhaustive cartesian product can be written as well to explain tests. A test’s covergate is how thoroughly is exercises the program. Statement coverage is if every statement is run by a test case, branch coverage checks every situation of an if/while statement is reached, and path coverage checks for every possible branch or path through the program is tested. Each of these is stronger than the previous. 100% statement coverage is rarely achieved since some defensive situations shouldn’t be reached. Full branch coverage is desirable but full path coverage is infeasible as test suites would be exponential. A strategy is to write black box tests and add more test cases until all important statements are logged. Code coverage tools such as EclEmma for Eclipse can help with writing tests. A typical goal is statement coverage for each reachable statement.
Typically, a program will test using a unit test for each individual module (method or class) in isolation. If a unit test fails then you can know the bug is the specific module. In comparison, an integration test tests a combination of modules or the full program, which are harder to debug on their own but still needed as one module may be expecting a different input from the one given by another. For instance, a web search engine could have getWebPage() and extractWords() methods, along with a makeIndex() method for creating an index Map by calling the other two functions. A test suite would want unit tests for getWebPage() and makeIndex() on various URls and sets of URLs respectively and for extractWords() for various strings. ExtractWords() should be tested in isolation even if it will be called in relation to other functions. Since makeIndex calls the other modules, stub versions of its modules could be written to attempt to isolate its functionality by returning mock content. Stubs are often called mock objects and are good when testing large systems. Running tests automatically can make things much easier, invoking modules on fix test cases rather than requiring manual checking, alerting developers if tests are OK or failed. JUnit is a tool for this in Java. Tests should be run when code is modified to avoid regressing or introducing bugs as you add features. Running tests after changes is regression testing. Inputs that cause bugs should be added to the test suite as regression tests. Test-first debugging is a strategy where you write a test for any bug that appears and then fix it. Automated testing and regression testing are generally used together and are best practices.
Reading 4: Code Review
A code review is a study of source code by people other than the original author, similar to proofreading a paper. It’s goals are improving code for clarity and correctness and improving the programmer by showing them new techniques or teaching them about coding standards. Much of the communication for open source projects is done through code reviews. Code Review is done both in open source and industry and usually a requirement for code entering main repositories. Large companies and projects typically have their own standards, such as Google Java Style which can specify even whitespace and braces locations based on preferences at the company. This reading goes over some general guidelines.
Don’t repeat yourself. Having identical code in multiple places means that buggy code will be duplicated and when one is fixed the other might not be. Copying and pasting is generally worse the larger the block copied is. Specifying methods can help with this. Commends should be used where needed as they make code easier to understand and document assumptions. A specification is a comment above a method documenting its behavior. This is typically a “Javadoc” comment which starts with /** and using @param and @return to specify those features of a method and document assumptions made. It’s also important to specify something adopted from elsewhere such as with “// see http://stackoverflow…”. This helps avoid copyright violations and out of date code. Avoid unnecessary comments that explain what the code itself is doing and assume viewers know the language, unless the code is particularly non-obvious.
Code should fail fast and reveal its bugs quickly. Static checking will be faster than dynamic which is faster than getting a wrong answer that could have future consequences. “Magic numbers” should be avoided and variables used in place of numbers except potentially 0 and 1. Hand calculated numbers should also be calculated with Java instead. New variables should be introduced instead of reusing older ones to store different unrelated values. Final should typically be used for method parameters and any variables where it’s appropriate. Final can be specified in a method definition such as “dayOfYear(final int month, final int dayOfMonth)”. Names should be long and descriptive and help avoid the need for comments. Names such as temp and data are due to laziness (whoops).
Different languages can have different lexical naming conventions. Python typically capitalizes class names, has lowercase variables and words separated by underscores. Java uses camelCase for method and variable names, CapitalizesClasses, writes CONSTANTS_WITH_ALL_CAPS_AND_UNDERSCORES and packages.are.lowercase.and.separated.by.dots. Method names are typically verb phrases while variables and class names are nouns. Abbreviations should be avoided. Whitespace can help make the code more human friendly. Spaces should be used and not tab characters. Editors should be set to replace tabs with spaces.
Global variables are variables with changed meanings and accessible and changeable anywhere in a program and should be avoided. These are defined with “public static” and should be changed to parameters and return values or put inside objects. Methods should return results instead of printing them to the console so they can be used by code instead of just seen. Humans should only need to interact with the highest level parts of the code unless debugging.
Reading 5: Version Control
Basically every software project uses version control for coordination between programmers. Dropbox, undo/redo and storing simple multiple versions of a file are examples of version control systems the student has likely used. Being able to go back to a past version is important if a mistake is made. In Unix, the diff tool exists for comparing files and version control systems have their own implementation. Diffs help pull back in working changes if a commit included a bug. Storing code online also helps make it retrievable. If versions get out of sync a merge can help creating a new version based on two code changes.
Even for a single developer, version control helps revert to previous versions, compare versions, push and pull version history to the cloud and merge versions that are based off a previous version. Adding a second develop means that a strict process is required and they’d need to come up with a shared naming structure since everything wouldn’t be in one person’s brain. Whole sets of files would need to be versioned together since they depend on each other. Uploading new source files with a new version doesn’t communicate the changes made clearly, so logs about changes would be needed with the author, changes, and date. Logs will also need to be merged and it should be easy to extract the files associated with a log entry. Branches in version control act as a parallel code universe for testing a new feature.
Git and other version control systems handle all of these processes. Centralized systems such as CVS and Subversion do only some of these, supporting a collaboration graph with a master server and copies communicating with the master. Everyone shares work to and from the master repository which is the only repository. Distributed systems like Git and Mercurial allow various collaboration graphs allowing for alternate versions of code and history and the ability to merge them when ready. Teams assign different repos different roles and more flexibility is allowed in distributed systems. In version control, a repository is a local or remote store of versions in a project, a working copy is a local, editable copy for working on. A version or revision is a record of the project’s contents at a certain time, with a change or diff being the difference in two versions. A file represents a single file in the project and the head is the current version.
Git is the version control system used for the course and is accessible via the command line. The course recommends the Pro Git book for everything we might need to know about Git. The three pieces of a Git repo are the .git directory, the working directory and the staging area and all Git operations work on a graph data structure storing all versions of files in a project along with log entries. The Git object graph is stored in the .git directory of the local repository. Git clone can copy this object graph from a remote to a local computer. The Git object graph isn’t in human usable form but normal copies of files at different points can be checked out. The default branch is master and additional branches aren’t used in the course, while necessary for real work. Git clone will checkout master by default giving a working directory of files.
For a convenient view of the graph structure, the course uses “git lol” which is set with ‘git config –global alias.lol “log –graph –oneline –decorate –color –all”’. Git’s project history is a directed acyclic graph and the backbone for the full object graph in .git. In the history graph, each node is a commit or version containing a snapshot of all project files at a point in time. Each commit is identified with a unique hexadecimal number ID and except for the initial commit, each commit has a pointer to its parent commit. Two commits can have the same parent if they diverge from one version and one commit can have two parents if it merges diverged parents. A branch is just a name that points to a commit. A HEAD points to the current branch which points to the current commit. Beyond the history graph, the full object graph represents each commit (which is a snapshot of the project) as a tree node, avoiding storing redundant copies and only storing what’s changed. Each version of a file is stored once and multiple commits share it. Each commit also has log data associated with it.
The staging area or index acts as a commit in progress. “Git add” updates the staging area and “git commit” finalizes the commit and updates the graph. “Git status” can tell you the status of your commits in different phases. A branch in git history doesn’t necessarily require “git branch” to be run and just means multiple commits have the same parent. Commits can be sent to a remote repository with “git push origin master”. A cloned repository remembers where it was cloned from as origin. New commits can be received with “git pull”, which also checks out the latest version. If a push is attempted while there are changes not in the local copy, the push will be rejected. This will require a “git pull” and “git merge” to merge in the changes which should allow for a push. A new commit will be created to join the diverged histories. If the same parts of the same files were edited there would be a merge conflict and manual changes would be required to fix them. “Git show :” will show the contents of the folder at a point in time while “Git show ” will show the differences from the commit. Adding a file name to the end of the first will display the file’s contents at that point.
Reading 6: Specifications
A specification is a contract that the implementer is responsible for meeting and that clients can rely on. Bugs can occur due to misunderstandings about expected behavior. Specifications can help show which code is incorrect and are easier to read than code. Specifications will generally contain straightforward descriptions with documentation containing more details such as for edge cases. They also let implementers change code without telling clients if following the specifications. Client and implementation code can change separately as long as each follows it’s part of the contract. A specification of a method has a precondition indicated by the keyword “requires” and a post condition indicated by “effects.” The precondition is the client or method caller’s condition specifying how to use it. The postcondition is what the method and implementer should do and can specify exceptions and values to return. If the precondition is true when the method is called then the postcondition must be true when it completes. If the precondition isn’t then it isn’t bound.
Eiffel and other languages use pre and postconditions as expressions the runtime system or compile can check to enforce contracts. In Java, static type declarations are part of these conditions and enforced by the compile, requiring code to guarantee the rest. Javadoc convention specifies that parameters should be specified with @param, return statements with @return and other results with @throws. Parameters should specify the preconditions and the other two should specify the postconditions. Requires and effects in a specification translate to params and returns in a comment in Java. Javadoc comments can be used to generate documentation in html as well.
Null is a special value any non-primitive variable, object and arrays can reference. These can lead to runtime errors as methods cant be used with them. Null isn’t the same as an empty string or array which can have methods like length() called with them. Instead null will lead to a NullPointerException. Collections of objects can also have a null value in them, likely to cause an error if looped over. Null values should usually be disallowed in parameters and return values and this is an implicit precondition and postcondition. A method should state if it allows or could return null values, though null should be avoided in general. Java extensions such as “NonNull” can automatically check for and disallow null. Another general rule is that mutating already existing objects is disallowed in a method unless explicitly specified in the specification.
When writing tests they should specifically test the specification’s promises and not be specific to implementation or assume anything else added by implementation. For instance, if a specification requires that the index of an item in an array is returned and it appears multiple times, the test shouldn’t be specific to which index is returned as long as its a correct one. Even glass box testing’s exercising of different paths shouldn’t be dependent on implementation. A unit test for a method shouldn’t fail if it calls another method that doesn’t meet its specification. An integration test will make sure that methods have compatible specifications even though individual methods should be tested separately with unit tests.
A method’s signature is its name, parameters and return type and a signature can also include exceptions, which indicate specific bug types and help find an error. ArrayIndexOutOfBoundsException and NullPointerExceptions are the most common and a couple of others are ArithmeticException for errors such as dividing by zero and NumberFormatException for trying to parse a string to an int. Returning special values such as “-1” or null is a bad practice as it requires checking a return value to see if a method fails. Calling an exception instead and using a catch block in the caller is a better practice. This requires referencing the exception in the method definition, “LocalDate lookup(String name) throws NonFoundException {…}” and in the code with “throw new NotFoundException();” in some block on a “birthdays” object (as an example). A calling function could use “try { LocalDate birthdate = birthdays.lookup(“Alyssa”); } catch (NotFoundException nfe) { … }”. This checks for expected exceptions without using special values.
Checked exceptions should signal special results and unchecked should signal bugs. If a method could throw a checked exception its declared in its signature and the compiler can help verify this. Messages can be associated with thrown exceptions. Throwable is a class of objects that can be thrown or caught, and it records a stacktrace and a string describing the exception. Throwable named exceptions are subclasses of Throwable. Error is a subclass reserved for runtime errors like StackOverflowError and OutOfMemoryError and AssertionError (weird as its technically a user error). Errors should be unrecoverable from and not caught. RuntimeExceptions and Errors are unchecked and not required to be declared or caught. Other Throwables and Exceptions are checked and required to be declared or caught when they can be thrown. User-defined exceptions should subclass RuntimeException for unchecked or Exception for checked and Error and Throwable themselves are reserved for Java. Since defining and using exceptions can be a lot of extra code and try/catch blocks, you could use an unchecked exception also if the client will usually be expected to write code avoiding the exception as its easy to avoid. For instance, Queue.pop() can throw an unchecked EmptyQueueException since the caller can reasonably avoid this by checking the size. Url.getWebPage should throw a checked IOException since the caller can’t reliably predict the result. Checking for a perfect square should also be checked as the caller likely doesn’t know the answer.
Reading 7: Designing Specifications
This reading compares different specs for similar behaviors and analyzes tradeoffs based on how deterministic, declarative and strong they are. Going back to the example of finding the index of an element in an array, a deterministic specification could require the value to occur only once. Since one input can only lead to one output, the outcome is completely determined. Returning the first or last occurrence in the implementation for a specification that allows duplicates and only requires one is returned would mean that there’s a deterministic implementation of a nondeterministic specification. If randomness or asynchronous processes are involved, a nondeterministic implementation is also a possibility Specifications that aren’t deterministic are referred to as underdetermined and will usually have a fully-deterministic implementation.
Operational specifications give a series of steps a method should perform, such as pseudocode. Declarative specifications just specify outcome properties and are generally preferable as they allow for more flexibility with implementation. A specification S2 is stronger than or equal to S1 if it’s precondition is weaker than or equal to S1 and postcondition is equal to or stronger than S1’s for states satisfying S1’s precondition. This means S2 can satisfy S1 and a S1 could be replaced safely with S2. The “at least once” array implementation could replace “exactly once” since the precondition is weaker and specifying the lowest index is returned could replace any since the postcondition is stronger. A specification is shown as a circle containing all possible implementations as different points. Strengthening the postcondition gives implementers less freedom and weakening the precondition could mean finding bugs on inputs that wouldn’t have been used before. A stronger spec is drawn as an inner circle of a weaker spec on a diagram.
Specifications should be coherent, avoiding nested if statements, cases and boolean flags. Often these can be split into two methods with simpler specifications. Call results should be informative, which is another reason for avoiding special values like null. Specifications should be strong and clear. For instance if throwing an error after mutating, the client may not know what happened before the error. The specification should be weak enough to avoid being too limited based on inputs to be practical (the example shows not to open a specifically named file). Abstract types like List or Set (not ArrayList or HashSet) should be used for more flexibility.
Preconditions are useful for demanding properties that are hard to check for in the method. For instance, checking that the input of binary search is sorted defeats the purpose. Often methods will specify a postcondition for what unchecked exception they’ll throw for inappropriate arguments. Failing fast is a good strategy to avoid letting errors get too far. Exceptions are more useful in public methods while preconditions can be followed better locally.
Each .java file can have a single package specification, “package test;” at the top for specifying a package its resources belong to. The name should be lowercase to avoid clashing with classes or interfaces. These can be used by importing them into another file with “import test.ClassName” if importing a class from test or you could import test.* to get everything. You can also use “import static” to get class members without having to prefix them with the class name, though this can make it harder to read as viewers may not know where value comes from. For style, java files should typically be named as the name of the class or interface defined in the file and classes should be split across files. A package should have its own folder with files in it being its objects. Files should be generated in this format after code is compiled.
Keeping some code private can make it easier to change and having less public methods will make code easier to understand. Private code can help avoid clutter and also bugs. Private specifies that a method can only be accessed in its class and protected specifies it can be accessed within its package or a subclass. Access levels should be thought about for each variable when designing or using classes. Private access should generally be the default. Static methods aren’t associated with a class and methods not specified with “static” are instance methods that must be called on a specific object. Specifications are the same for either, though instance method’s specifications will often refer to instance properties. For instance, referring to “this” array instead of a variable.
Reading 8: Avoiding Debugging
“The best defense against bugs is making them impossible by design.” Static checking catches many bugs at compile time and others are checked and caught dynamically. Immutability helps avoid bugs as well. Final can be used to make a variable immutable, but it only makes the reference immutable when pointing to a changeable object. The next best defense is to localize bugs to a part of a program. If a problem is caught close to its cause, it’s easier to fix. Checking preconditions in code is an example of defensive programming, which helps mitigate the effects of bugs. The command “assert (x >= 0);” can be used to make sure x is positive, throwing an AssertionError otherwise. ‘assert (x >= 0) : “x is “ + x;’ can be used to add an error message. Assertions are off by default and must be enabled by passing -ea to the JVM. It’s best practice to enable them by default and you can test them with
@Test(expected=AssertionError.class)
public void testAssertionsEnabled() {
assert false;
}
The decorator will expect an assertion error and fail otherwise. Java’s assert is different from JUnit’s assertTrue() and assertEquals(). They are used in different contexts, with assert being in implementation code for defensive checks and JUnit asserts in JUnit tests. Argument requirements and return value requirements can be used with asserts to check the inputs and outputs are right. You can also assert false as a default case for a switch if other options aren’t allowed. Assertions should be added as you write code. Since assertions can clutter code, avoid asserting trivially where bugs in code won’t be found. If it’s obvious, leave it out. Assertions should test internal state and not human input or the existence of a file. Assertion failures should indicate bugs and external failures should be handled with exceptions. Java’s assert statement will be used for debugging and turned off for release to avoid degrading performance even if its worth it in testing. Most assertions are cheap and shouldn’t be disabled after release. Assertions shouldn’t have side effects such as “assert list.remove(x)” which changes list. You could set list.remove(x) to a variable and assert the variable if you planned to remove x anyway.
Modularity can help localize bugs to a function or module. Encapsulation builds walls around a module and makes it responsible for its own internal behavior so outside bugs can’t affect it. An example of this is access control and keeping variables private to limit code that could cause bugs. Variable scopes can also be kept small to make it easier to find bugs related to variables. A loop variable should always be declared in the for-loop initializer to limit its scope to the loop. Variables should also only be declared in the innermost curly brace where it is first used (though in other languages the scope is often a whole function regardless). Global variables are a bad idea in general and should just be passed as parameters to functions.
Reading 9: Mutability and Immutability
Immutable objects always represent the same value once created while mutable ones have methods that can change their value. This doesn’t matter much if there’s only one reference but if multiple variables reference the same object then things change. Looping over n elements and adding them to a string with “s = s + n” creates temporary copies taking O(n2) to copy and create new strings. StringBuilder minimizes this using a data structure which creates a string by calling “sb.toString()”, while maintaining the characters in the string in a mutable way. Mutable objects can give better performance and a way of sharing a data structure across a program. Immutable types are safer and easier to understand. Mutability makes it harder to enforce contracts. Passing a mutable data structure to a function could allow the function to directly alter it while not expecting to.
Date should be avoided as classes from java.time are all immutable. When making a method that returns an object, using “return new ClassName();” instead will return a copy in a pattern known as defensive copying. Otherwise, any change made to one reference to the class would be made to others. This does do extra work and could lead to lots of copies, which is where using an immutable type could be better as different parts could safely share the same values in memory. Immutable types never need defensive copying. The problem seen with mutable objects is aliasing, since mutable references just alias the same mutable object in memory. Two variables in different parts of the code can reference and change the same object without realizing what the other part is doing.
Any time a method mutates an object, it should be included in the method’s spec under effects. Additionally, if not stated, the object should not be mutable at all as surprise mutations can lead to bugs. An iterator is a mutable object that returns elements in a collection on at a time, used behind the scenes in a “for (… : …)” loop. “For (String str : lst) { … }” is written by the compiler as
Iterator iter = lst.iterator();
while (iter.hasNext()) {
String str = iter.next();
…
}
Next is a mutator method which updates the iterator itself. A linked reading (https://www.codeguru.com/java/tij/tij0071.shtml) talks about all of the nuances of the final specifier including how private methods are automatically final and specifying final on a class prevents inheritance.
A class in Java has instance variables declared that will be stored on an object instance created and initialized by a constructor. The keyword “this” refers to the object instance though referencing object names without this can still be done.
public class MyIterator {
private final ArrayList<String> list;
private int index;
public MyIterator(ArrayList<String> list) {
this.list = list;
this.index = 0;
}
public boolean hasNext() {
return index < list.size();
}
public String next() {
final String element = list.get(index);
++index;
return element;
}
}
Iterators are useful for having one way of interacting with different collections. You can’t modify an iterator in its own loop. Another drawback to mutable objects is that contracts depend on any third parties with references to mutable objects. Mutable objects may be desirable for performance and convenience, but there’s a greater risk of bugs when using them. They also make it harder to change the code as the client and implementer would be changing the same object potentially. It’s better for inputs and returns to be immutable due to this. Primitive types, BigInteger and BigDecimal are all mutable. While most collections seen so far are mutable, Collections has unmodifiable versions in unmodifiableList, unmodifiableMap, and unmodifiableSet, which cause attempted alterations to get an exception. Collections can be wrapped in these before being passed to stop them from being altered. There’s also a Collections.emptyList. Immutable objects and references should be used as much as possible.
Reading 10: Recursion
Recursion is a technique for implementing a method given a specification. A recursive function has a base case where it can immediately compute results for a given input and a recursive step where it uses recursive calls reducing the inputs closer to the base case. As a product, n! = n x (n-1) x … x 2 x 1, while a recurrence relation would be n! = 1 if n is 0, or (n-1)! x n if n is greater than 0. Written out, the first would loop through numbers less than n and multiple a result variable (starting at 1) by each. A recursive version would be coded with
public static long factorial(int n) {
If (n == 0) {
return 1;
} else {
return n * factorial(n-1);
}
}
A main function calling factorial(3), would call factorial(2) which would call factorial(1) which would call factorial(0) and each would return its value to the previous after receiving a response. Another popular example is Fibonacci numbers which have 2 base cases, 0 and 1.
public static int fibonacci(int n) {
if (n==0 || n==1) {
return 1;
} else {
Return fibonacci(n-1) + fibonacci(n-2);
}
}
A third problem finds all subsequences in a word recursively, returning them in a string, separated by commas.
public static String subsequencesOfRest(String word) {
if (word.isEmpty()) {
return “”;
} else {
char firstLetter = word.charAt(0);
String restOfWord = word.substring(1);
String subsequncesOfRest = subsequences(restOfWord);
String result = “;
for (String subsequence : subsequencesOfRest.split(“,”, -1)) {
result += “,” + subsequence;
result += “,” + firstLetter + subsequence;
}
result = result.substring(1);
return result;
}
}
A base case is the simplest instance of the program that can’t be decomposed and often occurs when a collection is empty or a number is zero. The recursive step decomposes a larger problem into simpler ones recursively and recombines them to get a solution. Make sure the problem gets smaller otherwise it could never end. The subsequence recursion is known as a direct recursive implementation while a stronger solution uses the helper method
private static String subsequencesAfter(String partialSubsequence, String word) {
if (word.isEmpty()) {
return partialSubsequence;
} else {
return subsequencesAfter(partialSubsequence, word.substring(1)) + “,”
+ subsequencesAfter(partialSubsequence + word.charAt(0), word.substring(1));
}
}
to solve the problem by calling “return subsequencesAfter(“”, word);”. This solves the problem the opposite order and uses a variable to hold a temporary state until it reaches the base case at the end of the word, which returns a single result with the recursion backtracking. This should be split so a public subsequences method calls the private method with the right initialization to avoid exposing the inner workings.
Some problems break down into naturally smaller subproblems and recursion is an obvious solution. Data can also be recursive such as filesystems containing folders of files and folders. With base cases being files. Files in Java are represented with java.io.File which is a recursive data type. f.getParentFile() returns f’s parent folder which is a File object. F.listFiles() returns f’s files. This is a natural data type for a recursive function.
public static String fullPathname(File f) {
if (f.getParentFile() == null) {
return f.getName();
} else {
return fullPathname(f.getParentFile()) + “/” + f.getName();
}
}
java.nio.Files and java.nio.Path offer better representations in newer Java versions. Recursion is a special case in reentrancy, where code can be safely re-entered or called again even when a call is already running. Reentrant code has its state in local variables and parameters and doesn’t share aliases to mutable objects across the program or to recursive calls. Mutual recursion where A calls B which calls A can lead to bugs if unintentional. Code should be designed to be reentrant when possible as its safer and more useful for concurrency, mutual recursion and callbacks.
In general, recursion should be used when a problem or data is recursive. Ideally, all variables and data should be final and immutable and not mutate anything. All behaviors should simply be a relationship between parameters and return values without affecting other parts of the program. This is functional programming and is easier to reason about than imperative programs which have loops and variables with mutable objects affected in a loop and require thinking about points in time rather than the cause and effect of a function. Recursion can take more space since a stack takes up memory and is limited in size which can be a constraint. Common mistakes are forgetting a base case or not covering all base cases and forgetting to reduce the problem.
Reading 11: Debugging
Sometimes it can be hard to localize a bug to a module and a systematic debugging strategy is required. First, find a small, repeatable test case to produce the failure. This will be found automatically if regression testing found the bug, but it can be harder if a user found it. This can be based on timing and thread execution with GUIs and multithreaded programs. It’s still best to make the test case small since it will be run a lot while fixing. Afterward, the test case should be added to the regression tests. For instance, for a problem finding the most common word for a failing example given a large set of words, find a small subset with the same error and once you solve that, confirm with the original.
To localize the bug, study the data (input, results, failed assertions and stack traces), hypothesize (where the bug can and can’t be), experiment (test your hypothesis by collecting information without disturbing the program) and repeat, seeing what you could have missed. Stack traces give a lot of information for where and what the bug is. If a function calls smaller methods, a hypothesis could determine which method causes the error and after testing you’ll either be right or know one place it isn’t. Experimenting can be running a different test case, printing or asserting, or setting a breakpoint to step through code and look through its values. Probing is better than trying to guess solutions which can lead to bad code and can avoid fixing the underlying problem. Binary search can be useful for localizing bugs by recursively seeing which half of the code is causing the errors via probes. Hypotheses for where bugs are should be prioritized to trust older code and Java library code more than your new code. Trust lower levels until you have reason not to. If a working version exists, you can try swapping parts from it in. This should only be done if there’s good reason to suspect a component as it can waste a lot of time. Also make sure the code is up to date, delete your binaries and recompile (Project -> Clean in Eclipse). Asking for help or sleeping can also help to debug.
After finding a bug, come up with a fix. Ask if it’s a coding error or a design error, such as an insufficient interface. Design errors may mean seeing if the bug occurs elsewhere or revisiting the design. Look for other places you may have made the same mistake and make sure the fix won’t break other code. Lastly, add the bug to your regression tests and run them to verify the fix and that bugs weren’t reintroduced. Static typing and assertions can stop future edits from reintroducing bugs as well.
Reading 12: Abstract Data Types
Abstract data types help separate the form of a data structure from how it’s used. Clients making assumptions about a type’s internal representation can be a dangerous problem. Abstract data types help with the problems of abstraction (hiding low level details and showing high level data), modularity, encapsulation, information hiding (hiding details about implementation to allow for them to be changed later, and separation of concerns (a feature should be the responsibility of a single module). These all help with the three main goals of the course which are safety from bugs, ease of understanding and readiness for change.
Programming languages used to only contain built-in types and procedures and let users create procedures and abstract types (including user defined ones) were a major advancement. With data abstraction, a type is characterized by the operations that can be performed on it and the user doesn’t need to know about how its values are actually stored. Types can be implemented to be mutable (often via their own methods) or immutable. You can’t extend a primitive data type to make your own extension the way you can objects. An abstract data types operations are classified as follows. Creators create new objects of the type with arguments as long as they aren’t objects of the constructed types. Producers create new objects from old ones of the same type. Concat is an example of a producer as it combines two two strings to make a new one. Observers take objects of the type (and potentially another type) and return objects of a different one (list’s size gives an int). Lastly, mutators change objects. For example, add updates a list. Creators are often implemented as constructors used with “new”, though creators can also be static (new ArrayList() vs Array.asList(). A static creator is often called a factory method. String.valueOf methods are an example of this. Mutators often return void, but sometimes will return a value stating if the change was successful. Component.add() for Java’s GUI toolkit returns an object so add() calls can be chained.
Some examples of abstract data types are int, List and String in Java. An int is Java’s primitive integer, created via numeric literals with operators as producers, comparisons as observers and no mutators. Lists are mutable and an interface with varying constructors as creators (Collections.singletonList for ArrayLIst and LinkedList, Collections.unmodifiableList as a producer, size and ge methods for observers and add, remove, addAll and Collections.sort for mutators. String is java’s string type, immutable with string constructors as creators, concat, substring and toUpperCase as producers, length and charAt for observers, and no mutators. Sometimes operations can double as producers and mutators and “producer” is sometimes reserved for operations which don’t mutate.
Designing an ADT means choosing operations and their behavior. Fewer simple operations that can be combined is better than lots of complex ones. Each should have a purpose and coherent behavior working on all cases (not adding “sum” to a list which might have strings). Basic information should be easy to obtain such as list elements or size. Types can be generic or domain-specific (graph vs street map) but shouldn’t mix features specific to one. All operations should be specified with preconditions and postconditions so the implementation can be changed if necessary. An example is shown of an internal representation of a string as an internal array and methods that use it. Tests can be created for each operation to test the ADT. The only way to test creators, producers and mutators is to call observers on the objects they give. Each test case will test parts of several operations generally.
Reading 13: Abstraction Functions and Rep Invariants
Abstraction functions and rep invariants are practical mathematical notions that help define what it means for a class to use an ADT. A good ADT should preserve its own invariants or properties of a program that are always true. Immutability is one invariant where immutable objects shouldn’t be able to change. An ADT should be responsible for guaranteeing its own invariants hold regardless of client behavior. If you can trust this, it rules out a lot of test cases and places to look to debug when an error occurs. One step for making an ADT immutable is to make its fields private via “private final String name” and avoid representation exposure and independence. This means only class methods can access those fields directly and not the client. Having methods which return mutable objects also creates this problem as a modification on that object will apply to the ADT’s state. Defensive copying can fix this by returning a copy or “new” version of a class. “clone() is present on many types but has some problems and others have native copy constructors. Using immutable built in versions such as java.time.ZonedDateTime can help avoid having to worry about returning a copy. Wrappers are another method for making types immutable though attempts to modify them won’t be caught at compile time and will lead to a runtime exception.
Representation values consist of values of the implementation entities and can sometimes be complicated (though in the course it’s viewed as a mathematical value). Conversely, abstract values are values the type supports and how its viewed in the eyes of the client. An implementers job is to achieve the illusion of abstract values using representative values. An example of this is a representative string value showing an abstract set of characters. An abstraction function (AF) maps rep values to abstract values they represent. The function is surjective (onto) and not necessarily injective (one to one) or bijective and is often partial. A rep invariant (RI) maps rep values to boolean where RI(r) is true if r is mapped by AF. RI is the subset of rep values AF is defined for. Both should be documented in the code next to the representation documentation. You can catch bugs early by asserting the rep invariant at runtime and anytime the representation is changed and even observer methods for good measure. Checking that values aren’t null (when they aren’t asserted to be something else) is a good rep check to have. Documenting AF and RI are good practices.
Since an invariant holds true for an entire program or lifetime of an object, it needs to be true at the initial state and after any possible change. In other words, creators and producers must establish the invariant for new instances and mutators and observers must preserve it. For structural induction, these must hold as well as no representation exposure occurring. These help enforce and encapsulate properties that would need to be specified as a precondition and are safer and easier to enforce.
Reading 14: Interfaces
Separating the interface of an ADT from its implementation is important and enforceable with Java’s interface types. An interface is a list of method signatures without bodies. A class implements an interface and provides bodies for all methods. The interface is all a client needs to read to understand the ADT and doesn’t contain instance variables. Different classes can implement a single interface. Static type checking lets the compiler catch violations of the interface contract such as giving the wrong return type or forgetting to write a required method. Specify an interface with “public interface Name” and the class that implements it with “public class ClassName implements Name.” The interface will be delcations like “int methodName(VarType varName);” and the implementation will write the whole function to return the int. The implementing class is a subtype and the interface is its supertype. The spec of a subtype should be at least as strong as its supertype and that it isn’t weakened by strengthening a precondition or weakening a postcondition or guarantee the interface avertises. @Override can be placed in front of a field or method declaration to show it overrides its superclass’s implementation and alerts readers to a superclass present.
Since interfaces can’t have constructors, clients would have to call “InterfaceName y = new ClassName(x);” which creates a problem clients would need to know the name for the representation class and implementations may not contain the same constructors. Interfaces can have static methods so the creator operation “valueOf” can be implemented as a static factory in an interface to “return new ClassName(x);”, allowing a client to use the ADT without breaking the abstraction barrier. Set is an ADT of finite sets of elements of another type E. Set is a generic type which will be filled in, “public interface Set {“ and a static factory method is “public static Set make() {…}”. Called with Set strings = Set.make()”, a set of string objects would be created. Size and contains methods would be added as observer methods and add and remove for mutators, all to be implemented at the ADT level. “Public class CharSet1 implements Set {“ can be used to use Character in place of E for an implementation, though it can also be left as E to let the client pass any type.
Collection is an interface in Java that subinterfaces Set and List. Two Sets are equal if they have the same elements and three examples are HashSet (best but no ordering guarantee), TreeSet (orders based on values in tree) and LinkedHashSet (hash table and linked list in insertion order).There’s a lot more detail on the exact implementation and the main methods of each in Java’s documentation. Interfaces are generally good to use as they’re documentation for compiler and humans and allow for different implementations based on desired performance. They allow for optional methods. With optional methods, immutable lists can be created by not implementing mutation methods.
Reading 15: Equality
This reading talks about defining the notion of equalities for an ADT via the abstraction function. There are a few ways to regard equality. Using an abstraction function, f, a=b if and only if f(a)=f(b). Using a relation, an equivalence is a relation “E is a subset of T*T that is reflexive (E(t,t) for all t in T), symmetric (E(t,u) -> E(u,t)), and transitive (E(t,u) conjunction E(u,v) -> E(t,v). This way, a equals b if and only if E(a,b). These two notions are equivalent. The third way is talking equivalence based on what the client can see. Using observation, two objects are equal if every operation produces the same results for two objects. This is useful for abstract data types.
Java has two equality operators. “==” checks that two references point to the same place in memory and “equals()” compares objects’ contents and needs to be defined appropriately for ADTs. Python uses “is” for referential equality and “==” for object equality. I didn’t know that. In any language, referential equality can’t be changed and for a new Java type, equals needs to be implemented with “public boolean equals(Object that)”, which defaults to “return this == that” and should be overridden. A bizarre example of a failing implementation for an example class Duration is “return this.getLength() == that.getLength();”. Setting d1 to a new Duration(1,2) and d2 to new Duration (1,2), d1 will equal d2. However, if Object o2 is set to equal d2, d1 won’t equal o2. D2 and o2 reference the same object in memory but get different results in equals since Duration overloads the equals method. Duration will have the default equals(Object) inherited from Object and a new equals(Duration). Depending on the type passed to d1’s equals, a different method is called. Overloading instead of overriding is a common mistake and “@Override” should be specified to override a superclass’s method. With this, Java’s compiler will check for the method with the same signature in the superclass and give an error if not found. The following code will fix the issue.
@Override
public boolean equals (Object thatObject) {
if (!(thatObject instanceof Duration)) return false;
Duration thatDuration = (Duration) thatObject;
return this.getLength() == thatDuration.getLength();
}
The instanceof operator checks if an object is of a specific type and is a dynamic type checking method. Since static is preferred, the course disallows it (and other runtime type checks) except in equals methods. The specification of the Object class is referred to as the Object Contract. The overriding equals method must adhere to Object’s equals contract by defining an equivalence relation, that’s consistent, and hashCode must produce the same result for two objects deemed equal. A non-null x can’t equal null, as well (for some reason this is specified).
A hash table contains an array initialized to a size based on its expected elements. When a key and value are inserted, a hashcode of the key is computed and mapped to an index in the array (ex. with modulo) and the value is inserted there in a list or hash bucket. In java, an object with two fields (key and value) is added to the list. When looking up you get the hash of the key and check each pair in the list to find the right key and check its value. If two object’s hash codes aren’t equal the lookup could fail if one is substituted for the other. By default, hashCode will return the memory address of an object, but this won’t work for immutable objects, so Duration would currently break the Object contract. Returning the same value would be an easy solution but would map every key to the same slot creating a linear time search for a hash table. A better strategy is to compute the hash code of each component of the object used to determine equality and combine them. Objects.hash() can help with this. Effective Java is a book plugged a lot, I should check it out. Different hashing techniques will give different performances, but any correct one is better than one breaking the contract. In general, override hashCode when you override equals.
Mutable objects are equal when they can’t be distinguished by observation that doesn’t change their state (observational equality) or can’t be distinguished by any observation even state changes (behavioral equality). Since there are mutator methods, these are important to distinguish. In immutable objects, they’re the same. Java typically uses observational equality (two lists that have the same elements are the same). Using mutable objects for set elements can create a problem and results aren’t guaranteed if an object changes while in a set. Collections use observational equality but other mutable classes like StringBuilder use behavioral. From an example of messing up with set, behavioral is a better strategy as references should be equal only if they’re aliases for the same object. A new method (“similar”) should be used to compare current state. Immutable types should compare abstract values with equals and map abstract values to integers with hashCode, and override both. Mutable types should compare references directly and map to integers with hashCode, overriding neither. Both provide behavioral equality with these specifications as Object’s default implementation works for mutable types. “==” is referential equality even for reference types like Integer so two new Integer(3)’s won’t be equal that symbol, the way primitive ints would be and the automatic conversion (autoboxing/auto-unboxing) can lead to subtle bugs.
Reading 16: Recursive Data Types
This reading looks at recursively-defined types and how to specify and implement operations on them, looking at immutable lists and matrix multiplications. A recursive data type is defined in terms of itself requiring base and recursive cases as different variants of the abstract type. An immutable list is a classic recursive datatype. Immutability adds sharing potential which can allow for less memory consumption and copying time. An example immutable list, ImList<E> has four main operations. Empty returns an empty list (void -> ImList), cons returns a new list by adding an element to the front of another list (E, ImList -> ImList), first returns the first element (ImList -> E) and the list must be nonempty, and rest returns all elements except the first (ImList -> ImList) requiring a nonempty list. These four operations are fundamental for list-processing languages Lisp and Scheme and used widely in functional programming (head and tail instead of first and rest). What cons puts together, first and rest take apart.
Representing this, an ImList<E> interface is specified
public interface ImList<e> {
public static <E> ImList<E> empty() { return new Empty<>(); }
public ImList<E> cons(E e);
public E first();
public ImList<E> rest();
}
and Empty and Cons are classes that implement the interface. Empty<E> has a public Empty() {} and “ImList<E> cons(E e) { return new Cons<>(e, this); }.” First and rest throw UnsupportedOperationExceptions. Cons<E> has “private final E e” and “private final ImList<E> rest”, a Cons method which sets them and a first and rest methods which return them. With this, substructures are shared and two implementations of an interface are used to implement a datatype with both needed. ImList is a recursive data type. Cons is an ImList that uses ImList in its own representation for rest. A datatype definition is ImList<E>=Empty + Cons(first:E, rest:ImList)m meaning ImList consists of values formed by the Empty or Cons constructors. Datatype definitions have an abstract datatype on the left with its representation or concrete datatype on the right. Variants are separated with “+” and each variant is a constructor possibly with arguments. For a binary tree, Tree<E> = Empty + Node(e:E, left:Tree<E>, right:Tree<E>). This shows base and recursive cases and functions can be designed for each. For instance, a size method of ImList could return “size(empty)=zero” or “size(Cons(first: E, rest: ImList)) = 1 + size(rest)”, recursively giving the size.
The pattern of declaring the operation in an interface and implementing it for each concrete variant recursively is a common pattern known as the interpreter pattern (for some reason). Other examples of methods that could be implemented are isEmpty returning true on Empty or false for Cons, contains returning false for Empty or checking Cons first elements recursively. Append sets an empty list to an added list, or eventually gets to an empty list that it sets to the added list. Reverse recursively appends reverse(rest) and cons(first, empty()). Recursive reverse has quadratic performance and iterative is better. Saving a size variable can lead to constant time if called often and is an example of a beneficient mutation which is a state change that doesn’t change the value represented by the object, so its still immutable. Package private variables can be declared without public or private keywords so outside classes outside ImList’s package can’t see them.
Using an object instead of null for the basecase or end is an example of a design pattern called sentinel objects where an object acts like an object in the data type and methods can be called on it. Size can be called on an empty list, but not on null which would require manual checks. Keep null out of data structures. Java’s type checking has two cases, at compile time there’s a declared type which the compiler evaluates a program based on and at run time theres an actual type given by its constructor.
A recursive data type definition for representing propositional logic formulas is in the form
Formula = Variable(name:String) + Not(formula:Formula) + And(left:Formula, right:Formula) + Or(left:Formula, right:Formula).
(P OR Q) AND (NOT P OR R) would be “And( Or(Variable(“P”), Variable(“Q”)), Or(Not(Variable(“P”)), Variable(“R”)) ). A key operation for boolean formulas is testing if they can evaluate to true with a combination of true and false values. A slow algorithm for testing this is to extract the set of variables, try all true/false values for each (an assignment is an Environment, with a list of variables and values) and evaluate the formula for each environment, returning the first to give true.
If two lists are identical at the beginning but diverge, they should be stored separately. Backtracking search is a good application for immutable lists since a search makes one choice after another backtracking when a dead end is found. Mutable data structures make this hard since you have to undo variable changes of backtracking. With immutable maps you can throw the map away. Without sharing, the space will grow quadratically. With immutable lists, each step taken can share all information from previous steps by adding to the front. Backtracking gets rid of the current steps state while maintaining references to the previous step’s state. Immutable data structures are immediately ready for parallelized algorithms and will be useful for concurrency.
The next case looks at using test first programming to solve matrix multiplication. In its simplest form, write the specifications, then tests, and then implement a solution. Go back and improve the spec and tests with things you missed or improvements. For an ADT, specs should be written for datatype operations, method signatures and preconditions and postconditions. Then write test cases for each and improve the spec as needed. Implement the ADT by choosing a representation, writing down fields and variants (for recursive), writing the rep invariant as a comment. Assert the rep invariant with a checkRep method and call it in the operation methods. Once all tests pass, then the process is done. A broader recipe for writing a program with ADTs and procedures is to first choose datatypes, then procedures, then specs and tests. After that, implement simply and improve after a basic version is working.
Matrix multiplication is a problem where you want to multiply with a matrix quickly. Lowercase letters are scalars and uppercase are matrices. Multiplying (aX)b requires looping over matrix X twice once for a and once for b. Rearranging problems can help speed them up as (ab)X would be cheaper. A MatrixExpression data type, MatExpr would have a “make” function which takes a scalar (double) or matrix (double[][]) and returns an expression consisting of it. It would have a “times” function that multiplies two expressions if compatible, “isIdentity” would return true or false based on if an expression is the multiplicative identity. Lastly, “optimize” would return an expression with the same value that’s faster to compute.
Writing tests for optimize(), partitions would be the number of scalars in an expression and the positions in an expression tree. For the 0 scalar partition, X would be optimized as X. 1 scalar on the immediate left would be aX to aX. 2 scalars (immediate left and right-of-right) would be a(Xb) to (ab)X, 2 scalars (immediate right, left-of-left) would be (aX)b to (ab)X and 2 scalars (left-of-right, right-of-left) would be (Xa)(bY) to (((ab)X)Y).
The recursive data type definition would be MatExpr = Identity + Scalar(double) + Matrix(double[][]) + Product(MatExpr, MatExpr). A MatrixExpression interface is definite and Identity, Scalar, Matrix and Product are all classes that implement it. Scalar sets this.value to a passed double value, Matrix does the same for an array, and product sets two MatrixExpressions. The identity matrix (an empty product expression) is used as the value not representing anything. Two public “make” methods are added one taking a double and the other a double[][], returning a new Scalar or Matrix with the argument respectively. These factory methods are static methods that are used as constructors.
For isIdentity, rather than using instanceOf, each class is given its own implementation. Identity returns true, Scalar returns whether the value is 1, Matrix checks for ones on the diagonal and zeros elsewhere and product returns the AND of calling isIdentity on it’s two parameters (which can cause an error for the identity matrix). The spec of isIdentity can be weakened to help with this. Similarly, optimize should be defined on each class and not use instanceof checks. Scalars() return a MatExpr with only scalars and matrices() returns a MatExpr with only matrices in input order. These can be added to the interface and implemented on each class. Identity will “return this” for both, Scalar and Matrix return this for their respective type, I for the other’s. Product returns “times(m1.scalars(), m2.scalars())” for scalars and “times(m1.matrices(), m2.matrices())” for matrices. Optimize will either “return this” if the class isn’t Product, or “return times(scalars(), matrices());” if product, separating scalars and matrices.
Reading 17: Regular Expressions and Grammars
Some programs take input or produce output as a sequence of bytes or characters, called a string when stored in memory or a stream when it flows into or out of a module. This reading talks about writing a specification for these sequences. A sequence of bytes or characters could represent files, where the specification is a file format, messages over a network, where the specification is a wire protocol, a typed command (the specification is a CLI), or a string in memory. A grammar helps to distinguish between legal and illegal sentences or parse a sequence into a (often recursive) data structure a program can use. A regular expression is a specialized form of a grammar, widely used for string processing tasks. A grammar defines sets of sentences (sequences of symbols). For URLs, sentences are legal URLs for HTTP. Symbols in a sentence are terminals or tokens, since they’re the leaves of a tree representing the sentence. They are often written in quotes. A grammar is described as a set of productions defining nonterminals, which are the internal nodes of the tree. A production has the form nonterminal ::= expression of terminals, nonterminals and operators. Non terminals will be lowercase identifiers in this course. One nonterminal is the root or start.
The three most important operators for a production expression are concatenation, repetition and union (or alternation). For concatenation, x ::= y z (x is y followed by z), repetition is x ::= y* (x is zero or more y) and union is x ::= y | z (x is y or z). Combinations of these three can be used for option, which is x ::= y? (x is y or empty), 1+ repetition is x ::= y+ (x is at least 1 y) and character classes is done by x ::= [abc] which is the same as a union of the 3. X ::= [^b] is the same as a union of all other characters. “*”, “?”, and “+” have the highest precedence and “|” has the lowest. Precedence can be overridden with parenthesis, for instance, x ::= (y z | a b)* means x is zero or more y-z or a-b pairs.
To represent urls, a single url might be “url ::= ‘http://mit.edu/’”, but to allow other domains, a better representation would be “url ::= ‘http://’ + [a-z]+ ‘.’ [a-z]+ ‘/’”. This represents any two part hostname with only letters. Breaking this down, if a word is [a-z]+ and hostname is “word ‘.’ word”, then url is “‘http://’ hostname ‘/’”. Represented as a tree, url would be the root with children from left and right being “http://”, hostname, and ‘/’. Then the hostname would be given children word, “.”, and word and each word node would have a child of its value (ex. ‘Mit’ and ‘edu’). Non terminals are the rules while terminals are the exact values. Concatenating the leaves would give the actual URL string. To add an optional port number and additional hostname components, “url ::= ‘http://’ hostname (‘:’ port)? ‘/’” and “hostname ::= word ‘.’ hostname | word ‘.’ word”. Port is [0-9]+ and word is [a-z]+. With the repetition operator, “hostname ::= (word ‘.’)+ word”. This isn’t perfect yet as ports range from 0 to 65535 and additional protocols or paths could be specified, along with allowing for non-letter characters in domains.
In Markdown, “This is _italic_.” while in HTML, “Here is an italic word.” As grammar (only considering italics) for Markdown, “markdown ::= ( normal | italic ) *” where “italic ::= ‘_’ normal ‘_’”, “normal ::= text”, and “text ::= [^_]*”. For HTML, “html ::= ( normal | italic ) *”, “italic ::= ‘ html ‘’”, ‘normal ::= text’, and ‘text ::= [^<>]*’. A regular grammar has the property where by substituting every nonterminal except the root with its right hand side it can be reduced to a single production for the root with terminals and operators on the right. For instance, the URL grammar can be reduced to “url ::= ‘http://’ ([a-z]+ ‘.’)+ [a-z]+ (‘:’ [0-9]+)? ‘/’” and Markdown as “markdown ::= ([^_]* | ‘_’ [^_]* ‘_’ )*”. Html can only reduce to a recursive expression and isn’t regular.
The reduced expressions can be written more compactly as a regular expression which removes quotes and spaces consisting of terminals, parenthesis and operators. For instance, Markdown would become “([^]*|_[^_]*_)*”. Regular expressions or regexes are less readable but fast to implement and supported by many libraries and languages. Some other useful characters are “.” representing any single character, “\d” for any digit, “\s” for any whitespace character, “\w” for any word character including letters and digits. “\” can also be put in front of operators or special characters to escape them. URL would become “http://([a-z]+\.)+[a-z]+(:[0-9]+)/”.
In Java, regexes can be used to manipulate strings such as with String.split, String.matches, or java.util.regex.Pattern and are used as a “first-class feature” in Python, Ruby and Javascript along with text editors for find and replace. Some examples of this are replacing any number of spaces with a single space ‘String singleSpaced = string.replaceAll(“ +”, “ “);’, matching a URL with
Pattern regex = Pattern.compile(“http://([a-z]+\\.)+[a-z]+(:[0-9]+)?/”);
Matcher m = regex.matcher(string);
if (m.matches()) { ... }
or extracting part of a tag using Matcher.group. The double backslash before the period is needed in the above example to both have a literal period and to stop Java from treating it as a string escape character. Quote characters must be escaped to avoid ending the string. Languages expressible with the shown grammar system are context-free (though not always regular). Grammars for most programming languages are context-free and languages with nested structures typically are context-free and not regular. This applies to Java as well. Grammars are useful for describing text languages and regular expressions are an important subclass of grammars expressible without recursion.
Reading 18: Parser Generators
Parser generators take grammar as an input and generator source code for parsing streams of characters with that grammar. The generated code is a parser which takes a sequence of characters and tries to match it against a grammar, producing a parse tree showing how productions are expanded into a sentence matching the character sequence. The root is the starting nonterminal and each node expands into a production. Lastly, the tree should be used for something, here it is translated into a value of a recursive ADT, which are commonly used to to represent expressions in a language such as HTML, Markdown, or Java. A recursive ADT representing a language expression is an abstract syntax tree (AST).
Antlr is a widely used parser generator in Java and other languages. In an Antlr source file, the HTML grammar would be
‘’’ grammar Html; root : html EOF; html : ( italic | normal ) *; italic : ‘’ html ‘’; normal : TEXT; TEXT : ~[<>]+; /* representing a string of one for more characters that aren’t < or > ‘’’
Each rule consists of a name and definition separated by a colon and terminated by a semicolon. Nonterminals are lowercase and terminals are either capitalized or in quotes. “root“ is the entry point and the nonterminal the input needs to match, though it doesn’t have to be named root. EOF is a special terminal signifying End Of File or the end of the input. As seen in html, the alternation and other operators can be used in the same way as the previous reading and “?” can be used to show optional parts as well. “~” is “not” in Antlr and TEXT would be written “[^<>]” in regex. Antlr terminals can also be defined with regex such as “ID : [a-z]+;”.
Antlr code is stored in “.g4” files. The Antlr parser generator tool will convert a grammar source file into Java classes to implement a parser, such as “java -jar ../../../lib/antlr.jar IntegerExpression.g4”. Java source files would be generated in the current folder, divided into lexer, parser and tree walkers. Lexers take a stream of characters and produce a stream of tokens/terminals such as “NUMBER, “+” and “(“. For IntegerExpression.g4, the lexer would be IntegerExpressionLexer.java. A parser takes the stream of terminals from the lexer and creates a parse tree. The parser is in IntegerExpressionParser.java. Lastly, the tree walker lets you write code to walk over the parse tree and files include an interface IntegerExpressionListener.java and an empty implementation IntegerExpressionBaseListener.java. IntegerExpression.tokens and IntegerExpressionLexer.tokens are also generated, listing found terminals and are needed for nested grammars. Never edit Antlr’s generated files. Edit the source g4 file and regenerate them using “java -jar …”. Refresh the project each time to see the changes in Eclipse.
To use the parser, make a stream of characters for the lexer with ANTLRInputStream, which takes a String, Reader or InputStream. For instance, using a string, “CharStream stream = new ANTLRInputStream(“54+(2+89)”);” can be used to create a lexer class instance with “IntegerExpressionLexer lexer = new IntegerExpressionLexer(stream);” and “TokenStream tokens = new CommonTokenStream(lexer);”. This gives a stream of terminals that can be fed to the parser, “IntegerExpressionParser parser = new IntegerExpressionParser(tokens);”. To actually parse, call a nonterminal on the generated parser which has a method for each non terminal including root(), sum() and primitive(). Root represents the set of strings that should be matched, so “ParseTree tree = parser.root();” which can be debugged with “System.err.println(tree.toStringTree(parser));” or “Trees.inspect(tree, parser);” which will show a nice diagram.
Translating the parse tree into a value of a recursive ADT, a ParseTreeWalker can be used to traverse it, visiting nodes top to bottom, left to right. At each node, the walker calls methods on a provided listener implementing the IntegerExpressionListener interface in this example. This listener interface has enter and exit methods for root, sum, and primitive along with visitTerminal which just prints what its doing at the time. Unimplemented methods set to be overridden are enterEveryRule, exitEveryRule and visitErrorNode which work on each node or if a syntax error produces a bad node. Each parameter provides information and the opportunity for an action on a visited node. To use a listener and walker,
ParseTreeWalker = new ParseTreeWalker(); IntegerExpressionListener listener = new PrintEverything(); walker.walk(listener, tree);
This would enter root, sum, primitive, 54, and so on, following the tree. To convert the parse tree to a recursive data type, a definition could be “IntegerExpression = Number(n:int) + Plus(left:Integer Expression, right:IntegerExpression)”. The IntegerExpression values capture important features with groupings and integers omitting unnecessary details about the input. The parse tree created before is a concrete syntax tree as it has details about how the expression is represented in characters. For instance, ((2))+((2)) and 2+2 would have different concrete syntax tree corresponding to the same abstract IntegerExpression of Plus(Number(2), Number(2)). This is one reason for why an abstract syntax tree is good.
Implementing a MakeIntegerExpression class, sum nodes create Plus objects and primitive nodes matching the NUMBER terminal create Number objects. After the walker exits a node, it’s walked that entire subtle and a new IntegerExpression is created at the exit. A stack keeps track of all children created during the walk. getExpression() returns stack.get(0), exitSum and exitPrimitve are defined with
@Override public void exitSum(IntegerExpressionParser.SumContext context) {
List<IntegerExpressionParser.PrimitiveContext> addends = context.primitive();
assert stack.size() >= addends.size();
assert addends.size() > 0;
IntegerExpression sum = stack.pop();
for (int i = 1; i < addends.size(); ++i) {
sum = new Plus(stack.pop(), sum);
}
stack.push(sum);
}
@Override public void exitPrimitive(IntegerExpressionParser.PrimitiveContext context) {
if (context.NUMBER() != null) {
int n = Integer.valueOf(context.NUMBER().getText());
IntegerExpression number = new Number(n);
stack.push(number);
} else { // do nothing }
}
and other methods are left blank. Errors are printed to the console by default but ErrorListeners can be attached to lexers and parsers to throw exceptions. Configuration.g4 contains a reportErrorsAsExceptions() method which can be copied to the grammar file so lexer or parser can be given the same methods. An exception will then be thrown when something can’t be matched.
Reading 19: Concurrency
Concurrency means that multiple computations happen at the same time and occurs everywhere in modern programming. Multiple computers run in a network, multiple applications run on a computer and multiple processors are in a computer often with multiple cores on a chip. Concurrency is essential in modern programming as web sites need to be able to handle multiple users, mobile apps reach out from multiple phones to servers and GUI’s have background work that can’t interrupt the user (such as Eclipse compiling code while you edit it). As the new trend is adding more cores and parallelization instead of clock speed increasing, this will require handling more concurrent processes for increased speed.
Two common models for concurrent processing are shared memory and message passing. For shared memory, concurrent modules interact by reading and writing shared objects in memory. These could be two processors using the same physical memory, two programs sharing a file system or two threads in a Java program sharing objects. For message passing, concurrent modules send messages to each other through a communication channel. Modules send messages and incoming messages to a module are queued for handling. This could be two computers communicating over a network, a web browser requesting something from its server, an IM client and server or two programs where the input to one is the output of another.
These methods are how concurrent modules communicate. Concurrent modules themselves either processes or threads. A process is an instance of a running program isolated from other processes on its machine. It has its own private section of the machine’s memory. The process abstraction is a virtual computer making the program seem to have its own machine to run in. Processes generally share no memory, instead using a new process for message passing created with standard input and output streams such as System.out and System.in. A thread is a “locus of control” in a running program and is the place the program being run plus the stack of method calls leading there. The thread can go back up the stack when a return is reached. The thread abstraction represents a virtual processor in the process’s virtual computer. Threads run the same program and share memory with other threads in a process. In this case, it’s hard to get “thread-local” memory.
If there are more threads than processors, concurrency can be simulated by time slicing where the processor switches between threads. Time slicing usually happens unpredictably and nondeterministically and a thread can be paused or resumed any time. Time slicing helps share processing time for a small number of cores and is a feature of the operating system. Most operating systems support Inter Process Communication or IPC resources (pipes, sockets, etc) to communicate between processes on one or more systems. Many JVM implementations use a single process though an application can create additional processes with a ProcessBuilder object. From the app’s point of view each program starts with a main thread and can create more. You can create a thread by using a Runnable object and passing it to a Thread constructor and calling start on the thread. You can also extend Thread with a new class and call start on a new class after defining a run method for it. Always use the first method, for example
Public class HelloRunnable implements Runnable {
public void run() {
System.out.println(“Hello from thread”);
}
public static void main() {
new Thread(new HelloRunnable())).start();
}
}
You can also start a Thread with a “new Runnable” directly avoiding the need for a named class and can be useful if you only plan to use the class in one place. An anonymous class declares an unnamed class that implements an interface and immediately creates a single instance. This also means only having to look in one place to understand the object, though can be distracting if particularly long. Overall, these are good for short one-of implementations of a method. Runnable is a good use case for this since you use them to start a thread.
Public static void main(String[] args) {
new Thread(new Runnable() {
public void run() {
System.out.println(“Hello from thread”);
}
}).start();
}
As a lambda, this could be written
public static void main(String[] args) {
new Thread(() -> System.out.println(“Hello from thread”)).start();
}
Though this could be more confusing for why it works, starting out. An example of where concurrency can be tricker is a bank which supports deposits and withdrawals. Even if the only operation that can be run is depositing a dollar followed by taking it out and the bank starts with zero, oftentimes the balance at the end of the day isn’t zero. This is due to interleaving. For instance, if two machines are depositing at once, for the first instance it sees a balance of 0, deposits and sees a balance of 1. The second sees 1, adds one and sees 2. This means both dollars were put deposited successfully, but if staggered, both could see a balance of zero, add 1 and write the balance back as 1, causing a dollar to disappear since they wouldn’t be aware of the other deposit while writing a new balance. This is a race condition, where correctness depends on timing of events. Process A is in a race with process B. Unfortunately you can’t tell by looking at an expression if it’s safe from race conditions.
Compilers provide no guarantee for what they’ll actually run from the source code and sometimes can make temporary copies for caches on a processor, taking time to store them back to their original location and changing the order of variables being manipulated. Lines won’t necessarily be run in order and a variable defined on a first line can be set after the following. Message passing can also still lead to race conditions. Two processes could both think they could withdraw a dollar from an account with only one left. It can be very hard to debug and localize race conditions when found. Concurrency bugs are hard to reproduce as other factors such as other programs, network traffic and processor speeds can lead to varying behaviors across each run. These are known as heisenbugs which are nondeterministic and hard to reproduce compared to a bohrbug, which show up repeatedly. Bugs in sequential programming are usually bohrbugs. Since printing and debugging commands can be slower, the heisenbug may disappear when trying to view it, which may only mask the bug. The next readings show ways to make concurrent programs safer from bugs.
Reading 20: Thread Safety
Race conditions occur due to multiple threads sharing a single mutable variable without coordinating and can randomly impact the correctness of the program. Four ways to make variable access safe in shared-memory concurrency are confinement, immutability, using a thread safe data type and synchronization. Confinement avoids sharing variables between threads, immutability makes the data immutable, a threadsafe data type encapsulates the shared data in a way that does coordination for you and synchronization is used to stop threads from accessing a variable at the same time.
Threadsafe means a data type or method behaves correctly when used from multiple threads regardless of execution or additional coordination demands. Iterator is not threadsafe as it’s specification says you can’t modify a collection while iterating over which a timing-based precondition and additional coordination demand. Confinement solves the problem by not sharing the mutable data across threads. Local variables are always thread confined and stored in the stack (each thread has its own stack). Each invocation of a recursive method has a private copy of a variable, confining it. The problem is that if the variable is an object reference the object it points to must be confined as well and not referenced by any other thread. For instance, two threads will have their own “i” and “n” int variables in a for loop called directly and with a runnable, so they won’t interfere. This only works since none of the objects are mutable. This is another reason to avoid global variables.
Another example is a problem is a class with a getInstance method that creates a new instance only if a field set on it referencing an instance is null. If two threads call it at once, that could create an unplanned behavior. Static variables are risky for concurrency. Memoization can also be a problem as multiple calls to the same cache by different threads could lead to Exceptions or wrong answers.
Immutability handles the issue of shared mutable data by having the shared data not be mutable. Immutable values are usually threadsafe with exceptions being when a type can mutate its rep. Since caching is a beneficial mutation, concurrency can cause problems and the data type will have to use locks. So, a stronger definition of immutability would be no mutator methods, all fields are private and final, no representation exposure and no mutation of mutable objects in the rep even when beneficent. With these, an immutable data type will be threadsafe.
The third strategy is using threadsafe data types to store mutable data. A data type from the Java library will specify if it is in its documentation. It’s common for Java to have two mutable data types, one threadsafe and one not. For instance, StringBuffer is safe but StringBuilder isn’t. Threadsafe types usually have a performance penalty so they aren’t always better. Java’s collection interfaces have basic, not threadsafe implementations (such as ArrayList, HashMap, and HashSet). Similar to the immutable wrapper, there’s a wrapper to make collections threadsafe while still mutable. These make each method atomic with respect to the others, where an atomic action happens all at once and doesn’t interleave internal operations. The result of atomic action never looks partially done. “private static Map cache = Collections.synchonizedMap(new HashMap<>())” wraps a HashMap to make it threadsafe. It’s important to only reference the synchronized wrapper, which defining cache this way takes car of automatically. Iterators still aren’t threadsafe, so loops and iteration() calls should be avoided. A lock will be the solution for the iterator problem. Races can still occur with atomic operations. Even if each method is atomic, they can interleave with each other potentially. Because of this, races between different methods will have to be safe for the invariant. Java also provides a java.util.concurrent package with data types optimized for concurrency.
The best way to show a concurrent program is correct is to show its free from races, catalog all threads and their data and which techniques are used to protect against races for each object or variable. All accesses to data need to be appropriately atomic and invariants are not threatened by interleaving. A thread safety argument can be written in the comment for a method or class. Serializability is a property where for any set of operations executed concurrently, the result (values and observable state) must be a result given by some sequential ordering.
Reading 21: Sockets and Networking
This reading looks at client/server communication over a network using socket abstraction. Network communication is concurrent and building clients and servers will require thinking about their behavior and to use thread safety. A wire protocol is required for communication between the two. Sockets have blocking operations which block thread process until a result is ready but can lead to deadlocks. The client/server design pattern designed for communication has clients and servers. Clients initiate communication to servers, sending requests and getting replies back. Then the client disconnects. Clients can connect to multiple servers and vice versa. Web browsers are clients for web servers and email programs are clients for mail servers. Over the internet, clients and servers run on different machines, but in general they can run on the same machine.
A network interface is identified by an IP address. IPv4 addresses are 32-bit numbers written in four 8-bit parts. 18.9.22.69 is an example given of an MIT web server where every address starting with 18 was an MIT web server (seems this may no longer be true). 127.0.0.1 is a special loopback or localhost address which always refers to the local machine. Any address whose first octet is 127 is a loopback address technically, though this is the standard. Every time you connect a machine to a network, it can be assigned a new IP address.
Hostnames are names that can be translated to IP addresses. One hostname can map to different IP addresses at different times and multiple host names can map to the same IP address. For instance, web.mit.edu maps to 18.9.22.69 (maybe outdated) and dig, host, or nslookup command line tools can be used to find an IP address. Localhost is a hostname for 127.0.0.1. Domain Name Systems (DNS) translate from hostnames to IP addresses.
Ports are used to direct traffic on one network interface to different processes. Network interfaces have ports identified by 16-bit numbers from 0 to 65535, though 0 is reserved. A server process binds to and listens on a specific port that client needs to know. Some ports are reserved for system-level processes providing standard ports for those services. Port 22 is the standard port for SSH, port 25 is the same for an email server and 80 for a web server. Ports that aren’t standard need to be specified in the address such as “http://128.2.39.10:9000” to go to port 9000 for the machine at 128.2.39.10. Clients also connect via a port on the client’s network interface usually chosen randomly from ports that aren’t reserved.
A socket represents an end of a connection between client and server. A listening socket is used by the server process to wait for connections from remote clients. The ServerSocket class in Java is used to make a listening socket has an accept() method for listening to it. A connected socket can send and receive message to and from a process its connected to. It’s identified by the local IP and port number and the remote address and port, allowing a server to differentiate between connections from different IPs or the same IP on different remote ports. Clients use Socket in Java to establish a connection to a server, which obtains a connected socket as a Socket object via ServerSocket.accept.
Data is exchanged over the network in chunks. The sending side writes a large chunk which could be a string or 10mb or video data. The network chops it up into packets routing them separately across the network and the receiver reassembles them into a stream of bytes. When data arrives it goes into a buffer which is an array in memory. Data going in or out of a socket is a stream of bytes. Java’s InputStream objects represent sources of data flowing into a program such as FileInput stream for reading a file, System.in for user input, and an input from a network socket. OutputStream objects represent data sinks where data can be written to, such as FileOutputStream for saving to files, System.out is a PrintStream which prints readable representations, and can be output to a network socket. The output of one process is the input to another for sockets.
Streams can handle a variety of data times and are a sequence of data and byte streams are the most common stream type. The FileInputStream has a read method and FileOutputStream has a write method. It’s important to always close streams after using them. Byte streams what other stream types are built on but should generally be reserved for primitive I/O. Character streams can translate internal formats to a local character set automatically, typically an 8-bit superset of ASCII. Character stream classes descend from the Reader and Writer classes in Java with FileReader and FileWriter helping for file I/O. Character streams are often wrappers for byte streams. FileReader and FileWriter use FileInputStream and FileOutputStream respectively. In the examples in Java’s tutorial, BufferedReader and PrintWriter are added to support line-oriented I/O. In general, the implementation process is to set an inputSteam and outputStream and “while ((x = inputStream.read()) != null) { outputStream.write(x); }.” The exact function names can change for different readers and writers. The initialization and while loop are in a try block with “close” called in a finally block if the streams aren’t null.
The streams so far used unbuffered I/O, handling each request with the underlying OS which can be bad for efficiency. Java’s buffered I/O streams use a buffer, using the native API only when the buffer is empty for input or full for output. Readers and Writers can be wrapped in BufferedReader and BufferedWriter to help with this for characters and BufferedInputStream and BufferedOutputStream can do the same for byte streams. A buffer can be flushed or emptied by calling a flush method with some classes supporting “autoflush”, triggered by certain events. Scanner objects can be used to break formatted input into tokens and translating according to data type, separating on whitespace by default. A Buffered Reader can be passed to a Scanner and it’s “hasNext” and “next” methods can be used to print or access data. System.out.format can also be specified to format how outputs appear. Java’s standard streams (System.in, System.out and System.err) are byte streams with the latter two being PrintStream objects which use an internal character stream. For a character stream, System.in can be wrapped in InputStreamReader. System.Console has reader and writer methods providing character stream but may not always be supported based on OS. It can be useful for providing password entry as it suppresses echoing.
Blocking means a thread waits for an event to occur before proceeding. This can describe methods and method calls. If a method is a blocking method, then a call to it can block. Socket I/O streams exhibit blocking behavior when an incoming socket buffer is empty (calling read blocks until data is available) and when the destination socket’s buffer is full (calling write blocks until space is available).This is convenient for programming since the code can be written as if read or write will work regardless of the timing and the operating system can manage the delay until it can succeed. Blocking is used for concurrent programming as well, though this waiting can cause a deadlock.
In Java, Urls and URLConnections provide access to internet resources, sockets are good for lower level network communications such as for client-server applications. TCP provides a reliable communication channel where client and server bind a socket to their end of a connection and read and write from that socket. A socket is an endpoint in a two-way connection between programs running on a network and java.net provides Socket and ServerSocket for implementing the client and server sides respectively. When a server accepts a client request, it gets a new socket for the same local port and sets its remote endpoint to the address and port send by the client. The new socket lets it keep listening for connection requests while also handling a connection client. Endpoints combine IP and port numbers, allowing for multiple connections between a host and server. Java’s classes help to make connections platform-independent. URL classes are more appropriate for providing high level connections for web resources if Sockets aren’t needed. Java’s official tutorial shows examples of using these to write a client and server, specifically examples involving “KnockKnockServer” which does “knock knock“ jokes with a client.
Protocols are a set of messages that can be exchanged over a connection. A wire protocol is a set of messages represented as byte sequences. Most internet applications use ASCII based wire protocol and telnet can help inspect them. HTTP or Hypertext Transfer Protocol is the web’s language. Internet protocols are defined with RFC (request for comment) specifications and may require specific HTTP versions which the telnet command will show. SMPT or Simple Mail Transfer Protocol is a protocol for sending emails. When designing a wire protocol, the number of different messages should be small, each message should have a well-defined purpose and coherent behavior, and the set of messages should be enough to make needed requests. Protocols should be platform independent and not give away implementation details. The protocol should be easily generated and parsed which will help avoid bugs. Its also important to consider how to avoid spam, which SMTP didn’t handle well and required additional systems. Also, consider security and whether protocols let clients send large amount of data to overload a system.
Serialization is the process of transforming data structures in memory into an easily stored and transmitted format, such as JSON. It’s better to use existing ones rather than trying to invent your own. A grammar can be used to specify allowed messages on a protocol, and HTTP 1.1’s is shown at https://www.w3.org/Protocols/rfc2616/rfc2616-sec5.html in a similar format to the grammars shown before comparing the Telnet output to its interpretation. In addition to a grammar, preconditions and postconditions will also need to be specified what a request must be and what response will be sent back.
In testing, network code should be separated from the testing of data structure and algorithms. The thread safety strategies should be used for ADTs that won’t need to be used concurrently from multiple threads. Socket code should be separated from stream code and some modules can be tested with streams that don’t come from a socket via ByteArrayInputStream or ByteArrayOutputStream, using test stubs to isolate and test the specific function, though a mock object may be required to simulate real clients or servers for more complex modules.
Reading 22: Queues and Message-Passing
The two models for concurrent programming were shared memory and message passing. While multiple threads in a Java process was the primary example for shared-memory, this reading looks at message passing. In message passing, concurrent modules send immutable messages over a communication channel such as with clients and servers. Message-passing leads to better safety from bugs as interaction is explicit rather than implicit (via data alteration). Mutability is already a common source of bugs, which passing immutable objects helps handle.
In Java, a synchronized queue can help passage messages between threads via the BlockingQueue. An ordinary Queue has add(e) which adds e to the end of the queue and remove() which returns the head or throws an exception if empty. BlockingQueue adds operations which wait for space to be available or the queue to be non-empty, with put(e) and take() as blocking implementations of add(e) and remove(). The producer-consumer design pattern is similar to the client-server pattern. Producer and consumer threads share a synchronized queue which producers add to and consumers remove and process from, though the queue must be safe for concurrency. Java’s ArrayBlockingQueue implementation is a fixed size queue using an array representation where put() blocks if the queue is full. LinkedBlockingQueue can grow using a linked-list representation, so unless a max size is specified, put() won’t block. Queues can hold objects of an arbitrary immutable type and messages should prevent race conditions and enable clients to perform atomic operations they need.
In the client-server model if a client or server needs to stop listening for messages, a socket can be closed or the process can be quit altogether. But a queue cant be closed and what about a single thread in a process. A special message on the queue could signal the consumer to end its work. You can interrupt a thread with its interrupt() method. An InterruptedException catch block can be added for a try/catch in a while loop and another program can check if “Thread.interrupted()” for coordination based on this and break otherwise. Overall, compared to synchronization, message passing can make it easier for each module to maintain thread safety invariants as its data is transferred in a secure channel, you don’t have to worry about multiple threads accessing shared data.
Reading 23: Locks and Synchronization
The correctness of a concurrent program shouldn’t depend on accidents of timing. This reading focuses on synchronization to implement safe data types which share memory. Locks are a technique for this which allows at most one thread to own an object at once, which tells other threads not to touch it. Locks have acquire and release operations, where acquire lets a thread take ownership of a lock and blocks other threads from acquiring a lock until released. Using a lock in the bank account example, if a machine needs to acquire a lock before updating an account balance, ensuring machines are synchronized. A lock can be set per account for minimal interruption. While this can prevent race conditions, it’s possible to get into a deadlock where two threads wait for each other and neither can make progress. In the bank example, if two machines are trying to make transfers between the same two accounts, each will need a lock for both. If each gets one and waits for the other, there’s a deadlock. A deadlock can involve two or more modules where there is a cycle of dependencies. Deadlocks don’t necessarily require locks to be involved and can occur in other ways.
An example of a problem is a multi-user text editor like Google Docs where a mutable data type represents the document. An interface for EditBuffer has voids insert and delete and a public int length and string toString() method. A string wouldn’t be a good way of representing text as for every edit, it would need to be copied. A character array with an end space could be better if only the end is added to, but would require copying for edits elsewhere. A gap buffer is a representation used by many text editors which is a character array with extra space throughout. When an insert or delete is made, the gap is moved to the location of the operation and then the change is made. If the gap is already there, nothing needs to be copied, an insert() consumes part of the gap and delete() enlarges it. The cursor can help signal where the gap should be. A GapBuffer implementation of the EditBuffer could have character array, gapStart and gapLength properties. With multiple users, there would be different gaps corresponding to each user’s cursor, though systems should be tested for a sequential, single threaded environment first.
Java provides locks as a build-in feature. Every object has a lock associated with it implicitly and all object instances have a lock. Even Object itself has one. You can’t call acquire on release on intrinsic locks, but you can use “synchronized” to acquire the lock for a statement block, “synchronized (lock) { balance = balance + 1; }”. These provide mutual exclusion where only one thread can be in a synchronized region guarded by the lock. This sets you back in a sequential programming environment for that object. Unfortunately, acquiring a lock in this way only stops other threads from entering synchronized blocks until the lock is released and threads that don’t try and acquire the same lock can still access the object. All modules must agree on the lock they will acquire and release. For class methods (except the constructor), to enforce this, every method’s code can be wrapped with “synchronized (this) {“ to enforce these locks. This must be set for every method including reads since an object may be seen in a partially modified state otherwise. This is the monitor pattern where only one thread can be in an instance of a class at once. An equivalent would be writing “public synchronized …” in a method definition which does the same thing.
A locking discipline is a strategy for ensuring synchronized code is thread safe. Every shared mutable variable should be guarded by a lock and only accessed in a synchronized block that acquires it. If an invariant involves multiple shared mutable variables then all must be guarded by the same lock and the invariant reestablished before releasing the lock. The monitor pattern satisfies both of these. This might not be enough if a sequence of calls needs to be made, then the entire object may need to be called with a synchronized block which creates an atomic region while a multi-method process runs. Unfortunately, synchronization can cause a method call to take much longer due to lock acquisition, cache-flushing and communication and shouldn’t be used when it isn’t needed. If every method on an object has “synchronized,” then the lock is the object itself and every client with a reference to the object has a reference to the lock. For a static object, calling synchronized could also lock an entire class and block method calls to other objects that aren’t being worked on and code touching the document object may not even acquire the same lock. Thread safety requires a documented discipline and the synchronized keyword won’t fix most problems by itself.
For the EditBuffer the interface isn’t friendly for multiple simultaneous clients as if one person inserts or deletes before an index position obtained by another, the index will become invalid. A “Position” data type might keep track of a location based on text around it and inform a client what happened to the position to let them decide what to do. Again, locks can lead to the possibility of blocking and deadlock is more common here than with message passing. In a social network example, two friends calling methods that would change both objects’ status can each obtain a lock to one and deadlock waiting for the other. One solution is lock ordering, where all code must acquire locks in the same order (maybe alphabetically). Unfortunately, lock ordering isn’t modular as the code needs to know about all locks in its system and it would need to know about all locks it needs to obtain first which may be a problem in a tree structure. A more common solution is coarse-grained locking where a single lock is used to guard multiple objects based on some grouping. This can lock objects that don’t need to be locked and can make systems effectively sequential in the worst case.
In practice, library data structures use neither no synchronization letting multithreaded clients add locking or a monitor pattern. Mutable data structures with many parts typically use coarse-grained locking or thread confinement. Search often uses immutable data types and operating systems often use fine grained locks for high performance with lock ordering to handle dead locks. Databases use “transactions” to avoid race conditions which don’t acquire locks but can rollback on when a race occured. Other recommended courses on databases are 6.170 Software Studio and 6.184 Database Systems. For performance, 6.172 Performance Engineering is recommended.
Reading 24: Graphical User Interfaces
Three of the most important design patterns for GUI software architecture are the view tree, the model-view-controller pattern and the listener pattern. GUI’s are composed of view objects, each occupying an area of the screen (typically rectangular and called a bounding box). In Java Swing, a view is made up of JComponent objects and elements or nodes in HTML. The view tree is aheirarchy of views where some views contain others. Typical components are windows, panels and toolbars and the view tree is a spatial hierarchy with child views inside their parent’s bounding box. Views are responsible for displaying themselves and GUIs change their output by mutating the view tree, such as replacing photo nodes to show new images. A redraw algorithm in the GUI toolkit changes the affected parts of the tree. In Java Swing, views have paint() methods for drawing themselves and calling it on the root recursively redraws the tree. The view tree controls how views are laid out and bounding boxes assigned. A layout algorithm calculates positions and sizes of views. Some containers (JSplitPane and JScrollPane) do layout themselves while others (JPanel and JFrame) delegate decisions to a layout manager (GroupLayout, BorderLayout, BoxLayout).
Inputs for GUIs are handled modularly, passing inputs to where they occur in the view tree with event handling. This is an instance of the Listener or Publish-Subscribe pattern where an event source generates a stream of discrete events corresponding to the source’s state transitions and listeners subscribe to event streams calling functions as events occur. The mouse is the source here and events are the changes in its state (position or button clicks). When a source occurs, the source calls listeners’ callback methods. Some examples of objects include JButton which sends an action event when its button is pressed, JList which sends a selection event when the selected element changes, and JTextField which sends change events when its text changes.
A backend is used to represent the data and logic the user interface shows and edits. The model-view-controller pattern separates the UI frontend from the application backend with the backend as a model and frontend as the view and controller. The controller handles input and the view displays output. The model is responsible for maintaining application specific data and providing access to it. Models are often mutable with provided methods for safely changing the state. They notify clients so views can update their displays and controllers can respond, with vies and controllers registering themselves as listeners for change events from the model. View objects are responsible for the output and usually occupy part of the screen querying the model for what to display. The controller handles input, receiving keyboard and mouse events and informing the model. A simple example is a Java Swing JTextField where a model is a mutable string, the view is an object that draws the text on the screen and the controller receives keystrokes and inserts them into the model. A file system browser is a more complicated example of an MVC system. A benefit of this system is that an interface can have multiple views showing the same data. Views and models can also be reused in other applications. For instance, Java Swings UI classes can be reused on different models.
Background processes can be used so an event doesn’t delay returning to the event loop. Long tasks can run in the background while a program can be used in other ways. Java’s event-dispatch thread is different from its main thread and is started when a UI object is created, making every Java GUI program multithreaded. This often isn’t noticed as the main thread exits after starting creation of the view, but Swing programs’ multithreaded nature can create the risks seen before with multithreaded systems. The view tree is a shared mutable data type that isn’t thread safe and methods on Swing objects should be called in the event-dispatch thread. The event loop can be used as a message-passing queue to get back to the event-dispatch thread.
Reading 25: Map, Filter, Reduce
This reading is all about Functional Programming. Map/filter/reduce is a design pattern that simplifies the implementation of functions operating over sequences of elements without needing explicit control flow (ex “for” and “if”). Functions as first-class data values is another strategy talked about here, though requires more verbosity than with Python. Iterators, as seen before, were a way of looping through items without worrying about what the data structure used is. Iterable is an interface with these and any Iterable can be used with “for (type item: items)”. Any item this works on uses an iterator. Map/filter/reduce patterns are similar to Iterator, treating the entire sequence of elements as a unit, removing the need for control statements and temporary names.
An imagined abstract data type, Seq represents a sequence of type E elements (ex [1,2,3,4] in Seq). Map applies a function to each element returning a new sequence with the results in the same order. In Python “map(str.lower, [‘A’, ‘b’, ‘C’]) would give [‘a’, ‘b’, ‘c’]. The map function takes a function as its first argument. In Python, functions are first-class and can assigned to variables and used as parameters or return values and stored in data structures. First-class functions are a powerful programming idea and Lisp was the first language to implement them. If you only need to use a function for one map, you can use a lambda instead. For instance, “map(lambda k: 2**k, [1,2,3,4])” would give [2,4,8,16]. In Python, lambda’s can’t use if/else, loops or local variables. Map can also be used to mutate objects even if you don’t care about return values and some implementations (such as Python’s) can take multiple arguments (adding two lists, for example). Filter tests each example with a predicate, keeping only items that satisfy it and returning a new list. For instance, “filter(lambda x: x % 2 == 1, [1,2,3,4])” returns [1,3]. Lastly, reduce combines elements of the sequence and takes an initial value (which is the return for an empty list). For instance, reduce(lambda x,y: x+y, [1,2,3], 0) would be 6 since 0 is the initializer for x and the remaining items are added to it. If omitted, the first element of a list will be its initializer. It’s also possible to design a reduce algorithm where which goes in a different direction.
It’s possible to query databases using map, filter and reduce and relational databases call the paradigm called “project/select/aggregate.” In a SQL query, ‘select max(pixels) from cameras where brand == “Nikon”’, cameras is a sequence (list of rows), “brand == Nikon” is a filter, pixels is a map extracting the pixels field from each row, and max is a reduce. A couple of other techniques that can be used to combine functions are to create a compose(f, g) function to “return lambda: x: g(f(x))” and a chain(funcs) to “return reduce(compose, funcs)”. These techniques can be used instead of writing out lots of separate functions to handle loops. Maps and filters using pure functions, which don’t mutate data, are instantly parallelizable. MapReduce is a pattern for parallelizing large computations this way.
In Java, primitives and object references are the only first class values, though objects can have methods which can be used similarly. The Runnable object passed to a Thread constructor is a first-class function, same with Comparator passed to a SortedSet, or the KeyListener object for a GUI. This design pattern is a functional object or functor where an object is used to represent a function. Lambda’s can help create instances for functional objects, such as ‘new Thread(() -> { System.out.println(“Hello”); }).start();’. To use a lambda, the compiler needs to verify the type of the functional object (such as a Runnable) and that the inferred type is a functional interface, which has one method (run() for Runnable). Java’s standard functional interfaces Function, BiFunction and Predicate can be used to work with the map/filter/reduce pattern. For map,
public static <T,R> List<R> map(Function<T,R> f, List<T> list) {
List<R> result = new ArrayList<>();
for (T t : list) { result.add(f.apply(t)); }
return result;
}
can be used with
Function<String,String> toLowerCase = new Function<>() {
public String apply(String s) { return s.toLowerCase(); }
};
map(toLowerCase, Arrays.asList(new String[] {“A”, “b”, “C”}));
This also works passing a lambda function “s -> s.toLowerCase())” instead of “toLowerCase” or via a method reference “String::toLowerCase”. All three of these do the same thing. Referring to a method reference in Java is similar to referring to a Python function by name without calling it. Stream in java defines map, filter, reduce and more and collection types have a stream() operation for returning an object of that type. Arrays.stream returns a Stream of an array. Arrays.stream(x).filter(…) could then be called. Stream also provides a flatMap for mapping and flattening. Java’s Function interface provides a version of compose() although chain() causes an issue since lists must be homogenous. You can define them only if all arguments to the functions passed are the same type.
Reading 26: Little Languages
A little language is the idea of building a language to solve a range of problems instead of a program to solve a single problem. Comparing the Formula type value defined earlier, “And(Or(…), Or(…)” to something already in Java such as “(p || q) && ((!p) || r)”, the former can be saved and worked with later, while the former will be evaluated immediately. By defining other languages, code can be represented as data. Functional objects are another example of representing code as data to be passed around and called as needed. Lambda’s are a convenient tool for creating these objects. Building an abstract data type extends Java’s existing types to add a new type, with new operations for a new problem domain. This type is like a new language built on top of the existing one which was already an abstraction of something else. A language can be used to solve a variety of problems compared to a single program.
This reading shows an example of a language for writing music with the help of Java’s API for working with MIDI. Most of the functions and classes mentioned are specific to MIT code written for the course. Java’s music.midi.MidiSequence player plays a sequence of notes and implements the music.SequencePlayer interface. An addNote function schedules a note to be played, and play() actually plays the music. Instrument is an enumeration of different instruments and Pitch is an ADT for pitches. A notes operation takes a string of keys and instrument to create a tune. A Music class is created with duration and play methods. Music’s duration returns the duration of the music in beats and it’s play plays the music with a sequence player. A MusicLanguage class holds addNodes and other static methods which operator on Music objects. A pitch on an instrument is a Note and silence is a Rest. A tree-like structure is used to combine pieces of music.
Music’s data type definition is Music = Note(duration:double, pitch:Pitch, instrument:Instrument) + Rest(duration:double) + Concat(m1:Music, m2:Music). Music uses the composite pattern where single objects and groups are treated the same way. Formula and the GUI view tree also use this pattern, which leads to a tree data structure with primitive leaves and composite internal nodes. Notes are represented in abc notation which is a text based music format which a parser is implemented to handle. The code is designed to actually be able to write and play music in Java.
Reading 27: Team Version Control
This is a very short reading, reviewing the Getting Started section and previous reading on Git with a few notes on working in a team. It notes that it’s important to communicate, telling teammates what you’re working on to avoid wasted time. You should write specs and make sure they’re agreed on. Then write tests and run them before starting and then before commiting. Tests can be automated with JUnit or a tool called Didit when code is pushed to Athena (both MIT class tools, I believe). Review commits with git diff and avoid noisy logs. Pull code before you start working to get the latest version and avoid large merge conflicts late. At the end of a work session everyone should be updated to the same commit at the end of a work session. Lastly, it tells the students to avoid branches or rebasing for the course and to work together in the same place.
Conclusion
And with that, I’m reaching the last third of this project. While its weird to think that this is the first course to really be software focused since Intro to CS, this course provided some review along with a good amount of new material or at least familiar material I hadn’t thought much about. I haven’t done much with Java before but remember being initially confused by C#’s strongly typed nature and interfaces. Seeing how different classes build on each other, the comparison of mutable and immutable types and the techniques used for handling concurrency and multithreaded systems by writing safe code has been interesting. I’m not sure if I’ll ever end up working with Java of C# again, but if I do a lot of the material here will be useful to go back to. Regardless, the concepts taught are applicable across programming languages even if the syntax isn’t exactly the same.
Leave a Reply