"И назову ее лямбда..."

ru_declarative — 25.01.2010 X-Posted: http://kouzdra.livejournal.com/327847.html
X-Posted: http://lj.rossia.org/users/kouzdra/813843.html
X-Posted: http://community.livejournal.com/ru_declarative/94117.html

Прочитал тут в треде диалог про лямбды:

vitus-wagner: ... Ну в общем, похоже. Если бы в C можно было разместить функцию в динамической памяти - malloc-ом.
:
То есть это функция, тело которой существует только постольку, поскольку мы где-то храним или куда-то передаем на нее ссылку. (учитываем, что у нас язык с garbage collection, и как только у нас исчезла последняя ссылка на объект, он из памяти удалился)

karpion: А как код оказывается в памяти? Чем заполняется область при malloc()?

vitus-wagner: Ну у нас же на самом деле не C.

Вот соответственно, в теле оператора lambda и написан тот самый код, который нужно скомпилировать во внутреннее представление (байткод) и ссылку на него вернуть. Потом она будет передана куда-то в качестве параметра или чему-то присвоена.

И, натурально, испугался. И решил на конкретном примере компилятора O'Caml в нативный код рассказать, как это все устроено на самом деле - в командах, битиках и байтиках. Возможно, что это все знают и так, но есть большие сомнения.

Техническое предуведомление:

Приводимый ниже код является вполне реалистичным, но не 100% "из под компилятора" - отчасти потому что приходилось искусственными мерами давить проявления компиляторного интеллекта (например стремление все заинлайнить или соптимизировать хвостовую рекурсию), отчасти потому что имена приведены в человеческий вид, а сам код прочищен от лишних меток, отладочной информации etc

Как вообще реализуются функции:

Как известно согласно великой науке про страшное слово "карринг"

let f x y = x + y 

Это синтаксический сахар для:

let f = fun x -> (fun y -> x + y)

То есть функция от х, значением которой является функция от у, увеличиваяющая y на x

Так вот - забудьте, на самом деле

let f x y = x + y 

реализуется довольно традиционно: как функция от 2 аргументов, которые она получает в %eax и %ebx, а результат выдает в %eax (а в случае большего числа аргументов - пока регистров хватает - то в регистрах, а то, что не влезло - в стек - обычные вполне соглашения о связях):

f:
        lea     -1(%eax, %ebx), %eax
        ret

Сложение тут так странно выглядит потому, что целые, как и все unboxed значения в OCaml представляются сдвинутыми на 1 влево + 1 в младшем бите. Как видите, все как обычно. Пример вызова приводить не буду в силу очевиности.

Функция, как first-class value:

Теперь посмотрим, что происходит, когда функция передается в качестве параметра:

let apply_rev x f = f x
let _ =  apply_rev 10 (fun x -> x + 1)

Выглядит получающийся код так:

apply_rev:
        movl    (%ebx), %ecx
        call    *%ecx
        ret

_main:
        movl    $fun_closure, %ebx
        movl    $21, %eax   
        call    apply_rev
        movl    $1, %eax
        ret

        .long   2295
fun_closure:
        .long   fun
        .long   3

fun:  
        addl    $2, %eax
        ret

Обращаю внимание, что пока никаких malloc'ов нет.

Итак "что все это значит": функция fun - это, как не сложно догадаться fun x -> x + 1, а вотд fun_closure уже интереснее:

Это так называемое "замыкание" (closure) функции fun - та самая структура, адрес которой и представляет функцию, как first-class value. В нашем случае она вырождена. Слово, предшествующее метке fun_closure - служебное, содержащее управляющую информацию для gc (в частности - размер замыкания). Дальше идет адрес функции, замыкание которой образуется, после чего - количество ее аргументов (в принятом в OCaml представлении - n * 2 + 1).

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

В более традиционных языках (Algol-60, Pascal, PL/I, Algol-68, Ada, etc) и в функциональных функции могут быть вложены в другие функции и иметь доступ к их локальным переменным, поэтому в значение представляющее адрес функции должна как засовываться информация, позволяющая как минимум осуществлять к ним доступ. Это можно делать по разному, один из способов, в функциональных языках общепринятый, это представлять функцию в виде замыкания - то есть в виде блока, содержащего адрес функции и копии всех входящих в ее контекст значений, за исключением глобальных переменных.

При этом само замыкание передается в функцию в качестве "n+1"-го параметра. В нашем примере - в %ebx.

Для функциональных языков это тем более удобно, поскольку переменные в них immutable (а то, что кажется переменными - ref, mutable поля записей etc всегда являются полями данных, доступных по ссылке - которая immutable) - соответственно нет проблемы поддержания актуальности этих значений (это, кстати, как раз та причина, по которой в Java в анонимных классах можно ссылаться только на final переменные)

NB: Если не хотеть иметь возможности создавать функции высших порядков, а ограничиваться call-backs, замыкания и куча не нужны и в "старых" языках со вложенными функциями использовались другие методы реализации (если интересно могу рассказать как-нибудь как это делалось)

Итак приведенный выше код теперь понятен:

apply_rev:
        movl    (%ebx), %ecx
        call    *%ecx
        ret

apply_rev получила в %eax аргумент x, в %ebx - замыкание функции-параметра f, и должна вызвать лежащую в первом слове замыкании функцию, передав ей первый и единственный параметр в %eax (где он уже находится) и адрес ее замыкания - в %ebx (где он тоже уже находится). Что она и делает - вынимает адрес функции и вызывает ее. В реальном примере компилятор еще делает тут tail-call оптимизацию, так что реальный код выглядит так:

apply_rev:
        movl    (%ebx), %ecx
        jmp    *%ecx

Замыкания, серия вторая: функции высших порядков:

Самый, наверное, стандартный пример - функция композиции. Но мы ее чуть-чуть изменим: пусть она еще печатает строчку:

let compose f g  =
  print_string "compose called\n";
  fun x -> f (g x)

let _ = compose succ pred

печать текста я вставил исключительно, чтобы компилятор не склеил фукнции и не превратил compose из бинарной в тернарную функцию, что дало бы не совсем тот код, который мне нужен для иллюстрации. Тут уже код получается более интереcный:

compose:
        subl    $8, %esp

        movl    %eax, 0(%esp)
        movl    %ebx, 4(%esp)
        movl    $camlMain__6, %ebx
        movl    camlPervasives + 92, %eax
        call    camlPervasives__output_string_215

        movl    $20, %eax
        call    caml_allocN
        leal    4(%eax), %eax
        movl    $4343, -4(%eax)
        movl    $composition_fun, (%eax)
        movl    $3, 4(%eax)
        movl    0(%esp), %ebx
        movl    %ebx, 8(%eax)
        movl    4(%esp), %ebx
        movl    %ebx, 12(%eax)

        addl    $8, %esp
        ret

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

То есть это замыкание содержит одноместную функцию и - в первый раз - содержательный контекст: адреса замыканий функций, которые переданы compose в качестве параметров. А вот и сама функция, которая реализует композицию: Она берет

composition_fun:   
        subl    $4, %esp
        movl    8(%ebx), %ecx
        movl    %ecx, 0(%esp)   -- замыкание функции f сохраняется в стеке
        movl    12(%ebx), %ebx  -- замыкание функции g загружается в %ebx, в %eax параметр
        movl    (%ebx), %ecx 
        call    *%ecx           -- вызов функции g x
        movl    0(%esp), %ebx   -- загрузка из стека замыкания f
        movl    (%ebx), %ecx
        addl    $4, %esp
        jmp     *%ecx           -- хвостовой вызов f (g x)

Вот и все. Никакого "кода в стеке" естественно не генерируется.

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

Upd: И все-таки я был неправ - тайну "счетчика параметров" я не раскрыл, а она тут существенна: придется дописывать. Ждите.

Так вот - налицо загадка тайны брюквы - вопрос, а зачем нужно в замыкании держать количество аргументов? А ответ довольно простой - как раз для реализации карринга: у нас до сих пор все было замечательно и фактическая арность функций в замыкании совпадала с "формальной" - ради этого и была вставлена строчка print_string "compose called\n";. Давайте ее уберем:

let compose f g  =  fun x -> f (g x)

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

let compose = fun f  ->  fun g  ->  fun x -> f (g x)

в самом буквальном смысле слова: на уровне синтаксического дерева они не отличимы и потому в таком виде compose оказывается тернарной функцией, а не бинарной, возвращающей унарную:

compose:
        subl    $4, %esp
        movl    %eax, 0(%esp) -- сохранение f
        movl    %ecx, %eax    -- x -> %eax
        movl    (%ebx), %edx  -- адрес точки входа g в %edx
        call    *%edx

        movl    0(%esp), %ebx  -- f -> %ebx
        movl    (%ebx), %ecx   -- адрес точки f в %ecx
        addl    $4, %esp       -- сброс стека
        jmp     *%ecx          -- хвостовой вызов f (g x)

А теперь представьте себе что мы хотим сделать композицию двух функции - например let dummy = compose succ prev:
А обязательным условием для замыкания является то, что арность функции там должна соответствовать ее типу: иначе при попытке вызвать в параметрах будет черте что. Итак - нам надо из тернарной функции сделать унарную.

Самый очевидный способ - сгенерировать функцию-wrapper:

let sp = fun x -> compose succ pred x

Этот вариант дает вполне нормальный результат:

sp:
        movl    %eax, %ecx   -- пересылка
        movl    $prev_closure, %ebx  -- замыкания для prev
        movl    $succ_closure, %eax  -- и succ  формируется статически
        jmp     compose

Но в реальности O'Caml делает не так. У него есть набор "функций переходников": которые и используются в таких случаях. И вот им-то как раз в некоторых случаях и нужно знать число аргументов. Но вот это уже точно отдельным постом. А то и так многа букав. К тому же - я задумался над вопросом, о том почему там такие сложности.

Хотя обращу внимание - загадка тайны брюквы пока не так и не раскрыта.

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

Популярные посты:

• Архив