Это первая из серии статей, в которых я хочу передать то, что я узнал (или то, что я думаю, что узнал) из книг, статей и лекций Александра Степанова.

Вот уроки, которые дает нам Алекс, и я хочу показать их в этой серии:

  • Укажите наши алгоритмы правильно
  • Программирование должно основываться на прочном математическом фундаменте.
  • Последовательное проектирование нашего API
  • Не всегда реализации библиотек, предоставляемые языками программирования, которые мы используем, являются правильными, даже если они разработаны «экспертами».
  • Концепция стабильности
  • Универсальное программирование [1], конечно!

И… следующий урок мой:

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

Написание мин

Я попробую написать функцию min, то есть функцию, которая возвращает минимум двух вещей.

В это время вам может быть интересно, этот парень пишет целую запись в блоге о двухстрочной функции, это серьезно? Ответ положительный. Как говорит Алекс: «Простые вещи прекрасны», и, хотите верьте, хотите нет, мы можем многому научиться в процессе написания min.

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

"Лучше проектировать наши Компоненты (алгоритмы и структуры данных) не с точки зрения конкретных типов, а с точки зрения требований к типам, выраженным в виде синтаксических и семантических свойств"

Алекс называет набор требований Концепцией[3].

Несмотря на отсутствие поддержки Concepts в языках программирования, он десятилетиями использует их не в коде, а в уме и в документации разработанных им компонентов [4].

Первая попытка

Что ж, давайте начнем писать спецификацию, а затем код:

Спецификация: учитывая два объекта[5], a и b, вернуть меньший из них.

//Note: Naive min function in pseudo-code (contains errors).
min(a, b) {
	if (a < b) return a
	return b
}

Вышеуказанная функция написана на псевдокоде (который выглядит как смесь между C и Python), имеет некоторые недостатки, но мы увидим их позже. .

Самый важный вопрос… Какие требования функция min должна предъявлять к аргументам a и b? То есть... Что такое Концепции?

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

Я категорически не согласен!

«Даже если у нас нет понятий в языке, они должны существовать в нашем сознании. Вы должны научиться мыслить понятиями, какой бы язык вы ни использовали».

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

a < b

Что это значит?

Кто-то может сказать, что требование состоит в том, что аргументы a и b должны сравниваться с использованием оператора «меньше».

Но это всего лишь синтаксическое требование, мы должны пойти дальше, чтобы правильно указать нашу функцию. Нам нужно включить семантику в наши требования к типу! Но как это сделать?

Математика в помощь!

Что такое меньше, чем оператор?

Это способ сравнения двух объектов, возвращающий логическое значение. Достаточно ли этого для определения функции min?

Нет, и чтобы проиллюстрировать это, посмотрите, что произойдет, если оператор «меньше чем» будет определен следующим образом:

//Pseudo-code for less-than-operator
less_than_operator(a, b) {
	if ( is_even(system_time().seconds) ) return true
	return false
}

Эта функция возвращает true, если количество секунд системного времени четно, иначе возвращает false. В этом коде я хочу подчеркнуть, что оператор less_than_operator может быть определен с использованием случайного поведения, но нам нужно определить конкретное поведение.

Математически оператор меньше-чем — это отношение[6]. Отношение — это бинарный Предикат[6].

То есть предикат, который принимает два параметра одного типа. Если вы смотрите на две вещи, это либо правда, либо ложь. Отношение сохраняется или нет. Разница между приведенным выше кодом и отношением заключается в том, что отношение считается Функциональной процедурой[6], т. е. функцией, в которой замена входных данных равными объектами приводит к одинаковые выходные объекты.

Но концепция отношения слишком слаба, нам нужна более сильная концепция: Порядок.

"Что такое заказ? Что математики называют упорядочением?

Единственным абсолютным правилом упорядочения является требование транзитивности [6]. Отношение является транзитивным, если, когда бы оно ни выполнялось между a и b, а также между b и c, оно выполняется между a и c. Транзитивное отношение — это самое основное понятие упорядочения, но оно все еще слишком слабо для наших нужд».

Давайте рассмотрим, какие виды отношений заказа существуют:

  • Частичное упорядочение. Частичное упорядочение – это отношение упорядочения, в котором не каждая пара элементов должна быть связана.
    Примеры:
    Каноническим примером частичного упорядочения является отношение подмножества.
    Подмножества упорядочены, одно подмножество может быть подмножеством другого подмножества, например, подмножество {2, 4} является подмножеством подмножества {1, 2, 3, 4}. Но бывает и так, что есть подмножества, о которых можно было бы и не говорить, например, заданные {2, 4} и {3, 5}. Какой из них больше? Какой из них включает в себя другой?
    Это не определено!
    У нас есть два вида частичного заказа:
    - Рефлексивный частичный заказ (или нестрогий частичный заказ ): отношение является рефлексивным частичным порядком, если оно транзитивно, рефлексивно[6] и антисимметрично[6].< br /> - Строгий частичный порядок (или нерефлексивный частичный порядок): отношение является строгим частичным порядком, если оно транзитивно и ирефлексивный[6] (он же асимметричный[6], но эта аксиома вытекает из иррефлексивности и транзитивности)
  • Общее упорядочивание: Общее упорядочивание – это отношение упорядочивания, в котором любая пара элементов в наборе отношения сравнима по данному отношению. Тотальный порядок — это специализация частичного порядка. Примеры: Действительные числа, упорядоченные по соотношению "меньше" (‹) (также рациональные, целые и натуральные числа). Буквы алфавита, упорядоченные по естественному словарному порядку.
    У нас есть два вида полного упорядочения:
    - Рефлексивный общий порядок (или нестрогий общий порядок): отношение является рефлексивным полным порядком, если оно транзитивно, антисимметрично и полно[6]. (это также рефлексивно, но подразумевается полностью)
    - Строгий общий порядок[6] (или Нерефлексивный общий порядок): отношение является строгим полным порядком, если он транзитивен и подчиняется закону трихотомии, согласно которому для каждой пары элементов выполняется ровно одно из следующего: отношение, его обратное или равенство. (Это также иррефлексивно, но эта аксиома вытекает из закона трихотомии)

(Примечание: есть и другие отношения порядка, но мы увидим их позже)

Написание мин с использованием концепций

Что ж, теперь мы знаем об отношениях порядка, давайте посмотрим, как мы можем использовать их для указания функции min.

Но сначала, что мы должны использовать? Частичный или полный заказ?

"Если наше отношение является отношением подмножества в наборе, то _min_ и _max_ двух наборов не имеет смысла".

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

Нам нужно использовать Total Ordering для определения требований min, давайте сделаем это:

// Requires:
//  The type of a is equal to the type of b, and it is called T,
//  and T is TotallyOrdered[6]
min(a, b) {
	if (a < b) return a
	return b
}
// Note: the implementations still has errors.

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

Ну, этого достаточно для одного поста.

В следующих статьях цикла мы:

  • завершить и исправить ошибки реализации min
  • напишите функцию max
  • уточнить требования min и max
  • реализовать их на реальных языках программирования
  • проанализировать API, предоставляемый некоторыми языками программирования.

Быть в курсе!

Сериал

Часть 1: Возникновение понятий

использованная литература

[1] Исходное определение универсального программирования:
Дэвид Р. Массер и Александр А. Степанов: универсальное программирование. ISSAC 1988, страницы 13–25. http://www.stepanovpapers.com/genprog.pdf
[2] Элементы программирования Александра Степанова и Пола МакДжонса:
http://www.elementsofprogramming.com
> Купить на Amazon
[3] Определение понятия: Степанов и МакДжонс [2009, стр. 10]
[4] SGI STL с использованием понятий в документации: https://www.sgi.com /tech/stl/min.html
[5] Определение объекта:
Определение, используемое в этой статье, не имеет ничего общего с ООП-подобным определением объекта [7]. Используемое здесь определение является практическим определением объекта: Объект — это последовательность битов в памяти или Объект — это значение, хранящееся в памяти. Полное определение см. в Stepanov and McJones [2009, стр. 4].

[6] См. Приложение А

[7] Создание объектно-ориентированного программного обеспечения (2-е изд.) Бертрана Мейера [1997, стр. 1198]

Первоначально опубликовано на componentsprogramming.com.