Каррирование: для чего и как

У ветеринаров есть термин, схожий по звучанию с термином «каррирование». Схожесть есть не только в звучании, но и отчасти по смыслу: оба предполагают некое отсечение вроде бы как лишнего. Каррирование — это преобразование одной функции от многих аргументов в несколько функций, берущих аргументы по одному. То есть было у функции несколько аргументов, а потом раз! отсекаются лишние и остаётся один. Ветеринарный же термин означает, что отсекается вообще всё.

В языке Хаскелл каррирование применяется не просто часто, а всегда, если у функции больше одного аргумента. Вот, например, функция, которая выдаёт значение типа а, принимая два значения того же типа:

fn_2_1 :: a -> a -> a

fn_3_1 :: a -> a -> a -> a

Как это устроено

Когда задаёшься вопросом, как устроено такое преобразование, то возникают недоумение. Допустим, у нас есть исходная некаррированная функция f и каррированные f0, f1, … fn. Возьмём функцию, получившуюся после такого преобразования, которая должна отработать последней — f0. Она должна выдать тот же результат, что и исходная функция до преобразования — f. Функция f0 принимает лишь один аргумент. Но как она примет результаты от остальных функций f1, … fn, которые получились в результате каррирования? Функция f1 должны вернуть указатель на функцию, которую надо вызвать. Но как f0 возьмёт этот указатель? Ведь у неё единственный аргумент и он занят каким-то входным значением, отнюдь не указателем функции.

Тут что-то не договаривают. Углубление в тему ещё раз показало, что чудес не бывает. Этот указатель сохраняется во внешней нигде не объявленной переменной. Но можно поменять местами указатель и параметр: указатель можно передать как аргумент, а параметр сохранять во внешнюю переменную.

Такая непрозрачность действий, когда важные (потому что без этого работать не будет) механизмы прячутся в неочевидных местах, сбивает с толку и мешает быстро вникнуть в суть происходящего. Во-первых, никто из авторов книг и статей не объясняет устройства, внутренних механизмов того, что отличает Хаскелл от императивных языков. Во-вторых, такое замалчивание создаёт ощущение «бесплатности» этих «особенностей» этого языка. Что отнюдь не так: каррирование имеет свою цену, оно замедляет программы (см. «Измеряем замедление при вызове функций высших порядков»).

Вот пример на C++ из Википедии, который имитирует каррирование:

class curry {
private:
  int m_total;
public:
  curry(int x): m_total(x) {}
  curry& operator() (int y) { m_total += y; return *this; }
  operator int(void) { return m_total; }
};
int a1 = curry(4)(5);		// 9
int a2 = curry(4)(5)(6);	// 15
int a3 = curry(4)(5)(6)(7);	// 22

Для большей ясности и прозрачности напишем собственное каррирование на чистом Си. Тем более, что примера на Си нет в Википедии. Ведь нам интересно, как оно устроено изнутри. В языках, в которых есть так называемые замыкания, каррирование легко реализуемо. Но в Си нет замыканий, зато есть некоторые средства функционального программирования. В Си функции могут как принимать адреса функций и выдавать их в качестве результата. Т.е. функции в Си — это объекты первого класса.

#include   
int	global_var;
typedef  void (*f_1)(int);
typedef  f_1 (*f_2)(int);
typedef  f_2 (*f_3)(int);
typedef  f_3 (*f_4)(int);
typedef  f_4 (*f_5)(int);
// ---------------------------------------------------------------------------
int  f5 (int  a1, int  a2, int  a3, int  a4, int  a5) {
	printf ("function f5 (%i, %i, %i, %i, %i) returns ", a1, a2, a3, a4, a5);
	int  ret = a1*10000 + a2*1000 + a3*100 + a4*10 + a5;
	printf("%i\n", ret); return  ret;
}
// ---------------------------------------------------------------------------
void  F1 (int  a) {
	global_var += a*10000; printf (" (%i) returns %i", a, global_var);
}
f_1  F2 (int  a) {
	global_var += a*1000; printf (" (%i)", a); return  F1;
}
f_2  F3 (int  a) {
	global_var += a*100; printf (" (%i)", a); return  F2;
}
f_3  F4 (int  a) {
	global_var += a*10; printf (" (%i)", a); return  F3;
}
f_4  F5 (int  a) {
	global_var = a; printf ("F5 (%i)", a); return  F4;
}
// ---------------------------------------------------------------------------
main() {
	f5 (5, 4, 3, 2, 1);
	F5 (1) (2) (3) (4) (5);
}

function f5 (5, 4, 3, 2, 1) returns 54321
F5 (1) (2) (3) (4) (5) returns 54321

   ;	int  f5 (int  a1, int  a2, int  a3, int  a4, int  a5) {[/pre]
	push      ebp
	mov       ebp,esp
	push      ebx
	push      esi
	push      edi
	mov       edi,dword ptr [ebp+16]
	mov       esi,dword ptr [ebp+12]
	mov       ebx,dword ptr [ebp+8]
   ;		printf ("function f5 (%i, %i, %i, %i, %i) returns ", a1, a2, a3, a4, a5);
   ;		EBX = a1, ESI = a2, EDI = a3
	push      dword ptr [ebp+24]
	push      dword ptr [ebp+20]
	push      edi
	push      esi
	push      ebx
	push      offset s@
	call      @_printf
   ;		int  ret = a1*10000 + a2*1000 + a3*100 + a4*10 + a5;
	imul      eax,ebx,10000
	imul      edx,esi,1000
	imul      ecx,edi,100
	add       eax,edx
	mov       edx,dword ptr [ebp+20]
	add       edx,edx
	add       eax,ecx
	add       esp,24
	lea       edx,dword ptr [edx+4*edx]
	add       eax,edx
	add       eax,dword ptr [ebp+24]
	mov       ebx,eax
   ;		printf("%i\n", ret); return  ret;
   ; EBX = ret
	push      ebx
	push      offset s@+42
	call      @_printf
	add       esp,8
	mov       eax,ebx
   ;	}
	pop       edi
	pop       esi
	pop       ebx
	pop       ebp
	ret 
   ;	void  F1 (int  a) {
	push      ebp
	mov       ebp,esp
	mov       eax,dword ptr [ebp+8]
   ;		global_var += a*10000; printf (" (%i) returns %i", a, global_var);
   ; EAX = a
	imul      edx,eax,10000
	add       dword ptr [_global_var],edx
	push      dword ptr [_global_var]
	push      eax
	push      offset s@+46
	call      @_printf
	add       esp,12
   ;	}
	pop       ebp
	ret 
   ;	f_1  F2 (int  a) {
	push      ebp
	mov       ebp,esp
	mov       eax,dword ptr [ebp+8]
   ;		global_var += a*1000; printf (" (%i)", a); return  F1;
   ; EAX = a
	imul      edx,eax,1000
	add       dword ptr [_global_var],edx
	push      eax
	push      offset s@+63
	call      @_printf
	add       esp,8
	mov       eax,offset @@F1$qi
   ;	}
	pop       ebp
	ret 
   ;	f_2  F3 (int  a) {
	push      ebp
	mov       ebp,esp
	mov       eax,dword ptr [ebp+8]
   ;		global_var += a*100; printf (" (%i)", a); return  F2;
   ; EAX = a
	imul      edx,eax,100
	add       dword ptr [_global_var],edx
	push      eax
	push      offset s@+69
	call      @_printf
	add       esp,8
	mov       eax,offset @@F2$qi
   ;	}
	pop       ebp
	ret 
   ;	f_3  F4 (int  a) {
	push      ebp
	mov       ebp,esp
	mov       eax,dword ptr [ebp+8]
   ;		global_var += a*10; printf (" (%i)", a); return  F3;
   ; EAX = a
	mov       edx,eax
	push      eax
	add       edx,edx
	push      offset s@+75
	lea       edx,dword ptr [edx+4*edx]
	add       dword ptr [_global_var],edx
	call      @_printf
	add       esp,8
	mov       eax,offset @@F3$qi
   ;	}
	pop       ebp
	ret 
   ;	f_4  F5 (int  a) {
	push      ebp
	mov       ebp,esp
	mov       eax,dword ptr [ebp+8]
   ;		global_var = a; printf ("F5 (%i)", a); return  F4;
   ; EAX = a
	mov       dword ptr [_global_var],eax
	push      eax
	push      offset s@+81
	call      @_printf
	add       esp,8
	mov       eax,offset @@F4$qi
   ;	}
	pop       ebp
	ret 
   ;	main() {
   ;		f5 (5, 4, 3, 2, 1);
	push      1
	push      2
	push      3
	push      4
	push      5
	call      @@f5$qiiiii
	add       esp,20
   ;		F5 (1) (2) (3) (4) (5);
	push      5
	push      4
	push      3
	push      2
	push      1
	call      @@F5$qi
	pop       ecx
	call      eax
	pop       ecx
	call      eax
	pop       ecx
	call      eax
	pop       ecx
	call      eax
	pop       ecx
	xor       eax,eax
   ;	}
	ret

Что мы видим?

• Для накопления результата необходима дополнительная переменная — внешняя по отношению к функциям.
• Вызов одной функции с пятью аргументами заменён вызовами пяти функций с одним аргументом.

Рассмотрим, как вызывается каррированная функция. Видим несколько «call eax». Это в регистре eax содержится адрес функции, которую предстоит вызвать. Можно ли распараллелить эти многочисленные «call»? Чтобы один «call» выполнил один процессор, второй «call» — другой процессор и т. д. Но, в общем случае, пока не выполнится первый «call», второй «call» ещё не знает адреса второй подпрограммы. Поэтому второй «call» ждёт выполнения первого. Поэтому «раскидать» их по разным процессорам не получится. Возможно только последовательное исполнение.

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

В чём выгода

Попробуем поискать выгоды каррирования. Функция, имеющая один аргумент, имеет плоский график.

Функция от двух аргументов более сложная

Чтобы отобразить функцию от трёх аргументов, надо придумывать, как отобразить четвёртую ось. Чаще всего выбирают ось времени. Но как отобразить многомерные функции на графике — это уже головоломка.

Функции с одним аргументом удобны. А вот мнение Д.Шевченко, «О Haskell по-человечески», стр. 50:

В подавляющем большинстве случаев знать вышеизложенную информацию о каррировании функций и о частичном применении не нужно. Главное преимущество такого подхода, при котором одна функция от нескольких аргументов раскладывается на цепочку функций от одного аргумента каждая, лежит в «академической плоскости»: проводить формальные математические доказательства гораздо легче, если договориться, что каждая из вычисляемых функций всегда принимает строго один аргумент и выдаёт строго одно значение.

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

Каррирование делает картину мира во-первых, плоской, а во-вторых выглядящей одинаково для любого масштаба задач. В какой точке ни остановись — везде одинаковая картина: функция имеет единственный аргумент. Если надо решить проблему, зависящую от огромного количества входных параметров, то в теории можно разбить на множество простых функций, зависящих от единственного параметра. Сходные мысли высказываются в статье «Масштабируемые архитектуры программ». В перспективе это способ сделать программирование в «больших» масштабах сделать не сложнее, чем программирование в «малых» масштабах.

Так же можно вспомнить термин Владислава Джавадова «фрактальное программирование». Не встречал расшифровку этого термина, но функции с одним аргументом — весьма подходящий кандидат на фрактальность. Ведь фракталы — это когда картина выглядит одинаково при любом масштабе. Именно это обеспечивает каррирование.

Кривая Коха, пример фрактала

Но, скорее всего, Владислав имел в виду другое. Потому что заявил о «нетехнологичности синтаксиса Хаскелла» из-за каррирования, оно вроде бы несозвучно его идеям и неподходяще для проекта. Так что у «фрактального программирования» теперь есть два конкурирующих толкования :).

Частичное применение

Без каррирования невозможно то, что называют частичным применением. Это своего рода разбитие функции на части: какой-то параметр изымается из списка параметров, а вот функция от оставшихся параметров как раз и будет частичным применением. В принципе, нечто подобное есть в Си-подобных языках — операции инкремента и декремента, у которых есть изъятый параметр — единица. Вот пример частичного применения на Хаскелле:

increment :: (Integer) => a -> a
increment = (+ 1)

increment 99

Нам ничто не мешает написать на Си функцию с усечённым параметром. Но фишка каррирования в том, что частичные применения доступны в языке автоматически. Не надо описывать частично применённые функции, благодаря каррированию они у нас уже есть.

Опубликовано: 2022.05.27, последняя правка: 2022.05.27    10:41

Добавить свой отзыв

Написать автору можно на электронную почту
mail(аt)compiler.su