Декларативное программирование

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]

© 2003 И.А. Дехтяренко

5.7. Потоки и ленивые вычисления.

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

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

С абстрактной точки зрения потоки подобны спискам. Как абстракция данных список характеризуется набором функций (cons car cdr nil empty?). Аналогичный  набор для потока состоит из конструкторов (cons-stream the-empty-stream) и селекторов (head tail empty-stream?). Условия, которым должны удовлетворять эти функции совпадают с теми, которые выполнятся для списков. Единственное различие - время, когда вычисляются элементы последовательности. Для списка и голова и хвост вычисляются при создании списка. Хвост потока вычисляется в момент использования.

Для реализации потоков воспользуемся специальной формой называемой задержкой. Форма(delay e) не вычисляет выражение e, а возвращает специальный объект - "обещание" (promise) вычислить значение e, когда потребуется. Процедура force, получает такой объект в качестве аргумента и выполняет обещание, то есть   вычисляет значение выражения.

(define prom (delay (+ 2 3)))
prom
<promise>
(force prom)
5

Специальная форма cons-stream  определяется так, что(cons-stream a b) эквивалентно (cons a (delay b)). Таким образом, мы создаём потоки, используя пары. Однако, в отличие от списков, второй элемент пары содержит не оставшуюся часть последовательности, а обещание вычислить эту часть, если она когда-либо потребуется. Теперь можно определить процедуры head и tail:

(define (head s) (car s))
(define (tail s) (force (cdr s)))

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

(define the-empty-stream nil)
(define empty-stream? null?)

Обратите внимание, мы не можем определить cons-stream как процедуру. Если мы запишем (define (cons-stream a b) (cons a (delay b)), то при вызове (cons-stream a b)значения a и b будут вычислены до вызова cons-stream и применение задержки потеряет всякий смысл. Некоторые реализации уже содержат встроенную форму cons-stream. Если же это не так, мы можем воспользоваться механизмом макросов.

(define-syntax cons-stream
   (syntax-rules ()
       ((_ a b) (cons a (delay b)))))

Выглядит несколько устрашающе, но в действительности, это - всего лишь правило, преобразующее всякое вхождение выражения вида (cons-stream a b) в выражение  (cons a (delay b)). Например, поток из трёх чисел 1 2 3 может быть создан как

(define s123
   (cons-stream 1
                (cons-stream 2
                             (cons-stream 3 the-empty-stream)))

Что будет преобразовано в

(define s123
   (cons 1
        (delay (cons 2
                     (delay (cons 3
                                  (delay the-empty-stream)))

Мы можем обращаться с потоками, так же,  как со списками.

(head s123)
1
(head (tail s123))
2

(define (elem-no n s)
  (if (= n 1)
      (head s)
      (elem-no  (- n 1) (tail s))))

(elem-no 1 s123)
1
(elem-no 2 s123)
2

Особенно наглядно отношение между потоками и списками проявляется в следующих двух функциях.

(define (stream->list s)
   (if (empty-stream? s)
       nil
       (cons (head s) (stream->list (tail s)))))

(define (list->stream l)
    (if (null? l)
        the-empty-stream
        (cons-stream (car l) (list->stream (cdr l)))))

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

(define (stream-add s1 s2)
 (if (or (empty-stream? s1) (empty-stream? s2))
     the-empty-stream
     (cons-stream  (cons-stream  (+ (head s1) (head s2))
                   (stream-add (tail s1) (tail s2))))

(stream->list(stream-add s123 s123))
(2 4 6)

(define (stream-range m n)
   (if (> m n)
       the-empty-stream
       (cons-stream m
                   (stream-range (+ m 1) n))))

(stream->list(stream-range 1 5))
(1 2 3 4 5)

(elem-no 4 (stream-range 1 1000))
4

Чтобы почувствовать разницу, давайте рассмотрим процесс вычисления последнего выражения. Сначала вызывается функция stream-range, которая возвращает пару
(1 . "обещание вычислить (stream-range 2 1000)").
Затем  elem-no  пытается вычислить хвост этой пары, что приводит к новому вызову stream-range, которая теперь уже возвращает пару
(2 . "обещание вычислить (stream-range 3 1000)").
Процесс продолжается, пока не будет получена пара
(4 . "обещание вычислить (stream-range 5 1000)").
Поскольку именно эта четвёрка и требовалась функции elem-no, на этом она завершит свою работу и больше не будет требовать выполнения обещаний. Таким образом, остаток потока никогда не будет вычислен, что экономит массу времени и пространства.

Упражнение.

Обобщите функцию stream-add до функции (stream-map2 op s1 s2)последовательно применяющую бинарую оперaцию op ко всем парам элементов из s1 и s2.

Упражнение.

Определите набор функций, аналогичных функциям fold,scan,map и т.п.

Упражнение.

Возможно, кому то захочется представлять пустой поток не пустым списком, а специальным атомом, например:
(define the-empty-stream 'the-empty-stream).
Что потребуется изменить в реализации потоков?

Упражнение.

Мы применяли задержку только ко второму элементу пары, но возможны и другие реализации. Выражение (cons-stream a b) можно преобразовывать в (cons (delay a) (delay b)) или в (delay (cons a b)). Определите соответствующие варианты процедур head и tail.

О реализации delay и force

Хотя операции delay и force могут показаться несколько таинственными, в действительности их реализациия довольно проста. Задержка должна "упаковать" выражение так, чтобы его можно было вычислить позже, и мы можем сделать это, преобразовав выражение в процедуру без параметров. То есть, мы определяем специальную форму delay, таким образом, что выражение (delay a) преобразуется в (lambda () a). Теперь force просто вызывает процедуру без параметров созданную delay, так что мы можем определить её как процедуру:

(define (force promise) (promise))

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

Бесконечные потоки.

Как мы видели, при вычислениях с потоками происходят замысловатые передачи управления. Однако, нет необходимости вникать в эти тонкости. Когда мы вычисляли (elem-no (stream-range 0 100) 4), мы представляли себе последовательность чисел от 0 до 100 как реально существующую, хотя в действительности, вычислялись только первые четыре элемента. Интересно, что точно так же мы можем представлять потоками бесконечные последовательности, такие как:

(define (ones)
   (cons-stream 1 (ones)))

Это определения выглядит подобно ad-infinitum, но оно вполне осмыслено. Вызов (ones) возвратит пару, из единицы и обещания вычислить (ones). Таким образом, мы имеем бесконечно длинный поток единиц. Естественно, работа с бесконечными потоками требует определённой осторожности. Так, попытка вычислить длину такого потока приведёт к зацикливанию программы. Однако, если обращаться только к конечному числу элементов, работа даже с бесконечными потоками практически не отличается с работой со списками.

(elem-no 5 (ones))
1

(define (integers-from n)
   (cons-stream n (integers-from (+ n 1))))

(define ints (integers-from 1))

(elem-no 5 ints)
5

Поскольку применение функции stream->list к бесконечным потокам бессмысленно, мы определим похожую функцию, возвращающую список из первых n элементов потока.

(define (initial n s)
  (if (= n 0)
      (list)
      (cons (head s) (initial (- n 1) (tail s)))))

(initial 5 (stream-add ints (ones)))
(2 3 4 5 6)
(initial 5 (stream-map sqr ints)))
(1 4 9 16 25)
(initial 5 (stream-filter even? ints)))
(2 4 6 8 10)

Эти потоки определялись с помощью процедуры, генерирующей элементы потока один за другим. Но отложенные вычисления позволяют делать неявные определения.

(define ones (cons-stream 1 ones))

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

(define ints
   (cons-stream 1 (stream-add ones ints)))

Это определение гласит, что ints - поток, первый элемент которого 1, а остальная часть, является суммой потоков ones и ints. Таким образом, второй элемент ints - 1 плюс первый элемент ints, то есть 2; третий элемент ints - 1 плюс второй элемент ints то есть 3. и т. д.

Упражнение.

Какую последовательность описывает следующее определение?
(define x-stream
   (cons-stream 1 (stream-add x-stream x-stream)))

Еще раз о числах Фибоначчи.

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

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

(define fibs
   (cons-stream 1
                (cons-stream 1
                             (stream-add (tail fibs) fibs))))

(define (fib n) (elem-no n fibs))

Простые числа.

Следующий пример - поток простых чисел. Его можно можно построить, отфильтровав поток целых чисел с помощью предиката prime?, который проверяет, делится ли n на какое либо число, меньшее или равное корню из n:

(define primes
   (stream-filter prime? (integers-from 2)))

(define (prime? n)
   (define (nodiv? m limit)
      (or (> m limit)
          (and (not (= (remainder n m) 0))
               (nodiv (+ m 1) limit))))
   (nodiv? 2 (sqrt n)))

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

(define primes
   (cons-stream 2 (stream-filter prime? (integers-from 3))))

(define (prime? n)
   (define (nodiv? s limit)
      (or (> (head s) limit)
          (and (not (= (remainder n (head s)) 0))
               (nodiv (tail s) limit))))
   (nodiv? primes (sqrt n)))

Это определение рекурсивно, так как поток primes определяется через предикат prime?, который в свою очередь использует primes. Но в любой момент созданной части потока достаточно для проверки простоты очередного числа.

Упражнение.

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

(define primes (sieve (integers-from 2)))
(define (sieve s)
   (cons-stream (head s)
                (sieve (stream-filter <...> (tail s)))))

Представление итераций потоками.

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

(define (iterate f x)
   (cons-stream x (iterate f (f x))

Процедура limit, получает поток, находит в нем пару последовательных значений, отличающихся менее, чем на заданный допуск и возвращает второе из них, вычисляя, таким образом, предел последовательности.

(define (limit s)
   (let ((a (head s))
         (r (tail s))
         (b (head r)))
        (if (near? a b) b (limit r)))))

(define err 0.000001)
(define (near? x1 x2)
   (< (abs (- x1 x2)) err))

Собирая вместе, получаем новую реализацию fixed-point.

(define (fixed-point f x)
    (limit (iterate f x)))

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

Потоки в задачах моделирования.

Обычно мы моделируем состояния реальных объектов изменяемыми переменными. Изменению состояния объектов при этом соответствует изменение значений переменных. Таким образом, течение времени в реальном мире отождествляется с изменением времени в компьютере. Казалось бы, отсутствие оператора присваивания резко затрудняет решение задач моделирования. Но потоки предоставляют нам мощный инструмент для таких задач.

С математической точки зрения изменяющееся во времени значение x может быть описано как функция времени x(t). Если мы сосредотачиваемся на значениях x от одного момента времени к другому, мы думаем об x, как о переменной величине. Но, если мы рассматриваем хронологию значений в целом, мы видим что сама функция не изменяется! Если время измеряется дискретными шагами, то мы можем моделировать функцию времени (возможно бесконечным) потоком.

Рассмотрим задачу моделирования RS-триггера, описанную в [1]. Моделируемая система состоит из двух элементов И-НЕ, соединённых по следующей схеме.

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

Q_t+1 = ¬(S_t & P_t) , P_t+1 = ¬(R_t & Q_t).

Мы будем моделировать сигналы значениями 0 и 1, поэтому определим операцию.

(define (not-and x y) (- 1 (* x y)))

Теперь опишем взаимосвязи между потоками. Начальные значения выходных сигналов положим равным 0.

(define Q (cons-stream 0 (stream-map2 not-and S Q)))
(define P (cons-stream 0 (stream-map2 not-and R P)))

Осталось задать входные сигналы,

(define S (repeat 1))
(define R (repeat 1))

и можно любоваться результатами.

(initial 10 q)
(0 1 0 1 0 1 0 1 0 1)

Ленивые вычисления

Использование задержек открывает нам новые возможности, но в то же время создаёт дополнительные сложности. Нам приходилось иметь дело с двумя структурами данных и двумя разновидностями процедур: процедурами для списков и для потоков. Но мы могли бы применить задержки и к другим структурам, так что многие процедуры обзавелись бы двойниками, параметры которых - отложенные выражения. Мы могли бы избежать необходимости в двух различных классах процедур, если бы сделали все процедуры принимающими отложенные аргументы. Тем самым, мы полностью изменили бы стратегию вычислений и преобразовали бы наш язык программирования, в "ленивый" язык с нормальным порядком редукции. Это обеспечило бы однородный и изящный способ упростить использование отложенных вычислений.

Почему же это не было сделано с самого начала? Кроме упоминавшихся уже соображений эффективности, есть ещё одна важная проблема. Ленивые вычисления вступают в конфликт с императивным стилем программирования. Как можно было видеть на примере потоков, чрезвычайно трудно проследить последовательность выполнения операций. Для нас это не было существенным, поскольку мы писали чисто функциональные программы. Но Лисп, подобно многим другим (в том числе функциональным) языкам, предоставляет возможность писать программы с использованием присваиваний, циклов и т. п. Причём, эта возможность широко используется. Но написать программу, зависящую от порядка событий и в то же время использующую ленивые вычисления - задача нереальная. Поэтому, возможность использования отложенных вычислений отдана но откуп программисту, в надежде, что тот сумеет правильно ею распорядиться.

[1] В.С. Любченко "Искусство программирования ... RS-триггера?!" http://www.softcraft.ru/auto/ka/rsm/rsm01/

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]