In June of this year, the small Swiss town of Rapperswil hosted the event called . This time, more than five hundred Haskell enthusiasts gathered, from beginners to the founding fathers of the language. Although the organizers call it a hackathon, it is not a conference or hackathon in the traditional sense. Its format differs from traditional programming events. We learned about ZuriHac by happy coincidence, participated in it, and now feel it is our duty to share this unusual discovery!
About Us
This article was prepared by two third-year students of the Applied Mathematics and Computer Science program at HSE University — St. Petersburg: Vasily Alferov and Elizaveta Vasilenko. Our interest in functional programming started with a series of lectures by D. N. Moskvina in our second year at university. Currently, Vasily is participating in the Google Summer of Code program, where he is working on the implementation of algebraic graphs in Haskell under the guidance of the project team. Elizaveta applied her functional programming skills in her coursework focused on implementing the anti-unification algorithm with subsequent application in type theory.
Event Format
The target audience consists of open-source project owners, programmers looking to contribute to their development, researchers of functional programming, and simply Haskell enthusiasts. This year, at the venue – HSR Hochschule für Technik Rapperswil – developers from more than fifty open-source projects in Haskell from around the world gathered to present their products and engage new people in their development.
Photos from Twitter
The scheme is very simple: you need to write a few sentences about your project in advance and send them to the organizers, who will post the information about your project on the event's page. Additionally, on the first day, project authors have thirty seconds each to briefly share from the stage what they are working on and what needs to be done. Afterward, interested individuals seek out the authors and inquire in detail about their tasks.
We currently do not have any open projects of our own, but we are eager to contribute to existing ones, so we registered as regular participants. Over three days, we worked with two groups of developers. It turns out that collaborative code review and live interactions make the collaboration between project authors and contributors very productive – at ZuriHac, we managed to grasp new areas for us and helped two completely different teams, closing one task in each project.
In addition to valuable hands-on practice, ZuriHac also featured several lectures and workshops. Two lectures stood out to us in particular. In the first, Andrey Mokhov from Newcastle University discussed selective applicative functors — a class of types intended to serve as an intermediate point between applicative functors and monads. In another lecture, one of the founders of Haskell, Simon Peyton Jones, talked about how type inference works in the GHC compiler.
Lecture by Simon Peyton Jones. Photo from Twitter
The workshops held during the hackathon were divided into three categories based on the skill level of participants. The tasks offered to participants joining the project development were also marked with difficulty levels. The small but friendly community of functional programmers happily welcomes newcomers. However, the functional programming course we took at university proved very helpful for understanding the lectures by Andrey Mokhov and Simon Peyton Jones.
Registration for the event is free for both regular participants and project authors. We submitted our applications in early June, after which we were quickly moved from the waiting list to the list of confirmed participants.
Now we will talk about the projects we participated in.
Pandoc
is a universal document converter, effectively converting from any format to any other. For example, from docx to pdf, or from Markdown to MediaWiki. Its author, John MacFarlane, is a philosophy professor at the University of California, Berkeley. In general, Pandoc is quite well-known, and some of our acquaintances were surprised to learn that Pandoc is written in Haskell.
A list of document formats supported by Pandoc. There is also a whole graph on the website, but that image cannot be included in the article.
Of course, Pandoc does not implement direct conversion for every pair of formats. To support such a wide range of conversions, a standard architectural solution is used: first, the entire document is translated into a special internal intermediate representation, and then a document in another format is generated based on this internal representation. The internal representation is referred to by developers as 'AST', which stands for Abstract Syntax Tree, or . You can easily view the intermediate representation: just set the output format to 'native'.
$ cat example.html
<h1>Hello, World!</h1>
$ pandoc -f html -t native example.html
[Header 1 ("hello-world",[],[]) [Str "Hello,",Space,Str "World!"]]
Readers who have worked even a little with Haskell may infer from this small example that Pandoc is written specifically in Haskell: the output of this command is a representation of the internal structures of Pandoc as a string, created similarly to how it is usually done in Haskell, for example, in the standard library.
So here you can see that the internal representation is a recursive structure, where each internal node contains a list. For example, at the very top level, there is a list with a single element — a first-level header with attributes 'hello-world', [], []. Inside this header, there is a list of the string 'Hello,' a space, and the string 'World!'.
As can be seen, the internal representation is not much different from HTML. It represents a tree where each internal node provides some information about the formatting of its children, while the leaves contain the actual content of the document.
If we descend to the level of a specific implementation, the data type for the entire document is defined like this:
data Pandoc = Pandoc Meta [Block]Here Block refers to the internal nodes described above, while Meta is the metadata about the document, such as title, creation date, authors — this varies by format, and Pandoc tries to preserve such information as much as possible when converting from one format to another.
Almost all constructors of the Block type—such as Header or Para (paragraph)—accept attributes and a list of lower-level nodes as arguments, which are usually Inline. For instance, Space or Str are Inline-type constructors, and the HTML tag
also turns into its own special Inline. While we don’t see the point in providing a full definition of these types, we note that it can be viewed here. .
Interestingly, the Pandoc type is a monoid. This means there is an empty document, and documents can be combined together. This is convenient for writing Readers—you can break a document into parts with arbitrary logic, parse each separately, and then assemble everything back into one document. In doing so, the metadata will be gathered from all parts of the document at once.
When converting, say, from LaTeX to HTML, first a special module called LaTeXReader transforms the input document into an AST, and then another module called HTMLWriter converts the AST into HTML. Thanks to this architecture, it’s not necessary to write a quadratic number of conversions—it's enough to write a Reader and Writer for each new format, and all possible pairs of conversions will be automatically supported.
It’s clear that such an architecture has its drawbacks, which have long been predicted by software architecture specialists. The most significant issue is the cost of making changes to the parse tree. If the change is significant enough, it will require modifying the code in all Readers and Writers. For example, one of the tasks facing the developers of Pandoc is supporting complex table formats. Currently, Pandoc can only handle the simplest tables, with a header, columns, and a value in each cell. For instance, the colspan attribute in HTML will simply be ignored. One reason for this behavior is the lack of a unified schema for representing tables across all or at least many formats—thus, it’s unclear how to store tables in the internal representation. But even after choosing a specific representation, absolutely all Readers and Writers supporting table functionality will need to be changed.
The Haskell language was chosen not only because of the authors' deep love for functional programming. Haskell is known for its extensive capabilities in text processing. One example is the library — a library that actively utilizes concepts specific to functional programming—monoids, monads, applicative and alternative functors—for writing arbitrary parsers. The full power of Parsec can be seen in HaskellWiki, which discusses a complete parser for a simple imperative programming language. Naturally, Parsec is also actively used in Pandoc.
In brief, monads are used for sequential parsing, where one thing comes first, followed by another. For example, in the following case:
whileParser :: Parser Stmt
whileParser = whiteSpace >> statementFirst, it needs to read the whitespace, and then the statement—which is also of type Parser Stmt.
Alternative functors are used for backtracking in case parsing fails. For example,
statement :: Parser Stmt
statement = parens statement sequenceOfStmtThis means that it should either try to read the statement in parentheses, or sequentially try to read several statements.
Applicative functors are mainly used as shortcuts for monads. For example, let the function tok read some token (this is a real function from LaTeXReader). Let's look at such a combination
const <$ tok tokIt will read two tokens in succession and return the first one.
For all these classes, there are beautiful symbolic operators in Haskell, making the programming of Readers resemble ASCII art. Just look at this wonderful code.
Our tasks were related to LaTeXReader. Vasily's task was to support the mbox and hbox commands, which are useful for writing packages in LaTeX. Elizabeth was responsible for supporting the epigraph command, which allows formatting epigraphs in LaTeX documents.
Hatrace
In UNIX-like operating systems, the ptrace system call is often implemented. It is useful for debugging and simulating program environments, allowing tracking of system calls made by a program. For example, the very useful utility strace internally uses ptrace.
Hatrace is a library that provides an interface for ptrace in Haskell. The ptrace itself is quite complex, and using it directly can be difficult, especially from functional languages.
When launched, Hatrace functions like strace and accepts similar arguments. Its distinction from strace is that it is also a library, offering a simpler interface than just ptrace.
Using hatrace, we have already caught an unpleasant bug in the Haskell compiler GHC — when killed at the wrong moment, it generates incorrect object files and does not recompile them upon restart. Scripting system calls allowed us to reliably reproduce the error in one run, while random kills would reproduce the error in about two hours.
We have added system call interfaces to the library — Elizabeth added brk, and Vasily added mmap. As a result of our work, it is now easier and more accurate to use the arguments of these system calls when using the library.
Source: habr.com
