| |||
|
|
"И назову ее лямбда..." X-Posted: http://kouzdra.livejournal.com/327847.h X-Posted: http://lj.rossia.org/users/kouzdra/8138 X-Posted: http://community.livejournal.com/ru_dec Прочитал тут в треде диалог про лямбды: 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: И все-таки я был неправ - тайну "счетчика параметров" я не раскрыл, а она тут существенна: придется дописывать. Ждите. Так вот - 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 делает не так. У него есть набор "функций переходников": которые и используются в таких случаях. И вот им-то как раз в некоторых случаях и нужно знать число аргументов. Но вот это уже точно отдельным постом. А то и так многа букав. К тому же - я задумался над вопросом, о том почему там такие сложности. Хотя обращу внимание - загадка тайны брюквы пока не так и не раскрыта. |
||||||||||||||||||||||||