Category: авто

Dr.Strangelove

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

Часть в общем вторая к этому вот:

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

Итак: что на самом деле происходит в O'Caml при необходимости реализовывать частичное применение:

Там есть две группы встроенных функций
caml_curryN и caml_applyN, которые преобразуют ар-ность функций: примерно в таком смысле (на примере n=3):
caml_curry_3 fn = fun a -> fun b -> fun c -> fn a b c

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

Про caml_applyN:
caml_apply_3 fn a b c = fn a b c

А вот тут хитро: реально-то caml_apply_3 смотрит на указанное в замыкании число аргументов функции - если оно равно 3 - то он немедленно применяет fn к этим аргументам "напрямую" (адрес fn лежит в замыкании, создаваемом caml_curryN). Если же нет - то вызывает "поодиночке" столько замыканий, сколько надо - то есть "буквально" реализует синтаксис (((fn a) b) c).

То есть реальный код для примера из конца предыдущего поста
let compose = fun f  ->  fun g  ->  fun x -> f (g x)
let sp = compose succ pred

Будет:
       .long   3319
compose_closure:
        .long   caml_curry3
        .long   7              -- 3 аргумента
        .long   compose

_main:
        movl    $camlMain, %ecx
        movl    $pred_closure, %ebx
        movl    $succ_closure, %eax
        call    caml_apply2
        movl    %eax, camlMain + 4 -- сохранение результата-замыкания

compose: -- повтор из предыдущего поста
        subl    $4, %esp

        movl    %eax, 0(%esp)
        movl    %ecx, %eax
        movl    (%ebx), %edx
        call    *%edx

        movl    0(%esp), %ebx
        movl    (%ebx), %ecx
        addl    $4, %esp
        jmp     *%ecx



Вот в таком вот разрезе. Зачем это надо - точно сказать не возьмусь: гипотезы две - либо по результатам изысканий с профайлером там лучше, либо есть какие-то заморочки с полиморфизмом (весьма вероятно, кстати, восток полиморфизм - дело тонкое - там очень неожиданные вещи могут выплывать).
Dr.Strangelove

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

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 в нативный код рассказать, как это все устроено на самом деле - в командах, битиках и байтиках. Возможно, что это все знают и так, но есть большие сомнения.
Collapse )
Вот и все. Никакого "кода в стеке" естественно не генерируется.

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

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

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