Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет kouzdra ([info]kouzdra)
@ 2010-01-25 18:00:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
"И назову ее лямбда..."
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 о связях не сохраняет никаких регистров - отсюда необходимость сохранять параметры в стеке), а вот то, что идет вторым блоком - как раз и есть создание замыкания, представляющего искомую суперпозицию: вот с такой структурой:

-4 Служебное поле
0 Адрес функции composition
4 число аргументов: 1
8 Параметр f
12 Параметр g

То есть это замыкание содержит одноместную функцию и - в первый раз - содержательный контекст: адреса замыканий функций, которые переданы 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";</tt>. Давайте ее уберем:

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 делает не так. У него есть набор "функций переходников": которые и используются в таких случаях. И вот им-то как раз в некоторых случаях и нужно знать число аргументов. Но вот это уже точно отдельным постом. А то и так многа букав. К тому же - я задумался над вопросом, о том почему там такие сложности.

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


(Добавить комментарий)


[info]ketmar
2010-01-28 13:35 (ссылка)
ты действительно считаешь, что для «среднего сишника» твоё пояснение понятней? %-)

алсо, в чём-то витус прав. в Схеме, например, именно что аналог malloc происходит и компиляция на лету (если REPL). да и в любом языке, где REPL/инкрементальная компиляция есть.

зыж по ссылке я, конечно, не ходил, и о чём там речь, не знаю.

(Ответить) (Ветвь дискуссии)


[info]kouzdra
2010-01-28 14:07 (ссылка)
afaik - в схеме, если ее специально не просить - точно так же. Там собственно и придумано.

да и в любом языке, где REPL/инкрементальная компиляция есть.

Ну вот в Жабе есть - в жабе замыкание именно так и устроено (только объект, а не блок в памяти)

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ketmar
2010-01-28 14:18 (ссылка)
ну так я специально про REPL поправился.

а в жабе, пардон, говно какое-то стрёмное, а не замыкания. то есть понятно, что можно эмулировать что угодно и на gw-basic, но зачем?

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

зыж вопрос: а для кого это пояснение вообще? у меня сложилось мнение что те, кто грок, уже и так всё это знают. а кто не грок, тем это марсианская письменность.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2010-01-28 14:26 (ссылка)
В жабе как раз внутри-то вполне нормально. И сахару подсыпано - но в ограниченных дозах. Видимо пожалели или ОО-чистоплюйство замучило.

а для кого это пояснение вообще?

Ну в среднем по моему опыту народ не знает - часто даже не осознает проблемы (и, например, того, что в Lisp нормальных замыканий нет).

Равно как и с обычными процедурами алгола-паскаля - например тот факт, что в турбопаскале-Delphi они не полностью реализованы, большинство imho просто не знает, и думает, что так и надо.

Что например передача метки параметром, путем обертывания goto на нее в локальную функцию - штука довольно хитрая. И семантика у нее довольно странная - это не аналог try-catch

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ketmar
2010-01-28 14:33 (ссылка)
>В жабе как раз внутри-то вполне нормально.
дык я ж не про VM (я вообще про JVM говорить ничего не хочу: я совершенно не помню, как она устроена, читал один раз и то пьяный).
однако же факт, что полный call/cc реализовать, по-видимому, не просто — у простых схем только ограниченый вариант. (и не спрашивай, к чему я это — сам не понял).

>например тот факт, что в турбопаскале-Delphi они не полностью реализованы
э? боюсь, не уловил, о чём ты.

>Что например передача метки параметром, путем обертывания goto на нее в
>локальную функцию — штука довольно хитрая

а кто позволяет такой изврат вообще? не, честно, я не делал так никогда (до таких извратов мой моск не доходил, я обычно или в continuation style тогда преобразовываю, или реализую longjmp, магика де гипноз, блин), потому и не знаю. calculated goto в gcc использую, да — для bytecode самое оно.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2010-01-28 14:53 (ссылка)
дык я ж не про VM

Так и я в основном не про VM - от VM там разве что то, что nested class знает конкретный экземпляр объемлющего (если он не static). А анонимные классы - как раз чисто синтаксическая реализация замыканий. Только почему-то остановились на этом и уродство вроде Runnable облагораживать не стали.

однако же факт, что полный call/cc реализовать, по-видимому, не просто

Я схемой особенно не интересовался - но по поводу ML - они зависят от выбранной модели реализации - в SML/NJ они есть (и реализуются совершенно элементарно), но это потому что там нет стека - все в куче живет.

э? боюсь, не уловил, о чём ты.

Не работает передача nested процедур параметрами.

а кто позволяет такой изврат вообще?

GCC, например, более того - в описании, на которое я кидал ссылку, есть примеры использования - для обработки ошибок. Да в общем-то я не знаю ни одного языка, где бы были вложенные функции и goto и который бы не позволял.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ketmar
2010-01-28 15:07 (ссылка)
>Так и я в основном не про VM
ну, я и жабу помню "в объёме церковно-приходской", то бишь минимум, который был необходим, чтобы быстро что-то набыдлокодить на jme. и уже в этом объёме она мне шибко не понравилась.

>но это потому что там нет стека - все в куче живет
авторы обычно говорят, что куча тормозит. я тоже у себя в схеме всё в куче держу, тогда всё элементарно, конечно.

>Не работает передача nested процедур параметрами.
а-а-а. да, запамятовал. а в GNU Pascal работает, по-моему. %-)

>GCC, например
мда. количество извращений, поддерживаемых gcc, не перестаёт умилять. %-)

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2010-01-28 15:42 (ссылка)
авторы обычно говорят, что куча тормозит

Ну SML/NJ и не летает, мягко говоря. Собственно одно из реальных достижений OCaml - демонстрация того, что ML может быть реализовано эффективно и без извратов в виде замкнутой системы.

Clean тем же ценен - был намного легче Haskell при том, что относится с ним примерно как OCaml с SML

мда. количество извращений, поддерживаемых gcc, не перестаёт умилять

Почему изврат? - они реализовали стандартную для этой конструкции функциональность. Причем полезную - longjmp "с человеческим лицом"

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ketmar
2010-01-28 15:55 (ссылка)
>Clean тем же ценен
мне, почему-то, сразу вспоминается Self. ассоциативно.

>Почему изврат?
да потому что это всё и есть ни что иное, как извраты. из разряда «и водки выпить, и трезвым быть». коли уж нужно что-то «более продвинутое», так и стоит брать «более другой язык» тогда.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2010-01-28 16:27 (ссылка)
Self это немножко из другой оперы - это техноложество мрачное (как и GHC) - и вполне закономерно закончилось все миграцией этого технолжества в JVM. А O'Caml и Clean выезжают на базовых решениях.

да потому что это всё и есть ни что иное, как извраты

Почему изврат - если уж взялись тащить в язык обыденную вполне конструкцию - так есть смысл тащить ее полностью (ну вот как непонятно зачем в TP процедурные параметры порезали - еще и свой собственный синтаксис выдумали - потом начали изобретать уродство в вроде procedure of object, которые в нормальную семантику указателя на функцию ложатся полностью)

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ketmar
2010-01-28 16:34 (ссылка)
>Self это немножко из другой оперы
да просто ассоциация такая странная. меня там больше аспекты реализации компилятора интересовали. но да — гичество то ещё.

>так есть смысл тащить ее полностью
так полностью не притащили всё равно: first-class functions нет, только страшненький костыль (передаём в нечто типа setCallback() nested-функцию из gcc, выходим из парента, зовём callback, громко смеёмся).

я имел в виду то, что не надо тащить в язык вещи, которые совершенно не «родные». это всё равно, что в Схему тащить while: «if you want PL/I, you know where to get it». или вот изврат «сигнал-слот» в плюхплюах: идея хорошая, но в язык засовывается через анус. про boost я вообще лучше промолчу, это даже не просто пиздец, а пиздец в кубе.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2010-01-28 16:40 (ссылка)
так полностью не притащили всё равно

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

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ketmar
2010-01-28 16:56 (ссылка)
так вот тебе и ответ, почему TP не разрешает: чтобы долбоёбу было сложнее в ногу себе выстрелить.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2010-01-28 17:05 (ссылка)
С точностью до наоборот - выстрелить в ногу нельзя как раз в виртовском паскале (потому что нет процедурных переменных, а только параметры).

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

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ketmar
2010-01-28 17:11 (ссылка)
ну, спорить не буду: давно дело было. да и не знал, не использовал тогда такое.

(Ответить) (Уровень выше)