Файл: Современные языки программирования (основы программирования).pdf

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

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

Классификация структур данных:

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

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

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

Информация по каждому типу однозначно определяет :

1) структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, с одной стороны, и интерпретирование двоичного представления, с другой;

2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа;

3) множество допустимых операций, которые применимы к объекту описываемого типа.

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

1.4 Семантика языков программирования

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

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

Глава 2. Классификация языков программирования

2.1 Процедурные языки программирования

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

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

2.2. Язык программирования Си

2.2.1. Описание

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

Язык Си является универсальным языком программирования. Он первоначально появился в операционной системе UNIX, и развивался как основной язык систем, совместимых с ОС UNIX. Сам язык, однако, не связан с какой-либо одной операционной системой или машиной; и хотя его называют языком системного программирования, так как он удобен для написания операционных систем, он может использоваться для написания любых больших вычислительных программ, программ для обработки текстов и баз данных.

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

В языке Си отсутствуют операции, имеющие дело непосредственно с составными объектами, такими как строки символов, множества, списки или с массивами, рассматриваемыми как целое. Здесь, например, нет никакого аналога операциям PL/1, оперирующим с массивами и строками. Язык не предоставляет никаких других возможностей распределения памяти, кроме статического определения и механизма стеков, обеспечиваемого локальными переменных функций. Сам по себе язык Си не обеспечивает никаких возможностей ввода-вывода. Все эти механизмы высокого уровня должны обеспечиваться явно вызываемыми функциями.

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

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

Компилятор с Си может быть простым и компактным. Это обеспечивает высокую степень мобильности языка. Поскольку типы

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

оказывается очень маленькой. На СМ-4, например , она содержит только программы для 32-битового умножения и деления и

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

совместимую библиотеку функций для выполнения операций

ввода-вывода, обработки строк и распределения памяти, но так

как обращение к ним осуществляется только явно, можно, если

необходимо, избежать их вызова; эти функции могут быть компактно написаны на самом Си.

Опять же из-за того, что язык Си отражает возможности

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

вместо этого программы на языке ассемблера. Хотя Си соответствует возможностям многих ЭВМ, он не зависит от какой-либо конкретной архитектуры машины и в силу этого без особых

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

аппаратных средствах.

Язык Си не является языком со строгими типами данных в смысле Паскаля или Алгола-68. Он сравнительно снисходителен

к преобразованию данных, хотя и не будет буйно преобразовывать типы данных подобно языку PL/1. Компилятор не предусматривает никакой проверки индексов массивов, типов аргументов и т.д. во время выполнения программы.

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

Из-за того, что в языке отсутствуют средства ввода/вывода и т.п., при программировании на нем существенную роль играет библиотека стандартных программ, осуществляющих взаимодействие с системой. Во всех системах, совместимых с ОС UNIX, к которым относится и ДЕМОС, существует совместимый набор программ для ввода/вывода, управления памятью, преобразования данных и выполняющих другие функции, использование которых обеспечивает возможность переноса программ на другие ЭВМ.

2.3. Объектно-ориентированные языки программирования

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