Сделай Сам Свою Работу на 5

Присваивания для диапазонов.





 

Не всегда возможно определить заранее будет ли выражение содержащее значения из диапазона нарушать его границы. Рассмотрим следующий оператор присваивания, включающий переменную X типа SmallInt и Y типа SmallerInt, объявленные выше.

 

Y := Y + X

Поскольку владеющий тип в данном случае INTEGER, операция + допустима для операндов Y и X. Сложение дает значение типа INTEGER, которое может быть присвоено Y, как значение владеющего типа. Однако если результат сложения за пределами объявленного диапазона значений для Y, т.е. 0 ... 10, работа программы завершится с сообщением об ошибке.

 

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

 

V := E = {<s, t>: E(s) Î Vals(V), t = (s – {<V, c>: c Î Vals(V)}) È {<V, E(s)>}}

 

где Vals(V) – множество всех значений типа V.

 

Преобразование температур.

 

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



 

PROGRAM Temperature(INPUT, OUTPUT);

VAR

Farenheit: -459 .. 212;

Celsius: -273 .. 100;

BEGIN {Temperature}

READ(Farenheit);

Celsius := (Farenheit – 32)*5 DIV 9;

WRITELN(Farenheit:4, ‘degrees Farenheit or ’,

Celsius:4, ‘degrees Celsius’)

END. {Temperature}

 

Выполнение:

INPUT: 212

OUTPUT: 212 degrees Farenheit or 100 degrees Celsius

 

INPUT: 32

OUTPUT: 32 degrees Farenheit or 0 degrees Celsius

 

INPUT: -459

OUTPUT: -459 degrees Farenheit or –272 degrees Celsius

 

INPUT: 1000

OUTPUT: Value 1000 is out of range.

 

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

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

 

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

 

Правила проектирования для CF Pascal расширяются до применения с порядковыми типами с небольшими изменениями. Анализ программ также похож, но операторы для INTEGER потребуют некоторых новых методов. Особенно легка для анализа накапливающая итерация.



 

Правила проектирования.

 

Правила проектирования для операторов BEGIN, IF и WHILE в CF Pascal могут быть расширены для D Pascal и его перечислимых типов. Единственное требуемое изменение – это правило сохранности для операторов BEGIN:

Для CF Pascal оно будет:

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

Слово «сохраняйте» может быть заменено на «сохраняйте возможность вычисления», то есть:

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

 

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

 

Рассмотрим задачу построения оператора BEGIN для обмена двух целых значений без использования временной переменной.

X, Y := Y, X

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

BEGIN

X := X + Y;

Y := X – Y;

X := X – Y;

END:

Значения X и Y, конечно, должны лежать в интервале [-MAXINT, MAXINT], но обмен не будет работать, как требуется для всех этих значений. Результат каждой операции может также не попасть в интервал. Условия корректного выполнения вычислены в следующем символическом выполнении. Аббревиатура inrange(X) означает, что значение X находится в интервале [-MAXINT, MAXINT].



 

Часть Условие X Y
  X := X + Y Y := X – Y X := X - Y   inrange(X+Y) inrange(X+Y-Y) inrange(X+Y-X) X X+Y   X+Y-X=X Y   X+Y-Y=X  

 

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

(inrange(X+Y) -> X,Y := Y, X)

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

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

Переполнение с этого момента мы отслеживать не будем, тогда требуемая функция будет:

f= (0 <= Y -> X := X+Y)

Существование условия правила проектирования операторов WHILE требует, чтобы

range(f) Í domain(f)

и это условие удовлетворено и

для каждого s Î range(f), f(s) = s.

Последнее условие не срабатывает. Рассмотрим состояние s в range(f), в котором значение Y ненулевое. f ставит в соответствие этому состоянию состояние, в котором значение X заменяется значением X+Y, которое отличается от X, поэтому новое состояние не может быть s, как требует условие существования.

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

g=(0<=Y -> X,Y := X+Y, 0)

как целевую функцию. range(s) – те состояния, в которых значение Y равно нулю и определено на всех таких состояниях, поэтому условие:

range(g) Í domain(g)

удовлетворяется. Так же удовлетворяется вторая часть условия существования,

g(s) = s для всех s Î range(g)

потому что любое состояние s Î range(g) имеет нулевое значение Y и g добавляет нуль к X, оставляя его неизменным.

С удовлетворенным условием существования, условие WHILE B должно быть выбрано так что:

B(s) является TRUE для всех s Î domain(g) - range(g),

B(s) является FALSE для всех s Î range(g),

В domain(g) значение Y неотрицательное и поскольку значение Y нулевое в range(g), простейшее выражение для B будет Y > 0.

Наконец, оператор BEGIN D, должен быть выбран такой, что

WHILE Y > 0 DO D

завершается для любого состояния в domain(g) и

IF Y > 0 THEN D

сохраняет значения необходимые для достижения финального состояния, то есть X+Y.

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

 

WHILE Y > 0

DO

BEGIN

Y := Y –1;

X := X+1

END

 

Анализ программ.

 

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

 

BEGIN

X := 3;

Y := 5;

{(Y >= 0 --> X, Y := X+Y, 0) | (Y < 0 --> )}

WHILE Y > 0

DO

BEGIN

Y := Y – 1;

X := X + 1

END

END

 

Желаемая функция для оператора WHILE представлена комментарием:

F = (Y >= 0 --> X, Y := X+Y, 0) | (Y < 0 --> )

Правило верификации для WHILE требует выполнения следующих трех условий:

1. domain(F) = domain( WHILE Y > 0 DO BEGIN Y := Y – 1; X := X + 1 END )

2. (Y <= 0 -> F) = (Y <= 0 -> )

3. F = IF Y > 0 THEN BEGIN Y := Y-1; X := X + 1 END

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

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

Y <= 0 --> F

= (Y <= 0 --> (Y >= 0 --> X, Y := X+Y, 0) | (Y <= 0 --> (Y < 0 --> ))

= (Y <= 0 AND Y >= 0 --> X, Y := X+Y, 0) | (Y <= 0 AND Y < 0 --> )

= (Y = 0 --> X, Y := X+Y, 0) | (Y < 0 --> )

= (Y <= 0 --> )

 

Наконец, рассмотрим правую часть третьего условия:

IF Y > 0 THEN BEGIN Y := Y-1; X := X + 1 END ◦ F

Функция, соответствующая оператору IF будет:

IF Y > 0 THEN … = (Y > 0 -- > X, Y := X + 1, Y - 1) | (Y <= 0 --> )

тогда IF Y > 0 THEN … ◦ F будет

(Y > 0 -- > X, Y := X + 1, Y - 1) | (Y <= 0 --> ) ◦

(Y >= 0 --> X, Y := X+Y, 0) | (Y < 0 --> )

Здесь необходимо рассмотреть четыре случая соответствующих первому и второму условиям двух условных присваиваний. Обозначим эти случаи по номеру выбранного условия, например, случай 1-2 будет означать первое условие IF Y > 0 THEN … и второе условие F:

Случай 1-1

Часть Условие X Y
IF … F Y > 0 Y – 1 >= 0 X + 1 X + 1 + Y - 1 Y – 1

 

Условие упрощается до Y >= 1, тогда функция будет:

(Y >= 1 --> X, Y := X + Y, 0)

 

Случай 1-2

Часть Условие X Y
IF … F Y > 0 Y – 1 < 0 X + 1   Y – 1

Условие:

Y > 0 AND Y – 1 < 0 = Y > 0 AND Y < 1

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

 

Случай 2-1

Часть Условие X Y
IF … F Y <= 0 Y >= 0   X + Y  

 

Условие упрощается до Y = 0, тогда функция будет:

(Y = 0 --> )

 

Случай 2-2

Часть Условие X Y
IF … F Y <= 0 Y < 0    

Условие:

(Y < 0 --> )

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

(Y >= 1 --> X, Y := X + Y, 0) | (Y = 0 --> ) | (Y < 0 --> )

= (Y > 0 --> X, Y := X + Y, 0) | (Y <= 0 --> )

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

 

Поскольку условия верификации оператора WHILE удовлетворены, F – функция вычисляемая оператором WHILE.

Композиция F с первыми присваиваниями

(X, Y := 3, 5) ◦ F

дает значение всего фрагмента программы:

(5 > 0 --> X, Y := 3 + 5, 0) | (5 <= 0 --> X, Y := 3, 5) =

(X, Y := 8, 0)

 

Желаемая функция для оператора WHILE не всегда дается как условное присваивание, часто желаемая функция должна быть получена из программы. В предыдущем примере было легко определить функцию для оператора WHILE, потому что оба оператора присваивания в ней были накапливающими операторами присваивания. В накапливающем присваивании значение переменной изменяется прибавлением или вычитанием фиксированного значения. Математическая концепция суммирования (повторяющегося сложения) – естественный выбор для описания повторяющиеся эффекты для X и Y. Поскольку цикл выполняется так долго, как Y > 0 и значение Y уменьшается на 1 в течение каждого выполнения, суммирование будет содержать Y элементов. На каждой итерации, поскольку X и Y изменяются на константу 1, это элемент для суммирования. Сумма добавляется к исходному значению X и вычитается из исходного значения Y. Таким образом функция для оператора WHILE будет:

X, Y := X + ,

Эти значения могут быть упрощены:

 

X + = X + (Y –1 + 1) = X + Y – 1 + 1 = X + Y

= Y – 1(Y – 1 + 1) = Y – Y – 1 + 1 = 0

 

то есть функция будет:

(X, Y := X+Y, 0)

как и ранее.

 

Этот метод может быть использован для определения функции другого оператора WHILE. Фрагмент на Паскале ниже эмулирует операторы DIV и MOD используя только сложение и вычитание. Его желаемая функция будет:

f = (Numerator >= 0 AND Denominator > 0 -->

Quotient, Remainder :=

Numerator DIV Denominator, Numerator MOD Deniminator)

 

Для данной функции фрагмента программы должна быть определена функция вычисляемая оператором WHILE для того, чтобы верифицировать, что фрагмент вычисляет f.

Quotient := 0;

Reminder := Numerator;

WHILE Remider >= Denominator

DO

BEGIN

Quotient := Quotient + 1;

Reminder := Reminder - Denominator

END

Пусть значения Quotinet, Reminder и Denominator будут Q, R и D соответственно. Тест на завершение будет R ≥ D или R- D ≥ 0, цикл будет выполнен k раз, где:

k = (R-D) / D = R/D –1

Таким образом, Q и R изменяться до:

Q +

R -

соответственно. Эти выражение сокращаются до:

Q + = Q + 1 (R / D)

R - = R – D(R/D)

Функция для оператора WHILE следующая:

(Reminder >= Denominator AND Denominator > 0 -->

Remainder, Quotient :=

Reminder – (Reminder DIV Denominator)*Denominator,

Quotient + (Reminder DIV Denominator)) |

(Reminder < Denominator --> )

Верификация, что это функция оператора WHILE и фрагмент программы корректен для данной желаемой функции f, выполняются аналогично предыдущему примеру.

 

 

Заключение.

 

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

 

Оператор Операция Функциональность
NOT инверсия логический -> логический
AND коньюнкция логический x логический
OR дизъюнкция  
= эквивалентность порядковый x порядковый -> логический
<> неравенство  
< меньше  
<= меньше или равно  
> больше  
>= больше или равно  
+ унарный плюс целый -> целый
- унарный минус  
+ бинарное сложение целый x целый -> целый
- бинарное вычитание  
* умножение  
DIV целочисленное деление  
MOD остаток от деления  

 

Каждый порядковый тип используется по-своему. Переменные типа BOOLEAN могут быть использованы для хранения сложных условий для дальнейшего использования. Переменные типа INTEGER позволяют легко выполнять подсчет при условии, что выполняется ограничение [-MAXINT, MAXINT]. Перечислимые типы хороши, когда нужно зафиксировать небольшой набор значений, каждое со своим мнемоническим именем. Типы диапазоны позволяют программисту объявлять границы их значений, чтобы они проверялись автоматически.

Методы анализа, использованные в CF Pascal, расширены до использования с порядковыми типами без изменений.

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.