Возможно ли запоминание без побочных эффектов

У меня есть код F#, который кэширует результаты для будущего поиска. Насколько я понимаю, словари и другие структуры данных, которые вы добавляете, требуют побочных эффектов. (т.е. изменение состояния словаря) Это правильно? Считается ли это нечистым или это все еще в модели вычислений без побочных эффектов.

let rec fib =
    let dict = new System.Collections.Generic.Dictionary<_,_>()
    fun n ->
        match dict.TryGetValue(n) with
        | true, v -> v
        | false, _ -> 
            let fibN =
                match n with
                | 0 | 1 -> n
                | _ -> fib (n - 1) + fib(n - 2)
            dict.Add(n, fibN)
            fibN

f# functional-programming memoization side-effects
person t3dodson    schedule 26.05.2015    source источник
comment
Мой F # может быть немного заржавевшим, но я не понимаю, как последовательные вызовы fib могут совместно использовать экземпляр dict для обеспечения кэширования. Разве каждый вызов функции не получит свой экземпляр dict?   -  person CoderDennis    schedule 27.05.2015
comment
@CoderDennis Это закрытие dict. Слово fib связано с лямбда-функцией, которая реализует логику. Каждый вызов разделяет привязку dict   -  person t3dodson    schedule 27.05.2015
comment
Проблема с побочными эффектами заключается в масштабах и способности рассуждать о том, как функционирует система. Вот почему глобальные переменные являются абсолютным злом. Сама функция Фибоначчи не имеет побочных эффектов. Тот факт, что это имеет побочные эффекты в реализации, не имеет значения.   -  person N_A    schedule 27.05.2015
comment
@mydogisbox не будет dict.TryGetValue(n) подвержен побочным эффектам. Не в этом примере, а вообще. Потому что состояние некоторого места в памяти влияет на значение времени выполнения. Если, например, я сохранил неправильное значение в dict при первом вызове, но вернул правильное значение. Во второй раз, когда я назову это, я получу неправильное значение.   -  person t3dodson    schedule 27.05.2015
comment
@TomDDD: вы не можете сохранить неправильное значение в словаре, если (фактическая) функция чистая, потому что есть только одно значение, которое функция может создать для данного аргумента.   -  person scrwtp    schedule 27.05.2015
comment
@mydogisbox предположим, что мой вызов dict.Add прошел так. dict.Add(n, fibN - 1) Тогда при первом вызове fib 1 я получу 1, второй вызов даст мне 0. Я пришел к выводу, что это имеет побочные эффекты. Он просто ведет себя так, как ожидалось, потому что структура правильная.   -  person t3dodson    schedule 27.05.2015
comment
@TomDDD: Кроме того, я бы предложил переместить биты запоминания в специальную функцию запоминания более высокого порядка. Делая это, вы на самом деле можете сделать мемоизированную функцию чистой, а мемоизацию — деталью реализации. Код, который вы разместили, где эти две проблемы связаны друг с другом, не так прост для размышлений, как мог бы быть.   -  person scrwtp    schedule 27.05.2015
comment
@scrwtp Я думаю, это то, к чему я стремился. Довольно легко создать функцию запоминания, которая берет функцию и возвращает запомненную копию. Это было бы похоже на то, что внутренняя функция (fib) была бы чистой. Он понятия не имеет, что такое побочный эффект. Но поскольку вы вызываете запомненный, он знает, как уменьшить количество вызовов чистой функции.   -  person t3dodson    schedule 27.05.2015
comment
@TomDDD Теперь я вижу. Спасибо за объяснение.   -  person CoderDennis    schedule 27.05.2015

Ответы (2)


arrow_upward
5
arrow_downward

Чтобы повторить то, что было упомянуто в комментариях, вы можете извлечь мемоизацию в функцию более высокого порядка, которая вернет мемоизированную версию функции, переданной в качестве аргумента:

let memoize f =
    let dict = new System.Collections.Generic.Dictionary<_,_>()
    fun x ->
        match dict.TryGetValue(n) with
        | true, v -> v
        | false, _ ->
             let v = f x
             dict.Add(x, v)
             v

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

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

Отдельной проблемой здесь являются проблемы параллелизма, с которыми вы можете столкнуться. Чтобы бороться с ними, вы можете заблокировать dict.Add:

...
let v = f x
lock dict <| fun () ->
    if not <| dict.ContainsKey(x) then
       dict.Add(x, v)
v

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

person scrwtp    schedule 27.05.2015

arrow_upward
1
arrow_downward

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

Чтобы ответить на ваш комментарий о сохранении неправильного значения в dict; да, вы правы, но есть еще одна проблема, которая не связана с неправильными результатами. Класс Dictionary не является потокобезопасным. Если два потока попытаются читать и/или писать в словарь одновременно, вы, скорее всего, получите исключение. Например:

let data = [| 1 .. 20 |]
let fibs = data |> Array.Parallel.map fib

У меня не было никаких исключений, когда я запускал это несколько раз в интерактивном F #, но с некоторыми изменениями я получил System.ArgumentException:

Элемент с таким ключом уже добавлен.

Изменения заключались в следующем; в каждом случае я получил исключение с первой или второй попытки:

  • Включите функцию печати диагностической информации с помощью printfn
  • Измените числовой тип на uint64 (удалив диагностику printfn)
  • Измените числовой тип на float (т. е. System.Double).
  • Измените числовой тип на bigint
person phoog    schedule 26.05.2015