首页 文章

使用Haskell状态monad一个代码气味?

提问于
浏览
57

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

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

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

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

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

8 回答

  • 42

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

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

    一个相当明显的例子就是当我的团队正在为ICFP Programming Contest 2009进行输入时(代码可以在git://git.cynic.net/haskell/icfp-contest-2009获得) . 我们最终得到了几个不同的模块化部件:

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

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

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

    • Visualizers:几个不同的例程集,它们读取输入和输出端口,并生成某种可视化或记录模拟进行过程中发生的事情

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

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

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

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

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

  • 2

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

    这是Glasgow 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隐藏在一层抽象背后,它根本就没有臭!

  • 6

    你看过Attribute grammars(AG)吗? (关于wikipedia的更多信息和Monad Reader中的article)?

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

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

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

    在乌特勒支大学,我们使用Attribute Grammar SystemUUAGC)编写编译器 . 这是一个预处理器,它从提供的 .ag 文件生成haskell代码( .hs 文件) .


    虽然,如果你还在学习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
    
  • -13

    你可能想要一个applicative functor而不是monad:

    http://www.haskell.org/haskellwiki/Applicative_functor

    我认为原始论文比维基更好地解释了它:

    http://www.soi.city.ac.uk/~ross/papers/Applicative.html

  • 44

    我不认为使用状态Monad在用于模拟状态时是代码气味 .

    如果需要通过函数对状态进行线程化,则可以显式执行此操作,将状态作为参数并在每个函数中返回 . State Monad提供了一个很好的抽象:它为你传递状态,并提供许多有用的功能来组合需要状态的函数 . 在这种情况下,使用State Monad(或Applicatives)不是代码气味 .

    但是,如果您使用State Monad来模拟命令式编程,而功能性解决方案就足够了,那么您只是将事情变得复杂 .

  • -5

    一般来说,你应该尽可能地避免使用状态,但这并不总是实用的 . Applicative 使有效的代码看起来更好,更实用,尤其是树遍历代码可以从这种风格中受益 . 对于名称生成的问题,现在有一个相当不错的包:value-supply .

  • 0

    好吧,不要使用monads . 函数式编程的强大之处在于功能纯度及其重用 . 这篇论文是我的一位教授曾经写过的,他是帮助 Build Haskell的人之一 .

    这篇论文叫做“Why functional programming matters”,我建议你仔细阅读 . 这是一个很好的阅读 .

  • 3

    我们这里的术语要小心 . 国家本身并不坏;功能语言有状态 . 当你发现自己想要分配变量值并改变它们时,什么是“代码味道” .

    当然,Haskell状态monad就是出于这个原因 - 就像I / O一样,它让你在受限制的环境中做不安全和无功能的事情 .

    所以,是的,这可能是代码味道 .

相关问题