вторник, 29 января 2013 г.

Лямбды, блоки, замыкания


Этот текст не совсем статья в блог. Это слайды к презентации, перемешанные с текстом, который я говорил на выступлении, одной картинкой "от Кутейко" и парой пояснений. Это максимум времени, который я готов в это проинвестировать, поэтому, простите за некопирующийся исходный код. Весь код, который есть на картинках, есть в специальном github репозитории.


Лямбды, блоки, замыкания.







То, что было для меня лично наибольшим открытием в Руби - это блоки. Я до этого мало писал в Джаваскрипте и много - на Джаве, и удобство конструкций вида select, reject, inject, map, то, как они меняют способ думать о коде и решаемой задаче буквально покорило меня. Функции высшего порядка теперь неотъемлемая часть нашего арсенала и без них настолько неуютно, что язык, который их не поддерживает в буквальном смысле неполноценен.

Однако же, идея блоков кода или функций высокого порядка далеко не нова. Концепт блоков и замыканий появился через несколько лет после того, как Джон Маккарти написал первую версию языка Лисп. Позднее, он был взят на вооружение Сассманом и Стилем, когда они создавали диалект Лиспа, который называется “Схема”.




Внутри Руби представляет блоки как структуры С типа rb_block_t. Что же такое блоки? Давайте заглянем в описание этой структуры - это может пролить свет. 




Во-первых, очевидно там должен лежать кусок Руби кода или набор скопмилированных инструкций байт-кода YARV.

В примере, когда мы отдаём блок в метод times объекта 10, метод должен знать, какой код исполнять.



Однако же, интересной особенностью блоков в Руби является то, что код в них имеет доступ к лексическому окружению блока.

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

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

Так как же это работает?






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

Эта самая идея и взята на вооружение в Руби.





В нашем примере, при выполнении первой строки кода YARV сохранит локальную переменную str_ext в свой внутренний стек и сохранит её расположение в указателе EP (environment pointer), расположенном в структуре rb_control_frame_t.



Дальше идёт вызов “10.times do”. Поскольку порядок вычислений в Руби аппликативный, сначала вычислятся аргументы метода times, в нашем случае - блок. Руби создаст и проинициализирует новую структуру rb_block_t. В структуре кроме уже обсуждённого iseq есть свой указатель на окружение (EP), который показывает на текущий кадр стека. То есть, в блоке сохранён указатель на кадр стека, в котором создан блок.



Потом происходит вызов метода times на объекте 10. Создаётся новый кадр в стеке YARV. Метод Fixnum#times написан на С, но ход выполнения такой же, какой был бы, если бы метод был написан на Руби - перебираются числа от нуля до девяти и с каждым из этих чисел в качестве аргумента вызывается yield блока. Код, который выполняет yield блока, для того, чтобы выполнить инструкции, скомпилированные в iseq создаёт третий кадр в стеке YARV (там есть ещё один кадр в стеке непосредственно перед вызовом блока, но это не поможет нам сейчас рассуждать о замыканиях).





Итак мы видим три кадра стека:

  1. Кадр блока, содержит переменную str.
  2. Кадр Fixnum#times.
  3. Кадр верхнего уровня содержит переменную str_ext.

В процессе создания кадра стека для блока Руби копирует EP из блока в новый кадр стека. Теперь код внутри стека имеет доступ и к своим локальным переменным через rb_control_frame, и к переменным родительского кадра стека через EP с помощью динамического доступа к переменным. В нашем случае это помогает коду в блоке достать переменную str_ext.


Вот код, который обеспечивает динамический доступ к переменным. Макрос GET_EP возвращает EP текущей области видимости. Потом Руби перебирает все EP, передвигаясь от текущей области видимости к родительской и так далее. Для этого используется макрос GET_PREV_EP, который переходит к родительской области видимости. И вот EP кадра стека, в котором непосредственно исполняется код блока, указывает в качестве родительского на кадр, в котором объявлена переменная str_ext.

Помните? Замыкание - это структура, состоящая из лямбда-выражения, т.е., функции и окружения, которое будет использовано в момент вызова лямбды или функции.




Рубишный блок соответствует этому определению - вот функция (iseq), а вот указатель на окружение. Там ещё есть self, это очень важная часть замыкания, как мы увидим позже, и proc, используемый внутри для преобразования блока в proc, когда нужно.

Сравните определение с rb_control_frame_t. С self до proc они совпадают. Помните, когда блок только создаётся, в него копируется часть переменных, описывающих текущее окружение, в частности EP. Так вот, на самом деле Руби ничего не копирует. а вместо этого выставляет указатель прямо в середину структуры rb_control_frame_t. Подобная утиная типизация выглядит немного странно, но без неё создание блоков тормозило бы гораздо ощутимее - мы избегаем лишних операций malloc.




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



Давайте взглянем на другой кусок кода. Здесь с первого взгляда тоже блок, но не совсем. В функции get_helloer я с помощью ключевого слова lambda создаю и возвращаю некий блок кода - то, что обычно называют функцией высшего порядка или функции как граждане первого класса, сохраняю его в переменную и затем вызываю. С помощью ключевого слова lambda и, как обычно в Руби, ещё пары способов, блок можно превратить в такую сущность, которую можно возвращать как результат и передавать как аргумент. Лирическое отступление - почему лямбда?



В 1930-х годах Алонзо Чёрч ввёл лямбда-нотацию в своём исследовании "Лямбда-исчисление"

Лисперы привыкли к слову лябмда для создания анонимных функций, однако, не в Лиспе это придумано. Этот термин пришёл из труда Алонзо Чёрча “Лямбда-исчисление”, написанного в 1930-х. На этот труд ссылаются как Маккарти в своём историческом “Рекурсивные функции над символьными выражениями и их машинное вычисление” 1960-го, с которого берёт начало Лисп, и Сассман и Стиль в своей исторической статье “Схема: интерпретатор для продвинутого лямбда-исчисления” 1975-го, с которого берёт начало Схема.

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






Что там, внутри лямбды?




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

Итак, почему же в нашем коде сборщик мусора не съедает str_ext?






При создании лямбды, Руби создаёт копию кадра стека в куче! Теперь там есть ссылка на str_ext и переменной ничего не угрожает. Кроме этого, создаётся ещё два объекта:

  1. rb_ent_t - это обёртка для копии стека в куче и
  2. rb_proc_t - это наша лямбда.

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

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





Теперь видно, что когда мы вернёмся из функции, переменная str_ext уцелеет, потому что мы возвращаем лямбду, указатель на которую лежит в стеке. Лямбда, в свою очередь, ссылается на rb_env_t, которая среди всего прочего ссылается на str_ext.

Наконец, мы вызываем лямбду.





Единственная разница здесь с блоком в том, что родителем EP указана структура rb_env_t в куче.

Итак, есть важная разница между блоками и лямбдами. Лямбды - граждане первого класса, они включают структуру RBasic и представляют собой объекты Proc. Ну, это не совсем так, но с поправкой на абстракцию думать так можно.

Теперь давайте поэкспериментируем с замыканиями.




Посмотрите на этот код и скажите, что он, по-вашему выведет.

Конечно же, он выведет “Goodbye there!”

Как так? Ну, я забыл рассказать кое-то ещё. Руби не только копирует кадр стека в кучу, но ещё и выставляет EP структуры rb_control_frame_t на только что созданную копию.





Теперь в дальнейшем мы работаем с копией стека в куче. Зачем? Чтобы не копировать стек каждый раз, когда мы создаём лямбду.

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

Это даёт интересную с академической точки зрения возможность навертеть своё ООП.



Собственно, это даёт понимание того, что лексические замыкания - концепция более мощная, чем объектно-ориентированное программирование и ООП реализуется с их помощью легко и быстро.

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

Зачем же нам нужны блоки, если хватает лямбд? Производительность.



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

Вот разница того, что происходит в этих кусках кода:





Это "декомпилированные" функции из бенчмарка. Слева yield, справа &block.

Видно, что для вызова yield достаточно низкоуровневой инструкции "invokeblock". А вот второй вариант вынужден создавать объект и посылать ему сообщение "call". Понятно откуда накладные расходы. Тут и диспетчеризация и нагрузка на GC и чёрт знает что ещё. Дело в том, что интерпретатор не в состоянии предсказать, что произойдёт с блоком и вынужден отбросить оптимизации. Из блока строится Proc.

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

В конце вкратце коснусь JRuby и Rubinius.






JRuby не использует стек JVM тем способом, которым MRI использует стек YARV. Эквивалента EP в JRuby тоже нет. Вместо этого используется набор Java классов, и в особенности DynamicScope. Когда вы ссылаетесь на переменную не из своего окна, то есть, пользуетесь замыканием, JRuby сохраняет переменные, на которые вы сослались, в DynamicScope (на самом деле, в одном из его подклассов). Позже, когда JRuby выполняет блок, он создаёт новый объект DynamicScope, который ссылается на “родительский”. Каждый DynamicScope содержит ссылку на включающий его scope - так в JRuby реализован динамический доступ к переменным.




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

Комментариев нет:

Отправить комментарий