Monoidal解析 - 它是什么？

Question

我只是偶然发现了由Edward Kmett命名为" Monoids " 的幻灯片中的monoidal 解析这个术语.幻灯片始终使用haskell.

现在,在搜索这个词的时候,我发现只有极少数提及它,而且来自同一作者.所以我认为这个术语可以在这里解释.

那么,monoidal解析一些有趣和新的东西吗？它出现在除我链接到的幻灯片之外的任何地方吗？最重要的是它是什么？幻灯片本身似乎没有给出定义,也没有强调它.

Answer 1

我将从解析器通常如何工作开始.从广义上讲,解析器按顺序获取输入令牌.在某些时候(通常在所有令牌都耗尽之后),解析器返回输出.这个模型的一个缺点是它本身就是顺序的:因为解析器按顺序操作一系列令牌,所以如何并行化这个过程并不明显.

但是,如果我们可以访问能够将部分解析结果组合成单个结果的操作,则可以并行化解析.例如,如果我们的语言可以用无上下文语法表示,那么我们可以分别并行地解析每个顶级定义,然后使用组合操作组装这些片段.

Monoidal解析只是意味着解析器可以访问合适的组合函数.monoid是具有零元素和二元关联运算符的结构.例如,列表形成一个monoid,其中零是空列表,关联运算符是串联.请记住,关联性意味着(a++b)++c == a++(b++c).碰巧这是确保我们能够以合理的方式重组解析结果的必要属性.子解析重新组合的确切顺序无关紧要,只要每个子解析保持在正确的序列位置即可.

当然,对于实际编写并行解析器,还必须适当地拆分块.如果要并行解析顶级定义,则必须能够识别定义的开始位置.此任务通常由解析器本身执行.我记得,他的大部分幻灯片涵盖了这个主题.拆分顶级定义非常粗糙; 理想情况下,我们的解析器将能够从任意任意令牌开始,然后在应用幺半群运算符时从这些段中理解.

不幸的是,我不能说"monoidal parsing"是否是新的,因为我对文献并不是特别熟悉.但是我怀疑用于并行解析的任何模型或算法都涉及一个monoid结构,即使它没有明确命名.一段时间以来众所周知,幺半群适合并行化问题,所以如果这种技术在解析器研究人员中很常见,我也不会感到惊讶.

Answer 2

在这个页面上尝试他的另一个演示,它是你正在阅读的那个之后的第二个.这是一个新的东西,我真正能做的就是解释他的幻灯片并告诉你它是尝试采用monadic解析(如Parsec)并使用较弱的代数结构,以便有更多的空间来重组计算.这个想法是为了改善并行性.

编辑:页面上的评论表明两个会谈是背靠背安排的,所以也许你在幻灯片中提到的是第二次谈话的前奏.