ZuriHac: öva på funktionell programmering

I juni i år, i den lilla schweiziska staden Rapperswil, kallas ett evenemang ZuriHac. Den här gången samlade det mer än femhundra Haskell-älskare, från nybörjare till språkets grundare. Även om arrangörerna kallar detta evenemang för ett hackathon är det inte en konferens eller ett hackathon i klassisk mening. Dess format skiljer sig från traditionella programmerare. Vi lärde oss om ZuriHac av tur, deltog i det, och nu anser vi att det är vår plikt att berätta om det ovanliga fyndet!

om oss

Den här artikeln förbereddes av två tredjeårsstudenter på programmet "Applied Mathematics and Informatics" vid National Research University Higher School of Economics - St. Petersburg: Vasily Alferov och Elizaveta Vasilenko. Passionen för funktionell programmering för oss båda började med en serie föreläsningar av D. N. Moskvin på 3:a året på universitetet. Vasily deltar för närvarande i Google Summer of Code-programmet, inom vilket han implementerar algebraiska grafer i Haskell under ledning av projektteamet Alg. Elizaveta tillämpade de förvärvade funktionella programmeringsfärdigheterna i kursarbete ägnat åt implementeringen av anti-unifieringsalgoritmen med efterföljande tillämpning i typteori.

Händelseformat

Målgruppen är ägare av projekt med öppen källkod, programmerare som vill delta i deras utveckling, forskare inom funktionell programmering och människor som helt enkelt brinner för Haskell. I år samlades utvecklare från mer än femtio Haskell-projekt med öppen källkod från hela världen på platsen - HSR Hochschule für Technik Rapperswil - för att prata om sina produkter och få fräscha människor intresserade av deras utveckling.

Bild från Twitter ZuriHac

Schemat är väldigt enkelt: du måste skriva några förslag om ditt projekt i förväg och skicka dem till arrangörerna, som kommer att lägga upp information om ditt projekt på evenemangssidan. Dessutom har författarna till projekten den första dagen trettio sekunder på sig att mycket kortfattat från scenen berätta vad de gör och vad som behöver göras. Sedan letar intresserade efter författarna och frågar i detalj om uppgifterna.

Vi har inga egna öppna projekt än, men vi vill verkligen bidra till befintliga, så vi registrerade oss som vanliga deltagare. Under tre dagar arbetade vi med två grupper av utvecklare. Det visar sig att gemensamma studier av kod och livekommunikation gör interaktionen mellan projektförfattare och bidragsgivare mycket produktiv - på ZuriHac kunde vi förstå områden som var nya för oss och kunde hjälpa två helt olika team, och slutföra en uppgift i varje av projekten.

Förutom värdefull övning gavs även flera föreläsningar och masterclasses på ZuriHac. Vi minns särskilt två föreläsningar. Vid den första av dem talade Andrey Mokhov från University of Newcastle om selektiva applikativa funktorer – en klass av typer som borde bli mellanliggande mellan applikativa funktorer och monader. I en annan föreläsning pratade en av Haskells grundare, Simon Peyton Jones, om hur typinferens fungerar i GHC-kompilatorn.

Föreläsning av Simon Peyton Jones. Bild från Twitter ZuriHac

Masterklasserna som hölls under hackathonet var indelade i tre kategorier beroende på deltagarnas träningsnivå. De uppgifter som erbjöds deltagare som deltog i utvecklingen av projekt var också märkta med en svårighetsgrad. Den lilla men vänliga gruppen av funktionella programmerare välkomnar med glädje nykomlingar i sina led. För att förstå föreläsningarna av Andrei Mokhov och Simon Peyton Jones var dock kursen i funktionell programmering vi tog på universitetet mycket användbar.

Anmälan till evenemanget är gratis för både vanliga deltagare och projektförfattare. Vi lämnade in ansökningar om deltagande i början av juni, varefter vi snabbt flyttades från väntelistan till listan över bekräftade deltagare.

Och nu ska vi prata om de projekt i utvecklingen som vi deltog i.

Pandoc

Pandoc är en universell omvandlare av textdokument, faktiskt från vilket format som helst till vilket som helst. Till exempel från docx till pdf, eller från Markdown till MediaWiki. Dess författare, John MacFarlane, är professor i filosofi vid University of California, Berkeley. I allmänhet är Pandoc ganska känd, och några av våra vänner blev förvånade när de fick veta att Pandoc skrevs i Haskell.

Lista över dokumentformat som stöds av Pandoc. Det finns också en hel graf på sajten, men den här bilden passar inte in i artikeln.

Naturligtvis tillhandahåller Pandoc inte direkt konvertering för varje par format. För att stödja en sådan mängd olika transformationer används en standardarkitektonisk lösning: först översätts hela dokumentet till en speciell intern mellanrepresentation, och sedan genereras ett dokument i ett annat format från denna interna representation. Utvecklarna kallar den interna representationen "AST", som står för abstrakt syntaxträd, eller abstrakt syntaxträd. Du kan titta på den mellanliggande representationen mycket enkelt: allt du behöver göra är att ställa in utdataformatet till "native"

$ cat example.html
<h1>Hello, World!</h1>

$ pandoc -f html -t native example.html
[Header 1 ("hello-world",[],[]) [Str "Hello,",Space,Str "World!"]]

Läsare som har arbetat med Haskell åtminstone lite kan redan från detta lilla exempel anta att Pandoc är skrivet i Haskell: resultatet av detta kommando är en strängrepresentation av Pandocs interna strukturer, skapad i likhet med hur det vanligtvis görs i Haskell, till exempel i standardbiblioteket.

Så här kan du se att den interna representationen är en rekursiv struktur, i varje intern nod som det finns en lista över. Till exempel, på den översta nivån finns det en lista med ett element - den första nivåns rubrik med attributen "hello-world",[],[]. Gömd inuti den här rubriken finns en lista med strängen "Hello", följt av ett mellanslag och strängen "World!".

Som du kan se är den interna representationen inte mycket annorlunda än HTML. Det är ett träd där varje intern nod ger lite information om formateringen av dess avkomlingar, och bladen innehåller det faktiska innehållet i dokumentet.

Om vi ​​går ner till implementeringsnivån definieras datatypen för hela dokumentet så här:

data Pandoc = Pandoc Meta [Block]

Här är Block just de interna hörn som nämns ovan, och Meta är metainformation om dokumentet, såsom titel, skapelsedatum, författare - detta är olika för olika format, och Pandoc försöker om möjligt att bevara sådan information vid översättning från format till formatera.

Nästan alla konstruktörer av typen Block - till exempel Header eller Para (stycke) - tar attribut och en lista med hörn på lägre nivå som argument - Inline, som regel. Till exempel är Space eller Str konstruktörer av typen Inline, och HTML-taggen förvandlas också till sin egen speciella Inline. Vi ser ingen mening med att ge en fullständig definition av dessa typer, men notera att den finns här här.

Intressant nog är typen Pandoc en monoid. Det betyder att det finns någon form av tomt dokument, och att dokument kan staplas ihop. Detta är bekvämt att använda när du skriver läsare - du kan dela upp ett dokument i delar med godtycklig logik, analysera var och en separat och sedan sätta ihop allt till ett dokument. I det här fallet kommer metainformation att samlas in från alla delar av dokumentet på en gång.

När man konverterar, säg, från LaTeX till HTML, konverterar först en speciell modul som heter LaTeXReader inmatningsdokumentet till AST, sedan konverterar en annan modul som heter HTMLWriter AST till HTML. Tack vare denna arkitektur finns det inget behov av att skriva ett kvadratiskt antal konverteringar - det räcker att skriva Reader och Writer för varje nytt format, och alla möjliga par av konverteringar kommer att stödjas automatiskt.

Det är tydligt att en sådan arkitektur också har sina nackdelar, som länge förutspåtts av experter inom området mjukvaruarkitektur. Den mest betydande är kostnaden för att göra ändringar i syntaxträdet. Om förändringen är tillräckligt allvarlig måste du ändra koden i alla läsare och skribenter. Till exempel är en av utmaningarna som Pandoc-utvecklare står inför att stödja komplexa tabellformat. Nu kan Pandoc bara skapa mycket enkla tabeller, med en rubrik, kolumner och ett värde i varje cell. Till exempel kommer attributet colspan i HTML helt enkelt att ignoreras. En av anledningarna till detta beteende är avsaknaden av ett enhetligt schema för att representera tabeller i alla eller åtminstone många format - följaktligen är det oklart i vilken form tabellerna ska lagras i den interna representationen. Men även efter att ha valt en specifik vy måste du ändra absolut alla läsare och skribenter som stöder arbete med tabeller.

Haskell-språket valdes inte bara på grund av författarnas stora kärlek till funktionell programmering. Haskell är känt för sina omfattande textbehandlingsmöjligheter. Ett exempel är biblioteket parsec är ett bibliotek som aktivt använder begreppen funktionell programmering - monoider, monader, applikativa och alternativa funktorer - för att skriva godtyckliga parsers. Parsecs fulla kraft kan ses i exempel från HaskellWiki, där en komplett analys av ett enkelt imperativt programmeringsspråk analyseras. Naturligtvis används Parsec aktivt även i Pandoc.

Kort beskrivet, monader används för sekventiell analys, när en sak kommer först och sedan en annan. Till exempel, i det här exemplet:

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

Först måste du räkna utrymmet, och sedan uttalandet - som också har typen Parser Stmt.

Alternativa funktorer används för att återställa om analysen misslyckas. Till exempel,

statement :: Parser Stmt
statement = parens statement <|> sequenceOfStmt

Det betyder att du antingen måste försöka läsa påståendet inom parentes, eller försöka läsa flera påståenden i följd.

Applikativa funktorer används främst som genvägar för monader. Till exempel, låt tok-funktionen läsa någon token (detta är en riktig funktion från LaTeXReader). Låt oss titta på denna kombination

const <$> tok <*> tok

Den kommer att läsa två tokens i rad och returnera den första.

För alla dessa klasser har Haskell vackra symboliska operatorer, vilket gör att Reader-programmering ser ut som ASCII-konst. Bara beundra denna underbara kod.

Våra uppgifter var relaterade till LaTeXReader. Vasilys uppgift var att stödja kommandona mbox och hbox, användbara för att skriva paket i LaTeX. Elizabeth var ansvarig för att stödja epigrafkommandot, som låter dig skapa epigrafer i LaTeX-dokument.

Hatrace

UNIX-liknande operativsystem implementerar ofta systemanropet ptrace. Det är användbart vid felsökning och simulering av programmiljöer, vilket gör att du kan spåra systemanrop som programmet gör. Till exempel använder det mycket användbara strace-verktyget ptrace internt.

Hatrace är ett bibliotek som tillhandahåller ett gränssnitt för ptrace i Haskell. Faktum är att ptrace i sig är väldigt sofistikerat och det är ganska svårt att använda det direkt, särskilt från funktionella språk.

Hatrace körs som strace vid start och accepterar liknande argument. Det skiljer sig från strace genom att det också är ett bibliotek som ger ett enklare gränssnitt än bara ptrace.

Med hjälp av hatrace har vi redan fångat en obehaglig bugg i GHC Haskell-kompilatorn - om den dödas i fel ögonblick genererar den felaktiga objektfiler och kompilerar dem inte om när den startas om. Skriptning av systemanrop gjorde det möjligt att tillförlitligt återskapa felet i en körning, medan slumpmässiga dödar återskapade felet på cirka två timmar.

Vi lade till systemanropsgränssnitt till biblioteket - Elizaveta lade till brk och Vasily lade till mmap. Baserat på resultatet av vårt arbete är det möjligt att enklare och mer exakt använda argumenten för dessa systemanrop när du använder biblioteket.

Källa: will.com