Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

1.4. ВЫЧИСЛЕНИЯ И ТЕКСТ

ственно при составлении программы воспользоваться известной формулой

1,2

= −p/2 ±

/4 − q

и попытаться записать ее непосредственно на языке программирования.

Прямое решение на языке

— программа 1.4.1.

Программа 1.4.1

Корни квадратного уравнения

Прямолинейная попытка

#include <stdio.h>

#include <math.h> /*

это указание препроцессору о том,

что нужно получить доступ к функции

sqrt()

, которая, как и

средства ввода/вывода, имеется в стандартной

библиотеке

stdc */

int main (void)

{

ﬂoat X1, X2; /*

ВСЕ вычисления проводятся

с плавающей точкой!

ﬂoat P, q;

ﬂoat D;

ﬂoat r;

scanf ( "%f %f", &p, &q ); /*

Ввод

p, q.

Обратите внимание на

— формат ввода чисел с

плавающей точкой. Не забываем о взятии адреса:

& */

r = - p / 2;

D = sqrt( r*r - q );

X1 = r + D;

X2 = r - D;

printf ("\nX1 = %d; X2 = %d\n", X1, X2);

return 0;

}

Что будет, если r ∗ r − q < 0? Ошибка счета!

Ответ на этот вопрос доказывает, что программу требуется доработать.

Нужны разные вычисления в различных случаях, а значит, средства упра-

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

большинстве традиционных языков он представлен в двух формах:

ГЛАВА 1. ПОНЯТИЯ

(

условие

)

действие T

— если условие истинно, то выполняется

действие T

, в противном случае

действие T

пропускается;

(

условие

)

действие T else действие F

— если условие истинно, то

выполняется

действие T

, в противном случае выполняется

действие F

Действие T

действие F

— это операторы языка. За счет блоков (последова-

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

действий использовать несколько операторов.

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

соответствием указанной семантике:

if условие then действие T

if условие then действие T else действие F

Обе формы условного оператора восходят к устоявшимся стереотипам

управления фон Неймановских машин. Так, для формы 2 годится схема, изо-

браженная на таблице 1.1. Здесь выделены жирным шрифтом машинные ко-

Адреса Команды

m //

команды, вычисляющие условие и

m+1 //

помещающие результат в процессорный регистр

. ...

m+k (S = false)? ПЕРЕЙТИ К m+k+i

m+k+1 //

команды, вычисляющие

действие T

. ...

m+k+i-1 ПЕРЕЙТИ К m+k+i+j

m+k+i //

команды, вычисляющие

действие F

. ...

m+k+i+j //

команды, следующие за образом условного

... //

оператора в машинном коде

Таблица 1.1. Трансляция условного оператора

манды, записанные в некотором произвольном формате:

(аргумент-регистр = false)? ПЕРЕЙТИ К аргумент-адрес перехода

— условная передача управления по адресу перехода

1.4. ВЫЧИСЛЕНИЯ И ТЕКСТ

ПЕРЕЙТИ К аргумент-адрес перехода

— безусловная передача управления по адресу перехода.

m+k+i

m+k+i+j

изображают адреса, участвующие в командах перехода в ка-

честве операндов.

Покажем, как надо записывать условные операторы и блоки в текстах

программ.

Программа 1.4.2

Корни квадратного уравнения

Попытка решения с разветвлениями

#include <stdio.h>

#include <math.h>

int main (void)

{

ﬂoat X1, X2;

ﬂoat p, q;

ﬂoat D;

ﬂoat r;

scanf ( "%f %f", &p, &q );

r = - p / 2;

D = r*r - q;

if ( D > 0 )

{

D = sqrt ( D );

X1 = r + D;

X2 = r - D;

printf ("\nX1 = %f, X2 = %f\n", X1, X2);

}

else if ( D == 0 )

{

X1 = r;

printf ("\nX1 = X2 = %f\n", X1);

}

else printf ("\nДействительные корни не существуют\n");

ГЛАВА 1. ПОНЯТИЯ

return 0;

}

Оба приведенных выше представления условного оператора по сути изо-

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

запись

if ... then if ... then ... else ...;

К какому из

if ... then

относится

else

? Есть два, с внешней содержательной

точки зрения совершенно равноправных ответа:

if ... then

if ... then ...

else ...;

if ... then

if ... then ... else ...;

Здесь использованы отступы и концы строк, чтобы отразить в записи, что к

чему относится. Решения данной проблемы известны следующие:

1. Запретить использование условного оператор в качестве

действия T

Такое решение, принятое в

Алголе 60

, приводит тому, что при необхо-

димости нужно превращать условный оператор в безусловный, обрам-

ляя его блочными скобками:

if ... then begin if ... then ... else ... end;

if ... then begin if ... then ... end else ... ;

2. Видоизменить синтаксис условного оператора, рассматривая само if

как открывающую скобку и ввести парную к ней закрывающую, как

сделано в языках

Алгол 68

Modula-2

Ada

, соответственно:

if ... then ... else ... ﬁ

if ... then ... else ... endif

Пожалуй, это решение — самое лучшее.

3. Принять соглашение: считать верным один из указанных перед нача-

лом данного перечисления вариантов (чаще второй). Именно такое ре-

шение предлагается для

С++

Pascal

. Даже если такое соглашение

имеется, лучше им не пользоваться, а применять одно из тех предста-

влений, в которых структура вычислений указывается явно!

1.5. РАБОТА СО ЗНАЧЕНИЯМИ

§ 1.5. РАБОТА СО ЗНАЧЕНИЯМИ

В наиболее часто используемых профессионалами языках программиро-

вания предполагается устройство вычислителя, близкое к реальной аппара-

туре компьютеров. Известно, что компьютер выполняет действия в процес-

соре, а хранит данные и программы в памяти (см. § 1.2). Память может быть

представлена на самом абстрактном уровне как некоторая совокупность кон-

тейнеров, в которых размещаются значения. Реально такие контейнеры чаще

всего соответствуют ячейкам памяти, и именно на такое специальное (хотя и

практически общепринятое сейчас) устройство логической структуры памя-

ти ориентированы, в частности, традиционные языки. Из упомянутых нами

примеров к такой структуре не привязаны

Lisp

Рефал

Prolog

. Дальнейшее

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

В традиционных языках основными способами представлять значения и

оперировать ими является использование переменных и констант. Рассмо-

трим некоторые базовые понятия, связанные с этим.

Значения всегда принадлежат некоторому типу.

Определение 1.5.1. Тип данных,или сокращенно тип —это множество зна-

чений вместе с набором операций над этими значениями. Константное зна-

чение — это значение, которое существует независимо от выполнения про-

граммы и не может быть изменено. Константа — обозначение константного

значения. Литерал — частный случай константы, изображение, представля-

ющее в программе свое значение. Переменная — обозначение контейнера, в

котором может храниться одно значение в каждый данный момент.

Конец определения 1.5.1.

Например, число 1 — литерал со значением единица.

"Что за чушь!"

— лите-

рал, обозначающий соответствующую строку символов.

Типом константы является тип ее значения. Если есть некоторый тип, то

его множество значений чаще всего может рассматриваться как состоящее из

константных значений данного типа.

Например, bool — тип данных, мно-

жеством значений которого является {false, true}, а операциями — конъюнк-

ция, дизъюнкция, исключающее или и отрицание.

Тип литерала часто определяется по контексту, и поэтому литералы, вы-

рванные из контекста, иногда могут иметь неоднозначную интерпретацию.

Но не всегда: например, в объектно-ориентированном программировании появляются ти-

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

ГЛАВА 1. ПОНЯТИЯ

Например, в языке

Pascal "L"

— изображение как литерного, так и строково-

го значений.

Значения обозначаются не только своими изображениями, т. е. литерала-

ми, но часто и именами, которые должны быть описаны как имеющие опре-

деленные значения (например в конструкции описания константы — см. ни-

же).

Определение 1.5.2. Имя как конструкция (см. стр. 7) языка программиро-

вания — это последовательность символов, обычно букв, цифр и некоторых

дополнительных символов (например, "_"), построенная в соответствии с

определенными правилами (например, в

первый символ — буква или "_"),

которая является лексемой.

Конец определения 1.5.2.

Например, в языке

Pascal

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

следующему:

const size =1000;

Изображения констант разных типов, вообще говоря, могут совпадать,

но всегда должны существовать соглашения, позволяющие, в частности, при

определении имени константы, однозначно определить еще и ее тип. Напри-

мер, в

Алголе 68

константа описывается в виде

type const =< значение >;

Рассмотрим в языке

C++

два частных случая:

const ﬂoat shortlength = 2.2888;

const double length = 2.2888;

(1.4)

В первом из них

shortlength

будет интерпретировано как обычное действи-

тельное число, имеющее значение, изображаемое 2.2888. Во втором то же

изображение действительного числа понимается как константа, представля-

ющая длинное действительное число,имеющее повышенную точность и рас-

Обычно встречающимися исключениями из данного правила являются промежуточные

значения, возникающие в ходе вычисления выражений, например, значение x + y в выраже-

нии (x + y) ∗ z, и литералы.

1.5. РАБОТА СО ЗНАЧЕНИЯМИ

ширенный диапазон значений, так что число незначащих нулей,

автомати-

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

В языках традиционного типа переменная — основной способ предста-

вления данных программы. Она отражает понятие памяти вычислительной

машины и интерпретируется как контейнер для размещения значений. Пе-

ременные практически всегда задаются в программе своими именами и рас-

сматриваются по сути дела как более удобное представление адресов яче-

ек компьютера. Почти всегда переменной можно присвоить значение

, при

этом старое значение, хранившееся в контейнере, пропадает, и в нем теперь

будет новое.

Пример 1.5.3. Рассмотрим оператор

X = Y + Z;

Этот оператор обозначает в языке

следующую последовательность дей-

ствий:

Взять значение из ячейки, обозначенной как

;

Сложить его со значением из ячейки, обозначенной как

;

Поместить результат в ячейку, обозначенную как

Конец примера 1.5.3.

Пример 1.5.4. Рассмотрим оператор языка

Pascal

x := y + 1

Этот оператор дает следующую последовательность действий:

Взять значение из ячейки, обозначенной как

;

Сложить его с целым числом, имеющим значение единица;

Поместить результат в ячейку, обозначенную как

Конец примера 1.5.4.

То, что написано в основном тексте, является огрублением реальной ситуации. Число

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

ставлению соответствующего типа действительных чисел в машине. Способ дополнения

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

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

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

простой, но попробуйте-ка ее решить!

В объектно-ориентированном программировании есть некоторые исключения из данного

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

пустимая операция.

ГЛАВА 1. ПОНЯТИЯ

Для вычислительных машин с традиционной (классической) архитекту-

рой информация о типе значения не может быть извлечена из машинного

представления самого значения (принцип однородности памяти). Поэтому

тип значения (константы или переменной) остается внешней информацией,

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

Чаще всего типовая информация вычисляется до выполнения програм-

мы, т. е. статически, и принципиальной новацией объектно-ориентирован-

ного подхода явилось, в частности, широкое использование динамического

определения типа объекта и, более того, динамического его переопределе-

ния в некоторых пределах.

В дальнейшем это было перенесено и на типы

данных, используемые в работе с распределенными системами. В частности,

в системах

COM

CORBA

, предназначенных для построения программ, ра-

ботающих по схеме клиент-сервер (программ, которые могут работать в ка-

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

же, наоборот, использовать такие объекты, которые динамически подставля-

ются в момент исполнения (сервер)) широко применяется тип данных

variant

значение которого несет информацию о своем типе внутри себя.

Наряду с традиционными архитектурами вычислительных машин нашли

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

мяти не догматизируется (на уровне оборудования он давно потерял статус

абсолюта, например, в связи с очевидными преимуществами использования

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

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

ваемое тегирование. Смысл его заключается в том, что в ячейках (основной

памяти) выделены специальные разряды, именуемые тегом, которые пред-

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

чения (см. рис. 1.7).

Достоинствами тегирования, реализованного аппаратно, являются:

• семантически емкие операции (в частности, поэтому время выполне-

ния программ сокращается);

• дополнительный контроль корректности вычислений.

В языковых терминах это выражается как динамическая (определяемая при

выполнении программы) типизация данных.

На практике впервые такие средства получили распространение в языке

SMALLTALK

1.5. РАБОТА СО ЗНАЧЕНИЯМИ

определяет тип того, что хранится в основной части ячейки (тип значения)

<Int a> + <Float b> → <Float a

> + <Float b>

Выполняется

процессором

Тег Значение

Рис. 1.7. Структура ячейки при тегировании

В языке

тегированное данное соответствует описанию структуры, по-

добному

struct tagged

{

int type_tag;

union

{

int x;

ﬂoat y;

}

(1.5)

Здесь второе поле структуры

tagged

является значением, тип которого мо-

жет быть либо целым, либо действительным. Первое поле должно (по смы-

слу идентификатора) быть значением, которое однозначно идентифицирует,

согласно некоторой системе договоренностей, тип второго поля. При этом

приходится внешним образом (например, в фирменных либо технологиче-

ских стандартах) определять множество соглашений, являющихся по сути

затыканием очевидных недоделок языка. В данном случае (как и во многих

других) в языках

Pascal

Ada

приняты более логичные решения. Например,

в языке

Pascal

говорится о вариантной части структуры, причем должен яв-

но определяться соответствующий тег и значения этого тега, приписанные

каждому варианту:

record

case b : Boolean of

true : (i : integer);

false : (r : real)

end;

(1.6)

ГЛАВА 1. ПОНЯТИЯ

Соотношение между понятиями имя, значение, тип,константа и перемен-

ная наиболее точно и строго определено в языке

Алгол 68

. Эта точность от-

ражена и в языковых конструкциях описания имен. Так, описание

type Имя = выражение_вырабатывающее_значение_типа_тип;

трактуется как определение идентификатора

Имя

, обладающего

значением

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

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

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

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

одно и то же значение. Но при другом входе в тот же блок константа может

иметь другое значение.

Может показаться,что появление константы,обозначающей значение, воз-

никшее в ходе исполнения программы и не имеющее смысла вне контекста,

определяемого данным исполнением,противоречит самой сущности констан-

ты. Но самому математическому понятию константы это не противоречит. В

математических текстах все время встречаются конструкции типа «Обозна-

чим значение, которое существует согласно доказанному выше утверждению

(5), через a

.» Это утверждение (5) может не иметь смысла вне данного дока-

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

ем к абсурду), так что константа a

возникает и существует лишь в контексте

данного математического рассуждения, зато в нем она имеет некоторое фик-

сированное значение все время, пока используется. Именно это последнее

свойство нужно нам и от имени, обозначающего программистскую констан-

ту.

Такая конструкция позволяет определять не только имена констант, но и

имена переменных.

type Имя1;

рассматривается как сокращение для

ref type Имя1 = loc type;

где loc type — это выражение, вырабатывающее новое значение типа ref type

(локальный генератор адреса для размещения значений типа type в качестве

содержимого по указанному адресу; это — один из исключительно редко

встречающихся случаев, когда переменная задается не именем, а значением

некоторого выражения). Таким образом,по-прежнему определяется констан-

та, значением которой обладает имя

Имя1