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


Предыдущая часть:
1. Metaprogramming patterns — 25кю. Метод eval

bang-методы


В языке Ruby некоторые методы имеют два своих варианта — метод отображающий и метот преобразующий. Метод отображающий создаёт новый объект, а метод преобразующий преобразует объект на месте. Имена этим методам дают одинаковые, только к последнему добавляют в конец символ '!' (bang!!).

Примеры:
  • sort и sort! — по данному массиву можно получить новый отсортированный массив, а можно отсортировать его на месте
  • uniq и uniq! — по данному массиву можно получить новый массив без повторений, а можно удалить повторения в самом массиве на месте

Аналогичные пары имеем для методов select (отфильтровать элементы по заданному фильтру), map (преобразовать элементы массива согласно заданной функции) и flatten (раскрыть вложенные массивы, чтобы получился одномерный массив, элементы которого не есть массивы).
Такие пары методов встречаются не только для массивов, но и в других классах. Для строк мы имеем downcase и downcase!, upcase и upcase!, sub и sub! (замена первой найденной подстроки по образцу), gsub и gsub! (замена всех найденных подстрок), strip и strip! (удаление крайних пробельных символов),…

Напишем метод make_nobang



В закрепление материала предыдущего поста, напишем метод определяющ��й методы. Он будет называться make_nobang.

Представьте, что вы программист, которому поручили запрограммировать перечисленные выше методы класса String. Конечно, это слишком важные методы, чтобы программировать их на Ruby, а не на С (core классы Ruby написаны на C). Но тем не менее, давайте посмотрим, как можно было бы получить методы downcase, upcase, sub, strip, gsub, имея методы downcase!, upcase!, sub!, strip!, gsub!:
class String
  def downcase!
     ...
  end
  def  upcase!
     ...
  end
  def sub!
     ...
  end
  def strip!
     ...
  end
  make_nobang :downcase, :upcase, :sub, :gsub, :strip
end

Нужно только реализовать метод make_nobang:
class Module
  def make_nobang(*methods)
    methods.each do |method|
      define_method("#{method}") do |*args|
        self.dup.send("#{method}!", *args)
      end
    end
  end
end

Проверочный код может быть, например, таким:
class String
 def down!
   self.downcase!
 end
 make_nobang :down
end

a = "abcABC"
puts a.down
puts a
a.down!
puts a


К чему я пишу все эти простые, в принципе, вещи? У меня есть по меньшей мере три поинта:
1) Метод send. Познакомьтесь с методом send. Вы можете вызывать метод xyz у метода не только напрямую: a.xyz(1, 2), но и c помощью «передачи объекту сообщения»: a.send('xyz' ,1, 2). Принципиальная разница в том, что первый аргумент в последнем случае может быть вычисляемы выражением. Есть и другое различие — send игнорирует области видимости protected и private. Метод send — это следующий важный метод динамического программирования наряду с уже упомянутыми методами eval, class_eval, instance_eval, instance_variable_get, instance_variable_set, define_method.

2) Не бойтесь реюза в малом. Это нормально. Написать руками 5 * 3 похожих строк вместо одной программисту несложно. Но нужно понять важную вещь: программирование как деятельность сводится к чтению, написанию, говорению и слушанию. Вы только представьте, что вместо привычной фразы «Приятного аппетита» вы будете слышать «В связи с нашим совместным принятием пищи и доброжелательного моего к тебе отношения, желаю чтобы сия пища была тебе приятна и в конечном итоге была успешно переварена». Или вместо «добавь колбэк для моего хэндлера» будет произносится «добавь в свою функцию foo еще один аргумент handler, который будет иметь такой тип как функция bar, и это аргумент будет использоваться для вызова по нему функции для каждого итерируемого объекта в цикле функции foo». Слэнг вводится не только ради краткости, но и ещё и для того, чтобы упростить коммуникацию и взаимопонимание. Это позволяет осуществлять своеобразные микро-мета-системные переходы на уровне мышления программиста.

Ну и наконец:
3) На самом деле это непросто, а приведённый код не очень хорош и, более того, в некоторых случаях не работает. Пример:
class Array
 def m!(&block)
   self.map!(&block)
 end
 make_nobangs :m
end

a = [1,2,3]
puts (a.m{|i| i*i}).inspect
puts a.inspect

В результате вы получите
avoroztsov@subuntu:~/meta-lectures$ ruby -v make_nobang.rb
ruby 1.8.6 (2007-09-24 patchlevel 111) [i486-linux]
make_nobang.rb:27:in `map!': no block given (LocalJumpError)
        from make_nobang.rb:27:in `m!'
        from make_nobang.rb:6:in `send'
        from make_nobang.rb:6:in `m'
        from make_nobang.rb:33
avoroztsov@subuntu:~/meta-lectures$

Приведённая реализация make_nobang плоха, поскольку
1) сигнатура (здесь я имею ввиду лишь количество аргументов) получаемого метода отличается от сигнатуры исходного
2) не работает, если метод получает блок
3) делает метод с областью видимости public, хотя исходный возможно имел видимость private или protected.

Вот так вот!
С одной стороны это повод сказать, что всё это глупости и проще для каждого метода написать свои 3 строки.
С другой стороны, это как раз повод сделать такой метод make_nobang, чтобы он реально учитывал все тонкости, и чтобы при смене сигнатуры и видимости bang-метода не нужно было вносить соответствующие правки в nobang-метод. Кроме того, вызовы make_nobang можно обрабатывать автоматической системой документации.

Пункт 2 исправляется временем. В новой версии Ruby работает следующий код:
class Module
  def make_nobangs(*methods)
    methods.each do |method|
      define_method("#{method}") do |*args, &block|
        self.dup.send("#{method}!", *args, &block)
      end
    end
  end
end


Пункт 3 решается. См. методы private_methods, protected_methods,… для класса Object.

Пункт 1 тоже решается. По крайней мере, он решается с помощью eval. Cм. обсуждение Method#get_args где вы сможете вполной мере получить представление о том, что такое сигнатура метода в Ruby.

Метод make_bang



Методы sort и sort! уже есть у массивов. Но давайте, чтобы этот пост не пропал даром, напишем сами на Ruby быструю сортировку и реализуем методы qsort и qsort!

Метод 1



Попробуем использовать метод partition, определенный для экземпляров Enumerable:
class Array 
   def qsort
      return self.dup if size <=1
      # делить на части будем по первому элементу
      l,r = partition   {|x| x <= self.first}
      c,l = l.partition {|x| x == self.first}
      l.qsort + с + r.qsort # конкатенация трех массивов
   end
end


Метод 2


Удобно делить исходный массив сразу на три массива. Для этого определим метод partition3:

class Array 
   # given block should return 0, 1 or 2
   # -1 stands for 2
   # outputs three arrays
   def partition3
      a = Array.new(3) {|i| []}
      each do |x|
         a[yield(x)] << x
      end
      a
   end
   def qsort
      return self.dup if size <=1
      c,l,r = partition3 {|x| first <=> x}
      l.qsort + c +  r.qsort
   end
end


Необходима также версия функции сортировки, которая сортирует массив «на месте». Вот она:
class Array
   def qsort!
      self.replace(self.qsort)
   end
end
a = [1,7,6,5,4,3,2,1]
p a.qsort  # => [1, 1, 2, 3, 4, 5, 6, 7]
p a        # => [1,7,6,5,4,3,2,1]
a.qsort!
p a        # => [1, 1, 2, 3, 4, 5, 6, 7]


Но тоже самое можно было бы сделать, не пренебрегая метапрограммированием:
def make_bang(*methods)
  methods.each do |method|
    define_method("#{method}!") do |*args|
      self.replace(self.send(method, *args))
    end
  end
end
class Array
  make_bang :qsort
end


PS:


Надо сказать, что методы make_nobang и make_bang я придумал сам и ничего похожего пока в core и std, видимо, нет и не будет в ближайшее время. :)))
Это снова был исключительно учебный пример.

PSS: Вопросы на понимание и задачи



1. Почему у класса Set нет метода "sort!"? Почему у разных классов (например у Float) нет метода "to_i!"?
2. Почему нет унарного оператора "++"?
3. Как правильнее поступать: из bang-метода делать nobang-метод или наоборот?
4. Чем отличаются строки кода
а) a = a.sort.select{|x| x > 0}.uniq;
б) a.uniq!; a.select!{|x| x > 0}.sort!;
в) a.uniq!.select!{|x| x > 0}.sort!?
Какой из вариантов правильнее?
5. Попробуйте написать максимально правильный make_nobang.

6. Сравните два кода:
class Module
  def make_nobang(*methods)
    methods.each do |method|
      bang_method = "#{method}!"
      define_method("#{method}") do |*args|
        self.dup.send(bang_method, *args)
      end
    end
  end
end

и
class Module
  def make_nobang(*methods)
    methods.each do |method|
        define_method("#{method}") do |*args|
        self.dup.send("#{method}!", *args)
      end
    end
  end
end

Работает ли первый код? Доступна ли локальная переменная bang_method из создаваемого метода? Если доступна, то не чудо ли это? Она же локальная! А создаваемый метод будет вызываться потом, когда метод make_bang уже закончит свое выполнение!
Если всё таки оба способа работают, но какой из них эффективнее?