Главная запись: https://www.cyberforum.ru/blog... g1562.html
Параллелизм данных
Имея объект  , можно параллельно вычислять  и  , поэтому такие угловые скобочки спаривания  можно мыслить как маркер к фразе «функция параллельного вычисления  и  на общем аргументе». В этом прелесть параллелизма данных: в коде программы мы ни слова не пишем о том, что что-то нужно параллелить, а оно само сделается.
Аналогично, функторное произведение ![https://www.cyberforum.ru/cgi-bin/latex.cgi?\left[f,g\right]](https://www.cyberforum.ru/cgi-bin/latex.cgi?%5Cleft%26%2391%3Bf%2Cg%5Cright%26%2393%3B) обозначает функцию, которой не нужно знать целиков весь свой аргумент, чтобы начать вычисляться. Например, пусть  и  — два объекта, которые формируют пару как аргумент для этой функции, причём вычисляется/формирует дольше, чем . Если при этом  вычисляется быстрее, чем  , то имеет смысл начать вычислять как только будет готов. Безусловно, программист может позаботиться об этом самостоятельно и не вводить , а работать и ними в двух разных потоках, но зачем это делать, если компилятор может самостоятельно догадаться, что здесь возможно параллельное вычисление. Таким образом оптимизация произойдёт самостоятельно, а программист будет просто писать так, как ему удобнее.
Теория типов и лямбда-исчисление
Принципиальное отличие типа от множества заключается в том, что множество «знает» о своих элементах, а тип — нет. Тип — это всего лишь маркер, который ставится на объекты для того, чтобы они не попали в «чужой» контекст, чтобы функция не вызвалась на объекте, который не может быть её аргументом. Кроме этого, в ТТ аргументом и значением функции может быть объект любого допустимого типа, в т.ч. другие функции. Так, возможен тип  , описывающий функцию, отображающую функцию  в функцию  . Таким образом функция — это и объект, и значение, и алгоритм, и правило одновременно.
Каррирование
Понимание пары базируется на том, где чаще всего в программировании используется «два объекта» — на двухаргументных функциях. Действительно, тяжело себе представить, каково было бы программирование, если бы нельзя использовать двух и более аргументные функции и конструкторы. Тем не менее есть один способ, позволяющий обойти это ограничение. Называется каррирование и заключается в переходе от функции  к функции  .
| Haskell | 1
2
3
4
| curry :: ((x,y) -> c) -> x -> y -> c
curry f = \x y -> f (x,y)
-- или
curry f x y = f (x,y) |
|
| JavaScript | 1
2
3
4
5
6
7
8
9
10
11
| function curry(f) {
return function(x) {
return function(y) {
return f(x,y);
};
};
}
function add(x,y) { return x+y; }
var inc = curry(add)(1);
inc(2) == 3 // true |
|
Декартовое произведение типов  и  — это некоторый тип  и обратимая функция  . Слово «обратимая» означает, что существует функция  , которая в композиции с curry даёт идентичное отображение. Говоря ТК языком, curry — это изоморфизм в категории типов.
Это определение даёт представление, зачем нужны пары, а именно для того, чтобы переходить от двухаргументных (точнее от каскада) функций к одноаргументной, причём в этом одном аргументе содержится информация сразу про два аргумента. Недостаток также очевиден: определение неконструктивно; не понятно, как построить такой тип и как по двум аргументам построить их пару.
По аналогии с парованием функций в ТК можно потребовать существование функции (точнее, либо семейства функций, либо одну слабо-полиморфную)
В результате мы получим то, что было получено в ТК, только для категории типов. Поэтому следует поискать другое определение.
Прим.: Функция  имеет тип-параметр A, а потому нужно или продублировать fpair для всех типов, вроде fpairInt, fpairDouble, то есть рассматривать fpair как много overloaded функций, либо сказать, что A является типом-аргументом.
Определение в системе с полиморфизмом
Решим эту проблему, дав неэквивалентное второе определение: Понимать это нужно так: пусть есть два объекта и . Всякая двухаргументная (каскадная) функция принимает значение  типа c. Поэтому объекты и порождают функционал  , который и является парой в смысле последнего определения. Мы можем взять функции  и  и передать их в качестве аргумента функционалу. Ожидаемо, мы получим назад и соответственно:  . Поэтому эти две функции порождают проекции, уже известные нам из прошлых разделов. Точнее, проекции задаются так: Несложно убедиться, что curry и uncurry выражаются через две проекции и конструктор:
Этот подход при всей своей красоте оказывается очень требовательным: он требует возможности передавать в качестве аргумента функцию с заранее неизвестным типом. Этот тип  неизвестен до того, как функция  будет применена к функции-аргументу, тип которой известен, а потому тип c определится из аргумента. В определённом смысле это выглядит как generic; нельзя сказать, что c это тип-пустышка, прародитель всех типов, подобно Object в большинстве ЯП. Это скорее параметр функции, его типовый аргумент. Аналогия хорошо усматривается: подобно тому, как в функции  сам (т.н. формальный) аргумент не имеет определённого значения, является подстановочным местом для реального т.н. актуального аргумента, которое определяется во время применения функции к актуальному аргументу, здесь тип c играет ту же роль. Поэтому в некоторых нотациях (характерно для явнотипизированных aka Черчевых систем, неявнотипизированным системам aka типизации Карри это лишнее) типовый абстрактор пишется явно. Сравните:
В первом случае тип  является подстановочным местом для произвольного типа, в то время как тип во втором выражении конкретен. Как уже было упомянуто, в системах с неявной типизацией абстрактор по типу  в самом терме не пишется, указывается только абстракция  в типе терма. Системы, в которых допускается такой вид абстракции — абстрагирование терма от типа, — называются системами с полиморфизмом.
| JavaScript | 1
2
3
4
5
6
7
8
| function pairUncurry(x,y) { return function(g) { return g(x,y); }; }
function pair(x) { return function(y) { return function(g) { return g(x)(y); }; }; }
var projectX = curry(function(x,y) { return x; }); // чтоб понятнее было
var projectY = curry(function(x,y) { return y; }); // написано привычном виде
var p12 = pair(1)(2);
p12(projectX) + p12(projectY) == 3 // true
p12(curry(add)) == 3 // true |
|
Кратко о рассказанном:
1. Два конструктивных определения, ТМ и ТТ.
2. Два неконструктивных, но полезных определения, ТК и ТТ (неполноценное).
3. Спаривание функций, с общим аргументом и с независимыми.
4. Рассуждения об автоматическом распараллеливании.
5. Терминал и элементы, ТК описание типичных функций.
6. Демонстрация на языках JS, Haskell и Java.
|
