ZuriHac：练习函数式编程

今年XNUMX月，在瑞士小镇拉珀斯维尔，举办了一场名为“ 祖里哈克。这次它聚集了五百多名 Haskell 爱好者，从初学者到该语言的创始人。虽然组织者称这次活动为黑客马拉松，但它并不是传统意义上的会议或黑客马拉松。它的格式与传统的程序员不同。我们有幸了解到 ZuriHac，并参与其中，现在我们认为有责任讲述这个不寻常的发现！

关于我们

本文由圣彼得堡国立研究大学高等经济学院“应用数学和信息学”项目的两名三年级学生 Vasily Alferov 和 Elizaveta Vasilenko 撰写。我们俩对函数式编程的热情始于大学二年级 D. N. Moskvin 的一系列讲座。 Vasily 目前正在参加 Google Summer of Code 计划，在项目团队的指导下，他正在 Haskell 中实现代数图 藻类。 Elizaveta 将所获得的函数式编程技能应用于致力于实现反统一算法以及随后在类型论中的应用的课程作业。

活动形式

目标受众是开源项目的所有者、想要参与其开发的程序员、函数式编程研究人员以及对 Haskell 充满热情的人们。今年，来自世界各地 XNUMX 多个开源 Haskell 项目的开发人员聚集在 HSR Hochschule für Technik Rapperswil 会场，讨论他们的产品并让新人们对他们的开发感兴趣。

照片来自推特 祖里哈克

方案很简单：你需要提前写一些关于你的项目的提案并发送给组织者，组织者会在活动页面上发布关于你的项目的信息。此外，在第一天，项目的作者有三十秒的时间在舞台上非常简短地讲述他们正在做什么以及需要做什么。然后有兴趣的人寻找作者并详细询问任务。

我们还没有自己的开放项目，但我们真的很想为现有项目做出贡献，所以我们注册为常规参与者。在三天的时间里，我们与两组开发人员一起工作。事实证明，代码的联合研究和实时沟通使得项目作者和贡献者之间的互动非常富有成效 - 在 ZuriHac，我们能够了解对我们来说不熟悉的领域，并且能够帮助两个完全不同的团队，每个团队完成一项任务的项目。

除了宝贵的实践之外，ZuriHac 还举办了一些讲座和大师班。我们特别记得有两场讲座。在第一个会议上，来自纽卡斯尔大学的 Andrey Mokhov 谈到了选择性应用函子 - 一类应该成为应用函子和单子之间的中间类型。在另一场讲座中，Haskell 的创始人之一 Simon Peyton Jones 谈到了类型推断在 GHC 编译器中的工作原理。

西蒙·佩顿·琼斯的演讲。照片来自推特 祖里哈克

黑客马拉松期间举办的大师班根据参与者的培训水平分为三类。为参与项目开发的参与者提供的任务也标有一定的难度。这个小而友好的函数式程序员社区很高兴地欢迎新人加入其行列。然而，为了理解 Andrei Mokhov 和 Simon Peyton Jones 的讲座，我们在大学学习的函数式编程课程非常有用。

常规参与者和项目作者均可免费注册该活动。我们在六月初提交了参与申请，之后我们很快就从等待名单转入了确认的参与者名单。

现在我们将讨论我们参与开发的项目。

潘多克

潘多克 事实上，它是文本文档的通用转换器，可以从任何格式转换到任何格式。例如，从 docx 到 pdf，或者从 Markdown 到 MediaWiki。该书的作者约翰·麦克法兰是加州大学伯克利分校的哲学教授。总的来说，Pandoc 相当有名，我们的一些朋友在得知 Pandoc 是用 Haskell 编写时感到惊讶。

Pandoc 支持的文档格式列表。网站上还有一张完整的图表，但这张图片不适合文章。

当然，Pandoc 并不提供每对格式的直接转换。为了支持如此广泛的转换，使用了标准的架构解决方案：首先，将整个文档转换为特殊的内部中间表示，然后从该内部表示生成不同格式的文档。开发人员将内部表示称为“AST”，代表抽象语法树，或者 抽象语法树。您可以非常简单地查看中间表示：您所需要做的就是将输出格式设置为“native”

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

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

至少使用过一点 Haskell 的读者已经可以从这个小例子中假设 Pandoc 是用 Haskell 编写的：该命令的输出是 Pandoc 内部结构的字符串表示形式，其创建方式与通常的操作方式类似在 Haskell 中，例如在标准库中。

所以，在这里你可以看到内部表示是一个递归结构，在每个内部节点中有一个列表。例如，在顶层有一个元素的列表 - 第一级标头具有属性“hello-world”、[]、[]。隐藏在该标头内的是字符串“Hello”的列表，后跟空格和字符串“World!”。

正如您所看到的，内部表示与 HTML 没有太大区别。它是一棵树，其中每个内部节点都提供有关其后代格式的一些信息，叶子包含文档的实际内容。

如果我们深入到实现层面，整个文档的数据类型定义如下：

data Pandoc = Pandoc Meta [Block]

这里的Block正是上面提到的内部顶点，Meta是关于文档的元信息，例如标题、创建日期、作者——这对于不同的格式是不同的，并且Pandoc在从格式转换为格式。

几乎所有 Block 类型的构造函数 - 例如 Header 或 Para（段落） - 都将属性和较低级别的顶点列表作为参数 - 通常是内联的。例如，Space或Str都是Inline类型的构造函数，HTML标签也变成了自己特殊的Inline。我们认为提供这些类型的完整定义没有意义，但请注意，可以在此处找到它 这里.

有趣的是，Pandoc 类型是一个幺半群。这意味着存在某种空文档，并且文档可以堆叠在一起。这在编写 Readers 时使用起来很方便 - 您可以使用任意逻辑将文档分成多个部分，单独解析每个部分，然后将所有内容组合到一个文档中。在这种情况下，将立即从文档的所有部分收集元信息。

例如，当从 LaTeX 转换为 HTML 时，首先一个名为 LaTeXReader 的特殊模块将输入文档转换为 AST，然后另一个名为 HTMLWriter 的模块将 AST 转换为 HTML。由于这种架构，无需编写二次转换 - 为每种新格式编写 Reader 和 Writer 就足够了，并且将自动支持所有可能的转换对。

显然，这样的架构也有其缺点，这是软件架构领域专家早就预测到的。最重要的是更改语法树的成本。如果更改足够严重，您将不得不更改所有 Readers 和 Writers 中的代码。例如，Pandoc 开发人员面临的挑战之一是支持复杂的表格式。现在 Pandoc 只能创建非常简单的表格，每个单元格中有标题、列和值。例如，HTML 中的 colspan 属性将被忽略。造成这种行为的原因之一是缺乏一个统一的方案来表示所有或至少多种格式的表 - 因此，不清楚表应该以什么形式存储在内部表示中。但即使在选择特定视图之后，您也需要更改所有支持使用表的读取器和写入器。

选择 Haskell 语言不仅是因为作者对函数式编程的热爱。 Haskell 以其广泛的文本处理能力而闻名。图书馆就是一个例子 秒差距 是一个积极使用函数式编程概念（幺半群、单子、应用函数和替代函子）来编写任意解析器的库。秒差距的全部威力可见于 例子 来自HaskellWiki，其中解析了简单命令式编程语言的完整解析器。当然，Pandoc 中也积极使用 Parsec。

简而言之，单子用于顺序解析，即先出现一件事，然后再出现另一件事。例如，在这个例子中：

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

首先，您需要计算空间，然后是语句 - 它也具有 Parser Stmt 类型。

如果解析失败，则使用替代函子进行回滚。例如，

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

这意味着您要么需要尝试读取括号中的语句，要么尝试顺序读取多个语句。

应用函子主要用作单子的快捷方式。例如，让 tok 函数读取一些标记（这是来自 LaTeXReader 的真实函数）。我们来看看这个组合

const <$> tok <*> tok

它将连续读取两个令牌并返回第一个。

对于所有这些类，Haskell 都有漂亮的符号运算符，这使得 Reader 编程看起来像 ASCII 艺术。只是欣赏这段精彩的代码。

我们的任务与 LaTeXReader 相关。 Vasily 的任务是支持 mbox 和 hbox 命令，这对于在 LaTeX 中编写包很有用。 Elizabeth 负责支持 Epigraph 命令，该命令允许您在 LaTeX 文档中创建碑文。

哈特雷斯

类 UNIX 操作系统通常实现 ptrace 系统调用。它在调试和模拟程序环境时很有用，允许您跟踪程序进行的系统调用。例如，非常有用的 strace 实用程序在内部使用 ptrace。

Hatrace 是一个在 Haskell 中提供 ptrace 接口的库。事实上，ptrace 本身非常复杂，直接使用它非常困难，尤其是在函数式语言中。

Hatrace 在启动时像 strace 一样运行并接受类似的参数。它与 strace 的不同之处在于它也是一个提供比 ptrace 更简单的接口的库。

在 hatrace 的帮助下，我们已经发现了 GHC Haskell 编译器中的一个令人不快的错误 - 在错误的时刻被终止，它生成了错误的目标文件，并且在重新启动时不会重新编译它们。通过系统调用编写脚本可以在一次运行中可靠地重现错误，而随机杀戮则可以在大约两个小时内重现错误。

我们向库中添加了系统调用接口 - Elizaveta 添加了 brk，Vasily 添加了 mmap。根据我们的工作结果，在使用该库时可以更简单、更准确地使用这些系统调用的参数。

来源： habr.com