0

我正在用 Haskell 创建一个简单的解析库，它使用 Template Haskell 将解析器规范编译为优化的代码。

但是，我试图弄清楚哪种代码对优化最有效，所以让我们考虑一个简单的解析器编写的解析器片段。

解析器可以看作是一个函数String -> (a, String)，其中a是我们在解析过程中想要识别的任何内容，而生成的字符串是我们未匹配的输入的任何部分。当解析器按顺序运行时，下一个解析器应该继续处理这个字符串。最后，如果最终结果是 shape ，我们可以说成功解析了一个完整的字符串("", _)。

在此示例中，我们将使用解析任意数量的“a”字符的解析器。 （错误处理，即如果看到除“a”以外的任何字符时报告错误，已被排除在代码片段之外，以保持一切简洁，以使问题清晰）。

直截了当（天真的？）实施

如果我们用解析器编写递归解析器的代码，一个简单的手动实现可能是：

parser_raw :: String -> (String, String)
parser_raw str =
  case str of
    [] -> ([], [])
    ('a' : rest) ->
      let
        (res', rest') = parser_raw rest
      in
        (('a' : res'), rest')

这匹配任意数量的'a''。解析器递归直到字符串为空。

查看创建的 GHC Core，我们看到以下输出：

Rec {
-- RHS size: {terms: 36, types: 45, coercions: 0, joins: 0/1}
$wparser_raw
  = \ w_s7BO ->
      case w_s7BO of {
        [] -> (# [], [] #);
        : ds_d736 rest_a5S6 ->
          case ds_d736 of { C# ds1_d737 ->
          case ds1_d737 of {
            __DEFAULT -> case lvl6_r7Fw of wild2_00 { };
            'a'# ->
              let {
                ds3_s7vv
                  = case $wparser_raw rest_a5S6 of { (# ww1_s7C3, ww2_s7C4 #) ->
                    (ww1_s7C3, ww2_s7C4)
                    } } in
              (# : lvl2_r7Fs
                   (case ds3_s7vv of { (res'_a65m, rest'_a65n) -> res'_a65m }),
                 case ds3_s7vv of { (res'_a65m, rest'_a65n) -> rest'_a65n } #)
          }
          }
      }
end Rec }

在我未经训练的眼里，这似乎不是尾递归，因为我们首先进行递归调用，然后仍然需要将输出组合成一个元组。我还觉得奇怪/有趣的是let，源代码中的 仍然存在于编译代码中，这使得计算看起来确实需要在多个（即非尾递归）步骤中完成。

我想到了另外两种编写此代码的方法。（也许还有更多？）

续传风格

parser_cps :: String -> (String, String)
parser_cps str = parser_cps' str id
  where
    parser_cps' :: String -> ((String, String) -> (String, String)) -> (String, String)
    parser_cps' str fun =
      case str of
        [] -> fun ([], [])
        ('a' : rest) ->
          parser_cps' rest ((\(tl, final) -> (('a' : tl), final) ) . fun)

这导致：

Rec {
-- RHS size: {terms: 28, types: 29, coercions: 0, joins: 0/0}
parser_cps_parser_cps'
  = \ str_a5S8 fun_a5S9 ->
      case str_a5S8 of {
        [] -> fun_a5S9 lvl9_r7FM;
        : ds_d72V rest_a5Sa ->
          case ds_d72V of { C# ds1_d72W ->
          case ds1_d72W of {
            __DEFAULT -> lvl8_r7FL;
            'a'# ->
              parser_cps_parser_cps'
                rest_a5Sa
                (\ x_i72P ->
                   case fun_a5S9 x_i72P of { (tl_a5Sb, final_a5Sc) ->
                   (: lvl2_r7FF tl_a5Sb, final_a5Sc)
                   })
          }
          }
      }
end Rec }

-- RHS size: {terms: 4, types: 4, coercions: 0, joins: 0/0}
parser_cps = \ str_a5S6 -> parser_cps_parser_cps' str_a5S6 id

从我们执行尾调用的意义上说，这看起来是尾递归的。然而，结果似乎确实是一个巨大的重击。在到达递归的基础之前，我们是否使用了大量额外的堆空间？

国家单子

-- Using `mtl`'s
-- import Control.Monad.State.Strict

parser_state :: String -> (String, String)
parser_state = runState parser_state'
  where
    parser_state' :: State String String
    parser_state' = do
      str <- get
      case str of
        [] -> return []
        ('a' : rest) -> do
          put rest
          res <- parser_state'
          return ('a' : res)

这导致：

Rec {
-- RHS size: {terms: 26, types: 36, coercions: 0, joins: 0/0}
$wparser_state'
  = \ w_s7Ca ->
      case w_s7Ca of {
        [] -> (# [], [] #);
        : ds_d72p rest_a5Vb ->
          case ds_d72p of { C# ds1_d72q ->
          case ds1_d72q of {
            __DEFAULT -> case lvl11_r7FO of wild2_00 { };
            'a'# ->
              case $wparser_state' rest_a5Vb of { (# ww1_s7Cl, ww2_s7Cm #) ->
              (# : lvl2_r7FF ww1_s7Cl, ww2_s7Cm #)
              }
          }
          }
      }
end Rec }

-- RHS size: {terms: 8, types: 14, coercions: 6, joins: 0/0}
parser_state1
  = \ w_s7Ca ->
      case $wparser_state' w_s7Ca of { (# ww1_s7Cl, ww2_s7Cm #) ->
      (ww1_s7Cl, ww2_s7Cm) `cast` <Co:6>
      }

-- RHS size: {terms: 1, types: 0, coercions: 7, joins: 0/0}
parser_state = parser_state1 `cast` <Co:7>

在这里，我不确定如何解释核心：-code 的 Thelet消失parser_raw了。相反，递归调用立即在case. 之后我们仍然需要将结果放入一个元组中，但是这个“无缺点”是否足以取悦递归之神？

所以，总结一下：这是编写简单解析函数的三种技术。我想知道其中哪一个是最节省内存的，以及如何通过查看 GHC 核心输出来获得一些直觉来识别尾递归。

4

0 回答 0