Функциональное программирование

Неявные (неожиданные) изменения. Нарушение инвариантов

Потенциально проблемный код:

class Box():
    def __init__(self, value):
        self.value = value
    def __eq__(self, other):
        return self.value == other.value
    def __hash__(self):
        return hash(self.value)
    def update_value(self, value):
        self.value = value

a, b = Box(1), Box(2)
a == a
    # => True
a != b
    # => True
a == Box(1)           # => True

Проблема 1. Эквивалентность и необходимость знания деталей

class Box():
    def __init__(self, value):
        self.value = value
    def __eq__(self, other):
        return self.value == other.value
    def __hash__(self):
        return hash(self.value)
    def update_value(self, value):
        self.value = value

a, b = Box(1), Box(1)
a == b          # => True
dict = {}
dict[a] = 'a'
dict[b] = 'b'
dict
# => { <__main__.Box object at 0x101046f50>: 'a',
    #      <__main__.Box object at 0x100ea0ad0>: 'b' }

a, b = 1, 1
a == b          # => True
dict = {}
dict[a] = 'a'
dict[b] = 'b'
dict
# => {1: 'b'}

Проблема 2. Утиная типизация и коммутативность

class Box():
    def __init__(self, value):
        self.value = value
    def __eq__(self, other):
        return self.value == other.value
    def __hash__(self):
        return hash(id(self))
    def update_value(self, value):
        self.value = value

class DoubleBox():
    def __init__(self, value1, value2):
        self.value = value1
        self.second_value = value2
    def __eq__(self, other):
        if type(self) == type(other):
return self.value == other.value \
    and self.second_value == other.second_value
        return False

Box(1) == DoubleBox(1, 2)     # => True
DoubleBox(1, 2) != Box(1)     # => True

Проблема 3. Нарушение внешнего инварианта (dict)

class Box():
    def __init__(self, value):
        self.value = value
    def __eq__(self, other):
        return self.value == other.value
    def __hash__(self):
        return hash(self.value)
    def update_value(self, value):
        self.value = value

dict = {}
a, b = Box(1), Box(2)
dict[a] = 'a'
dict[b] = 'b'
a.update_value(10)
a in dict # => False
b in dict # => True
a         # => <__main__.Box object at 0x101047790>
b         # => <__main__.Box object at 0x101047dd0>
dict  # => {
      # <__main__.Box object at 0x101047790>: 'a',
      # <__main__.Box object at 0x101047dd0>: 'b'
      # }

Кэширование

class Cart {
    private Customer customer;
    private List<Product> products;
    private int totalPrice = -1;

    private int computeTotalPrice() { ... } // hard to compute function
    public int getTotalPrice() {
        if(totalPrice == -1)
totalPrice = computeTotalPrice();
        return totalPrice;
    }
    public void addProduct(Product p) {
        products.add(p);
        totalPrice = -1;
    }
    public void removeProduct(Product p) {
        products.remove(p);
        totalPrice = -1;
    }
}
class Product {
    public void setPrice(int price) { ... }
}

Является ли totalPrice корректно кешируемым значением?

Нет, не является.

Сценарий:

1. Пользователь собрал корзину.
2. Магазин обновил цены на продукты.
3. Пользователь заглянул в свою корзину.
4. Пользователь видит, что totalPrice не равен сумме стоимостей товаров.

Пути решения проблемы:

• отказ от кэширования
• класс Product подписывается на изменения цены
• корзина фиксирует стоимость товара для данного пользователя.

Многопоточность

class BankAccount {
    void deposit(int amount) {
setMoney(getMoney() + amount);
    }
    void withdraw(int amount) {
        if(amount > getMoney()) throw new InsufficientMoneyException();
        setMoney(getMoney() - amount);
    }
}

Мария и Иван кладут на счёт по 25 и 50 рублей соответственно:

| Действия Марьи      | Действия Ивана      | Деньги на счете |
|:--------------------|:--------------------|:----------------|
| deposit(50)         | deposit(25)         | 100
 |
| getMoney() -> 100   |
         | 100             |
|
         | getMoney() -> 100   | 100             |
| setMoney(100+50)    |
         | 150             |
|
         | setMoney(100+25)    | 125             |

Вопрос: У банка три дата-центра. Как добиться защиты от brain split?

Сложный код

Вставка в двусвязный список. Можете проверить корректность реализации без листа бумаги и ручки?

public void add(int index, Object o) {
    Entry e = new Entry(o);
    if (index < size) {
        Entry after = getEntry(index);
        e.next = after;
        e.previous = after.previous;
        if (after.previous == null)
first = e;
        else
after.previous.next = e;
        after.previous = e;
    } else if (size == 0) {
        first = last = e;
    } else {
        e.previous = last;
        last.next = e;
        last = e;
    }
    size++;
}

1. Отсутствие изменяемого состояния

• Существует в теории (процессора используют регистры, память).
• Абсолютно безопасен.

2. Невидимое программисту изменяемое состояние

• Алгоритм не использует изменяемых состояний.
• Машинный код, сгенерированный компилятором, использует изменяемые регистры, стек, память.
• Безопасен, если нет инструментальных ошибок.

3. Невидимое клиенту изменяемое состояние

• Клиент — другой программист, использующий функцию/алгоритм.
• Изменяемая локальная переменная в функции (к примеру счётчик).
• Безопасен с точки зрения клиента.

4. Монотонное изменяемое состояние

• Переменные присваиваются не более 1 раза: не определена, а затем определена.
• Часто контролируется инструментарием.
• Довольно безопасно, т.к. всего 2 состояния:
  • лишь одно не целостно;
  • целостное состояние испортить нельзя.

5. Двухфазный цикл жизни (вариация п. 4)

• Жизнь объекта поделена на две фазы:
  • инициализация (запись);
  • мирная жизнь (использование).
• Необходимо гарантировать, что во время фазы чтения не будет производиться запись, и наоборот.
• Довольно безопастно при соблюдении гарантий.

6. Управляемое изменяемое состояние

• В системе присутствуют специальные средства для координации работы с состоянием.
• Пример: СУБД, транзакции, Software Transaction Memory, Actor.

7. Инкапсулированное изменяемое состояние

• Доступ производится из одного места (private поля).
• Контроль целостности лежит на реализации объекта.
• Ключевая проблема: контроль инвариантов, охватывающих несколько объектов (см. пример с dict).

8. Неинкапсулированное изменяемое состояние (глобальные переменные)

• Всем известно, что это — страшное зло.
• Не изменяет ли ее кто-нибудь прямо сейчас?
  • Вот в этой строчке?
  • Между вот этими двумя строками кода?

9. Разделяемое между несколькими процессами изменяемое состояние

• Ад во всех случаях, кроме тривиальных.
• $N$ потоков, $K$ состояний у каждого. Количество возможных последовательностей событий порядка $K^N$.
• Избегать любой ценой. Добавлять механизмы управления.

Осознайте и одумайтесь

Меньше состояний $\rightarrow$ меньше мест для ошибки.

• Действительно ли предметная область требует изменяемого состояния?
  • Нужны ли банковским системам изменяемые данные?
• Может применимы чисто функциональные структуры данных?
  • Вам точно нужен изменяемые словари?
  • Вам точно нужны изменяемые строки?
• Корректно ли выделено изменяемое состояние?
  • Это одно изменяемое состояние или группа связанных изменяемых состояний?

Инкапсуляция

Меньше кода вносит изменения $\rightarrow$ легче его поддерживать.

Сперва посчитать $\rightarrow$ потом внести изменения.

• Не возвращайте изменяемые объекты из "читающих" методов. Если невозможно — верните копию.
  • Вам точно нужно вернуть изменяемое значение Calendar вместо UNIX-time?
• Не возвращайте массивы/словари — возвращайте неизменяемые коллекции (tuple, а не list).
  • Особенно если они продолжают использоваться внутри.
• Предоставляйте интерфейс для изменения, соответствующий предметной области.
  • Инкапсулируйте координацию изменений.
  • Не getMoney/setMoney, а deposit/withdraw.

Двухфазный цикл жизни

1. Запись. Накопить информацию или проинициализировать объект.
2. Чтение. Объект для клиента неизменяем.

public interface WriteFacet {
  void addQux(Qux qux);
  void setBaz(Baz baz);
  ReadFacet freeze();
}
public interface ReadFacet {
  Foo getFoo(int fooId);
  Bar getBar();
}

class Item implements WriteFacet {
  ...
  ReadFacet freeze() {
      ...
      return new FrozenItem(myData);
  }
}
class FrozenItem
  implements ReadFacet {
  ...
}

class Item {
  private boolean isFrozen = false;
  ...
  void addQux(Qux qux) {
    if (isFrozen)
      throw new IllegalStateException();
    ...
  }

  Foo getFoo(int fooId) {
    if (!isFrozen)
      throw new IllegalStateException();
   ...
  }

  void freeze() {
    ...
    isFrozen = true;
  }
}

Единовременная инициализация вместо настройки

Последовательность действий при инициализации:

class Database {
    void setLogin(String login);
    void setPassword(String password);
    Connection connect() throws InvalidCredentialsException;
}

Атомарная инициализация:

class Database {
    Connection connect(String login, String password)
        throws InvalidCredentialsException;
}

Концентрация изменений во времени

• Избавление от промежуточных состояний между изменениями.
• Избавление от протокола последовательных изменений.

interface RuleEngine {
    void addRule(String varName, String formula)
        throws ParseException, UndefinedVariableException;

    double computeValue(String varName);
}
// Rule 1: a = b - 1
// Rule 2: b = a - 1

Как быть, если в правилах есть циклические зависимости?

interface RuleParser {
    RuleSet parseRules(Map<String,String> var2formula)
        throws ParseException, CircularDependencyException;
}
interface RuleSet {
    double computeValue(String varName);
}

Зависимость правил — проблема сервиса, а не клиента.

Концентрация изменений в пространстве объектов

Минимизировать количество объектов, охватываемых инвариантами.

class Artifact {
  Player getOwner();
  void setOwner(Player player);
  int getStrengthBoost();
  // ... other boosts
}
class Player {
  List<Artifact> getArtifacts();

  void addArtifact(Artifact a);
  void dropArtifact(Artifact a);
  void passArtifact(Artifact a,
        Player toWhom);
}

class Artifact {
  getStrengthBoost(Player player)
}
// or
class Player {
  int getStrengthBoost(
    List<Artifact> a)
}
// or
class ArtifactRules {
    getStrengthBoost(
      Artifact a, Player p)
}

Многопоточные техники

1. Использование критических секций для синхронизации.
2. Использование атомарных операций (compare-and-swap).
3. Локализация изменяемого состояния.
   • Заменить несколько изменений глобального состояния на вычисление большого изменения и его атомарное применение.
   • Инкапсуляция изменяемого состояния в акторе.
4. Навязывание эквивалентности трасс:
   • Идемпотентность: Операция, будучи выполненной несколько раз, имеет тот же эффект.
   • Коммутативность: Порядок операций различного типа не имеет значения.
   • Пример: пользователь много раз нажал buy и сделал много одинаковых заказов. Вариант решения: счётчик шагов взаимодействия.