Парадигмы программирования, 10 лекция (от 26 ноября)

Материал из eSyr's wiki.

• Аудиозапись: http://esyr.org/lections/audio/paradigms_2009_winter/paradigms_09_11_26.ogg

Тема сегодняшней лекции — ленивые вычисления.

Когда мы изучали ленивые исчисл., у нас возн.два пордяка редукции. Один из них энергичный, второй --- ленивый. Есть ЯП, которые поддерж. ленивый порядок вычисл.

По-настоящему мы гвоорим о лнивых вычисл., когда у нас возникло выраж., вычислитель запоминает его, но вычисл. не происходит, пока это не потрбуется. Запоминается само выражение плюс котекст. Например, для языков типа лиспа контекст предст. собой набор лекс. связей, лекс. связанных с переменными значений. Соотв., не имея контекста, вычисл. выраж. невозможно, поэтому всечте с вычисл. необх. запомнить контекст. Кроме того, если у нас функции имеют побочные эффекты, то с ленивыми вычисл. у нас есть одна проблема --- мы не знаем, когда вычисл. функция, более того, если функция зависит от глоб. перем., то она в разные моменты времени может иметь разн. рез=т. Соответственно нужно в ЯП либо отказ. от побоч. эффектов, либо ленивость отдельно. Поэтому большая часть ЯП на ленивость не заточена.

Есть ЯП полностью ленивый, например, Хаскель. Он сам по себе дост. ргомоздкий, поэтому рассм. не будет. Там нет побоч.эффектов, глоб перем., и так далее, и он ленивый.

Расск. сегодня лектор ленивость на примере языка, существ. в воображ. лектора, это вариант лиспа с ленивым cons. Зачем это? Лектор хзочет показать, какие возм. открывают ленивые вычисл. Самый простейший вариант, вроде бы, эффективность. Утв., что поск. не всё вычисл., то можно иногда сэкономить. Например, опишем функцию:

(defun f(x y)
  (cond
    ((< x 10) x)
    (t        y)
  )
)

В Этой функции y может быть недовычислен. Поэтому можно туда передать y, который недовычислен. Предст., что можно передавать в функции недовыч. значения, понятно, что x должен быть вычисл., f н vj;tn ytn/

Теперь предст., что вызвали что-то такое:

(f 4 (...))

Если это обычный лисп, то второй арг. вычислится, но в ленивом лиспе это не понадобится. Например, в данном случае, до вычисл. y не пойдёт. Это может быть полезно в случае, если y может вычисл. долго. Второе --- это форма, которая может вообще не завершаться. Например, если второй арг. связан с первым, и в нек-рыз случаях (например, при x>10) оно нормально вычисл., а при меньшем десяти --- нет. В этой ситуации получается, что ленивая рез. работает, энерг. пасует.

На самом деле, выигрыш здесь кажущийся. Поск. возн. необх. хранить выражение и контекст. Если это --- альтернатива передаче целых чисел, например, то эти накл. расх. будут сравнимы, а в реальных ситуациях окажутся и выше.

Но дело, однако, отнюдь не только в эффективности. Дело в том, что лен. вычисл. позв. делать то, что энерг. вообще не позв. делать. В частности, позв. работать с беск. структурами данных. Далее лектору потребуется функция reduce:

(defun reduce (fun start list)
  (cond ((null list) start)
    (t (funcall fun (car list)
       (reduce fun start (cdr list))
  )))
)

Это правая редукция

(reduce f x '(1 2 3))

эквивалентно

(f 1 (f 2 (f 3 x)))

Давайте теперь посм. Мы знаем, что с помозью редукции можно прогр. без рекурсии операции над целым списком. Допустим, мы хотим запрогр., есть ли в списке элемент. Напр., проверить, есть ли в списке единица:

(reduce #'(lambda (elem already)
  (cond ((eql elem 1) t)
        (t already)
  ))
nil
list
)

Теперь посм.,если первый элем. списка явл. единицей (например, (1 3 5)). То он просм. весь:

(reduce fun nil '(1 3 5))

получается

(funcall fun 1 (funcall fun 3 (funcall fun 5 nil)))

А что будет при ленивом вычислении? Оно превратится в

(funcall fun 1 (reduce fun nil '(1 3 5)))

Но выражение дальше разв. не будет. Почему оно не будет? Тому що мы обратимся к этой функции, но оно не дойдёт, поск. заматчи тся единица. А если бы список был бесконечный? Несмотря на это, всё равно с ним что-то можно сделать за конеч. чичсло шагов. Что такое беск. список, что с ним можно делать? Можно считать, что у нас есть беск. список, а также инструкция, как делать остальные. То есть, мы его не сформировали, но можем за конеч. время выч. любой элемент. Здесь получаются очень удобными ленивые вычисления.

Рассмотрим функцию.

(defun from (n)
  (cons n (from (+ n 1)))
)

Понятно, что строить такую функцию в энергичном лиспе не надо. Тут есть рекурсия, но нет базиса. В ленивом лиспе при аызове будет возвр. точечная пара след. вида:

(5 . (from (+ n 1)) + контекст n=5)

Такая недовыч. пара. Если мы обр. ко второну элементу, то получим

(5 . (6 . (from (+ n 1)) + контекст n=6))

Nfrbv j,h/ vs cjplfkb gjntywbfkmyj ,tcr/ cnhernehe lfyys[. Понятно, что в памяти она имеет конеч. объём, но потенциально оно беск.

Другой пример:

(defun sum_n (n list)
  (cond ((= n 0) 0)
        (t (+ (car list)
              (sum_n (- n 1) (cdr list)))
        )
  )
)

Тогда можно запросто на вход подать беск. список:

(sum 3 (from 20))

Рез. будет 63, при условии, что у нас ленивый интерпретатор. Вычисл. очередное знач. только при очередном вызове, если же считать функцию нестрогой, то вычисл. будет при car/cdr.

Для иллюстрации хочется что-то такое вычисл. Например, решето Эратосфена. Берём все нат. числа, единицу вычёркиваем. Потом берём первое число из ост., объявл. его простым, потом вычёрк все, которые на него делятся, и заново. Обычно, понятно, это делают на конеч. посл. чисел, но мы сделаем на бесконечном. напишем функцию filter, она будет ост. только те эл-ты, которые не делятся на заданное число:

(define filter (m list)
  (cond ((null list) nil)
        ((= 0 (mod (car list) m)) (filter m (cdr list)))
        (t (cons (car list) (filter m (cdr list))))
  )
)

Что предст. собой тогда решето эратосфена:

(define sieve (list)
  (cons (car list)
        (sieve (filter (car list)
                       (cdr list)
        ))
  )
)

Что мы делаем? Берём исх. список, берём первый эл-т, выкидываем все делящиеся, всё, что осталось, соединяейм.

Как это вызвать?

(sieve (from 1))

Самое интересное, что если у нас ленивая реализация, то у нас получится беск. посл., но реально там будет 2. ..., но мы этого не увидим, поскольку как только мы туда полезем, то то, куда лезем, будет вычисляться.

То есть, получилибеск посл., но реально вычисл. только те, которые нужны.

Есть книга Филда-Гаррисона, в которой предл. расс.м ленивые вычисл. в терминах сетей процессов. Попробуем перписать функцию немного по-другому:

(defun inclist (lst)
  (cons (+ 1 (car lst))
        (inclist (cdr lst))
  )
)

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

(defun ints()
  (cons 0 (inclist (ints)))
)

Эта функция делает бес. список интов. Как это получается:

(ints) => (0 . (inclist (ints)))
       => (0 . inclist(0 . (inclist (ints))))
       => (0 1 . (inclist (ints)))

При этом сложность растёт с каждым элементом. Как это можно представить альтернативно, по краайней мере, автлры этой книжки? В виде диаграммы:

graph {
  0 -> cons;
  cons -> Ints
  cons -> inclist
  inclist -> cons
}

То есть, на выходе получается примерно такая ситуация:

graph {
 "... 5,4,3,2,1" -> inclist -> "...6,5,4,3,2"
}

Получается такая странная вещь. Что говорят авторы книжки на эту тему? В терминах такой вещи легко опис. паралл. взаимож. процессы, мы можем рассм. это дело в терминах ленивых вычислениях. Т. е., ЛВ приводит аж вот к таким вещам.

Другой вариант ints. Тут будет исп. let. Главное его непривычное свойство — x, если не объявл. в блоке, может быть иса. внешний, при это, если другая перем....

(defun ints (x) (cons 0 x))
(let* ((s1 (inclist s2))
       (s2 (ints s1)))
      s2
)

Как в рез-те будет выглядеть диаграмма:

graph {
  inclist -> ints [label "s1"];
  ints -> inclist [;abel "s2"];
}

Здесб let*, где исп. перем. из одного контекста. Получается такой хитрый цикл. Тем же самым мех. можно восп. для чисел фибоначчи. Это любимый пример, по аналогии с факториалом, выч. рекурсивно.

      1 2 3 4 ...
f_n   1 1 2 3 ... (s1)
f_n+1 1 2 3 5 ... (s2)
f_n+2 2 3 5 8 ... (s3)

(defun F(n) (cons 1 n))
(defun A (k0 k1)
  (cons (+ k0 k1)
        (A k0 k1))
)

Запустить этот процесс можно след. образом:

(let* ((s1 (F s2))
       (s2 (F s3))
       (s3 (A s1 s2))
      )
      s1
)

Лектор польз. синтаксисом лиспа, чтобы не вводить новый синтаксис.

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