Как абстракции помогают нам управлять сложностью программного обеспечения

Примечание. Это часть серии s (теперь книга!) Программное обеспечение для создания композиций, посвященной изучению функционального программирования и методов композиционного программного обеспечения на JavaScriptES6 + с нуля. Будьте на связи. Впереди еще много всего!
Купить книгу | Индекс | ‹ Предыдущая | "Следующий >"

Абстрактные типы данных

Не путать с:

Алгебраические типы данных (иногда сокращенно ADT или AlgDT). Алгебраические типы данных относятся к сложным типам в языках программирования (например, Rust, Haskell, F #), которые отображают некоторые свойства определенных алгебраических структур. например, типы сумм и типы продуктов.

Алгебраические структуры. Алгебраические структуры изучаются и применяются из абстрактной алгебры, которая, как и ADT, также обычно определяется в терминах алгебраических описаний аксиом, но применима далеко за пределами мира компьютеров и кода. Может существовать алгебраическая структура, которую невозможно полностью смоделировать в программном обеспечении. Напротив, абстрактные типы данных служат в качестве спецификации и руководства для формальной проверки работоспособности программного обеспечения.

Абстрактный тип данных (ADT) - это абстрактное понятие, определяемое аксиомами, которые представляют некоторые данные и операции с этими данными. ADT не определены в терминах конкретных экземпляров и не определяют конкретные типы данных, структуры или алгоритмы, используемые в реализациях. Вместо этого ADT определяют типы данных только в терминах своих операций и аксиом, которым эти операции должны придерживаться.

Общие примеры ADT

  • Список
  • Куча
  • Очередь
  • Установленный
  • карта
  • Транслировать

ADT могут представлять любой набор операций с любыми типами данных. Другими словами, исчерпывающий список всех возможных ADT бесконечен по той же причине, что и исчерпывающий список всех возможных английских предложений бесконечен. ADT - это абстрактная концепция набора операций с неопределенными данными, а не конкретный набор конкретных типов данных. Распространенное заблуждение состоит в том, что конкретные примеры ADT, преподаваемые во многих университетских курсах и учебниках по структуре данных, и есть ADT. Многие такие тексты маркируют структуры данных «ADT», а затем пропускают ADT и вместо этого описывают структуры данных в конкретных терминах, никогда не подвергая учащегося фактическому абстрактному представлению типа данных. Ой!

ADT могут выражать множество полезных алгебраических структур, включая полугруппы, моноиды, функторы, монады и т. Д. Спецификация Fantasyland - полезный каталог алгебраических структур, описываемых ADT для поощрения совместимых реализаций в JavaScript. Создатели библиотек могут проверить свои реализации, используя предоставленные аксиомы.

Почему ADT?

Абстрактные типы данных полезны, потому что они позволяют нам формально определять повторно используемые модули математически правильным, точным и однозначным образом. Это позволяет нам использовать общий язык для обозначения обширного словаря полезных строительных блоков программного обеспечения: идей, которые полезно изучать и носить с собой при перемещении между доменами, фреймворками и даже языками программирования.

История ADT

В 1960-х и начале 1970-х годов кризис программного обеспечения интересовал многих программистов и исследователей информатики. Как сказал Эдсгер Дейкстра в своей лекции о премии Тьюринга:

«Основная причина программного кризиса в том, что машины стали на несколько порядков мощнее! Проще говоря: пока не было машин, программирование не было проблемой; когда у нас было несколько слабых компьютеров, программирование превратилось в небольшую проблему, а теперь у нас есть гигантские компьютеры, программирование стало столь же гигантской проблемой ».

Проблема, о которой он говорит, заключается в том, что программное обеспечение очень сложное. Печатная версия лунного модуля и системы наведения «Аполлон» для НАСА размером с картотечный шкаф. Это много кода. Представьте, что вы пытаетесь прочитать и понять каждую строчку из этого.

Современное программное обеспечение на порядки сложнее. В 2015 году у Facebook было примерно 62 миллиона строк кода. Если вы напечатали 50 строк на странице, вы заполнили бы 1,24 миллиона страниц. Если вы сложите эти страницы, вы получите около 1800 страниц на фут, или 688 футов. Это выше, чем Башня Миллениум в Сан-Франциско, самое высокое жилое здание в Сан-Франциско на момент написания этой статьи.

Управление сложностью программного обеспечения - одна из основных задач, с которыми сталкивается практически каждый разработчик программного обеспечения. В 1960-х и 1970-х годах у них не было языков, шаблонов или инструментов, которые мы сегодня принимаем как должное. Такие вещи, как линтеры, intellisense и даже инструменты статического анализа еще не были изобретены.

Многие инженеры-программисты отмечали, что оборудование, на котором они строили вещи, в основном работало. Но программное обеспечение чаще всего было сложным, запутанным и непрочным. Программное обеспечение обычно было:

  • Сверх бюджета
  • Поздно
  • Багги
  • Отсутствующие требования
  • Трудно поддерживать

Если бы вы только могли думать о программном обеспечении в виде модульных частей, вам не нужно было бы понимать всю систему, чтобы понять, как заставить работать часть системы. Этот принцип разработки программного обеспечения известен как локальность. Чтобы получить локальность, вам нужны модули, которые вы можете понимать отдельно от остальной системы. Вы должны иметь возможность однозначно описать модуль, не уточняя его реализацию. Это проблема, которую решают ADT.

Начиная с 1960-х годов почти до наших дней, развитие модульности программного обеспечения было основной задачей. Помня об этих проблемах, люди, в том числе Барбара Лисков (тот же Лисков, на который ссылается принцип замены Лискова из принципов проектирования SOLID OO), Алан Кей, Бертран Мейер и другие легенды информатики работали над описанием и указанием различных инструментов, позволяющих модульное программное обеспечение, включая ADT, объектно-ориентированное программирование и проектирование по контракту соответственно.

ADT возникли в результате работы Лисков и ее студентов над языком программирования CLU в период с 1974 по 1975 годы. Они внесли значительный вклад в современное состояние спецификации программных модулей - языка, который мы используем для описания интерфейсов, которые позволяют программным модулям взаимодействовать. . Формально доказуемое соответствие интерфейса значительно приближает нас к модульности и функциональной совместимости программного обеспечения.

Лисков была награждена премией Тьюринга за свою работу по абстракции данных, отказоустойчивости и распределенным вычислениям в 2008 году. ADT сыграли значительную роль в этом достижении, и сегодня практически каждый университетский курс информатики включает ADT в учебную программу.

Кризис программного обеспечения так и не был разрешен полностью, и многие из описанных выше проблем должны быть знакомы любому профессиональному разработчику, но изучение использования таких инструментов, как объекты, модули и ADT, безусловно, помогает.

Технические характеристики ADT

Для оценки соответствия спецификации ADT можно использовать несколько критериев. Я называю эти критерии ИЗВЕСТНОСТЬЮ, но я только придумал мнемонику. Оригинальные критерии были опубликованы Лисковым и Зиллесом в их знаменитой статье 1975 года Методы спецификации для абстракции данных.

  • Официально. Технические характеристики должны быть формальными. Значение каждого элемента в спецификации должно быть определено достаточно подробно, чтобы целевая аудитория имела достаточно хорошие шансы построить совместимую реализацию на основе спецификации. Должна существовать возможность реализовать алгебраическое доказательство в коде для каждой аксиомы в спецификации.
  • Применимо. ADT должны иметь широкое применение. ADT, как правило, следует использовать повторно для множества различных конкретных случаев использования. ADT, который описывает конкретную реализацию на определенном языке в определенной части кода, вероятно, чрезмерно определяет вещи. Вместо этого ADT лучше всего подходят для описания поведения общих структур данных, компонентов библиотеки, модулей, функций языка программирования и т. Д. Например, ADT, описывающего операции со стеком, или ADT, описывающего поведение обещания.
  • Минимум. Спецификации ADT должны быть минимальными. Спецификация должна включать интересные и широко применимые части поведения и ничего более. Каждое поведение следует описывать точно и недвусмысленно, но с как можно меньшими конкретными или конкретными деталями. Большинство спецификаций ADT должно быть доказано с помощью нескольких аксиом.
  • Расширяемый. ADT должны быть расширяемыми. Небольшое изменение требования должно привести лишь к небольшому изменению спецификации.
  • Декларативная. Декларативные спецификации описывают что не как. ADT следует описывать в терминах того, что есть вещи, и сопоставления отношений между входами и выходами, не шаги по созданию структур данных или конкретные шаги, которые должна выполнять каждая операция.

Хороший ADT должен включать:

  • Описание, удобочитаемое человеком. ADT могут быть довольно краткими, если они не сопровождаются каким-либо понятным для человека описанием. Описание на естественном языке в сочетании с алгебраическими определениями может служить проверкой друг друга, чтобы прояснить любые ошибки в спецификации или двусмысленность в понимании ее читателем.
  • Определения. Четко определите все термины, используемые в спецификации, чтобы избежать двусмысленности.
  • Абстрактные подписи. Опишите ожидаемые входные и выходные данные, не связывая их с конкретными типами или структурами данных.
  • Аксиомы. Алгебраические определения инвариантов аксиом, используемые для доказательства того, что реализация удовлетворяет требованиям спецификации.

Пример стека ADT

Стек - это стопка элементов «последним вошел - первым ушел» (LIFO), которая позволяет пользователям взаимодействовать со стеком, помещая новый элемент в верхнюю часть стека или выталкивая последний отправленный элемент из верхней части стека.

Стеки обычно используются в алгоритмах синтаксического анализа, сортировки и сопоставления данных.

Определения

  • a: любой тип
  • b: любой тип
  • item: любой тип
  • stack(): пустой стек
  • stack(a): стопка из a
  • [item, stack]: пара item и stack

Абстрактные подписи

Строительство

Операция stack принимает любое количество элементов и возвращает стопку этих элементов. Обычно абстрактная сигнатура конструктора определяется в терминах самой себя. Не путайте это с рекурсивной функцией.

  • stack(...items) => stack(...items)

Операции со стеком (операции, возвращающие стек)

  • push(item, stack()) => stack(item)
  • pop(stack) => [item, stack]

Аксиомы

Аксиомы стека имеют дело в первую очередь с идентичностью стека и элемента, последовательностью элементов стека и поведением pop, когда стек пуст.

Личность

Нажатие и хлопанье не имеют побочных эффектов. Если вы нажимаете в стек и сразу выскакиваете из этого же стека, стек должен быть в том состоянии, в котором он был до того, как вы нажали.

pop(push(a, stack())) = [a, stack()]
  • Дано: поместить a в стек и сразу выскочить из стека
  • Следует: вернуть пару a и stack().

Последовательность

При извлечении из стека должна соблюдаться последовательность: последний пришел - первый ушел (LIFO).

pop(push(b, push(a, stack())) = [b, stack(a)]
  • Дано: поместить a в стек, затем поместить b в стек, затем вытолкнуть из стека
  • Следует: вернуть пару b и stack(a).

Пустой

Выталкивание из пустого стека приводит к неопределенному значению элемента. Конкретно это можно определить с помощью «Может быть» (элемент), «Ничего» или «Либо». В JavaScript обычно используется undefined. Извлечение из пустого стека не должно изменять стек.

pop(stack()) = [undefined, stack()]
  • Дано: выскакивать из пустого стека
  • Следует: вернуть пару неопределенных и stack().

Конкретные реализации

Абстрактный тип данных может иметь множество конкретных реализаций на разных языках, в библиотеках, фреймворках и т. Д. Вот одна из реализаций вышеуказанного ADT стека, использующая инкапсулированный объект и чистые функции над этим объектом:

const stack = (...items) => ({
  push: item => stack(...items, item),
  pop: () => {
    // create a item list
    const newItems = [...items];
    // remove the last item from the list and
    // assign it to a variable
    const [item] = newItems.splice(-1);
    // return the pair
    return [item, stack(...newItems)];
  },
  // So we can compare stacks in our assert function
  toString: () => `stack(${ items.join(',') })`
});
const push = (item, stack) => stack.push(item);
const pop = stack => stack.pop();

И еще один, который реализует операции со стеком в терминах чистых функций над существующим Array типом JavaScript:

const stack = (...elements) => [...elements];
const push = (a, stack) => stack.concat([a]);
const pop = stack => {
  const newStack = stack.slice(0);
  const item = newStack.pop();
  return [item, newStack];
};

Обе версии удовлетворяют следующим доказательствам аксиом:

// A simple assert function which will display the results
// of the axiom tests, or throw a descriptive error if an
// implementation fails to satisfy an axiom.
const assert = ({given, should, actual, expected}) => {
  const stringify = value => Array.isArray(value) ?
    `[${ value.map(stringify).join(',') }]` :
    `${ value }`;

  const actualString = stringify(actual);
  const expectedString = stringify(expected);

  if (actualString === expectedString) {
    console.log(`OK:
      given: ${ given }
      should: ${ should }
      actual: ${ actualString }
      expected: ${ expectedString }
    `);
  } else {
    throw new Error(`NOT OK:
      given ${ given }
      should ${ should }
      actual: ${ actualString }
      expected: ${ expectedString }
    `);
  }
};
// Concrete values to pass to the functions:
const a = 'a';
const b = 'b';
// Proofs
assert({
  given: 'push `a` to the stack and immediately pop from the stack',
  should: 'return a pair of `a` and `stack()`',
  actual: pop(push(a, stack())),
  expected: [a, stack()]
})
assert({
  given: 'push `a` to the stack, then push `b` to the stack, then pop from the stack',
  should: 'return a pair of `b` and `stack(a)`.',
  actual: pop(push(b, push(a, stack()))),
  expected: [b, stack(a)]
});
assert({
  given: 'pop from an empty stack',
  should: 'return a pair of undefined, stack()',
  actual: pop(stack()),
  expected: [undefined, stack()]
});

Заключение

  • Абстрактный тип данных (ADT) - это абстрактное понятие, определяемое аксиомами, которые представляют некоторые данные и операции с этими данными.
  • Абстрактные типы данных сосредоточены на том, что, а не на том, как (они сформулированы декларативно и не определяют алгоритмы или структуры данных).
  • Распространенные примеры включают списки, стопки, наборы и т. д.
  • ADT позволяют нам формально определять повторно используемые модули математически обоснованным, точным и недвусмысленным образом.
  • ADT возникли в результате работы Лискова и студентов, изучавших язык программирования CLU в 1970-х годах.
  • ADT должны быть ИЗВЕСТНЫ. Официальные, широко применимые, минимальные, расширяемые и декларативные.
  • ADT должны включать удобочитаемое описание, определения, абстрактные подписи и формально проверяемые аксиомы.

Дополнительный совет. Если вы не уверены, следует ли вам инкапсулировать функцию, спросите себя, должны ли вы включить ее в ADT для своего компонента. Помните, что ADT должны быть минимальными, поэтому, если они несущественны, не связаны с другими операциями или их спецификация может измениться, инкапсулируйте их.

Глоссарий

  • Аксиомы - это математически обоснованные утверждения, которые должны выполняться.
  • Математически обоснованный означает, что каждый термин четко определен математически, что позволяет создавать на их основе однозначные и доказуемые утверждения о фактах.

Следующие шаги

EricElliottJS.com предлагает многочасовые видеоуроки и интерактивные упражнения на подобные темы. Если вам нравится этот контент, подумайте о том, чтобы присоединиться.

Эрик Эллиотт - консультант по техническим продуктам и платформе, автор Composing Software, соучредитель EricElliottJS.com и DevAnywhere.io и наставник команды разработчиков. Он участвовал в разработке программного обеспечения для Adobe Systems, Zumba Fitness, The Wall Street Journal, ESPN, BBC, и ведущие музыканты, в том числе Ашер, Фрэнк Оушен, Metallica и многие другие.

Он ведет уединенный образ жизни с самой красивой женщиной в мире.