ZuriHac: øver sig i funktionel programmering

I juni i år, i den lille schweiziske by Rapperswil, hed en begivenhed ZuriHac. Denne gang samlede det mere end fem hundrede Haskell-elskere, fra begyndere til sprogets grundlæggere. Selvom arrangørerne kalder dette arrangement for et hackathon, er det ikke en konference eller et hackathon i klassisk forstand. Dens format er anderledes end traditionelle programmører. Vi lærte om ZuriHac ved held, tog del i det, og nu betragter vi det som vores pligt at fortælle om det usædvanlige fund!

Om os

Denne artikel er udarbejdet af to 3. års studerende på programmet "Anvendt matematik og informatik" ved National Research University Higher School of Economics - St. Petersburg: Vasily Alferov og Elizaveta Vasilenko. Passionen for funktionel programmering for os begge begyndte med en række forelæsninger af D. N. Moskvin på 2. år på universitetet. Vasily deltager i øjeblikket i Google Summer of Code-programmet, inden for hvilket han implementerer algebraiske grafer i Haskell under vejledning af projektteamet Alga. Elizaveta anvendte de erhvervede funktionelle programmeringsfærdigheder i kursusarbejde dedikeret til implementeringen af ​​anti-foreningsalgoritmen med efterfølgende anvendelse i typeteori.

Hændelsesformat

Målgruppen er ejere af open source-projekter, programmører, der ønsker at deltage i deres udvikling, funktionelle programmeringsforskere og folk, der simpelthen brænder for Haskell. I år var udviklere fra mere end halvtreds open source Haskell-projekter fra hele verden samlet på stedet - HSR Hochschule für Technik Rapperswil - for at tale om deres produkter og få friske mennesker til at interessere sig for deres udvikling.

Foto fra Twitter ZuriHac

Ordningen er meget enkel: Du skal på forhånd skrive et par forslag om dit projekt og sende dem til arrangørerne, som vil lægge information om dit projekt op på begivenhedssiden. Desuden har forfatterne til projekterne på den første dag tredive sekunder til meget kort at fortælle fra scenen, hvad de laver, og hvad der skal gøres. Så leder interesserede efter forfatterne og spørger i detaljer om opgaverne.

Vi har ikke vores egne åbne projekter endnu, men vi vil rigtig gerne bidrage til eksisterende, så vi tilmeldte os som faste deltagere. I løbet af tre dage arbejdede vi med to grupper af udviklere. Det viser sig, at fælles undersøgelse af kode og live kommunikation gør interaktionen mellem projektforfattere og bidragydere meget produktive - hos ZuriHac var vi i stand til at forstå områder, der var nye for os, og var i stand til at hjælpe to helt forskellige teams, der fuldførte en opgave i hver af projekterne.

Ud over værdifuld praksis blev der også holdt adskillige foredrag og masterclasses på ZuriHac. Vi husker især to foredrag. Ved den første af dem talte Andrey Mokhov fra University of Newcastle om selektive applikative funktorer - en klasse af typer, der skulle blive mellemliggende mellem applikative funktorer og monader. I et andet foredrag talte en af ​​grundlæggerne af Haskell, Simon Peyton Jones, om, hvordan typeinferens fungerer i GHC-kompileren.

Foredrag af Simon Peyton Jones. Foto fra Twitter ZuriHac

Masterklasserne afholdt under hackathonet blev opdelt i tre kategorier afhængigt af deltagernes træningsniveau. De opgaver, der blev tilbudt deltagere, der deltog i udviklingen af ​​projekter, var også mærket med en sværhedsgrad. Det lille, men venlige fællesskab af funktionelle programmører byder gladeligt nytilkomne velkommen i sine rækker. For at forstå forelæsningerne af Andrei Mokhov og Simon Peyton Jones var det funktionelle programmeringskursus, vi tog på universitetet, dog meget nyttigt.

Tilmelding til arrangementet er gratis for både faste deltagere og projektforfattere. Vi indsendte ansøgninger om deltagelse i starten af ​​juni, hvorefter vi hurtigt blev flyttet fra ventelisten til listen over bekræftede deltagere.

Og nu vil vi tale om de projekter i udviklingen, som vi deltog i.

Pandoc

Pandoc er en universel konverter af tekstdokumenter, faktisk fra ethvert format til ethvert. For eksempel fra docx til pdf eller fra Markdown til MediaWiki. Dens forfatter, John MacFarlane, er professor i filosofi ved University of California, Berkeley. Generelt er Pandoc ret berømt, og nogle af vores venner blev overraskede, da de fandt ud af, at Pandoc var skrevet i Haskell.

Liste over dokumentformater understøttet af Pandoc. Der er også en hel graf på siden, men dette billede passer ikke ind i artiklen.

Selvfølgelig giver Pandoc ikke direkte konvertering for hvert par formater. For at understøtte en så bred vifte af transformationer bruges en standard arkitektonisk løsning: Først oversættes hele dokumentet til en speciel intern mellemrepræsentation, og derefter genereres et dokument i et andet format ud fra denne interne repræsentation. Udviklerne kalder den interne repræsentation "AST", som står for abstrakt syntakstræ, eller abstrakt syntakstræ. Du kan se på den mellemliggende repræsentation meget enkelt: alt du skal gøre er at indstille outputformatet til "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æsere, der har arbejdet med Haskell i det mindste lidt, kan allerede ud fra dette lille eksempel antage, at Pandoc er skrevet i Haskell: outputtet af denne kommando er en strengrepræsentation af Pandocs interne strukturer, skabt i lighed med, hvordan det normalt gøres. i Haskell, for eksempel i standardbiblioteket.

Så her kan du se, at den interne repræsentation er en rekursiv struktur, i hver intern node, som der er en liste over. For eksempel er der på det øverste niveau en liste over et element - det første niveaus overskrift med attributterne "hello-world",[],[]. Gemt inde i denne overskrift er en liste over strengen "Hej", efterfulgt af et mellemrum og strengen "Verden!".

Som du kan se, er den interne repræsentation ikke meget anderledes end HTML. Det er et træ, hvor hver intern node giver nogle oplysninger om formateringen af ​​dens efterkommere, og bladene indeholder det faktiske indhold af dokumentet.

Hvis vi går ned til implementeringsniveauet, er datatypen for hele dokumentet defineret således:

data Pandoc = Pandoc Meta [Block]

Her er Block netop de interne toppunkter nævnt ovenfor, og Meta er metainformation om dokumentet, såsom titel, oprettelsesdato, forfattere - dette er forskelligt for forskellige formater, og Pandoc forsøger, hvis det er muligt, at bevare sådanne informationer, når man oversætter fra format til format.

Næsten alle konstruktører af typen Blok - for eksempel Header eller Para (afsnit) - tager attributter og en liste over hjørnepunkter på lavere niveau som argumenter - Inline, som regel. For eksempel er Space eller Str konstruktører af typen Inline, og HTML-tagget bliver også til sin egen specielle Inline. Vi ser ingen mening i at give en fuldstændig definition af disse typer, men bemærk, at den kan findes her her.

Interessant nok er typen Pandoc en monoid. Det betyder, at der er en form for tomt dokument, og at dokumenter kan stables sammen. Dette er praktisk at bruge, når du skriver læsere - du kan opdele et dokument i dele ved hjælp af vilkårlig logik, parse hver enkelt separat og derefter sætte alt sammen i et dokument. I dette tilfælde vil metainformation blive indsamlet fra alle dele af dokumentet på én gang.

Når man konverterer, f.eks. fra LaTeX til HTML, konverterer først et særligt modul kaldet LaTeXReader inputdokumentet til AST, derefter konverterer et andet modul kaldet HTMLWriter AST til HTML. Takket være denne arkitektur er der ingen grund til at skrive et kvadratisk antal konverteringer - det er nok at skrive Reader og Writer for hvert nyt format, og alle mulige par af konverteringer vil automatisk blive understøttet.

Det er klart, at en sådan arkitektur også har sine ulemper, længe forudsagt af eksperter inden for softwarearkitektur. Det vigtigste er omkostningerne ved at lave ændringer i syntakstræet. Hvis ændringen er alvorlig nok, bliver du nødt til at ændre koden i alle læsere og forfattere. For eksempel er en af ​​udfordringerne for Pandoc-udviklere at understøtte komplekse tabelformater. Nu kan Pandoc kun lave meget simple tabeller, med en overskrift, kolonner og en værdi i hver celle. For eksempel vil colspan-attributten i HTML simpelthen blive ignoreret. En af grundene til denne adfærd er manglen på et samlet skema til at repræsentere tabeller i alle eller i det mindste mange formater - derfor er det uklart i hvilken form tabellerne skal gemmes i den interne repræsentation. Men selv efter at have valgt en specifik visning, bliver du nødt til at ændre absolut alle læsere og forfattere, der understøtter arbejde med tabeller.

Haskell-sproget blev ikke kun valgt på grund af forfatternes store kærlighed til funktionel programmering. Haskell er kendt for sine omfattende tekstbehandlingsmuligheder. Et eksempel er biblioteket parsec er et bibliotek, der aktivt bruger begreberne funktionel programmering - monoider, monader, applikative og alternative funktorer - til at skrive vilkårlige parsere. Den fulde kraft af Parsec kan ses i eksempel fra HaskellWiki, hvor en komplet parser af et simpelt imperativt programmeringssprog analyseres. Parsec bruges selvfølgelig også aktivt i Pandoc.

Kort beskrevet bruges monader til sekventiel parsing, når én ting kommer først, og så en anden. For eksempel i dette eksempel:

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

Først skal du tælle mellemrummet, og derefter sætningen - som også har typen Parser Stmt.

Alternative funktorer bruges til at rulle tilbage, hvis parsing mislykkes. For eksempel,

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

Betyder, at du enten skal prøve at læse udsagnet i parentes eller prøve at læse flere udsagn i rækkefølge.

Applikative funktorer bruges primært som genveje til monader. Lad for eksempel tok-funktionen læse et eller andet token (dette er en rigtig funktion fra LaTeXReader). Lad os se på denne kombination

const <$> tok <*> tok

Den vil læse to tokens i træk og returnere den første.

For alle disse klasser har Haskell smukke symbolske operatorer, som får Reader-programmering til at ligne ASCII-kunst. Bare beundre denne vidunderlige kode.

Vores opgaver var relateret til LaTeXReader. Vasilys opgave var at understøtte mbox- og hbox-kommandoerne, nyttige til at skrive pakker i LaTeX. Elizabeth var ansvarlig for at understøtte epigraph-kommandoen, som giver dig mulighed for at oprette epigrafer i LaTeX-dokumenter.

Hatrace

UNIX-lignende operativsystemer implementerer ofte ptrace-systemkaldet. Det er nyttigt til fejlfinding og simulering af programmiljøer, så du kan spore de systemkald, som programmet foretager. For eksempel bruger det meget nyttige strace-værktøj ptrace internt.

Hatrace er et bibliotek, der giver en grænseflade til ptrace i Haskell. Faktum er, at ptrace i sig selv er meget sofistikeret, og det er ret svært at bruge det direkte, især fra funktionelle sprog.

Hatrace kører som strace ved opstart og accepterer lignende argumenter. Det adskiller sig fra strace ved, at det også er et bibliotek, der giver en enklere grænseflade end blot ptrace.

Ved hjælp af hatrace har vi allerede fanget en ubehagelig fejl i GHC Haskell-kompileren - bliver dræbt på det forkerte tidspunkt, genererer den forkerte objektfiler og genkompilerer dem ikke, når den genstartes. Scripting ved hjælp af systemkald gjorde det muligt pålideligt at gengive fejlen i én kørsel, mens tilfældige dræb reproducerede fejlen på omkring to timer.

Vi tilføjede systemopkaldsgrænseflader til biblioteket - Elizaveta tilføjede brk, og Vasily tilføjede mmap. Baseret på resultaterne af vores arbejde er det muligt mere enkelt og præcist at bruge disse systemkalds argumenter, når du bruger biblioteket.

Kilde: www.habr.com