[ИУ9] Основы информатики

Лекция 9б. Мемоизация и нестрогие вычисления

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

В общем случае нужно мемоизировать чистые функции: детерминированные и без побочных эффектов. Обоснование:

• Нет смысла мемоизировать функцию (read port) — она на каждом вызове должна выдавать очередное значение из файла.
• Нет смысла мемоизировать функцию (display message), т.к. она должна выполнять побочный эффект.

Пример мемоизации «нечистой» функции. Функция (get-messages lang-id) загружает из файла ресурсов сообщения программы на некотором языке. В процессе работы программы пользователь может залезть в настройки и поменять выбранный язык. Если функцию вызывать при каждой потребности вывести на экран сообщение, то она будет многократно читать один и тот же файл. Если загружать все ресурсы для всех языков в начале работы программы, то будут загружены лишние ресурсы. Приемлемый вариант — мемоизировать вызовы get-messages.

Приём мемоизации в Scheme. Пусть нам нужно мемоизировать функцию вида

(define (func x y z)
  (+ x y z))

Данная функция должна при вызове с ранее известными аргументами «вспоминать» свой результат, не вычисляя его заново. Но если аргументы новые, она должна результат вычислить и запомнить его.

Для этой цели нам нужно некоторое хранилище, где мы будем сопоставлять аргументы с вычисленными результатами. Для этой цели проще всего использовать ассоциативный список. Делать хранилище открытым тоже не стоит — снаружи должна быть видна только функция func (хороший стиль — минимизировать область видимости переменных). Соответственно, будем использовать приём статических переменных в языке Scheme:

(define func-memo
  (let ((known-results '()))
    (lambda (x y z)
       ...)))

Если значения аргументов есть в хранилище, то нужно вернуть известный результат. Если нет — вычислить и положить в список known-results:

(define func-memo
  (let ((known-results '()))
    (lambda (x y z)
      (let* ((args (list x y z))
             (res (assoc args known-results)))
        (if res
            (cadr res)
            (let (res (+ x y z))
              (set! known-results (cons (list args res) known-results))
              res))))))

Так мы запоминаем все предыдущие значения. Иногда функция часто вызывается с теми же значениями, которые были в прошлый раз. Тогда имеет смысл запоминать только последнее значение:

 (define func-memo-last
   (let ((last-arg #f)
         (known-result #f))
      (lambda (x y z)
        (let ((arg (list x y z)))
          (if (equal? arg last-arg)
            known-result
            (let ((res (+ x y z)))
              (set! last-arg arg)
              (set! known-result res)
              res))))))

Строгие вычисления — аргументы функции полностью вычисляются до того, как эта функция вызывается. Вызовы процедур в Scheme всегда строгие. Строгую стратегию вычислений часто называют call-by-value.

В случае нестрогих вычислений значения выражений могут вычисляться по необходимости, их вызов может быть отложен.

Примеры нестрогих вычислений:

• (if cond then else) — вычисляется либо then, либо else.
• (and …), (or …).
• В языке Си логические операции &&, || тоже не строгие.

В теории рассматривают две разновидности нестрогих вычислений:

• call-by-name, вызов по имени — нормальная редукция в лябмда-исчислении,
• call-by-need, вызов по необходимости — ленивые вычисления.

В некотором смысле разновидность call-by-name — макроподстановка:

(define-syntax double
  (syntax-rules ()
    ((double x) (+ x x)))

(define-syntax ++
  (syntax-rules ()
    ((++ var) (begin (set! var (+ var 1))
                     var))))

(define x 10)

(double (++ x))  ;; выведет 23
x                ;; выведет 12

Вызов по имени в Алголе-60

function sum(i, start, end, val): real;
    integer i, start, end;
    real val;
    value start, end;
begin
  real res := 0;
  for i := start to end do
    res := res + val;

  comment почему нельзя res := (end - start + 1) * val?;

  sum := res
end;

function square(x): real;
     integer x;
begin
  square := x * x;
end;

real temperature[1 : 100];

integer k;

print(sum(k, 1, 10, square(k)));
print(sum(k, 1, 100, temperature[k]) / 100);

Пример стратегии call-by-need — ленивый язык программирования Хаскель

test xs = head (map (\x -> x*x) xs)

Будет вычисляться квадрат только самого первого элемента списка.

Примитивы Scheme для обеспечения ленивых вычислений

Это макрос (delay expr) и функция (force promise). Макрос delay принимает выражение и формирует обещание (promise) вычислить это выражение, когда потребуется. force вычисляет этот promise, результат мемоизируется.

В первом приближении:

(define-syntax delay
  (syntax-rules ()
    ((delay expr) (lambda () expr))))

(define (force promise)
  (promise))

С мемоизацией:

(define-syntax delay
  (syntax-rules ()
    ((delay expr) (list #f (lambda () expr)))))

(define (force promise)
  (if (car promise)
      (caar promise)
      (begin
        (set-car! promise (list ((cadr promise))))
        (caar promise))))