Самодокументированный код

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

Для начала договоримся об определениях

Самодокументированный код

Это програмный код, при переводе которого на русский язык получается хорошая техническая документация

Хорошая техническая документация

Техническая документация, достаточная для понимания кода

Сепульки

Сепульки — важный элемент цивилизации ардритов с планеты Энтеропия. См. Сепулькарии.

Операционная семантика

Понимание программы как последовательного набора инструкций. Иными словами, код `a = b + c` имеет операционную семантику "теперь a это сумма b и c"

Давайте посмотрим на отделенный от документации код

# Yields ordered prime numbers up to infinity
# It uses "Sieve of Eratosthenes" algorithm to find all primes less than 8192
# After it reached it rebuild sieve with limit increased twice
# It takes only O(n**2) to take first n primes
class PrimeEnumerator
  # @return [Enumerator] enumeratior of prime numbers
  def self.enumerate!
    Enumerator.new do |x|
      instance = new
      loop { x << instance.next }
    end
  end

  def initialize
    @idx = 0
    @limit = 1
    @primes = []
  end

  # Returns next prime number and increments counter
  def next
    while @idx >= @primes.length
      lb = @limit + 1
      rb = @limit *= 2
      sieve = Array.new(rb - lb + 1) { true }

      # No one number in (n+1..2n) can factorize other, so we just have to
      # check already known primes
      @primes.each do |prime|
        j = (lb - 1) / prime
        sieve[prime * j - lb] = false while prime * (j += 1) <= rb
      end

      sieve.each_with_index do |is_prime, idx|
        @primes << idx + lb if is_prime
      end
    end

    @idx += 1
    @primes[@idx - 1]
  end
end

Вроде бы все понятно

не смотря на обилие документации код все равно не очень хорошо поддается анализу. Я не стал намеренно завышать ABC-сложность, так как полезность метрик очевидна безотносительно подхода к документации, поэтому разобраться в нем даже без документации вполне доступно каждому. Отсюда, кстати, следствие: отстутствие технической документации для простого кода — хорошая техническая документация. В то же время иметь хорошую документацию для публичного API все равно не лишне, поскольку в данном случае речь уже идет о контексте другого модуля.

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

Посмотрим, как можно увеличить количество документации,

чтобы код стал абсолютно понятен

# Yields ordered prime numbers up to infinity
# It uses "Sieve of Eratosthenes" algorithm to find all primes less than 8192
# After it reached it rebuild sieve with limit increased twice
# It takes only O(n**2) to take first n primes
class PrimeEnumerator
  # @return [Enumerator] enumeratior of prime numbers
  def self.enumerate!
    Enumerator.new do |x|
      instance = new
      loop { x << instance.next }
    end
  end

  # We have following instance variables:
  # @primes is an array of primes, which extends automatically when limit
  #   reached. We need to store them to evaluate next primes
  # @limit is not less than maximum prime number in @primes
  #   and less then next prime
  # @idx is next enumeration index in @primes
  def initialize
    @idx = 0
    @limit = 1
    @primes = []
  end

  # Returns next prime number and increments counter
  def next
    while @idx >= @primes.length
      # Increase @limit when all primes <= @limit already enumerated
      lb = @limit + 1 # left bracket
      rb = @limit *= 2 # right bracket

      # This array of booleans represents (lb..rb) part of Eratosthenes sieve
      # By defenition, Eratosthenes sieve is array where all multiplicators
      # of found are marked as "not prime" or false. We index it from 0
      # to rb - lb so wee need to add lb to all primes
      sieve = Array.new(rb - lb + 1) { true }
      @primes.each do |prime|
        j = (lb - 1) / prime
        sieve[prime * j - lb] = false while prime * (j += 1) < rb
      end

      # No one element of (n+1..2n) can be multiplicator of other so all
      # indexes left true are primes
      sieve.each_with_index do |is_prime, idx|
        @primes << idx + lb if is_prime
      end
    end

    # increment counter as told
    @idx += 1
    # return prime as told (@idx already incremented)
    @primes[@idx - 1]
  end
end

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

Сформулируем это как Простой и короткий участок кода, соответствующий привычному паттерну, вполне самодокументирован

Мы уже умеем писать самодокументированный код

Разбиение кода на простые и короткие участки известно как процедурное програмирование

# Yields ordered prime numbers up to infinity
# It uses "Sieve of Eratosthenes" algorithm to find all primes less than 8192
# After it reached it rebuild sieve with limit increased twice
# It takes only O(n**2) to take first n primes
class PrimeEnumerator
  # @return [Enumerator] enumeratior of prime numbers
  def self.enumerate!
    Enumerator.new do |x|
      instance = new
      loop { x << instance.next }
    end
  end

  # We have following instance variables:
  # @primes is an array of primes, which extends automatically when limit
  #   reached. We need to store them to evaluate next primes
  # @limit is not less than maximum prime number in @primes
  #   and less then next prime
  # @idx is next enumeration index in @primes
  def initialize
    @idx = 0
    @limit = 1
    @primes = []
  end

  # Returns next prime number and increments counter
  def next
    increase_limit! while @idx >= @primes.length
    @idx += 1
    @primes[@idx - 1]
  end

  # Increase @limit when all primes <= @limit already enumerated
  def increase_limit!
    lb = @limit + 1 # left bracket
    rb = @limit *= 2 # right bracket

    sieve = build_sieve(lb, rb)
    collect_primes_from_sieve(sieve, lb)
  end

  # This array of booleans represents (lb..rb) part of Eratosthenes sieve
  # By defenition, Eratosthenes sieve is array where all multiplicators
  # of found are marked as "not prime" or false. We index it from 0
  # to rb - lb so wee need to add lb to all primes
  def build_sieve(lb, rb)
    @primes.each_with_object(Array.new(rb - lb + 1) { true }) do |prime, sieve|
      j = (lb - 1) / prime
      sieve[prime * j - lb] = false while prime * (j += 1) < rb
    end
  end

  # No one element of (n+1..2n) can be multiplicator of other so all
  # indexes left true are primes
  def collect_primes_from_sieve(sieve, lb)
    sieve.each_with_index do |is_prime, idx|
      # build_sieve return value is indexed from 0 instead from lb
      @primes << idx + lb if is_prime
    end
  end
end

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

Добро пожаловать в структурное программирование!

# Yields ordered prime numbers up to infinity
# It uses "Sieve of Eratosthenes" algorithm to find all primes less than 8192
# After it reached it rebuild sieve with limit increased twice
# It takes only O(n**2) to take first n primes
class PrimeEnumerator
  # This array of booleans represents (lb..rb) part of Eratosthenes sieve
  # By defenition, Eratosthenes sieve is array where all multiplicators
  # of found are marked as "not prime" or false.
  class EratosthenesSieveSlice
    Number = Struct.new(:value, :is_prime)
    # @array_representation is shifted by lower bracket of range
    def initialize(range)
      @range = range
      @array_representation = Array.new(@range.size) do |idx|
        Number.new(idx + range.begin, true)
      end
    end

    def [](idx)
      @array_representation[idx - @range.begin]
    end

    def remove_prime_multiplications(prime)
      multiplication = find_first_prime_multiplicator_in_range(prime)
      while multiplication <= @range.end
        self[multiplication].is_prime = false
        multiplication += prime
      end
    end

    def primes
      @array_representation.lazy.select(&:is_prime).map(&:value).to_a
    end

    private

    def find_first_prime_multiplicator_in_range(prime)
      # This code is operational self-documented
      ((@range.begin - 1) / prime + 1) * prime
    end
  end

  # @return [Enumerator] enumeratior of prime numbers
  def self.enumerate!
    Enumerator.new do |x|
      instance = new
      loop { x << instance.next }
    end
  end

  # We have following instance variables:
  # @primes is an array of primes, which extends automatically when limit
  #   reached. We need to store them to evaluate next primes
  # @limit is not less than maximum prime number in @primes
  #   and less then next prime
  # @idx is next enumeration index in @primes
  def initialize
    @idx = 0
    @limit = 1
    @primes = []
  end

  # Returns next prime number and increments counter
  def next
    increase_limit! while @idx >= @primes.length
    @idx += 1
    @primes[@idx - 1]
  end

  def increase_limit!
    sieve = EratosthenesSieveSlice.new((@limit + 1)..(@limit *= 2))
    @primes.each { |prime| sieve.remove_prime_multiplications(prime) }
    # No one element of (n+1..2n) can be multiplicator of other so all
    # non-primes removed
    @primes += sieve.primes
  end
end

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

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

Второй модуль более сложный в плане доказательста корректности (у нас там ТЕОРЕМА в комментариях), но сам по себе содержит очень мало кода и при условии корректности работы модуля решета его корректность не сложно вывести.

На этом в общем то в плане руби у нас все.

Является ли этот код само-документированным?

В моем понимании вполне. Доказательства теорем это еще не документация. Остались пояснения назначения переменных и классов, но это связанно в основном с разуменым ограничением на длину имени метода / класса. Единственное что не удалось уложить туда это апроксимацию сложности алгоритма

Давайте называть само-документированный с таким допущениями код вполне самодокументированным. Отсюда

Вывод

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

Напоследок,

проверим идею о том что функциональная парадигма нам поможет

module Data.Primes (
  primes
) where

import Data.List
import qualified Data.List.Ordered as Ordered

data EratosthenesSieveSlice = EratosthenesSieveSlice {
  entities :: [Integer]
, lower :: Integer
, upper :: Integer
}

primes :: [Integer]
primes = recursive [] 1
  where
    recursive primes upper =
      let slice = makeEratosthenesSieveSlice (upper + 1) (upper * 2)
          -- all numbers in slice could not be multiplier of other number
          -- so we can remove only known primes
          newPrimes = entities $
            foldl (removePrimeMultipliersFromSlice) slice primes
      -- as it is infinite recursion we should yield new primes imediatly
      in newPrimes ++ recursive (primes ++ newPrimes) (upper * 2)

makeEratosthenesSieveSlice :: Integer -> Integer -> EratosthenesSieveSlice
makeEratosthenesSieveSlice lower upper = EratosthenesSieveSlice {
  entities = [lower..upper]
, lower = lower
, upper = upper
}

removePrimeMultipliersFromSlice ::
  EratosthenesSieveSlice -> Integer -> EratosthenesSieveSlice

removePrimeMultipliersFromSlice slice prime =
  let multipliers = iterate (+ prime) prime
  in EratosthenesSieveSlice{
    entities = entities slice `Ordered.minus` multipliers
  , lower = lower slice
  , upper = upper slice
  }

Кстати, весьма лаконично, но сложно для понимания без знания паттернов. Я сильно сомневаюсь что документация тут поможет улучшить понимание.

Кстати, было бы прикольно посмотреть доказательство корректности на зависимых типах, то есть подобный код, который возвращает какой-нибудь PrimeInteger вместо Integer. Мы ведь уже дошли до этой стадии развития языков?