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

[ Содержание | 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.6. Последовательности как стандартные интерфейсы.

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

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

1. (sum-int m n)суммa целых чисел от m до n.
2. (sum-list l) суммa элементов списка..
3. (sum-tree t) суммa листьев дерева.

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

Создать список целых чисел от m до n можно с помощью следующей процедуры.

(define (range m n)
   (if (> m n)
       nil
       (cons m (range (+ m 1) n))))
(range 1 5)
(1 2 3 4 5)

Чтобы перечислить листья дерева, мы можем использовать процедуру flatten.

(define (flatten t)
   (cond ((null? t) null)
         ((atom? t) (list t))
         (else (append (flatten (car t))
                       (flatten (cdr t))))))

Теперь определениям трёх функций можно придать единообразную форму.

(define (sum-list l)    (fold + 0 l)

(define (sum-int m n)   (fold + 0 (range m n))

(define (sum-tree t)    (fold + 0 (flatten t))

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

(define (sum-sqr-odd t)
   (cond ((null? t) 0)
         ((not (pair? t))
            (if (odd? t) (sqr t) 0))
         (else (+ (sum-sqr-odd (car t))
                  (sum-sqr-odd (cdr t))))))

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

(define (sum-sqr-odd t)
   (fold +
         0
         (map sqr
              (filter odd?
                      (flatten t)))))

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

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

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

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

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

Факториал числа n можно вычислить как произведение всех чисел от 1 до n.

(define (fac n)
   (foldl * 1 (range 1 n))

Функции накопления accr и accl легко определяются с помощью свертки, например:

(define (accr op e f m n)
   (foldr op e (map f (range m n)))

Две функции foldl1 и foldr1, выполняют свертки на непустых списках. Они не имеют аргумента, задающего базовое значение, но используют в этом качестве первый (последний) элемент списка.

(define (foldl1 op l)
   (foldl op (car l) (cdr l)))

Упражнение.

Определите функцию foldr1.

С их помощью определения некоторых функций упрощаются.

(define (maximum l)  (foldl1 max l))
(define (minimum l)  (foldl1 min l))

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

(define (sum l)  (foldl1 + l))

мы уже не сможем применять её к пустым спискам.

Упражнение.

Пусть функция (enum-personal) возвращает последовательность записей о персонале, селектор (salary r) возвращает зарплату, а предикат (programmer? r) проверяет, что данная запись относится к программисту. Напишите функцию, вычисляющую зарплату самого высокооплачиваемого программиста.

Функции семейства scan подобно функциям fold последовательно применяют бинарную операцию, но возвращают последовательности результатов, то есть подобно  map отображают списки на списки.

(define (scanl op a l)
   (cons a
         (if (null? l)
             nil
             (scanl op (op a (car l)) (cdr l)))))


(scanl + 0 (list 1 2 3 4))
(0 1 3 6 10)

(define (scanl1 op l)
   (if (null? l)
       nil
       (scanl op (car l) (cdr l))))

(scanl1 +  (list 1 2 3))
(1 3 6 10)

С помощью этих функций можно создавать элементы чувствительные к истории. Например, форме (scan1 + l) на "электронной схеме" соответствовал бы "интегратор".

Упражнение.

Пусть дано начальное значение некоторой величины и последовательность изменений. Напишите предикат (correct? s0 l) проверяющий, что в процессе изменений значение никогда не становится отрицательным.
Например:
(correct? 10 (list 2 -8 3 -5))
#t
(correct? 10 (list 2 -8 -5 3))
#f

Упражнение.

Определите функции scanr и scanr1 выполняющие вычисления справа налево.
Например:
(scanr + 0 (list 1 2 3 4))
(10 9 7 4 0)

(scanr1 + (list 1 2 3))
(10 9 7 4)

Мы могли бы определить функцию (map2 f l1 l2), применяющую функцию двух аргументов f к парам элементов из списков l1 и l2, а также аналогичные функции map3, map4..., но в этом нет необходимости. Встроенная функция map допускает произвольное количество аргументов.

(map + (list 1 2 3) (list 4 5 6))
(5 7 9)

(map + (list 1 2 3) (list 1 2 3) (list 1 2 3) )
(3 6 9)

(map + (list 1 2 3 4 5) (list 6 7))
(7 9)
(map list '(a b) '(1 2 3 4 5))
((a 1) (b 2))

Как видно, "лишние" элементы просто игнорируются. Используя эти свойства, легко определить сумму и скалярное умножение векторов, представленных списками или предикат, проверяющий что последовательность является упорядоченной¹.

(define (vector-sum u v)
   (map + u v))

(define (scalar-product u v)
  (foldr + 0 (map * u v)))

(define (ordered? l)
   (foldl1 and (map <= l (cdr l))))

Такого рода элементам также можно придать электронную аналогию. Форме (map + u v) соответствует "сумматор" с двумя входами. Нетрудно представить себе "сумматор" и с большим числом входов, "компаратор" соответствующий (map - u v) и т.п.

Ещё одна вариация на тему map могла бы получать аргументы в виде списка списков. Не столь уж трудно дать определение и такой функции, но проще воспользоваться встроенной функцией apply².

(apply map + (list (list 1 2) (list 3 4)))
(4 6)

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

(define (matrix-sum A B)
   (map vector-sum A B))

(define (matrix-apply A v)
   (map (lambda (x)(scalar-product v x)) A))

(define (transpose A)
   (apply map list A)

(define (matrix-product A B)
   (let ((B-tr (transpose B)))
        (map (lambda (x)(matrix-apply B-tr x)) A)))

Упражнение.

Определите функции умножения вектора на число и матрицы на число.

Комбинаторные функции

Определённый интерес представляют функции, определенные на списках и не использующие никаких свойств их элементов. Понятно, что число таких функций ограничено. В сущности, они могут возвращать часть списка или просто переупорядочивать его элементы, как это делают cdr или reverse. Другой пример: функция rotl, которая "вращает" список, переставляя его голову в конец.

(define (rotl l)
    (append (cdr l) (list (car l))))

Упражнение.

Определите функцию rotr, вращающую список в другую сторону.

К этому же классу относятся комбинаторные функции, возвращающие списки списков. Например, prefixes и suffixes находят все "префиксы" и "суффиксы" последовательности, то есть фрагменты, которыми она начинается и заканчивается.

(define (prefixes l)
   (if (null? l)
       nil
       (cons l (prefixes (init l) ))))

(define (suffixes l)
   (if (null? l)
       nil
       (cons l (suffixes (cdr l)))))

(suffixes (list 1 2 3 4))
((1 2 3 4) (2 3 4) (3 4) (4))

(prefixes (list 1 2 3 4))
((1 2 3 4) (1 2 3) (1 2) (1))

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

(define (subsequences l)
   (foldl append nil (map prefixes (suffixes l))))

(subsequences (list 1 2 3 4))
((1 2 3 4) (1 2 3) (1 2) (1) (2 3 4) (2 3) (2) (3 4) (3) (4))

Упражнение.

Естественно включать пустой список в число подпоследовательностей. Исправьте описанные функции соответствующим образом.

Несколько сложнее задача поиска всех перестановок данной последовательности. Нам поможет следующее наблюдение: из каждой перестановки A множества M мы можем получить ряд перестановок множества M U {x}, вставляя x в разные места A. Например, из  (a₁,a₂), получим {(x,a₁,a₂), (a₁,x,a₂), (a₁,a₂,x)}. Соответствующую функцию назовем interleaves. Таким образом, если известны все перестановки множества M, то можно найти все перестановки множества M U {x}, применяя interleaves к каждой из них и объединяя результаты.

(define (interleaves x l)
  (if (null? l)
      (list (list x))
      (cons (cons x l)
            (map (lambda (y) (cons (car l) y))
                 (interleaves x (cdr l))))))

(define (permutations l)
    (if (null? l)
       (list nil)
       (foldl1 append
               (map (lambda (a) (interleave (car l) a))
                    (permutations (cdr l))))))

Теперь мы можем отсортировать список, сгенерировав все его перестановки и выбрав из них упорядоченную

(define (crazy-sort l)
   (car (filter ordered? (permutations l))))

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

Упражнение.

Примените функцию permutations к решению задачи о 8-ми ферзях.

Автоматы

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

Для задания автомата достаточно определить его начальное состояние и пару функций: функцию переходов и функцию выходов. В качестве элементарных примеров рассмотрим два автомата у которых  множества состояний, входных и выходных сигналов состоят из двух элементов - 0 и 1. Первый автомат (A) задерживает сигнал на один такт, второй (B) переключается из одного состояния в другое сигналом "1" и выдаёт на выход своё состояние. Начальным состоянием для обоих автоматов положим "0". Для таких простых автоматов не стоит связываться с таблицами переходов, а можно прямо закодировать функции.

(define a-init 0)
(define (a-trans s x) x)
(define (a-out s x) s)

(define b-init 0)
(define (b-trans s x) (if (= x 1) (- 1 s) s))
(define b-out b-trans)

Нам понадобится некий аналог функции map для автоматов. Эта функция (назовём её auto-run) будет "применять" автомат к последовательности входных сигналов и отображать её в последовательность выходных сигналов. Функция имеет четыре аргумента (функцию переходов, функцию выходов, состояние и список входных сигналов) и возвращает список выходных сигналов.

(define (auto-run ft fo st in)
   (if (null? l)
       nil
       (cons (fo st (car in))
             (auto-run ft fo (ft st (car in)) (cdr in)))))

(auto-run b-trans b-out b-init (list 1 1 1 1 1))
(1 0 1 0 1)

Мы можем применять эту функцию прямо, подобно map, но интереснее создавать автоматы и потом применять их. Функция auto получает три аргумента, описывающие автомат и возвращает "сам автомат", то есть функцию, определяющую его поведение.

(define (auto ft fo s0)
    (lambda (l) (auto-run ft fo s0 l)))

С её помощью мы можем определять автоматы, а затем применять их к последовательностям сигналов.

(define au-a (auto a-trans a-out a-init))
(define au-b (auto b-trans b-out b-init))

(define test-in (list 0 0 0 1 1 1 1 1))
(au-b test-in)
(0 0 0 1 0 1 0 1)
(au-b (au-a test-in))
(0 0 0 0 1 0 1 0)

Можно видеть, что определение auto-run не зависит от того, что мы применяем его к конечным автоматам. Оно подходит для более широкого класса систем, выход которых определяется входом и текущим состоянием.

Упражнение.

Реализуйте какой-нибудь автомат с памятью, например стековый автомат.

Упражнение.

Наш автомат B представляет собой так называемый автомат Мура - его выход совпадает с текущим состоянием, то есть функции переходов и выходов совпадают. Таким образом на каждом шаге два раза вычисляется одно и то же выражение. Дайте более эффективное определение auto-run специально для таких случаев.

Частичные применения функций.

Возможно вы обратили внимание на формы вида  (map (lambda(x)(f a x)) l). Здесь из бинарной функции f создаётся унарная функция, требуемая  map, путём частичного применения f к аргументу a. Этот образец встречается так часто (особенно при обработке списков), что его можно выделить в функцию высшего порядка.

(define (part-apply f a)
   (lambda (x) (f a x)))

(map (part-apply + 1) (list 1 2 3))
(2 3 4)

Можно дать и более общее определение, пригодное для функции большей арности.

(define (part-apply f a)
   (lambda x (apply f a x)))

Теперь, можно придать определеням функций более прямой вид.

(define (matrix-apply A v)
   (map (part-apply scalar-product v) A))

(define (matrix-product A B)
    (map (part-apply matrix-apply (transpose B)) A))

Упражнение.

Почему в первом определении умножения матриц применялась конструкция let, а во втором - нет?

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

(define maximum  (part-apply foldl1 max))

(define sum (part-apply (part-apply foldl +) 0))

(define (auto ft fo s0)
    (part-apply
        (part-apply
            (part-apply auto-run ft)
            fo
         s0)))))

Упражнение.

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

Карринг

Стоит рассмотреть и другую методику, которая непопулярна в Лиспе, но широко применяется в некоторых других языках. Дело в том, что в математике "первично" понятие функции как отображение из одного множества в другое. Функция двух аргументов трактуется как отображение из множества пар, функция трёх аргументов - отображение из множества троек и т.д. (В Лиспе все функции, в сущности, определены на множестве списков). Другая трактовка была предложена Фреге, затем переоткрыта Шёнфинкелем, и ещё раз переоткрыта Карри, в честь которого и получила название "карринг". Бинарная функция рассматривается как функция одного аргумента, возвращающая функцию одного аргумента. Аналогично функция нескольких аргументов рассматривается как функция одного аргумента, возвращающая функцию, возвращающую функцию,... возвращающую функцию одного аргумента. Например, "каррированую" функцию сложения можно определить так.

(define (<+> x)
   (lambda (y)  (+ x y)))

(<+> 1)
<procedure>

((<+> 1) 2)
3

(map (<+> 1 ) (list 1 2 3))
(2 3 4)

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

(define (curry f)
   (lambda (x) (lambda (y) (f x y))))

(define (uncurry f)
   (lambda (x y) ((f x) y)))

(map ((curry +) 1 ) (list 1 2 3))
(2 3 4)

В Лиспе применение карринга делает программы несколько громоздкими, но в таких языках как ML, Miranda, Haskell, где большинство функций определено в каррированой форме, а синтаксис требует меньшего количества скобок, он выглядит вполне естественно.

¹ Использование специальных форм, таких как and, в качестве аргумента функции может вызвать проблемы. Некоторые реализации не позволяют этого делать. Другие позволяют, но при этом таинственным образом портят внутренние структуры данных интерпретатора. В таких случаях можно определить "обычную" функцию конъюнкции, например (define (& a b) (and a b)).

² Эта функция получает функцию f и список l и вызывает f с элементами списка в качестве параметров. То есть, (apply f (l₁...l_n)) = (f l₁...l_n). Другая форма вызова - обобщение первой: (apply f a₁...a_m (l₁...l_n)) = (f a₁...a_m l₁...l_n), например:

(apply + (list 1 2 3))
6
(apply list 0 (list 1 2 3))
(0 1 2 3)

Кроме того, в некоторых вариантах Лиспа (но не в Scheme) она позволяет вызывать функции по имени:  (apply '+ (list 1 2)), что используется, например, при создании метаинтерпретаторов.

Стоит отметить определённое сходство в использовании форм типа (apply + l)и (foldl1 + l). В обоих случаях мы получим один и тот же результат, но смысл этих форм совершенно разный. В первом случае мы пользуемся специфической особенностью процедуры +, а во втором применяем весьма общую методику.

[ Содержание | 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 | Литература ]