пятница, 13 августа 2010 г.

"Асинхронные" продолжения

Сегодня осознал одну замечательную вещь. Оказывается, что в F# можно использовать async workflow вместо продолжений… Фактически, async состоит из трех продолжений: основной ветки вычислений, обработки ошибок и экстренной отмены вычислений. Все это разные продолжения под куполом единого значения в монаде Async.

Вот, пример примитивного вычисления функции Аккермана с кешированием промежуточных результатов:
open System.Collections.Generic

let ackermann m n =
let dict = Dictionary<_, _> ()
let fix m n x = async {
let! a = x
dict.Add ((m, n), a)
return! x
}
let rec ack m n = async {
if m = 0 then
return n + 1
elif dict.ContainsKey (m, n) then
return dict.[(m, n)]
elif n = 0 then
return! fix m n <| ack (m - 1) 1
else
let! x = ack m (n - 1)
return! fix m n <| ack (m - 1) x
}
ack m n
А это результат работы:
> ackermann 3 19 |> Async.RunSynchronously;;
Real: 00:01:15.849, CPU: 00:01:15.816, GC gen0: 1398, gen1: 515, gen2: 7
val it : int = 4194301
Без продолжений был бы явный StackOverflowException при гораздо меньших значениях n и m.

Комментариев нет:

Отправить комментарий