# Haskell: ДЗ 4 -- Параллельность. Многопоточность. Строгость. В данном домашнем задании от Вас требуется продемонстрировать знание многопоточных примитивов в Haskell, а так же умение делать код строгим. Ваш код будет компилироваться с флагом `-threaded` и запускаться с флагом`+RTS -N4`. В заданиях, где приведены сигнатуры функций - Вы должны строго следовать данным сигнатурам, за изменение типа функций будут сниматься баллы. Для некоторых заданий есть усложненные версии, в которых требуется измерить перфоманс. Для этого необходимо использовать пакет `criterion`. Будьте осторожны с тем, что при тестировании Ваш код может не вычислиться в нормальную форму, и следовательно, не будет вызываться код, перфоманс которого Вы хотите измерить. ## Задание 1. Перемножение матриц Реализуйте функцию ```haskell multiply :: [[Int]] -> [[Int]] -> Maybe [[Int]] ``` принимающую две матрицы и возвращающую их произведение. Гарантируется, что строки в пределах одной матрицы будут иметь равную длину. Гарантируется, что размерности матриц ненулевые. Учтите, что реализация должна быть эффективной и не вызывать space leak-ов. Для реализации можно использовать монаду `ST` и/или пакет `vector`, и другие примитивы разобранные на лекциях. #### Усложненное задание Необходимо написать несколько тестов измеряющих перфоманс, используя пакет `criterion`. Напишите для тестов более наивную реализацию и сравните их по времени и памяти. ## Задание 2. Геометрия В данном задании от вас требуется создать дататайп `Point`, который будет представлять точку в двумерном пространстве с целочисленными координатами. Затем реализуйте функции для работы с точками: ```haskell plus :: Point -> Point -> Point minus :: Point -> Point -> Point scalarProduct :: Point -> Point -> Int crossProduct :: Point -> Point -> Int ``` Затем реализуйте функции, которые принимают на вход многоугольник без самопересечений, заданный координатами его вершин в порядке против часовой стрелки. Многоугольник может быть как выпуклый, так и не выпуклый. ```haskell perimeter :: [Point] -> Double -- Считает периметр doubleArea :: [Point] -> Int -- Считает удвоенную площадь ``` Функции должны обрабатывать многоугольники с количеством точек до $10^7$ за 1-2 секунды. Чтобы ускорить реализацию, делайте Ваш код строгим по возможности и используйте примитивы многопоточности. #### Усложненное задание Необходимо написать несколько тестов измеряющих перфоманс, используя пакет `criterion`. Напишите для тестов более наивную реализацию и сравните их по времени и памяти. ## Задание 3. Система уравнений В данном задании от Вас требуется реализовать функцию ```haskell gauss :: [[Bool]] -> [Bool] -> Maybe [Bool] ``` которая решает систему уравнений методом Гаусса над булевым полем. $$ a_{11} \wedge x_1 \oplus a_{12} \wedge x_2 \oplus ... \oplus a_{1n} \wedge x_n = y_1$$ $$a_{21} \wedge x_1 \oplus a_{22} \wedge x_2 \oplus ... \oplus a_{2n} \wedge x_n = y_2 $$ $$ ... $$ $$a_{m1} \wedge x_1 \oplus a_{m2} \wedge x_2 \oplus ... \oplus a_{mn} \wedge x_n = y_m $$ $\wedge$ - операция $and$ $\oplus$ - операция $xor$ $a_{ij}$, $y_j$ и $x_i$ - булевые значения, которые равны либо $0$ (`False`), либо $1$ (`True`). Вам заданы коэффициенты $a_{ij}$ и $y_j$, найдите значение переменных $x_1, ... x_n$, на которых удовлетворяется данная система или выясните, что система не имеет решений. Можете считать, что функция вызывается с корректными данными, а именно: * количество строк в матрице $a_{ij}$ равно количеству элементов в $y$ * количество элементов в каждом $a_i$ одинаково Далее реализуйте функцию, которая проверяет, что решение корректно: ```haskell verifySolution :: [[Bool]] -> [Bool] -> [Bool] -> Bool ``` Данная функция также будет проверяться с корректным входом. Постарайтесь сделать реализациb по возможности быстрыми, используя строгость и примитивы для многопоточности. ## Задание 4. Хэш таблица В данном задании от Вас требуется написать хэш таблицу, которая способна обрабатывать запросы из нескольких потоков одновременно. Хэш таблица должна работать довольно быстро для $10^5$ параллельных запросов. Необходимо реализовать следующий дататайп: ```haskell data ConcurrentHashTable k v = ...your code here.. ``` а затем следующие функции: ```haskell newCHT :: IO (ConcurrentHashTable k v) getCHT :: k -> ConcurrentHashTable k v -> IO (Maybe v) putCHT :: k -> v -> ConcurrentHashTable k v -> IO () sizeCHT :: ConcurrentHashTable k v -> IO Int ``` Сигнатуры функций даны без констреинтов, потому что они будут зависеть от реализации. Ваша реализация должна удовлетворять следующим условиям: * выполнять все операции `put` в конечном итоге, если все потоки завершаются * быть устойчива к асинхронным исключениям: асинхронное исключение не должно делать состояние хэш-таблицы неконсистентным * использовать $O(n)$ памяти, где $n$ - количество добавленных элементов Для реализации можете использовать примитивы для конкаренси, такие как `MVar`, `TVar`, `TMVar` и другие. #### Усложненное задание Необходимо написать несколько тестов измеряющих перфоманс, используя пакет `criterion`. Также необходимо написать несколько тестов, проверяющих корректность операций и устойчивость к асинхронным исключениям. ## Задание 5. Управление ресурсами В данном задании от Вас требуется реализовать трансформер монад, для безопасного управления ресурсами. Он должен освобождать ресурсы и находиться в консистентном состоянии даже в случае, если другой поток бросает асинхронное исключение потоку исполнения. В данном задании Вам даны сигнатуры функций, без констреинтов, потому что они будут зависеть от реализации. Трансформер должен иметь тип ```haskell newtype AllocateT m a = ...your definition here... ``` Далее необходимо реализовать следующие функции: ```haskell allocate :: IO a -- ^ действие, которое выделяет ресурс -> (a -> IO ()) -- ^ действие, которое освобождает его -> AllocateT m (a, ResourceKey) -- ^ ресурс и указатель на негоs ``` Эта функция выделяет ресурс и возвращает его вместе с указателем (который используется далее). ```haskell release :: ResourceKey -> AllocateT m () ``` Данная функция освобождает ресурс. ```haskell runAllocateT :: AllocateT m a -> m a ``` Запуск действия в `AllocateT`. Данная функция должна реализовывать следующую сементику: все еще не освобожденные ресурсы должны освободиться. Обратите внимание, что освобождение ресурса должно произойти в любом случае, даже если потоку освобождающему ресурс брошено асинхронное исключение. Используйте `bracket`, `mask`, `finally` и другие функции для выполнения этого условия. Предполагается, что вы будете обрабатывать ошибки, возникающие в результате неправильного/неожиданного использоваания данного трансформера, например вызов `release` дважды от одного и того же указателя на ресурс. Если в результате выполнения брошено исключение, должны освободиться все ресурсы. #### Усложненное задание В данном задании Вам необходимо реализовать функции для безопасной работы с ресурсами в многопоточном окружении. Функции должны быть неблокирующими. ```haskell resourceFork :: (m () -> m ()) -- ^ функция fork, для создания дочернего потока -> AllocateT m () -> AllocateT m () ``` Данная функция принимает действие, которое должно быть выполнено в другом потоке. Это действие захватывает все уже выделенные ресурсы, то есть если главный поток завершает свое выполнение (успешно либо с исключением), а дочерний поток нет - ресурсы не должны быть освобождены до тех пор, пока дочерний поток не завершится. Данное правило не распространяется на `release`: он освобождает ресурс в любом случае.