Хвостовая рекурсия с монадами State и CPS?

Question

Я занимаюсь созданием простой библиотеки синтаксического анализа в Haskell, которая компилирует спецификацию синтаксического анализатора в оптимизированный код с использованием Template Haskell.

Однако я пытаюсь выяснить, какой код наиболее эффективен для оптимизации, поэтому давайте рассмотрим простой фрагмент кода парсера, написанный синтаксическим анализатором.

Парсер можно рассматривать как функцию куда - это то, что мы хотим распознать во время синтаксического анализа, а результирующая строка - это та часть ввода, которую мы не сопоставили. Когда парсеры запускаются последовательно, следующий парсер должен продолжить работу с этой строкой. В конце мы можем сказать, что вся строка была успешно проанализирована, если конечный результат имеет форму .

В этом примере мы будем использовать синтаксический анализатор, который анализирует любое количество символов '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')

Это соответствует любому количеству с. Анализатор выполняет рекурсию до тех пор, пока строка не станет пустой.

Глядя на созданное ядро ​​GHC, мы видим следующий результат:

      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 }

На мой нетренированный взгляд кажется, что это не хвостовая рекурсия, поскольку мы сначала выполняем рекурсивный вызов, а потом все равно нужно объединить вывод в кортеж. Мне также кажется странным / интересным то, что исходный код все еще присутствует в скомпилированном коде, из-за чего кажется, что вычисления действительно должны выполняться в несколько (т.е. не рекурсивных) шагов.

На ум приходят два других подхода к написанию этого кода. (Может есть еще?)

стиль передачи

      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>

Здесь я не уверен, как интерпретировать ядро: из -код ушел. Вместо этого рекурсивный вызов немедленно заканчивается в . Впоследствии нам все еще нужно поместить результат в кортеж, но достаточно ли этого «без минусов», чтобы угодить богам рекурсии?

---

Итак, подведем итог: это три метода написания простой функции синтаксического анализа. Я хотел бы знать, какой из них наиболее эффективен с точки зрения памяти и как получить некоторую интуицию в распознавании хвостовой рекурсии, глядя на выходные данные GHC Core.