ZuriHac: pràctica de programació funcional

El juny d'aquest any, a la petita ciutat suïssa de Rapperswil, es va convocar un esdeveniment ZuriHac. Aquesta vegada va reunir més de cinc-cents amants de l'Haskell, des de principiants fins als pares fundadors de la llengua. Tot i que els organitzadors anomenen aquest esdeveniment un hackathon, no és una conferència o un hackathon en el sentit clàssic. El seu format és diferent dels programadors tradicionals. Vam aprendre de ZuriHac per sort, vam participar-hi i ara considerem que és el nostre deure explicar-ne la insòlita troballa!

sobre nosaltres

Aquest article va ser preparat per dos estudiants de 3r curs del programa "Matemàtiques i Informàtica Aplicades" de la National Research University Higher School of Economics - Sant Petersburg: Vasily Alferov i Elizaveta Vasilenko. La passió per la programació funcional per a tots dos va començar amb una sèrie de conferències de D. N. Moskvin a 2n curs d'universitat. Actualment, Vasily està participant en el programa Google Summer of Code, dins del qual està implementant gràfics algebraics a Haskell sota la direcció de l'equip del projecte. Alga. Elizaveta va aplicar les habilitats de programació funcional adquirides en el treball del curs dedicat a la implementació de l'algorisme anti-unificació amb la posterior aplicació en la teoria de tipus.

Format d'esdeveniment

El públic objectiu són propietaris de projectes de codi obert, programadors que volen participar en el seu desenvolupament, investigadors de programació funcional i persones simplement apassionades per Haskell. Aquest any, els desenvolupadors de més de cinquanta projectes Haskell de codi obert d'arreu del món es van reunir al lloc, la HSR Hochschule für Technik Rapperswil, per parlar dels seus productes i fer que gent fresca s'interessi pel seu desenvolupament.

Foto de Twitter ZuriHac

L'esquema és molt senzill: heu d'escriure algunes propostes sobre el vostre projecte amb antelació i enviar-les als organitzadors, que publicaran informació sobre el vostre projecte a la pàgina de l'esdeveniment. A més, el primer dia, els autors dels projectes disposen de trenta segons per explicar molt breument des de l'escenari què estan fent i què cal fer. Després, les persones interessades busquen els autors i pregunten detalladament sobre les tasques.

Encara no tenim els nostres propis projectes oberts, però realment volem contribuir als ja existents, així que ens vam registrar com a participants habituals. Durant tres dies, vam treballar amb dos grups de desenvolupadors. Resulta que l'estudi conjunt del codi i la comunicació en directe fa que la interacció entre els autors del projecte i els col·laboradors sigui molt productiva: a ZuriHac vam poder entendre àrees que eren noves per a nosaltres i vam poder ajudar dos equips completament diferents, completant una tasca en cadascun. dels projectes.

A més d'una pràctica valuosa, també es van oferir diverses conferències i classes magistrals a ZuriHac. Recordem especialment dues conferències. En el primer d'ells, Andrey Mokhov, de la Universitat de Newcastle, va parlar sobre els funtors aplicatius selectius, una classe de tipus que haurien de convertir-se en intermedis entre els funtors aplicatius i les mónades. En una altra conferència, un dels fundadors de Haskell, Simon Peyton Jones, va parlar sobre com funciona la inferència de tipus al compilador GHC.

Conferència de Simon Peyton Jones. Foto de Twitter ZuriHac

Les classes magistrals realitzades durant l'hackathon es van dividir en tres categories en funció del nivell de formació dels participants. Les tasques que s'oferien als participants que s'incorporaven al desenvolupament dels projectes també estaven marcades amb un nivell de dificultat. La petita però amigable comunitat de programadors funcionals dóna la benvinguda als nouvinguts a les seves files. Per entendre les conferències d'Andrei Mokhov i Simon Peyton Jones, però, el curs de programació funcional que vam fer a la universitat va ser molt útil.

La inscripció a l'esdeveniment és gratuïta tant per als participants habituals com per als autors del projecte. Vam presentar sol·licituds de participació a principis de juny, després de la qual cosa ens van traslladar ràpidament de la llista d'espera a la llista de participants confirmats.

I ara parlarem dels projectes en el desenvolupament dels quals hem participat.

Pandoc

Pandoc és un convertidor universal de documents de text, de fet, de qualsevol format a qualsevol. Per exemple, de docx a pdf, o de Markdown a MediaWiki. El seu autor, John MacFarlane, és professor de filosofia a la Universitat de Califòrnia, Berkeley. En general, Pandoc és bastant famós, i alguns dels nostres amics es van sorprendre quan van saber que Pandoc estava escrit en Haskell.

Llista de formats de documents suportats per Pandoc. També hi ha un gràfic sencer al lloc, però aquesta imatge no encaixa a l'article.

Per descomptat, Pandoc no proporciona conversió directa per a cada parell de formats. Per donar suport a una varietat tan àmplia de transformacions, s'utilitza una solució arquitectònica estàndard: primer, tot el document es tradueix a una representació intermèdia interna especial i després es genera un document en un format diferent a partir d'aquesta representació interna. Els desenvolupadors anomenen la representació interna "AST", que significa arbre de sintaxi abstracta, o arbre de sintaxi abstracta. Podeu mirar la representació intermèdia de manera molt senzilla: tot el que heu de fer és establir el format de sortida a "natiu"

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

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

Els lectors que han treballat almenys una mica amb Haskell ja poden suposar a partir d'aquest petit exemple que Pandoc està escrit a Haskell: la sortida d'aquesta ordre és una representació en cadena de les estructures internes de Pandoc, creada a semblança de com es fa habitualment. a Haskell, per exemple, a la biblioteca estàndard.

Així doncs, aquí podeu veure que la representació interna és una estructura recursiva, en cada node intern del qual hi ha una llista. Per exemple, al nivell superior hi ha una llista d'un element: la capçalera del primer nivell amb els atributs "hello-world",[],[]. Dins d'aquesta capçalera s'amaga una llista de la cadena "Hola", seguida d'un espai i la cadena "Món!".

Com podeu veure, la representació interna no és gaire diferent de l'HTML. És un arbre on cada node intern proporciona informació sobre el format dels seus descendents, i les fulles contenen el contingut real del document.

Si baixem al nivell d'implementació, el tipus de dades per a tot el document es defineix així:

data Pandoc = Pandoc Meta [Block]

Aquí Block són precisament els vèrtexs interns esmentats anteriorment, i Meta és metainformació sobre el document, com ara el títol, la data de creació, els autors; això és diferent per a diferents formats, i Pandoc intenta, si és possible, conservar aquesta informació quan es tradueix d'un format a un altre. format.

Gairebé tots els constructors del tipus Bloc (per exemple, Capçalera o Paràgraf (paràgraf)) prenen atributs i una llista de vèrtexs de nivell inferior com a arguments - En línia, com a regla. Per exemple, Space o Str són constructors del tipus Inline, i l'etiqueta HTML també es converteix en la seva pròpia Inline especial. No veiem cap sentit proporcionar una definició completa d'aquests tipus, però tingueu en compte que es pot trobar aquí aquí.

Curiosament, el tipus Pandoc és un monoide. Això vol dir que hi ha algun tipus de document buit i que els documents es poden apilar. És convenient utilitzar-lo quan escriu Readers: podeu dividir un document en parts mitjançant una lògica arbitrària, analitzar-ne cadascun per separat i després agrupar-ho tot en un sol document. En aquest cas, la metainformació es recopilarà de totes les parts del document alhora.

Quan es converteix, per exemple, de LaTeX a HTML, primer un mòdul especial anomenat LaTeXReader converteix el document d'entrada en AST, després un altre mòdul anomenat HTMLWriter converteix l'AST a HTML. Gràcies a aquesta arquitectura, no cal escriure un nombre quadràtic de conversions: n'hi ha prou d'escriure Reader i Writer per a cada nou format, i tots els parells de conversions possibles seran compatibles automàticament.

És evident que aquesta arquitectura també té els seus inconvenients, predits des de fa temps pels experts en l'àmbit de l'arquitectura del programari. El més important és el cost de fer canvis a l'arbre de sintaxi. Si el canvi és prou greu, haureu de canviar el codi a tots els lectors i escriptors. Per exemple, un dels reptes als quals s'enfronten els desenvolupadors de Pandoc és donar suport a formats de taula complexos. Ara Pandoc només pot crear taules molt senzilles, amb una capçalera, columnes i un valor a cada cel·la. Per exemple, l'atribut colspan en HTML simplement s'ignorarà. Una de les raons d'aquest comportament és la manca d'un esquema unificat per representar taules en tots els formats o almenys en molts; per tant, no està clar de quina forma s'han d'emmagatzemar les taules a la representació interna. Però fins i tot després de seleccionar una vista específica, haureu de canviar absolutament tots els lectors i escriptors que admeten el treball amb taules.

El llenguatge Haskell va ser escollit no només pel gran amor dels autors per la programació funcional. Haskell és conegut per les seves àmplies capacitats de processament de text. Un exemple és la biblioteca parsec és una biblioteca que utilitza activament els conceptes de programació funcional -monoides, mónades, funtors aplicatius i alternatius- per escriure analitzadors arbitraris. Tot el poder de Parsec es pot veure a exemple de HaskellWiki, on s'analitza un analitzador complet d'un llenguatge de programació imperatiu senzill. Per descomptat, Parsec també s'utilitza activament a Pandoc.

Breument descrit, les mónades s'utilitzen per a l'anàlisi seqüencial, quan una cosa arriba primer i després una altra. Per exemple, en aquest exemple:

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

Primer heu de comptar l'espai i després la instrucció, que també té el tipus Parser Stmt.

Funtors alternatius s'utilitzen per retrocedir si l'anàlisi falla. Per exemple,

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

Això vol dir que heu de provar de llegir l'enunciat entre parèntesis o bé intentar llegir diverses declaracions de forma seqüencial.

Els funtors aplicatius s'utilitzen principalment com a dreceres per a les mónades. Per exemple, deixeu que la funció tok llegeixi algun testimoni (aquesta és una funció real de LaTeXReader). Vegem aquesta combinació

const <$> tok <*> tok

Llegirà dues fitxes seguides i retornarà la primera.

Per a totes aquestes classes, Haskell té bells operadors simbòlics, cosa que fa que la programació de Reader sembli art ASCII. Només admireu aquest meravellós codi.

Les nostres tasques estaven relacionades amb LaTeXReader. La tasca de Vasily era donar suport a les ordres mbox i hbox, útils per escriure paquets en LaTeX. Elizabeth va ser responsable de donar suport a l'ordre epigraph, que us permet crear epígrafs en documents LaTeX.

Hatrace

Els sistemes operatius semblants a UNIX solen implementar la crida al sistema ptrace. És útil per depurar i simular entorns de programa, permetent rastrejar les trucades al sistema que fa el programa. Per exemple, la molt útil utilitat strace utilitza ptrace internament.

Hatrace és una biblioteca que proporciona una interfície per rastrejar a Haskell. El cas és que ptrace en si és molt sofisticat i és bastant difícil utilitzar-lo directament, sobretot des de llenguatges funcionals.

Hatrace funciona com Strace a l'inici i accepta arguments similars. Es diferencia de strace perquè també és una biblioteca que proporciona una interfície més senzilla que només ptrace.

Amb l'ajuda d'hatrace, ja hem detectat un error desagradable al compilador GHC Haskell: si s'elimina en el moment equivocat, genera fitxers d'objecte incorrectes i no els recompila quan es reinicia. L'escriptura de les trucades del sistema va permetre reproduir de manera fiable l'error en una execució, mentre que les morts aleatòries van reproduir l'error en unes dues hores.

Hem afegit interfícies de trucada del sistema a la biblioteca: l'Elizaveta ha afegit brk i Vasily ha afegit mmap. A partir dels resultats del nostre treball, és possible utilitzar de manera més senzilla i precisa els arguments d'aquestes crides al sistema quan s'utilitza la biblioteca.

Font: www.habr.com