გასულ ზაფხულს მივიღე მონაწილეობა Google Summer of Code - პროგრამა Google-ის სტუდენტებისთვის. ყოველწლიურად, ორგანიზატორები ირჩევენ რამდენიმე ღია კოდის პროექტს, მათ შორის ისეთი ცნობილი ორგანიზაციებიდან, როგორიცაა Boost.org и Linux ფონდი. Google იწვევს სტუდენტებს მთელი მსოფლიოდან ამ პროექტებზე სამუშაოდ. 

როგორც Google Summer of Code 2019-ის მონაწილემ, გავაკეთე პროექტი ბიბლიოთეკის ფარგლებში ალგა ორგანიზაციასთან Haskell.org, რომელიც ავითარებს ჰასკელის ენას - ერთ-ერთ ყველაზე ცნობილ ფუნქციონალურ პროგრამირების ენას. ალგა არის ბიბლიოთეკა, რომელიც წარმოადგენს აკრიფეთ სეიფი გრაფიკების წარმოდგენა ჰასკელში. იგი გამოიყენება, მაგალითად, ქ სემანტიკური — Github ბიბლიოთეკა, რომელიც აშენებს სემანტიკურ ხეებს, ზარების და დამოკიდებულების გრაფიკებს კოდის საფუძველზე და შეუძლია მათი შედარება. ჩემი პროექტი იყო დაემატებინა ტიპის უსაფრთხო წარმოდგენა ორმხრივი გრაფიკებისთვის და ალგორითმები ამ წარმოდგენისთვის. 

ამ პოსტში მე ვისაუბრებ ჰასკელში ორმხრივობის გრაფიკის შესამოწმებლად ალგორითმის ჩემს განხორციელებაზე. მიუხედავად იმისა, რომ ალგორითმი ერთ-ერთი ყველაზე ძირითადია, მისი ლამაზად ფუნქციონალურ სტილში დანერგვამ რამდენიმე გამეორება დამჭირდა და საკმაოდ დიდი შრომა დამჭირდა. შედეგად, მე გადავწყვიტე განხორციელება მონადის ტრანსფორმატორებით. 

ჩემ შესახებ

მე მქვია ვასილი ალფეროვი, ვარ პეტერბურგის HSE-ის მეოთხე კურსის სტუდენტი. ადრე ბლოგზე დავწერე ჩემი პროექტის შესახებ პარამეტრიზებული ალგორითმების შესახებ и ZuriHac-ში მოგზაურობის შესახებ. ამჟამად სტაჟირებაზე ვარ ბერგენის უნივერსიტეტი ნორვეგიაში, სადაც ვმუშაობ პრობლემისადმი მიდგომებზე სია შეღებვა. ჩემს ინტერესებში შედის პარამეტრიზებული ალგორითმები და ფუნქციონალური პროგრამირება.

ალგორითმის განხორციელების შესახებ

წინასიტყვაობა

პროგრამაში მონაწილე სტუდენტებს ვურჩევთ ბლოგზე. მათ მომცეს ბლოგის პლატფორმა ჰასკელის ზაფხული. ეს სტატია არის თარგმანი მუხლი, ჩემს მიერ დაწერილი იქ ივლისში ინგლისურად, მოკლე წინასიტყვაობით. 

Pull Request მოცემული კოდით შეგიძლიათ იხილოთ აქ.

შეგიძლიათ წაიკითხოთ ჩემი მუშაობის შედეგების შესახებ (ინგლისურად) აქ.

ეს პოსტი მიზნად ისახავს მკითხველს გააცნოს ფუნქციური პროგრამირების ძირითადი ცნებები, თუმცა ვეცდები გავიხსენო ყველა გამოყენებული ტერმინი, როცა დრო მოვა.

გრაფიკების შემოწმება ორმხრივობაზე 

გრაფის ორმხრივობის შემოწმების ალგორითმი ჩვეულებრივ მოცემულია ალგორითმების კურსში, როგორც ერთ-ერთი უმარტივესი გრაფიკის ალგორითმი. მისი იდეა ცალსახაა: ჯერ რატომღაც ვათავსებთ წვეროებს მარცხენა ან მარჯვენა წილში და როდესაც აღმოვაჩენთ ურთიერთსაწინააღმდეგო კიდეს, ვამტკიცებთ, რომ გრაფიკი არ არის ორმხრივი.

ცოტა მეტი დეტალი: ჯერ მარცხენა წილში ჩავსვით რაღაც წვერო. ცხადია, ამ წვერის ყველა მეზობელი უნდა იყოს მარჯვენა წილში. გარდა ამისა, ამ წვეროს მეზობლების ყველა მეზობელი უნდა იყოს მარცხენა წილში და ა.შ. ჩვენ ვაგრძელებთ წილების მინიჭებას წვეროებზე მანამ, სანამ ჯერ კიდევ არის წვეროები იმ წვეროების დაკავშირებულ კომპონენტში, რომლითაც ჩვენ დავიწყეთ, რომლებსაც მეზობლები არ მივანიჭეთ. ჩვენ ვიმეორებთ ამ მოქმედებას ყველა დაკავშირებული კომპონენტისთვის.

თუ არსებობს ზღვარი წვეროებს შორის, რომლებიც ერთსა და იმავე დანაყოფში ხვდებიან, ძნელი არ არის გრაფაში უცნაური ციკლის პოვნა, რაც საყოველთაოდ ცნობილია (და სრულიად აშკარად) შეუძლებელია ორმხრივ გრაფაში. წინააღმდეგ შემთხვევაში, ჩვენ გვაქვს სწორი დანაყოფი, რაც ნიშნავს, რომ გრაფიკი ორმხრივია.

როგორც წესი, ეს ალგორითმი ხორციელდება გამოყენებით სიგანის პირველი ძიება ან სიღრმის პირველი ძიება. იმპერატიულ ენებში, სიღრმისეული ძიება ჩვეულებრივ გამოიყენება, რადგან ის ოდნავ მარტივია და არ საჭიროებს მონაცემთა დამატებით სტრუქტურებს. მე ასევე ავირჩიე სიღრმისეული ძიება, რადგან ეს უფრო ტრადიციულია.

ამრიგად, მივედით შემდეგ სქემამდე. ჩვენ ვკვეთთ გრაფის წვეროებს სიღრმე-პირველი ძიების გამოყენებით და ვანიჭებთ მათ წილებს, ვცვლით წილის რაოდენობას კიდეზე გადაადგილებისას. თუ ჩვენ ვცდილობთ წილის მინიჭებას წვეროზე, რომელსაც უკვე აქვს წილი მინიჭებული, თამამად შეგვიძლია ვთქვათ, რომ გრაფიკი არ არის ორმხრივი. იმ მომენტში, როდესაც ყველა წვეროს ენიჭება წილი და ჩვენ გადავხედეთ ყველა კიდეს, გვაქვს კარგი დანაყოფი.

გამოთვლების სისუფთავე

ჰასკელში ჩვენ ვვარაუდობთ, რომ ყველა გამოთვლა არის სუფთა. თუმცა, ეს რომ მართლაც ასე ყოფილიყო, ჩვენ არ გვექნებოდა საშუალება რაიმეს დაბეჭდვა ეკრანზე. Საერთოდ, სუფთა გამოთვლები იმდენად ზარმაცია, რომ არცერთი არ არის სუფთა რაიმეს გამოთვლის მიზეზები. პროგრამაში მომხდარი ყველა გამოთვლა რატომღაც იძულებულია "უწმინდური" მონადი IO.

მონადები არის გამოთვლების წარმოდგენის საშუალება ეფექტები ჰასკელში. იმის ახსნა, თუ როგორ მუშაობენ ისინი, სცილდება ამ პოსტის ფარგლებს. კარგი და მკაფიო აღწერა შეიძლება წაიკითხოთ ინგლისურად აქ.

აქვე მინდა აღვნიშნო, რომ მაშინ, როცა ზოგიერთი მონადა, როგორიცაა IO, დანერგილია კომპილერის მაგიის საშუალებით, თითქმის ყველა დანარჩენი დანერგილია პროგრამულ უზრუნველყოფაში და მათში არსებული ყველა გამოთვლა სუფთაა.

ბევრი ეფექტია და თითოეულს თავისი მონადა აქვს. ეს არის ძალიან ძლიერი და ლამაზი თეორია: ყველა მონადა ახორციელებს ერთსა და იმავე ინტერფეისს. ჩვენ ვისაუბრებთ შემდეგ სამ მონადაზე:

• ან ea არის გაანგარიშება, რომელიც აბრუნებს a ტიპის მნიშვნელობას ან აყენებს e ტიპის გამონაკლისს. ამ მონადის ქცევა ძალიან ჰგავს იმპერატიულ ენებში გამონაკლისების დამუშავებას: შეცდომების დაფიქსირება ან გადაცემა შესაძლებელია. მთავარი განსხვავება ისაა, რომ მონადა მთლიანად ლოგიკურად არის დანერგილი ჰასკელის სტანდარტულ ბიბლიოთეკაში, ხოლო იმპერატიული ენები ჩვეულებრივ იყენებენ ოპერაციული სისტემის მექანიზმებს.
• მდგომარეობა sa არის გამოთვლა, რომელიც აბრუნებს a ტიპის მნიშვნელობას და აქვს წვდომა s ტიპის ცვალებადი მდგომარეობაზე.
• შესაძლოა ა. შესაძლოა მონადა გამოხატავს გამოთვლას, რომელიც შეიძლება ნებისმიერ დროს შეწყდეს არაფრის დაბრუნებით. თუმცა, ჩვენ ვისაუბრებთ MonadPlus კლასის განხორციელებაზე Maybe ტიპისთვის, რომელიც გამოხატავს საპირისპირო ეფექტს: ეს არის გამოთვლა, რომელიც ნებისმიერ დროს შეიძლება შეწყდეს კონკრეტული მნიშვნელობის დაბრუნებით.

ალგორითმის განხორციელება

ჩვენ გვაქვს მონაცემთა ორი ტიპი, Graph a და Bigraph ab, რომელთაგან პირველი წარმოადგენს გრაფიკებს წვეროებით, რომლებიც მონიშნულია a ტიპის მნიშვნელობებით, ხოლო მეორე წარმოადგენს ორმხრივ გრაფიკებს მარცხენა მხარის წვეროებით, რომლებიც ეტიკეტირებულია a და მარჯვენა ტიპის მნიშვნელობებით. - გვერდითი წვეროები, რომლებიც ეტიკეტირებულია b ტიპის მნიშვნელობებით.

ეს არ არის ტიპები ალგას ბიბლიოთეკიდან. ალგას არ აქვს წარმოდგენა არამიმართული ორმხრივი გრაფიკებისთვის. მე გავაკეთე ასეთი ტიპები სიცხადისთვის.

ჩვენ ასევე დაგვჭირდება დამხმარე ფუნქციები შემდეგი ხელმოწერებით:

-- Список соседей данной вершины.
neighbours :: Ord a => a -> Graph a -> [a]

-- Построить двудольный граф по графу и функции, для каждой вершины
-- выдающей её долю и пометку в новой доле, игнорируя конфликтные рёбра.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
                                         -> Graph a
                                         -> Bigraph b c

-- Список вершин в графе
vertexList :: Ord a => Graph a -> [a]
Сигнатура функции, которую мы будем писать, выглядит так:

type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)

ადვილი მისახვედრია, რომ თუ პირველი სიღრმის ძიების დროს აღმოვაჩინეთ კონფლიქტური ზღვარი, კენტი ციკლი დევს რეკურსიის სტეკის თავზე. ამრიგად, მის აღსადგენად, ჩვენ უნდა გავწყვიტოთ ყველაფერი რეკურსიული დასტადან ბოლო წვერომდე პირველ გაჩენამდე.

ჩვენ ვახორციელებთ სიღრმის პირველ ძიებას თითოეული წვეროსთვის წილი ნომრების ასოციაციური მასივის შენარჩუნებით. რეკურსიული სტეკი ავტომატურად შენარჩუნდება ჩვენ მიერ არჩეული მონადის Functor კლასის განხორციელების გზით: ჩვენ მხოლოდ დაგვჭირდება ყველა წვეროს ჩასმა ბილიკიდან რეკურსიული ფუნქციიდან დაბრუნებულ შედეგში.

ჩემი პირველი იდეა იყო გამომეყენებინა ან მონადი, რომელიც, როგორც ჩანს, ახორციელებს ზუსტად იმ ეფექტებს, რაც ჩვენ გვჭირდება. პირველი განხორციელება, რომელიც დავწერე, ძალიან ახლოს იყო ამ ვარიანტთან. სინამდვილეში, მე მქონდა ხუთი განსხვავებული განხორციელება ერთ მომენტში და საბოლოოდ გადავწყვიტე მეორეზე.

პირველ რიგში, ჩვენ უნდა შევინარჩუნოთ აქციების იდენტიფიკატორების ასოციაციური მასივი - ეს არის რაღაც სახელმწიფოს შესახებ. მეორეც, ჩვენ უნდა შევძლოთ შეჩერება კონფლიქტის აღმოჩენისას. ეს შეიძლება იყოს ან Monad-ისთვის, ან MonadPlus შესაძლოა. მთავარი განსხვავება ისაა, რომ ან შეიძლება დააბრუნოს მნიშვნელობა, თუ გაანგარიშება არ შეჩერდა და შესაძლოა ამ შემთხვევაში მხოლოდ ამის შესახებ აბრუნებს ინფორმაციას. ვინაიდან ჩვენ არ გვჭირდება ცალკე მნიშვნელობა წარმატებისთვის (ის უკვე ინახება State-ში), ვირჩევთ შესაძლოა. და იმ მომენტში, როდესაც ჩვენ უნდა გავაერთიანოთ ორი მონადის ეფექტი, ისინი გამოდიან მონადის ტრანსფორმატორები, რომელიც ზუსტად აერთიანებს ამ ეფექტებს.

რატომ ავირჩიე ასეთი რთული ტიპი? ორი მიზეზი. ჯერ ერთი, განხორციელება ძალიან ჰგავს იმპერატივს. მეორეც, ჩვენ გვჭირდება მანიპულირება დაბრუნების მნიშვნელობით კონფლიქტის შემთხვევაში, როდესაც დავბრუნდებით კენტი მარყუჟის აღსადგენად, რაც ბევრად უფრო ადვილია Maybe მონადაში.

ამრიგად, ჩვენ ვიღებთ ამ განხორციელებას.

{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE ScopedTypeVariables #-}

data Part = LeftPart | RightPart

otherPart :: Part -> Part
otherPart LeftPart  = RightPart
otherPart RightPart = LeftPart

type PartMap a = Map.Map a Part
type OddCycle a = [a]

toEither :: Ord a => PartMap a -> a -> Either a a
toEither m v = case fromJust (v `Map.lookup` m) of
                    LeftPart  -> Left  v
                    RightPart -> Right v

type PartMonad a = MaybeT (State (PartMap a)) [a]

detectParts :: forall a. Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)
detectParts g = case runState (runMaybeT dfs) Map.empty of
                     (Just c, _)  -> Left  $ oddCycle c
                     (Nothing, m) -> Right $ toBipartiteWith (toEither m) g
    where
        inVertex :: Part -> a -> PartMonad a
        inVertex p v = ((:) v) <$> do modify $ Map.insert v p
                                      let q = otherPart p
                                      msum [ onEdge q u | u <- neigbours v g ]

        {-# INLINE onEdge #-}
        onEdge :: Part -> a -> PartMonad a
        onEdge p v = do m <- get
                        case v `Map.lookup` m of
                             Nothing -> inVertex p v
                             Just q  -> do guard (q /= p)
                                           return [v]

        processVertex :: a -> PartMonad a
        processVertex v = do m <- get
                             guard (v `Map.notMember` m)
                             inVertex LeftPart v

        dfs :: PartMonad a
        dfs = msum [ processVertex v | v <- vertexList g ]

        oddCycle :: [a] -> [a]
        oddCycle c = tail (dropWhile ((/=) last c) c)

სადაც ბლოკი არის ალგორითმის ბირთვი. შევეცდები აგიხსნათ რა ხდება მის შიგნით.

• inVertex არის სიღრმე-პირველი ძიების ნაწილი, სადაც პირველად ვეწვევით წვეროს. აქ ჩვენ მივანიჭებთ გაზიარების ნომერს წვეროზე და ვაწარმოებთ onEdge-ს ყველა მეზობელზე. აქ ასევე აღვადგენთ ზარის სტეკს: თუ msum დააბრუნებს მნიშვნელობას, ჩვენ ვაყენებთ v vertex-ს იქ.
• onEdge არის ნაწილი, სადაც ჩვენ ვეწვევით ზღვარს. მას ორჯერ ეძახიან თითოეულ კიდეზე. აქ ჩვენ ვამოწმებთ, არის თუ არა მონახულებული წვერო მეორე მხარეს, და ვესტუმრეთ მას, თუ არა. თუ მონახულებულია, ჩვენ ვამოწმებთ არის თუ არა ზღვარი კონფლიქტური. თუ ეს ასეა, ჩვენ ვაბრუნებთ მნიშვნელობას - რეკურსიის სტეკის ზედა ნაწილს, სადაც ყველა სხვა წვერო განთავსდება დაბრუნებისთანავე.
• processVertex ამოწმებს თითოეული წვეროსთვის, იყო თუ არა მისი მონახულება და აწარმოებს მასზე inVertex, თუ არა.
• dfs აწარმოებს processVertex-ს ყველა წვეროზე.

ეს ყველაფერი.

სიტყვა INLINE ისტორია

სიტყვა INLINE არ იყო ალგორითმის პირველ განხორციელებაში; ის მოგვიანებით გამოჩნდა. როდესაც ვცდილობდი უკეთესი იმპლემენტაციის პოვნას, აღმოვაჩინე, რომ არა INLINE ვერსია ზოგიერთ გრაფიკზე შესამჩნევად ნელი იყო. იმის გათვალისწინებით, რომ სემანტიკურად ფუნქციები ერთნაირად უნდა მუშაობდნენ, ამან ძალიან გამაკვირვა. კიდევ უფრო უცნაური, სხვა აპარატზე GHC-ის განსხვავებული ვერსიით, შესამჩნევი განსხვავება არ იყო.

GHC Core-ის გამომავალი ერთი კვირის გატარების შემდეგ, მე შევძელი პრობლემის გადაჭრა აშკარა INLINE-ის ერთი ხაზით. რაღაც მომენტში GHC 8.4.4 და GHC 8.6.5 შორის ოპტიმიზატორმა შეწყვიტა ამის გაკეთება თავისთავად.

არ ველოდი, რომ ჰასკელის პროგრამირებაში ასეთ ჭუჭყს შევხვდებოდი. თუმცა, დღესაც, ოპტიმიზატორები ხანდახან უშვებენ შეცდომებს და ჩვენი ამოცანაა მივცეთ მათ მინიშნებები. მაგალითად, აქ ჩვენ ვიცით, რომ ფუნქცია უნდა იყოს ჩასმული, რადგან ის ჩართულია იმპერატიულ ვერსიაში და ეს არის მიზეზი, რომ შემდგენელს მივცეთ მინიშნება.

Რა მოხდა შემდეგ?

შემდეგ ჰოპკროფტ-კარპის ალგორითმი სხვა მონადებთან ერთად განვახორციელე და ამით პროგრამა დასრულდა.

Google Summer of Code-ის წყალობით, შევიძინე პრაქტიკული გამოცდილება ფუნქციონალურ პროგრამირებაში, რაც დამეხმარა არამარტო სტაჟირების გავლა ჯეინის ქუჩაზე მომდევნო ზაფხულში (დარწმუნებული არ ვარ რამდენად ცნობილია ეს ადგილი Habr-ის მცოდნე აუდიტორიაშიც კი, მაგრამ ის ერთ-ერთია. იმ რამდენიმედან, სადაც შეგიძლიათ ზაფხულში ჩაერთოთ ფუნქციურ პროგრამირებაში), მაგრამ ასევე გამაცნო ამ პარადიგმის პრაქტიკაში გამოყენების მშვენიერი სამყარო, რომელიც მნიშვნელოვნად განსხვავდება ტრადიციულ ენებში ჩემი გამოცდილებისგან.

წყარო: www.habr.com