r6 - 31 May 2004 - 00:05:25 - Yuri KlimovYou are here: TWiki >  XSG Web > WhatIsCoarity

Что такой коарность?

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

//C/C++ 
int add(int x, int y) 
{ 
    return x+y; 
}

--Haskel
add :: Int->Int->Int
add = (+)

В языке XSG помимо этого каждая функция может иметь нетривиальную коарность то есть количество возвращаемых значений XSG функции может отличаться от единицы. Чтобы воспользоваться этим значениями нужно использовать let ... in конструкцию, например:

Swap x y = y x -- XSG функция с арностью и коарностью 2
F x y z = 
    let 
        x' y' = Swap x y   -- Вызываем 2-коарную функцию Swap
    in Cons z (Cons y' x') -- Используем результаты ее вычисления

Внимание: Коарность не имеет никакого отношения к недетерминизму!

-- Andrei Mishchenko - 24 Mar 2004

Вполне можно писать и так:

F x y z = Cons z Cons Swap x y
Т.к. все функции и конструкторы имеют заданную арность и коарность и записываются в префиксной форме, то скобки не обязательны. wink

-- Yuri Klimov - 24 Mar 2004

Ну, это все правильно (кстати, до тех пор, пока нет функций высших порядков; вроде даже типизация не спасет). Но я имею ввиду, что в языках без коарности конструкция let ... in нужна в основном для того, чтобы воспользоваться результатом некоторого вызова более одного раза, скажем.

f x = let y = g x in h y y 
А в XSG конструкции let ... in зачастую нельзя избежать даже если каждым из результатов многокоарной функции надо воспользоваться лишь в одном месте. Вот пример получше.
Swap x y = y x -- XSG функция с арностью и коарностью 2
F x y z = 
    let 
        x' y' = Swap x y   -- Вызываем 2-коарную функцию Swap
    in Cons x' Cons z y' -- Используем результаты ее вычисления

-- Andrei Mishchenko - 31 Mar 2004


Дуальность арности и коарности в языках высшего порядка

Позвольте обратить внимание на причину, по которой в области частичных вычислений для функциональных языков высшего порядка коарности "не уделяется достаточного внимания":

Коарность переходит в арность при переводе программы в Continuation Passing Style (CPS).

Это значит, что результаты полученные для языков высшего порядка с арностью, механически переносятся на языки с коарностью, что и наблюдается в статьях. Тем самым, по принципу Бритвы Оккама в языках высшего порядка отдельно коарностью заниматься не нужно. (Речь идет о теоретических работах, конечно; на практике минимизация понятий не всегда облегчает жизнь).

Вспомним идею CPS: если обычная функция f выдает результат "наружу", то соответствующая ей CPS-ная f' вызывает переданную в качестве дополнительного аргумента функцию, называемую продолжением, continuation. При этом вызову композиции g(f x) соответствует вызов (f' x g), где g -- продолжение. Если g в свою очередь переведена в CPS, то вызову h(g(f x)) соответствует f' x (g' h), и т.д.Текст определений функций перекодируется в CPS вполне механически: обычное f:

f аргументы = значение

превращается в CPS-ное f':

f аргументы c = c (значение)

Если же в правой части на верхней уровне стоит вызов CPS-ной функции h'( ...), то так:

f аргументы c = h' (...) c

Аппликацию аргумента-продолжения "пропихивают" в глубину всех конструкций, для которых это возможно -- if, case, let и т.д., имея целью не увеличить глубину стека при вычислении, а уменьшить.

Заметим, что часть функций в программе может быть переведена в CPS, а часть остаться обычными.

Итак, в композиции g(f x) арности g соответствует коарность f, без которой арностью g не воспользуешься. То есть, в функциональных языках первого порядка, сказав "арность" нужно тут же вводить коарность, иначе невозможно записать композицию. Это мы и наблюдали в истории Рефалов: до Рефала-Плюс и арность, и коарность были единичными. А в Рефале-Плюс они появились одновременно. Все логично. Обратите внимание, что метавычисления здесь еще не при чем: работает первичная логика языка (если язык логичен, конечно:-).

В типизированных функциональных языках арность и коарность замаскировали по n-ки (tuples), и стало казаться, что коарности "не уделяется достаточно внимания". Но зжесь хотя бы арность и коарность обработаны одинаково. Однако, в языках высшего порядка есть еще арность закарринных функций. Ее так просто не замаскируешь. Тем не менее, вводить для нее коарность (в теоретических исследованиях) нет смысла, так как через CPS она сводится к арности. Например, пусть мы хотим записать композицию g(f x), но g имеет 2 закарриных аргумента, то есть ее надо вызывать как (g y z). Вопрос: как закодировать f, чтобы она выдавала 2 аргумента по отдельности и они сразу попадали в соответствующие аргументы g, тем самым f фактически имела коарность 2? Без CPS мы можем закодировать коарность через tuple и let:

let (y, z) = f x in g y z

Сложновато в том смысле, что надо поддерживать эквивалентность tuples и коарности. (Хотя, заметим, в практических языках это всех устраивает: зачем плодить еще одно понятие для пользователя, когда можно протащить его через tuples? Пусть теоретики и реализаторы "мучаются".;-).

А если перевести определение f c CPS, то все выглядит естественно: вызываем (f' x g), а определение вместо обычного:

f аргументы = хотим выдать 2 значения, заданных выражениями A и B

в CPS пишем так:

f' аргументы c = с A B

Кстати, вот еще один философский вопрос: что "первичнее" -- понятие пары или (ко)арности?. (:-) Если идти от лямбда-исчисления, то арность "первичнее". Если же от аксиом теории множеств Цермело-Френкеля, то заметим, что аксиому пары принято писать раньше аксиом, связанных с функциями.

-- Andrei Klimov - 29 May 2004


Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r6 < r5 < r4 < r3 < r2 | More topic actions
 
Powered by TWiki

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback