Эффективное изложение информации

[Mihaylo]

Возьмем рассмотренный ранее пример пирамидальной сортировки на языке Java:

(Оффтоп)

/**
* Класс для сортировки массива целых чисел с помощью кучи.
* Методы в классе написаны в порядке их использования. Для сортировки
* вызывается статический метод sort(int[] a)
*/
class HeapSort {
   /**
    * Размер кучи. Изначально равен размеру сортируемого массива
    */
   private static int heapSize;
   
   /**
    * Сортировка с помощью кучи.
    * Сначала формируется куча:
    * @see HeapSort#buildHeap(int[])
    * Теперь максимальный элемент массива находится в корне кучи. Его нужно
    * поменять местами с последним элементом и убрать из кучи (уменьшить
    * размер кучи на 1). Теперь в корне кучи находится элемент, который раньше
    * был последним в массиве. Нужно переупорядочить кучу так, чтобы
    * выполнялось основное условие кучи - a[parent]>=a[child]:
    * @see #heapify(int[], int)
    * После этого в корне окажется максимальный из оставшихся элементов.
    * Повторить до тех пор, пока в куче не останется 1 элемент
    *
    * @param a сортируемый массив
    */
   public static void sort(int[] a) {
      buildHeap(a);
      while (heapSize > 1) {
         swap(a, 0, heapSize - 1);
         heapSize--;
         heapify(a, 0);
      }
   }
   
   /**
    * Построение кучи. Поскольку элементы с номерами начиная с a.length / 2 + 1
    * это листья, то нужно переупорядочить поддеревья с корнями в индексах
    * от 0 до a.length / 2 (метод heapify вызывать в порядке убывания индексов)
    *
    * @param a - массив, из которого формируется куча
    */
   private static void buildHeap(int[] a) {
      heapSize = a.length;
      for (int i = a.length / 2; i >= 0; i--) {
         heapify(a, i);
      }
   }
   
   /**
    * Переупорядочивает поддерево кучи начиная с узла i так, чтобы выполнялось
    * основное свойство кучи - a[parent] >= a[child].
    *
    * @param a - массив, из которого сформирована куча
    * @param i - корень поддерева, для которого происходит переупорядочивание
    */
   private static void heapify(int[] a, int i) {
      int l = left(i);
      int r = right(i);
      int largest = i;
      if (l < heapSize && a[i] < a[l]) {
         largest = l;
      }
      if (r < heapSize && a[largest] < a[r]) {
         largest = r;
      }
      if (i != largest) {
         swap(a, i, largest);
         heapify(a, largest);
      }
   }
   
   /**
    * Возвращает индекс правого потомка текущего узла
    *
    * @param i индекс текущего узла кучи
    * @return индекс правого потомка
    */
   private static int right(int i) {
      return 2 * i + 2;
   }
   
   /**
    * Возвращает индекс левого потомка текущего узла
    *
    * @param i индекс текущего узла кучи
    * @return индекс левого потомка
    */
   private static int left(int i) {
      return 2 * i + 1;
   }
   
   /**
    * Меняет местами два элемента в массиве
    *
    * @param a массив
    * @param i индекс первого элемента
    * @param j индекс второго элемента
    */
   private static void swap(int[] a, int i, int j) {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
   }
}

Я, к сожалению, не силен в Java, но что-то понимаю в C++. Представим себе, возникла ошибка обращения к массиву за пределами выделенной памяти, такая ошибка возможна в C++. В этом случае разработчику актуален вот такой вид листинга (в нем скрыто все, кроме массивов):

class HeapSort {

   ...;
   
   public static void sort(int[] a) {
      ...
      }
   }
   
   private static void buildHeap(int[] a) {
      ...
      }
   }
   
   private static void heapify(int[] a, int i) {
      ...;
      if (... && a[i] < a[l]) {
         ...;
      }
      if (... && a[largest] < a[r]) {
         ...;
      }
      ...
   }
   
   private static int right(int i) {
      ...;
   }
   
   private static int left(int i) {
      ...;
   }
   
   private static void swap(int[] a, int i, int j) {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
   }
}

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

Непонятно? User story:
Разработчик ищет текст ошибки, пусть она формулируется как "Out of memory" (поиск не в гугле и на stackoverflow, а прямо в IDE). Такой текст обнаруживается в одном из абстрактных описаний в файле "windows10_build2021H1.ied" как объект типа "terminal". Вау круто! Теперь благодаря абстрактным описаниям можно найти абстрактную связь между данным сообщением (терминалом) и обращениями к массивам, то есть построить тот сокращенный листинг кода, который я привел чуть выше.

Теперь само абстрактное описание (оно включает в себя описание компилятора ЯП, рантайма и описание операционной системы):

array_list = abstract(parse(source_code, '\t[] \v')) // про парсинг объявлений массивов в коде, source_code - текст кода, \t - тип данных, \v - имя массива

array_access_list = abstract(parse(source_code, '\v[\e]')) // тут про то, что компилятор парсит обращения к массиву - имя \v и выражение \e для вычисления индекса, я не привожу описание функции parse(), так как оно и так понятно, но вообще описание parse() обязательно требуется

array_memory = abstract(array_list) // тут про выделение памяти для массивов

terminal array_out_of_memory_error = abstract(array_memory, array_access_list) // тут про то, что ошибка "Out of memory" возникает из-за выделенной памяти для массивов и обращений к этой памяти

В итоге это описание позволяет выследить две цепочки зависимостей:
array_out_of_memory_error → array_access_list → parse(source_code, '\v[\e]')
array_out_of_memory_error → array_memory → array_list → parse(source_code, '\t[] \v')

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

Иными словами, абстрактное описание хранит в себе информацию о том, что ошибка "Out of memory" возникает из-за объявления массивов и обращения к ним.

-- 09.04.2021, 21:49 --

Преимущества абстрактного описания:
1. Описание очень короткое и может быть написано не разработчиками компилятора и операционной системы, а энтузиастами.
2. IDE может найти актуальные участки в коде на основании лишь указания терминала и абстрактного описания.

* Терминал (конечная остановка) - это некий объект, который неким образом проявляется у пользователя. Частным случаем терминала может быть переменная (объект, функция и прочие сущности, в том числе непрограммные).

-- 09.04.2021, 21:58 --

В рассмотренном примере абстрактное описание аккумулирует в себе знания, которые опытный разработчик знает и использует следующим образом: он видит ошибку "Out of memory" -> понимает, что эта ошибка скорее всего вызвана работой с массивами -> находит все объявления массивов и обращения к ним. То же самое IDE может сделать автоматически.

Уровень экспертности IDE будет зависеть от уровня абстрактности/конкретности описания и уровня абстрактности/конкретности исследования зависимостей (чисто теоретически IDE могла бы указать не просто список объявлений массивов и обращений к ним, но и указать конкретные места ошибок).

[Mihaylo]

Я немного почитал теорию языков программирования (ТЯП) и решил выразить описание своего абстрактного языка в терминах этой теории.

Абстрактный язык паразитирует на грамматике одного из языков программирования (для простоты).
Привносится новое:
1. Абстрактная цепочка символов - это цепочка символов, содержащая символ неопределенности (...) или ключевое слово abstract.
2. Грамматическое правило: последовательно идущие символы неопределенности (...) в цепочке эквивалентны одному символу неопределенности (...). Данное преобразование производится автоматически, так как более короткая запись предпочтительна.

Хотя язык абстрактен, у него строгая грамматика.

Помимо данного простого абстрактного языка еще вижу потребность в более сложном языке, в котором для каждого символа в цепочке сопоставлено целое число - счетчик использования. При операции использования цепочки или ее части, в том числе отдельного символа, счетчик соответствующих символов прирастает на единицу. Что за операция использования? Если это цепочка императивного ЯП, то операцией использования станет исполнение символа-инструкции процессором. Если в программе нет условных и безусловных переходов, циклов, вызовов функций, то счетчики использования прирастают одинаково. Переходы, циклы, вызовы функций вносят разнообразие в приращение счетчиков использования.
Удивительное свойство счетчиков использования - они отражают, насколько важен символ в цепочке.
1. GOTO делает более важной инструкцию, на которую он переводит, и делает менее важной инструкцию, следующую за GOTO.
2. IF-THEN-ELSE распределяет важность между инструкциями блоков THEN и ELSE. Чем важнее THEN, тем менее важен ELSE, и наоборот. Счетчики этих блоков можно соотнести с важностью условия IF и с важностью антиусловия, т.е. важностью могут обладать не только инструкции.
3. Цикл FOR/WHILE повышает важность инструкций в теле цикла по сравнению с инструкциями вне тела цикла.
4. Многократный вызов функции многократно повышает важность тела функции, хотя каждый из вызовов может быть однократным.

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

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

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

Вообще, может быть спорным тот момент, что счетчики использования относятся непосредственно к языку. Разрешить этот конфликт помогает следующее рассуждение: пусть язык описывает не общее поведение алгоритма, а конкретные значения, которые были получены в результате исполнения программы (язык логирования). Очевидно, что язык со счетчиками использования находится на каком-то промежуточном уровне абстракции между обычным ЯП и языком логирования. То есть язык со счетчиками является абстрактным по отношению к языку логирования. Для нас очень важно, что этот абстрактный язык логирования отличается всего лишь на массив целых чисел (счетчиков) от обычного ЯП.

Тут закралась одна важная мысль: разработчику недостаточно знания, как работает алгоритм, ему в идеале нужно логирование значений переменных, объектов. И это правда. Абстрактный язык логирования - это прекрасное частичное решение проблемы.

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

Счетчики использования привносят в разработку очень большой объем информации, я намеренно придумал данный "язык", чувствую потребность в нем. Таким образом начинающие разработчики могут сравнивать библиотечные функции по важности. Начинающие разработчики еще не успели воспринять частоту использования ментально путем долгих экспериментов, как это получается у опытных разработчиков. Проблема даже не в опытных/неопытных разработчиках, даже опытный разработчик может долго вникать в особенности использования системы без помощи извне.

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

[Mihaylo]

Я наверное зря ввел понятие языка логирования и абстрактного языка логирования. Думаю достаточно было одного абзаца с экскурсом в это. На самом деле нет никаких языков логирования.

Итак, просто есть система счетчиков использования, которые позволяет оценить частоту использования, то есть важность символа в некотором контексте использования.
При этом есть связь с абстрактным ЯП: если частота использования равна нулю или ниже некоторого порога, то от соответствующего символа можно абстрагироваться, т.е. заменить его на символ неопределенности (...).

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

Благодаря автоматизации сбора значений счетчиков может складываться общая картина использования кода и эта информация будет доступна для анализа средствами IDE. IDE может скрывать (абстрагироваться от) менее востребованные части кода. Новый разработчик в команде может увидеть код глазами тех разработчиков, которые уже "в теме".

Эти возможности имеют научное обоснование.

[Mihaylo]

Забавная штука. Начал гуглить, кому нужны мои идеи умной IDE. Загуглил Jetbrains с ее средой разработки IntelliJ, попал на википедию. Оттуда прошел по ссылке покрытие кода.
Покрытие кода - это по сути и есть счетчики использования. Однако используется для другого, для тестирования кода.

[Mihaylo]

Регулярно устраиваю мозговой штурм касательно применения своего абстрактного языка.

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

y = abstract(x1, x2, x3, ...)

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

Например, можно определить, что некоторые объекты в коде document1, document2, document3 образуют систему документации. Однако этот нюанс может быть не отражен в коде, три данных объекта не имеют никакой связи между собой, кроме того, что у них похожи имена. Тогда можно написать такое абстрактное описание:

terminal doc_system = abstract(document1, document2, document3)

Абстрактная функция позволяет лениво описать тот факт, что несколько документов образуют структуру с именем doc_system. Более подробное и точное описание могло включать в себя конструкцию struct {}.

terminal struct doc_system {document1, document2, document3}

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

Таких структур, которые объединяют переменные и функции в коде, на самом деле очень много. Среди них я выделяю стандартные терминалы, например:
terminal Graphics
terminal Graphics.Console
terminal Graphics.OS
terminal Filesystem
terminal Database
terminal Keyboard
terminal Mouse
и т.д.

Вы могли бы указывать терминалы в навигаторе IDE и от этого подсвечивались бы (раскрывались бы) те участки кода, которые содержат переменные, объекты, события, которые отслеживались бы благодаря абстрактным описаниям.

Вообще, строго говоря, если зациклиться на одних абстрактных функциях, то в общем-то никаких абстрактных описаний и не нужно было бы. Можно было бы просто указать мышью ряд объектов в коде и связать с некоторой сущностью в IDE и не заморачиваться с абстрактным языком. Однако это работает лишь для связывания конкретных объектов кода, по имени которых можно ткнуть мышью в коде.
Можно написать такое абстрактное описание, которое позволило бы парсить код и находить в нем такие терминалы как массивы (terminal arrays), условия "если" (terminal if_conditions) и другие языковые конструкции. В отличие от конкретных объектов в коде, такие терминалы обладают свойством обобщения, т.е. не требуют указания имени. Обобщенные терминалы могли бы участвовать в более сложных высокоуровневых абстрактных описаниях, таких как описания ошибок. С другой стороны, IDE, используя достаточно точное описание функций парсинга кода, может по обобщенным описаниям находить конкретные объекты в коде.
Иными словами, благодаря абстрактным описаниям, IDE может автоматизированно выполнять действия разработчика. Разработчик узнает на stackoverflow, что некоторая ошибка может возникать из-за обращения к массивам в коде - он находит все обращения к массивам в коде. Фактически, когда IDE парсит код, она выполняет совершенно те же действия, которые разработчик выполняет при ручном поиске. Абстрактное описание парсинга кода и терминалы, связанные с этим, должны иметь важное значение для автоматизации разработки. Эти вещи прячутся в голове программиста в виде порядочно-беспорядочных моделей, и эти модели в своем подавляющем большинстве стандартны.

Кто-то бы мог додуматься написать программу-навигатор, которая находила бы в коде участки, которые релевантны тому или иному терминалу. Однако моя идея заключается в том, чтобы использовать для этого абстрактные модели, в той или иной мере, соответствующие реальности (туманным представлениям в голове команды разработчиков).

Среди промежуточных терминалов можно выделить, например, паттерны проектирования. Если бы IDE могла распознавать паттерны, то появился бы дополнительный инструмент и элемент абстрактного языка. Это было бы поддержкой в общении двух разработчиков "через код": если один разработчик создал паттерн, то второй заметил бы это благодаря абстрактному описанию паттерна и подсказке IDE.

На самом деле, с помощью абстрактного языка можно было бы не только анализировать имеющийся код, но и создавать новый. Например, можно задать абстрактную функцию, которая описывает связь между терминалами Keyboard, Graphics.Console и Printer. Под этой абстрактной функцией следовало бы понимать некий конкретный код, который еще предстоит разработать. Поэтапная разработка заключается, по сути, в устранении символов неопределенности (...) и abstract из абстрактного описания и заменой их на конкретные цепочки символов. Здесь также можно изобрести механизмы поддержки со стороны IDE.