Re[13]: Арифметическое переполнение
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 01.03.14 07:11
Оценка:
Здравствуйте, AlexRK, Вы писали:

ARK>Крутится мысль о выносе в сигнатуру функции некоторой дополнительной информации о числовых параметрах. Этакие "типы для числовых типов", но не просто диапазоны.


Контракты живут в последнем стандарте Ada 2012, заимствовано из Eiffel. Выглядит как-то так:

   procedure Dedupe (Arr: in out Int_Array; Last : out Natural) with
     Pre => Has_Duplicates(Arr),
     Post => not Has_Duplicates( Arr(Arr'First .. Last) )
             and then (for all Item of Arr'Old =>
                        (for some J in Arr'First .. Last =>
                            Item = Arr(J)))
                      -- Only duplicates removed
             and then (for all J in Arr'First .. Last =>
                        (for some Item of Arr'Old =>
                            Item = Arr(J)));
                      -- Nothing new added

   function Has_Duplicates(Arr : Int_Array) return Boolean is
   begin
      return (for some I in Arr'First .. Arr'Last-1 =>
              (for some J in I+1 .. Arr'Last => Arr(I)=Arr(J)));
   end Has_Duplicates;


То же применимо для состояния объекта

type Disc_Pt is
  record
    X, Y: Float range –1.0 .. +1.0;
  end record
  with
    Type_Invariant => Disc_Pt.X**2 + Disc_Pt.Y**2 <= 1.0;


Type_Invariant проверяется только при входе/выходе из метода. Поэтому код

P.X := 1.0;
P.Y := 0.0;


пройдет проверку даже если в начале P.Y было равно 1.0.

здесь
Re[14]: Арифметическое переполнение
От: AlexRK  
Дата: 01.03.14 08:21
Оценка:
Здравствуйте, Mystic, Вы писали:

M>Здравствуйте, AlexRK, Вы писали:


ARK>>Крутится мысль о выносе в сигнатуру функции некоторой дополнительной информации о числовых параметрах. Этакие "типы для числовых типов", но не просто диапазоны.


M>Контракты живут в последнем стандарте Ada 2012, заимствовано из Eiffel. Выглядит как-то так:


Да, я слышал про новый стандарт. Похоже на Эйфель, хотя, ИМХО, синтаксис страшнее и менее последователен. Эйфель сильно опередил свое время.
Все проверки, естественно, в рантайме?

Вообще, конечно, контракты — это однозначно хорошо, но для такой простой (даже не простой, а вездесущей) вещи, как арифметические операции, это серьезный оверкилл. Никто не будет писать их в обычном коде только из-за того, чтобы предотвратить мифический случай переполнения, которое на 95% не возникнет за все время эксплуатации этого куска кода (а потом его просто выбросят или перепишут). А если язык будет заставлять делать это, то этот язык просто не будут использовать. Нужен какой-то совершенно иной подход, поисками которого я озабочен.
Re: Арифметическое переполнение
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 01.03.14 09:16
Оценка: 106 (3) +1
Здравствуйте, AlexRK, Вы писали:

ARK>Думаю над сабжевым вопросом. Существующие языки программирования разбираются с переполнением по-разному:


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

A. Переполнение может не быть ошибкой, это может быть желаемый эффект в случае вычисления CRC, разных хэшей, кольцевого буфера и т. п.
B. Переполнение может быть нежелательным поведением, проводящей к ошибке.

Замечу, что если поведение A не поддерживается языком, то реализовать его может быть нетривиально. Даже не говоря про эффективность. Допустим в некотором языке у нас есть тип U64, который при любом переполнении бросает исключение. Типа U128 нет. Возникает вопрос, как реализовать метод, который выполнит сложение без учета переполнения? У меня затруднение.

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

1. Выполнить любой ценой. Например, в игре пользователю было бы очень грустно получить сообщение: "ошибка при вычислении следующего действия босса. Загрузите прошлое сохранение".
2. Остановить выполнение действия. Зачислить кому-то на счет 18446744073709551610 ¥ хоть и не смертельно, но неприятно.

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

Также есть аспект стоимости ошибки:

a. ошибка в релизе стоит мало (один пользователь из тысячи открыл файл размером больше 4G в текстовом редакторе)
b. ошибка в релизе стоит много (ошибка в наводке ядерной боеголовки и хана мировому империализму)

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

α. Мы сражаемся за каждый такт
ß. По сравнению с обращением к SQL-серверу экономия на арифметика выполняется чуть менее чем мгновенно.

А теперь можно думать, как это все разрулить
переполнение
Re[2]: Арифметическое переполнение
От: AlexRK  
Дата: 01.03.14 09:34
Оценка:
Здравствуйте, Mystic, Вы писали:

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


Я как раз думаю с учетом практической точки зрения.

M>A. Переполнение может не быть ошибкой, это может быть желаемый эффект в случае вычисления CRC, разных хэшей, кольцевого буфера и т. п.

M>B. Переполнение может быть нежелательным поведением, проводящей к ошибке.

В подавляющем большинстве случаев все-таки будет вариант B.

M>Замечу, что если поведение A не поддерживается языком, то реализовать его может быть нетривиально. Даже не говоря про эффективность. Допустим в некотором языке у нас есть тип U64, который при любом переполнении бросает исключение. Типа U128 нет. Возникает вопрос, как реализовать метод, который выполнит сложение без учета переполнения? У меня затруднение.


Э... а так не пойдет?

int SafeAdd(int val)
{
  return (val < Int32.MaxValue) ? (val + 1) : 0;
}


M>1. Выполнить любой ценой. Например, в игре пользователю было бы очень грустно получить сообщение: "ошибка при вычислении следующего действия босса. Загрузите прошлое сохранение".


Но программа остается непонятно в каком состоянии. Босс продолжает битву, но становится неубиваемым.

M>И последний аспект состоит в производительности:

M>α. Мы сражаемся за каждый такт
M>ß. По сравнению с обращением к SQL-серверу экономия на арифметика выполняется чуть менее чем мгновенно.

Я сейчас подумал и понял, что на самом деле для меня в списке приоритетов производительность стоит далеко не на первых местах.
А вот что я считаю ценным — так это простоту, и в том числе простоту реализации. Поэтому вариант таскать с собой рантайм с поддержкой чисел произвольной длины мне ОЧЕНЬ не нравится.
Re[2]: Арифметическое переполнение
От: andy1618 Россия  
Дата: 01.03.14 11:01
Оценка:
Здравствуйте, Mystic, Вы писали:

...
M>Еще один разрез получится в случае требуемого поведения программы, если ошибка все-таки возникла в релизе. Тут есть варианты

M>1. Выполнить любой ценой. Например, в игре пользователю было бы очень грустно получить сообщение: "ошибка при вычислении следующего действия босса. Загрузите прошлое сохранение".

M>2. Остановить выполнение действия. Зачислить кому-то на счет 18446744073709551610 ¥ хоть и не смертельно, но неприятно.

M>Эти варианты объединяет поведение программы в отладочной сборке: как-то сообщить пользователю о неприятности. Но поведение в релизе отличается.


M>Также есть аспект стоимости ошибки:


M>a. ошибка в релизе стоит мало (один пользователь из тысячи открыл файл размером больше 4G в текстовом редакторе)

M>b. ошибка в релизе стоит много (ошибка в наводке ядерной боеголовки и хана мировому империализму)


Да, эти два аспекта — классическая дилемма:

Устойчивость против корректности
Как нам показали примеры с видеоигрой и рентгеновской установкой, выбор подходящего
метода обработки ошибки зависит от приложения, в котором эта ошибка
происходит. Кроме того, обработка ошибок в общем случае может стремиться
либо к большей корректности, либо к большей устойчивости кода. Разработчики
привыкли применять эти термины неформально, но, строго говоря, эти термины
находятся на разных концах шкалы. Корректность предполагает, что нельзя
возвращать неточный результат; лучше не вернуть ничего, чем неточное значение.
Устойчивость требует всегда пытаться сделать что-то, что позволит программе
продолжить работу, даже если это приведет к частично неверным результатам.
Приложения, требовательные к безопасности, часто предпочитают корректность
устойчивости. Лучше не вернуть никакого результата, чем неправильный
результат. Радиационная машина — хороший пример применения такого принципа.
В потребительских приложениях устойчивость, напротив, предпочтительнее корректности.
Какой-то результат всегда лучше, чем прекращение работы. Текстовый
редактор, которым я пользуюсь, временами показывает последнюю на экране
строку лишь частично. Хочу ли я, чтобы при обнаружении этой ситуации
редактор завершал выполнение? Нет: когда я в следующий раз нажму Page Up или Page
Down, экран обновится, и изображение исправится.

(С) Стив Макконнелл, "Совершенный код"
Re[3]: Арифметическое переполнение
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 03.03.14 15:37
Оценка:
Здравствуйте, AlexRK, Вы писали:

M>>A. Переполнение может не быть ошибкой, это может быть желаемый эффект в случае вычисления CRC, разных хэшей, кольцевого буфера и т. п.

M>>B. Переполнение может быть нежелательным поведением, проводящей к ошибке.

ARK>В подавляющем большинстве случаев все-таки будет вариант B.


Тем не менее, вариант A, особенно Aα должен быть учтен.

ARK>Э... а так не пойдет?


ARK>
ARK>int SafeAdd(int val)
ARK>{
ARK>  return (val < Int32.MaxValue) ? (val + 1) : 0;
ARK>}
ARK>


Это просто инкремент. Не будешь же в цикле так числа складывать. Поэтому надо писать что-то вроде

int AddModU32(UInt32 a, UInt32 b)
{
  int max = UInt32.MaxValue - a;
  if (b <= max) {
    return a + b; // No overflow
  }

  return max - b; 
}


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

M>>1. Выполнить любой ценой. Например, в игре пользователю было бы очень грустно получить сообщение: "ошибка при вычислении следующего действия босса. Загрузите прошлое сохранение".


ARK>Но программа остается непонятно в каком состоянии. Босс продолжает битву, но становится неубиваемым.


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


M>>И последний аспект состоит в производительности:

M>>α. Мы сражаемся за каждый такт
M>>ß. По сравнению с обращением к SQL-серверу экономия на арифметика выполняется чуть менее чем мгновенно.

ARK>Я сейчас подумал и понял, что на самом деле для меня в списке приоритетов производительность стоит далеко не на первых местах.

ARK>А вот что я считаю ценным — так это простоту, и в том числе простоту реализации. Поэтому вариант таскать с собой рантайм с поддержкой чисел произвольной длины мне ОЧЕНЬ не нравится.

Зависит от решаемых задач. В данном случае речь идет о дизайне языка, так что надо или заранее предупредить о возможных проблемах с производительностью. Заранее описать, на какие из сочетаний AB12abαß ориентирован язык.
Re[4]: Арифметическое переполнение
От: AlexRK  
Дата: 03.03.14 15:45
Оценка:
Здравствуйте, Mystic, Вы писали:

M>Это просто инкремент. Не будешь же в цикле так числа складывать. Поэтому надо писать что-то вроде

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

Ну да. Но реализовать в принципе можно.

M>Опять же, неприемлемо для Aα, потому как я смутно представляю, чтобы оптимизатор заменил этот код одной инструкцией.


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

ARK>>Но программа остается непонятно в каком состоянии. Босс продолжает битву, но становится неубиваемым.

M>В принципе понятно, в каком состоянии. Как в JA2, когда прокачанный донельзя навык скрытности персонажа приводит к переполнению, и персонаж начинает греметь как слон в посудной лавке.

Ну я о том и говорю.

M>Зависит от решаемых задач. В данном случае речь идет о дизайне языка, так что надо или заранее предупредить о возможных проблемах с производительностью. Заранее описать, на какие из сочетаний AB12abαß ориентирован язык.


Согласен, но главная проблема пока не в этом, а в том, чтобы придумать хоть что-то разумное.
Re[2]: Арифметическое переполнение
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 03.03.14 16:28
Оценка:
Здравствуйте, Mystic, Вы писали:

M>A. Переполнение может не быть ошибкой, это может быть желаемый эффект в случае вычисления CRC, разных хэшей, кольцевого буфера и т. п.

M>B. Переполнение может быть нежелательным поведением, проводящей к ошибке.

M>1. Выполнить любой ценой. Например, в игре пользователю было бы очень грустно получить сообщение: "ошибка при вычислении следующего действия босса. Загрузите прошлое сохранение".

M>2. Остановить выполнение действия. Зачислить кому-то на счет 18446744073709551610 ¥ хоть и не смертельно, но неприятно.

M>a. ошибка в релизе стоит мало (один пользователь из тысячи открыл файл размером больше 4G в текстовом редакторе)

M>b. ошибка в релизе стоит много (ошибка в наводке ядерной боеголовки и хана мировому империализму)

M>α. Мы сражаемся за каждый такт

M>ß. По сравнению с обращением к SQL-серверу экономия на арифметика выполняется чуть менее чем мгновенно.

M>А теперь можно думать, как это все разрулить


Продолжу свои изыски. Итак, язык должен быть эффективным в случае любой из комбинаций AB 12 ab αß.

Начинать лучше с варианта (12). Для выполнения этого требования должна быть некоторая опция (pragma), которая меняет поведение программы в debug/release. Тут я не вижу вариантов.

Далее, (AB)α. Тут варианты такие:


Такие pragm-ы реализованы во многих языках программирования, к полному удовлетворению 99% программистов.

Самый неприятный вариант Bbα. В этом случае нам надо передавать компилятору как можно больше информации о том, что происходит в программе, чтобы он мог проверять ее верифицировать (например, гарантировать отсутствие случаев переполнения). В этом случае использование обычных целых типов без дополнительной информации (диапазоны) приводит к необходимости большого количества Assert-ов, пост и предусловий. Типы-диапазоны позволяют уменьшить количество работы. Сюда же для большей прозрачности намерений, идеально вписываются модульные типы, которые дают еще дополнительный синтаксический сахар. Это путь Ada.

И добавить к существующим реализациям вроде бы нечего. Чего и следовало ожидать
Re[3]: Арифметическое переполнение
От: AlexRK  
Дата: 03.03.14 17:29
Оценка: 1 (1)
Здравствуйте, Mystic, Вы писали:

M>И добавить к существующим реализациям вроде бы нечего. Чего и следовало ожидать


Ну да, это более-менее известные подходы, применяющиеся на практике.

Что можно добавить? Я думаю, можно смотреть в направлении отказа от универсальности. Подход схож с DSL — делаем что-то одно, зато хорошо.
То бишь убираем абстрактные числовые типы вообще, а вместо них появляется семейство специальных типов — "счетчик", "деньги" и т.п., каждый со своими ограничениями.
Это просто туманное и сильно обобщенное предположение, пока что мысли не оформились, никаких деталей нет. Не уверен, что этот подход даст реальные преимущества, но направление мне кажется верным.
Re[3]: Арифметическое переполнение
От: Sinclair Россия https://github.com/evilguest/
Дата: 01.04.14 04:42
Оценка:
Здравствуйте, Mystic, Вы писали:
M>Самый неприятный вариант Bbα. В этом случае нам надо передавать компилятору как можно больше информации о том, что происходит в программе, чтобы он мог проверять ее верифицировать (например, гарантировать отсутствие случаев переполнения). В этом случае использование обычных целых типов без дополнительной информации (диапазоны) приводит к необходимости большого количества Assert-ов, пост и предусловий. Типы-диапазоны позволяют уменьшить количество работы. Сюда же для большей прозрачности намерений, идеально вписываются модульные типы, которые дают еще дополнительный синтаксический сахар. Это путь Ada.
Имхо, надо понять, какого рода ошибки хочется отлавливать, и что с ними делать.
Вот, например, классика:
public int Mid(int a, int b)
{
  return (a + b)/2; // arrgh!
}

Здесь намерения программиста прозрачны, как день. Тыкать его носом в ошибку — странно. Чего мы ожидаем от программиста? Что он напишет (a/2 + b/2)? А зачем?
В таких случаях поддержка чисел произвольной разрядности выглядит предпочтительной. Оптимизации — отдельный вопрос. Можно поработать над числами произвольной разрядности так, чтобы операции над ними были близки по производительности к нативным в случае достаточно маленьких реальных разрядностей, и разумно медленными в случае больших.

Вот — другой род ошибки:
public int Mid(int a, int b)
{
  return (a * b)/2; // arrgh!
}

Здесь мы перепутали операцию, и автоматическое расширение типа до long int только ухудшит ситуацию. Рецепт для предотвращения таких ошибок — контроль размерности.
Он же, по идее, поможет избежать ошибок масштабирования (типа * 3600 при переходе от секунд к часам, вместо наоборот).


Третий род ошибки:

public uint Factorial(uint n)
{
  switch(n)
  {
    case 0:
    case 1: return 1
    default: return n*fac(n-1);
  }
}

Ошибка, вроде бы, очевидна. Но как её исправить? Либо научиться возвращать числа достаточно большого размера (читай: произвольная разрядность), либо ограничить вход значениями от 0 до 12 (какой тогда смысл в такой функции?)
Получается, что наши "традиционные" языки программирования, построенные на концепции целых чисел фиксированной разрядности, вообще не позволяют написать осмысленную реализацию функции Factorial. Так что нужно либо отказываться от таких функций (что можно сделать, опять же, при помощи контроля размерностей), либо разрешать плавающую разрядность.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[15]: Арифметическое переполнение
От: Jack128  
Дата: 01.04.14 19:06
Оценка:
Здравствуйте, AlexRK, Вы писали:


ARK>Это верно. Но мне кажется важным обстоятельство, что язык должен подталкивать и склонять к некоторому типу действий. В принципе, ООП может быть реализовано и на С, но язык этому не способствует. C# с ключевым словом readonly способствует созданию изменяемых переменных, а Ceylon с ключевым словом variable — наоборот. Языки равны по мощности, но приучают программиста к разным вещам.

ARK>Так вот, ИМХО, автоматический вывод контрактов совершенно не способствует созданию модульного, компонентного ПО. Если вообще не препятствует этому.

А что нить такое:


public void DoWork()
{
   Contract.GenerateContractByImplementation();// явное указание, что контракты нудно сгенерить
   
   DoWork(DefaultArg);
}


норм?
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.