Лекция 1: введение в программирование.

Курс лекций по программированию на языках высокого уровня

I семестр: язык Си

Важные примечания

© Максим Максимович Ковалев, 2008 год, МИЭМ.Каждый имеет право воспроизводить, распространять и/или вносить изменения внастоящий Документ в соответствии с условиями GNU Free Documentation License,Версией 1.2 или любой более поздней версией, опубликованной Free SoftwareFoundation;данный Документ не содержит Неизменяемых разделов, не содержитТекста, помещаемого на первой странице обложки, и не содержит Текста,помещаемого на последней страницы обложки.

Полную официальную версию текста лицензии GNU FDL на английском языке можно найти по адресу http://www.gnu.org/licenses/fdl.html, а её неофициальный перевод на русский язык – по адресу http://ru.wikisource.org/wiki/GNU_FDL.

При написании настоящего Документа использованы материалы с сайта http://wikipedia.org/ и из документации к компилятору GCC 4.2.1, распространяемые по лицензии GNU FDL.

Все приведённые в тексте листинги проверены компилятором GCC 4.2.1 под управлением ОС SuSe Linux 10.3 и не содержат ошибок (Error) и предупреждений (Warning), если не указано обратное.

Вся приведённая информация об архитектуре ЭВМ относится к архитектурам x86 и x64, если не указано обратное.

Содержание

Лекция 1: введение в программирование.

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

История программирования восходит к Аде Лавлейс, которая ещё в середине XIX века наметила такие понятия как подпрограмма, библиотека подпрограмм, регистр, цикл и другие. В то время все эти понятия формулировались применительно к разностной машине Бэббиджа, что отрицательным образом сказывалось на их общности и формальности, ведь приходилось привязываться к конкретным техническим решениям механической машины. Поэтому в 1936 году английский математик Алан Тьюринг предложил понятие абстрактного автомата, позднее названного в его честь машиной Тьюринга. Машина Тьюринга состоит из бесконечной ленты, разделённой на ячейки, по которой движется управляющее устройство. Управляющее устройство может считать символ, хранящийся в ячейке, и в зависимости от того, каким будет этот символ, переместиться вправо или влево, или остаться на месте, но при этом записать в ячейку новое значение. Конкретные правила движения управляющего устройства определяются алгоритмом, реализуемым данной машиной Тьюринга.

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

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

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

1. Состоит из арифметико-логического устройства (АЛУ), устройства управления (УУ), запоминающего устройства, устройств ввода-вывода.
2. АЛУ и УУ, объединённые в центральный процессор (ЦП), определяют действия, подлежащие выполнению, считывая команды из оперативной памяти (ОЗУ).
3. Машина работает в двоичном коде.
4. Программы и данные хранятся в одном и том же пространстве памяти.

Из пунктов 3 и 4 становится ясно, что программа для фон-неймановской машины представляет собой последовательность нулей и единиц, одни участки которой кодируют команды, а другие – данные. Подобная последовательность называется машинным кодом. Если учесть, что любое число в машинном представлении кодируется фиксированным количеством разрядов (неиспользуемые заполняются нулями), число которых может доходить до 64, можно понять, что программировать в машинном коде невероятно сложно. Поэтому в 1950 году Грейс Хоппер создаёт для ЭВМ «Эдсак» первый язык ассемблера.

Язык ассемблера пре6дставляет собой удобную для восприятия человеком форму записи машинных команд. Между машинным кодом и кодом на языке ассемблера существует взаимно однозначное соответствие. Тем не менее, стоит заметить, что современные ассемблеры предоставляют программисту базовый уровень абстракции. Во-первых, это переменные и метки с символьными именами, в противоположность тому, что в машинном коде на их местах стоят адреса в памяти. Во-вторых, это независимость мнемокода команды от её операндов. Например, с точки зрения процессора, присваивание одной переменной значения другой переменной и присваивание переменной значения, записанного в коде программы – это разные инструкции, но в языке ассемблера они обозначаются одним мнемокодом mov, а выбор ассемблером конкретной инструкции зависит от формата записи операндов.

Несмотря на то, что язык ассемблера существенно упростил написание программ, этот процесс всё ещё требовал больших знаний в области организации конкретной ЭВМ, для которой писалась программа. А программирование в то время требовалось в основном учёным и военным – то есть людям, которые не могут тратить много времени на овладение навыками программирования. Поэтому в 1958 году Джон Бэкус разрабатывает в корпорации IBM язык Фортран (от англ. FORmula TRANslator), тем самым начиная историю развития языков высокого уровня.

Язык программирования высокого уровня – это язык программирования, в который введены неочевидные и часто неоднозначные в машинном коде смысловые конструкции. Перевод текста на языке высокого уровня в машинный код осуществляет специальная программа, называемая компилятором. Грамматика языка высокого уровня определяется не особенностями ЭВМ, а тем, какие классы задач предполагается решать на данном языке.

Можно составить некоторую классификацию языков программирования.

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

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

• Программа на императивном языке программирования с математической точки зрения представляет собой общее решение поставленной задачи, иными словами, ответ на вопрос «как делать?». Это последовательность команд, которые должен выполнить исполнитель.
• Программа на декларативном языке программирования является сочетанием формализованной в рамках языка программирования задачей и всех необходимых для её решения теорем, проще говоря, ответ на вопрос «что делать?». Конкретную последовательность выполняемых действий выполняет компилятор, или чаще интерпретатор – программа, в реальном времени выполняющая код программы без его преобразования в машинный код.

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

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

Дата добавления: 2015-11-13