HCOONa's blog

发表于 更新于 分类于

这是对 Monadic parsing in Haskell 一文的翻译。

引言（Introduction）

本文是一篇关于在 Haskell 中定义递归下降解析器（recursive descent parsers）的教程。秉持“一站式服务”的精神，文章把三个领域的材料整合到一个来源中。这三个领域分别是函数式解析器（functional parsers）（Burge, 1975; Wadler, 1985; Hutton, 1992; Fokker, 1995）、使用单子（monads）来组织函数式程序（Wadler, 1990, 1992a, 1992b），以及在 Haskell 中用于单子程序的特殊语法（Jones, 1995; Peterson 等, 1996）。更具体地说，本文展示了如何在 Haskell 中使用 do 记法（do notation）来定义单子解析器。

当然，手写的递归下降解析器在效率上不如由工具生成的自底向上解析器（Aho 等, 1986; Mogensen, 1993; Gill 与 Marlow, 1995）。然而，对于许多研究型应用，一个简单的递归下降解析器已足够。此外，解析器生成器通常仅提供一套固定的组合子（combinators）来描述文法，而本文的方法则完全可扩展：解析器是第一类值（first-class values），我们可以充分利用 Haskell 的能力来为特定应用定义新的组合子。该方法也是展示函数式编程优雅性的一个极佳例子。

本文的目标读者是熟悉 Haskell 并且学过“文法与解析”课程的优秀本科生。具备一些函数式解析器的知识会有帮助，但不要求具备单子方面的经验。基于本文而来的一个 Haskell 库可在网页上获取： http://www.cs.nott.ac.uk/Department/Staff/gmh/bib.html#pearl（链接已失效）

阅读全文 »

发表于 更新于 分类于

staged event-driven architecture (SEDA) 框架在建模的时候就将负载和资源瓶颈考虑在内，从而可以在高负载的情况下也能工作良好，并且有效防止服务过载。SEDA 架构的基本思想是将业务逻辑切分成一系列通过 queues 连接起来的 stages，组合成一个 data flow 网络去执行。

很久之前就看到过 SEDA 的论文，当时没有太过在意，因为这个 idea 实在是太简单了。最近这几年在多租户系统的隔离性，延迟稳定性方面进行了一些比较深入的工作，又加上最近看到了比较相关的论文和文章之后，突然又产生了一些触动，决定把这篇文章再捞起来写上几句。

阅读全文 »

发表于 更新于 分类于

RUM 猜想指的是在 Read Overhead，Update Overhead 和 Memory (or Storage) Overhead 中，同时优化 2 项时需要以剩余的 1 项劣化作为代价。论文原作者进一步解释了一下，在一定程度以内（还没有达到最优的情况下）优化，不遵循 RUM 猜想，但是达到一定阈值后，就需要付出代价才能进一步进行优化。这里的 Update Overhead 只考虑写放大，不考虑写时寻址的代价。

The RUM Conjecture: Read, Update, Memory – Optimize Two at the Expense of the Third.

designing access methods that set an upper bound for two of the RUM overheads, leads to a hard lower bound for the third overhead which cannot be further reduced.

论文原作者解释，提出这一猜想不是说大家啥都不用干了，而是说在达到优化阈值后，如果不想付出某一项性能劣化的代价，应当考虑自适应调整之类的方法，根据数据的特征在这三个重要的参数之间进行平衡。

RUM-Aware Access Method Design. Accepting that a perfect access method does not exist, does not mean the research community should stop striving to improve; quite the opposite. The RUM Conjecture opens the path for exciting research challenges towards the goal of creating RUM-aware and RUM-adaptive access methods.

P.S. 这篇论文也由相同的作者在 SIGMOD'16 上发表了几乎相同的内容[2]。

阅读全文 »
0%