Рекурсивные функции в вычислительных выражениях

Сначала немного предыстории. В настоящее время я изучаю кое-что о комбинаторах монадического синтаксического анализатора. Пока я пытался перенести функцию 'chainl1' из этой статьи ( с. 16-17), я пришел к такому решению:

let chainl1 p op = parser {
  let! x = p
  let rec chainl1' (acc : 'a) : Parser<'a> =
      let p' = parser {
          let! f = op
          let! y = p
          return! chainl1' (f acc y)
          }
      p' <|> succeed acc
  return! chainl1' x
}

Я протестировал функцию с большим объемом ввода и получил исключение StackOverflowException. Теперь мне интересно, можно ли переписать рекурсивную функцию, которая использует какое-то выражение вычисления, таким образом, чтобы она использовала хвостовую рекурсию?

Когда я раскрываю выражение вычисления, я не понимаю, как это вообще возможно.

let chainl1 p op =
    let b = parser
    b.Bind(p, (fun x ->
    let rec chainl1' (acc : 'a) : Parser<'a> =
        let p' =
            let b = parser
            b.Bind(op, (fun f ->
            b.Bind(p, (fun y ->
            b.ReturnFrom(chainl1' (f acc y))))))
        p' <|> succeed acc
    b.ReturnFrom(chainl1' x)))

f# tail-recursion computation-expression
person PetPaulsen    schedule 29.06.2010    source источник

Ответы (2)


arrow_upward
6
arrow_downward

В вашем коде следующая функция не является хвостовой рекурсивной, потому что на каждой итерации она делает выбор между p' или succeed:

// Renamed a few symbols to avoid breaking SO code formatter
let rec chainl1Util (acc : 'a) : Parser<'a> = 
  let pOp = parser { 
    let! f = op 
    let! y = p 
    return! chainl1Util (f acc y) } 
  // This is done 'after' the call using 'return!', which means 
  // that the 'cahinl1Util' function isn't really tail-recursive!
  pOp <|> succeed acc

В зависимости от вашей реализации комбинаторов синтаксического анализатора может сработать следующая перезапись (я здесь не эксперт, но, возможно, стоит попробовать это):

let rec chainl1Util (acc : 'a) : Parser<'a> = 
  // Succeeds always returning the accumulated value (?)
  let pSuc = parser {
    let! r = succeed acc
    return Choice1Of2(r) }
  // Parses the next operator (if it is available)
  let pOp = parser {
    let! f = op
    return Choice2Of2(f) }

  // The main parsing code is tail-recursive now...
  parser { 
    // We can continue using one of the previous two options
    let! cont = pOp <|> pSuc 
    match cont with
    // In case of 'succeed acc', we call this branch and finish...
    | Choice1Of2(r) -> return r
    // In case of 'op', we need to read the next sub-expression..
    | Choice2Of2(f) ->
        let! y = p 
        // ..and then continue (this is tail-call now, because there are
        // no operations left - e.g. this isn't used as a parameter to <|>)
        return! chainl1Util (f acc y) }

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

let rec foo(arg) = id { 
  // some computation here
  return! foo(expr) }

Как видите, новая версия соответствует этому шаблону, а исходная - нет.

person Tomas Petricek    schedule 29.06.2010
comment
Это избавляет от рекурсии через пользовательский код, но в моей реализации здесь lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!1772.entry он по-прежнему StackOverflow проходит через саму реализацию парсера. Теперь я буду мотивирован исследовать «синтаксические анализаторы с продолжениями» ... - person Brian; 29.06.2010
comment
Брайан, я также использовал вашу серию блогов как источник знаний. Это очень помогло. Тем временем я сравнил ответ Мау (seq) с моим синтаксическим анализатором. И я предполагаю, что метод задержки в монаде - это импорт. Но я действительно не знаю. FParsec использует while ... но я хочу использовать функциональное решение: D - person PetPaulsen; 29.06.2010
comment
Да, я догадываюсь, что вам нужно будет реорганизовать базовую реализацию синтаксического анализатора, чтобы принять параметр продолжения, а комбинатор <|> будет использовать продолжения для выполнения хвостовых вызовов своих аргументов, что-то вроде lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!250.entry по сравнению с lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!174.entry ... но в какой-то момент (через долгое время, с моим текущим отставанием) я надеюсь сам проработать все детали и написать об этом в блоге :) - person Brian; 29.06.2010
comment
Было бы здорово, если бы вам это удалось. Я с нетерпением жду этого и слежу за вашим блогом. - person PetPaulsen; 29.06.2010

arrow_upward
2
arrow_downward

Как правило, можно писать выражения хвостовой рекурсии для вычислений (см. 1 и 2), даже с несколькими привязками let! благодаря ' механизм задержки.

В этом случае, я думаю, последнее утверждение chainl1 - это то, что загоняет вас в угол.

person Mau    schedule 29.06.2010