Каким будет JInterval на языке Scala

На этой страничке будем проектировать версию библиотеки JInterval на языке Scala. При этом постараемся использовать положительный и отрицательный опыт, полученный при проектировании и использовании библиотеки JInterval на языке Java.

Однако некоторые проектные решения в JInterval/Scala будут отличаться от соответсвующих проектных решений в JInterval/Java, потому что Scala позволяет удобно выразить многое из того, что невыразимо в Java.

Полезные для нас возможности Scala

Выделим из возможностей Scala те, которые повлияют на проектирование JInterval API

• Методы могут вызываться как инфиксные операторы
• Неявные преобразования
• Улучшенная параметризация типов
• Неявные параметры

Что предстоит сделать

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

• Точное определение интервальных алгебр
• Варианты API на Scala
• Повышение производительности

Точное определение интервальных алгебр

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

Алгебры плавающих чисел

Во первых, есть алгебры плавающих числами. Стандарт IEEE 754-2008 определил базовые форматы

• Binary32 (Float)
• Binary64 (Double)
• Binary128
• Decimal64
• Decimal128

а также стандартизовал ряд форматов других размера

• Binary16
• Binary160; Binary192; Binary224; Binary256; ...
• Decimal32
• Decimal96
• Decimal160; Decimal192; Decimal224; Decimal256; ...

Математическим значением Binary-форматов являются рациональные числа Математическим значением Decimal-форматов являются пары(рациональное число,квант), то есть числа 1e3, 1000, 1000.00 считаются разными.

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

 def addition(x: Binary128, y: Binary128, r: RoudningDirection): (Binary128, Flags)

Видимо придется самим определить объединенные алгебры Binary и Decimal. Операции этой алгебры имеют два варианта

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

 def addition(x: Binary, y: Binary, r: RoundingDirection, vs: ValueSet): (Binary,Flags);

• без дополнительного параметра . Такие операции возвращают предел соответствующей операции предыдущего вид при устремлении ValueSet к большой точности.

 def addition(x: Binary, y: Binary, r: RoundingDirection): (Binary, Flags);

Некоторые операции (например minNum), расширяются однозначно. С некоторые (например nextUp) - не совсем ясно .

Стоит ли определять обединенную алгебры из Binary и Decimal ? Стоит ли вообще связываться с Decimal ?

Алгебра классических интервалов

Я думаю, надо ориентироваться на разрабатываемый интервальный стандарт. Еще со времен проектирования JInterval/Scala остались вопросы

• границы пустого интервала. JInterval/Java считает [0,1] ∩ [2,3] = [+∞,-∞], многие другие считают [0,1] ∩ [2,3] = [NaN, NaN].
• результат частично определенной операции. Интервалы в JInterval/Java могут содержать пометку о возможном неопределенном результате). JInterval/Java считает

   sqrt([1,4])  = ([1,2],false)
   sqrt([-1,4]) = ([0,2],true)

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

• В случае представления интервала в виде пары элементов double-массива место под отдельную пометку не находится. Поэтому в этом случае множество значений интервалов могло бы быть таким
  • бесконечный интервал [-∞,+∞]
  • полубесконечные интервалы [-∞,a] или [a,+∞], где a - конечное double-число
  • невырожденные конечные интервалы [a,b] , где a < b , a и b - конечные double-числа
  • вырожденные интервалы [a,a], где a - конечное double-число
  • пустой интервал [+∞,-∞]
  • неопределенный интервал [NaN,NaN] - результат частично определенной операции в случае, если аргументы выходят за область определения
• интересный способ построения интервальных алгебр описан в этой статье Зигфрида Румпа
• какое бы мы ни приняли множество значений интервала, требуется ясно определить, как должна вести себя каждая в элементарная функция на каждом сочетании аргументов
• Уточненить определение doubleCenter() и doubleRadius(). Семантика функции exactCenter() и exactRadius() однозначно определена - они возвращают точные середину и радиус. Функции doubleCenter() и doubleRadius() претерпевают округление? Должны ли они округление быть согласованным ? Надо ли требовать, чтобы исходный интервал был бы включен в интервал [doubleCenter()-doubleRadius(),doubleCenter()+doubleRadius()] ? Что делать если doubleCenter() не принадлежит интервалу (это возможно у узкого интервала с границами большой точности) ?
• был вопрос про операцию pow с вырожденным вторым аргументом pow([-2,-1],[2,2]). Результат не определена или равен [1,4] ?

Алгебра Каухера

• Возможны ли границы -∞ и +∞ ?
• Вкладывается ли классическая алгебра в алгебру Каухера ?
• Каким должно быть направление округления ?

Алгебры комплексных интервалов

?

Автоматическое дифференцирование выражений

?

Центральные формы, аффинные интервалы, апостериорный интервальный анализ

• Работы Ю.В.Матиясевича и Э.А.Мусаева
• Smartfloat Эвы Даруловой

Варианты API на Scala

Числа

Более понятно, если ввести раздельные классы Binary128, Binary160, Decimal64, ... .

• Набор операций над T с направленным округлением выражается наследником классов

scala.math.Numeric[T] и scala.math.Fractional[T].

• Нужен ли вариант операций, возвращающий и число и IEEE флаги ?

Менее понятно как эти различные классы взаимодействуют.

• Нужны ли классы Binary и Decimal ?
• Видимо, Binary может быть подклассом Rational .
• Будет ли Decimal подклассом Rational (в Decimal есть квант, в Rational - нет) ?

Классические Интервалы

• набор API с разными, но фиксированными точностями Interval[Double], Interval[Binary128], Interval[Rational]

или API с динамически задаваемой точностью (как настраивалась точность JInterval/Java/rational_bounds) ? Сейчас мы склоняемся к тому, что динамически настраиваемая точность в JInterval/Java появилась из-за того, что параметризованная система типов Java была слишком бедна, чтобы эффективно выразить параметризованное семейстов Interval<T>. Ожидаем, что параметризованная система типов Scala позволит эффективно определить семейство Interval[T] с точность, статически задаваемой параметром T.

• Как будут взаимодействуют Interval[Double] и Interval[Binary128] ?
• Три варианта подкласса scala.math.PartialOrdering (possibly, certainly, set).
• Требуется определит scala.math.Ordering (хотя бы синтаксически). Как ?
• Надеюсь , что IEEE флаги в интервалах не нужны.
• Нужны ли Decimal границы? Как быть с квантом ?

Интервалы Каухера

• Как взаимодействуют с классическими

Векторы,матрицы,тензоры

• Берем ли за основу Scalala ?
• mutable interval или IntervalRef ?

Обкатка

Наверняка придется перепробовать несколько вариантов JInterval/Scala API. Критерий выбора - удобство пользования. Поэтому будет необходимо написать на этих вариантах несколько тестовых приложений - как больших так и малых. Источники:

• Нулевой список задач C.П. Шарого
• Пакет глобальной оптимизации Н.В.Панова
• Фрагменты исходных текстов IntLab Зигфрида Румпа (как там с лицензией ?)
• Что еще ?

Лицензия

• Лицензия Scala - BSD
• Лицензия Scalala - LGPLv2.1

Этот слайд показывает, что исходники BSD-проектов можно включать в LGPL проекты, но не наоборот.

Хостинг

• kenai.com - закрывается в конце 2012
• java.net
  • Плюсы - такая же инфраструктура, что и kenai.com, возможность полного переноса содержимого проекта, возможность помещать версии проекта в центральный maven-репозиторий
  • Минусы - вдруг тоже закроют или выгонят все Scala-проекты
• github.com
  • Плюсы - git, возможность делать fork, а затем возвращать pull-request
  • Минусы-легко потеряться среди множества не-JDK проектов

Повышение производительности

• В первую очередь боремся за производительность на AMD64 ?
• Для векторов/матриц используем JNI подпрограммы с аппаратным направленным округлением ?
• Мне кажется, что для быстрого интерфейса с JNI внутреннее представление интрервала должно быть в виде соседних элементов массива (double[] для Interval[Double], long[] для Interval[Binary128])
• Вылизывание Java-кода для скалярных операций с направленным округлением
• Fork какой-нибудь JVM (Hostspot, Maxine, GCJ), который будет уметь исполльзовать аппаратное направленное округление. Нет времени успеть, но стоит иметь в виду.