Overview

• Preliminaries.
  • Admin.
  • Questions on the homework.
• Thinking about memory.
• Loop invariants.
• Data structure invariants.

Preliminaries

Admin

• For the asssignment, you do not need to grab the JSON from the Web. Assume that it's in a string. (In your epxeriments, you can just load that string from a file, or use a predefined string, or ...)
• Something fun you might like to contribute to https://github.com/kyledreger/1000-nights
• Upcoming extra credit opportunities:
  • One Grinnell rally today at 4pm (unless you are taking photos).
  • Any self-care week activity.
  • Learning from Alumni Thursday: Erik Hanson (in person)
  • CS Extras Thursday: Summer opportunities in CS.
  • CS Table Friday: Beyond Efficiency.
  • Swim meet Friday and Saturday.
  • Dance Ensemble, Friday 7:30, Saturday 7:30, Sunday 1:00
  • One Acts, Figure it out yourself

Questions on the Homework

What simple tests?

{ }
{ "sam":"rebelsky" }
{ "samr" : { "fname":"Sam", "lname":"Rebelsky", "ryphot":0 } }

What do we return?

Mostly dictionary-like thingys

Also arrays of those

You might create MyJSONObject and MyJSONArray

Thinking about memory

Memory associated with your program has three parts

• Fixed
  • Globals
  • Constants (e.g., char *str = "Hello";
• Stack
  • Local procedure variables
  • Procedure parameters
• Heap
  • Things created by malloc and new and the like

Sample code!

public class Counter {
    static int operations = 0;
    int counter;
    void increment() {
        ++Counter.operations;
        ++this.counter;
    } // increment()

    void decrement() {
        ++Counter.operations;
        --this.counter;
    } // decrement()

    int get() {
        ++Counter.operations;
        return this.counter;
    } // get()
} // class Counter

public class CounterExpt {
    public static void main(String[] args) {
        Counter c1 = new Counter();
        Counter c2 = new Counter();
        Counter c3 = c1;

        c1.increment();
        c2.decrement();
        c3.increment();

        System.out.println("ops: " + Counter.operations);
        System.out.println("c1: " + c1.get());
        System.out.println("c2: " + c2.get());
        System.out.println("c3: " + c3.get());
        System.out.println("ops: " + Counter.operations);
    } // main
} // class CounterExpt

Why doesn't this code do what we expect?

// Replace a tree by its right subtree
tree = tree.larger;

It doesn't work because it's pointer assignment (see whiteboard)

Is there a *tree = *tree.larger in Java? NO

We also can't explicitly get the address of something.

Why do we not allow such assignments?

• Java tries to conceal memory.
• Subclassing means that in *left = *right, right have more fields than left.

Code

class Foo {
    int x;
}
class Bar extends Foo {
    int y;
}
Foo foo = new Foo();
Foo bar = new Bar();
*foo = *bar;        // What does this really mean?

Loop invariants

• Evidence suggests that programmers frequently write incorrect code.
• Retrospective: Test!
• Maybe we'd be better off finding techniques to write correct code in the first place.
• Basically: Think carefully about the code while you are writing it
  • Perhaps even construct an informal proof that it's correct
• Evidence; Loops create many problems - Incorrect termination conditions, off-by-1 errors, etc.
• Enter loop invariants - A way to think carefully about what the procedure does.
  • What is the state of my program (memory) before the loop starts?
  • What is the state of my program after some number of repetitions?
  • What is the state of my program after the loop terminates?

Data structure invariants