Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

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

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

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

fn_2_1 :: a -> 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

Что мы видим?

  • Для накопления результата необходима дополнительная переменная — внешняя по отношению к функциям.
  • Вызов одной функции с пятью аргументами заменён вызовами пяти функций с одним аргументом.
С точки математики функции f5 (a, b, c, d, e) и F5 (e) (d) (c) (b) (a) эквивалентны. А вот системному программисту нужны доказательства, что привнесение в жертву эффективности не напрасно и оно обернётся существенными выгодами в другом.

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

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

В чём выгода

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

Функция одного аргумента
Работать с такими функциями удобно. Если у функции два аргумента, то сложность работы с неё возрастает.
Функция двух аргументов
Функция от двух аргументов более сложная

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

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

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

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

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

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

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

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

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

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

increment :: (Integer) => a -> a
increment = (+ 1)
После этого
increment 99
выдаст 100.

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

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

ОценитеОценки посетителей
   ██████████████████████████████████████████ 2 (100%)
   ▌ 0
   ▌ 0
   ▌ 0

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

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

Авторизация

Регистрация

Выслать пароль

Карта сайта


Содержание

Каким должен быть язык программирования?

Анализ и критика

●  Устарел ли текст как форма представления программы

●  Русский язык и программирование

●  Многоязыковое программирование

Синтаксис языков программирования

Синтаксический сахар

●  Некоторые «вкусности» Алгол-68

●  «Двухмерный» синтаксис Python

●  Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

●  Должна ли программа быть удобочитаемой?

●  Стиль языка программирования

●  Тексто-графическое представление программы

●●  Разделители

●●  Строки программы

●●  Слева направо или справа налево?

●  Комментарии

●●  Длинные комментарии

●●  Короткие комментарии

●●  Комментарии автоматической генерации документации

●●  Нерабочий код

●●  Помеченные комментарии

●  Нужны ли беззнаковые целые?

●  Шестнадцатиричные и двоичные константы

●  Условные операторы

●  Переключатель

●  Циклы

●●  Продолжение цикла и выход из него

●  Некошерный «goto»

●  Изменение приоритетов операций

●  Операции присвоения и проверки на равенство. Возможно ли одинаковое обозначение?

●  Так ли нужны операции «&&», «||» и «^^»?

●  Постфиксные инкремент и декремент

●  Почему в PHP для конкатенации строк используется «.»?

●  Указатели и ссылки в C++

●●  О неправомерном доступе к памяти через указатели

●  Обработка ошибок

●  Функциональное программирование

●●  Нечистые действия в чистых функциях

●●  О чистоте и нечистоте функций и языков

●●  Макросы — это чистые функции, исполняемые во время компиляции

●●  Хаскелл, детище британских учёных

●●  Измеряем замедление при вызове функций высших порядков

●●  C vs Haskell: сравнение скорости на простом примере

●●  Уникальность имён функций: за и против

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

●●  О тестах, доказывающих отсутствие ошибок

●  Надёжные программы из ненадёжных компонентов

●●  О многократном резервировании функций

●  Использование памяти

●  Почему динамическое распределение памяти — это плохо

●  Как обеспечить возврат функциями объектов переменной длины?

●●  Типы переменного размера (dynamically sized types, DST) в языке Rust

●●  Массивы переменной длины в C/C++

●●  Размещение объектов в стеке, традиционный подход

●●  Размещение объектов переменной длины с использованием множества стеков

●●  Размещение объектов переменной длины с использованием двух стеков

●●  Реализация двухстековой модели размещения данных

●●  Двухстековая модель: тесты на скорость

●●  Изменение длины объекта в стеке во время исполнения

●●  Размещение объектов переменной длины с использованием одного стека

●  Можно ли забыть о «куче», если объекты переменной длины хранить в стеке

●  Безопасность и размещение объектов переменной длины в стеке

●  Массивы, структуры, типы, классы переменной длины

●  О хранении данных в стеке, вместо заключения

●  Реализация параметрического полиморфизма

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Компьютерный юмор

Новости и прочее




Последние отзывы

2024/03/28 21:36 ••• Ivan
Энтузиасты-разработчики компиляторов и их проекты

2024/03/27 19:12 ••• MihalNik
Постфиксные инкремент и декремент

2024/03/22 20:41 ••• void
Раскрутка компилятора

2024/03/20 19:54 ••• kt
О многократном резервировании функций

2024/03/20 13:13 ••• Неслучайный читатель
Надёжные программы из ненадёжных компонентов

2024/03/10 18:33 ••• Бурановский дедушка
Русской операционной системой должна стать ReactOS

2024/03/07 14:16 ••• Неслучайный читатель
«Двухмерный» синтаксис Python

2024/03/03 16:49 ••• Автор сайта
О неправомерном доступе к памяти через указатели

2024/02/28 18:59 ••• Вежливый Лис
Про лебедей, раков и щук

2024/02/24 18:10 ••• Бурановский дедушка
ЕС ЭВМ — это измена, трусость и обман?

2024/02/22 15:57 ••• Автор сайта
Русский язык и программирование

2024/02/19 17:58 ••• Сорок Сороков
О русском языке в программировании

2024/02/16 16:33 ••• Клихальт
Избранные компьютерные анекдоты