авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 11 |

«Учебник по Haskell Антон Холомьёв Книга зарегистрирована под лицензией Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Generic license (CC BY-NC-ND 3.0), 2012 год. Вы можете ...»

-- [ Страница 6 ] --

mul = FUN( a let succ = THUNK (add a) in foldNat one succ ) Для того, чтобы вычислить THUNK(add a) нам необходимо знать значение a, это значение определено в те ле функции. Оно определяется из контекста. По отношению к объекту такую переменную называют свободной (free). В куче мы будем хранить не только выражение (add a), но и ссылки на все свободные переменные, ко торые участвуют в выражении объекта. Эти ссылки называют довесок (payload). Объект кучи содержит ссылку на специальную таблицу и довесок. В таблице находятся информация о типе объекта и код, который необ ходимо вычислить, а также другая служебная информация. При вычислении объекта мы заменяем ссылки настоящими значениями или ссылками на конструкторы.

Объект кучи может быть:

• FUN – определением функции;

• PAP – частичным применением;

• CON – полностью применённым конструктором;

• THUNK – отложенным вычислением;

• BLACKHOLE – это значение используется во время вычисления THUNK. Этот трюк предотвращает появле ние утечек памяти.

Мы будем считать, что куча – это таблица, которая ставит в соответствие адресам объекты или вычис ленные значения.

158 | Глава 10: Реализация Haskell в GHC Стек Стек служит для быстрого переключения контекста. Мы будем пользоваться стеком при вычислении case выражений и THUNK-объектов. При вычислении case-выражения мы сохраняем в стеке альтернативы и место возврата значения, а сами начинаем вычислять аргумент case-выражения. При вычислении THUNK-объекта мы запомним в стеке, адрес с которым необходимо связать полученное значение.

При вычислении в стратегии вставка-вход мы будем сохранять в стеке аргументы функции. А при вычис лении в стратегии вычисление-применение мы также будем сохранять аргументы функции в стеке. Какая разница между этими вариантами? В первой стратегии мы можем доставать из стека произвольное число аргументов, после определения арности функции мы добираем столько, сколько нам нужно, поэтому мы будем хранить аргументы по одному. Во второй же стратегии нам нужно просто сохранить все оставшиеся аргументы. Мы сохраняем и извлекаем их все сразу. Упрощая, объекты стека можно представить так:

::= case • of {alt1 ;

... altn } контекст case-выражения k Обновить отложенное вычисление | U pd t • Применить функцию к аргументам, только для | (• a1...an ) стратегии вычисление-применение Аргумент на потом, только для | Arg a стратегии вставка-вход Рис. 10.3: Синтаксис STG Правила общие для обеих стратегий вычисления Состояние вычислителя состоит из трёх частей. Это выражение для вычисления e, стек s и куча H. Мы рассмотрим правила по которым вычислитель переходит из одного состояния в другое. Все они имеют вид:

e1 ;

s1 ;

H1 e2 ;

s2 ;

H Левая часть переходит в правую, при условии, что левая часть имеет определённый вид. Начнём с правил, которые одинаковы и в той и в другой стратегии вычисления. Для простоты пока мы будем полагать, что объекты только добавляются в кучу и никогда не стираются. Мы будем обозначать добавление в стек как добавление элемента в обычный список: elem : s.

Рассмотрим правило для let-выражений:

e[x /x];

H[x obj], x – новое имя x obj e;

s;

H s;

let = in Рис. 10.4: Синтаксис STG В этом правиле мы добавляем в кучу новый объект obj под именем (или по адресу) x. Запись e[x /x] означает замену x на x в выражении e.

Теперь разберёмся с правилами для case-выражений.

v of {... ;

C x1... xn e;

... };

e[a1 /x1... an /xn ];

s;

H case H[v CON (C a1... an )] s;

v of {... ;

x e};

s;

H e[v/x];

s;

H case Если v – литерал или H[v] – значение, которое не подходит ни по одной из альтернатив e of {... };

• {... } : s;

s;

H e;

H case case of • {... } : s;

v of {... };

v;

H s;

H case of case Рис. 10.5: Синтаксис STG Вычисления начинаются с третьего правила, в котором нам встречается case-выражения с произвольным e. В этом правиле мы сохраняем в стеке альтернативы и адрес возвращаемого значения и продолжаем вы числение выражения e. После вычисления мы перейдём к четвёртому правилу, тогда мы снимем со стека Вычисление STG | информацию необходимую для продолжения вычисления case-выражения. Это приведёт нас к одному из первых двух правил. В первом правиле значение аргумента содержит конструктор, подходящий по одной из альтернатив, а во втором мы выбираем альтернативу по умолчанию.

Теперь посмотрим как вычисляются THUNK-объекты.

H[x T HU N K e] U pd x • : s;

H[x BLACKHOLE] x;

s;

e;

U pd x • : s;

H[x H[y]] y;

H y;

s;

если H[y] является значением Рис. 10.6: Синтаксис STG Если переменная указывает на отложенное вычисление e, мы сохраняем в стеке адрес по которому необходимо обновить значение и вычисляем значение e. В это время мы записываем в по адресу x объ ект BLACKHOLE. У нас нет такого правила, которое реагирует на левую часть, если в ней содержится объект BLACKHOLE. Поэтому во время вычисления T HU N K ни одно из правил сработать не может.

Этот трюк необходим для избежания утечек памяти. Как только выражение будет вычислено, мы извлечём из стека адрес x и обновим значение.

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

H[y F U N (x1... xn e)] e[a1 /x1... an /xn ];

s;

H f n a1... an ;

s;

a1... an ;

a;

s;

H s;

H a – результат вычисления ( a1... an ) Рис. 10.7: Синтаксис STG Мы просто заменяем все вхождения аргументов на значения. Второе правило выполняет применение примитивной функции к значениям.

Правила для стратегии вставка-вход Arg a1 : … : Arg am : s;

f k a1... a m ;

s;

H f;

H Arg a1 : … : Arg an : s;

H[f F U N (x1... xn e)] f;

e[a1 /x1... an /xn ];

s;

H Arg a1 : … : Arg am : s;

H[f F U N (x1... xn e)] f;

p;

s;

H[p P AP (f a1... am )] при m 1;

m n;

верхний элемент s не является Arg;

p – новый адрес H[f P AP (g a1... an )] f;

Arg an+1 : s;

g;

Arg a1 : … : Arg an : Arg an+1 : s;

H Рис. 10.8: Синтаксис STG Первое правило выполняет этап “вставка”. Если мы видим применение функции, мы первым делом со храняем все аргументы в стеке. Во втором правиле мы вычислили значение f, оно оказалось функцией с арностью n. Тогда мы добираем из стека n аргументов и подставляем их в правую часть функции e. Если в стеке оказалось слишком мало аргументов, то мы переходим к третьему правилу и составляем частичное применение. Последнее правило говорит о том как расшифровывается частичное применение. Мы вставляем в стек все аргументы и начинаем вычисление функции g из тела P AP.

160 | Глава 10: Реализация Haskell в GHC f • a1... a n ;

H[f F U N (x1... xn e)] s;

e[a1 /x1... an /xn ];

s;

H H[f F U N (x1... xn e)] f k a1... a m ;

s;

e[a1 /x1... an /xn ];

(• an+1... am ) : s;

H при m n p;

s;

H[p P AP (f a1... am )] при m n, p – новый адрес f • a1... a m ;

H[f T HU N K e] s;

f ;

(• a1... am ) : s;

H H[f P AP (g a1... an )] f k an+1... am ;

s;

g • a1... an an+1... am ;

s;

H f • a1... an ;

s;

H f;

(• a1... an ) : s;

H H[f ] является F U N или P AP Рис. 10.9: Синтаксис STG Правила для стратегии вычисление-применение Разберёмся с первыми двумя правилами. В первом правиле статическая арность f неизвестна, но зна чение f уже вычислено, и мы можем узнать арность по объекту F U N, далее возможны три случая. Число аргументов переданных в функцию совпадает с арностью F U N, тогда мы применяем аргументы к правой части F U N. Если в функцию передано больше аргументов чем нужно, мы сохраняем лишние на стеке. Если же аргументов меньше, то мы создаём объект P AP. Третье правило говорит о том, что нам делать, если зна чение f ещё не вычислено. Оно является T HU N K. Тогда мы сохраним аргументы на стеке и вычислим его.

В следующем правиле мы раскрываем частичное применение. Мы просто организуем вызов функции со все ми аргументами (и со стека и из частичного применения). Последнее правило срабатывает после третьего.

Когда мы вычислим T HU N K и увидим там F U N или P AP. Тогда мы составляем применение функции.

Сложность применения стратегии вставка-вход связана с плохо предсказуемым изменением стека. Если в стратегии вычисление-выполнение мы добавляем и снимаем все аргументы, то в стратегии вставка-вход мы добавляем их по одному и неизвестно сколько снимем в следующий раз. Кроме того стратегия вычисление применение позволяет проводить оптимизацию перемещения аргументов. Вместо стека мы можем хранить аргументы в регистрах. Тогда скорость обращения к аргументам резко возрастёт.

10.4 Представление значений в памяти. Оценка занимаемой памяти Ранее мы говорили, что полностью вычисленное значение – это дерево, в узлах которого находятся одни лишь конструкторы. Процесс вычисления похож на очистку дерева выражения от синонимов. Мы начинаем с самого верха и идём к листьям. Потом мы выяснили, что для предотвращения дублирования вычислений мы подставляем в функции не сами значения, а ссылки на значения. Теперь нам понятно, что ссылки указывают на объекты в куче. Ссылки – это атомарные переменные. Полностью вычисленное значение является сетью (или графом) объектов кучи типа CON.

Поговорим о том сколько места в памяти занимает то или иное значение. Как мы говорили память ком пьютера состоит из ячеек, в которых хранятся значения. У каждой ячейки есть адрес. Ячейки памяти неде лимы, их также принято называть словами. Мы будем оценивать размер значения в словах.

Каждый конструктор требует столько слов сколько у него полей плюс ещё одно слово для ссылки на служебную информацию (она нужна вычислителю). Посмотрим на примеры:

data Int = I# Int# -- 2 слова data Pair a b = Pair a b -- 3 слова У этого правила есть исключение. Если у конструктора нет полей, то есть он является константой или примитивным конструктором, то в процессе вычисления значение этого конструктора представлено ссылкой.

Это означает, что внутри программы все значения ссылаются на одну область памяти. У нас действительно есть лишь один пустой список или одно значение True или False.

Посчитаем число слов в значении [Pair 1 2]. Для этого для начала перепишем его в STG nil = [] -- глобальный объект (не в счёт) Представление значений в памяти. Оценка занимаемой памяти | let x1 = I# 1 -- 2 слова x2 = I# 2 -- 2 слова p = Pair x1 x2 -- 3 слова val = Cons p nil -- 3 слова in val ----------- -- 10 слов Поскольку объект кучи CON может хранить только ссылки, нам пришлось введением дополнительных переменных “развернуть” значение. Примитивный конструктор не считается, поскольку он сохранён гло бально, в итоге получилось 10 слов. Посмотрим на ещё один пример, распишем значение [Just True, Just True, Nothing]:

nil = [] true = True nothing = Nothing let x1 = Just true -- 2 слова x2 = Just true -- 2 слова p1 = Cons nothing nil -- 3 слова p2 = Cons x2 p1 -- 3 слова p3 = Cons x1 p2 -- 3 слова in p3 --------- -- 13 слов Обычно одно слово соответствует 16, 32 или 64 битам. Эта цифра зависит от процессора. Мы считали, что любое значение можно поместить в одно слово, но это не так. Возьмём к примеру действительные чис ла с двойной точностью, они не поместятся в одно слово. Это необходимо учитывать при оценке объёма занимаемой памяти.

10.5 Управление памятью. Сборщик мусора В прошлом разделе для простоты мы считали, что объекты только добавляются в кучу. На самом деле это не так. Допустим во время вычисления функции нам нужно было вычислить какие-то промежуточные дан ные, например объявленные в локальных переменных, тогда после вычисления результата все эти значения больше не нужны. При этом в куче висит много-много объектов, которые уже не нужны. Нам нужно как-то от них избавится. Этой задачей занимается отдельный блок вычислителя, который называется сборщиком му сора (garbage collector), соответственно процесс автоматического освобождения памяти называется сборкой мусора (garbage collection или GC).

На данный момент в GHC используется копирующий последовательный сборщик мусора, который рабо тает по алгоритму Чейни (Cheney). Для начала рассмотрим простой алгоритм сборки мусора. Мы выделяем небольшой объём памяти и начинаем наполнять его объектами. Как только место кончится мы найдём все “живые” объекты, а остальное пространство памяти будем считать свободным. Как только после очередной очистки оказалось, что нам всё же не хватает места. Мы найдём все живые объекты, подсчитаем сколько ме ста они занимают и запросим у системы этот объём памяти. Скопируем все живые объекты на новое место, а старую память будем считать свободной. Так например, если у нас было выделено 30 Мб памяти и оказалось, что живые объекты занимают 10 Мб, мы выделим ещё 10 Мб, скопируем туда все живые объекты и общий объём памяти станет равным 40 Мб.

Мы можем оптимизировать сборку мусора. Есть такая гипотеза, что большинство объектов имеют очень короткую жизнь. Это промежуточные данные, локальные переменные. Нам нужен лишь результат функции, но на подходе к результату мы сгенерируем много разовой информации. Ускорить очистку можно так. Мы выделим совсем небольшой участок памяти внутри нашей кучи, его принято называть яслями (nursery area), и будем выделять и собирать новые объекты только в нём, как только этот участок заполнится мы скопируем все живые объекты из яслей в остальную память и снова будем наполнять ясли. Как только вся память закон чится мы поступим так же как и в предыдущем сценарии. Когда заканчивается место в яслях, мы проводим поверхностную очистку (minor GC), а когда заканчивается вся память в текущей куче, мы проводим глубокую очистку (major GC). Эта схема соответствует сборке с двумя поколениями.

10.6 Статистика выполнения программы Процесс управления памятью скрыт от программиста. Но при этом в GHC есть развитые средства косвен ной диагностики работы программы. Пока мы пользовались самым простым способом проверки. Мы вклю чали флаг s в интерпретаторе. Пришло время познакомиться и с другими.

162 | Глава 10: Реализация Haskell в GHC Статистика вычислителя Для начала научимся смотреть статистику работы вычислителя. Посмотреть статистику можно с помо щью флагов s[file] и S[file]. Эти флаги предназначены для вычислителя низкого уровня (realtime system или RTS, далее просто вычислитель), они заключаются в окружение +RTS... -RTS, если флаги идут в кон це строки и считается, что все последующие флаги предназначены для RTS мы можем просто написать ghc –make file.hs +RTS... Например скомпилируем такую программу:

module Main where main = print $ sum [1.. 1e5] Теперь скомпилируем:

$ ghc --make sum.hs -rtsopts -fforce-recomp Флаг rtsopts позволяет передавать скомпилированной программе флаги для вычислителя низкого уров ня, далее для краткости мы будем называть его просто вычислителем. С флагом fforce-recomp программа будет каждый раз заново пересобираться. Теперь посмотрим на статистику выполнения программы (флаг s[file], в этом примере мы перенаправляем выход в поток stderr):

$./sum +RTS -sstderr 5.00005e 14,145,284 bytes allocated in the heap 11,110,432 bytes copied during GC 2,865,704 bytes maximum residency (3 sample(s)) 460,248 bytes maximum slop 7 MB total memory in use (0 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 21 colls, 0 par 0.00s 0.01s 0.0006s 0.0036s Gen 1 3 colls, 0 par 0.01s 0.01s 0.0026s 0.0051s INIT time 0.00s ( 0.00s elapsed) MUT time 0.01s ( 0.01s elapsed) GC time 0.01s ( 0.02s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 0.02s ( 0.03s elapsed) %GC time 60.0% (69.5% elapsed) Alloc rate 1,767,939,507 bytes per MUT second Productivity 40.0% of total user, 26.0% of total elapsed Был распечатан результат и отчёт о работе программы. Разберёмся с показателями:

bytes allocated in the heap -- число байтов выделенных в куче -- за всё время работы программы bytes copied during GC -- число скопированных байтов -- за всё время работы программы bytes maximum residency -- в каком объёме памяти работала программа -- в скобках указано число глубоких очисток bytes maximum slop -- максимум потерь памяти из-за фрагментации total memory in use -- сколько всего памяти было запрошено у ОС Показатель bytes maximum residency измеряется только при глубокой очистке, поскольку новая память выделяется именно в этот момент. Размер памяти выделенной в куче гораздо больше общего объёма памяти.

Так происходит потому, что этот показатель указывает на общее число памяти в куче за всё время работы программы. Ведь мы переиспользуем не нужную нам память. По этому показателю можно судить о том, сколько замыканий (объектов) было выделено в куче.

Следующие две строчки говорят о числе сборок мусора. Мы видим, что GC выполнил 21 поверхностную очистку (поколение 0) и 3 глубоких (поколение 1). Дальше идут показатели скорости. INIT и EXIT – это Статистика выполнения программы | инициализация и завершение программы. MUT – это полезная нагрузка, время, которая наша программа тра тила на изменение (MUTation) значений. GC – время сборки мусора. Далее GHC сообщил нам о том, что мы провели 60% времени в сборке мусора. Это очень плохо. Продуктивность программы очень низкая. Затратна глубокая сборка мусора, поверхностная – это дело обычное. Теперь посмотрим на показатели строгой версии этой программы:

module Main where import Data.List(foldl’) sum’ = foldl’ (+) main = print $ sum’ [1.. 1e5] Скомпилируем:

$ ghc --make sumStrict.hs -rtsopts -fforce-recomp Посмотрим на статистику:

$./sumStrict +RTS -sstderr 5.00005e 10,474,128 bytes allocated in the heap 24,324 bytes copied during GC 27,072 bytes maximum residency (1 sample(s)) 27,388 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 19 colls, 0 par 0.00s 0.00s 0.0000s 0.0000s Gen 1 1 colls, 0 par 0.00s 0.00s 0.0001s 0.0001s INIT time 0.00s ( 0.00s elapsed) MUT time 0.01s ( 0.01s elapsed) GC time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 0.01s ( 0.01s elapsed) %GC time 0.0% (3.0% elapsed) Alloc rate 1,309,266,000 bytes per MUT second Productivity 100.0% of total user, 116.0% of total elapsed Мы видим, что произошла лишь одна глубокая сборка. И это существенно сказалось на продуктивности.

Кромке того мы видим, что программа заняла лишь 27 Кб памяти, вместо 2 Мб как в прошлом случае. Теперь давайте покрутим ручки у GC. В GHC можно устанавливать разные параметры сборки мусора с помощью флагов. Все флаги можно посмотреть в документации GHC. Мы обратим внимание на несколько флагов.

Флаг H назначает минимальное значение для стартового объёма кучи. Флаг A назначает объём памяти для яслей. По умолчанию размер яслей равен 512 Кб (эта цифра может измениться). Изменением этих параметров мы можем отдалить сборку мусора. Чем дольше работает программа между сборками, тем выше вероятность того, что многие объекты уже не нужны.

Давайте убедимся в том, что поверхностные очистки происходят очень быстро и совсем не тормозят программу. Установим размер яслей на 32 Кб вместо 512 Кб как по умолчанию (размер пишется сразу за флагом, за цифрой идёт k или m):

$./sumStrict +RTS -A32k -sstderr...

Tot time (elapsed) Avg pause Max pause Gen 0 318 colls, 0 par 0.00s 0.00s 0.0000s 0.0000s Gen 1 1 colls, 0 par 0.00s 0.00s 0.0001s 0.0001s...

MUT time 0.01s ( 0.01s elapsed) GC time 0.00s ( 0.00s elapsed)...

%GC time 0.0% (11.8% elapsed) 164 | Глава 10: Реализация Haskell в GHC Мы видим, что за счёт уменьшения памяти очистки существенно участились, но это не сказалось на об щем результате. С помощью флага H[size] мы можем устанавливать рекомендуемое минимальное значение для размера кучи. Оно точно не будет меньше. Вернёмся к первому варианту и выделим алгоритму побольше памяти, например 20 Мб:

./sum +RTS -A1m -H20m -sstderr 5.00005e 14,145,284 bytes allocated in the heap 319,716 bytes copied during GC 324,136 bytes maximum residency (1 sample(s)) 60,888 bytes maximum slop 22 MB total memory in use (1 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 2 colls, 0 par 0.00s 0.00s 0.0001s 0.0001s Gen 1 1 colls, 0 par 0.00s 0.00s 0.0007s 0.0007s INIT time 0.00s ( 0.00s elapsed) MUT time 0.02s ( 0.02s elapsed) GC time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 0.02s ( 0.02s elapsed) %GC time 0.0% (4.4% elapsed) Alloc rate 884,024,998 bytes per MUT second Productivity 100.0% of total user, 78.6% of total elapsed Произошла лишь одна глубокая очистка (похоже, что эта очистка соответствует начальному выделению памяти) и продуктивность программы стала стопроцентной. С помощью флага S вместо s мы можем по смотреть более детальную картину управления памяти. Будут распечатаны показатели памяти для каждой очистки.

./sum +RTS -Sfile В файле file мы найдём такую таблицу:

память время выделено скопировано в живых GC Total Тип очистки Alloc Copied Live GC GC TOT TOT Page Flts bytes bytes bytes user elap user elap 545028 150088 174632 0.00 0.00 0.00 0.00 0 0 (Gen: 1) 523264 298956 324136 0.00 0.00 0.00 0.00 0 0 (Gen: 0)...

Итак у нас появился один существенный показатель качества программ. Это количество глубоких очи сток. Во время глубокой очистки вычислитель производит две затратные операции: сканирование всей кучи и запрос у системы возможно большого блока памяти. Чем меньше таких очисток, тем лучше. Сократить их число можно удачной комбинацией показателей A и H. Но не стоит сразу начинать обновлять параметры по умолчанию, если ваша программа работает слишком медленно. Лучше сначала попробовать изменить ал горитм. Найти функцию, которая слишком много ленится и ограничить её с помощью seq или энергичных образцов. В этом примере у нас была всего одна функция, поэтому поиск не составил труда. Но что если их уже очень много? Скорее всего так и будет. Не стоит оптимизировать не рабочую программу. А в рабочей программе обычно много функций. Но это не так страшно, помимо суммарных показателей GHC позволяет собирать более конкретную статистику.

Стоит отметить функцию performGC из модуля System.Mem, она форсирует поверхностную сборку мусора.

Допустим вы читаете какие-то данные из файла и тут же преобразуете их в структуру данных. После того как чтение данных закончится, вы знаете, что промежуточные данные, связанные с чтением, вам уже не нужны.

Выполнив performGC вы можете подсказать об этом вычислителю.

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

Статистика выполнения программы | module Main where concatR = foldr (++) [] concatL = foldl (++) [] fun :: Double fun = test concatL - test concatR where test f = last $ f $ map return [1.. 1e6] main = print fun У нас есть подозрение, что какая-то из двух функций concatX работает слишком медленно. Мы можем посмотреть какая, если добавим к ним специальную прагму SCC:

concatR = {-# SCC ”right” #-} foldr (++) [] concatL = {-# SCC ”left” #-} foldl (++) [] Напомню, что прагмой называется специальный блочный комментарий с решёткой. Это специальное со общение компилятору. Прагмой SCC мы устанавливаем так называемый центр затрат (cost center). Она пи шется сразу за знаком равно. В кавычках пишется имя, под которым статистика войдёт в итоговый отчёт.

После этого вычислитель будет следить за нагрузкой, которая приходится на эту функцию. Теперь нам нуж но скомпилировать модуль с флагом prof, который активирует подсчёт статистики в центрах затрат:

$ ghc --make concat.hs -rtsopts -prof -fforce-recomp $./concat +RTS -p Второй командой мы запускаем программу и передаём вычислителю флаг p. После этого будет создан файл concat.prof. Откроем этот файл:

concat +RTS -p -RTS total time = 1.45 secs (1454 ticks @ 1000 us, 1 processor) total alloc = 1,403,506,324 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc left Main 99.8 99. individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 46 0 0.0 0.0 100.0 100. CAF GHC.Integer.Logarithms.Internals 91 0 0.0 0.0 0.0 0. CAF GHC.IO.Encoding.Iconv 71 0 0.0 0.0 0.0 0. CAF GHC.IO.Encoding 70 0 0.0 0.0 0.0 0. CAF GHC.IO.Handle.FD 57 0 0.0 0.0 0.0 0. CAF GHC.Conc.Signal 56 0 0.0 0.0 0.0 0. CAF Main 53 0 0.2 0.2 100.0 100. right Main 93 1 0.0 0.0 0.0 0. left Main 92 1 99.8 99.8 99.8 99. Мы видим, что почти всё время работы программа провела в функции concatL. Функция concatR была вычислена мгновенно (time) и почти не потребовала ресусов памяти (alloc). У нас есть две пары колонок ре зультатов. individual указывает на время вычисления функции, а inherited – на время вычисления функции и всех дочерних функций. Колонка entries указывает число вызовов функции. Если мы хотим проверить все функции мы можем не указывать функции прагмами. Для этого при компиляции указывается флаг auto-all.

Отметим также, что все константы определённый на самом верхнем уровне модуля, сливаются в один центр.

Они называются в отчёте как CAF. Для того чтобы вычислитель следил за каждой константой по отдельности необходимо указать флаг caf-all. Попробуем на таком модуле:

module Main where fun1 = test concatL - test concatR fun2 = test concatL + test concatR 166 | Глава 10: Реализация Haskell в GHC test f = last $ f $ map return [1.. 1e4] concatR = foldr (++) [] concatL = foldl (++) [] main = print fun1 print fun Скомпилируем:

$ ghc --make concat2.hs -rtsopts -prof -auto-all -caf-all -fforce-recomp $./concat2 +RTS -p 0. 20000. После этого можно открыть файл concat2.prof и посмотреть итоговую статистику по всем значениям.

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

Динамика изменения объёма кучи В предыдущем разделе мы смотрели общее время и память затраченные на вычисление функции. В этом мы научимся измерять динамику изменения расхода памяти на куче. По этому показателю можно понять в какой момент в программе возникают утечки памяти. Мы увидим характерные горбы на картинках, ко гда GC будет активно запрашивать новую память. Для этого сначала нужно скомпилировать программу с флагом prof как и в предыдущем разделе, а при выполнении программы добавить один из флагов hc, hm, hd, hy или hr. Все они начинаются с буквы h, от слова heap (куча). Вторая буква указывает тип графика, какими показателями мы интересуемся. Все они создают специальный файл имяПриложения.hp, который мы можем преобразовать в график в формате PostScript с помощью программы hp2ps, она устанавливается автоматически вместе с GHC.

Рассмотрим типичную утечку памяти (из упражнения к предыдущей главе):

module Main where import System.Environment(getArgs) main = print. sum2. xs. read = fmap head getArgs where xs n = [1.. 10 ^ n] sum2 :: [Int] - (Int, Int) sum2 = iter (0, 0) where iter c [] =c iter c (x:xs) = iter (tick x c) xs tick :: Int - (Int, Int) - (Int, Int) tick x (c0, c1) | even x = (c0, c1 + 1) | otherwise = (c0 + 1, c1) Скомпилируем с флагом профилирования:

$ ghc --make leak.hs -rtsopts -prof -auto-all Статистика вычислителя показывает, что эта программа вызывала глубокую очистку 8 раз и выполняла полезную работу лишь 40% времени.

$./leak 6 +RTS -K30m -sstderr...

Tot time (elapsed) Avg pause Max pause Gen 0 493 colls, 0 par 0.26s 0.26s 0.0005s 0.0389s Gen 1 8 colls, 0 par 0.14s 0.20s 0.0248s 0.0836s...

Productivity 40.5% of total user, 35.6% of total elapsed Теперь посмотрим на профиль кучи.

Статистика выполнения программы | $./leak 6 +RTS -K30m -hc (500000,500000) $ hp2ps -e80mm -c leak.hp В первой команде мы добавили флаг hc для того, чтобы создать файл с расширением.hp. Он содержит таблицу с показателями размера кучи, которые вычислитель замеряет через равные промежутки времени. Мы можем изменять интервал с помощью флага iN, где N – время в секундах. Второй командой мы преобразуем профиль в картинку. Флаг c, говорит о том, что мы хотим получить цветную картинку, а флаг e80mm, говорит о том, что мы собираемся вставить картинку в текст LaTeX. После e указан размер в миллиметрах. Мы видим характерный горб (рис. 10.10).

leak 6 +RTS -K30m -hc 3,008,476 bytes x seconds Fri Jun 1 21:17 bytes 14M 12M (103)tick/sum2.iter/sum2/m...

10M 8M (102)main.xs/main/Main.CAF 6M 4M (101)sum2.iter/sum2/main/M...

2M 0M 0.0 0.1 0.1 0.2 0.2 0.2 seconds Рис. 10.10: Профиль кучи для утечки памяти В картинку не поместились имена функций мы можем увеличить строку флагом L. Теперь все имена поместились (рис. 10.11).

$./leak 6 +RTS -K30m -hc -L (500000,500000) $ hp2ps -e80mm -c leak.hp С помощью флага hd посмотрим на объекты, которые застряли в куче (рис. 10.12):

$./leak 6 +RTS -K30m -hd -L (500000,500000) $ hp2ps -e80mm -c leak.hp Теперь куча разбита по типу объектов (замыканий) (рис. 10.12). BLACKHOLE это специальный объект, ко торый заменяет THUNK во время его вычисления. I# – это скрытый конструктор Int. sat_sUa и sat_sUd – это имена застрявших отложенных вычислений. Если бы наша программа была очень большой на этом месте мы бы запустили профилирование по функциям с флагом p и из файла leak.prof узнали бы в каких функциях программа тратит больше всего ресурсов. После этого мы бы пошли смотреть исходный код подозрительных функций и после внесённых изменений снова посмотрели бы на графики кучи.

Если подумать, что мы делаем? Мы создаём отложенное вычисление, которое обещает построить большой список, вытягиваем из списка по одному элементу и, если элемент оказывается чётным, прибавляем к одному элементу пары, а если не чётным, то к другому. Проблема в том, что внутри пары происходит накопление отложенных вычислений, необходимо сразу вычислять значения перед запаковыванием их в пару. Изменим код:

{-# Language BangPatterns #-} module Main where import System.Environment(getArgs) 168 | Глава 10: Реализация Haskell в GHC leak 6 +RTS -K30m -hc -L45 2,489,935 bytes x seconds Fri Jun 1 23:11 bytes 14M 12M (103)tick/sum2.iter/sum2/main/Main.CAF 10M 8M (102)main.xs/main/Main.CAF 6M 4M (101)sum2.iter/sum2/main/Main.CAF 2M 0M 0.0 0.0 0.0 0.1 0.1 0.1 0.1 0.1 0.2 0.2 0.2 0.2 seconds Рис. 10.11: Профиль кучи для утечки памяти leak 6 +RTS -K30m -hd -L45 3,016,901 bytes x seconds Fri Jun 1 23:14 bytes 14M BLACKHOLE 12M 10M I# 8M main:Main.sat_sUa 6M 4M main:Main.sat_sUd 2M 0M 0.0 0.1 0.1 0.2 0.2 0.2 seconds Рис. 10.12: Профиль кучи для утечки памяти main = print. sum2. xs. read = fmap head getArgs where xs n = [1.. 10 ^ n] sum2 :: [Int] - (Int, Int) sum2 = iter (0, 0) where iter c [] =c iter c (x:xs) = iter (tick x c) xs tick :: Int - (Int, Int) - (Int, Int) tick x (!c0, !c1) | even x = (c0, c1 + 1) | otherwise = (c0 + 1, c1) Мы сделали функцию tick строгой. Теперь посмотрим на профиль:

$ ghc --make leak2.hs -rtsopts -prof -auto-all $./leak2 6 +RTS -K30m -hc (500000,500000) Статистика выполнения программы | $ hp2ps -e80mm -c leak2.hp Не получилось (рис. 10.13). Как же так. Посмотрим на расход памяти отдельных функций. tick стала строгой, но этого не достаточно, потому что в первом аргументе iter накапливаются вызовы tick. Сделаем iter строгой по первому аргументу:

leak2 6 +RTS -K30m -hc 1,854,625 bytes x seconds Fri Jun 1 21:38 bytes 12M 10M (102)main.xs/main/Main.CAF 8M 6M (101)sum2.iter/sum2/main/M...

4M 2M 0M 0.0 0.0 0.0 0.1 0.1 0.1 0.1 0.1 0.2 0.2 0.2 seconds Рис. 10.13: Опять двойка sum2 :: [Int] - (Int, Int) sum2 = iter (0, 0) where iter !c [] =c iter !c (x:xs) = iter (tick x c) xs Теперь снова посмотрим на профиль:

$ ghc --make leak2.hs -rtsopts -prof -auto-all $./leak2 6 +RTS -K30m -hc (500000,500000) $ hp2ps -e80mm -c leak2.hp Мы видим (рис. 10.14), что память резко подскакивает и остаётся постоянной. Но теперь показатели измеряются не в мегабайтах, а в килобайтах. Мы справились. Остальные флаги hX позволяют наблюдать за разными специфическими объектами в куче. Мы можем узнать сколько памяти приходится на разные модули (hm), сколько памяти приходится на разные конструкторы (hd), на разные типы замыканий (hy).

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

*** Exception: Prelude.head: empty list или *** Exception: Maybe.fromJust: Nothing И совсем не понятно откуда эта ошибка. В каком модуле сидит эта функция. Может мы её импортировали из чужой библиотеки или написали сами. Как раз для таких случаев в GHC предусмотрен специальный флаг xc.

Посмотрим на выполнение такой программы:

170 | Глава 10: Реализация Haskell в GHC leak2 6 +RTS -hc 5,944 bytes x seconds Fri Jun 1 21:51 bytes 30k (51)PINNED 25k 20k (72)GHC.IO.Encoding.CAF 15k (59)GHC.IO.Handle.FD.CAF 10k (58)GHC.Conc.Signal.CAF 5k 0k 0.0 0.0 0.0 0.1 0.1 0.1 0.1 0.1 0.2 0.2 0.2 seconds Рис. 10.14: Профиль кучи без утечки памяти module Main where addEvens :: Int - Int - Int addEvens a b | even a && even b = a + b q = zipWith addEvens [0, 2, 4, 6, 7, 8, 10] (repeat 0) main = print q Для того, чтобы воспользоваться флагом xc необходимо скомпилировать программу с возможностью про филирования:

$ ghc --make break.hs -rtsopts -prof $./break +RTS -xc *** Exception (reporting due to +RTS -xc): (THUNK_2_0), stack trace:

Main.CAF break: break.hs:(4,1)-(5,30): Non-exhaustive patterns in function addEvens Так мы узнали в каком месте кода проявился злосчастный вызов, это строки (4,1)-(5,30). Что соот ветствует определению функции addEvens. Не очень полезная информация. Мы и так бы это узнали. Нам бы хотелось узнать тот путь, по которому шла программа к этому вызову. Проблема в том, что все вызовы слились в один CAF для модуля. Так разделим их:

$ ghc --make break.hs -rtsopts -prof -caf-all -auto-all $./break +RTS -xc *** Exception (reporting due to +RTS -xc): (THUNK_2_0), stack trace:

Main.addEvens, called from Main.q, called from Main.CAF:q -- evaluated by: Main.main, called from :Main.CAF:main break: break.hs:(4,1)-(5,30): Non-exhaustive patterns in function addEvens Теперь мы видим путь к этому вызову, мы пришли в него из значения q, которое было вызвано из main.

10.7 Оптимизация программ В этом разделе мы поговорим о том этапе компиляции, на котором происходят преобразования Core Core. Мы называли этот этап упрощением программы.

Оптимизация программ | Флаги оптимизации Мы можем задавать степень оптимизации программы специальными флагами. Самые простые флаги на чинаются с большой буквы O. Естественно, чем больше мы оптимизируем, тем дольше компилируется код.

Поэтому не стоит увлекаться оптимизацией на начальном этапе проектирования. Посмотрим какие возмож ности у нас есть:

• без -O – минимум оптимизаций, код компилируется как можно быстрее.

• -O0 – выключить оптимизацию полностью • -O – умеренная оптимизация.

• O2 – активная оптимизация, код компилируется дольше, но пока O2 не сильно выигрывает у O по про дуктивности.

Для оптимизации мы компилируем программу с заданным флагом, например попробуйте скомпилиро вать самый первый пример с флагом O:

ghc --make sum.hs -O и утечка памяти исчезнет.

Посмотреть описание конкретных шагов оптимизации можно в документации к GHC. Например при вклю чённой оптимизации GHC применяет анализ строгости. В ходе него GHC может исправить простые утечки памяти за нас. Стоит отметить оптимизацию -fexcess-precision, он может существенно ускорить програм мы, в которых много вычислений с Double. Но при этом вычисления могут потерять в точности, округление становится непредсказуемым.

Прагма INLINE Если мы посмотрим в исходный файл для модуля Prelude, то мы найдём такое определение для компо зиции функций:

-- | Function composition.

{-# INLINE (.) #-} -- Make sure it has TWO args only on the left, so that it inlines -- when applied to two functions, even if there is no final argument (.) :: (b - c) - (a - b) - a - c (.) f g = \x - f (g x) Помимо знакомого нам определения и комментариев мы видим новую прагму INLINE. Она указывает компилятору на то, что на этапе упрощения программы необходимо заменить вызов функции на её правую часть. Этот процесс называют встраиванием функций. Замена будет произведена только в случае полного применения функции, если синтаксическая арность (количество аргументов слева от знака равно) совпадает с числом переданных в функцию аргументов. Поэтому для GHC есть существенная разница между определе ниями:

(.) f g = \x - f (g x) (.) f g x = f (g x) Встраиванием функций мы экономим на создании лишних объектов в куче, но при этом код может су щественно разбухнуть. GHC пользуется эвристическим алгоритмом при определении когда функцию стоит встраивать, а когда – нет. По умолчанию GHC проводит встраивание только внутри модуля. Если мы компи лируем с флагом O, функции будут встраиваться между модулями. Для этого GHC сохраняет в интерфейсном файле (с расширением.hi) не только типы функций, но и правые части достаточно кратких функций. Дли на функции определяется числом узлов в синтаксическом дереве кода её правой части. Директивой INLINE мы приказываем GHC встроить функцию. Также есть более слабая версия этой прагмы –INELINABLE. Этой прагмой мы рекомендуем произвести встраивание функции не смотря на её величину.

Задать порог величины функции для встраивания можно с помощью флага -funfolding-use threshold=16. Отметим, что если функция не является экспортируемой и используется лишь один раз, то GHC встроит её в любом случае, поэтому стоит определять списки экспортируемых определений в шапке модуля, иначе компилятор будет считать, что экспортируются все определения.

Прагма INLINE может стоять в любом месте, где можно было бы объявить тип значения. Так например можно указать компилятору встраивать методы класса:

172 | Глава 10: Реализация Haskell в GHC instance Monad T where {-# INLINE return #-} return =...

{-# INLINE (=) #-} (=) =...

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

Например если мы скомпилируем такой код с флагом ddump-hi:

module Inline(f, g) where g :: Int - Int gx=x+ f :: Int - Int fx=g$gx то среди прочих определений увидим:

ghc -c -ddump-hi -O Inline.hs...

f :: GHC.Types.Int - GHC.Types.Int {- Arity: 1, HasNoCafRefs, Strictness: U(L)m, Unfolding: InlineRule (1, True, False) (\ x :: GHC.Types.Int case x of wild { GHC.Types.I# x1 GHC.Types.I# (GHC.Prim.+# (GHC.Prim.+# x1 2) 2) }) -}...

В этом виде прочесть функцию не так просто. Ко всем именам добавлены имена модулей. Приведём вывод к более простому виду с помощью флага dsuppress-all:

ghc -c -ddump-hi -dsuppress-all -O Inline.hs...

f :: Int - Int {- Arity: 1, HasNoCafRefs, Strictness: U(L)m, Unfolding: InlineRule (1, True, False) (\ x :: Int - case x of wild { I# x1 - I# (+# (+# x1 2) 2) }) -}...

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

Отметим также прагму NOINLINE с её помощью мы можем запретить встраивание функции. Эта праг ма часто используется при различных трюках с unsafePerformIO, встраивание функции, которая содержит неконтролируемые побочные эффекты, может повлиять на её результат.

Прагма RULES Разработчики GHC хотели, чтобы их компилятор был расширяемым и программист мог бы определять специфические для его приложения правила оптимизации. Для этого была придумана прагма RULES. За счёт чистоты функций мы можем в очень простом виде выражать инварианты программы. Инвариант – это неко торое свойство значения, которое остаётся постоянным при некоторых преобразованиях. Наиболее распро странённые инварианты имеют собственные имена. Например, это коммутативность сложения:

forall a b. a + b = b + a Здесь мы пишем: для любых a и b изменение порядка следования аргументов у (+) не влияет на результат.

С ключевым словом forall мы уже когда-то встречались, когда говорили о типе ST. Помните тип функции runST? Пример свойства функции map:

forall f g. map f. map g = map (f. g) Оптимизация программ | Это свойство принято называть дистрибутивностью. Мы видим, что функция композиции дистрибутив на относительно функции map. Инварианты определяют скрытые закономерности значений. За счёт чистоты функций мы можем безболезненно заменить в любом месте программы левую часть на правую или наобо рот. Оптимизация начинается тогда, когда мы понимаем, что одна из частей может быть вычислена гораздо эффективнее другой. Так в примере с map выражение справа от знака равно гораздо эффективнее, поскольку в нём мы не строим промежуточный список. Особенно ярко разница проявляется в энергичной стратегии вычислений. Или посмотрим на такое совсем простое свойство:

map id = id Если мы заменим левую часть на правую, то число сэкономленных усилий будет пропорционально длине списка. Вряд ли программист станет писать такие выражения, однако они могут появиться после выполнения других оптимизаций, например после многих встраиваний различных функций.

Можно представить, что эти правила являются дополнительными уравнениями в определении функции:

map f [] = [] map f (x:xs) = f x : map f xs map id a =a map f (map g x) = map (f. g) x Словно теперь мы можем проводить сопоставление с образцом не только по конструкторам, но и по выра жениям самого языка и функция map стала конструктором. Что интересно, зависимости могут быть какими угодно, они могут выражать закономерности, присущие той области, которую мы описываем. В дополни тельных уравнениях мы подставляем аргументы так же как и в обычных, если где-нибудь в коде программы находится соответствие с левой частью уравнения, мы заменяем её на правую. При этом мы пишем правила так, чтобы действительно происходила оптимизация программы, поэтому слева пишется медленная версия.

Такие дополнительные правила пишутся в специальной прагме RULES:

{-# RULES ”map/compose” forall f g x. map f (map g x) = map (f. g) x ”map/id” map id = id #-} Первым в кавычках идёт имя правила. Оно используется только для подсчёта статистики (например ес ли мы хотим узнать сколько правил сработало в данном прогоне программы). За именем правила пишут уравнение. В одной прагме может быть несколько уравнений. Правила разделяются точкой с запятой или переходом на другу строку. Все свободные переменные правила перечисляются в окружении forall (...).~. Компилятор доверяет нам абсолютно. Производится только проверка типов. Никаких других проверок не проводится. Выполняется ли на самом деле это свойство, будет ли вычисление правой части действительно проще программы вычисления левой – известно только нам.

Отметим то, что прагма RULES применяется до тех пор пока есть возможность её применять, при этом мы можем войти в бесконечный цикл:

{-# RULES ”infinite” forall a b. f a b = f b a #-} С помощью прагмы RULES можно реализовать очень сложные схемы оптимизации. Так в Prelude реализу ется слияние (fusion) списков. За счёт этой оптимизации многие выражения вида свёртка/развёртка не будут производить промежуточных списков. Этой схеме будет посвящена отдельная глава. Например если список преобразуется серией функций map, filter и foldr промежуточные списки не строятся.

Посмотрим как работает прагма RULES, попробуем скомпилировать такой код:

module Main where data List a = Nil | Cons a (List a) deriving (Show) foldrL :: (a - b - b) - b - List a - b foldrL cons nil x = case x of Nil - nil Cons a as - cons a (foldrL cons nil as) 174 | Глава 10: Реализация Haskell в GHC mapL :: (a - b) - List a - List b mapL = undefined {-# RULES ”mapL” forall f xs.

mapL f xs = foldrL (Cons. f) Nil xs #-} main = print $ mapL (+100) $ Cons 1 $ Cons 2 $ Cons 3 Nil Функция mapL не определена, вместо этого мы сделали косвенное определение в прагме RULES. Проверим, для того чтобы RULES заработали, необходимо компилировать с одним из флагов оптимизаций O или O2:

$ ghc --make -O Rules.hs $./Rules Rules: Prelude.undefined Что-то не так. Дело в том, что GHC проводит встраивание простых функций. GHC слишком поторопился и заменил mapL на её определение. Также обратим внимание на то, что выражение не соответствует левой части правила. У нас:

mapL f xs =/= mapL f $ xs Функция $ также является простой и GHC встраивает её. Для успешной замены нам необходимо, чтобы $ встроился раньше mapL и чтобы наше правило сработало раньше встраивания mapL.

Фазы компиляции Для решения этой проблемы в прагмы RULES и INLINE были введены ссылки на фазы компиляции. С по мощью них мы можем указать GHC в каком порядке реагировать на эти прагмы. Фазы пишутся в квадратных скобках:

{-# INLINE [2] someFun #-} {-# RULES ”fun” [0] forall...

”fun” [1] forall...

”fun” [~1] forall...

#-} Компиляция выполняется в несколько фаз. Фазы следуют от некоторого заданного целого числа, напри мер трёх, до нуля. Мы можем сослаться на фазу двумя способами: просто номером и номером с тильдой.

Ссылка без тильды говорит: не применяй правило до наступления данной фазы, далее – применяй. Ссылка c тильдой говорит: попытайся применить это правило как можно раньше – до наступления данной фазы, далее – не применяй.

В нашем примере мы задержим встраивание для mapL и foldrL так:

{-# INLINE [1] foldrL #-} foldrL :: (a - b - b) - b - List a - b {-# INLINE [1] mapL #-} mapL :: (a - b) - List a - List b Посмотреть какие правила сработали можно с помощью флага ddump-rule-firings. Теперь скомпилиру ем:

$ ghc --make -O Rules.hs -ddump-rule-firings...

Rule fired: SPEC Main.$fShowList [GHC.Integer.Type.Integer] Rule fired: mapL Rule fired: Class op show...

$./Rules Cons 101 (Cons 102 (Cons 103 Nil)) Среди прочих правил, определённых в стандартных библиотеках, сработало и наше.

Оптимизация программ | Прагма UNPACK Наш основной враг на этапе оптимизации программы это лишние объекты кучи. Чем меньше объектов мы создаём на пути к результату, тем эффективнее наша программа. С помощью прагмы INLINE мы можем избавиться от многих объектов, связанных с вызовом функции, это объекты типа FUN. Прагма UNPACK позволя ет нам бороться с лишними объектами типа CON. В прошлой главе мы говорили о том, что значения в Haskell содержат дополнительную служебную информацию, которая необходима на этапе вычисления, например значение сначала было отложенным, потом мы до него добрались и вычислили, возможно оно оказалось не определённым значением (undefined). Такие значения называются запакованными (boxed). Незапакованное значение, это примитивное значение, как оно представлено в памяти компьютера. Вспомним определение целых чисел:

data Int = I# Int# По традиции все незапакованные значения пишутся с решёткой на конце. Запакованные значения поз воляют откладывать вычисления, пользоваться undefined при определении функции. Но за эту гибкость приходится платить. Вспомним расход памяти в выражении [Pair 1 2] nil = [] -- глобальный объект (не в счёт) let x1 = I# 1 -- 2 слова x2 = I# 2 -- 2 слова p = Pair x1 x2 -- 3 слова val = Cons p nil -- 3 слова in val ----------- -- 10 слов Получилось десять слов для списка из одного элемента, который фактически хранит два значения. Размер списка, который хранит такие пары будет зависеть от числа элементов N как 10N. Тогда как полезная нагрузка составляет 2N. С помощью прагмы UNPACK мы можем отказаться от ленивой гибкости в пользу меньшего расхода памяти. Эта прагма позволяет встраивать один конструктор в поле другого. Это поле должно быть строгим (с пометкой !) и мономорфным (тип поля должен быть конкретным типом, а не параметром), причём подчинённый тип должен содержать лишь один конструктор (у него нет альтернатив):

data PairInt = PairInt {-# UNPACK #-} !Int {-# UNPACK #-} !Int Мы конкретизировали поля Pair и сделали их строгими с помощью восклицательных знаков. После этого значения из конструктора Int будут храниться прямо в конструкторе PairInt:

nil = [] -- глобальный объект (не в счёт) let p = PairInt 1 2 -- 3 слова val = Cons p nil -- 3 слова in val ----------- -- 6 слов Так мы сократим размер до 6N. Но мы можем пойти ещё дальше. Если этот тип является ключевым типом нашей программы и мы рассчитываем на то, что в нём будет хранится много значений мы можем создать специальный список для таких пар и распаковать значение списка:


data ListInt = ConsInt {-# UNPACK #-} !PairInt | NilInt nil = NilInt let val = ConsInt 1 2 nil -- 4 слова in val ---------- -- 4 слова Значение будет встроено дважды и получится, что у нашего нового конструктора Cons уже три поля.

Отметим, что эта прагма имеет смысл лишь при включённом флаге оптимизации -O или выше. Если мы не включим этот флаг, то компилятор не будет проводить встраивание функций, поэтому при вычислении функций вроде 176 | Глава 10: Реализация Haskell в GHC sumPair :: PairInt - Int sumPair (Pair a b) = a + b Плюс не будет встроен и вместо того, чтобы сразу сложить два числа с помощью примитивной функции, компилятор сначала запакует их в конструктор I# и затем применит функцию +, в которой опять распакует их, сложит и затем, снова запаковав, вернёт результат.

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

В стандартных библиотеках предусмотрено много незапакованных типов. Например это специальные кортежи. Они пишутся с решётками:

newtype ST s a = ST (STRep s a) type STRep s a = State# s - (# State# s, a #) Это определение типа ST. Специальные кортежи используются для возврата нескольких значений напря мую, без создания промежуточного кортежа в куче. В этом случае значения будут сохранены в регистрах или на стеке. Для использования специальных значений необходимо активировать расширения MagicHash и UnboxedTuples Разработчики различных библиотек могут предоставлять несколько вариантов своих данных: ленивые версии и незапакованные. Например в ST-массив незапакованных значений STUArray s i a эквивалентен массиву значений в C. В таком массиве можно хранить лишь примитивные типы.

10.8 Краткое содержание Эта глава была посвящена компилятору GHC. Мы говорим Haskell подразумеваем GHC, говорим GHC подразумеваем Haskell. К сожалению на данный момент у этого компилятора нет достойных конкурентов.

А может и к счастью, ведь если бы не было GHC, у нас была бы бурная конкуренция среди компиляторов поплоше. Мы бы не знали, что они не так хороши. Но у нас не было бы программ, которые способны тягаться по скорости с С. И мы бы говорили: ну декларативное программирование, что поделаешь, за радость аб стракций приходится платить. Но есть GHC! Всё-таки это очень трудно: написать компилятор для ленивого языка Отметим другие компиляторы: Hugs разработан Марком Джонсом (написан на C), nhc98 основанный Николасом Райомо (Niklas Rjemo) этот компилятор задумывался как легковесный и простой в установке, он разрабатывался при поддержке NUTEK, Йоркского университета и Технического университета Чалмерса. От этого компилятора отпочковался YHC, Йоркский компилятор. UHC – компилятор Утрехтского университета, разработан для тестирования интересных идей в теории типов. JHC (Джон Мичэм, John Meacham) и LHC (Дэвид Химмельступ и Остин Сипп, David Himmelstrup, Austin Seipp) компиляторы предназначенные для проведения более сложных оптимизаций программ с помощью преобразований дерева программы.

В этой главе мы узнали как вычисляются программы в GHC. Мы узнали об этапах компиляции. Снача ла проводится синтаксический анализ программы и проверка типов, затем код Haskell переводится на язык Core. Это сильно урезанная версия Haskell. После этого проводятся оптимизации, которые преобразуют де рево программы. На последнем этапе Core переводится на ещё более низкоуровневый, но всё ещё функцио нальный язык STG, который превращается в низкоуровневый код и исполняется вычислителем. Посмотреть на текст вашей программы в Core и STG можно с помощью флагов ddump-simpl ddump-stg при этом лучше воспользоваться флагом ddump-suppress-all для пропуска многочисленных деталей. Хардкорные разработ чики Haskell смотрят Core для того чтобы понять насколько строгой оказалась та или иная функция, как аргументы размещаются в памяти. Но это уже высший пилотаж искусства оптимизации на Haskell.

Мы узнали о том как работает сборщик мусора и научились просматривать разные параметры работы программы. У нас появилось несколько критериев оценки производительности программ: минимум глубоких очисток и отсутствие горбов на графике изменения кучи. Мы потренировались в охоте за утечками памяти и посмотрели как разные типы профилирования могут подсказать нам в каком месте затаилась ошибка.

Отметим, что не стоит в каждой медленной программе искать утечку памяти. Так в примере concat у нас не было утечек памяти, просто один из алгоритмов работал очень плохо и через профилирование функций мы узнали какой.

Также мы познакомились с новыми прагмами оптимизации программ. Это встраиваемые функции INLINE, правила преобразования выражений RULE и встраиваемые конструкторы UNPACK. Разработчики GHC отмеча ют, что грамотное использование прагмы INLINE может существенно повысить скорость программы. Если мы встраиваем функцию, которая используется очень часто, нам не нужно создавать лишних отложенных вычислений при её вызовах.

Краткое содержание | Надеюсь, что содержание этой главы упростит понимание программ. Как они вычисляются, куда идёт память, почему она висит в куче. При оптимизации программ предпочитайте изменение алгоритма перед настройкой параметров компилятора под плохой алгоритм. Вспомните самый первый пример, увеличением памяти под сборку мусора нам удалось вытянуть ленивую версию sum, но ведь строгая версия требовала в 100 раз меньше памяти, причём её запросы не зависели от величины списка. Если бы мы остановились на ленивой версии, вполне могло бы так статься, что первый год нас бы устраивали результаты, но потом наши аппетиты могли возрасти. И вдруг программа, так тщательно настроенная, взорвалась. За год мы, конечно, многое позабыли о её внутренностях, искать ошибку было бы гораздо труднее. Впрочем не так безнадёжно:

включаем auto-all, caf-all с флагом prof и смотрим отчёт после флага p.

10.9 Упражнения • Попытайтесь понять причину утечки памяти в примере с функцией sum2 на уровне STG. Не запоминайте этот пример, вроде, ага, тут у нас копятся отложенные вычисления в аргументе. Переведите на STG и посмотрите в каком месте происходит слишком много вызовов let-выражений. Переведите и пример без утечки памяти, а также промежуточный вариант, который не сработал. Для этого вам понадобится выразить энергичный образец через функцию seq.

Подсказка: За счёт семантики case-выражений нам не нужно специальных конструкций для того чтобы реализовать seq в STG:

seq = FUN( a b case a of x - b ) При этом вызов функции seq будет встроен. Необходимо будет заменить в коде все вызовы seq на пра вую часть определения (без FUN). Также обратите внимание на то, что плюс не является примитивной функцией:

plusInt = FUN( ma mb case ma of I# a - case mb of I# b - case (primitivePlus a b) of res - I# res ) В этой функции всплыла на поверхность одна тонкость. Если бы мы писали это выражение в Haskell, то мы бы сразу вернули результат (I#(primitivePlus a b)), но мы пишем в STG и конструктор может принять только атомарное выражение. Тогда мы могли бы подумать и сохранить его по старинке в let-выражении:

- let v = primitivePlus a b in I# v Но это не правильное выражение в STG! Конструкция в правой части let-выражения должна быть объ ектом кучи, а у нас там простое выражение. Но было бы плохо добавить к нему THUNK, поскольку это выражение содержит вызов примитивной функции на незапакованных значениях. Эта операция выпол няется очень быстро. Было бы плохо создавать для неё специальный объект на куче. Поэтому мы сразу вычисляем это выражение в третьем case. Эта функция также будет встроенной, необходимо заменить все вызовы на определение.

• Набейте руку в профилировании, пусть это станет привычкой. Вы долго писали большую программу и теперь вы можете узнать много подробностей из её жизни, что происходит с ней во время вычисления кода. Вернитесь к прошлой главе и попрофилируйте разные примеры. В конце главы мы рассматрива ли пример с поиском корней, там мы создавали большой список промежуточных результатов и в нём искали решение. Я говорил, что такие алгоритмы очень эффективны при ленивой стратегии вычис лений, но так ли это? Будьте критичны, не верьте на слово, ведь теперь у вас есть инструменты для проверки моих туманных гипотез.

• Откройте документацию к GHC. Пролистайте её. Проникнитесь уважением к разработчикам GHC. Най дите исходники GHC и почитайте их. Посмотрите на Haskell-код, написанный профессионалами. Вы берите функцию наугад и попытайтесь понять как она строит свой результат.

178 | Глава 10: Реализация Haskell в GHC • Откройте документацию вновь. Нас интересует глава Profiling. Найдите в разделе профилирование кучи как выполняется retainer profiling. Это специальный тип профилирования направленный на по иск данных, которые удерживают в памяти другие данные (типичный сценарий для утечек памяти).

Разберитесь с этим типом профилирования (флаг hr).

• Постройте систему правил, которая выполняет слияние для списков List, определённых в примере для прагмы RULES. Сравните показатели производительности с правилами и без (для этого скомпилируйте дважды с флагом O и без) на тестовом выражении:

main = print $ sumL $ mapL (\x - x - 1000) $ mapL (+100) $ mapL (*2) $ genL 0 1e Функция sumL находит сумму элементов в списке, функция genL генерирует список чисел с единичным шагом от первого аргумента до второго.

Подсказка: вам нужно воспользоваться такими свойствами (не забудьте о фазах компиляции) mapL f (mapL g xs) =...

foldrL cons nil (mapL f xs) =...

• Откройте исходный код Prelude и присмотритесь к различным прагмам. Попытайтесь понять почему они там используются.

Упражнения | Глава Ленивые чудеса В прошлой главе мы узнали, что такое ленивые вычисления. В этой главе мы посмотрим чем они хо роши. С ними можно делать невозможные вещи. Обращаться к ещё не вычисленным значениям, работать с бесконечными данными.


Мы пишем программу, чтобы решить какую-нибудь сложную задачу. Часто так бывает, что сложная задача оказывается сложной до тех пор пока её не удаётся разбить на отдельные независимые подзадачи. Мы решаем задачи по-меньше, потом собираем из них решения, из этих решений собираем другие решения и вот уже готова программа. Но мы решаем задачу не на листочке, нам необходимо объяснить её компьютеру. И тот язык, на котором мы пишем программу, оказывает сильное влияние на то как мы будем решать задачу. Мы не можем разбить программу на независимые подзадачи, если в том языке на котором мы собираемся объяснять задачу компьютеру нет средств для того, чтобы собрать эти решения вместе.

Об этом говорит Джон Хьюз (John Huges) в статье “Why functional programming matters”. Он приводит та кую метафору. Если мы делаем стул и у нас нет хорошего клея. Единственное что нам остаётся это вырезать из дерева стул целиком. Это невероятно трудная задача. Гораздо проще сделать отдельные части и потом собрать вместе. Функциональные языки программирования предоставляют два новых вида “клея”. Это функ ции высшего порядка и ленивые вычисления. В статье можно найти много примеров. Некоторые из них мы рассмотрим в этой главе.

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

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

11.1 Численные методы Рассмотрим несколько численных методов. Все эти методы построены на понятии сходимости. У нас есть последовательность решений и она сходится к одному решению, но мы не знаем когда. Мы только знаем, что промежуточные решения будут всё ближе и ближе к итоговому.

Поскольку у нас ленивый язык мы сначала построим все возможные решения, а затем выберем итоговое.

Так же как мы делали это в прошлой главе, когда искали корни уравнения методом неподвижной точки. Эти примеры взяты из статьи “Why functional programming matters” Джона Хьюза.

Дифференцирование Найдём производную функции в точке. Посмотрим на математическое определение производной:

f (x + h) f (x) f (x) = lim h h Производная это предел последовательности таких отношений, при h стремящемся к нулю. Если предел сходится, то производная определена. Для того чтобы решить эту задачу мы начнём с небольшого значе ния h и будем постепенно уменьшать его, вычисляя промежуточные значения производной. Как только они перестанут сильно изменяться мы будем считать, что мы нашли предел последовательности Этот процесс напоминает то, что мы делали при поиске корня уравнения методом неподвижной точки.

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

180 | Глава 11: Ленивые чудеса converge :: (Ord a, Num a) = a - [a] - a converge eps (a:b:xs) | abs (a - b) = eps =a | otherwise = converge eps (b:xs) Теперь осталось только создать последовательность значений производных. Напишем функцию, которая вычисляет промежуточные решения:

easydiff :: Fractional a = (a - a) - a - a - a easydiff f x h = (f (x + h) - f x) / h Мы возьмём начальное значение шага и будем последовательно уменьшать его вдвое:

halves = iterate (/2) Соберём все части вместе:

diff :: (Ord a, Fractional a) = a - a - (a - a) - a - a diff h0 eps f x = converge eps $ map (easydiff f x) $ iterate (/2) h where easydiff f x h = (f (x + h) - f x) / h Сохраним эти определения в отдельном модуле и найдём производную какой-нибудь функции. Проте стируем решение на экспоненте. Известно, что производная экспоненты равна самой себе:

*Numeric let exp’ = diff 1 1e-5 exp *Numeric let test x = abs $ exp x - exp’ x *Numeric test 1.4093421286887065e- *Numeric test 1.767240203776055e- Интегрирование Теперь давайте поинтегрируем функции одного аргумента. Интеграл это площадь кривой под графиком функции. Если бы кривая была прямой, то мы могли бы вычислить интеграл по формуле трапеций:

easyintegrate :: Fractional a = (a - a) - a - a - a easyintegrate f a b = (f a + f b) * (b - a) / Но мы хотим интегрировать не только прямые линии. Мы представим, что функция является ломаной прямой линией. Мы посчитаем интеграл на каждом из участков и сложим ответы. При этом чем ближе точки друг к другу, тем точнее можно представить функцию в виде ломаной прямой линии, тем точнее будет значение интеграла.

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

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

Построим последовательность решений:

integrate :: Fractional a = (a - a) - a - a - [a] integrate f a b = easyintegrate f a b :

zipWith (+) (integrate a mid) (integrate mid b) where mid = (a + b)/ Первое решение является площадью под прямой, которая соединяет концы отрезка. Потом мы делим от резок пополам, строим последовательность приближений и складываем частичные суммы с помощью функ ции zipWith.

Эта версия функции хоть и наглядная, но не эффективная. Функция f вычисляется заново при каждом ре курсивном вызове. Было бы хорошо вычислять её только для новых значений. Для этого мы будем передавать значения с предыдущего шага:

integrate :: Fractional a = (a - a) - a - a - [a] integrate f a b = integ f a b (f a) (f b) where integ f a b fa fb = (fa+fb)*(b-a)/2 :

zipWith (+) (integ f a m fa fm) (integ f m b fm fb) where m = (a + b)/ fm = f m Численные методы | В этой версии мы вычисляем значения в функции f лишь один раз для каждой точки. Запишем итоговое решение:

int :: (Ord a, Fractional a) = a - (a - a) - a - a - a int eps f a b = converge eps $ integrate f a b Мы опять воспользовались функцией converge, нам не нужно было её переписывать. Проверим решение.

Для проверки также воспользуемся экспонентой. В прошлой главе мы узнали, что x ex = 1 + et dt Посмотрим, так ли это для нашего алгоритма:

*Numeric let exp’ = int 1e-5 exp *Numeric let test x = abs $ exp x - 1 - exp’ x *Numeric test 8.124102876649886e- *Numeric test 4.576306736225888e- *Numeric test 1.0683757864171639e- Алгоритм работает. В статье ещё рассмотрены методы повышения точности этих алгоритмов. Что инте ресно для улучшения точности не надо менять существующий код. Функция принимает последовательность промежуточных решений и преобразует её.

11.2 Степенные ряды Напишем модуль для вычисления степенных рядов. Этот пример взят из статьи Дугласа МакИлроя (Douglas McIlroy) “Power Series, Power Serious”. Степенной ряд представляет собой функцию, которая опре деляется списком коэффициентов:

F (x) = f0 + f1 x + f2 x2 + f3 x3 + f4 x4 +...

Степенной ряд содержит бесконечное число слагаемых. Для вычисления нам потребуются функции сло жения и умножения. Ряд F (x) можно записать и по-другому:

F (x) = F0 (x) = f0 + xF1 (x) = f0 + x(f1 + xF2 (x)) Это определение очень похоже на определение списка. Ряд есть коэффициент f0 и другой ряд F1 (x) умноженный на x. Поэтому для представления рядов мы выберем конструкцию похожую на список:

data Ps a = a :+: Ps a deriving (Show, Eq) Но в нашем случае списки бесконечны, поэтому у нас лишь один конструктор. Далее мы будем писать просто f + xF1, без скобок для аргумента.

Определим вспомогательные функции для создания рядов:

p0 :: Num a = a - Ps a p0 x = x :+: p0 ps :: Num a = [a] - Ps a ps [] = p0 ps (a:as) = a :+: ps as Обратите внимание на то, как мы дописываем бесконечный хвост нулей в конец ряда. Теперь давайте определим функцию вычисления ряда. Мы будем вычислять лишь конечное число степеней.

eval :: Num a = Int - Ps a - a - a eval 0 _ _= eval n (a :+: p) x = a + x * eval (n-1) p x В первом случае мы хотим вычислить ноль степеней ряда, поэтому мы возвращаем ноль, а во втором случае значение ряда a+xP складывается из числа a и значения ряда P умноженного на заданное значение.

182 | Глава 11: Ленивые чудеса Арифметика рядов В результате сложения и умножения рядов также получается ряд. Также мы можем создать ряд из числа.

Эти операции говорят о том, что мы можем сделать степенной ряд экземпляром класса Num.

Сложение Рекурсивное представление ряда f + xF позволяет нам очень кратко выражать операции, которые мы хотим определить. Теперь у нас нет бесконечного набора коэффициентов, у нас всего лишь одно число и ещё один ряд. Операции существенно упрощаются. Так сложение двух бесконечных рядов имеет вид:

F + G = (f + xF1 ) + (g + xG1 ) = (f + g) + x(F1 + G1 ) Переведём на Haskell:

(f :+: fs) + (g :+: gs) = (f + g) :+: (fs + gs) Умножение Умножим два ряда:

F G = (f + xF1 ) (g + xG1 ) = f g + x(f G1 + F1 G) Переведём:

(.*) :: Num a = a - Ps a - Ps a k.* (f :+: fs) = (k * f) :+: (k.* fs) (f :+: fs) * (g :+: gs) = (f * g) :+: (f.* gs + fs * (g :+: gs)) Дополнительная операция (.*) выполняет умножение всех коэффициентов ряда на число.

Класс Num Соберём определения для методов класса Num вместе:

instance Num a = Num (Ps a) where (f :+: fs) + (g :+: gs) = (f + g) :+: (fs + gs) (f :+: fs) * (g :+: gs) = (f * g) :+: (f.* gs + fs * (g :+: gs)) negate (f :+: fs) = negate f :+: negate fs fromInteger n = p0 (fromInteger n) (.*) :: Num a = a - Ps a - Ps a k.* (f :+: fs) = (k * f) :+: (k.* fs) Методы abs и signum не определены для рядов. Обратите внимание на то, как рекурсивное определение рядов приводит к рекурсивным определениям функций для рядов. Этот приём очень характерен для Haskell.

Поскольку наш ряд это число и ещё один ряд за счёт рекурсии мы можем воспользоваться операцией, которую мы определяем, на “хвостовом” ряде.

Деление Результат деления Q удовлетворяет соотношению:

F =QG Переписав F, G и Q в нашем представлении, получим f + xF1 = (q + xQ1 ) G = qG + xQ1 G = q(g + xG1 ) + xQ1 G = qg + x(qG1 + Q1 G) Следовательно q = f /g Q1 = (F1 qG1 )/G Если g = 0 деление имеет смысл только в том случае, если и f = 0. Переведём на Haskell:

Степенные ряды | instance (Eq a, Fractional a) = Fractional (Ps a) where (0 :+: fs) / (0 :+: gs) = fs / gs (f :+: fs) / (g :+: gs) = q :+: ((fs - q.* gs)/(g :+: gs)) where q = f/g fromRational x = p0 (fromRational x) Производная и интеграл Производная одного члена ряда вычисляется так:

dn x = nxn dx Из этого выражения по свойствам производной d d d (f (x) + g(x)) = f (x) + g(x) dx dx dx d d (k f (x)) = k f (x) dx dx мы можем получить формулу для всего ряда:

d F (x) = f1 + 2f2 x + 3f3 x2 + 4f4 x3 +...

dx Для реализации нам понадобится вспомогательная функция, которая будет обновлять значение допол нительного множителя n в выражении nxn1 :

diff :: Num a = Ps a - Ps a diff (f :+: fs) = diff’ 1 fs where diff’ n (g :+: gs) = (n * g) :+: (diff’ (n+1) gs) Также мы можем вычислить и интеграл степенного ряда:

int :: Fractional a = Ps a - Ps a int (f :+: fs) = 0 :+: (int’ 1 fs) where int’ n (g :+: gs) = (g / n) :+: (int’ (n+1) gs) Элементарные функции Мы можем выразить элементарные функции через операции взятия производной и интегрирования. К примеру уравнение для ex выглядит так:

dy =y dx Проинтегрируем с начальным условием y(0) = 1:

x y(x) = 1 + y(t)dt Теперь переведём на Haskell:

expx = 1 + int expx Кажется невероятным, но это и есть определение экспоненты. Так же мы можем определить и функции для синуса и косинуса:

sin x = cos x, sin(0) = 0, d dx cos x = sin x, cos(0) = d dx Что приводит нас к:

sinx = int cosx cosx = 1 - int sinx И это работает! Вычисление этих функций возможно за счёт того, что вне зависимости от аргумента функция int вернёт ряд, у которого первый коэффициент равен нулю. Это значение подхватывается и ис пользуется на следующем шаге рекурсивных вычислений.

Через синус и косинус мы можем определить тангенс:

tanx = sinx / cosx 184 | Глава 11: Ленивые чудеса 11.3 Водосборы В этом примере мы рассмотрим одну интересную технику рекурсивных вычислений, которая называется мемоизацией (memoization). Она заключается в том, что мы запоминаем все значения, с которыми вызывалась функция и, если с данным значением функция уже вычислялась, просто используем значение из памяти, а если значение ещё не вычислялось, вычисляем его и сохраняем.

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

Посмотрим на такой классический пример. Вычисление чисел Фибоначчи. Каждое последующее число ряда Фибоначчи равно сумме двух предыдущих. Наивное определение выглядит так:

fib :: Int - Int fib 0 = fib 1 = fib n = fib (n-1) + fib (n-2) В этом определении число вычислений растёт экспоненциально. Для того чтобы вычислить fib n нам нужно вычислить fib (n-1) и fib (n-2), для того чтобы вычислить каждое из них нам нужно вычислить ещё два числа, и так вычисления удваиваются на каждом шаге. Если мы вызовем в интерпретаторе fib 40, то вычислитель зависнет. Что интересно в этой функции вычисления пересекаются, они могут быть пере использованы. Например для вычисления fib (n-1) и fib (n-2) нужно вычислить fib (n-2) (снова), fib (n-3), fib (n-3) (снова) и fib (n-4).

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

fib’ :: Int - Int fib’ n = fibs !! n where fibs = 0 : 1 : zipWith (+) fibs (tail fibs) Попробуем вычислить для 40:

*Fib fib’ *Fib fib’ Вычисления происходят мгновенно. Если задача состоит из множества подзадач, которые самоподобны и для вычисления последующих подзадач используются решения из предыдущих, стоит задуматься об ис пользовании мемоизации. Такие задачи называются задачами динамического программирования. Вычисление чисел Фибоначчи яркий пример задачи динамического программирования.

Рассмотрим такую задачу. Дана прямоугольная “карта местности”, в каждой клетке целым числом ука зана высота точки. Необходимо разметить местность по следующим правилам:

• Из каждой клетки карты вода стекает не более чем в одном из четырёх возможных направлений (“се вер”, “юг”, “запад”, “восток”).

• Если у клетки нет ни одного соседа с высотой меньше её собственной высоты, то эта клетка – водосток, и вода из неё никуда дальше не течёт.

• Иначе вода из текущей клетки стекает на соседнюю клетку с минимальной высотой.

• Если таких соседей несколько, то вода стекает по первому из возможных направлений из списка “на север”, “на запад”, “на восток”, “на юг”.

Все клетки из которых вода стекает в один и тот же водосток принадлежат к одному бассейну водосбо ра. Необходимо отметить на карте все бассейны. Решение этой задачи встретилось мне в статье Дмитрия Астапова “Рекурсия+мемоизация = динамическое программирование”. Здесь оно и приводится с незначи тельными изменениями.

Карта местности представлена в виде двумерного массива, в каждой клетке которого отмечена высота точки, нам необходимо получить двумерный массив того же размера, который вместо высот содержит метки водостоков. Мы будем отмечать их буквами латинского алфавита в том порядке, в котором они встречаются при обходе карты сверху вниз, слева направо. Например:

Водосборы | 123456 aaabbb 789245 aabbbb 353367 - ccdbbe 645531 fgdbee 224537 fgghhe Для представления двумерного массива мы воспользуемся типом Array из стандартного модуля Data.Array. Тип Array имеет два параметра:

data Array i a Первый указывает на индекс, а второй на содержание. Массивы уже встречались нам в главе о типе ST.

Напомню, что подразумевается, что этот тип является экземпляром класса Ix, который описывает целочис ленные индексы, вспомним его определение:

class Ord a = Ix a where range :: (a, a) - [a] index :: (a, a) - a - Int inRange :: (a, a) - a - Bool rangeSize :: (a, a) - Int Первый аргумент у всех этих функций это пара, которая представляет верхнюю и нижнюю грань после довательности. Попробуйте догадаться, что делают методы этого класса по типам и именам.

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

import Data.Array type Coord = (Int, Int) type HeightMap = Array Coord Int type SinkMap = Array Coord Coord type LabelMap = Array Coord Char Значение типа HeightMap хранит карту высот, значение типа SinkMap хранит в каждой координате, ту точ ку, которая является водостоком для данной точки. Тип LabelMap обозначает итоговую разметку водостоков.

Начнём с функции:

flow :: HeightMap - SinkMap Мы будем решать эту задачу рекурсивно. Представим, что мы знаем водостоки для всех точек кроме данной. Для каждой точки мы можем узнать в какую сторону из неё стекает вода. При этом водосток для следующей точки такой же как и для текущей. Если же из данной точки вода никуда не течёт, то она сама является водостоком. Мы определим эту функцию через комбинатор неподвижной точки fix.:

flow :: HeightMap - SinkMap flow arr = fix $ \result - listArray (bounds arr) $ map (\x - maybe x (result !) $ getSink arr x) $ range $ bounds arr getSink :: HeightMap - Coord - Maybe Coord Мы ищем решение в виде неподвижной точки функции, которая принимает карту стоков и возвращает карту стоков. Функция getSink по данной точке на карте вычисляет соседнюю точку, в которую стекает вода.

Эта функция частично определена, поскольку для водостоков нет такой соседней точки, в которую бы утекала вода. Функция listArray конструирует значение типа Array из списка значений. Первым аргументом она принимает диапазон значений для индексов. Размеры массива совпадают с размерами карты высот, поэтому первым аргументом мы передаём bounds arr.

Теперь разберёмся с тем как заполняются значения в список. Сначала мы создаём список координат исходной карты высот с помощью выражения:

range $ bounds arr После этого мы по координатам точек находим водостоки, причём сразу для всех точек. Это происходит в лямбда-функции:

\x - maybe x (result !) $ getSink arr x 186 | Глава 11: Ленивые чудеса Мы принимаем текущую координату и с помощью функции getSink находим соседнюю точку, в которую убегает вода. Если такой точки нет, то в следующем выражении мы вернём исходную точку, поскольку в этом случае она и будет водостоком, а если такая соседняя точка всё-таки есть мы спросим результат из будущего.

Мы обратимся к результату (result !), посмотрим каким окажется водосток для соседней точки и вернём это значение. Поскольку за счёт ленивых вычислений значения результирующего массива вычисляются лишь один раз, после того как мы найдём водосток для данной точки этим результатом смогут воспользоваться все соседние точки. При этом порядок обращения к значениям из будущих вычислений не играет роли.

Осталось только определить функцию поиска ближайшего стока и функцию разметки.



Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |   ...   | 11 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.