ZuriHac: praticando programação funcional

Em junho deste ano, um evento chamado ZuriHac foi realizado pela décima vez na pequena cidade suíça de Rapperswil. Desta vez, mais de quinhentos amantes de Haskell se reuniram desde iniciantes até os pais fundadores da língua. Embora os organizadores chamem esse evento de hackathon, ainda não é uma conferência ou hackathon no sentido clássico. Seu formato é diferente da programação tradicional. Aprendemos sobre o ZuriHac por uma coincidência de sorte, participamos e agora consideramos nosso dever contar sobre uma descoberta incomum!

Sobre nós

Este artigo foi preparado por dois alunos do terceiro ano do programa de Matemática Aplicada e Ciência da Computação da Escola Superior de Economia - São Petersburgo: Vasily Alferov e Elizaveta Vasilenko. A paixão pela programação funcional para nós dois começou com uma série de palestras de D.N. Moskvin no 2º ano da universidade. Atualmente, Vasily participa do programa Google Summer of Code, no qual está envolvido na implementação de gráficos algébricos na linguagem Haskell, sob a orientação da equipe do projeto Alga . Elizabeth aplicou as habilidades adquiridas de programação funcional no trabalho do curso dedicado à implementação do algoritmo anti-unificação com o uso subsequente na teoria dos tipos.

Formato do Evento

O público-alvo são os proprietários de projetos de código aberto, programadores que desejam participar de seu desenvolvimento, pesquisadores de programação funcional e apenas pessoas apaixonadas por Haskell. Este ano, o local da HSR Hochschule für Technik Rapperswil University reuniu desenvolvedores de mais de cinquenta projetos de código aberto Haskell de todo o mundo para falar sobre seus produtos e interessar pessoas novas em seu desenvolvimento.



Foto do Twitter ZuriHac

O esquema é muito simples: você precisa escrever algumas propostas com antecedência sobre o seu projeto e enviá-las aos organizadores, que publicarão informações sobre o seu projeto na página do evento. Além disso, no primeiro dia, os autores dos projetos têm trinta segundos para dizer muito brevemente desde o estágio o que estão fazendo e o que precisa ser feito. Em seguida, as pessoas interessadas pesquisam autores e perguntam em detalhes sobre as tarefas.

Ainda não temos nossos próprios projetos abertos, mas queremos realmente contribuir com os existentes, por isso nos registramos como participantes regulares. Durante três dias, trabalhamos com duas equipes de desenvolvimento. Acontece que o estudo conjunto do código e da comunicação ao vivo torna a interação dos autores e colaboradores do projeto muito produtiva - no ZuriHac, conseguimos descobrir novas áreas para nós e ajudar duas equipes completamente diferentes, fechando a tarefa em cada um dos projetos.

Além da prática valiosa, várias palestras e master classes também foram ministradas no ZuriHac. Lembramos especialmente duas palestras. No início, Andrei Mokhov, da Universidade de Newcastle, falou sobre os agentes aplicadores seletivos - uma classe de tipos que deve se tornar intermediária entre os agentes aplicadores e as mônadas. Em outra palestra, um dos fundadores de Haskell, Simon Peyton Jones, falou sobre como a inferência de tipos funciona no compilador do GHC.



Palestra de Simon Peyton Jones. Foto do Twitter ZuriHac

As master classes realizadas durante o hackathon foram divididas em três categorias, dependendo do nível de treinamento dos participantes. As tarefas oferecidas aos participantes que ingressaram no desenvolvimento dos projetos também tiveram notas com níveis de dificuldade. A comunidade pequena, mas amigável, de programadores funcionais tem o prazer de receber os recém-chegados às suas fileiras. Para entender as palestras de Andrei Mokhov e Simon Peyton Jones, no entanto, o curso de programação funcional aprovado na universidade foi muito útil para nós.

Para participantes comuns e autores do projeto, a inscrição para o evento é gratuita. Solicitamos a participação no início de junho, após o qual fomos transferidos rapidamente da lista de espera para a lista de participantes confirmados.

E agora vamos falar sobre projetos em cujo desenvolvimento participamos.

Pandoc

Pandoc é um conversor universal de documentos de texto - de qualquer formato para qualquer. Por exemplo, de docx para pdf, ou de Markdown para MediaWiki. Seu autor, John MacFarlane, é professor de filosofia na Universidade da Califórnia, Berkeley. Em geral, Pandoc é bastante famoso e alguns de nossos amigos ficaram surpresos ao saber que Pandoc estava escrito em Haskell.



Lista de formatos de documento suportados pelo Pandoc. O site também possui um gráfico inteiro, mas esta imagem não se encaixa no artigo.

Obviamente, o Pandoc não implementa a conversão direta para cada par de formatos. Para suportar um conjunto tão amplo de transformações, é usada uma solução arquitetural padrão: primeiro, o documento inteiro é traduzido em uma representação intermediária interna especial e, em seguida, um documento em um formato diferente é gerado a partir dessa representação interna. Os desenvolvedores chamam a representação interna de "AST", que significa Árvore de sintaxe abstrata ou árvore de sintaxe abstrata . Você pode olhar para a representação intermediária de maneira muito simples: para isso, você só precisa definir "nativo" como o formato de saída

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

Os leitores que trabalharam com Haskell pelo menos um pouco já podem assumir que Pandoc está escrito especificamente em Haskell: a saída desse comando é uma representação da estrutura interna de Pandoc como uma string, criada à semelhança de como geralmente é feita em Haskell, por exemplo, na biblioteca padrão.

Então, aqui você pode ver que a representação interna é uma estrutura recursiva, em cada nó interno do qual existe uma lista. Por exemplo, no nível mais alto, há uma lista de um elemento - o cabeçalho do primeiro nível com os atributos "hello-world", [], []. Dentro deste cabeçalho, há uma lista da string "Hello", um espaço e a string "World!".

Como você pode ver, a representação interna não é muito diferente do HTML. É uma árvore, em que cada nó interno relata algumas informações sobre a formatação de seus descendentes e as folhas contêm o conteúdo real do documento.

Se você descer para o nível de uma implementação específica, o tipo de dados para todo o documento será definido assim:

 data Pandoc = Pandoc Meta [Block] 

Aqui, Block é precisamente os picos internos mencionados acima e Meta é meta-informação sobre o documento, como título, data de criação, autores - isso é diferente para diferentes formatos, e Pandoc tenta salvar essas informações sempre que possível ao transferir de um formato para outro.

Quase todos os construtores do tipo Bloco - por exemplo, Cabeçalho ou Pará (parágrafo) - usam atributos e uma lista de vértices de um nível inferior - Inline, como regra, como argumentos. Por exemplo, Space ou Str são designers do tipo Inline, e a tag HTML também é convertida em seu Inline especial. Não vemos nenhum motivo para dar uma definição completa desses tipos, no entanto, observamos que isso pode ser visto aqui .

Curiosamente, o tipo Pandoc é um monóide. Isso significa que existe algum tipo de documento vazio e que os documentos podem ser empilhados entre si. É conveniente usar ao escrever leitores - você pode dividir um documento em partes com lógica arbitrária, analisar cada um individualmente e, em seguida, juntar tudo em um documento. Nesse caso, as meta-informações serão coletadas de todas as partes do documento de uma só vez.

Ao converter, digamos, de LaTeX para HTML, primeiro um módulo especial chamado LaTeXReader converte o documento de entrada em AST, depois outro módulo chamado HTMLWriter converte AST em HTML. Graças a essa arquitetura, não é necessário escrever um número quadrático de conversões - basta escrever o Reader e o Writer para cada novo formato, e todos os pares possíveis de conversões serão automaticamente suportados.

É claro que essa arquitetura também tem suas desvantagens, previstas há muito tempo por especialistas no campo da arquitetura de software. O mais significativo é o custo de fazer alterações na árvore de sintaxe. Se a alteração for séria o suficiente, você precisará alterar o código em todos os leitores e gravadores. Por exemplo, um dos desafios enfrentados pelos desenvolvedores do Pandoc é oferecer suporte a formatos complexos de tabelas. Agora, o Pandoc pode apenas nas tabelas mais simples, com um cabeçalho, colunas e valor em cada célula. Digamos que o atributo colspan em HTML seja simplesmente ignorado. Uma das razões para esse comportamento é a falta de um esquema de representação de tabela única em todos ou pelo menos muitos formatos - portanto, não está claro em que tabelas de formulário devem ser armazenadas na representação interna. Porém, mesmo depois de escolher uma visualização específica, será necessário alterar absolutamente todos os leitores e gravadores que suportam o trabalho com tabelas.

Haskell foi escolhido não apenas por um grande amor dos autores pela programação funcional. Haskell é conhecido por suas poderosas capacidades de processamento de texto. Um exemplo é a biblioteca parsec - uma biblioteca que usa ativamente os conceitos de programação funcional - monóides, mônadas, functores aplicativos e alternativos - para escrever analisadores arbitrários. O poder total do Parsec pode ser visto no exemplo do HaskellWiki, que analisa o analisador completo de uma simples linguagem de programação imperativa. Obviamente, o Parsec também é usado ativamente no Pandoc.

Em suma, as mônadas são usadas para análise sequencial quando uma chega primeiro e depois a outra. Por exemplo, neste exemplo:

 whileParser :: Parser Stmt whileParser = whiteSpace >> statement 

Primeiro você precisa considerar um espaço e depois a instrução - que também tem o tipo Parser Stmt.

Os functores alternativos são usados ​​para reverter se a análise falhar. Por exemplo

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

Significa que você precisa tentar ler a instrução entre parênteses ou sequencialmente tentar ler várias instruções.

Os functores aplicáveis ​​são usados ​​principalmente como atalhos para mônadas. Por exemplo, deixe a função tok ler algum tipo de token (essa é a função real do LaTeXReader). Vamos olhar para essa combinação

 const <$> tok <*> tok 

Ela lerá dois tokens seguidos e retornará o primeiro.

Haskell possui belos operadores simbólicos para todas essas classes, o que faz com que os leitores de programação pareçam arte ASCII. Apenas admire esse código maravilhoso.

Nossas tarefas estavam relacionadas ao LaTeXReader. A tarefa de Vasily era oferecer suporte aos comandos \ mbox e \ hbox, úteis ao escrever pacotes no LaTeX. Elizabeth foi responsável pelo suporte da equipe \ epigraph, que permite a execução de epígrafos nos documentos do LaTeX.

Hatrace

Em sistemas operacionais do tipo UNIX, a chamada do sistema ptrace é frequentemente implementada. É útil na depuração e simulação de ambientes de programas, permitindo rastrear as chamadas do sistema que o programa faz. Por exemplo, o utilitário strace muito útil usa ptrace dentro de si.

O Hatrace é uma biblioteca que fornece uma interface para o ptrace em Haskell. O fato é que o ptrace em si é muito sofisticado e é muito difícil usá-lo diretamente, especialmente a partir de linguagens funcionais.

O Hatrace na inicialização é executado como strace e aceita argumentos semelhantes. Sua diferença em relação ao strace é que também é uma biblioteca que fornece uma interface mais simples do que apenas o ptrace.

O Hatrace já detectou um bug desagradável no compilador Haskell GHC - quando morto na hora errada, gera arquivos de objeto incorretos e não os recompila quando é reiniciado. Os scripts nas chamadas do sistema tornaram possível reproduzir o erro de forma garantida em uma execução, quando assassinatos aleatórios reproduziam o erro em cerca de duas horas.

Adicionamos interfaces de chamada do sistema à biblioteca - Elizabeth adicionou brk e Vasily adicionou mmap. De acordo com os resultados de nosso trabalho, podemos usar com mais facilidade e precisão os argumentos dessas chamadas de sistema ao usar a biblioteca.