使用Haskell状态monad一个代码味？

上帝我讨厌"代码味"这个词,但我想不出更准确的东西.

我正在业余时间为Whitespace设计一个高级语言和编译器,以了解编译器构造,语言设计和函数编程(编译器是用Haskell编写的).

在编译器的代码生成阶段,我必须在遍历语法树时保持"状态" - 数据.例如,在编译流控制语句时,我需要为要跳转到的标签生成唯一的名称(从传入,更新和返回的计数器生成的标签,并且绝不能再次使用计数器的旧值).另一个例子是当我在语法树中遇到内联字符串文字时,它们需要永久转换为堆变量(在空白中,字符串最好存储在堆上).我目前正在处理状态monad中的整个代码生成模块来处理这个问题.

我被告知编写编译器是一个非常适合功能范例的问题,但我发现我的设计方式与我在C中设计它的方式大致相同(你真的可以用任何语言编写C语言 - 甚至Haskell w/state monads).

我想学习如何在Haskell中思考(而不是在函数范式中) - 而不是在C中使用Haskell语法.我真的应该尝试消除/最小化状态monad的使用,还是一个合法的功能"设计模式"？

我在Haskell中编写了多个编译器,状态monad是许多编译器问题的合理解决方案.但你想保持抽象 - 不要明显你使用monad.

下面是来自格拉斯哥Haskell编译一个例子(我也没有写,我只是解决了几边),在我们构建的控制流图.以下是制作图表的基本方法:

empyGraph    :: Graph
mkLabel      :: Label -> Graph
mkAssignment :: Assignment -> Graph  -- modify a register or memory
mkTransfer   :: ControlTransfer -> Graph   -- any control transfer
(<*>)        :: Graph -> Graph -> Graph

但正如您所发现的,保持独特标签的供应充其量是乏味的,因此我们也提供以下功能:

withFreshLabel :: (Label -> Graph) -> Graph
mkIfThenElse :: (Label -> Label -> Graph) -- branch condition
             -> Graph   -- code in the 'then' branch
             -> Graph   -- code in the 'else' branch 
             -> Graph   -- resulting if-then-else construct

整个Graph事情是一个抽象类型,翻译者只是以纯粹的功能性方式快乐地构建图形,而不知道任何monadic正在发生.然后,当最终构造图形时,为了将其转换为代数数据类型,我们可以生成代码,我们为它提供一系列唯一标签,运行状态monad,并拉出数据结构.

状态monad隐藏在下面; 虽然它没有暴露给客户端,但定义Graph是这样的:

type Graph = RealGraph -> [Label] -> (RealGraph, [Label])

或更准确一点

type Graph = RealGraph -> State [Label] RealGraph
  -- a Graph is a monadic function from a successor RealGraph to a new RealGraph

随着状态monad隐藏在一层抽象背后,它根本就没有臭!

我会说,状态一般不是代码气味,只要它保持小而且控制良好.

这意味着使用状态,ST或自定义构建的monad,或者只是将包含状态数据的数据结构传递到几个地方,这并不是一件坏事.(实际上,monad只是帮助完成这个!)然而,拥有遍布整个地方的状态(是的,这意味着你,IO monad!)是一种难闻的气味.

一个相当明显的例子就是我的团队正在参加2009年ICFP编程竞赛(该代码可在git://git.cynic.net/haskell/icfp-contest-2009获得).我们最终得到了几个不同的模块化部件:

VM:运行模拟程序的虚拟机

控制器:几组不同的例程,用于读取模拟器的输出并生成新的控制输入

解决方案:根据控制器的输出生成解决方案文件

可视化器:几组不同的例程,它们读取输入和输出端口,并在模拟过程中生成某种可视化或记录的内容

它们中的每一个都有自己的状态,它们都通过VM的输入和输出值以各种方式进行交互.我们有几个不同的控制器和可视化器,每个控制器和可视化器都有自己不同的状态.

这里的关键点是任何特定状态的内部都局限于他们自己的特定模块,并且每个模块对于其他模块的状态存在一无所知.任何特定的有状态代码和数据集通常只有几十行,在该州有一些数据项.

所有这些都粘在一起,只有十几条线的小功能,它们无法进入任何一个州的内部,并且只是在正确的顺序中调用正确的东西,因为它在模拟中循环,并且通过了非常有限的每个模块的外部信息量(当然还有模块的先前状态).

当状态以这种有限的方式使用,并且类型系统阻止您无意中修改它时,它很容易处理.它是Haskell的优点之一,它可以让你做到这一点.

一个答案说,"不要使用monad." 从我的观点来看,这完全是倒退.Monads是一种控制结构,除其他外,它可以帮助您最小化接触状态的代码量.如果你看monadic解析器作为一个例子,解析的状态(即被解析的文本,已经进入它的距离,已累积的任何警告等)必须贯穿解析器中使用的每个组合器. .然而,只会有一些组合者直接操纵国家; 其他任何东西都使用这些函数中的一个.这使您可以清楚地在一个地方看到可以改变状态的所有少量代码,并且更容易理解如何更改状态,再次使其更容易处理.

你看过属性语法(AG)了吗？(关于维基百科的更多信息和Monad Reader中的文章)？

使用AG,您可以向语法树添加属性.这些属性在合成和继承属性中分开.

合成属性是您从语法树生成(或合成)的东西,可以是生成的代码,也可以是所有注释,或者您感兴趣的任何其他内容.

继承的属性输入到语法树,可以是环境,也可以是代码生成期间使用的标签列表.

在乌特勒支大学,我们使用属性语法系统(UUAGC)编写编译器.这是一个预处理器,它.hs从提供的.ag文件中生成haskell代码(文件).

虽然,如果你还在学习Haskell,那么也许现在不是开始学习另一层抽象的时候了.

在这种情况下,您可以手动编写属性语法为您生成的代码类型,例如:

data AbstractSyntax = Literal Int | Block AbstractSyntax
                    | Comment String AbstractSyntax

compile :: AbstractSyntax -> [Label] -> (Code, Comments)
compile (Literal x) _      = (generateCode x, [])
compile (Block ast) (l:ls) = let (code', comments) = compile ast ls
                             in (labelCode l code', comments)
compile (Comment s ast) ls = let (code, comments') = compile ast ls
                             in (code, s : comments')

generateCode :: Int -> Code
labelCode :: Label -> Code -> Code