Рекурсивные функции в выражениях вычисления
Некоторый фон сначала. Я в настоящее время узнаю некоторый материал об одноместном синтаксическом анализаторе combinators. В то время как я пытался передать функцию 'chainl1' из данной статьи (p. 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)))
2 ответа
В вашем коде следующая функция не является хвостовой рекурсивной, потому что на каждой итерации она делает выбор между p ' или успешно :
// 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) }
Как вы можете проверить, новая версия соответствует этому шаблону, а исходная - нет.
В общем, можно писать выражения хвостовой рекурсии для вычислений (см. 1 и 2 ), даже с несколькими let! привязок благодаря механизму «задержки».
В данном случае, я думаю, последнее утверждение chainl1 - это то, что загоняет вас в угол.