Моей жене Диане за ее безграничное терпение.

Предисловие

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

Мне всегда нравилось искать способы написания более совершенного кода, но собственно начало этой книги, мне кажется, было заложено в 2015 году. Я тогда перешел из одной команды разработчиков в другую и хотел обновить свои знания языка C++. Я начал смотреть видео с конференций по C++, читать книги Александра Степанова по обобщенному программированию и полностью изменил свои представления о том, как нужно писать код.

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

Я прочитал немало книг на эту тему, начиная от Elements of Programming и From Mathematics to Generic Programming Степанова1 и до Category Theory for Programmers Бартоша Милевски (Bartosz Milewski)2 и Types and Programming Languages Бенджамина Пирса (Benjamin Pierce)3. Как вы понимаете из названий, книги посвящены скорее теоретико-математическим вопросам. Чем больше я узнавал о системах типов, тем лучше становился код, который я писал на работе. Между теоретическими вопросами проектирования систем типов и повседневной работой над программным обеспечением существует самая непосредственная связь. Я вовсе не открываю Америку: все причудливые возможности систем типов существуют как раз для решения реальных задач.

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

Цель книги — подробный анализ возможностей систем типов, начиная от базовых типов, функциональных типов и создания подтипов4, ООП, обобщенного программирования и типов более высокого рода, например функторов и монад. Вместо того чтобы сосредоточиться на теоретической стороне этих возможностей, я опишу их практическое применение. В данной книге рассказывается, как и когда использовать каждую из них, чтобы сделать свой код лучше.

Изначально предполагалось, что примеры кода будут на языке C++. Система типов C++ обладает намного большими возможностями, чем у таких языков, как Java и C#. С другой стороны, C++ — сложный язык, и я не хотел искусственно ограничивать аудиторию книги, так что решил применить вместо него TypeScript. Система типов этого языка тоже располагает широкими возможностями, но его синтаксис более доступен, поэтому изучение примеров не доставит сложностей даже тем, кто привык к другим языкам. В приложении Б приведена краткая шпаргалка по используемому в данной книге подмножеству TypeScript.

Я надеюсь, что вы получите удовольствие от чтения этой книги и изучите кое-какие новые методики, которые сможете сразу же применить в своих проектах.

Благодарности

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

Написание книги, безусловно, заслуга целой команды. Я признателен Майклу Стивенсу (Michael Stephens) за первоначальные отзывы. Я хочу поблагодарить моего редактора Элешу Хайд (Elesha Hyde) за всю ее помощь, советы и отзывы. Спасибо Майку Шепарду (Mike Shepard) за рецензию на каждую из глав и честную критику. Кроме того, спасибо Херману Гонсалесу (German Gonzales) за просмотр всех до единого примеров кода и проверку правильности их работы. Я хотел бы поблагодарить всех рецензентов за уделенное мне время и бесценные отзывы. Спасибо вам, Виктор Бек (Viktor Bek), Роберто Касадеи (Roberto Casadei), Ахмед Чиктэй (Ahmed Chicktay), Джон Корли (John Corley), Джастин Коулстон (Justin Coulston), Тео Деспудис (Theo Despoudis), Дэвид Ди Мария (David DiMaria), Кристофер Фрай (Christopher Fry), Херман Гонсалес-Моррис (German Gonzalez-Morris), Випул Гупта (Vipul Gupta), Питер Хэмптон (Peter Hampton), Клайв Харбер (Clive Harber), Фред Хит (Fred Heath), Райан Хьюбер (Ryan Huber), Дес Хорсли (Des Horsley), Кевин Норман Д. Капчан (Kevin Norman D. Kapchan), Хосе Сан-Леандро (Jose San Leandro), Джеймс Люй (James Liu), Уэйн Мазер (Wayne Mather), Арнальдо Габриэль Айала Мейер (Arnaldo Gabriel Ayala Meyer), Риккардо Новьелло (Riccardo Noviello), Марко Пероне (Marco Perone), Джермаль Прествуд (Jermal Prestwood), Борха Кеведо (Borja Quevedo), Доминго Себастьян Састре (Domingo Sebastia'n Sastre), Рохит Шарм (Rohit Sharm) и Грег Райт (Greg Wright).

Я хотел бы поблагодарить моих сослуживцев и наставников за все, чему они меня научили. Когда я изучал возможности применения типов для улучшения нашей кодовой базы, мне повезло встретить нескольких замечательных менеджеров, всегда готовых прийти на помощь. Спасибо Майку Наварро (Mike Navarro), Дэвиду Хансену (David Hansen) и Бену Россу (Ben Ross) за их веру в меня.

Спасибо всему сообществу разработчиков C++, от которых я столь многому научился, особенно Шону Пэренту (Sean Parent) — за вдохновение и замечательные советы.

О книге

Цель этой книги — продемонстрировать вам, как писать лучший, более безопасный код с помощью систем типов. Хотя большинство изданий, посвященных системам типов, сосредотачиваются на более формальных аспектах вопроса, данная книга представляет собой скорее практическое руководство. Она содержит множество примеров, приложений и сценариев, встречающихся в повседневной работе программиста.

Целевая аудитория

Книга предназначена для программистов-практиков, которые хотят узнать больше о функционировании систем типов и о том, как с их помощью повысить качество своего кода. Желательно иметь опыт работы с объектно-ориентированными языками программирования: Java, C#, C++ или JavaScript/TypeScript, а также хотя бы минимальный опыт проектирования ПО. Хотя в этой книге рассматриваются различные методики написания надежного, пригодного для компоновки и хорошо инкапсулированного кода, предполагается, что вы понимаете, почему эти свойства желательны.

Структура книги

Книга содержит 11 глав, посвященных различным аспектам типизированного программирования.

• В главе 1 мы познакомимся с типами и их системами, обсудим, для чего они служат и какую пользу могут принести. Рассмотрим существующие виды систем типов и поговорим о строгой, а также статической и динамической типизациях.

• В главе 2 мы рассмотрим простые типы данных, существующие в большинстве языков программирования, и нюансы, которые следует учитывать при их использовании. К распространенным простым типам данных относятся: пустой тип и единичный тип, булевы значения, числа, строки, массивы и ссылки.

• В главе 3 мы изучим сочетаемость: разнообразные способы сочетания типов для определения новых типов. Кроме того, рассмотрим различные способы реализации паттерна проектирования «Посетитель» и алгебраические типы данных.

• В главе 4 мы поговорим о типобезопасности — пути снижения неоднозначности и предотвращения ошибок при использовании типов. Кроме того, я расскажу о добавлении/удалении информации о типе из кода с помощью приведения типов.

• В главе 5 вы познакомитесь с функциональными типами и возможностями, возникающими благодаря созданию функциональных переменных. Мы рассмотрим альтернативные способы реализации паттерна проектирования «Стратегия» и конечных автоматов, а также базовые алгоритмы map(), filter() и reduce().

• В главе 6 будет представлен расширенный материал предыдущей главы и продемонстрировано несколько продвинутых приложений функциональных типов данных, начиная от упрощенного паттерна проектирования «Декоратор» и заканчивая возобновляемыми и асинхронными функциями.

• В главе 7 мы познакомимся с созданием подтипов и обсудим совместимость типов данных. Мы рассмотрим применение низшего и высшего типов и увидим, как связаны друг с другом тип-сумма, коллекции и функциональные типы с точки зрения подтипизации.

• В главе 8 мы обсудим ключевые элементы объектно-ориентированного программирования и их использование. Рассмотрим интерфейсы, наследование, сочетание типов и примеси.

• В главе 9 вы познакомитесь с обобщенным программированием и его первым приложением: обобщенными структурами данных. Эти структуры отделяют схему данных от них самих; обход структур возможен с помощью итераторов.

• В главе 10 мы продолжим тему обобщенного программирования и обсудим обобщенные алгоритмы и категории итераторов. Обобщенными являются алго­ритмы, которые можно использовать повторно для различных типов данных. Итераторы играют роль интерфейса между структурами данных и алгоритмами и, в зависимости от своих возможностей, могут запускать различные алгоритмы.

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

Все главы используют понятия, описанные в предыдущих главах книги, так что читать их следует по порядку. Тем не менее четыре основные темы более или менее независимы. В первых четырех главах описываются основные понятия; в главах 5 и 6 рассказывается о функциональных типах данных; в главах 7 и 8 — о создании подтипов; главы 9, 10 и 11 посвящены обобщенному программированию.

О коде

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

Во многих случаях первоначальный исходный код был переформатирован: были добавлены разрывы строк и переработаны отступы, чтобы наилучшим образом использовать доступное место на страницах книги. В редких случаях этого оказывалось недостаточно, и листинги включают маркеры продолжения строки (). Кроме того, из исходного кода нередко удалялись комментарии там, где он описывался в тексте. Многие листинги сопровождают примечания к коду, подчеркивающие важные нюансы.

Исходный код для всех листингов данной книги доступен для скачивания с GitHub по адресу https://github.com/vladris/programming-with-types/. Сборка кода производилась с помощью версии 3.3 компилятора TypeScript со значением ES6 для опции target и c опцией strict.

Об авторе

Влад Ришкуция — специалист по разработке ПО в Microsoft, имеет более чем десятилетний опыт. За это время он руководил несколькими крупными программными проектами и обучил множество молодых специалистов.

Дискуссионный форум книги

Покупка этой книги дает право на бесплатный доступ к частному веб-форуму издательства Manning, где можно оставлять комментарии о книге, задавать технические вопросы и получать помощь от автора книги и других пользователей. Чтобы попасть на этот форум, перейдите по адресу https://livebook.manning.com/#!/book/natural-language-processing-in-action/discussion. Узнать больше о форумах издательства и правилах поведения на них можно на странице https://livebook.manning.com/#!/discussion.

Обязательства издательства Manning по отношению к своим читателям заключаются в том, чтобы предоставить место для содержательного диалога между отдельными читателями, а также читателями и авторами. Эти обязательства не включают какого-либо конкретного объема участия со стороны авторов, чей вклад в работу форума остается добровольным (и неоплачиваемым). Мы советуем вам задавать авторам интересные и трудные вопросы, чтобы их интерес не угас!

Об иллюстрации на обложке

Рисунок на обложке называется Fille Lipporolle en habit de Noce («Девица Липороль в свадебном платье»). Эта иллюстрация взята из недавнего переиздания книги Жака Грассе де Сан-Савье Costumes de Diffe'rents Pays («Наряды разных стран»), опубликованной во Франции в 1797 году. Все иллюстрации прекрасно прорисованы и раскрашены вручную. Широкое разнообразие коллекции нарядов Грассе де Сан-Савье напоминает нам, насколько разъединены были различные регионы мира всего 200 лет назад. Изолированные друг от друга, люди говорили на разных диалектах и языках. На улицах городов и в деревнях по одной манере одеваться можно было легко понять, каким ремеслом занимается человек и каково его социальное положение.

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

В наше время, когда книги на компьютерную тематику так мало отличаются друг от друга, издательство Manning отдает должное изобретательности и инициативе компьютерного бизнеса обложками книг, основанными на богатом разнообразии жизни в разных уголках мира двухвековой давности, возвращенном к нам иллюстрациями Жака Грассе де Сан-Савье.

От издательства

Ваши замечания, предложения, вопросы отправляйте по адресу comp@piter.com (издательство «Питер», компьютерная редакция).

Мы будем рады узнать ваше мнение!

На веб-сайте издательства www.piter.com вы найдете подробную информацию о наших книгах.

Глава 1. Введение в типизацию

В этой главе

• Зачем нужны системы типов.

• Преимущества сильно типизированного кода.

• Разновидности систем типов.

• Распространенные возможности систем типов.

Аппарат Mars Climate Orbiter развалился в атмосфере Марса, поскольку разработанный компанией Lockheed компонент выдавал измерения импульса силы в фунт-силах на секунду (единицы измерения США), а другой компонент, разработанный НАСА, ожидал, что импульс силы будет измеряться в ньютонах на секунду (единицы СИ). Катастрофы можно было избежать, если бы для этих двух величин использовались различные типы данных.

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

Благодаря научным изысканиям в области языков программирования возникают все более и более эффективные системы типов (см., например, такие языки программирования, как Elm и Idris). Растет популярность языка Haskell. В то же время продолжаются попытки добиться проверки типов на стадии компиляции в динамически типизированных языках: в Python появилась поддержка указаний ожидаемых типов (type hints) и был создан язык TypeScript, единственная цель которого — обеспечить проверку типов во время компиляции в JavaScript.

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

1.1. Для кого эта книга

Книга предназначена для программистов-практиков. Читатель должен хорошо уметь писать код на одном из таких языков программирования, как Java, C#, C++ или JavaScript/TypeScript. Примеры кода приведены на языке TypeScript, но большая часть излагаемого материала применима к любому языку программирования. На самом деле в примерах далеко не всегда используется характерный TypeScript. По возможности они адаптировались так, чтобы их понимали программисты на других языках программирования. Сборка примеров кода описана в приложении A, а краткая «шпаргалка» по языку TypeScript — в приложении Б.

Если вы по работе занимаетесь разработкой объектно-ориентированного кода, то, возможно, слышали об алгебраических типах данных (algebraic data type, ADT), лямбда-выражениях, обобщенных типах данных (generics), функторах, монадах и хотите лучше разобраться, что это такое и как их использовать в своей работе.

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

Основная часть литературы по системам типов сильно формализована. Книга же сосредотачивает внимание на практических приложениях систем типов; поэтому математики в ней очень мало. Тем не менее желательно, чтобы вы имели представление об основных понятиях алгебры, таких как функции и множества. Это понадобится для пояснения некоторых из нужных нам понятий.

1.2. Для чего существуют типы

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

Пример подобной нестрогой интерпретации — функция eval() языка JavaScript, выполняющая строковое значение как код. Она отлично работает, если переданная ей строка представляет собой допустимый код на языке JavaScript, но вызывает ошибку времени выполнения в противном случае, как показано в листинге 1.1.

Листинг 1.1. Попытка интерпретировать данные как код

 

1.2.1. Нули и единицы

Необходимо не только различать код и данные, но и интерпретировать элементы данных. Состоящая из 16 бит последовательность 1100001010100011 может соответствовать беззнаковому 16-битному целому числу 49827, 16-битному целому числу со знаком –15709, символу '£' в кодировке UTF-8 или чему-то совершенно другому, как можно видеть на рис. 1.1. Аппаратное обеспечение, на котором работают наши программы, хранит все в виде последовательностей битов, так что необходим дополнительный слой для осмысления этих данных.

 

Рис. 1.1. Последовательность битов можно интерпретировать по-разному

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

Кроме того, типы ограничивают множество допустимых значений переменных. Шестнадцатибитное целое число со знаком может отражать любое из целочисленных значений от –32768 до 32767 и только их. Благодаря ограничению диапазона допустимых значений исключаются целые классы ошибок, поскольку не допускается возникновения неправильных значений во время выполнения, как показано на рис. 1.2. Чтобы понять многие из приведенных в этой книге концепций, важно рассматривать типы как множества возможных значений.

В разделе 1.3 мы увидим: система обеспечивает также соблюдение многих других мер безопасности при добавлении возможностей в код, например обозначение значений как const или членов как private.

 

Рис. 1.2. Последовательность битов с типом 16-битного знакового целого. Информация о типе (16-битное знаковое целое число) указывает компилятору и/или среде выполнения, что эта битная последовательность представляет собой целочисленное значение в диапазоне от –32 768 до 32 767, благодаря чему она правильно интерпретируется как –15 709

1.2.2. Что такое типы и их системы

Раз уж книга посвящена типам и их системам, дам определения этих терминов, прежде чем идти дальше.

Что такое Тип

Тип (type) — классификация данных, определяющая допустимые операции над ними, смысл этих данных и множество допустимых значений. Компилятор и/или среда выполнения производят проверку типов, чтобы обеспечить целостность данных и соблюдение ограничений доступа, а также интерпретацию данных в соответствии с замыслом разработчика.

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

Система типов

Система типов (type system) представляет собой набор правил присвоения типов элементам языка программирования и обеспечения соблюдения этих присвоений. Такими элементами могут быть переменные, функции и другие высокоуровневые конструкции языка. Системы типов производят присвоение типов с помощью задаваемой в коде нотации или неявным образом, путем вывода типа конкретного элемента по контексту. Системы типов разрешают одни преобразования типов друг в друга и запрещают другие.

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

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

 

Рис. 1.3. С помощью компилятора или интерпретатора исходный код преобразуется в код, запускаемый средой выполнения. Ее роль может играть физический компьютер или виртуальная машина, например JVM Java или движок JavaScript браузера

Проверка типов

Процесс проверки типов (type checking) обеспечивает соблюдение программой правил системы типов. Проверка производится компилятором во время преобразования кода или средой выполнения при его работе. Компонент компилятора, обеспечивающий соблюдение правил типизации, называется модулем проверки типов (type checker).

Если проверка типов завершается неудачно, то есть программа не соблюдает правила системы типов, то возникает ошибка на этапе компиляции или выполнения. Разницу между проверкой типа на этапе компиляции и на этапе выполнения мы обсудим подробнее в разделе 1.4.

Проверка типов и доказательства В основе систем типов лежит формальная теория. Замечательное соответствие Карри-Ховарда (Curry-Howard correspondence), известное также как эквивалентность между математическими доказательствами и программами (proofs-as-programs), демонстрирует родственность логики и теории типов. Оно показывает, что тип можно рассматривать как логическое высказывание, а функцию, принимающую на входе один тип и возвращающую другой, — как логическую импликацию. Значение типа эквивалентно факту справедливости высказывания. Возьмем для примера функцию, принимающую на входе boolean и возвраща­ющую string. Из булева значения в строковое function booleanToString(b: boolean): string {     if (b) {         return "true";     } else {         return "false";     } } Эту функцию можно интерпретировать как «из boolean следует string». По заданному факту высказывания типа boolean данная функция (импликация) выдает факт высказывания типа string. Факт boolean представляет собой значение этого типа, true или false. По нему указанная функция (импликация) выдает факт string в виде строки "true" или"false". Тесная связь между логикой и теорией типов показывает: соблюдающая правила системы типов программа эквивалентна логическому доказательству. Другими словами, система типов — язык написания этих доказательств. Соответствие Карри-Ховарда важно тем, что правильность работы программы гарантируется с логической строгостью.

1.3. Преимущества систем типов

Все данные, по сути, представляют собой нули и единицы, поэтому все свойства данных, например их интерпретация, неизменяемость и видимость, относятся к уровню типа. Переменная объявляется с числовым типом, и модуль проверки типа гарантирует, что ее значение не будет интерпретировано как строковое. Переменная объявляется как приватная или предназначенная только для чтения. И хотя сами данные в памяти ничем не отличаются от аналогичных публичных изменяемых данных, модуль проверки типа гарантирует, что мы не будем обращаться к приватной переменной вне ее области видимости или пытаться изменить данные, предназначенные только для чтения.

Основные преимущества типизации — корректность (correctness), неизменя­емость (immutability), инкапсуляция (encapsulation), компонуемость (composability) и читабельность (readability). Это фундаментальные признаки хорошей архитектуры и нормального поведения программного обеспечения. С течением времени системы развиваются. Эти признаки противостоят энтропии, которая неизбежно возникает в любой системе.

1.3.1. Корректность

Корректным (сorrect) является код, который ведет себя в соответствии со спецификациями, выдает ожидаемые результаты без ошибок и сбоев во время выполнения. Благодаря типам растут строгость кода и гарантии его должного поведения.

Для примера предположим, что нам нужно найти позицию строки "Script" внутри другой строки. Мы не будем передавать достаточную информацию о типе и разрешим передачу в качестве аргумента нашей функции значения типа any. Как показывает листинг 1.2, это приведет к ошибкам во время выполнения.

В этой программе содержится ошибка — 42 не является допустимым аргументом для функции scriptAt, но компилятор об этом молчит, поскольку мы не предоставили достаточную информацию о типе данных. Усовершенствуем данный код, ограничив аргумент типом string в листинге 1.3.

Теперь компилятор отвергает эту некорректную программу, выдавая следующее сообщение об ошибке: Argumentoftype'42'isnotassignabletoparameteroftype'string' (невозможно присвоить параметру типа 'string' аргумент типа '42').

Листинг 1.2. Недостаточная информация о типе данных

 

Листинг 1.3. Уточненная информация о типе

 

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

Ошибки возникают, когда программа переходит в некорректное состояние, то есть текущее сочетание всех ее действующих переменных некорректно по какой-либо причине. Один из методов, позволяющих избавиться от части таких некорректных состояний, — уменьшение пространства состояний за счет ограничения количества возможных значений переменных, как показано на рис. 1.4.

 

Рис. 1.4. Благодаря правильному объявлению типа можно запретить некорректные значения. Первый тип слишком широк и допускает нежелательные нам значения. Второй тип — более жестко ограниченный — не скомпилируется, если код попытается присвоить переменной нежелательное значение

Пространство состояний (state space) работающей программы можно описать как сочетание всех вероятных значений всех ее действующих переменных. То есть декартово произведение типов всех переменных. Напомню, что тип переменной можно рассматривать как множество ее возможных значений. Декартово произведение двух множеств представляет собой множество, состоящее из всех их упорядоченных пар элементов.

Безопасность

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

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

1.3.2. Неизменяемость

Неизменяемость (immutability) — еще одно свойство, тесно связанное с представлением о нашей работающей системе как о движении по пространству состояний. Вероятность ошибок можно снизить, если при нахождении системы в заведомо хорошем состоянии не допускать его изменений.

Рассмотрим простой пример, в котором попытаемся предотвратить деление на ноль с помощью проверки значения делителя и генерации ошибки в случае, когда оно равно 0, как показано в листинге 1.4. Если же значение может меняться после нашей проверки, то она теряет всякий смысл.

Листинг 1.4. «Плохое» изменение значения5

 

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

Листинг 1.5. Неизменяемость

 

Теперь компилятор отвергает некорректный код, выводя следующее сообщение об ошибке: Cannotassignto'x'becauseitisaconstant (Присвоение значения переменной x невозможно, поскольку она является константой).

В смысле представления в оперативной памяти разницы между изменяемой и неизменяемой x нет. Свойство константности значит что-то только для компилятора. Это свойство, обеспечиваемое системой типов.

Указание на неизменяемость состояния с помощью добавления ключевого слова const в описание типа предотвращает те изменения значений, при которых теряются гарантии, полученные благодаря предыдущим проверкам. Особенно полезна неизменяемость в случае конкурентного выполнения, поскольку делает невозможной состояние гонки.

Оптимизация компиляторов обеспечивает выдачу более эффективного кода в случае неизменяемых переменных, так как их значения можно встраивать в код. В некоторых функциональных языках программирования все данные — неизменяемые: функции принимают на входе какие-либо данные и возвращают другие, никогда не меняя входных. При этом достаточно один раз проверить значение переменной и убедиться в ее хорошем состоянии с целью гарантировать, что она будет находиться в хорошем состоянии на протяжении всего жизненного цикла. Конечно, при этом приходится идти на (не всегда желательный) компромисс: копировать данные, с которыми в противном случае можно было бы работать, не прибегая к дополнительным структурам данных.

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

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

Инкапсуляция (encapsulation) — сокрытие части внутреннего устройства кода в функции, классе или модуле. Как вы, вероятно, знаете, инкапсуляция — желательное свойство, она помогает понижать сложность: код разбивается на меньшие компоненты, каждый из которых предоставляет доступ только к тому, что действительно нужно, а подробности реализации скрываются и изолируются.

В листинге 1.6 мы расширим пример безопасного деления, превратив его в класс, который старается гарантировать отсутствие деления на 0.

Листинг 1.6. Недостаточная инкапсуляция

 

В данном случае мы не можем сделать делитель неизменяемым, поскольку хотим, чтобы у вызывающего наш API кода была возможность его обновлять. Проблема такова: вызывающая сторона может обойти проверку на 0 и непосредственно задать любое значение для divisor, так как он для них доступен. Эту проблему в данном случае можно решить, объявив его в качестве private и ограничив его область видимости классом, как показано в листинге 1.7.

Листинг 1.7. Инкапсуляция

 

Представление в оперативной памяти приватных и публичных членов класса одинаково; проблемный код не компилируется во втором примере просто благодаря указанию типа. На самом деле public, private и другие модификаторы видимости — свойства соответствующего типа.

Инкапсуляция (сокрытие информации) позволяет разбивать логику программы и данные на публичный интерфейс и непубличную реализацию. Это очень удобно в больших системах, поскольку при работе с интерфейсами (абстракциями) требуется меньше умственных усилий, чтобы понять конкретный фрагмент кода. Желательно анализировать и понимать код на уровне интерфейсов компонентов, а не всех их нюансов реализации. Полезно также ограничивать область видимости непубличной информации, чтобы внешний код не мог их модифицировать попросту вследствие отсутствия доступа.

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

1.3.4. Компонуемость

Допустим, нам требуется найти первое отрицательное число в числовом массиве и первую строку из одного символа в символьном массиве. Не прибегая к разбиению этой задачи на две части и последующему их объединению в единую систему, мы получили бы в итоге две функции: findFirstNegativeNumber() и findFirstOneCha­racterString(), показанные в листинге 1.8.

Листинг 1.8. Некомпонуемая система

function findFirstNegativeNumber(numbers: number[])

    : number | undefined {

    for (let i of numbers) {

        if (i < 0) return i;

    }

}

 

function findFirstOneCharacterString(strings: string[])

    : string | undefined {

    for (let str of strings) {

        if (str.length == 1) return str;

    }

}

Эти две функции ищут первое отрицательное число и первую строку из одного символа соответственно. Если подобных элементов не найдено, то функции возвращают undefined (неявно, путем выхода из функции без оператора return).

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

Листинг 1.9. Обновление некомпонуемой системы

function findFirstNegativeNumber(numbers: number[])

    : number | undefined {

    for (let i of numbers) {

        if (i < 0) return i;

    }

    console.error("No matching value found");

}

 

function findFirstOneCharacterString(strings: string[])

    : string | undefined {

    for (let str of strings) {

        if (str.length == 1) return str;

    }

    console.error("No matching value found");

}

Данный вариант явно не оптимальный. Что, если мы забудем обновить код в одном из мест? Подобные проблемы усугубляются в больших системах. Судя по виду этих функций, алгоритм в них один и тот же; но в одном случае мы работаем с числами с одним условием, а в другом — со строками с другим условием. Можно написать обобщенный алгоритм с параметризацией по типу обрабатываемых данных и проверяемому условию, как показано в листинге 1.10. Подобный алгоритм не зависит от других частей системы, и его можно анализировать отдельно.

Листинг 1.10. Компонуемая система

function first<T>(range: T[], p: (elem: T) => boolean)

    : T | undefined {

    for (let elem of range) {

        if (p (elem)) return elem;

    }

}

 

function findFirstNegativeNumber(numbers: number[])

    : number | undefined {

    return first(numbers, n => n < 0);

}

 

function findFirstOneCharacterString(strings: string[])

    : string | undefined {

    return first(strings, str => str.length == 1);

}

Не волнуйтесь, если синтаксис немного непривычен; мы обсудим встраиваемые функции (такие как n=>n<0) в главе 5 и обобщенные функции — в главах 9 и 10.

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

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

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

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

1.3.5. Читабельность

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

Важную роль в этом процессе играют наименования и комментарии, но типизация добавляет в него дополнительный слой информации, позволяя именовать ограничения. Взглянем на нетипизированное объявление функции find() в листинге 1.11.

Листинг 1.11. Нетипизированная функция find()

declare function find(range: any, pred: any): any;

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

Сравните с предыдущим объявлением следующий код (листинг 1.12).

Листинг 1.12. Типизированная функция find()

declare function first<T>(range: T[],

    p: (elem: T) => boolean): T | undefined;

Из этого описания сразу понятно, что для произвольного типа T необходимо передать в качестве аргумента range массив T[] и функцию, принимающую T и возвращающую boolean в качестве аргумента p. Кроме того, сразу же понятно, что функция возвращает T или undefined.

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

В большинстве современных языков программирования существуют какие-либо правила вывода типов (type inference), то есть определения типа переменной по контексту. Это удобно, поскольку позволяет снизить объем требуемого кода, но может превращаться в проблему, если код становится легко понятным для компилятора, но слишком запутанным для людей. Явно прописанный тип намного ценнее комментария, так как его соблюдение обеспечивает компилятор.

1.4. Разновидности систем типов

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

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

При сильной типизации производится очень мало преобразований типов (а то и вообще не производится), а менее сильные системы типов допускают больше неявных преобразований типов данных.

1.4.1. Динамическая и статическая типизация

JavaScript — язык с динамической типизацией, а TypeScript — со статической. На  самом деле TypeScript был создан именно для добавления статической проверки типов в JavaScript. Превращение ошибок времени выполнения в ошибки компиляции, особенно в больших приложениях, улучшает сопровождаемость и отказоустойчивость кода. Эта книга посвящена статической типизации и статическим языкам программирования, но полезно разобраться и в динамической модели.

Динамическая типизация не предполагает никаких ограничений типов во время компиляции. Обиходное название «утиная типизация» (duck typing) возникло из фразы «Если нечто ходит как утка и крякает как утка то, значит, это утка». Переменная может свободно применяться в коде как угодно, типизация происходит на этапе выполнения. Динамическую типизацию можно имитировать в TypeScript с помощью ключевого слова any, которое позволяет использовать нетипизированные переменные.

Реализуем функцию quacker(), принимающую на входе аргумент duck типа any и вызывающую для него функцию quack(). Все прекрасно работает, если у передаваемого объекта есть метод quack(). Если же передать нечто «не умеющее крякать» (без метода quack()), то получим TypeError времени выполнения, как показано в листинге 1.13.

Листинг 1.13. Динамическая типизация

 

При статической типизации, с другой стороны, проверка типов производится на этапе компиляции, так что попытка передать аргумент не того типа вызывает ошибку компиляции. Для полноценного использования возможностей статической типизации TypeScript можно усовершенствовать код, объявив в нем интерфейс Duck и указав соответствующий тип аргумента функции, как показано в листинге 1.14. Обратите внимание: в TypeScript не обязательно явным образом указывать, что мы реализуем интерфейс Duck, лишь бы был метод quack(). Если функция quack() есть, то компилятор считает интерфейс реализованным. В других языках программирования пришлось бы явным образом объявить, что класс реализует этот интерфейс.

Листинг 1.14. Статическая типизация

 

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

1.4.2. Слабая и сильная типизации

При описания систем типов часто можно встретить термины «сильная типизация»6 (strong typing) и «слабая типизация» (weak typing). Сила системы типов определяется степенью строгости соблюдения ею ограничений типов. Слабая система неявно преобразует значения из их фактических типов в типы, ожидаемые там, где они используются.

Задумайтесь: «молоко» равно «белое»? В сильно типизированном мире ответ на этот вопрос: нет, молоко — жидкость и сравнивать ее с цветом бессмысленно. В слабо типизированном мире можно сказать: «Ну, цвет молока — белый, так что да, молоко равно белому». В сильно типизированном мире можно явным образом преобразовать молоко в цвет, задав вопрос вот так: «Равен ли цвет молока белому?» В слабо типизированном мире это уточнение не требуется.

JavaScript — слабо типизированный язык. Чтобы это увидеть, достаточно воспользоваться типом any в TypeScript и делегировать типизацию во время выполнения JavaScript. В JavaScript есть два оператора проверки на равенство: ==, проверяющий равенство двух значений, и ===, проверяющий равенство как значений, так и их типов (листинг 1.15). Поскольку JavaScript — слабо типизированный язык, выражение вида "42"==42 равно true. Это довольно странно, ведь "42" — текстовое значение, а 42 — число.

Листинг 1.15. Слабая типизация

 

Неявные преобразования типов удобны тем, что не нужно писать много лишнего кода для явного преобразования из одного типа в другой, но и опасны, поскольку во многих случаях такие трансформации нежелательны и неожиданны для программиста. Благодаря сильной типизации TypeScript не скомпилирует ни одну из предыдущих операций сравнения, если объявить должным образом переменную a с типом string и переменную b с типом number, как показано в листинге 1.16.

Все эти операции сравнения вернут ошибку "Thisconditionwillalwaysreturn'false'sincethetypes'string'and'number'havenooverlap". (Это условие всегда возвращает false, поскольку типы 'string' и 'number' не пересекаются.) Модуль проверки типа обнаруживает, что мы пытаемся сравнить значения различных типов, и забраковывает код.

Листинг 1.16. Сильная типизация

 

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

Обратите внимание: хотя система типов может быть либо динамической (проверка типов во время выполнения), либо статической (проверка типов во время компиляции), существует целый диапазон степеней ее строгости: чем менее явные преобразования она производит, тем слабее система. В большинстве систем типов, даже сильных, есть какие-либо ограниченные возможности неявного приведения типов для считающихся безопасными преобразований. Распространенный пример — преобразование к boolean: if(a) скомпилируется, даже если a — number или относится к ссылочному типу. Еще один пример — расширяющее приведение типов (widening cast), о котором мы поговорим подробнее в главе 4. Для числовых значений в TypeScript используется только тип number, но в других языках, когда, допустим, передается восьмибитное значение при необходимом 16-битном целом числе, преобразование обычно выполняется автоматически, так как риска порчи данных нет (16-битное целое число может содержать любое значение, содержащееся в восьмибитном числе, и не только его).

1.4.3. Вывод типов

В некоторых случаях компилятор может вывести, исходя из контекста, тип переменной или функции, не указанный явным образом. Если присвоить переменной значение 42, например, то компилятор TypeScript может вывести, что ее тип — number, и нам не придется указывать тип. Это позволит увеличить прозрачность и понятность читателям кода, но соответствующая нотация необязательна.

Аналогично, если функция возвращает значения одного типа во всех операторах return, то указывать возвращаемый тип явно в описании функции не нужно. Компилятор может вывести эту информацию из кода, как показано в листинге 1.17.

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

Листинг 1.17. Вывод типа

 

1.5. В этой книге

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

Мы начнем с простых типов данных (primitive types), готовых для применения типов, доступных в большинстве языков программирования. Обсудим, как правильно их использовать и избежать распространенных ловушек. В ряде случаев будут показаны способы реализации некоторых из этих типов данных при отсутствии их нативной реализации в языке программирования.

Далее мы обсудим компонуемость и возможность сочетания простых типов данных в целях создания целой вселенной типов, необходимых для предметной области конкретной задачи. Существует множество способов сочетания типов данных, и вы узнаете, как выбрать правильный инструмент в зависимости от конкретной решаемой задачи.

Затем будет рассказано о функциональных типах данных (function types) и новых реализациях, обязанных своим появлением возможностям типизации функций и использования их аналогично обычным значениям. Функциональное программирование — весьма обширная тема, так что я не стану пытаться изложить ее во всей полноте, мы позаимствуем из нее некоторые полезные понятия и применим их к нефункциональному языку программирования для решения реальных задач.

Следующий этап эволюции систем типов после типизации значений, компоновки типов и типизации функций — создание подтипов (subtyping). Мы обсудим, какие качества делают тип подтипом другого типа, и попытаемся применить в нашем коде некоторые концепции объектно-ориентированного программирования. Обсудим наследование, компоновку и такой менее традиционный инструмент, как примеси.

Далее будет рассказано про обобщенные типы данных (generics), благодаря которым возможны переменные типов и параметризация кода типом данных. Обобщенные типы представляют собой совершенно новый уровень абстракции и компонуемости, расцепляя данные с их структурами, а структуры — с алгоритмами и делая вероятными адаптивные алгоритмы.

И наконец, обсудим типы более высокого рода (higher kinded types) — следующий уровень абстракции, параметризацию обобщенных типов данных. Типы более высокого рода представляют собой формализацию таких структур данных, как моноиды и монады. В настоящее время многие языки программирования не поддерживают типы более высокого рода, но их широкое применение в таких языках, как Haskell, и растущая популярность в конце концов должны привести и к внедрению их в более традиционные языки программирования.

Резюме

• Тип — классификация данных по возможным операциям над ними, их смыслу и набору допустимых значений.

• Система типов — набор правил назначения типов элементам языка программирования.

• Тип ограничивает диапазон принимаемых переменной значений, так что в некоторых случаях ошибка времени выполнения превращается в ошибку компиляции.

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

• Видимость — еще одно свойство уровня типа, определяющее, к каким данным есть доступ у тех или иных компонентов.

• Обобщенное программирование предоставляет широкие возможности расцепления и повторного использования кода.

• Указание нотаций типов упрощает понимание кода.

• Динамическая («утиная») типизация — определение типа на этапе выполнения.

• При статической типизации типы проверяются во время компиляции и перехватываются ошибки, которые в противном случае могли бы возникнуть во время выполнения.

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

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

В главе 2 мы рассмотрим простые типы данных — простейшие стандартные блоки систем типов. Научимся избегать некоторых распространенных ошибок, возника­ющих при использовании этих типов, а также узнаем, как создать практически любую структуру данных из массивов и ссылок.

Глава 2. Базовые типы данных

В этой главе

• Основные простые типы данных и их использование.

• Вычисление булевых значений.

• Ловушки числовых типов и кодирования текста.

• Базовые типы для создания структур данных.

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

В этой главе мы рассмотрим часто встречающиеся простые типы данных (пустой, единичный, булев тип, числа, строки, массивы и ссылки), способы их применения и распространенные ловушки. Хотя мы используем простые типы данных ежедневно, существуют малозаметные нюансы, которые необходимо учитывать для эффективного применения этих типов. Например, существует возможность сокращенного вычисления булевых выражений, а при вычислении числовых выражений может происходить переполнение.

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

2.1. Проектирование функций, не возвращающих значений

Если рассматривать типы как множества вероятных значений, то возникает вопрос: а существует ли тип, соответствующий пустому множеству? Оно не содержит элементов, так что невозможно будет создать экземпляр этого типа. Будет ли польза от такого типа?

2.1.1. Пустой тип

Посмотрим, сможем ли мы описать как часть библиотеки утилит функцию, которая, получив сообщение в качестве параметра, заносила бы в журнал факт возникновения ошибки, включая метку даты/времени и сообщение, после чего генерировала бы исключение, как показано в листинге 2.1. Такая функция является просто оберткой для throw, поэтому не должна возвращать управление.

Листинг 2.1. Генерация и журналирование ошибки в случае отсутствия файла конфигурации

 

Обратите внимание: возвращаемый тип функции в данном примере — never. Благодаря этому читателям кода понятно, что функция raise никогда не должна возвращать значение. Более того, если кто-нибудь потом случайно изменит описание функции, добавив оператор return, то код перестанет компилироваться. Типу never нельзя присвоить абсолютно никакое значение, поэтому задуманное поведение функции обеспечивает компилятор и гарантирует, что она не будет возвращать управление.

Подобный тип данных называется «необитаемым» (uninhabitable type), или пустым типом данных (empty type), поскольку создать его экземпляр невозможно.

Пустой тип данных

Пустой тип — это тип данных, у которого не может быть никакого значения: множество его вероятных значений — пустое. Задать значение переменной такого типа невозможно. Пустой тип уместен как символ невозможности чего-либо, например, в качестве возвращаемого типа функции, которая никогда не возвращает значения (генерирует исключение или содержит бесконечный цикл).

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

Объявление подобной функции как возвращающей void (тип, используемый в большинстве языков программирования для указания на отсутствие осмысленного значения) только вводит читателя в заблуждение. Наша функция не просто не возвращает осмысленное значение, она вообще ничего не возвращает!

Незавершающиеся функции Пустой тип может показаться тривиальным, но демонстрирует фундаментальное различие между математикой и информатикой: в математике нельзя определить функцию, отображающую непустое множество в пустое. Это просто лишено смысла. Функции в математике не «вычисляются», они просто «существуют». Компьютеры, с другой стороны, вычисляют программы; пошагово выполняют инструкции. Компьютер в процессе вычислений может оказаться в бесконечном цикле, выполнение которого никогда не прекратится. Поэтому в компьютерных программах могут описываться осмысленные функции отображения в пустое множество, такие как в предыдущих примерах.

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

Самодельный пустой тип

Далеко не во всех широко распространенных языках программирования есть готовый пустой тип данных наподобие типа never в TypeScript. Но в большинстве языков его можно реализовать самостоятельно. Это осуществимо с помощью описания перечисляемого типа, не содержащего никаких элементов или структуры с одним только приватным конструктором, чтобы его нельзя было вызвать.

В листинге 2.2 показано, как можно реализовать пустой тип в TypeScript в виде класса, не допускающего создания экземпляров. Обратите внимание: TypeScript считает два типа со схожей структурой совместимыми, так что нам придется добавить фиктивное свойство типа void, чтобы в прочем коде не могло оказаться значения, которое неявно бы преобразовалось в Empty. В прочих языках, например Java и C#, такого дополнительного свойства не требуется, поскольку в них совместимость типов не определяется на основе их формы. Мы обсудим этот вопрос подробнее в главе 7.

Листинг 2.2. Реализация пустого типа в виде невоплощаемого класса

 

Данный код компилируется, поскольку компилятор выполняет анализ потока команд и определяет, что оператор return не нужен. С другой стороны, добавить этот оператор невозможно, поскольку нельзя создать экземпляр класса Empty.

2.1.2. Единичный тип

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

Рассмотрим в качестве примера функцию console.log(): она выводит свой аргу­мент в отладочную консоль, но не возвращает никаких осмысленных значений. С другой стороны, по завершении выполнения она возвращает управление вызывающей стороне, так что ее возвращаемым типом не может служить never.

Классическая функция "Helloworld!", приведенная в листинге 2.3, — еще один хороший пример этого. Ее вызывают для вывода в консоль приветствия (то есть ради побочного эффекта), а не в целях возврата значения, так что мы укажем для нее возвращаемый тип void.

Листинг 2.3. Функция «Hello world!»

 

Возвращаемый тип подобных функций называется единичным типом (unit type), то есть типом, у которого может быть только одно значение, и в TypeScript и большинстве других языков он называется void. Причина, из-за чего обычно не используются переменные типа void, а просто производится возврат из void функции без указания реального значения, состоит как раз в том, что значение единичного типа неважно.

Единичный тип

Единичный тип (unit type) — это тип, число вероятных значений которого равно одному. Нет смысла проверять значение переменной подобного типа — оно может быть только одним. Единичный тип используют, когда возвращаемый функцией результат неважен.

Функции, принимающие какое-либо число аргументов, но не возвращающие никакого осмысленного значения, называются также действиями (actions), поскольку обычно выполняют одну или несколько операций, которые меняют состояние, или потребителями (consumers), так как получают аргументы, но ничего не возвращают.

Самодельный единичный тип

Типы, подобные void, есть в большинстве языков программирования, однако некоторые языки рассматривают этот тип особым образом и не позволяют использовать его полностью аналогично другим типам. В подобных случаях можно создать собственный единичный тип, описав перечисляемый тип из одного элемента или класс-одиночку без состояния. Так как переменная единичного типа может принимать только одно значение, неважно, каким это значение будет; все единичные типы эквивалентны. Преобразование из одного единичного типа в другой тривиально, поскольку нет никаких вариантов: единственное значение одного типа соответствует единственному значению другого.

В листинге 2.4 показано, как можно реализовать единичный тип в TypeScript. Как и для самодельного пустого типа, мы воспользуемся свойством типа void, чтобы другие типы с совместимой структурой не преобразовывались неявно в Unit. В других языках программирования, например Java и C#, это дополнительное свойство не нужно.

Листинг 2.4. Реализация единичного типа в виде класса-одиночки без состояния

 

 

2.1.3. Упражнения

1. Какой возвращаемый тип должен быть у функции set(), принимающей на входе значение и присваивающей его глобальной переменной?

А. never.

Б. undefined.

В. void.

Г. any.

2. Какой возвращаемый тип должен быть у функции terminate(), которая немедленно прерывает выполнение программы?

А. never.

Б. undefined.

В. void.

Г. any.

2.2. Булева логика и сокращенные схемы вычисления

За типами, у которых не может быть возможных значений (пустых типов наподобие never), и типами с одним вероятным значением (единичных типов вроде void) логично следуют типы с двумя такими значениями. Каноническим примером типа с двумя возможными значениями, доступным в большинстве языков программирования, является булев (Boolean) тип.

Булевы значения отражают правдивость. Свое название они получили в честь Джорджа Буля (George Boole), придумавшего то, что сегодня носит название булевой алгебры — алгебры, состоящей из истинного значения (1), ложного значения (0) и логических операций над ними, например AND, OR и NOT.

В некоторых системах типов есть встроенный булев тип со значениями true и false. Другие системы используют числовые значения, считая, что 0 означает false, а любое другое число — true (то есть все, что не ложь, — истина). В TypeScript есть встроенный тип boolean, который может принимать значения true и false.

Вне зависимости от того, существует ли в конкретном языке простой булев тип или истинность определяется на основе значений других типов, в большинстве языков программирования используется какая-либо форма булевой семантики для условного ветвления (conditional branching). В таких операторах, как if(условие){...}, выражение между фигурными скобками выполняется, только если в результате вычисления условия получается истина. Условия применяются и в циклах, чтобы понять, продолжать ли итерации или завершить выполнение цикла: while(условие){...}. Без условного ветвления писать по-настоящему полезный код было бы невозможно. Представьте, как бы вы реализовали простейший алгоритм, например поиск первого четного числа в списке чисел, без циклов или условных операторов.

2.2.1. Булевы выражения

Во многих языках программирования для распространенных булевых операций используются следующие символы: && для AND, || для OR и ! для NOT. Булевы выражения обычно описываются с помощью таблиц истинности (рис. 2.1).

 

Рис. 2.1. Таблицы истинности AND, OR и NOT

2.2.2. Схемы сокращенного вычисления

Представьте, что вы хотите создать шлюз для системы комментирования, показанной в листинге 2.5: шлюз отвергает комментарии, отправленные пользователем менее чем через 10 секунд после предыдущего (спам), и комментарии с пустым содержимым (пользователь случайно нажал кнопку Comment (Отправить комментарий) до того, как написал что-либо).

Функция-шлюз принимает в качестве аргументов сам комментарий и идентификатор пользователя. Функция secondsSinceLastComment() у вас уже реализована; она выполняет запрос к базе данных по заданному идентификатору пользователя и возвращает количество секунд, прошедших с отправки им последнего комментария.

Если оба условия выполнены, то комментарий отправляется в базу данных, если нет — возвращается false.

Листинг 2.5 — одна из возможных реализаций подобного шлюза. Обратите внимание на выражение OR, в котором возвращается false, если предыдущий комментарий был отправлен менее чем 10 секунд назад или текущий комментарий пуст.

Другой способ реализации той же логики — поменять два операнда местами, как показано в листинге 2.6. Сначала проверяем, не пуст ли текущий комментарий; а затем проверяем, когда был отправлен предыдущий комментарий, как и в листинге 2.5.

Есть ли преимущество у какой-либо из этих версий? В них описаны одни и те же проверки — только в другом порядке. Оказывается, различие есть. В зависимости от входных данных версии могут вести себя по-разному во время выполнения вследствие того, как вычисляются булевы выражения.

Листинг 2.5. Шлюз

 

Листинг 2.6. Другой вариант реализации шлюза

 

Большинство компиляторов и сред выполнения оптимизируют булевы выражения с помощью так называемого сокращенного вычисления (short circuit). Выражение вида aANDb преобразуется в ifathenbelsefalse. При этом используется таблица истинности для операции AND: если первый операнд ложен, то и все выражение ложно, вне зависимости от значения второго операнда. С другой стороны, если первый операнд истинен, то все выражение истинно только в случае истинности и второго операнда.

Аналогичное преобразование производится для выражения aORb, которое превращается в ifathentrueelseb. Из таблицы истинности для операции OR видим, что если первый операнд истинен, то и все выражение истинно, вне зависимости от значения второго операнда. В противном же случае, когда первый операнд является ложным, все выражение истинно, если истинен второй операнд.

Причина такого преобразования и появления названия «сокращенное вычисление» — тот факт, что если вычисление первого операнда дает достаточно информации для вычисления всего выражения, то значение второго вообще не вычисляется. Шлюзовая функция должна выполнить две проверки. Первая не требует особых затрат ресурсов и проводится с целью убедиться в том, что полученный комментарий не пуст. Вторая — потенциально весьма дорогостоящая, включает запрос к базе комментариев. В листинге 2.5 сначала выполняется запрос к базе данных. Если последний комментарий был отправлен более 10 секунд назад, то сокращенная схема вычислений вообще не станет анализировать текущий комментарий и просто вернет false. В листинге 2.6, если текущий комментарий пуст, запрос к базе данных производиться не будет. Вторая версия потенциально может исключить дорогостоящую проверку за счет вычисления другой, гораздо менее затратной.

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

2.2.3. Упражнение

Что будет выведено в результате выполнения следующего кода?

let counter: number = 0;

 

function condition(value: boolean): boolean {

    counter++;

    return value;

}

 

if (condition(false) && condition(true)) {

    // ...

}

console.log(counter)

А. 0.

Б. 1.

В. 2.

Г. Ничего, будет сгенерировано исключение.

2.3. Распространенные ловушки числовых типов данных

В большинстве языков программирования одним из простых типов данных служат числовые типы. Существует несколько нюансов, которые желательно учитывать при работе с числовыми данными. Возьмем в качестве примера простую функцию для вычисления общей стоимости купленных товаров (листинг 2.7). Если пользователь купил три пачки жевательной резинки по 10 центов каждая, то итоговая сумма должна быть 30 центов. Но результат, полученный при некоторых способах применения числовых типов, может вас удивить.

Листинг 2.7. Функция подсчета общей стоимости купленных товаров

 

Почему же в результате суммирования 0,10 три раза не получается 0,30? Чтобы понять это, нам придется разобраться в том, как в компьютерах представляются числовые типы данных. Две определяющие характеристики числового типа — его ширина и способ кодирования.

Ширина (width) — это количество битов, используемое для представления значения. Может варьироваться от восьми бит (один байт) или даже одного бита до 64 бит и более. Битовая ширина тесно связана с архитектурой процессора: у 64-битного процессора и регистры 64-битные, благодаря чему операции над 64-битными значениями выполняются чрезвычайно быстро. Существует три способа кодирования числа заданной ширины: беззнаковый двоичный код (unsigned binary), дополнительный код (two's complement) и IEEE 754.

2.3.1. Целочисленные типы данных и переполнение

При беззнаковом двоичном кодировании для представления части значения используются все биты. Например, четырехбитное беззнаковое целое число может представлять любое значение от 0 до 15. В общем случае с помощью N-битного беззнакового целого числа можно представить значения от 0 (все биты равны 0) до 2N–1 (все биты равны 1). На рис. 2.2 показано несколько возможных значений четырехбитного беззнакового целого числа. Последовательность из N двоичных цифр (bN–1bN–2... b1b0) можно преобразовать в десятичное число по формуле bN–1 × 2N–1 + bN–2 × 2N–2 + ... + b1 × 21 + b0 × 20.

Это очень простой способ кодирования, который, впрочем, позволяет представлять только положительные числа. Представление отрицательных чисел возможно с помощью другого способа. Обычно для этой цели используется так называемый дополнительный код. Представление положительных чисел — точно такое же, как показано выше, а отрицательные кодируются путем вычитания их модуля из 2N, где N — количество битов. На рис. 2.3 показано несколько возможных значений четырехбитного знакового целого числа.

 

Рис. 2.2. Четырехбитное беззнаковое кодирование целых чисел. Минимально возможное значение при равенстве всех четырех бит 0 равно 0. Максимальное значение при равенстве всех четырех бит 1 равно 15 (1 × 23 + 1 × 22 + 1 × 21 + 1 × 20)

 

Рис. 2.3. Четырехбитное знаковое кодирование целых чисел. Значение –8 кодируется как 24 – 8 (1000 в двоичной системе счисления), а –3 — как 24 – 3 (1101 в двоичной системе счисления). Первый бит всегда равен 1 для отрицательных чисел и 0 для положительных

При таком способе кодирования у всех отрицательных чисел первый бит будет равен 1, а у всех положительных — 0. С помощью четырехбитного знакового целого можно отражать значения от –8 до 7. Чем больше битов используется для представления значения, тем большее значение можно представить.

Переполнение и потеря значимости

А что происходит, если результат арифметической операции не помещается в заданное число битов? Что, если мы пытаемся с помощью четырехбитного беззнакового кодирования сложить 10 с 10, хотя максимальное значение, которое можно представить с помощью четырех бит, — 15?

Подобная ситуация называется арифметическим переполнением (arithmetic overflow). Противоположная ситуация, когда число оказывается слишком маленьким для того, чтобы его можно было представить, называется потерей значимости или исчезновением порядка (arithmetic underflow). В различных языках программирования эти ситуации решаются по-разному (рис. 2.4).

Основные три способа решения проблем арифметического переполнения и потери значимости — возврат на ноль (wrap around), останов на максимальном значении (saturation) и вывод сообщения об ошибке (error out).

 

Рис. 2.4. Различные способы решения проблемы арифметического переполнения. Одометр переходит с 999 999 обратно на 0; диск телефона останавливается на максимально возможном значении; карманный калькулятор выводит на экран сообщение об ошибке (Error) и прекращает работу

Аппаратное обеспечение обычно производит возврат на ноль, то есть просто отбрасывает лишние биты. В случае четырехбитного беззнакового целого числа, если биты выглядят как 1111 и мы пытаемся прибавить 1, результат будет равен 10000, но, поскольку есть только четыре бита, один отбрасывается и остается 0000, то есть просто 0. Это самый эффективный способ борьбы с переполнением, но и самый опасный, так как может привести к неожиданным результатам. Это все равно что прибавить один доллар к имеющимся 15 и остаться с нулем.

Второй способ — останов на максимальном значении. Если результат превышает максимально представимое значение, то мы просто останавливаемся на данном максимуме. Это хорошо согласуется с реальным миром: при реле температуры, рассчитанном на определенную максимальную температуру, попытка сделать теплее ничего не даст. С другой стороны, при использовании этого метода арифметические операции перестают быть ассоциативными. Если наше максимальное значение равно 7, то 7+(2–2)=7+0=7, но (7+2)–2=7–2  =5.

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

Обнаружение переполнения и потери значимости

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

Например, чтобы проверить, не приведет ли сложение значений a и b к переполнению/потере значимости диапазона [MIN,MAX], необходимо убедиться, что не получится a+b<MIN (при сложении двух отрицательных чисел) или a+b>MAX.

Если значение b больше нуля, то ситуация a+b<MIN невозможна в принципе, так как мы увеличиваем значение a, а не уменьшаем. В этом случае необходимо проверять только возможность переполнения. Вычитая с обеих сторон неравенства b, можно переписать a+b>MAX в виде a>MAX–b. А поскольку мы вычитаем положительное число, сумма становится меньше, поэтому риска переполнения нет (MAX–b заведомо находится в диапазоне [MIN,MAX]). Так что переполнение происходит, если b>0 и a>MAX–b.

Если значение b меньше нуля, то ситуация a+b>MAX невозможна в принципе, так как мы уменьшаем значение a, а не увеличиваем. В этом случае достаточно проверить только на потерю значимости. Вычитая с обеих сторон неравенства b, можно переписать a+b<MIN в виде a<MIN–b. А поскольку мы вычитаем отрицательное число, значение становится больше, поэтому риска потери значимости нет (MIN–b заведомо находится в диапазоне [MIN,MAX]). Так что потеря значимости происходит, если b<0 и a<MIN–b, как показано в листинге 2.8.

Листинг 2.8. Проверка переполнения при сложении

 

Аналогичная логика применима при вычитании.

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

Переполнение происходит, если:

• b>0, a>0 и a>MAX/b;

• b<0, a<0 и a<MAX/b.

Потеря значимости происходит, если:

• b>0, a<0 и a<MIN/b;

• b<0, a>0 и a>MIN/b.

При целочисленном делении значение a/b всегда представляет собой целое число в диапазоне от –a до a. Проверять на переполнение и потерю значимости необходимо, только если отрезок [–a,a] не полностью находится внутри отрезка [MIN,MAX]. Возвращаясь к нашему примеру с четырехбитным знаковым целым числом, в котором MIN=–8, а MAX=7, видим, что единственный случай переполнения при делении –8/–1 (поскольку отрезок [–8,8] не полностью находится внутри отрезка [–8,7]). Фактически единственный сценарий переполнения при делении для знаковых целых чисел — когда a равно минимальному представимому значению, а b=–1. При делении беззнаковых целых чисел переполнение вообще невозможно.

В табл. 2.1 и 2.2 подытожены этапы проверки на переполнение и потерю значимости для случаев, когда необходима особая обработка.

Таблица 2.1. Обнаружение целочисленного переполнения для a и b в диапазоне [MIN, MAX] при MIN = –MAX – 1

Сложение	Вычитание	Умножение	Деление
b>0 и a>MAX–b	b<0 и a>MAX + b	b>0, a>0 и a>MAX/b b<0, a<0 и a<MAX/b	a==MIN и b==–1

Таблица 2.2. Обнаружение целочисленной потери значимости для a и b в диапазоне [MIN, MAX] при MIN = –MAX – 1

Сложение	Вычитание	Умножение	Деление
b<0 и a<MIN–b	b>0 и a<MIN+b	b>0, a<0 и a < MIN/b b<0, a>0 и a>MIN/b	N/A

2.3.2. Типы с плавающей точкой и округление

IEEE 754 представляет собой стандарт Института инженеров электротехники и электроники для представления чисел с плавающей точкой (floating-point), то есть чисел с дробной частью. В TypeScript (и JavaScript) числа представляются в виде 64-битных чисел с плавающей точкой с помощью кодирования binary64. Подробное описание этого представления приведено на рис. 2.5.

 

Рис. 2.5. Представление числа с плавающей точкой 0,10. Во-первых, тут можно видеть двоичное представление в оперативной памяти трех компонентов: бита знака, порядка и мантиссы. Ниже приведена формула преобразования двоичного представления в число. Наконец, вы видите результат приложения этой формулы: 0,10 аппроксимируется значением 0,100000000000000005551115123126

Три компоненты, составляющие число с плавающей точкой: знак, порядок и мантисса. Знак (sign) — один бит со значением 0 для положительных чисел и 1 для отрицательных. Мантисса (mantissa) представляет собой дробную часть, как показано в формуле на рис. 2.5. Эта часть умножается на 2 в степени, соответствующей смещенному порядку (biased exponent).

Порядок называется смещенным, поскольку из представленного порядком беззнакового целого числа мы вычитаем определенное значение, чтобы он мог представлять как положительные, так и отрицательные числа. В случае кодирования binary64 это значение равно 1023. В стандарте IEEE 754 описано несколько кодировок, в ряде которых используется основание 10 вместо 2, хотя 2 в качестве основания на практике встречается чаще.

В стандарте также определено несколько специальных значений.

• NaN — расшифровывается как not a number («не число») и применяется для результата некорректных операций, например деления на 0.

• Положительная и отрицательная бесконечность (Inf), используемая в качестве максимальных (минимальных) значений при переполнении.

• И хотя согласно вышеприведенной формуле значение 0,10 превращается в число 0,100000000000000005551115123126, оно округляется до 0,1. На самом деле числа 0,10 и 0,100000000000000005551115123126 считаются в JavaScript равными. Единственная возможность представлять дробные числа из огромного диапазона значений при наличии относительно небольшого числа битов — с помощью округления и аппроксимации.

Точность

Если нужны точные значения — при работе с денежными суммами, например, — избегайте использования чисел с плавающей точкой. Дело в том, что суммирование 0,10 три раза не дает 0,30 ввиду того, что, хоть каждое отдельное представление 0,10 и округляется до 0,10, в результате их сложения получается число, которое округляется до 0,30000000000000004.

Небольшие целые числа можно спокойно представить без округления, так что лучше кодировать цену в виде двух целочисленных значений: одно для долларов, а второе для центов. В JavaScript есть функция Number.isSafeInteger(), позволя­ющая узнать, можно ли представить данное целочисленное значение без округления. На ее основе можно создать тип Currency, который кодирует два целочисленных значения и защищает от проблем округления, как показано в листинге 2.9.

В другом языке программирования мы воспользовались бы двумя переменными целочисленного типа и защитились от проблем переполнения/потери значимости. Но, поскольку в JavaScript нет простого целочисленного типа данных, мы применили функцию Number.isSafeInteger() для защиты от проблем округления. При работе с денежными суммами лучше выдать ошибку, чем обнаружить потом, что деньги появились/исчезли загадочным образом.

Листинг 2.9. Класс Currency и функция сложения денежных сумм

 

Класс в листинге 2.9 — лишь каркас. Хорошим упражнением будет его расширение так, чтобы по достижении 100 в переменной для числа центов они автоматически превращались в доллар. Будьте осторожнее с проверкой безопасности целых чисел: что, если количество долларов представляет собой безопасное число, но при добавлении к нему 1 (получившейся из 100 центов) перестает быть таковым?

Сравнение чисел с плавающей точкой

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

Какое пороговое значение следует выбрать? Оно должно равняться максимальной возможной погрешности округления. Это значение называется машинным эпсилон (machine epsilon) и зависит от способа кодирования. В JavaScript данное значение указано в константе Number.EPSILON. С его помощью можно реализовать проверку двух чисел на равенство, проверяя, не превышает ли абсолютное значение их разности машинного эпсилон (листинг 2.10). Если нет, то эти значения отличаются друг от друга менее чем на погрешность округления, так что их можно считать равными.

Листинг 2.10. Равенство двух чисел с плавающей точкой в пределах эпсилон

 

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

2.3.3. Произвольно большие числа

В большинстве языков программирования есть библиотеки, позволяющие работать со сколь угодно большими числами. Данные типы способны увеличивать ширину до количества битов, требуемого для представления любого значения. В Python подобный тип является числовым типом по умолчанию, а для стандарта JavaScript сейчас предлагается использовать тип произвольно больших чисел BigInt. Тем не менее произвольно большие числа нельзя считать простыми типами данных, поскольку их можно построить на основе числовых типов фиксированной ширины. Они удобны, но во многих средах выполнения отсутствует их нативная реализация из-за отсутствия аппаратного эквивалента (микросхемы всегда работают с фиксированным количеством битов).

2.3.4. Упражнения

1. Что выведет следующий код?

let a: number = 0.3;

let b: number = 0.9;

 

console.log(a * 3 == b);

А. Ничего; вернет ошибку.

Б. true.

В. false.

Г. 0.9.

2. Каким должно быть поведение при переполнении числа, служащего для отслеживания уникальных идентификаторов?

А. Останов на максимальном значении.

Б. Возврат на ноль.

В. Возврат ошибки.

Г. Подходит любой из предыдущих вариантов.

2.4. Кодирование текста

Еще один распространенный простой тип данных — строка (string), используемая для представления текста. Строка (строковое значение) состоит из нуля или более символов, так что это первый из описанных нами простых типов данных, который потенциально может принимать бесконечное множество значений.

На заре эпохи компьютеров для кодирования каждого символа использовался один байт, поэтому компьютеры могли представлять текст с помощью всего 256 символов. После введения стандарта Unicode, предназначенного для представления всех мировых алфавитов и других символов (таких как эмодзи), 256 символов явно стало недостаточно. На самом деле в Unicode описано более миллиона символов!

2.4.1. Разбиение текста

Рассмотрим пример простой функции разбиения текста, принимающей на входе строку и разбивающей ее на несколько строк заданной длины, которые поместились бы в окне текстового редактора, как показано в листинге 2.11.

Листинг 2.11. Простая функция разбиения текста

 

На первый взгляд, данная реализация должна работать корректно. Для входного текста "Testing,testing" и длины строки 5 получаются строки ["Testi","ng,t","estin",g"]. Именно этого мы и ожидали: текст разбивается на несколько строк на каждом пятом символе.

Но другие символы кодируются более сложным образом. Возьмем, например, эмодзи «женщина-полицейский»:

. Хотя он и выглядит отдельным символом, JavaScript использует для его представления пять символов. Вызов "

".length возвращает 5. Попытка разбить строку, содержащую такой эмодзи, на основе его внешнего вида в тексте может повлечь неожиданные результаты. Например, если разбить текст ...

с длиной строки 5, мы получим в качестве результата массив ["...

","

"].

Эмодзи «женщина-полицейский» состоит из двух отдельных эмодзи: «полицейский» и знак, обозначающий женский пол. Они объединяются с помощью соединительного символа нулевой длины "\ud002". Он не имеет визуального представления и служит для объединения других символов.

Эмодзи «полицейский»,

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

с длиной строки 5. В результате этого эмодзи «женщина-полицейский» разбивается на два и мы получаем ["....\ud83d","\udc6e

"]. Элемент \uXXXX — управляющие последовательности Unicode, представляющие символы, которые нельзя вывести в консоль «как есть». Эмодзи «женщина-полицейский», хоть и визуализируется как один символ, состоит из пяти различных управляющих последовательностей: \ud83d, \udc6e, \u200d, \u2640 и \ufe0e.

Бездумное разбиение текста по границам символов может привести к невизуализируемым результатам и даже изменить смысл текста.

2.4.2. Кодировки

Чтобы разобраться, как правильно обрабатывать текст, необходимо изучить кодировки символов. Стандарт Unicode работает с двумя близкими, однако не идентичными понятиями: символы и графемы. Символы (characters) служат для представления текста (эмодзи «женщина-полицейский», объединяющий символ нулевой длины) в компьютере, а графемы (graphemes) — символы, которые видит пользователь (женщина-полицейский). При визуализации текста мы работаем с графемами, и разбивать многосимвольную графему нежелательно. В момент кодирования текста мы взаимодействуем с символами.

Глифы и графемы

Глиф (glyph) — это конкретное представление символа. C полужирным шрифтом и C курсивом — две различные визуализации данного символа.

Графема (grapheme) — неделимая единица, которая теряет смысл при разбиении на составные части, как в примере с женщиной-полицейским. Графему можно представить с помощью нескольких глифов. Эмодзи Apple для женщины-полицейского внешне отличается от эмодзи Microsoft; они представляют собой различные глифы, визуализирующие одну графему (рис. 2.6).

 

Рис. 2.6. Символьная кодировка эмодзи «женщина-полицейский» (символ эмодзи «женщина-полицейский» + объединяющий символ нулевой длины + эмодзи «женский пол») и графема, которая получается в результате (женщина-полицейский)

Каждый из символов Unicode описывается в виде кодовой точки, представля­ющей собой значение от 0x0 до 0x10FFFF, так что всего существует 1 114 1117 кодовых точек. Они отражают все алфавиты мира, эмодзи и множество других символов, и остается еще немало места для будущих дополнений.

UTF-32

Самая простая кодировка этих кодовых точек — UTF-32, в которой используется 32 бита для каждого символа; 32-битное целое число может представлять значения от 0x0 до 0xFFFFFFFF, так что в нем поместится любая кодовая точка и останется немало незанятых чисел. Проблема кодировки UTF-32 состоит в ее крайне низкой эффективности, поскольку теряется очень много места для неиспользуемых битов. Как следствие, было разработано несколько более сжатых кодировок, применяющих меньше битов для первых кодовых точек и больше битов по мере роста значений. Их называют кодировками переменной длины (variable-length encodings).

UTF-16 и UTF-8

Чаще всего используются кодировки UTF-16 и UTF-8. В JavaScript применяется кодировка UTF-16. Единица кодировки в ней составляет 16 бит. Кодовые точки, которые умещаются в это количество битов (0x0 до 0xFFFF), представляются с помощью одного 16-битного целого числа, а кодовые точки, требующие более 16 бит (от 0x10000 до 0x10FFFF), представляются с помощью двух 16-битных значений.

UTF-8, наиболее широко используемая кодировка, развивает этот подход: единица кодировки составляет 8 бит и кодовые точки представляются с помощью одного, двух, трех или четырех восьмибитных значений.

2.4.3. Библиотеки кодирования

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

Например, библиотека grapheme-splitter для JavaScript предназначена для работы как с символами, так и с графемами. Установить ее можно с помощью коман­ды npminstallgrapheme-splitter. Библиотека позволяет реализовать функцию lineBreak() для разбиения текста на уровне графем путем разбиения его на массив графем с последующей группировкой их в строки графем длиной lineLength, как показано в листинге 2.12.

Листинг 2.12. Функция для разбиения текста с помощью библиотеки grapheme-splitter

 

При такой реализации строки ...

и ....

вообще не будут разбиваться при длине строки в 5, поскольку ни одна из них не превышает длины пять графем, а строка .....

будет правильно разбита на [".....","

"].

Библиотека grapheme-splitter помогает предотвратить один из трех классов ошибок, часто встречающихся при работе со строками.

• Выполнение операций над кодированным текстом на уровне символов, а не графем. Мы рассмотрели данный пример в подразделе 2.4.1, где разбивали текст посимвольно, хотя для визуализации нам нужно было разбивать его по графемам. Попадание точки разбиения на пятый символ может привести к разбиению графемы на несколько отдельных графем. При отображении текста необходимо также учитывать то, из каких последовательностей символов состоят графемы.

• Выполнение операций над кодированным текстом на уровне байтов, а не символов. Подобная ситуация возможна, когда последовательность текста в кодировке переменной длины обрабатывается некорректно без учета кодировки, в результате чего символ может оказаться разбит на несколько, например при разбиении по пятому байту, когда нужно было разбивать по пятому символу. В зависимости от кодировки конкретный символ может содержать один байт или более, так что допущения, которые не учитывают способ кодирования, нежелательны.

• Интерпретация последовательности байтов как текста с неправильной кодировкой (например, пытаться интерпретировать текст в кодировке UTF-16 как текст в UTF-8, и наоборот). Необходимо знать, какова кодировка текста, полученного от другого компонента в виде байтовой последовательности. В различных языках приняты разные кодировки для текста по умолчанию, поэтому нельзя просто интерпретировать байтовые последовательности как строки — можно получить неправильную интерпретацию.

На рис. 2.7 показано, что графема «женщина-полицейский» состоит из двух символов Unicode. На этом рисунке также приведены их коды UTF-16 и бинарное представление.

 

Рис. 2.7. Эмодзи «женщина-полицейский» в виде битов в памяти в строковой кодировке UTF-16, байтовой последовательности UTF-16, последовательности кодовых точек UTF-16 и графемы

Обратите внимание, что UTF-8-кодирование для этой же графемы отличается, хотя экранное представление такое же. Кодирование UTF-8 для нее: 0xF00x9F0x910xAE0xE20x800x8D0xE20x990x800xEF0xB80x8F.

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

2.4.4. Упражнения

1. Сколько байтов необходимо для кодирования символа UTF-8?

А. 1 байт.

Б. 2 байта.

В. 4 байта.

Г. Зависит от символа.

2. Сколько байтов необходимо для кодирования символа UTF-32?

А. 1 байт.

Б. 2 байта.

В. 4 байта.

Г. Зависит от символа.

2.5. Создание структур данных на основе массивов и ссылок

Последние два простых типа данных, которые мы обсудим, — массивы и ссылки. С их помощью можно создать любую более сложную структуру данных, например список или дерево. У реализации структур данных на основе каждого из этих двух простых типов есть свои плюсы и минусы. Мы обсудим подробнее, как лучше их использовать в зависимости от ожидаемых паттернов обращения (частота чтения относительно частоты записи) и плотности данных (плотные или разреженные).

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

Мы не относим массивы переменной длины к простым типам данных, поскольку они реализуются на основе массивов фиксированной длины и/или ссылок, как мы увидим в этом разделе.

2.5.1. Массивы фиксированной длины

Массивы фиксированной длины представляют непрерывную область оперативной памяти, содержащую несколько значений одного типа. Так, массив из пяти 32-битных целых чисел занимает область 160 бит (5 × 32), в котором в первых 32 битах содержится первое число, во вторых 32 битах — второе и т.д.

Массивы используются чаще, чем, скажем, связные списки, из соображений быстродействия: доступ к любому из хранящихся последовательно значений не требует много времени. Если массив 32-битных целых чисел начинается по адресу 101 в оперативной памяти (первое целое число (с индексом 0) хранится в виде 32 бит, от 101 до 132), то целое число с индексом N в массиве находится по адресу 101 + N × 32. В общем случае, если массив начинается по адресу base, а размер элемента M, то элемент с индексом N находится по адресу base + N × M. Поскольку оперативная память непрерывна, достаточно высока вероятность попадания массива в одну страницу памяти и кэширования целиком, что позволит обращаться к нему очень быстро.

Напротив, для доступа к N-му элементу связного списка придется начать с головы (head) списка и переходить по указателям next узлов, пока не будет достигнут N-й элемент. Вычислить адрес узла напрямую невозможно. Память под узлы не обязательно выделяется последовательно, так что может понадобиться подгрузить/выгрузить несколько страниц памяти, прежде чем будет достигнут желаемый узел. На рис. 2.8 приведены представления массивов и связных списков целых чисел в оперативной памяти.

 

Рис. 2.8. Хранение пяти 32-битных целых чисел в массиве фиксированной длины и в связном списке. Поиск элемента в таком массиве производится чрезвычайно быстро, поскольку можно вычислить по формуле его точное местоположение. Напротив, при работе со связным списком необходимо следовать по указателям next элементов списка вплоть до достижения нужного элемента. Элементы могут располагаться в любом месте оперативной памяти

Термин «фиксированная длина» (fixed-size) означает, что массив нельзя увеличить в размере или сжать. Если понадобится сохранить в массиве шестой элемент, то придется выделить память под новый массив, вмещающий шесть элементов, и скопировать первые пять из старого. А в связный список, в отличие от массива, можно добавить узел без каких-либо модификаций уже существующих узлов. В зависимости от предполагаемого паттерна доступа (больше операций чтения или операций записи) лучше подойдет либо первое представление, либо второе.

2.5.2. Ссылки

Ссылочные типы содержат указатели на объекты. Значение ссылочного типа — содержащиеся в переменной биты — отражает не содержимое объекта, а лишь место, где он находится. Несколько ссылок на один объект не означают дублирования состояния объекта, поэтому изменения такого объекта, произведенные через одну из ссылок, видны через все остальные ссылки.

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

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

2.5.3. Эффективная реализация списков

В стандартной библиотеке многих языков программирования существует реализация структуры данных список. Обратите внимание: это не простой тип данных, а структура данных, реализованная на основе простых типов данных. Списки могут сжиматься/расти по мере удаления/добавления элементов.

Реализация списков в виде связных позволяет добавлять и удалять узлы без копирования данных, но обход списка оказывается весьма дорогостоящим (линейное время обхода, то есть сложность порядка O(n), где n — длина списка). В листинге 2.13 приведена подобная реализация списка — NumberLinkedList с двумя функциями: at(), для извлечения значения элемента списка с заданным индексом, и append(), добавляющая значение в конец списка. Эта реализация содержит две ссылки: одну на начало списка, с которого можно начинать обход, и вторую — на конец списка. Благодаря ей можно добавлять новые элементы, не обходя весь список.

Листинг 2.13. Реализация связного списка

 

 

Как видим, функция append() в данном случае реализована очень эффективно, поскольку должна лишь добавить узел в хвост списка и сделать этот новый узел хвостовым. С другой стороны, функция at() начинает с головы списка и проходит по ссылкам next вплоть до достижения искомого узла.

В листинге 2.14 мы сравним это с реализацией на основе массива, в которой доступ к элементу производится эффективно, а вот добавление элемента является дорогостоящей операцией.

Листинг 2.14. Реализация списка на основе массива

 

Здесь доступ к элементу с заданным индексом означает просто выбор элемента из базового массива number по индексу. А вот добавление нового значения становится непростой операцией.

1. Необходимо выделить память под новый массив, на один элемент больше текущего.

2. Необходимо скопировать все элементы из текущего массива в новый.

3. Далее новое значение нужно добавить в новый массив в качестве последнего элемента.

4. Текущий массив следует заменить новым.

Копирование всех элементов массива при каждом добавлении нового элемента, скажем прямо, не самая эффективная реализация.

На практике большинство библиотек реализуют списки в виде массивов с не­которым запасом места. Выбирается больший размер массива, чем требуется изначально, поэтому новые элементы можно добавить, не прибегая к созданию нового массива и копированию данных. При заполнении массива выделяется память под новый массив, правда, двойного размера, и элементы копируются в него (рис. 2.9).

 

Рис. 2.9. Список на основе массива, содержащий девять элементов, но потенциально вмещающий 16. В него можно добавить еще семь элементов, прежде чем придется переносить данные в новый, больший массив

Благодаря такому эвристическому алгоритму вместимость массива растет экспоненциально, поэтому данные не приходится копировать так часто, как если бы массив наращивался по одному элементу за раз (листинг 2.15).

Листинг 2.15. Реализация списка на основе массива с расширенной вместимостью

 

 

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

2.5.4. Бинарные деревья

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

Один из вариантов: представить бинарное дерево с помощью массива. На первом уровне дерева, корневом, содержится не более одного узла. На втором — не более двух: дочерние узлы корневого. На третьем — не более четырех: дочерние узлы двух узлов предыдущего уровня и т.д. В общем случае у дерева с N уровнями может быть не более 1 + 2 + ... + 2N – 1 узлов, что равняется 2N – 1.

Бинарное дерево можно хранить в массиве, расположив в нем уровни один за другим. Если дерево не полное (не на всех уровнях присутствуют все возможные узлы), то мы будем отмечать недостающие узлы undefined. Преимущество этого представления — легкость перехода от родительского узла к дочерним: если родительский узел располагается в массиве по индексу i, то левый дочерний узел будет находиться по индексу 2*i, а правый — 2*i+1.

На рис. 2.10 показано представление бинарного дерева с помощью массива фиксированной длины.

 

Рис. 2.10. Представление бинарного дерева с помощью массива фиксированной длины. Отсутствующий узел (правый дочерний узел узла 2) соответствует неиспользуемому элементу массива. Связь «предок — потомок» между узлами неявная, поскольку индекс дочернего узла можно вычислить на основе индекса родительского узла, и наоборот

Добавление узла также происходит достаточно эффективно, если не меняется количество уровней дерева. Однако при добавлении нового уровня необходимо не только скопировать все дерево, но и удвоить размер массива, чтобы хватило места для всех возможных узлов, как показано в листинге 2.16. Это аналогично эффективной реализации списка.

Листинг 2.16. Реализация бинарного дерева на основе массива

 

У этой реализации есть недостаток: в случае разреженных деревьев требуемый объем дополнительного пространства может оказаться неприемлемым (рис. 2.11).

 

Рис. 2.11. Для корректного представления разреженного бинарного дерева, содержащего всего три узла, тем не менее требуется массив из семи элементов. А если у узла 9 появится дочерний узел, то размер массива вырастет до 15

Из-за избыточного расхода памяти для более компактного представления бинарных деревьев обычно используются ссылочные структуры данных (листинг 2.17). При этом в каждом узле хранятся значение и ссылки на дочерние узлы.

При такой реализации дерево представлено ссылкой на свой корневой узел. С этой отправной точки можно достичь любого узла дерева, следуя по левым/правым дочерним узлам. Для добавления узла в произвольном месте достаточно выделить под него память и задать значение свойства left или right его родительского узла. На рис. 2.12 показано представление разреженного дерева с помощью ссылок.

 

Рис. 2.12. Представление разреженного дерева с помощью ссылок. Схема справа демонстрирует структуру данных узла в виде значения, ссылки на левый и правый дочерний узлы

Листинг 2.17. Компактная реализация бинарного дерева

 

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

В общем случае для представления разреженных структур данных, в которых может быть множество «пропусков», а элементы могут добавляться в различные места, гораздо лучше подходит вариант, когда одни элементы ссылаются на другие. Размещение же всей структуры данных в массиве фиксированной длины чревато неприемлемыми накладными расходами.

2.5.5. Ассоциативные массивы

Некоторые языки программирования предоставляют встроенную поддержку синтаксиса и других простых типов структур данных. Один из часто встречающихся подобных типов — ассоциативный массив (associative array), также известный под названиями «словарь» (dictionary) и «хеш-таблица» (hash table). Этот тип структуры данных представляет собой набор пар «ключ — значение» и обеспечивает эффективное извлечение значения по ключу.

Вопреки тому, что вы могли подумать при чтении предыдущих примеров, массивы JavaScript/TypeScript — ассоциативные. В этих языках программирования нет простого типа данных, соответствующего массиву фиксированной длины. Наши примеры кода демонстрируют, как можно реализовать структуры данных на основе массивов фиксированной длины. Массивы фиксированной длины предполагают чрезвычайно эффективный доступ по индексу и неизменяемый размер. В случае JavaScript/TypeScript этого нет. Мы рассматриваем тут массивы фиксированной длины вместо ассоциативных потому, что последние можно реализовать с помощью обычных массивов и ссылок. Для наглядности мы рассматриваем массивы TypeScript как массивы фиксированной длины, чтобы примеры кода можно было непосредственно перенести на большинство других популярных языков программирования.

В таких языках программирования, как Java и C#, массивы и ссылки являются простыми типами данных, а словари и хеш-карты входят в стандартную библиотеку. В JavaScript и Python ассоциативные массивы — простые типы данных, но среды выполнения также реализуют их на основе массивов и ссылок. Массивы и ссылки — низкоуровневые конструкции, отражающие определенные схемы размещения данных в оперативной памяти и модели доступа, в то время как ассоциативные массивы являются высокоуровневыми абстракциями.

Ассоциативные массивы часто реализуются как массивы фиксированной длины, элементами которых являются списки. Хеш-функция принимает на входе ключ произвольного типа и возвращает индекс в массиве фиксированной длины. Пара «ключ — значение» добавляется в список или извлекается из него по заданному индексу в массиве. Списки используются потому, что хеш нескольких ключей может соответствовать одному индексу (рис. 2.13).

 

Рис. 2.13. Реализация ассоциативного массива в виде массива списков. Данный экземпляр содержит соответствия «ключ — значение»: 0 → 10, 2 → 9, 5 → 10 и 42 → 0

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

Хорошая функция хеширования обеспечивает равномерное распределение ключей по спискам, чтобы длины списков были примерно равны.

2.5.6. Соотношения выгод и потерь различных реализаций

В предыдущем подразделе мы увидели, что массивов и ссылок вполне достаточно для реализации других структур данных. В зависимости от ожидаемых паттернов обращения (например, частоты чтения относительно частоты записи) и формы данных (плотные или разреженные) можно подобрать нужные простые типы для компонентов структуры данных и объединить их так, чтобы получилась наиболее эффективная реализация.

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

2.5.7. Упражнение

Какая структура данных лучше подойдет для обращения к элементам в случайном порядке?

А. Связный список.

Б. Массив.

В. Словарь.

Г. Очередь.

Резюме

• Функции, которые никогда ничего не возвращают (работают бесконечно или генерируют исключения), следует объявлять как возвращающие пустой тип. Пустой тип можно реализовать в виде класса, не допускающего создания экземпляров, или как перечисляемый тип, не содержащий элементов.

• Функции, которые не возвращают никакого осмысленного результата по завершении выполнения, следует объявлять как возвращающие единичный тип (в большинстве языков программирования — void). Единичный тип можно реализовать в виде класса-одиночки или перечисляемого типа, содержащего один элемент.

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

• Возможно переполнение целочисленных типов фиксированной ширины. Поведение по умолчанию при переполнении зависит от языка программирования. А желаемое поведение зависит от конкретного сценария использования.

• Представление чисел с плавающей точкой — приближенное, так что лучше не сравнивать значения на равенство, а проверять, не отстоят ли они дальше EPSILON друг от друга.

• Текст состоит из графем, представление которых строится из одной или нескольких кодовых точек Unicode; каждая из них кодируется одним байтом или более. Библиотеки для операций над строками ограждают нас от всех сложностей кодирования и представления строк, так что лучше полагаться на них, а не производить операции над текстом напрямую.

• Массивы фиксированной длины и ссылки — стандартные «строительные блоки» структур данных. В зависимости от паттернов обращения к данным и степени их плотности можно использовать те или другие либо их сочетание для эффективной реализации любой, сколь угодно сложной структуры данных.

Ответы к упражнениям

2.1. Проектирование функций, не возвращающих значений

1. В — функция set() не возвращает никакого осмысленного значения, так что единичный тип void отлично подойдет в качестве возвращаемого типа.

2. А — функция set() никогда ничего не возвращает, поэтому в качестве возвращаемого типа отлично подойдет пустой тип never.

2.2. Булева логика и сокращенные схемы вычисления

Б — значение счетчика увеличивается только один раз, поскольку функция возвращает false, так что булево выражение вычисляется по сокращенной схеме.

2.3. Распространенные ловушки числовых типов данных

1. В — из-за округления чисел с плавающей точкой результат вычисления выражения — false.

2. В — оптимальным поведением в данном случае будет выдача ошибки, поскольку идентификаторы должны быть уникальными.

2.4. Кодирование текста

1. Г — UTF-8 — кодировка переменной длины.

2. В — UTF-32 — кодировка фиксированной длины; все символы кодируются четырьмя байтами.

2.5. Создание структур данных на основе массивов и ссылок

Б — для произвольного доступа лучше подходят массивы.

Глава 3. Составные типы данных

В этой главе

• Объединение типов в составные типы данных.

• Объединение типов в XOR-типы данных.

• Реализация паттерна проектирования «Посетитель».

• Алгебраические типы данных.

В главе 2 мы рассмотрели некоторые простые типы данных — строительные блоки системы типов. В текущей главе мы обсудим способы их сочетания в целях описания новых типов данных.

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

Далее мы обсудим XOR-типы данных (either-or types) (строго дизъюнктивные типы), содержащие ровно одно значение одного или нескольких типов. Мы рассмотрим такие распространенные типы данных, как опционалы, XOR-типы данных и вариантные типы данных, а также некоторые их приложения. Мы увидим, например, почему возвращать результат или ошибку обычно безопаснее, чем возвращать результат и ошибку.

В качестве приложения XOR-типов данных мы рассмотрим паттерн проектирования «Посетитель» и сравним реализацию, использующую иерархии классов, с реализацией, в которой для хранения объектов и выполнения операций над ними используется вариантный тип данных.

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

3.1. Составные типы данных

Простейший способ сочетания типов данных — группировка их в новые типы. Возьмем пару координат x и y на плоскости. Тип обеих координат x и y — number. У точки на плоскости есть обе координаты (x и y), поэтому два типа в ней объединяются в третий, значениями которого служат пары чисел.

В общем случае объединение одного или нескольких типов подобным образом приводит к созданию нового типа данных, значениями которого являются все возможные сочетания составляющих его типов (рис. 3.1).

 

Рис. 3.1. Объединение двух типов таким образом, чтобы итоговый содержал по одному значению из каждого этого типа. Каждый эмодзи представляет значение одного из этих типов. Скобки отражают тот факт, что значения объединенного типа являются парами значений исходных типов

Обратите внимание: речь идет про объединение значений типов, а не операций над ними. Комбинирование операций мы обсудим, когда будем рассматривать элементы объектно-ориентированного программирования в главе 8. Пока же ограничимся значениями.

3.1.1. Кортежи

Допустим, нам нужно вычислить расстояние между двумя точками, заданными в виде пар координат. Можно определить функцию, которая принимает координаты x и y сначала первой точки, а затем второй и вычисляет расстояние между ними, как показано в листинге 3.1.

Листинг 3.1. Расстояние между двумя точками

function distance(x1: number, y1: number, x2: number, y2: number)

    : number {

    return Math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2);

}

Этот код работает, но не идеален: координата x1, если речь идет о точках, не имеет смысла без соответствующей координаты y1. Скорее всего, нужно будет производить операции над точками во многих местах нашего приложения. Поэтому вместо того, чтобы передавать отдельно координаты x и y, мы можем сгруппировать их в кортеж (tuple).

Типы-кортежи

Тип-кортеж состоит из набора типов-компонентов, к которым можно обращаться по их позициям в кортеже. Кортежи — способ группировки данных специально для конкретного случая, позволяющий передавать в виде одной переменной несколько значений различных типов.

С помощью кортежей можно передавать пары координат x и y как цельные точки. Это упрощает чтение и написание кода. Чтение — поскольку теперь понятно, что мы имеем дело с точками, а написание — поскольку можно использовать объявление point:Point вместо x:number,y:number, как показано в листинге 3.2.

Листинг 3.2. Расстояние между двумя точками, описанными в виде кортежей

 

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

Кортеж своими руками

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

Рассматривая типы как множества возможных значений, можно сказать, что если координаты x и y могут принимать любые значения из задаваемого типом number множества, то кортеж Point может принимать любое значение из задаваемого парой <number,number> множества пар.

Листинг 3.3. Тип Pair

 

3.1.2. Указание смыслового содержания

Точки вполне можно описывать как пары чисел, но при этом теряется определенная часть смыслового содержания: пара чисел интерпретируется либо как координаты x и y, либо как координаты y и x (рис. 3.2).

 

Рис. 3.2. Два способа интерпретации пары (1, 5): как точка A с координатой x = 1 и координатой y = 5, либо как точка Б с координатой x = 5 и координатой y = 1

До сих пор в наших примерах предполагалось, что первый компонент — координата x, а второй — y. Данное допущение работает, но оставляет возможности для ошибок. Лучше было бы закодировать смысл в саму систему типов, таким образом гарантируя невозможность неправильной интерпретации x как y или y как x. Сделать это можно с помощью так называемого типа-записи (record type).

Типы-записи

Типы-записи аналогично кортежам объединяют значения нескольких других типов. Но вместо того, чтобы обращаться к значениям компонентов в соответствии с их позицией в кортеже, типы-записи позволяют давать компонентам названия и обращаться по ним. Типы-записи в различных языках называются record («запись») или struct («структура»).

Если описать наш тип Point как структуру, то можно будет назначить для двух ее компонентов названия x и y и исключить всякую неоднозначность, как видно из листинга 3.4.

Листинг 3.4. Расстояние между двумя точками, описанными как записи

 

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

3.1.3. Сохранение инвариантов

В языках программирования, где у типов-записей могут быть методы, обычно есть и возможность описания видимости членов этих типов. Член такого типа может быть публичным (public) — доступным из любого места кода, приватным (private) — доступным только в пределах записи и т.д. В TypeScript члены классов по умолчанию публичны.

В общем случае при описании типов-записей, если члены типа не зависят друг от друга и их изменение не приводит к проблемам, их можно смело описывать как публичные. Как раз такая ситуация и имеет место при описании точек как пар координат x и y: координаты могут меняться независимо друг от друга при перемещении точки по плоскости.

Рассмотрим другой пример, в котором члены типа не могут беспроблемно меняться независимо друг от друга: тип данных — для денежных сумм, о котором мы говорили в главе 2, состоящий из количества долларов и центов. Расширим описание этого типа следующими правилами, определяющими корректное количество денег.

• Количество долларов должно представлять собой неотрицательное целое число, подходящее для безопасного представления с помощью типа number.

• Количество центов должно представлять собой неотрицательное целое число, подходящее для безопасного представления с помощью типа number.

• Количество центов не должно превышать 99; каждые следующие 100 центов необходимо преобразовывать в 1 доллар.

Подобные правила, гарантирующие верную структуру значений, называются инвариантами (invariants), поскольку должны соблюдаться при изменении значений, входящих в составной тип данных (compound type). Если сделать члены типа публичными, то внешний код сможет их менять, в результате чего записи могут оказаться сформированы некорректно, как показано в листинге 3.5.

Листинг 3.5. Денежная сумма некорректного вида

 

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

Теперь внешнему коду придется менять значения только через функции as­signDol­lars() и assignCents(), что гарантирует сохранение инвариантов: в случае некорректности передаваемых значений генерируется исключение. Если количество центов превышает 100, то сотни центов преобразуются в доллары.

В целом при отсутствии необходимости сохранять инварианты (как в случае независимых компонентов x и y точки на плоскости) вполне допустимо предоставлять прямой доступ к публичным членам записи. С другой стороны, при наличии набора правил, определяющих, какова корректная форма записи, для ее обновления следует использовать приватные поля и методы, чтобы гарантировать соблюдение этих правил.

Еще один вариант: сделать поля класса неизменяемыми, как показано в листинге 3.7. В этом случае можно обеспечить корректное состояние записи при ее инициа­лизации, а затем разрешить прямой доступ к членам класса, поскольку внешний код все равно не сможет их поменять.

Листинг 3.6. Класс Currency, сохраняющий инварианты

 

Листинг 3.7. Класс Currency с неизменяемыми полями

 

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

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

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

3.1.4. Упражнение

Какое определение точки в 3D-пространстве предпочтительнее?

А. typePoint=[number,number,number];.

Б. typePoint=number|number|number;.

В. typePoint={x:number,y:number,z:number};.

Г. typePoint=any;.

3.2. Выражаем строгую дизъюнкцию с помощью типов данных

До сих пор мы изучали сочетание типов путем такой их группировки, что значение включало по одному значению каждого из типов-компонентов. Другой основной способ сочетания типов — строгая дизъюнкция, при которой значение представляет собой любое одно из возможных наборов значений типов, лежащих в его основе (рис. 3.3).

 

Рис. 3.3. Объединение двух типов таким образом, чтобы итоговый тип содержал значение одного из этих типов

3.2.1. Перечисляемые типы

Начнем с очень простой задачи: кодирования дня недели в системе типов. Можно кодировать день недели в виде числа от 0 до 6, где 0 — первый день недели, а 6 — последний. Это неидеальный вариант, поскольку у разных людей, работающих над кодом, представления о том, какой день недели считать первым, могут различаться. В таких странах, как США, Канада и Япония, первым днем недели считается воскресенье, а в стандарте ISO 8601 и большинстве европейских стран — понедельник (листинг 3.8).

Листинг 3.8. Кодирование дня недели с помощью числа

 

Из этого примера кода очевидно, что обе функции не могут быть правильными одновременно. Если 0 соответствует воскресенью, то функция isWeekend работает неправильно; если же 0 соответствует понедельнику, то некорректна функция isWeekday. К сожалению, автоматически предотвращать подобные ошибки невозможно, поскольку смысл значения 0 не обеспечивается системой типов, а определяется соглашением.

В качестве альтернативного варианта можно объявить набор констант, соответствующих дням недели, и использовать их везде, где ожидается день недели (листинг 3.9).

Эта реализация немного лучше предыдущей, но по-прежнему есть проблема: из объявления функций непонятно, какие значения ожидаются в качестве аргументов типа number. Как разработчику, незнакомому с кодом, догадаться по dayOfWeek:number, что необходимо использовать одну из приведенных констант? Он вообще может не знать, что эти константы определены где-то в каком-то модуле, и вместо них применять числа, как в нашем первом примере в листинге 3.8. Кроме того, не исключено, что кто-нибудь вызовет такую функцию с совершенно недопустимыми аргументами, например –1 или 10. Лучшим решением будет объявить для дней недели перечисляемый тип данных (листинг 3.10).

Листинг 3.9. Кодирование дня недели с помощью констант

 

Листинг 3.10. Кодирование дня недели с помощью перечисляемого типа данных

 

При таком подходе дни недели непосредственно кодируются в перечисляемом типе данных, что имеет два преимущества. Во-первых, отсутствует неоднозначность относительно того, какое число соответствует понедельнику и какое — воскресенью, поскольку все явно прописано в коде. Во-вторых, из объявления функции, ожидающей dayOfWeek:DayOfWeek, совершенно ясно, что необходимо передать в качестве аргумента не число, а член перечисления DayOfWeek.

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

3.2.2. Опциональные типы данных

Допустим, нам нужно преобразовать переданное пользователем значение типа string в DayOfWeek. Если полученную строку можно интерпретировать как день недели, то необходимо вернуть значение DayOfWeek, в противном случае следует явным образом сообщить, что день недели — undefined. В TypeScript это можно реа­лизовать с помощью оператора |, который позволяет сочетать типы, как показано в листинге 3.11.

Листинг 3.11. Разбор входных данных с преобразованием в DayOfWeek или undefined

 

Функция parseDayOfWeek() возвращает DayOfWeek или undefined, а функция useInput вызывает ее и пытается развернуть результат, занося в журнал сообщение об ошибке или получая пригодное для использования значение DayOfWeek.

Опциональные типы данных

Опциональный тип данных (optional type), или просто опционал, отражает (вероятно, отсутствующее) значение другого типа T. Экземпляр опционального типа может содержать (любое) значение типа T или специальное значение, указывающее на отсутствие значения типа T.

Опционал своими руками

Некоторые из самых широко используемых языков программирования до сих пор не имеют синтаксической поддержки сочетания типов подобным образом, но основные конструкции доступны в виде библиотек. Наш пример с DayOfWeek или undefined представляет собой опциональный тип. Опционал содержит либо значение лежащего в его основе типа, либо индикатор отсутствия значения.

Опциональный тип данных обычно служит оберткой для другого типа, передаваемого в качестве обобщенного аргумента типа, и включает несколько методов: hasValue(), указывающий, содержит ли объект реальное значение, и getValue(), который возвращает значение. Попытка вызвать метод getValue(), когда значение отсутствует, приводит к генерации исключения, как показано в листинге 3.12.

Листинг 3.12. Опциональный тип данных

 

В других языках, где нет оператора типа |, который позволяет задать тип T|undefined, можно воспользоваться типом, допускающим неопределенное значение. Тип, допускающий неопределенное значение (nullable type), может принимать любое значение типа либо значение null, отражающее отсутствие значения.

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

Отличие в том, что использование null может приводить к ошибкам (о чем сказано во врезке «Ошибка стоимостью миллиард долларов» ниже), поскольку непонятно, может ли конкретная переменная принимать значение null. Приходится добавлять проверки на null по всему коду или рисковать разыменованием переменной со значением null, приводящим к ошибке во время выполнения. Идея опционального типа данных состоит в расцеплении null с диапазоном допустимых значений. Всякий раз, встречая опционал, мы знаем, что он может не содержать никакого значения. И лишь после проверки, что в нем действительно содержится значение, мы можем «распаковать» опционал и получить переменную типа, лежащего в его основе. С этого момента мы точно знаем, что переменная не может быть null. Это различие отражается в системе типов: тип переменной (DayOfWeek|undefined или Optional<DayOfWeek>), которая «может быть null», отличается от «распакованного» значения, которое, как мы знаем, не может быть null (DayOfWeek). Несовместимость опционала и лежащего в его основе типа очень удобна, поскольку гарантирует невозможность случайно использовать опционал (в котором может не содержаться значения) вместо лежащего в его основе типа без распаковки значения явным образом.

Ошибка стоимостью миллиард долларов Знаменитый специалист по теории вычислительной техники и лауреат премии Тьюринга Тони Хоар называет нулевые ссылки своей ошибкой стоимостью миллиард долларов. Цитируют следующее его высказывание: «Я называю изобретение нулевой ссылки в 1965 году своей ошибкой стоимостью миллиард долларов. В то время я проектировал первую комплексную систему типов для ссылок в объектно-ориентированном языке. Я ставил перед собой цель обеспечить абсолютную безопасность всех ссылок путем автоматической проверки их компилятором. Но я поддался искушению включить в язык нулевую ссылку просто потому, что ее было так легко реализовать. Это привело к бесчисленным ошибкам, уязвимостям и системным сбоям, причинившим, вероятно, за последние 40 лет неприятностей и убытков на миллиард долларов». После десятилетий ошибок, связанных с разыменованием null, стало очевидно, что лучше будет не считать null (отсутствие значения) допустимым значением типа.

3.2.3. Результат или сообщение об ошибке

Расширим наш пример преобразования строки DayOfWeek так, чтобы при невозможности определить значение DayOfWeek возвращать не просто неопределенное значение, а более подробную информацию об ошибке. Желательно различать случай, когда строка пуста и мы не можем произвести ее разбор. Это удобно, если данный код используется для элемента управления текстовым вводом, для отображения пользователю различных сообщений в зависимости от ошибки (например, Please enter a day of week (Пожалуйста, введите день недели) или Invalid day of week (Недопустимый день недели)).

Часто встречающийся антипаттерн состоит в возврате иDayOfWeek, и кода ошибки, как показано в листинге 3.13. Если код ошибки указывает на успешное выполнение, то можно использовать значение DayOfWeek. Если же он указывает на ошибку, то значение DayOfWeek некорректно и его не следует применять.

Листинг 3.13. Возвращаем из функции результат и ошибку

 

Этот вариант неидеален, ведь ничего не мешает нам задействовать DayOfWeek, даже если случайно забыть проверить код ошибки. Кроме того, может исполь­зоваться значение по умолчанию, и отнюдь не всегда мы различим, допустимо ли оно. Мы можем передать ошибку далее по системе, например записать ее в базу данных, не отдавая себе отчета, что это значение вообще не следовало применять.

Если посмотреть на это с точки зрения типов данных как множеств, то можно считать, что наш результат содержит комбинацию всех возможных кодов ошибок и всех возможных результатов (рис. 3.4).

 

Рис. 3.4. Все возможные значения типа Result как сочетание InputError и DayOfWeek. Всего 21 значение (3 InputError x 7 DayOfWeek)

Вместо этого желательно возвращать либо ошибку, либо допустимое значение. Если нам это удастся, то множество возможных значений резко сократится и будет исключен риск случайно использовать компонент DayOfWeek типа Result, в котором компонент InputError имеет значение NoInput или Invalid (рис. 3.5).

 

Рис. 3.5. Все возможные значения типа Result как сочетание InputError или DayOfWeek. Всего девять значений (2 InputError + 7 DayOfWeek). Больше не требуется InputError со значением OK, поскольку само наличие значения DayOfWeek указывает на отсутствие ошибки

XOR-тип данных своими руками

Наш XOR-тип данных Either будет оберткой для двух типов, TLeft и TRight, где TLeft станет служить для хранения типа ошибки, а TRight — типа допустимого значения (если ошибки нет, то значение «правильное»8) (листинг 3.14). Напомню, в некоторых языках программирования это включено в стандартную библиотеку, но при необходимости можно легко реализовать подобный тип данных.

Листинг 3.14. Тип Either

 

В языках, где отсутствует оператор типа |, можно просто использовать значение общего типа, например Object в Java и C#. Преобразование обратно в типы TLeft и TRight осуществляется методами getLeft() и getRight() соответственно.

С помощью подобного типа можно усовершенствовать нашу реализацию par­seDayOfWeek() так, чтобы она возвращала результат типа Either<InputError,DayOfWeek>, делая невозможным дальнейшее распространение по системе некорректного или используемого по умолчанию значения DayOfWeek. Если функция возвращает InputError, то в результате отсутствует DayOfWeek и попытка извлечь его с помощью вызова getLeft() приводит к генерации ошибки (листинг 3.15).

Нам опять приходится явным образом распаковывать значение. Если мы знаем точно, что значение допустимое (isLeft() возвращает true), и извлекаем его с помощью метода getLeft(), то гарантированно получим корректные данные.

Листинг 3.15. Возвращаем из функции результат или ошибку

 

Эта усовершенствованная реализация использует систему типов для исключения некорректных состояний, каких как (NoInput,Sunday), из которых мы могли случайно применить значение Sunday. Кроме того, не требуется InputError со значением OK, поскольку при успешном разборе сообщение об ошибке отсутствует.

Исключения

Генерация исключения при ошибке — прекрасный пример того, как возвращается результат или ошибка: функция либо возвращает результат, либо генерирует исключение. В некоторых случаях использовать исключения нельзя и лучше задействовать тип Either. Это пригодится в следующих ситуациях: для распространения ошибки по процессам или потокам выполнения; в качестве принципа проектирования, когда сама ошибка не носит характера исключения (частый случай при обработке вводимых пользователем данных); при вызове API операционной системы, использующих коды ошибок, и т.д. В подобных случаях, когда генерация исключения невозможна или нежелательна, но необходимо сообщить о наличии значения или неудачном разборе, лучше всего кодировать подобное сообщение в виде «значение или ошибка», а не «значение и ошибка».

Если же генерация исключений приемлема, то можно использовать их для дополнительной уверенности, что мы не получим в итоге некорректный результат и ошибку. При генерации исключения функция больше не выполняет «обычный» возврат, передавая значение вызывающей стороне с помощью оператора return. Вместо этого объект исключения проходит по системе до тех пор, пока не встретится соответствующий оператор catch. Таким образом, мы получаем или результат, или исключение. Мы не станем описывать подробно генерацию исключений, поскольку, несмотря на то что во многих языках программирования есть возможности генерации и перехвата исключений, типы исключения не выделяются ничем особенным.

3.2.4. Вариантные типы данных

Мы рассмотрели опциональные типы данных, которые содержат значение определенного типа либо не содержат никакого значения. Затем изучили XOR-типы данных, содержащие значение либо TLeft, либо TRight. Обобщением их являются вариантные типы данных (variant types).

Вариантные типы данных

Вариантные типы данных, известные также как маркированные объединения (tagged unions), могут содержать значение любого из нескольких типов, лежащих в их основе. Маркированные потому, что, даже если диапазоны значений таких типов пересекаются, мы все равно сможем точно сказать, к какому из них относится конкретное значение.

Рассмотрим в листинге 3.16 пример с набором геометрических фигур. У каждой из них свой набор свойств и метка (реализованная в виде свойства kind). Опишем тип, представляющий собой объединение типов всех фигур. Далее при необходимости, например, визуализировать эти фигуры можно воспользоваться их свойствами kind для определения того, какой фигурой является конкретный экземпляр, и привести его к соответствующему типу фигуры. Этот процесс аналогичен распаковке в предыдущих примерах.

Листинг 3.16. Маркированное объединение фигур

 

В предыдущем примере член kind во всех классах отражает метку, указывающую фактический тип значения. Значение поля shape.kind указывает, является ли экземпляр Shape на самом деле Point, Circle или Rectangle. Можно также реализовать обобщенный вариантный тип данных, который самостоятельно отслеживает тип данных и не требует хранения метки в самих типах.

Реализуем простой вариантный тип данных, способный хранить значение одного из трех типов данных и отслеживать фактически хранимый тип на основе индекса типа.

Вариантный тип данных своими руками

Различные языки программирования предоставляют разные возможности обобщения и проверки типов. Так, одни языки допускают переменное количество обобщенных аргументов (поэтому вариантные типы данных могут основываться на любом числе типов). Другие дают различные способы определения, к какому типу относится значение, на этапе как компиляции, так и выполнения.

У следующей реализации на TypeScript есть свои достоинства и недостатки, которые, возможно, отличаются от других языков программирования (листинг 3.17). Она является отправным пунктом для создания обобщенного вариантного типа данных. Однако, скажем, в Java или C# ее нужно реализовывать иначе. TypeScript, например, не поддерживает перегрузки методов, а в других языках можно обойтись одной функцией make(), перегруженной для каждого из обобщенных типов.

Листинг 3.17. Тип данных Variant

class Variant<T1, T2, T3> {

    readonly value: T1 | T2 | T3;

    readonly index: number;

 

    private constructor(value: T1 | T2 | T3, index: number) {

        this.value = value;

        this.index = index;

    }

 

    static make1<T1, T2, T3>(value: T1): Variant<T1, T2, T3> {

        return new Variant<T1, T2, T3>(value, 0);

    }

 

    static make2<T1, T2, T3>(value: T2): Variant<T1, T2, T3> {

        return new Variant<T1, T2, T3>(value, 1);

    }

 

    static make3<T1, T2, T3>(value: T3): Variant<T1, T2, T3> {

        return new Variant<T1, T2, T3>(value, 2);

    }

}

Эта реализация берет на себя хранение меток, так что теперь можно исключить их из типов геометрических фигур (листинг 3.18).

Может показаться, что эта реализация не имеет особых преимуществ; мы пришли к использованию числовых меток и произвольно выбрали метку 0 для Point и 1 — для Circle. Возможно, вы недоумеваете, почему мы вместо этого не применили для наших фигур иерархию классов с базовым методом, который реализовывал бы каждый тип.

Листинг 3.18. Объединение геометрических фигур как вариантный тип данных

 

Для решения этой задачи нам понадобится изучить паттерн проектирования «Посетитель» и способы его реализации.

3.2.5. Упражнения

1. Пользователи передают значение для выбора из нескольких цветов (красный, зеленый и синий). Каким должен быть тип этого значения?

А. number с Red=0,Green=1,Blue=2.

Б. string с Red="Red",Green="Green",Blue="Blue".

В. enumColors{Red,Green,Blue}.

Г. typeColors=Red|Green|Blue, где цвета являются классами.

2. Значение какого типа должна возвращать функция, получающая на входе строку и производящая разбор этой строки в числовое значение? Функция не генерирует исключений.

А. number.

Б. number|undefined.

В. Optional<number>.

Г. Или Б, или В.

3. В операционных системах коды ошибок обычно представляют собой числовые значения. Каков должен быть возвращаемый тип функции, которая может возвращать либо числовое значение, либо числовой код ошибки?

А. number.

Б. {value:number,error:number}.

В. number|number.

Г. Either<number,number>.

3.3. Паттерн проектирования «Посетитель»

Обсудим паттерн «Посетитель» и обход элементов документа — сначала с точки зрения объектно-ориентированного программирования, а затем с помощью реализованного нами обобщенного типа маркированного объединения. Если вы не знакомы с этим паттерном, то не волнуйтесь, я расскажу, что он собой представляет, по мере работы над примером.

Мы начнем с «наивной» реализации, увидим, как паттерн позволяет усовершенствовать архитектуру, а затем рассмотрим альтернативную реализацию, в которой не требуются иерархии классов.

Начнем с трех элементов документа: с абзаца (paragraph), изображения (picture) и таблицы (table). Нам нужно либо визуализировать их на экране, либо обеспечить их прочтение вслух утилитой чтения с экрана для слабовидящих пользователей.

3.3.1. «Наивная» реализация

Один из возможных подходов — создание общего интерфейса, чтобы все элементы умели визуализироваться на экране или обеспечивать чтение вслух, как показано в листинге 3.19.

Листинг 3.19. «Наивная» реализация

 

С точки зрения архитектуры это не лучший подход. В элементах документа должна храниться информация, описывающая его содержимое, например текст или изображения, они не должны отвечать за все остальное, скажем за визуализацию и доступ. Наличие кода для визуализации и обеспечения доступа в каждом из элементов документа сильно раздувает код. Хуже того, если нужно добавить новую возможность (например, возможность печати), то для ее реализации придется модифицировать описание интерфейса и всех реализующих его классов.

3.3.2. Использование паттерна «Посетитель»

Данный паттерн описывает операцию, которую необходимо выполнить над элементами объектной структуры данных. Он позволяет описать новую операцию без изменения классов элементов, над которыми она производится.

В нашем примере, приведенном в листинге 3.20, данный паттерн позволяет добавить новую возможность, вообще не трогая код элементов документа. Реализовать это можно с помощью механизма двойной диспетчеризации (double-dispatch mechanism), при котором элементы документа получают в качестве параметра объект-посетитель, после чего передают себя самих в него. Посетитель знает, как следует обрабатывать каждый из элементов (визуализировать, прочитать вслух и т.д.), и выполняет нужную операцию над переданным ему экземпляром элемента (рис. 3.6).

 

Рис. 3.6. Паттерн «Посетитель». Благодаря интерфейсу IDocumentItem у каждого из элементов документа есть метод accept(), принимающий в качестве аргумента экземпляр IVisitor. Он обеспечивает возможность обработки любым объектом-посетителем всех возможных типов элементов документа. Все элементы реализуют метод accept() для передачи себя посетителю. Благодаря этому паттерну можно разделять обязанности, такие как визуализация на экране и обеспечение доступа, между отдельными компонентами (посетителями), абстрагируя их от элементов документа

Листинг 3.20. Обработка с помощью паттерна «Посетитель»

 

Термин «двойная диспетчеризация» обязан своим названием тому факту, что благодаря интерфейсу IDocumentItem сначала вызывается соответствующий метод accept(); а затем в соответствии с полученным аргументом IVisitor вызывается соответствующая операция.

Теперь посетитель может пройти по набору объектов IDocumentItem, обрабатывая их с помощью вызова метода accept() для каждого из них. Ответственность за обработку теперь лежит на посетителях вместо самих элементов. Добавление нового посетителя никак не влияет на элементы документа. Новый посетитель должен лишь реализовать интерфейс IVisitor, и элементы документа примут его так же, как и любой другой.

Новый класс-посетитель Printer мог бы, например, реализовывать логику для распечатки абзаца, изображения и таблицы в методах visitParagraph(), visitPic­ture() и visitTable(). И элементам документа не понадобятся никакие изменения, чтобы стать доступными для печати.

Данный пример — классическая реализация паттерна «Посетитель». Теперь посмотрим, как выполнить нечто похожее с помощью вариантного типа данных.

3.3.3. Посетитель-вариант

Для начала снова обратимся к нашему обобщенному вариантному типу данных и реализуем функцию visit(). Она принимает в качестве аргументов объект вариантного типа данных и набор функций по одной для каждого типа и (в зависимости от значения, имеющегося в варианте) применяет к нему соответствующую функцию (листинг 3.21).

Листинг 3.21. Посетитель-вариант

 

Поместив элементы документа в вариантный тип данных, можно будет воспользоваться этой функцией для выбора соответствующего метода посетителя. При этом никаким из наших классов больше не нужно реализовывать определенные интерфейсы: ответственность за подбор нужного метода-обработчика для элемента документа возлагается теперь на обобщенную функцию visit().

При таком подходе механизм двойной диспетчеризации расцепляется с используемыми нами типами и переносится в посетитель-вариант. Оба они представляют собой обобщенные типы данных, которые можно использовать повторно для предметных областей различных задач (листинг 3.22). Преимущество этого подхода таково: посетители отвечают лишь за обработку, а элементы документа — только за хранение данных предметной области (рис. 3.7).

Листинг 3.22. Альтернативный способ обработки с помощью посетителя-варианта

 

Кроме того, предполагается, что вариантный тип данных будет использоваться с помощью созданной нами функции visit(). Выяснение, какой именно тип содержит вариантный тип, на основе поля index чревато ошибками. Но обычно мы не извлекаем значение из этого типа, а применяем к нему различные функции с помощью метода visit(). Таким образом, чреватый ошибками выбор производится в реализации метода visit(), и мы можем об этом не думать. Инкапсуляция небезопасного в смысле ошибок кода в повторно используемом компоненте — рекомендуемая практика для снижения риска, поскольку позволяет положиться во множестве сценариев использования на одну проверенную реализацию.

 

Рис. 3.7. Упрощенный паттерн «Посетитель»: теперь от элементов документа и посетителей не требуется реализация никаких интерфейсов. Сравните с рис. 3.6. Ответственность за подбор нужного метода-обработчика для элемента документа инкапсулируется в методе visit(). Как видно из рисунка, типы не связаны, что хорошо, поскольку программа становится более гибкой

Преимущество применения посетителя на основе вариантного типа данных вместо традиционной объектно-ориентированной реализации — полное разделение объектов предметной области с посетителями. Нам больше не требуется даже метод accept(), а элементы документа могут вообще ничего не знать о коде, который будет обрабатывать их. Не должны они и соответствовать какому-либо конкретному интерфейсу, такому как IDocumentItem в нашем примере. А все потому, что в типе Variant и его функции visit() инкапсулирован связующий код, который подбирает для фигур соответствующий посетитель.

3.3.4. Упражнение

Наша реализация метода visit() возвращает void. Расширьте ее так, чтобы она, получая на входе Variant<T1,T2,T3>, возвращала Variant<U1,U2,U3> с помощью одной из трех функций: (value:T1)=>U1, или (value:T2)=>U2, или (value:T3)=>U3.

3.4. Алгебраические типы данных

Возможно, вы уже слышали термин «алгебраические типы данных» (algebraic data types, ADT). Они представляют собой способы сочетания типов в системе типов. На самом деле именно их мы и обсуждали на протяжении всей этой главы. ADT позволяют сочетать типы двумя способами, создавая типы-произведения и типы-суммы.

3.4.1. Типы-произведения

Типы-произведения (product types) — то, что мы называли в этой главе составными типами данных (compound types). Кортежи и записи относятся к типам-произведениям, поскольку их значения являются декартовыми произведениями составляющих их типов. Объединение типа A={a1,a2} (тип A с возможными значениями a1 и a2) и типа B={b1,b2} (тип B с возможными значениями b1 и b2) представляет собой тип-кортеж <A,B> вида AxB={(a1,b1),(a1,b2),(a2,b1),(a2,b2)}.

Типы-произведения

Типы-произведения объединяют несколько типов в новый тип, в котором хранится по значению каждого из этих типов. Тип-произведение типов A, B и C — который можно записать в виде A x B x C — содержит значение типа A, значение типа B и значение типа C. Примерами типов-произведений могут служить кортежи и записи. Кроме того, записи позволяют присваивать их компонентам осмысленные названия.

Типы-записи должны быть вам хорошо знакомы, ведь это обычно первый метод сочетания типов, изучаемый программистами-новичками. В последнее время в наиболее широко востребованных языках программирования начали применяться кортежи, но разобраться с ними совсем не сложно. Они очень похожи на записи. Отличие состоит в том, что нельзя дать названия их членам и их обычно можно описывать аналогично встроенным (inline) функциям/выражениям, указывая составляющие кортеж типы. В TypeScript, например, тип-кортеж, состоящий из двух значений типа number, можно описать в виде [number,number].

Сначала мы обсудили типы-произведения, поскольку они должны быть более привычными для вас. Практически во всех языках программирования есть способы описания типов записей. А вот синтаксическая поддержка типов-сумм присутствует в меньшем числе широко используемых языков программирования.

3.4.2. Типы-суммы

Типы-суммы (sum types) — то, что мы называли в этой главе XOR-типами данных (either-or types). Они объединяют несколько типов в один, который может содержать значение любого из типов-компонентов, но только одного из них. Объединение типа A={a1,a2} и типа B={b1,b2} представляет собой тип-сумму A|B вида A+B={a1,a2,b1,b2}.

Типы-суммы

Типы-суммы объединяют несколько типов в новый тип, в котором хранится значение одного любого из этих типов. Тип-сумма типов A, B и C — который можно записать в виде A + B + C — содержит значение типа A, или значение типа B, или значение типа C. Примерами типов-сумм могут служить опционалы и вариантные типы данных.

Как мы видели, в языке TypeScript есть оператор типа |, но часто встречающиеся типы-суммы, например Optional, Either и Variant, реализуются и без его помощи. Эти типы обеспечивают широкие возможности представления результата или ошибки и закрытых множеств типов, предоставляя различные способы реализации распространенного паттерна «Посетитель».

В общем случае типы-суммы позволяют хранить значения не связанных друг с другом типов в одной переменной. Как показано в примере с паттерном «Посетитель», в качестве объектно-ориентированной альтернативы типам-суммам можно использовать общий базовый класс или интерфейс, но такое решение плохо масштабируется. Сочетание и комбинирование разных типов в различных местах приложения неизбежно приведет к огромному количеству интерфейсов или базовых классов, которые не слишком пригодны для повторного использования. Типы-суммы — это простой и аккуратный способ сочетания типов для подобных сценариев.

3.4.3. Упражнения

1. Какую разновидность типа описывает следующий оператор?

let x: [number, string] = [42, "Hello"];

А. Простой тип данных.

Б. Тип-сумму.

В. Тип-произведение.

Г. И тип-сумму, и тип-произведение.

2. Какую разновидность типа описывает следующий оператор?

let y: number | string = "Hello";

А. Простой тип данных.

Б. Тип-сумму.

В. Тип-произведение.

Г. И тип-сумму, и тип-произведение.

3. Допустим, заданы типы enumTwo{A,B} и enumThree{C,D,E}. Каково количество возможных значений типа-кортежа [Two,Three]?

А. 2.

Б. 5.

В. 6.

Г. 8.

4. Допустим, заданы типы enumTwo{A,B} и enumThree{C,D,E}. Каково количество возможных значений типа Two|Three?

А. 2.

Б. 5.

В. 6.

Г. 8.

Резюме

• Типы-произведения — это кортежи и записи, группирующие значения из нескольких типов.

• Записи позволяют задать названия членов записи, то есть придать им определенный смысл. Кроме того, оставляют меньше возможностей для путаницы, чем кортежи.

• Инварианты — правила, которым должна соответствовать корректно заданная запись. Обеспечить соблюдение инвариантов обладающего ими типа и невозможность их нарушения внешним кодом можно, объявив члены этого типа как private или readonly.

• Типы-суммы группируют типы по принципу «или-или» и содержат значения только одного из типов-компонентов.

• Функция должна возвращать значение или ошибку, а не значение и ошибку.

• Опциональный тип данных может содержать значение лежащего в его основе типа либо не содержать ничего. Риск ошибок снижается, если отсутствие значения не входит в состав области значений переменной (ошибка стоимостью миллиард долларов с указателем null).

• XOR-типы данных содержат значение левого или правого типа. По традиции правый тип соответствует корректному значению, а левый — ошибке.

• Вариантный тип данных может содержать значение из любого числа лежащих в его основе типов и позволяет выражать значения закрытых множеств типов, никак не связанных между собой (без каких-либо общих интерфейсов или базовых типов).

• Функция-посетитель, служащая для применения нужной функции к объекту вариантного типа данных, позволяет реализовать паттерн проектирования «Посетитель» другим способом, обеспечивающим лучшее разделение обязанностей.

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

Ответы к упражнениям

3.1. Составные типы данных

В — оптимальным подходом будет задать названия для трех компонентов координат.

3.2. Выражаем строгую дизъюнкцию с помощью типов данных

1. В — в данном случае уместен перечисляемый тип данных. При подобных требованиях классы не нужны.

2. Г — допустимым возвращаемым типом в данном случае будет или встроенный тип-сумма, или Optional, поскольку и тот и другой могут выражать отсутствие значения.

3. Г — лучше всего использовать тип-маркированное объединение (number|number не позволит отличить, отражает ли данное значение ошибку).

3.3. Паттерн проектирования «Посетитель»

Вот одна из возможных реализаций:

function visit<T1, T2, T3, U1, U2, U3>(

    variant: Variant<T1, T2, T3>,

    func1: (value: T1) => U1,

    func2: (value: T2) => U2,

    func3: (value: T3) => U3

): Variant<U1, U2, U3> {

    switch (variant.index) {

        case 0:

            return Variant.make1(func1(<T1>variant.value));

        case 1:

            return Variant.make2(func2(<T2>variant.value));

        case 2:

            return Variant.make3(func3(<T3>variant.value));

        default: throw new Error();

    }

}

3.4. Алгебраические типы данных

1. В — кортежи являются типами-произведениями.

2. Б — это тип-сумма языка TypeScript.

3. В — так как кортежи — это типы-произведения, количества возможных значений двух перечисляемых типов данных перемножаются (2x3).

4. Б — поскольку это тип-сумма, количества возможных значений двух перечисляемых типов данных складываются (2+3).