[Lecture Notes] CMU 17-514 Software Construction

Lec 2. Object-Oriented Basics

Tradeoffs?

  • Version 1
1
2
3
4
5
6
7
8
9
void sort(int[] list, String order) {
// ...
boolean mustswap;
if (order.equals("up")) {
mustswap = list[i] < list[j];
} else if (order.equals("down")) {
mustswap = list[i] > list[j];
}
}
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void sort(int[] list, Comparator cmp) {
// ...
boolean mustswap;
mustswap = cmp.compare(list[i], list[j]);
}

interface Comparator {
boolean compare(int i, int j);
}
class UpComparator implements Comparator {
boolean compare(int i, int j) { return i < j; }
}
class DownComparator implements Comparator {
boolean compare(int i, int j) { return i > j; }
}

Version 1: Shorter

Version 2: Expandable.

TypeScript is a superset of JavaScript because it allows for gradual migration from JS to TS

  • Design for Change (flexibility, extensibility, modifiability)
  • Design for Division of Labor
  • Design for Understandability

Java Primitives: int, long, byte, short, char, float, double, boolean. 注意没有string!

JavaScript Primitives: null, undefined, boolean, number, string, symbol, bigint

  • Primitives are immutable, and passed by value

Object is a non-primitive type.


以下是八股文,看完就忘

Subtype Polymorphism / Dynamic Dispatch

An interface describes the API/way to interact with an object. It does NOT provide the implementation.

There can be multiple implementations of one interface. Multiple implementations can coexist.

Java: Classes implicitly have Interfaces. Prefer interfaces over class types

例如:class PolarPoint implements Point

Dynamic dispatch (in both Java and JavaScript): 用父类指针指向子类对象,调用方法, method is decided at runtime

Java: Static methods are global functions, only single copy exists; class provides only namespace. Java does not allow global functions outside of classes. Java中Static函数就是全局函数(java不允许class外的全局函数),class只作为命名空间。

Dynamic dispatch的优点: Design for change

  • A user of an object does not need to know the object’s implementation, only its interface. 用户不需要知道实现,只需要知道Interface
  • All objects implementing the interface can be used interchangeably. 所有implement这个interface的Object可以互换使用
  • Allows flexible change (modifications, extensions, reuse) later without changing the client implementation, even in unanticipated contexts. 方便修改和重构

Why multiple implementations

  • Different performance: Choose implementation that works best for your use

  • Different behavior:

    • Choose implementation that does what you want
    • Behavior must comply with interface spec (“contract”)
  • Often performance and behavior both vary: Provides a functionality – performance tradeoff. Example: HashSet, TreeSet

Encapsulation / Information hiding

Information hiding的优点

  • Decouples the objects that comprise a system: Allows them to be developed, tested, optimized, used, understood, and modified in isolation

  • Speeds up system development: Objects can be developed in parallel

  • Eases maintenance burden: Objects can be understood more quickly and debugged with little fear of harming other modules

  • Enables effective performance tuning: “Hot” classes can be optimized in isolation

  • Increases software reuse: Loosely-coupled classes often prove useful in other contexts

How to hide information?

  • Java中使用private(注意interface method must be public)
  • Declare variables using interface types, not class types
    • client can use only interface methods. Fields and implementation-specific methods are not accessible from client code.
  • JavaScript中使用闭包 closure, TypeScript中能直接private。
  • JavaScript中使用Modules能 information hiding at file level.

Lec 3. Object-oriented Analysis

如何把用户需求转变成代码实现?

Problem Space (Domain Model) ----> Solution Space (Object model)

Problem Space (Domain Model)Solution Space (Object Model)
Real-world thingsSystem Implementation
Requirements, conceptsClasses, objects
Relationships among conceptsReferences among objects and inheritance hierarchies
Solving a problemComputing a result
Building a vocabularyFinding a solution

Domain Models

Object-Oriented Analysis: understanding the problem

  • domain model

  • find key concepts in the problem domain

    • 找名词、动词、和concepts之间的relationships。避开不明确的词例如system。
  • using UML (Unified Modeling Language) class diagrams as informal notation

  • glossary

    • Identify and define key concepts. Ensure shared understanding between developers and customers.
    • 例如: “Library Item: Any item that is indexed and can be borrowed from library.” 这句话对于可能有歧义的concepts给出了明确定义。
  • system sequence diagram: a model that shows, for one usage scenario, sequence of events that occur on the system’s boundary.

  • system behavioral contracts

OO Design: Defining a solution

  • object interaction diagrams
  • object model

Domain Model长这样

  • 空心菱形:aggregation 聚合关系,例如:班级 ◇--- 学生(学生可以存在于班级之外)
  • 实心菱形:composition 组合关系,例如:人 ♦--- 心脏(心脏不能离开人体独立存在)
  • 三角形:inheritance/generalization 继承/泛化关系,例如:狗 ---△ 动物(狗继承自动物)

UML Sequence Diagram 长这样

Behavioural Contract 长这样

完成了Domain Model, System Sequence Diagram 和 Behavioural Contract 之后,就是从Problem Space到Solution Space的转换。希望能low representational gap

Lec 4. Responsibility Assignment

Problem Space (Domain model) —> Solution Space (Object model)

Representational gap

Design Principle

  • Low representational gap

    Domain concepts provide inspiration for software classes.

    Classes for domain concepts intuitive to understand, rarely change.

    为什么要low representational gap? 你可以建立一个class LibrarySystem然后把所有东西放在单个巨大的class里,但是这样不好做后续修改(我们需要 design for change

    Benefits

    • facilitates understanding of design and implementation
    • facilitates traceability from problem to solution
    • facilitates evolution (design for change)
  • Low coupling

    A model should depend on as few other modules as possible

    一个module要和尽量少的module之间有依赖关系

    Benefits

    • Enhances understanability

    • Reduce the cost of change (如果每个module最多只和另外两个module有关系,那么改变module时最多只需要修改两个module,不需要牵一发而动全身)

    • Enhances reuse (fewer dependencies, easier to adapt to a new context)

    A related design heuristic: law of demeter: each module should have only limited knowledge about other units

    a.getB().getC().foo is a bad practice !!! This means you are not distributing knowledge correctly !!!

    Prefer coupling to interfaces over coupling to implementations (interface相比implementation改变得更少)

  • High cohesion (or single-responsibility principle)

    Each component should have a small set of closely-related responsibilities

    每个component(每个class/object)只负责较少的职责

    Benefits:

    • facilitates understandability
    • facilitates reuse
    • eases maintenance

Coupling vs Cohesion

把所有代码写在一个class里:very low coupling, but very low cohesion.

把每个模块都分开来:very high cohesion, but very high coupling.

Find a good tradeoff!

Lec 5. Inheritance and Delegation

Java中class的继承关系,所有class都继承自 class Object

Java编译期判断which class to look in, method signature to be executed,运行时判断class的动态类型,对于动态class判断到底执行哪个method。

JavaScript运行时解析methods。

  • Inheritance vs Subtyping

    Inheritance: class A extends B

    Subtyping: class A implements B, class A extends B

Lec 6. Design Patterns

“Each pattern describes a problem which occurs over and over again in our environment, and then describes the core of the solution to that problem, in such a way that you can use this solution a million times over, without ever doing it the same way twice.”

Design pattern是针对软件开发中反复出现的问题,总结出可复用、灵活解决方案的一种经验方法

Strategy Pattern

Problem: Clients need different variants of an algorithm

Solution: Create an interface for the algorithm, with an implementing class for each variant of the algorithm

Consequences

  • Easily extensible for new algorithm implementations.
  • Separates algorithm from client context
  • Introduces an extra interface and many classes: (1) code can be harder to understand, (2) lots of overhead if the strategies are simple.

Template Method Design Pattern

  • Applicability

    • When an algorithm consists of varying and invariant parts that must be customized

    • When common behavior in subclasses should be factored and localized to avoid code duplication

    • To control subclass extensions to specific operations

  • Consequences

    • Code reuse

    • Inverted “Hollywood” control: don’t call us, we’ll call you

    • Ensures the invariant parts of the algorithm are not changed by subclasses

Abstract class 抽象类,指一个class有些方法implement了有些方法没有implement

Template Method vs Strategy Pattern

  • Template method uses inheritance to vary part of an algorithm
  • Strategy pattern uses delegation to vary the entire algorithm

Inheritance vs. Composition + Delegation

  • Inheritance can enable substantial reuse when strong coupling is reasonable

    • Sometimes a natural fit for reuse – look for “is-a” relationships.
    • Does not mean “no delegation”
  • That said, good design typically favors composition + delegation

    • Enables reuse, encapsulation by programming against interfaces

    • Delegation supports information hiding; inheritance violates it

    • Usually results in more testable code.

    • Composition facilitates adding multiple behaviors, much less messily than multiple inheritance.

Composite Design Pattern

  • Applicability

    • You want to represent part-whole hierarchies of objects

    • You want to be able to ignore the difference between compositions of objects and individual objects

  • Consequences

    • Makes the client simple, since it can treat objects and composites uniformly

    • Makes it easy to add new kinds of components

    • Can make the design overly general

      • Operations may not make sense on every class

      • Composites may contain only certain components

Module Pattern

Hide internals in closure

Lec 7. Design Practice

One more pattern called decorator pattern.

Decorator Pattern

Inheritance的局限性:

e.g. 需要写一个Stack,有UndoStack, SecureStack / LockedStack(需要密码才能读stack), SynchronizedStack (concurrent-safe)

还要能将上面这些结合起来,有SecureUndoStack, SynchronizedUndoStack, SecureSynchronizedStack等等 (arbritrarily composable extensions)

Decorator Pattern: add functionality at runtime

Decorator Pattern is good if you want to arbitrarily combine/add features to a class.

以下是八股

Problem: Responsibilities should be added to an object dynamically at runtime.

Solution: Defines a Decorator object that implements the interface of an extended object, optionally performing additional functionality before/after forwarding the request.

  • Applicability
    • add responsibilities to individual objects dynamically and transparently
    • for responsibilities that can be withdrawn
    • when extension by subclassing is impractical
  • Consequences
    • more flexible than static inheritance
    • avoids large classes in the hierarchy
    • lots of little objects

[Lecture Notes] CMU 17-514 Software Construction
https://www.billhu.us/2025/057_cmu_17514/
Author
Bill Hu
Posted on
January 16, 2025
Licensed under