Lecture 34 (Tychonievich) - Good Code

Lecture Date: Wednesday, April 8

What makes good code?

  • It works (for what set of inputs?) – versatility and correctness
  • It is maintainable – readable, simple, good comments and naming, etc.
  • It is efficient – uses minimal time or memory when running
  • It is easy to create (meaning inexpensive to create too)

We looked at the following code for the grid-of-rooms we did in Lab 2:

Tiny
1
2
Robot r = new Robot(4,4);
r.say(16);
Squares
1
2
3
4
5
6
7
Robot r = new Robot(4,4);
int roomsInY = 1;
while(r.check('S')) { // proportional to height
  r.go('S');
  roomsInY += 1;
}
r.say(roomsInY * roomsInY);
Random
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
Robot r = new Robot("xx x\nx  x\n xxx");
ArrayList<String> visited = new ArrayList<String>();
int x = 0, y = 0;
visited.add(x+","+y);
while (true) {
  double number = Math.random();
  if (number < 0.25) {
      if(r.check('E')) {
          r.go('E');
          x += 1;
      }
  }
  else if (number < 0.5) {
      if(r.check('S')) {
          r.go('S');
          y += 1;
      }
  }
  else if (number < 0.75) {
      if(r.check('W')) {
          r.go('W');
          x -= 1;
      }
  }
  else {
      if(r.check('N')) {
          r.go('N');
          y -= 1;
      }
  }
  String here = x + "," + y;
  if(!visited.contains(here)) {
      visited.add(here);
      r.say(visited.size());
  }
}

… as well as general maze solving

From Lecture


Lecture 34 (Sherriff) - Speed, Simplicity, Correctness

Lecture Date: Wednesday, April 8

Do you remember Lab 2? The one with the robot and counting rooms? We’re going to circle back around to that today.

What makes code “good”? It’s kind of an arbitrary question. Code can always be “better” to some degree.

It could be:

  • faster
  • easier to read
  • have fewer bugs

We can almost always improve on one of these three areas: speed, simplicity, and correctness. All of them don’t have to be perfect to have a “working” system. (Yes, even correctness - most, if not all, software ships with some known errors in it.)

Consider these two bits of code:

1
2
3
4
5
6
int x = a;
int y = b;
// swap x and y:
int tmp = x; // x = a, y = b, tmp = a
x = y;       // x = b, y = b, tmp = a
y = tmp;     // x = b, y = a, tmp = a
1
2
3
4
5
6
int x = a;
int y = b;
// swap x and y:
x -= y;    // x = a-b,         y = b
y += x;    // x = a-b,         y = b+(a-b) = a
x = y - x; // x = a-(a-b) = b, y = a

Which is “better”? Why?

Today we start on discussing various core algorithms in CS. We want to write “good code” that’s “fast” and “easy to maintain.” So what exactly does that mean?

As an example, we’ll play with a robot counting rooms, just like you did in Lab 2.


Lecture 21 (Edwards) - Types

Lecture Date: Monday, April 6

illustration of type by location or by label Courtesy of Professor Tychonievich.

How do you remember what is Jim’s phone number? Do you leave it on a postit note on your desk and just remember that the number there must be Jim’s? Or do you Write Jim’s name on the postit note and leave it some where in your room?

This first way of keeping information is known as “static” since it is dependent on the position of the informaiton. The second we call “dynamic” since the information could be moved anywhere.

Computers have the same issue: Remember that computers store information in binary (instead of base 10) but this means that everything is really a number. A computer needs to know if that sequence of 0’s and 1’s are for an int or a double or a String, etc.

Java is a statically typed language. When we say ‘int x’ we are saying create a box called ‘x’ and it can only hold ints. I can write ‘x=3;’ but I cannot write ‘x=“hello”’. In a dynamic language this is allowed.

As we talk about type systems and languages, we’ll think about how they impact the following:

  • ease of writing programs
  • program runtime speed
  • liklihood of bugs
  • ease of reading the program a month from now
  • ability to run the program on a particular device

After this we will start talking about what makes good code. Have a look at the following and see which you think is better code.

int x = a; int y = b; // swap x and y: int tmp = x; // x = a, y = b, tmp = a x = y; // x = b, y = b, tmp = a y = tmp; // x = b, y = a, tmp = a

int x = a; int y = b; // swap x and y: x -= y; // x = a-b, y = b y += x; // x = a-b, y = b+(a-b) = a x = y - x; // x = a-(a-b) = b, y = a

Which one is faster to run? Faster to write? Easier to understand? More likely to work?

cfg.jpeg


Lecture 33 (Tychonievich) - Type Systems

Lecture Date: Monday, April 6

How do you rememember which number is your student ID, which is your phone number, which is your social security number, and so on? Suppose you wrote down a number and are trying to remember what type of number it is?

illustration of type by location or by label

Some people might file the numbers in particular locations: “it’s the number on the post-it by my bed so it must be my SSN.” We’ll call those people “static” since their filing system depends on things staying where they are placed. Others might file them wherever, but write down what they are: “this card says ‘SSN:’ so it must be my SSN.” We’ll call those people “dynamic” since their filing system works even if they move things around.

Computers have this same problem: they store things in binary, but that’s just another kind of number. Was this bunch of 1s and 0s supposed to be an int or a double or maybe even where to look to find an ArrayList<String>? We know it is a binary value, but what type of value is it? Computers use one of the same two kinds of solutions to this problem too: statically-typed languages remember what type they put in that box there while dynamically-typed languages store the type with the value.

Java is statically typed. When we write int x we tell java “this box I’m calling x, any bits you find in it must be an int”. Where the value is located tells us what type of value it is.

There are also dynamically typed languages: Javascript, Matlab, and Python to name just a few you might have heard of. In those languages, variables don’t have type, values do. We can write x = 3 on one line and x = "hi" on the next: x is just a box, the type is stored with the value.

Today we’ll poke around a bit with these ideas, see how sometimes Java actually does both static and dynamic typing, and talk about learning other languages.

Java is also a strongly typed language, which means that once you set a type, it can never be changes. You can cast it, but that’s actually makes a new value with the new type, it doesn’t change the type of what was alreayd there. The original data stays with the original type.

As we talk about type systems and languages, we’ll think about how they impact the following:

  • ease of writing programs
  • program runtime speed
  • liklihood of bugs
  • ease of reading the program a month from now
  • ability to run the program on a particular device

From Lecture


Lecture 33 (Sherriff) - Type Systems

Lecture Date: Monday, April 6

We’ll pick up with looking one more time at our poor, discarded kittens from Friday. Specifically, we’ll look at how we kept up with the kitten’s ID number.

We’ll move on from there to talk about data types. How exactly does Java keep up with what type a variable is? How do other languages do it?

The War between Filing Systems

There are lots of numbers in your life. Social security numbers, student ID numbers, SIS person numbers, telephone numbers, zip codes, … How do you know which number is which?

Option 1: remember. This number is on the post-it beside my bed, which is where I wrote my student ID number, so that must be what it is.

Option 2: annotate. This piece of paper says SSN: 012345678 so it must by my SSN, not my telephone number.

In programming we call the first static typing and the latter dynamic typing. People argue about which one is better heatedly.

Java happens to be statically typed. Other languages, like Python, are dynamically typed.

How does this affect how we write our programs?

Imagine a program that you might write that has these lines:

1
2
3
x = 4;
x = "Hello World";
x = new Kitten();

In Java, this would never work, because we would have defined x to have a particular type. After that, it can’t be changed. But, if we store the type with the data itself and not the variable, then this works just fine. x is just a pointer to some data - how we interpret it is up to the programmer.

You might think that dynamic typing can get a programmer in a lot of trouble if they don’t keep their variables straight. And you’re right. But it does make for less coding in general, even if dynamically typed languages are usually slower than statically typed ones.

Java is also a strongly typed language, which means that once you set a type, it can never be changes. Oh sure, you can cast it, but that’s just the type being temporarily converted. The original data stays with the original type.

So, if we’re building a program, and given a choice, which would you prefer to do?

  • Write a program quickly
  • Write a program that runs fast
  • Write a program that has few if any bugs
  • Write a program that you can read and make sense of latter
  • Write a program that runs on many different devices

This partially drives our choice of language.


Lecture 32 (Sherriff & Tychonievich) - Under the Hood

Lecture Date: Friday, April 3

With all this talk of objects and pass by reference and allocating memory… did you ever wonder exactly where this stuff was being stored?

There are different types of “memory” in a computer

  • Cache - small, really fast memory that’s attached to the processor - used as “working memory”
  • RAM (Random Access Memory) - holds info about programs currently running - used as “short term memory”
  • Hard disk / SSD - holds data that will persist if the power is cut off - used as “long term memory”

Your programs are .java files, stored on the disk itself. But when they run, the JVM (Java Virtual Machine) requests from the operating system that some space be set aside for your program to run in. This is typically in RAM (although it can vary a little).

Once the program gets going, you have something called the stack and the heap.

stackvsheap

Image credit: thenewcircle.com

The stack is where variable pointers go, such as with a complex type. The actual values of the complex type variable is found in the heap.

What happens when a variable no longer points to something in the heap? This is called garbage collection. We’ll take a look at how this works by looking at an example program.

Sherriff:

Tychonievich:



Lecture 30 (Tychonievich) - Exam 2 Review

Lecture Date: Monday, March 30

We walked through the Test 2 Review Guide

We wrote the following code:

Example code from class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.ArrayList;
import java.util.Arrays;

public class Exam2Review1 {
  public static void main(String[] args) {
      String s = "123";
      int[] a = {1,2,3};
      ArrayList<Boolean> l = new ArrayList<Boolean>();
      l.add(false);
      l.add(true);
      l.add(true);
      int slen = s.length();
      int alen = a.length;
      int llen = l.size();
      
      String ss = s.toString();
      String as = a.toString(); // a was an int[], 
      // above toString was non-static and defined in int[] class (almost)
      
      String ls = l.toString();
      
      String as2 = Arrays.toString(a);
      // above toString was static and defined in Arrays class
  
      
      System.out.println(ss);
      System.out.println(as);
      System.out.println(as2);
      System.out.println(ls);
      System.out.println(System.out.toString());
      
      System.out.println(Exam2Review1.logBase3(1110.5));
      System.out.println(Exam2Review1.theAnswer());
  }
  
  public static void anything() {
      System.out.println("Anything could happen here");
  }
  public static String anything2() {
      return "Anything could happen here";
  }
  public static int theAnswer() {
      return 42;
  }
  
  /* logBase3(81) = 1 + logBase3(27) = 1 + 3 = 4
  * logBase3(27) = 1 + logBase3( 9) = 1 + 2 = 3
  * logBase3( 9) = 1 + logBase3( 3) = 1 + 1 = 2
  * logBase3( 3) = 1 + logBase3( 1) = 1 + 0 = 1
  * logBase3( 1) = 0
  */
  public static int logBase3(double x) {
      if (x <= 1) {
          // 1. base case
          return 0;
      } else {
          // 2. recursive case that 3. makes progress
          return 1 + logBase3(x / 3);
      }
  }
}

We also took the following problem description:

You are asked to create a simulation of a free market economy. The basic idea is that different people will trade money for products and that different people value different products differently but that they all want money. Your simulation should be able to run for different time steps and involve the idea that people only know a subset of the other people.

and identified potential classes Person, Market, Money, Product, and Time; mentioned that no all would need to be classes in all designs (double might do fine for Money, for example); and sketched out the following Person UML Class Diagram:

Person
- known : ArrayList<Person>
- desiredProducts : ArrayList<Product>
- money : Money
+ Person()
+ Person(wanted : ArrayList<Product>)
+ Person(wallet : Money)
+ trade(fromProduct : Product, toProdct : Product, Person) : boolean
+ trade(Product, Money, Person) : boolean
+ tax(Money) : boolean
+ tax(Money) : Money
+ tax() : Money
+ salesTax(Product) : Money