Сегодня мы поговорим о рекурсивных let-биндингах в F#, которые являются неотъемлемой частью разработки на функциональных языках семейства ML. Хм, а что тут может быть вообще интересного?

Интерес представляет то, что с помощью let rec можно определять не только рекурсивные и взаимнорекурсивные функции, но ещё и рекурсивные значения. Сложно представить? На самом деле это обычное дело, например, вам надо подписаться на IObservable каким-нибудь хитрым IObserver‘ом, который должен уметь сам отписываться при определённых условиях:

open System

let source : int IObservable = ...

let rec subscription : IDisposable =
  source.Subscribe {
    new IObserver<int> with
      member o.OnNext(x) =
        if x > 0 then
          subscription.Dispose()
      ...
  }

То есть мы использовали значение subscription внутри самого определения того, чем же subscription будет на самом деле являться. Ключевой момент тут заключается в том, что все обращения к subscription внутри IObserver‘а являются отложенными, они не будут производиться во время вызова Subscribe(), иначе это приводило либо к ошибке компиляции, если компилятор может выяснить, что использование не является отложенным:

let rec foo : int = foo

error FS0031: The value ‘foo’ will be evaluated as part of its own definition

Либо результировать ошибкой времени исполнения с непонятным сообщением:

let rec foo =
    let f() = foo + 1 in f()

System.InvalidOperationException: ValueFactory attempted to access the Value property of this instance.

Вот ещё один пример рекурсивного определения значения бесконечной последовательности чисел Фибоначчи, возможного благодаря тому, что seq-выражения являются отложенными:

let rec fibs =
    seq { yield 0
          yield! Seq.scan (+) 1 fibs
    } |> Seq.cache

Или более «понятный» вариант, через сложение последовательности с самой собой, смещённой на один элемент:

let rec fibs' =
    seq { yield 0
          yield 1
          yield! Seq.map2 (+)
                    (Seq.skip 1 fibs')
                               (fibs')
    } |> Seq.cache

В любом случае компилятор F# не любит рекурсивные определения значений и ругается на них следующим предупреждением:

warning FS0040: This and other recursive references to the object(s) being defined will be checked for initialization-soundness at runtime through the use of a delayed reference. This is because you are defining one or more recursive objects, rather than recursive functions.

Которое легко прибить директивой компилятора:

#nowarn "40"

Из сообщения предупреждения сразу становится интересно (по крайней мере, мне), что же такое «delayed reference» и во что компилируются обращения к значению внутри определения его самого, а так же что происходит со значением, если во время его инициализации происходит исключение.

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

module LetRec

let rec foo =
  let neverUsed() = foo + 1
  in 0

Реально компилятор F# транлирует в примерно следующий код:

let rec private foo' =
  lazy (
    let neverUsed() = Lazy.force foo' + 1
    in 0
  )

let foo = Lazy.force foo'

Здесь всё равно присутствует let rec-привязка, но за ней больше не скрывается какая-либо логика. Тело lazy-выражения неявно становится телом функции unit -> ‘T, которая становится функцией отложенной инициализации значения, представляемого классом System.Lazy<’T>. То есть инициализация рекурсивного значения подразумевает создание отложенного значения Lazy<’T> и его последующее немедленное вычисление, при этом все обращения к значению заменяются на вычисления отложенного значения.

Логика Lazy<’T> такова, что если во время вычисления значения происходит обращение к этому же значению, то возбуждается исключение System.InvalidOperationException (иначе бы происходило зацикливание и переполнение стека), что мы наблюдали в примере выше. Если во время вычисления отложенного значения произошло исключение, то оно будет проброшено к клиентскому коду, но и будет сохранено внутри Lazy<’T> чтобы быть выброшено при возможных следующих обращениях к отложенному значению. В этом легко убедиться, если «вытащить» обращение к рекурсивному значению из кода его инициализации, например:

let mutable f = (fun() -> 0)

try
  let rec foo : int =
    f <- (fun() -> foo) // сохраняем обращение к foo в f
    failwith "uups!"    // и выбрасываем исключение

  printfn "foo = %d" foo
with e ->
  printfn "foo = %A" e.Message

foo = uups!

Если теперь обратиться к значению функционального типа f, то мы снова получим исключение:

try
  printfn "f() = %d" (f())
with e ->
  printfn "f() = %A" e.Message

f() = uups!

В итоге следует понимать, что обращения к значению внутри определения его самого обращаются в манипуляции с классом Lazy<’T>, которые имеют небольшой оверхед и могут приводить к исключениям в неожиданных местах, поэтому следует свести к минимуму вероятность возникновения исключения в коде инициализации рекурсивного значения. Старайтесь вовсе избегать использования рекурсивных значений, заменяя значения на функции или используя вспомогательные «мутабельные» средства. Например, в Rx для решения проблемы с IObserver‘ом из начала поста применяется класс MutableDisposable:

var subscribtion = new System.Disposables.MutableDisposable();

subscribtion.Disposable = source.Subscribe(x => {
  if (x > 0) subscribtion.Dispose();
});