Сложность простоты30.09.2019 10:49

Как я писал в предисловии предыдущей статьи, я нахожусь в поисках языка, в котором я мог бы писать поменьше, а безопасности иметь побольше. Моим основным языком программирования всегда был C#, поэтому я решил попробовать два языка, симметрично отличающиеся от него по шкале сложности, про которые до этого момента приходилось только слышать, а вот писать не довелось: Haskell и Go. Один язык стал известен высказыванием «Avoid success at all costs»*, другой же, по моему скромному мнению, является полной его противоположенностью. В итоге, хотелось понять, что же окажется лучше: умышленная простота или умышленная строгость?

Я решил написать решение одной задачки, и посмотреть, насколько это просто на обоих языках, какая у них кривая обучения для разработчика с опытом, сколько всего надо изучить для этого и насколько идиоматичным получается «новичковый» код в одном и другом случае. Дополнительно хотелось понять, сколько в итоге мне придется заплатить за ублажание хаскеллевского компилятора и сколько времени сэкономит знаменитое удобство горутин. Я старался быть настолько непредвзятым, насколько это возможно, а субъективное мнение приведу в конце статьи. Итоговые результаты меня весьма удивили, поэтому я решил, что хабровчанам будет интересно почитать про такое сравнение.

И сразу небольшая ремарка. Дело в том, что выражение (*) часто используют иронически, но это лишь потому, что люди его неверно парсят. Они читают это как «Avoid (success) (at all costs)», то есть «что бы ни произошло, если это ведет к успеху, мы должны это избежать», тогда как по-настоящему фраза читается как «Avoid (success at all costs)», то есть «если цена успеха слишком велика, то мы должны отступить на шаг и всё переосмыслить». Надеюсь, после этого объяснения она перестала быть смешной и обрела настоящий смысл: идеология языка требует правильно планировать свое приложение, и не вставлять adhoc костылей там, где они обойдутся слишком дорого. Идеология го, в свою очередь, скорее «код должен быть достаточно простым, чтобы в случае изменения требований его легко было выкинуть и написать новый».

Методика сравнения

Не мудрувствуя лукаво, я взял задачку, которую придумал товарищ 0xd34df00d и звучит она следующим образом:

Допустим у нас есть дерево идентификаторов каких-либо сущностей, например, комментариев (в памяти, в любом виде). Выглядит оно так:

|- 1
   |- 2
   |- 3
      |- 4
      |- 5

Ещё у нас есть некое API которое по запросу /api/{id} возвращает JSON-представление этого комментария.

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

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

В итоге вывод программы должен выглядеть примерно так:

|- 1
   |- 2
   |- 3
      |- 4
      |- 5

|- 1:Оригинальный комментарий
   |- 2:Ответ на комментарий 1
   |- 3:Ответ на комментарий 2
      |- 4:Ответ на ответ 1
      |- 5:Ответ на ответ 2

В качестве тестового апи я использовал любезно предоставленный первой строчкой гугла сервис https://jsonplaceholder.typicode.com/todos/

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

Отступление про Haskell

Если вы знаете, зачем нужны точка-оператор, доллар-оператор и как работает do-нотация, то смело пропускайте раздел и преходите к следующему. Иначе очень рекомендую почитать, будет интересно. А ещё будут монады на C#

Здесь что-то на эльфийском. Не могу прочитать

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

Прежде чем начать статью, я хотел бы немного поговорить о структуре ML языков. Дело в том, что всем известно, что Lingua Franca низко- и среднеуровневых* языков это С. Если ты пишешь на джаве, а твой коллега на питоне, просто пошли ему сниппет на С, он поймет. Работает и в обратную сторону. Все знают си, и на чем бы они ни писали по работе, на нем они всегда договорятся.

* под низкоуровневыми языками я имею ввиду языки С/С++/…, а под среднеуровневыми — C++/C#/Java/Kotlin/Swift/…

Но менее известно, что в высокоуровневых языках это Haskell. В Scala/F#/Idris/Elm/Elexir/… тусовках если не знаешь, на чем пишет твой визави — пиши на хаскелле, не ошибешься. Однако программистов на этих языках не так много, и для более широкого охвата статьей я приведу небольшой разговорник, чтобы вариант на Haskell не казался китайской грамотой. Я буду приводить примеры на Rust/C#, они должны быть понятны любому человеку, знакомому с С. Термины Option/Maybe, Result/Either и Task/Promise/Future/IO означают одно и то же в разных языках и могут быть взаимозаменяемо использованы друг вместо друга.

Итак, Если вы видете перед собой

data Maybe a = Just a | Nothing  -- это комментарий

То это означает

// это тоже комментарий
enum Maybe {
   Just(T),
   Nothing
}

То есть просто энум, к одному из значений которых прицеплено дополнительное значение. Отличия в записи от Rust: генерик-аргументы в С-подобных языках принято выделять угловыми скобками и зачастую начинать с T. В хаскелле генерик-аргументы пишутся маленькими буквами через пробел. Одно это знание позволит вам расшифровывать тайные письмена хаскеллистов. Например, другой тип

data Either a b = Left a | Right b

мы теперь легко можем прочитать, и переписать знакомым нам образом

enum Either {
   Left(A),
   Right(B)
}

Довольно логично и последовательно. Стоит немного привыкнуть, и эта запись будет вам казаться вполне естественной (лично я переучился где-то за полчаса написания кода).

Ну и конечно кроме тип-сумм есть и типы-произведения, это обычные структуры, которые пишутся так:

data Comment = Comment {
      title :: String
    , id  :: Int
    } deriving (Show) -- просим компилятор автоматически генерировать функцию
              -- преобразования в строку (аналог метода ToString() в C#/Java)

и переводятся как:

#[derive(Display)]
struct Comment {
    title: String,
    id: i32
}

Пока вроде все просто, идем дальше.

Если же вы видете перед собой

sqr :: Int -> Int
sqr x = x*x

main :: IO () -- IO это специальный тип, обозначающий взаимодействие с внешним миром, в частности вывод на консоль
main = print (sqr 3)

То это

fn sqr(x: i32) -> i32 { x*x }
fn main() {
   println!("{}", sqr(3));
}

Здесь мы объявляем две функции, одна — функция возведения в квадрат, а другая — вездесущий main.

Одна особенность, которую мы сразу видим: в С-языках вызов функции обособляется собками, в ML-подобных — пробелом. Но скобками все-равно приходится пользоваться из-за левой ассоциативности языка. Поэтому мы выделяем (sqr 3) в скобочки, чтобы сперва вычислилось это значение, а затем оно использовалось для вывода на экран. Без скобочек компилятор попробует сначала выполнить print sqr и конечно же выдаст ошибку компиляции, потому sqr является типом Fn(i32) -> i32 (Func в терминах C#), для которого не определен метод show (местный ToString()).

Другая особенность: объявление функции в хаскеле состоит из двух частей: первая (необязательная) — описание сигнатуры, и вторая — непосредственно тело функции. Из-за особенностей языка (в которые я сейчас не буду углубляться) все аргументы перечисляются стрелочкой ->, последнее значение справа это результат функции. Например, если вы видите функцию foo :: Int -> Double -> String -> Bool, то эта функция которая называется foo и принимающая три аргумента: один целочисленный, один с плавающей запятой и один строковый, и возвращащий булевское значение.

Теперь попробуйте проверить себя, что за сигнатура у функции bar :: (Int -> Double) -> Int -> (String -> Bool)?

Ответ

Функция по имени bar принимает два аргумента: функцию Int -> Double и значение типа Int, и возвращает функцию String -> bool.

Rust-сигнатура: fn bar(f: impl Fn(i32) -> f64, v: i32) -> impl Fn(String) -> bool

C#-сигнатура: Func Bar(Func f, int v)

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

Теперь же, если вы видите

sqr x = x*x     -- обратите внимание на опущенные сигнатуры, они будут выведены
add x y = x + y -- Однако: FOR EXAMPLE PURPOSES ONLY!
add5_long x = add 5 x
add5 = add 5    -- как и в математике, иксы по обе части уравнения можно сократить, 
                -- поэтому add5 это сокращенная запись варианта add5_long. 
                -- Принцип схож с Method Groups в C#
                -- Официальное название такого приема - каррирование

main :: IO ()
main = putStrLn (show (add 10 (add5 (sqr 3))))

то это переводится как

fn sqr(x: i32) -> i32 { x*x }
fn add(x: i32, y: i32) -> i32 { x + y }
fn add5(x: i32) -> i32 { add(5, x) }

fn main() {
   println!("{}", ToString::to_string(add(10, add(5, sqr(3)))));                
}

Естественно, писать столько скобочек утомительно. Поэтому хаскеллисты придумали использовать символ $ для того чтобы им их заменять. Таким образом a $ b всего лишь означает a (b). Поэтому пример выше можно переписать так:

main = putStrLn $ show $ add 10 $ add5 $ sqr 3 -- ура! нет скобочек

С таким количество долларов в программах хаскеллистам была бы открыта дорога во все банки мира, но им это почему-то не понравилось. Поэтому они придумали писать точки. Оператор точка — это оператор композиции, и он определяется как f (g x) = (f . g) x. Например print (sqr 3) можно записать как (print . sqr) 3. Из функций «распечатай» и «возведи в квадрат» мы построили функцию «распечатай возведенный в квадрат аргумент», а потом передали ей значение 3. С его помощью пример выше будет выглядеть:

main = putStrLn . show . add 10 . add5 $ sqr 3

Стало намного чище, но заканчиваются ли на этом плюсы этого оператора? Как вы и догадались, ответ — нет, теперь благодаря этому мы можем вынести это все в отдельную функцию, придумать ей легкопроизносимое и очевидное имя и переиспользовать где-нибудь ещё:

-- функция прибавляет к аргументу 5, затем прибавляет 10, затем преобразует в строчку, затем выводит на экран
putStrLnShowAdd10Add5 = putStrLn . show . add 10 . add5
-- аналогичная запись putStrLnShowAdd10Add5 x = putStrLn . show . add 10 . add5 x
-- поэтому вычисление происходит справа налево (как, впрочем, и во всех языках)

main :: IO ()
main = putStrLnShowAdd10Add5 $ sqr 3

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

Мы узнали про ML синтаксис практически всё, чтобы читать произвольный Haskell код, остался последний рывок и с разговорником покончено

Последний рывок

main :: IO ()
main = 
  let maybe15 = do
      let just5 = Just 5    -- создаем объект типа Maybe с конструктором Just (см. первый пример) из начением 5
      let just10 = Just 10  -- то же самое с 10
      a <- just5            -- Пытаемся достать из него значение, если оно есть, то сохранить его в `a`.  если тут не будет значения то следующая строчка не выполнится!
      b <- just10           -- то же самое с `b`
      return $ a + b        -- если получилось, складываем числа. В противном случае вернется одна из веток выше провалила проверку на наличие значения и вернула Nothing
  in 
    print maybe15

Такая запись, область с выделением do-блока и использованием <- стрелочек, называется do-нотация, и она работает с любыми типами, являющимися монадой (не пугайтесь, это не страшно). На примере его использования с типом Maybe вы могли сразу узнать элвис-оператор (он же «Null condition operator»), позволяющий обрабатывать null-значения по цепочке, который возвращает null, если он не смог где-то получить значение. do-синтксис весьма-похож на него, но намного шире по возможностям.

Подумайте, где вы могли такое видеть? Оператор, который позволяет вам «раскрыть» значение, лежащее в некоемом контейнере (в данном случае Maybe, но может быть и любой другой, например Result, или как его называют в ФП языках — Either), а если не получилось, то прервать выполнение? Предлагаю вам немного подумать, стрелочка <- может вам казаться странной, но на самом деле вы это наверняка писали тысячу раз в своем любимом языке.

Ответ

А ведь это ни что иное, как общий случай async/await (я использую синтаксис C# т.к. в Rust async-await ещё не стабилизирован):

async ValueTask Maybe15() {
    var just5 = Task.FromResult(5);
    var just10 = Task.FromResult(10);
    int a = await just5; // если тут будет ошибка то следующая строчка не выполнится!
    int b = await just10;
    return a + b;
}

Console.WriteLine(Maybe15().ToString()) // выведет ожидаемое 15

Здесь я использую тип Task вместо Maybe, но даже по коду видно, как они похожи.
В целом, можно воспринимать do-нотацию как расширение async/await (который работает только с асинхронными контейнерами навроде Task) на тип любых контейнеров, где do — это «начало async-блока», а <- — это «авейт» (раскрытие содержимого контейнера). Частные случаи включают в себя Future/Option/Result/ List, и многие другие.

Магия C#

На самом деле в C# есть полноценная do-нотация, а не только ограниченный async/await для Task. И имя ему, барабанная дробь, LINQ-синтаксис. Да, многие давно про него забыли, кто-то наоборот знает про этот маленький трюк, но для полноты картины рассказать о нем точно не помешает. Если мы напишем пару хитрых методов расширения для Nullable, то переписать код с Haskell в таком случае можно буквально один в один (не прибегая к аналогии с Task). Вспомним, как оно выглядело (немного упрощу):

main :: IO ()
main = 
  let maybe15 = do
      a <- Just 5
      b <- Just 10
      return $ a + b 
  in 
    print maybe15

И теперь версия C#

int? maybe15 = from a in new int?(5)
               from b in new int?(10)
               select a + b;

Console.WriteLine(maybe15?.ToString() ?? "Nothing");

Вы видите разницу? Я — нет, за исключением того что haskell умеет выводить имя конструктора Nothing, а в C# это приходится делать самостоятельно.

Поиграться и посмотреть как же оно работает можно в заботливо подготовленном repl (для просмотра результатов программы прокрутите нижний див до конца). По ссылочке приложены также примеры работы с Result и Task. Как видите, работа с ними абсолютно идентична. Все контейнеры, с которыми можно работать подобным образом в ФП называются монадами (оказывается, это понятие не так уж страшно, правда?).

Ну, а тут можно посмотреть как то же самое выглядит на Haskell: https://repl.it/@Pzixel/ChiefLumpyDebugging

Итак, вступление уже изрядно затянулось, предлагаю перейти непосредственно к коду

Haskell

С чем сталкивается каждый начинающий хаскеллист сразу после установки языка? Правильно, IDE ничего не подсказывает

Примерно весь первый час после того как я решил начать с версии на хаскелле я настраивал окружение: устанавливал GHC (компилятор), Stack (сборщик и депенденси менеджер, похож на cargo или dotnet), IntelliJ-Haskell, и ждал установки всех зависимостей. Потом пришлось повозиться с идеей, но после очистки кешей и пары профилактических перезагрузок IDE все наладилось.

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

main :: IO ()
main = putStrLn "Hello, World!"

Ура, оно живое! Теперь начинаем с первого пункта, вывести дерево на экран. После непродолжительного гуглежа находим стандартный тип Data.Tree с прекрасным методом drawTree. Отлично, пишем, прям как написано в документации:

import Data.Tree

main :: IO ()
main = do
    let tree = Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]
    putStrLn . drawTree $ tree -- в этот момент я пошел гуглить, что такое точка и доллар.
                               -- результат моего расследования вы прочитали в предыдущей части

И получаем нашу первую ошибку:

    • No instance for (Num String) arising from the literal ‘1’
    • In the first argument of ‘Node’, namely ‘1’
      In the expression:
        Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]

Где-то секунд 30 я разглядывал её, потом подумал «при чем тут стринга?… Хм… А, наверное он может вывести только дерево строк», гуглю «haskell map convert to string», и по первой ссылке нахожу решение использовать map show. Что ж проверяем: меняем последнюю строчку на putStrLn . drawTree . fmap show $ tree, компилируем, и радуемся нарисованному дереву

Отлично, дерево мы рисовать научились, а как преобразовать его в дерево комменатриев?
Гуглим, как объявить структуры, и пишем метод загрузки комментария по номеру. Раз я пока не знаю, как писать сетевое взаимодействие, мы напишем метод-заглушку который возвращает какой-то константный комментарий. Т.к. я уже имел какой-то опыт Rust я знал, что в современных языках все асинхронные операции по АПИ похожи на Option — опциональный тип, поэтому решил сделать сделать возвращаемое значение метода-заглушки Maybe (местный Option), а потом, когда разберусь как делать HTTP запросы, заменю на нормальный асинк. А пока пусть возвращает вместо комментария число, преобразованное в строку.

Дописываем объявление структуры и метод-заглушку:

import Data.Tree

data Comment = Comment {
      title :: String
    , id  :: Int
    } deriving (Show)

getCommentById :: Int -> Maybe Comment
getCommentById i = Just $ Comment (show i) i

main :: IO ()
main = do
    let tree = Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]
    putStrLn . drawTree . fmap show $ tree

Все отлично, теперь нужно применить нашу функию-заглушку для каждого узла. На этом моменте я загуглил «haskell map maybe list» (потому что на практике знаю, что мап списка он ничем не отличается от мапа дерева, а загуглить будет проще), и второй ссылкой нашел ответ «Просто используйте mapM». Пробуем:

import Data.Tree
import Data.Maybe

data Comment = Comment {
      title :: String
    , id  :: Int
    } deriving (Show)

getCommentById :: Int -> Maybe Comment
getCommentById i = Just $ Comment (show i) i

main :: IO ()
main = do
    let tree = Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]
    putStrLn . drawTree . fmap show $ tree
    let commentsTree = mapM getCommentById tree
    putStrLn . drawTree . fmap show $ fromJust commentsTree

Получаем:

1
|
+- 2
|
`- 3
   |
   +- 4
   |
   `- 5
Comment {title = "1", id = 1}
|
+- Comment {title = "2", id = 2}
|
`- Comment {title = "3", id = 3}
   |
   +- Comment {title = "4", id = 4}
   |
   `- Comment {title = "5", id = 5}

Фух, вроде даже работает. Пришлось дополнительно добавить fromJust (аналогичен unwrap() в расте или Nullable.Value в C#, пытается развернуть значение, если там пусто, то бросает исключение), в остальном сделали все так, как написано по ссылке и получили вывод нашего дерева на экран.

После этого я немного застопорился, потому что я не понял, как делать асинхронные запросы и парсить JSON’ы.
К счастью, в чатике мне быстренько помогли и дали ссылки на wreq и местную либу для десериализации. Минут 15 я игрался с примерами после чего получил предварительно рабочий код:

{-# LANGUAGE DeriveGeneric #-}

import Data.Tree
import Data.Maybe
import Network.Wreq
import GHC.Generics
import Data.Aeson
import Control.Lens

data Comment = Comment {
      title :: String
    , id  :: Int
    } deriving (Generic, Show)

instance FromJSON Comment

getCommentById :: Int -> IO Comment
getCommentById i = do
  response <- get $ "https://jsonplaceholder.typicode.com/todos/" ++ show i
  let comment = decode (response ^. responseBody) :: Maybe Comment
  return $ fromJust comment

main :: IO ()
main = do
    let tree = Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]
    Prelude.putStrLn . drawTree . fmap show $ tree
    let commentsTree = mapM getCommentById tree
    Prelude.putStrLn . drawTree . fmap show $ fromJust commentsTree

И… Сначала ждем 20 минут, пока скачаются и соберутся все зависимости (привет, сборка reqwest в Rust), а затем получаем нашу вторую ошибку:

    * Couldn't match expected type `Maybe (Tree a0)'
                  with actual type `IO (Tree Comment)'
    * In the first argument of `fromJust', namely `commentsTree'
      In the second argument of `($)', namely `fromJust commentsTree'
      In a stmt of a 'do' block:
        putStrLn . drawTree . fmap show $ fromJust commentsTree
   |
28 |     Prelude.putStrLn . drawTree . fmap show $ fromJust commentsTree
   |                                                        ^^^^^^^^^^^^^

Ну да, мы же использовали fromJust чтобы сделать преобразование Maybe Tree → Tree, а теперь же у нас вместо заглушки настоящее IO происходит, которое и возвращает соответственно IO Tree вместо Maybe Tree. Как же достать значение? Как и прежде, обращаемся в гугл за этой информацией и получаем «используйте оператор <-» первой ссылкой. Пробуем:

main :: IO ()
main = do
    let tree = Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]
    Prelude.putStrLn . drawTree . fmap show $ tree
    commentsTree <- mapM getCommentById tree
    Prelude.putStrLn . drawTree . fmap show $ commentsTree

Ура, работает. Только медленно. Ах да, мы же забыли запараллелить.

Следующие минут 20 я гуглил, как распараллелить обход дерева. Находил всякие странные Concurrent-пакеты, какие-то стратегии обхода, ещё что-то. Но ищущий да обрящет, и в конце концов я наткнулся на async. В итоге параллельная версия потребовала некоторых монументальных изменений, но в конце концов все-таки заработала:

commentsTree <- mapConcurrently getCommentById tree

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

Примечание: последние несколько ссылкок в песочнице не собираются т.к. они требуют библиотек, создающих HTTP соединений, а repl.it их не разрешает. Желающие могут скачать и скомпилировать пример локально

На этом мой эксперимент с написанием на хаскелле завершается. Путем нехитрого гугла и интуиции от опыта работы с C# и Rust получилось меньше чем за час написать рабочую программу. Из них почти половину времени заняла просто установка 67 зависимостей веб-клиента. В принципе я был готов к этому, у reqwest в расте больше 100 зависимостей если мне не изменяет память, но все равно немного неприятно. Хорошо, что при последующей разработке все эти пакеты уже закэшированны локально и это был разовый оверхед на разворачивание окружения.

Простота параллелизации меня очень приятно удивила. А также я внезапно обнаружил, что я совершенно не использую тот факт, что у меня дерево. Ради эксперимента я решил поменять дерево на массив, и вот какие изменения мне пришлось внести:

main = do
    let tree = [1,2,3,4,5]
    print tree
    commentsTree <- mapConcurrently getCommentById tree
    print commentsTree

выводит

[1,2,3,4,5]
[Comment {title = "delectus aut autem", id = 1},Comment {title = "quis ut nam facilis et officia qui", id = 2},Comment {title = "fugiat veniam minus", id = 3},Comment {title = "et porro tempora", id = 4},Comment {title = "laboriosam mollitia et enim quasi adipisci quia provident illum", id = 5}]

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

Ну, хаскель оставил приятные впечатления, давайте перейдем к следующей части, go. Его синтаксис больше похож на привычные мне языки, поэтому мне не придется тратить время на параллельное изучение синтаксиса (как видите, для go не понадобилось делать словарика) и я смогу сразу написать код. Я морально смирился, что мне придется писать более топорно (например, придется реализовать два разных типа для деревьев идентификаторов и деревьев комментариев), зато я смогу воспользоваться всей мощью главной рекламной фичи го — горутинами!

Go

Сейчас го покажет, как нужно писать асинхронные программмы

Так как мы уже немного набили руку с предыдущим вариантом и знаем, что хотим получить в итоге, то просто открываем https://play.golang.org/ и пишем код.

Сначала гуглим, как в го создаются структуры. Затем, как их инициализировать. Через минуту первая программа на go готова:

package main

type intTree struct {
    id int
    children []intTree
}

func main() {
    tree := intTree{
        id: 1,
        children: []intTree {
            {
                id: 2,
                children: []intTree{

                },
            },
            {
                id: 3,
                children: []intTree{
                    {
                        id: 4,
                    },
                    {
                        id: 5,
                    },
                },
            },
        },
    }
}

Пытаемся скомпилировать — ошибка, tree declared and not used. Окей, в принципе я заранее знал, что го не разрешает иметь неиспользуемые переменные, переименовываем tree в _. Пробуем собрать, получаем ошибку no new variables on left side of :=. Ну, видимо нам даже проверить что мы не ошиблись в коде создания дерева не дадут, придется сразу дописывать форматирование и вывод на экран. Тратим ещё пару минут на то, чтобы узнать, как выводить форматирующую строкун, а экран и как сделать foreach цикл и дописываем необходимые функции:

func showIntTree(tree intTree) {
    showIntTreeInternal(tree, "")
}

func showIntTreeInternal(tree intTree, indent string) {
    fmt.Printf("%v%v\n", indent, tree.id)
    for _, child := range tree.children {
        showIntTreeInternal(child, indent + "  ")
    }
}

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

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

type comment struct {
    id int
    title string
}

type commentTree struct {
    value comment
    children []commentTree
}

func loadComments(node intTree) commentTree {
    result := commentTree{}
    for _, c := range node.children {
        result.children = append(result.children, loadComments(c))
    }
    result.value = getCommentById(node.id)
    return result
}

func getCommentById(id int) comment { 
    return comment{id:id, title:"Hello"} // наша заглушка в случае go
}

ну и конечно же дописать пару строчек кода для вывода дерева комментариев:

func showCommentsTree(tree commentTree) {
    showCommentsTreeInternal(tree, "")
}

func showCommentsTreeInternal(tree commentTree, indent string) {
    fmt.Printf("%v%v - %v\n", indent, tree.value.id, tree.value.title)
    for _, child := range tree.children {
        showCommentsTreeInternal(child, indent + "  ")
    }
}

С первой задачей мы почти справились, осталось только научиться получать реальные данные от веб-сервиса, и заменить заглушку на получение данных. Гуглим, как делать http запросы, гуглим, как десериализовывать JSON, и спустя ещё 5 минут дописываем следующее:

func getCommentById(i int) comment {
    result := &comment{}
    err := getJson("https://jsonplaceholder.typicode.com/todos/"+strconv.Itoa(i), result)
    if err != nil {
        panic(err) // для игрушечной задачи сойдет
    }
    return *result
}

func getJson(url string, target interface{}) error {
    var myClient = &http.Client{Timeout: 10 * time.Second}
    r, err := myClient.Get(url)
    if err != nil {
        return err
    }
    defer r.Body.Close()

    return json.NewDecoder(r.Body).Decode(target)
}

Запускаем, получаем

В этом момент я немного удивился. Вроде, все написано правильно, а результат некорректный. Надо разбираться.

Минут через 5 дебага и посматривания в документацию, стало понятно, что проблема в регистрозависимости десериализатора: распарсить {Title = "delectus aut autem", Id = 1} как cтруктуру id, title го не может. Заодно находим правила именования, что с маленькой буквы пишутся приватные члены, а с большой — публичные. В принципе, решений потенциальных два: первое — просто сделать поля публичными с большой буквы, второе — повесить специальные атрибуты чтобы указать имена, из которых нужно парсить.

Ну так как у нас простая DTO, поэтому просто делаем поля публичными, запускаем, все работает.

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

Тратим ещё минут 5, узнаем про вейтгруппы и go-нотацию. Пишем

func loadComments(root intTree) commentTree {
    var wg sync.WaitGroup
    result := loadCommentsInner(&wg, root)
    wg.Wait()
    return result
}

func loadCommentsInner(wg *sync.WaitGroup, node intTree) commentTree {
    result := commentTree{}
    wg.Add(1)
    for _, c := range node.children {
        result.children = append(result.children, loadCommentsInner(wg, c))
    }
    go func() {
        result.value = getCommentById(node.id)
        wg.Done()
    }()
    return result
}

И снова получаем

Эмм, ну, а теперь-то почему? Начинаем разбираться, ставим брейкпоинт на начало функции, проходим её. Становится понятно, что мы выходим из функции не дожидаясь результата, поэтому когда wg.Wait() на верхнем уровне дожидается сигнала от всех горутин, у него уже на руках есть сформированное пустое дерево, которое он и возвращает.

Окей, значит нам нужен какой-то способ вернуть значение после того, как функция вернулась. Опять обращаемся к поисковику, узнаем про каналы, учимся с ними работать, и ещё минут через 10 у нас готов следующий код:

func loadComments(root intTree) commentTree {
    ch := make(chan commentTree, 1)   // создаем канал
    var wg sync.WaitGroup             // создаем вейт группу
    wg.Add(1)                         // у неё будет один потомок
    loadCommentsInner(&wg, ch, root)  // грузим дерево
    wg.Wait()                         // дожидаемся результата
    result := <- ch                   // получаем значение из канала
    return result
}

func loadCommentsInner(wg *sync.WaitGroup, channel chan commentTree, node intTree) {
    ch := make(chan commentTree, len(node.children))  // создаем канал по количеству детей
    var childWg sync.WaitGroup                        // создаем вейт группу для детей
    childWg.Add(len(node.children))
    for _, c := range node.children {
        go loadCommentsInner(&childWg, ch, c)         // рекурсивно грузим детей в горутинах (параллельно)
    }
    result := commentTree{
        value: getCommentById(node.id),               // синхронно грузим себя
    }
    if len(node.children) > 0 {                       // если у нас есть дети, которых надо дождаться, то ждем их
        childWg.Wait()
        for value := range ch {                       // все дети сигнализировали об окончании работы, забираем у них результаты
            result.children = append(result.children, value)
        }
    }
    channel <- result                                 // отдаем результат в канал наверх
    wg.Done()                                         // сигнализируем родителю об окончании работы
}

Запускаем и… тишина. Ничего не происходит. Честно говоря, в этот момент я ощутил некоторое замешательство. Я слышал, что в го есть детектор дедлоков, раз он молчит, значит мы не залочились. То есть какая-то работа выполняется. Но какая?

Ещё минут 15 я расставлял ифчики, перестраивал код, добавлял/удалял вейтгруппы, тасовал каналы… Пока наконец не догадался заменить получение по HTTP на нашу изначальную заглушку:

func getCommentById(id int) comment {
    return comment{Id: id, Title: "Hello"}
}

После чего го выдал:

1
  2
  3
    4
    5
fatal error: all Goroutines are asleep - deadlock!

goroutine 1 [semacquire]:
sync.runtime_Semacquire(0xc00006e228)
    C:/go/src/runtime/sema.go:56 +0x49
sync.(*WaitGroup).Wait(0xc00006e220)
    C:/go/src/sync/waitgroup.go:130 +0x6b
main.loadCommentsInner(0xc00006e210, 0xc0000ce120, 0x1, 0xc000095f10, 0x2, 0x2)
    C:/Users/pzixe/go/src/hello/hello.go:47 +0x187
main.loadComments(0x1, 0xc000095f10, 0x2, 0x2, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0)
    C:/Users/pzixe/go/src/hello/hello.go:30 +0xec
main.main()
    C:/Users/pzixe/go/src/hello/hello.go:94 +0x14d

Ага, то есть все-таки дедлок происходит. Непонятно, почему ты раньше-то этого не сказал? Ведь получение данных по HTTP по идее не должно никак на тебя влиять, синхронная версия же работала как надо…

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

Строить ноды рекурсивно в узлах это плохо. Нужно создать всё дерево заранее, а потом дать ссылки на ноды каждой горутине, чтобы она в это общее для всех горутин место по нужному адресу перезаписало пустую структуру comment на полученную из JSON
Вызывать горутины рекурсивно тоже плохо. По опыту сишарпа я привык, что стартовать Task внутри други Task и аггрегация через WhenAny/WhenAll это совершенно нормальная операция. В го, судя по той информации, что мне сказали, это не так. Как я понял, там и планировщику плохо становится, и с производительностью наступает кирдык. То есть правильный сценарий использования — исключительно в роли веб-сервера а-ля
```
for httpRequest := range webserer.listen() {
    go handle(httpRequest)
} 
```
На практике никто не пишет по функции на каждый чих и go-way будет написать одну функцию printTree:
```
func printTree(tree interface{}) string {
    b, err := json.MarshalIndent(tree, "", "  ")
    if err != nil {
        panic(err)
    }
    return string(b)
}
```
Где interface {} — это аналог шарпового dynamic или тайпскриптового any, то есть локальное отключение всех проверок типов. Дальше с таким объектом надо работать либо через рефлексию, либо через даункаст к известному типу.
Но сериализация в JSON и вывод на экран немного читерский способ выполнить задачу, поэтому мы так делать не будем.

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

func loadComments(root intTree) commentTree {
    result := commentTree{}
    var wg sync.WaitGroup
    loadCommentsInner(&result, root, &wg)
    wg.Wait()
    return result
}

func loadCommentsInner(resNode *commentTree, node intTree, wg *sync.WaitGroup) {
    wg.Add(1)
    for _, res := range node.children {
        resNode.children = append(resNode.children, &commentTree{})
        loadCommentsInner(resNode.children[len(resNode.children)-1], res, wg)
    }
    resNode.value = getCommentById(node.id)
    wg.Done()
}

Что тут происходит? Ну, тут учтено первое замечание из списка рекомендаций «go-way»: мы изначально создаем пустое дерево, а потом начинаем заполнять его из разных горутин. У нас нет кучи вейтгруп на каждый узел дерева, есть одна единственная, куда каждая нода себя добавляет, и которую мы наверху ждем.

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

Ответ

Несмотря на то, что тут есть вейтгруппы и вот это все, код полностью синхронный.

Я обратил внимание в чате на эту проблему, после чего мы продолжили обдумывать разные варианты, и вскоре кто-то предложил вполне подходящее решение:

func loadComments(root intTree) commentTree {
    result := commentTree{}
    var wg sync.WaitGroup
    loadCommentsInner(&result, root, &wg)
    wg.Wait()
    return result
}

func loadCommentsInner(resNode *commentTree, node intTree, wg *sync.WaitGroup) {
    wg.Add(len(node.children))
    for _, res := range node.children {
        child := &commentTree{}
 
    
            © Habrahabr.ru