7. Структуры и типы данных языка программирования
Язы́к программи́рования — формальная знаковая система, предназначенная для записи программ. Программа обычно представляет собой некоторый алгоритм в форме, понятной для исполнителя (например, компьютера). Язык программирования определяет набор лексических, синтаксических и семантических правил, используемых при составлении компьютерной программы. Он позволяет программисту точно определить то, на какие события будет реагировать компьютер, как будут храниться и передаваться данные, а также какие именно действия следует выполнять над этими данными при различных обстоятельствах. Со времени создания первых программируемых машин человечество придумало уже более восьми с половиной тысяч языков программирования. Каждый год их число пополняется новыми. Некоторыми языками умеет пользоваться только небольшое число их собственных разработчиков, другие становятся известны миллионам людей. Профессиональные программисты иногда применяют в своей работе более десятка разнообразных языков программирования. Создатели языков по-разному толкуют понятие язык программирования. К наиболее распространенным утверждениям, признаваемым большинством разработчиков, относятся следующие: · Функция: язык программирования предназначен для написания компьютерных программ, которые применяются для передачи компьютеру инструкций по выполнению того или иного вычислительного процесса и организации управления отдельными устройствами. · Задача: язык программирования отличается от естественных языков тем, что предназначен для передачи команд и данных от человека компьютеру, в то время, как естественные языки используются для общения людей между собой. В принципе, можно обобщить определение «языков программирования» — это способ передачи команд, приказов, четкого руководства к действию; тогда как человеческие языки служат также для обмена информацией. · Исполнение: язык программирования может использовать специальные конструкции для определения и манипулирования структурами данных и управления процессом вычислений. Язык программирования может быть представлен в виде набора спецификаций, определяющих его синтаксис и семантику. Для многих широко распространённых языков программирования созданы международные стандарты. Специальные организации проводят регулярное обновление и публикацию спецификаций и формальных определений соответствующего языка. В рамках таких комитетов продолжается разработка и модернизация языков программирования и решаются вопросы о расширении или поддержке уже существующих и новых языковых конструкций. Во внутреннем представлении обычно данные в современных цифровых компьютерах сохраняются в бинарном виде (в двоичном виде). Данные, которые представляют информацию из реального мира (имена, банковские счета, измерения и др.) — высокоуровневые концепции. Особая система, по которой данные организуются в программе, — это система типов языка программирования; разработка и изучение систем типов известна под названием теория типов. Языки могут быть классифицированы как системы со статической типизацией и языки с динамической типизацией. Статически-типизированные языки могут быть в дальнейшем подразделены на языки с обязательной декларацией, где каждая переменная и объявление функции имеет обязательное объявление типа, и языки с выводимыми типами. Иногда динамически-типизированные языки называются латентно типизированными. Системы типов в языках высокого уровня позволяют определять сложные, составные типы, так называемые структуры данных. Как правило, структурные типы данных образуются как декартово произведение базовых (атомарных) типов и ранее определённых составных типов. Основные структуры данных (списки, очереди, хэш-таблицы, двоичные деревья и пары) часто представлены особыми синтаксическими конструкциями в языках высокого уровня. Такие данные структурируются автоматически. Существует несколько подходов к определению семантики языков программирования. Наиболее широко распространены разновидности следующих: операционного (или так называемого математического), и деривационного (или аксиоматического). При описании семантики в рамках операционного подхода обычно исполнение конструкций языка программирования интерпретируется с помощью некоторой воображаемой (абстрактной) ЭВМ. Деривационная семантика описывает последствия выполнения конструкций языка с помощью языка логики и задания пред- и постусловий. Денотационная семантика оперирует понятиями, типичными для математики — множества, соответствия и др. Язык программирования строится в соответствии с той или иной базовой моделью вычислений. Несмотря на то, что большинство языков ориентировано на так называемую императивную модель вычислений, задаваемую так называемой фоннеймановской архитектурой ЭВМ, существуют и другие подходы. Прежде всего следует упомянуть языки со стековой вычислительной моделью (Forth, Factor, Postscript и др), а также функциональное (Лисп, Haskell, ML и др.) и логическое программирование (Пролог). В настоящее время также активно развиваются проблемно-ориентированные, декларативные и визуальные языки программирования. В вычислительной технике структура данных — это программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих интерфейс структуры данных. Структура данных часто является реализацией какого-либо абстрактного типа данных. При разработке программного обеспечения большую роль играет проектирование хранилища данных, и представление всех данных в виде множества связанных структур данных. Хорошо спроектированное хранилище данных оптимизирует использование ресурсов (таких как время выполнения операций, используемый объём оперативной памяти, число обращений к дисковым накопителям), требуемых для выполнения наиболее критичных операций. Структуры данных формируются с помощью типов данных, ссылок и операций над ними в выбранном языке программирования. Различные виды структур данных подходят для различных приложений; некоторые из них имеют узкую специализацию для определённых задач. Например, Б-деревья обычно подходят для создания баз данных, в то время как хэш-таблицы используются повсеместно для создания различного рода словарей, например, для отображения доменных имён в интернет адреса компьютеров. При разработке программного обеспечения сложность реализации и качество работы программ существенно зависит от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности, позволяющим структурам данных безопасно переиспользоваться в различных приложениях. Объектно-ориентированные языки, такие как Java, C# и C++, являются примерами такого подхода. Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хэш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов STL языка C++. Фундаментальными строительными блоками для большей части структур данных являются массивы, записи (см. конструкцию structв языке Си и конструкциюrecordв языке Паскаль), размеченные объединения (см. конструкциюunionв языке Си) и ссылки. Например, структура данных двусвязный список, может быть построена с помощью записей и зануляемых ссылок, а именно, каждая запись будет предоставлять блок данных (узел, node), содержащий ссылки на «левый» и «правый» узлы, а также сами хранимые данные.
Для продолжения скачивания необходимо пройти капчу:
Системы типов в языке — какие бывают и чем отличаются
В языках программирования у любого кусочка данных (переменной, константы, аргумента функции) есть тип. Тип определяет множество возможных значений и операции, которые с ними можно проводить. Например, в этом участке псевдокода переменная age имеет тип «число»:
В разных языках по-разному устроена работа с типами. Важно понимать, чем отличаются разные системы типизации, чтобы умело и к месту использовать тот или иной язык.
Вообще, существуют «бестиповые языки», где вся работа с типами возлагается на разработчика. Но таких языков немного и они довольно редкие. Один из примеров — язык ассемблера (очень низкоуровневый язык программирования).
Сильная — слабая
В первую очередь системы типов делятся по способу приведения типов.
Приведение типов — это превращение данных одного типа в данные другого типа. Например, строку «12» довольно легко превратить в число 12:
Некоторые языки сами приводят типы, делают это скрыто от программиста. Такое поведение принято назвать слабой (или нестрогой) типизацией. Обычно, это позволяет в одном выражении использовать переменные любых типов и не беспокоиться об их приведении. Часто это приводит к удивительным последствиям.
С другой стороны стоят языки, которые требуют явно определить, что следует делать с данными, чтобы перевести их в другой тип. Они полностью отдают эту работу программисту. Это поведение называется сильной (или строгой) типизацией.
Иногда бывает сложно провести черту между сильной и слабой типизацией. Во многих языках некоторые преобразования происходят автоматически, а некоторые требуют явного приведения типов. Строгость типизации — это шкала, и язык может располагаться на ней где угодно.
Статическая — динамическая
Другая важная классификация делит языки на статически типизированные и динамически типизированные.
В статически типизированном языке каждая переменная имеет определенный тип на всем протяжении жизни, он не может измениться во время выполнения. То есть все типы известны ещё на этапе написания кода. Если же во время выполнения попытаться присвоить переменной одного типа значение другого типа, произойдет ошибка. Причём такие ошибки можно найти без запуска программы.
Динамически типизированные языки работают иначе. У каждой переменной всё ещё есть тип. Но он может легко меняться по ходу исполнения программы. На практике это означает, что в конкретный момент времени мы достоверно не знаем, данные какого типа находятся в переменной.
И что лучше?
Проблема в том, что ничего не лучше. Каждая система типизации решает разные проблемы, у каждой свои плюсы и минусы. Динамическая типизация проще и удобнее на ранних этапах разработки программы, статическая типизация обеспечивает более высокую степень надёжности. С другой стороны, слабая типизация позволяет более комфортно писать код, не заботиться о преобразованиях типов и отдать это на откуп языку, а сильная позволяет лучше контролировать исполнение программы и иметь больше уверенности в корректности написанного.
На практике
Мир программирования разнообразен, в нём можно встретить языки с абсолютно любыми комбинациями систем типов, например:
- C — слабая статическая
- Python — сильная динамическая
- Java — сильная статическая
- JavaScript — слабая динамическая
При этом для многих языков появляются инструменты, позволяющие брать лучшие практики из всех систем типизации. Например, в Python появились опциональные аннотации типов, которые позволяют принести немного статической типизации. Аналогичные проекты есть для JavaScript (TypeScript, Flow) и Ruby (Sorbet).
Читайте также Как проверять типы данных в JavaScript с помощью JSDoc: подробное руководство.