3.0 - Introduction

Recap

• We know how to construct compound entities from primitive procedures and data.
• We know that abstraction helps us cope with complexity.
• We don't know how to combine these together to create a larger system.
• We don't know how to make this combination modular.

Modular System - System divided "naturally" into coherent parts that can be separately developed and maintained.

Design Strategies

The goal of each design strategy is to minimize the amount of time and effort it takes to modify the program.

Object-Based

• Structure of programs should be based on the structure of the system being modeled.

• Each object in the system has a corresponding object in the program.

• Each action in the system has a corresponding operation in the program.

• The behavior of the objects in the system change over time.

• Problems:

  • Identity - How objects can change yet maintain their identity.

Stream-Processing

• Concerned with how information flows through the system.
• Problems:
  • Time - Need some way to decouple simulated time in our model from the actual order of the events that take place in the computer during evaluation.

3.1 - Assignment and Local State

• Introduces assignment.
• The mechanism used to perform assignment, set!.
• The concept of state, and that state can be local to a procedure.
• The benefits of assignment such as:
  • Letting us encapsulate local state variables inside of a procedure.
    • How this encapsulation allows us to maintain a modular design.
• The costs of assignment such as:
  • Computational functions can no longer be interpreted as their equivalent mathematical counterparts.
    • This leads to the breakdown of our substitution model of computation.
  • Issues of identity between two computational objects.
    • Two objects defined in the same way may have completely different behavior due to differences in their internal state.
• Introduction to the environment model of computation to cope with the fact that variables now refer to places rather than values.
• The difference between two programming paradigms:
  • Functional
    • Programs designed without any assignment.
  • Imperative
    • Programs designed with extensive use of assignment.

What is Assignment?

A variable used to directly map to a value. A variable and its value were interchangeable.

    x <---> 4

For this reason, we could safely substitute every instance of our variable (x) with the value (4) it was mapped to.

    x + 7

is identical to

    4 + 7

When we add assignment, a variable is no longer interchangeable with it's value. A variable now maps to a place.

                -----------
    x -------> | somewhere |
                -----------

In this location, we store our value.

                  -------
                 |   4   |
                  -------

Once again, we still have:

    x + 7
    // becomes
    4 + 7 

Crucially though, we can change the value in the location at any time without our variable knowing.

                  -------
                 |   5   |
                  -------

And now, even though we have the same expression of x + 7, we get a completely different answer.

    x + 7
    // becomes
    5 + 7 // <- This is a completely different expression. x became 5 instead of 4.

Because the value at a location can change at any time, we must begin to start thinking about time. Before the change, x gets subsituted with 4, after with 5.

3.2 - The Environment Model of Evaluation

This section is sort of intuitive to me so I didn't take too many notes.

• Introduces environments.
  • Environments maintain the places where values are stored.
• An environment is made up of a sequence of frames.
• Each frame is a table of bindings.
  • A binding is just another name for a place.
    • As such, a binding is what we use to map a variable name to its corresponding value.
• Explains when frames get created (when we evaluate a procedure), and that local state is stored within these frames.
• Explains that the same procedure can be executed in different environments yielding different results.

3.3 - Modeling with Mutable Data

• We already know to use data abstraction when modeling complex real-world objects.
• We have not yet had to model objects with changing state. How do we cope with this new requirement?
  • We must be able to modify our data abstractions with some new operation.
    • These operations are called mutators.

Just by looking at the structure of this section, we can assume that mutable list structure is used to represent both queues and tables.

We can also assume that queues and tables are used as primitives when creating a simulator for digital circuits.

Lastly, we are likely to encounter some_ information regarding how multiple objects can be composed together to mutate each other's state.

Layout of the Section

Data Abstraction Recap

Let's look again at what data abstraction is:

We represent a real world concept as something (denoted in picture as a "cloud of nothingness"). This cloud is created via a constructor. Now, anytime we want to work with the real-world concept, we just create a new cloud using our constructor.

To get information out of the cloud, we define selectors.

There is one thing missing however, the ability to modify a pre-existing cloud. To enable this, we define mutators. A mutator just lets us change something about our cloud, more specifically, it lets us modify the internal state of the cloud.

3.3.1 Mutable List Structure

• We know how to work with lists already.
• We also know that variables point to places rather than values.
• We can change the values in these places. We call this mutation.
• We can define mutators on our data abstractions such that we can change these values.
• The primitive data abstraction that we've used to build all of our data abstractions was list structure.
  • So to create mutators for our data abstractions, lisp provides us with mutators for list structure. These mutators are:
    • set-car!
    • set-cdr!

3.3.2 Representing Queues

3.3.3 Representing Tables

3.3.4 A Simulator for Digital Circuits

3.3.5 Propagation of Constraints