MIT_6.031之抽象函数与表示不变量

抽象函数与表示不变量

上一章的重要概念

表示独立性（Representation Independence，RI）

• 客户在使用抽象数据类型（ADT）时无需关心其内部实现，只需依据ADT的规约进行使用。
• 关键在于将数据结构的使用和数据结构自身的形式分离，防止用户假设ADT的内部实现，从而形成依赖。

本章涉及的概念

不变量（Invariants）

• 指在ADT创建后不会改变的量，始终为True，且不受外部使用者操作的影响。
• 如果ADT的不变量发生改变，则说明ADT出现了变异，可能在程序运行的某个地方存在bug。

表示暴露（Representation Exposure）

• 指类外部代码可以直接修改类内部存储的数据，从而影响不变量及表示独立性。

抽象函数（Abstraction Functions）& 表示不变量（Representation Invariants）

表示空间与抽象空间

• 表示空间R：开发人员实现时使用的内部值。

表示空间 RRR 是开发人员在实现和处理数据时使用的内部表示。这个空间包含了系统如何存储、计算和操作数据的所有细节，包括：

• 数据结构：例如，数组、链表、树等。这些结构决定了数据在内存中的组织方式。
• 数据类型：如整数、浮点数、字符等，这些类型定义了数据的特性和操作方式。
• 编码方式：包括二进制编码、字符编码（如 UTF-8、ASCII）等，影响数据在存储和传输过程中的格式。
• 性能优化：开发人员在表示空间中可能会做出许多优化决定，例如选择使用何种算法、数据压缩、内存管理等，以提高系统的效率和性能。

在表示空间中，开发人员需要处理所有这些细节，以确保系统能够有效运行。这些细节通常是透明的，用户并不直接看到或理解这些内部实现。

• 抽象空间A：用户看到和使用的值。

抽象空间 AAA 是用户直接交互和使用的界面及数据。这个空间关注的是用户体验，包括：

• 用户界面：设计和布局、按钮、菜单等元素，如何呈现给用户并允许他们进行操作。
• 功能性：用户需要的功能和服务，例如数据输入、输出、处理和展示的方式。
• 用户体验：系统如何满足用户的需求、使用的简便性、响应速度和整体满意度。
• 抽象和简化：开发人员通常会在这个层面上隐藏复杂性，让用户不需要关心底层的实现细节，而只需关注他们要完成的任务。

• 开发人员更关注表示空间R，而用户则更关注抽象空间A。

开发者关注的重点：

• 性能和效率：在表示空间中，开发者会关注算法的复杂度、内存的使用、数据处理的速度等，以确保系统高效运行。
• 安全性和稳定性：开发者需要确保数据的完整性和安全性，防止潜在的漏洞和攻击。

用户关注的重点：

• 易用性：用户希望界面简洁明了，操作直观，能够迅速上手。
• 可访问性：确保所有用户（包括有特殊需求的用户）都能方便地使用系统。
• 可靠性：用户希望系统在使用过程中能够稳定工作，不出现崩溃或错误。

二者的关系

在软件开发中，表示空间和抽象空间之间的关系至关重要。开发者在设计时需要考虑如何在不牺牲性能和效率的前提下，为用户提供良好的体验。因此，良好的设计往往需要在表示空间和抽象空间之间找到平衡点。

• 举例
  • 一个复杂的图形处理软件可能在内部使用复杂的数据结构和算法（表示空间）来实现高效的图像渲染，但对用户来说，它只需要一个简单的界面来选择和编辑图像（抽象空间）。
  • 一个数据库管理系统可能在内部使用复杂的索引和查询优化算法（表示空间），但用户只需使用简单的查询语言（如 SQL）与数据库交互（抽象空间）。

抽象函数（AF）

• 用于将表示空间中的一个值解释为抽象空间中的一个值。
• AF是一个满射，即用户看到的任意值都由一个表示值映射而来。
• AF不一定是单射，可能有多个表示值映射到同一个抽象值。
• AF也不一定是双射，即可能存在不满足前置条件的表示值，这类值没有对应的抽象值。

1. 抽象函数的定义

抽象函数 $ $ 是一个数学概念，用于将表示空间中的值映射到抽象空间中的值。它定义了如何将内部表示（开发人员使用的值）转换为用户可以理解和操作的外部表示。具体来说，抽象函数有以下几个特性：

• 映射关系：对于每个表示空间中的值 $ r R $，都有一个对应的抽象空间中的值 $ a A $，即 $ (r) = a $。这个映射关系使得用户可以通过抽象值与系统进行交互。

2. 满射（Surjective）

• 定义：抽象函数 $ $ 是一个满射，意味着在抽象空间 $ A $ 中的每个值都至少有一个表示空间 $ R $ 中的值与之对应。换句话说，对于任意的 $ a A $，都存在至少一个 $ r R $ 使得 $ (r) = a $。
• 意义：这种特性保证了用户在使用系统时能接触到所有可能的抽象值，而这些抽象值都可以追溯到具体的内部表示。这对于用户来说是至关重要的，因为它确保了用户能够利用系统的全部功能。

3. 非单射（Not Injective）

• 定义：抽象函数 $ $ 不是单射，意味着可能存在多个不同的表示空间值 $ r_1, r_2 R $ 映射到同一个抽象值 $ a A \(。即，\) (r_1) = a $ 和 $ (r_2) = a $，且 $ r_1 r_2 $。
• 例子：考虑一个数据库系统，两个不同的用户输入了相同的用户名。尽管在表示空间中这两个用户名对应着不同的内部表示，但在抽象空间中，它们都会被视为同一个用户名。这种情况在系统中是常见的，尤其是在需要处理相似或重复数据时。
• 影响：这种非单射的特性有助于简化用户的体验，因为用户可以通过相同的抽象值与系统交互，而不必关心底层的实现差异。

4. 非双射（Not Bijective）

• 定义：抽象函数 $ $ 也不是双射，这意味着不仅存在多个表示值映射到同一个抽象值，还可能存在一些表示值在抽象空间中没有对应的抽象值。即，可能存在 $ r R $ 使得 $ (r) $ 不属于 $ A $。
• 例子：考虑一个情况，在一个电商平台上，用户可以输入商品的评分（如 1-5 分）。但如果评分系统规定评分必须在 1 到 5 的范围内，那么用户输入的评分（如 6）将没有对应的抽象值。因此，尽管内部有这个值的表示，系统并不会将其映射到抽象空间。
• 影响：这种非双射性使得开发人员在设计系统时需要处理输入有效性的问题，以确保用户输入的值能够正确地映射到抽象空间中。若用户输入不合法的值，系统可能需要提供反馈并要求用户重新输入。

5. 抽象函数的设计考量

在设计抽象函数时，开发人员需要考虑以下因素：

• 用户友好性：确保用户可以轻松理解和使用抽象值，设计直观的界面。
• 错误处理：处理不符合前置条件的表示值，提供清晰的错误消息，以指导用户进行正确的输入。
• 性能优化：在内部实现中可能需要优化映射的效率，确保抽象函数的调用不会造成性能瓶颈。

表示不变量（RI）

• 定义了哪些表示值无法被映射到抽象空间。
• RI是一个映射，将表示值空间R中的值映射到布尔值，只有映射为true的值才能映射到抽象空间A中。
• RI构成了表示空间R的一个子集，该子集中的值能够被映射到抽象空间A中。

好的，让我们深入探讨表示不变量（Representation Invariant, RI）的概念以及它在软件开发和系统设计中的作用。

1. 表示不变量的定义

表示不变量 $ $ 是一种约束，它定义了在表示空间 $ R $ 中哪些值是有效的，能够被映射到抽象空间 $ A $ 中。它确保了系统在运行过程中所使用的内部值始终符合一定的条件，以保持数据的一致性和有效性。

2. 映射到布尔值

• 布尔映射：表示不变量是一个函数，将表示空间中的每个值 $ r R $ 映射到一个布尔值（True 或 False）。即： $ (r) { , } $
• 有效性检查：只有当 $ (r) = $ 时，该表示值 $ r $ 才能被映射到抽象空间中的值 $ a $。这意味着 $ r $ 是有效的并且符合预定义的条件。如果 $ (r) = $，则该值不能被映射，通常意味着这个值在逻辑上是不合适的或不合理的。

3. 表示不变量的作用

• 数据完整性：通过定义表示不变量，可以确保在表示空间中的数据始终保持有效状态。无效数据的存在可能会导致系统错误或不可预期的行为，因此 RI 在系统的稳定性和可靠性方面发挥了重要作用。

• 系统安全性：表示不变量可以防止潜在的恶意输入或错误数据导致的安全漏洞。通过强制执行 RI，可以减少系统遭受攻击的风险。

4. 形成有效值的子集

• 有效值的定义：表示不变量的应用形成了表示空间 $ R $ 的一个子集，称为有效值子集（Valid Representation Subset）。该子集中的值是符合所有表示不变量约束的，能够安全地映射到抽象空间 $ A $ 中。即： $ (R) = { r R (r) = } $

• 映射关系：在映射过程中，只有当 $ r (R) $ 时，才能进行映射： $ (r) (r) = $

5. 实际应用中的示例

• 示例一：银行账户：考虑一个银行账户的系统。表示不变量可能包括账户余额不能为负，且账户状态必须是活动状态。只有在这些条件满足时，才能进行交易操作。通过这些 RI，可以防止用户尝试透支或对已关闭账户进行操作。

• 示例二：用户输入：在一个表单提交的场景中，可能会定义表示不变量来确保用户输入的数据格式正确（如电子邮件地址的格式、年龄的合理范围等）。只有当这些条件满足时，输入的数据才能被接受并映射到系统的相应抽象表示。

6. 设计表示不变量的考虑

• 明确性：在设计表示不变量时，必须确保其规则和条件明确，易于理解和实施。模糊的表示不变量可能会导致开发和使用中的困惑。

• 可维护性：表示不变量应便于更新和维护。随着系统需求的变化，表示不变量可能需要调整，因此在设计时应考虑其灵活性。

• 测试覆盖：在开发过程中，需要对表示不变量进行充分的测试，确保所有可能的输入都经过验证，以符合相应的约束。

7. 总结

表示不变量（RI）在系统设计中扮演着至关重要的角色。通过定义有效的映射条件和约束，RI 有助于确保数据的完整性、安全性和一致性。在开发过程中，明确的表示不变量不仅提高了代码的可维护性，还能够在用户交互时提供更好的体验。理解并正确实施表示不变量对于构建健壮和可靠的系统至关重要。

构建ADT的步骤

1. 选定表示空间（R）。
2. 选定其中满足条件的子集（RI）。
3. 为子集中的每个元素做出对应的解释（AF）。
4. 映射到抽象空间（A）。

使用数学思想理解ADT

• 抽象函数使我们能够清晰地定义两个ADT之间的相等性判断。
• 表示不变量使我们更容易发现破坏数据结构的bug。

不变量与设计良好的ADT

• 保护自己的不变量是设计良好ADT的关键。
• 不变量是在程序运行时始终保持的状态。一旦不变类型的对象被创建，它始终表示一个不变的值。
• 当ADT确保其内部的不变量保持恒定不变（不受外部影响）时，称为保护自己的不变量。

不变性示例

public class Tweet {
    private final String author;
    private final String text;
    private final Date timestamp;

    public Tweet(String author, String text, Date timestamp) {
        this.author = author;
        this.text = text;
        this.timestamp = timestamp;
    }

    public String getAuthor() {
        return author;
    }

    public String getText() {
        return text;
    }

    public Date getTimestamp() {
        return timestamp;
    }
}

确保Tweet对象不可变

• 使用private限制访问权限。
• 使用final确保变量不可变。
• 防御性编程，避免暴露可变对象。

示例中的问题

public static Tweet retweetLater(Tweet t) {
    Date d = t.getTimestamp();
    d.setHours(d.getHours() + 1);
    return new Tweet("rbmllr", t.getText(), d);
}

• 以上代码改变了d的时间，进而影响了t的时间，破坏了Tweet的不变性。

解决方案

1. 使用防御性复制：

   public Date getTimestamp() {
       return new Date(timestamp.getTime());
   }

2. 在构造函数中也进行防御性编程：

   public Tweet(String author, String text, Date timestamp) {
       this.author = author;
       this.text = text;
       this.timestamp = new Date(timestamp.getTime());
   }

不可变类型的使用

• 使用不可变的类型如java.time.ZonedDateTime替代java.util.Date。
• 使用Collections.unmodifiableList()包装可变List，提供不可变接口。

抽象函数与表示不变量

• 在研究抽象类型时，思考表示域和抽象域之间的关系。
• 表示域是具体实现的实体，抽象域是设计时支持使用的值。
• 实现者的责任是实现表示域到抽象域的转换（映射）。

CharSet示例

public class CharSet {
    private String s;

    // Rep invariant:
    //   s contains no repeated characters
    // Abstraction function:
    //   AF(s) = {s[i] | 0 <= i < s.length()}
}

其他例子

有理数

public class RatNum {
    private final int numerator;
    private final int denominator;

    // Rep invariant:
    //   denominator > 0
    //   numerator/denominator is in reduced form

    // Abstraction function:
    //   AF(numerator, denominator) = numerator/denominator

    public RatNum(int n) {
        numerator = n;
        denominator = 1;
        checkRep();
    }
}

动态检查不变量

checkRep() 方法
为了在程序运行时捕获潜在的错误，checkRep() 方法被设计用于在每一次创建或改变表示数据后被调用。它通常在以下情况下被调用：

• 创建者（构造函数）
• 生产者（工厂方法）
• 改造者（修改方法）

观察者通常不需要进行这种检查，因为它们不直接改变表示状态。checkRep() 是私有的，开发者有责任确保表示不变量的维护。

// 检查表示不变量是否为真
// *** 警告：除非通过 -enableassertions 否则此代码无效
private void checkRep() {
    assert denominator > 0;
    assert gcd(Math.abs(numerator), denominator) == 1;
}

关于 Null 值的限制
在表示中禁止使用 null 值。前置条件和后置条件中都隐含地不允许出现 null。例如，假设有一个类 CharSet，它的字符串字段 s 默认不能为 null，因此不需要在 RI 注释中专门说明。然而，在实现 checkRep() 时，应该显式检查 s != null，以确保在 s 为 null 时程序能快速失败。

private void checkRep() {
    assert s.length() % 2 == 0;
    assert s != null;  // 显式检查
}

友善改动（Beneficent Mutation）

友善改动指的是对象在创建后，其抽象值保持不变，而实现者可以在内部表示域进行改动。例如，某个类的 toString 方法可能会改变其私有字段的值，但这种改动不影响对象的抽象值。

public class RatNum {
    private int numerator;
    private int denominator;

    // 表示不变量
    //   denominator != 0

    // 抽象函数
    //   AF(numerator, denominator) = numerator/denominator

    @Override
    public String toString() {
        int g = gcd(numerator, denominator);
        numerator /= g;  // 友善改动
        denominator /= g;  // 友善改动
        return (denominator > 1) ? (numerator + "/" + denominator) : (numerator + "");
    }
}

表示的安全性与不变量

在类的设计中，表示不变量、抽象函数以及安全性注释应当明确说明其不变性。以下是一个安全性声明的例子：

// 不变性声明
//   author 是 Twitter 用户名（由字母、数字和下划线组成的非空字符串）
//   text.length <= 140

// 抽象函数
//   AF(author, text, timestamp) = 由 author 发布，内容为 text 的推文，
//                                 在 timestamp 时间发布

规范与表示不变量

抽象数据类型（ADT）的规范应仅关注用户可见的部分，包括参数、返回值和可能抛出的异常。规范中引用的值应为抽象域的值，而非表示域的值。这样做有助于保持实现细节的隐藏，避免不必要的复杂性。

例如，一个 ADT 可以被用来替代前置条件的说明：

/** @return characters that appear in one set but not the other */
static SortedSet<Character> exclusiveOr(SortedSet<Character> set1, SortedSet<Character> set2);

示例：银行账户管理系统

1. 抽象数据类型（ADT）定义

我们将银行账户视为一个抽象数据类型，其核心功能包括存款、取款和查询余额。该银行账户有以下属性：

• 账户号码（Account Number）：唯一标识账户的字符串。
• 账户余额（Balance）：当前账户可用余额，通常是非负数。

2. 表示空间（R）与抽象空间（A）

• 表示空间 $ R $：内部实现的属性和数据结构。
  • 内部表示：
    • accountNumber: 字符串表示的账户号码（如“123-456-789”）。
    • balance: 以浮点数表示的账户余额（如1000.0）。
• 抽象空间 $ A $：用户与之交互的外部接口。
  • 用户可以进行的操作：存款、取款和查询余额。

3. 抽象函数（AF）的定义

抽象函数将表示空间的值映射到抽象空间中。对于一个银行账户，其抽象函数可以定义为：

• 抽象函数 $ \(:\) (account) = $

其中，账户的余额可以通过账户号码查询。

4. 表示不变量（RI）的定义

表示不变量确保账户的状态始终是有效的。对于银行账户，定义如下：

• 表示不变量 $ $:
  • balance 必须为非负数（即 balance >= 0）。
  • accountNumber 必须是有效格式（如“XXX-XXX-XXX”）。

具体的 RI 实现可以用以下布尔表达式表示： $ (account) = (balance ) ((accountNumber)) $

其中，isValidAccountNumber 是一个验证账户号码格式的辅助函数。

5. 系统操作与 RI 检查

在系统中，每当执行存款、取款或查询余额操作时，都需要验证表示不变量。

• 存款操作：

  public void deposit(Account account, double amount) {
      if (amount > 0) {
          account.balance += amount;
      }
      assert RI(account);  // 检查不变量
  }

• 取款操作：

  public void withdraw(Account account, double amount) {
      if (amount > 0 && account.balance >= amount) {
          account.balance -= amount;
      }
      assert RI(account);  // 检查不变量
  }

• 查询余额操作：

  public double getBalance(Account account) {
      assert RI(account);  // 检查不变量
      return account.balance;
  }

6. 不变量的重要性

通过定义并检查表示不变量，可以确保以下几点：

• 数据完整性：不允许账户余额变为负数，从而防止不合逻辑的操作。
• 安全性：只允许格式正确的账户号码被创建和修改，防止错误输入。
• 易用性：通过提供清晰的错误消息（如“余额不足”或“账户号码格式错误”），引导用户进行正确的操作。